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: http://www.postgresql.org/mailpref/pgsql-hackers
