From: | Don Baccus <dhogaza(at)pacifier(dot)com> |
---|---|
To: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
Cc: | "Roberto Cornacchia" <rob(dot)c(at)virgilio(dot)it>, pgsql-hackers(at)postgreSQL(dot)org |
Subject: | Re: [HACKERS] Re: about 7.0 LIMIT optimization |
Date: | 2000-02-24 02:33:36 |
Message-ID: | 3.0.1.32.20000223183336.0170dc60@mail.pacifier.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
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.
From | Date | Subject | |
---|---|---|---|
Next Message | Tom Lane | 2000-02-24 05:45:56 | Re: [HACKERS] Out of memory problem (forwarded bug report) |
Previous Message | Tom Lane | 2000-02-24 02:30:29 | Re: [HACKERS] Re: about 7.0 LIMIT optimization |