Re: [HACKERS] 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
Serviceand other goodies at http://donb.photo.net.