On Tue, Mar 20, 2012 at 7:44 AM, Greg Stark <st...@mit.edu> wrote:
> On Tue, Mar 20, 2012 at 1:57 AM, Tom Lane <t...@sss.pgh.pa.us> wrote:
>> That was a long time ago, of course, but I have some vague recollection
>> that keeping next-run tuples in the current heap achieves a net savings
>> in the total number of comparisons needed to heapify both runs.
> Offhand I wonder if this is all because we don't have the O(n) heapify
> implemented.

I'm pretty sure that's not the problem.  Even though our heapify is
not as efficient as it could be, it's plenty fast enough.  I thought
about writing a patch to implement the better algorithm, but it seems
like a distraction at this point because the heapify step is such a
small contributor to overall sort time.  What's taking all the time is
the repeated siftup operations as we pop things out of the heap.

Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:

Reply via email to