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