Re: [HACKERS] Re: about 7.0 LIMIT optimization

At 09:30 PM 2/23/00 -0500, Tom Lane wrote:
>Don Baccus <dhogaza(at)pacifier(dot)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(at)pacifier(dot)com>
Nature photos, on-line guides, Pacific Northwest
Rare Bird Alert Service and other goodies at
http://donb.photo.net.