>> - You cannot select the top N rows according to criterion A ordering
>>   the results with a different criterion B.

> True, but I don't see how to do that with one indexscan (for that
> matter, I don't even see how to express it in the SQL subset that
> we support...)

...That's why we proposed this syntax extension:

SELECT
.
.
STOP AFTER <N>   (we changed the name, but this is the LIMIT)
RANK BY <A>
ORDER BY <B>

Here you can select the best <N> rows according to <A> and then order the results on <B>. 
We note that, not accounting for a similar extension, you could do the same thing only using a subselect (with an ORDER BY clause in the inner select, that is non-standard as well).


>> - If you ask for the best 10 rows, from a relation including 
>>   100000 rows, you have to do a traditional sort on 100000 rows and
>>   then retain only the first 10, doing more comparisons than requested.

> Not if there's an index that implements the ordering --- and if there
> is not, I don't see how to avoid the sort anyway.

Of course, if you have an index there is no problem. 
It is even true that if you don't have an index there is no way to avoid the sort, but in that case we use a specialized sort, which does much less comparisons. 
For example, if you want the 10 best rows from 100000, these are the average numbers of comparisons:

QuickSort: 1.6E+14
SortStop: 1.5E+11

>> - You can choose a "fast-start" plan (i.e., basically, 
>>   a pipelined plan), but you cannot performe an "early-stop" of 
>>   the stream when you have a "slow-start" plan  (e.g. involving sorts 
>>   or hash tables).

> Why not?  The executor *will* stop when it has as many output rows as
> the LIMIT demands.

Yes, but consider this very simple case:

LIMIT 10
[something else]
  MergeJoin (100000 rows)
    Sort (100000 rows)
      SeqScan on Table1 (100000 rows)


    IndexScan on Table2 (100 rows)

Assuming that referential constraints allow us to do it, we would do the following:

[something else]
  MergeJoin (10 rows)
    SortStop 10 (10 rows)
        SeqScan on Table1 (100000 rows)
    IndexScan on Table2 (100 rows)

Here, we get only 10 rows from the outer relation. *In general*, this is NOT correct, but referential constraints make it safe in many cases. You can see that in the second approach, the "[something else]" will operate with an input stream cardinality of 10, against 100000 of the first approach. This is what we call the "push-down" of the Stop operator.

> I'd be the first to admit that the cost model needs some fine-tuning
> still.  It's just a conceptual structure at this point.

We hope you are not considering our posts as a criticism. We used PostgreSQL as a base to our proposal, finding good results, and now we are wondering if you are interested to continue in this sense.
Btw, DB2 currently adopts "LIMIT" optimization techniques similar to ours. 

Regards
 
Roberto Cornacchia


===========================================================

VIRGILIO MAIL - Il tuo indirizzo E-mail gratis e per sempre
http://mail.virgilio.it/


VIRGILIO - La guida italiana a Internet
http://www.virgilio.it/


Wed, 23 Feb 2000 19:10:36 -0500
"Roberto Cornacchia" <rob.c@virgilio.it>
Re: about 7.0 LIMIT optimization 
At 07:10 PM 2/23/00 -0500, Roberto Cornacchia wrote:

>Of course, if you have an index there is no problem. 
>It is even true that if you don't have an index there is no way to avoid
the sort, but in that case we use a specialized sort, which does much less
comparisons. 
>For example, if you want the 10 best rows from 100000, these are the
average numbers of comparisons:
>
>QuickSort: 1.6E+14
>SortStop: 1.5E+11

This makes sense ... you can stop once you can guarantee that the first
ten rows are in proper order.  I'm not familiar with the algorithm
but not terribly surprised that one exists.



- Don Baccus, Portland OR <dhogaza@pacifier.com>
  Nature photos, on-line guides, Pacific Northwest
  Rare Bird Alert Service and other goodies at
  http://donb.photo.net.

