On Tue, Mar 20, 2012 at 12:33 PM, Tom Lane <t...@sss.pgh.pa.us> wrote: > 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?
No. It does the opposite: it slows it down. This is a highly surprising result but it's quite repeatable: removing comparisons makes it slower. As previously pontificated, I think this is probably because the heap can fill up with next-run tuples that are cheap to compare against, and that spares us having to do "real" comparisons involving the actual datatype comparators. > 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. I don't think virtual memory locality is the problem. I read somewhere that a ternary heap is supposed to be about one-eighth faster than a binary heap, but that's because picking the smallest of three tuples requires two comparisons, whereas picking the smallest of four tuples requires three comparisons, which is better. -- 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
