On 12/10/2014 10:59 PM, Arthur Silva wrote:
It may be better to replace the lib/binaryheap altogether as it offers comparable/better performance.
It's not always better. A binary heap is more memory-efficient, for starters.
There are only two uses of lib/binaryheap: reorderbuffer.c and merge append. Reorderbuffer isn't that performance critical, although a binary heap may well be better there, because the comparison function is very cheap. For merge append, it might be a win, especially if the comparison function is expensive. (That's on the assumption that the overall number of comparisons needed with a pairing heap is smaller - I'm not sure how true that is). That would be worth testing.
I'd love to test some other heap implementation in in tuplesort.c. It has a custom binary heap implementation that's used in the final merge phase of an external sort, and also when doing a so-called bounded sort, i.e. "ORDER BY x LIMIT Y". But that would be difficult to replace, because tuplesort.c collects tuples in an array in memory, and then turns that into a heap. An array is efficient to turn into a binary heap, but to switch to another data structure, you'd suddenly need extra memory. And we do the switch when we run out of work_mem, so allocating more isn't really an option.
- Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