Wed, 23 Feb 2000 17:33:15 -0800
Don Baccus <dhogaza@pacifier.com>
Re: [HACKERS] Re: about 7.0 LIMIT optimization 
"Roberto Cornacchia" <rob.c@virgilio.it> writes:
>> Why not?  The executor *will* stop when it has as many output rows as
>> the LIMIT demands.

> Yes, but consider this very simple case:

> LIMIT 10
> [something else]
>   MergeJoin (100000 rows)
>     Sort (100000 rows)
>       SeqScan on Table1 (100000 rows)


>     IndexScan on Table2 (100 rows)

> Assuming that referential constraints allow us to do it, we would do the
> following:

> [something else]
>   MergeJoin (10 rows)
>     SortStop 10 (10 rows)
>         SeqScan on Table1 (100000 rows)
>     IndexScan on Table2 (100 rows)

> Here, we get only 10 rows from the outer relation. *In general*, this is
> NOT correct, but referential constraints make it safe in many cases. You
> can see that in the second approach, the "[something else]" will operate
> with an input stream cardinality of 10, against 100000 of the first
> approach. This is what we call the "push-down" of the Stop operator.

If I understand your point correctly, the existing code arrives at this
same effect through another direction: it will choose the right plan for
the query when the [something else] node doesn't need to read very many
rows.  This isn't reflected in the EXPLAIN output very well, which might
be fooling you as to what's really happening.

I'm not sure about your comment about referential constraints.  If you
are doing analysis of restriction clauses to prove that a particular
stage doesn't require reading as many rows as it otherwise would, then
you've done more than I have.

			regards, tom lane

Wed, 23 Feb 2000 21:23:46 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: about 7.0 LIMIT optimization 
Don Baccus <dhogaza@pacifier.com> writes:
>> For example, if you want the 10 best rows from 100000, these are the
> average numbers of comparisons:
>> 
>> QuickSort: 1.6E+14
>> SortStop: 1.5E+11

Are there some zeroes missing here?  That sounds like an awful lot of
operations for a quicksort of only 1E5 elements...

> This makes sense ... you can stop once you can guarantee that the first
> ten rows are in proper order.  I'm not familiar with the algorithm
> but not terribly surprised that one exists.

The obvious way to do it would be with a heap-based sort.  After you've
built the heap, you pull out the first ten elements and then stop.
Offhand this only seems like it'd save about half the work, though,
so maybe Roberto has a better idea.

			regards, tom lane

Wed, 23 Feb 2000 21:30:29 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: [HACKERS] Re: about 7.0 LIMIT optimization 
At 09:30 PM 2/23/00 -0500, Tom Lane wrote:
>Don Baccus <dhogaza@pacifier.com> writes:
>>> For example, if you want the 10 best rows from 100000, these are the
>> average numbers of comparisons:
>>> 
>>> QuickSort: 1.6E+14
>>> SortStop: 1.5E+11
>
>Are there some zeroes missing here?  That sounds like an awful lot of
>operations for a quicksort of only 1E5 elements...

Yeah, obviously one or more of his numbers are wrong.  Let's see, a
bubble sort's only O(n^2), "only" 1E10/2 comparisons for 1E5 elements,
right?  Surely O(n*log(n)) is quicker :)

>
>> This makes sense ... you can stop once you can guarantee that the first
>> ten rows are in proper order.  I'm not familiar with the algorithm
>> but not terribly surprised that one exists.
>
>The obvious way to do it would be with a heap-based sort.  After you've
>built the heap, you pull out the first ten elements and then stop.
>Offhand this only seems like it'd save about half the work, though,
>so maybe Roberto has a better idea.

I'd like to see some elaboration.



- Don Baccus, Portland OR <dhogaza@pacifier.com>
  Nature photos, on-line guides, Pacific Northwest
  Rare Bird Alert Service and other goodies at
  http://donb.photo.net.

Wed, 23 Feb 2000 18:33:36 -0800
Don Baccus <dhogaza@pacifier.com>
Re: [HACKERS] Re: about 7.0 LIMIT optimization 