Robert Haas <robertmh...@gmail.com> writes: > On Tue, Mar 20, 2012 at 7:44 AM, Greg Stark <st...@mit.edu> wrote: >> 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. Right, but wouldn't getting rid of the run-number comparisons provide some marginal improvement in the speed of tuplesort_heap_siftup? BTW, there's a link at the bottom of the wikipedia page to a very interesting ACM Queue article, which argues that the binary-tree data structure isn't terribly well suited to virtual memory because it touches random locations in succession. I'm not sure I believe his particular solution, but I'm wondering about B+ trees, ie more than 2 children per node. regards, tom lane -- Sent via pgsql-hackers mailing list (firstname.lastname@example.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers