Hi.
There are two or three places in the Postgres source that implement heap
sort (e.g. tuplesort.c, nodeMergeAppend.c), and it's also needed by the
BDR code. It seemed reasonable to factor out the functionality.
I've attached a patch (binaryheap.diff) that contains a straightforward
implementation of a binary heap (originally written by Andres, with a
few bugfixes and cleanups by me).
There doesn't seem to be any place to put unit tests for code like this,
so at Alvaro's suggestion, I have attached a small standalone program I
used for testing (testbinheap.c) and a Makefile. If you copy them both
to src/backend/lib and run "make -f Makefile.binheap", it'll build the
test program. It's nothing exciting, just exercises the functions in
various ways.
I've also attached a patch (nodeMergeAppend.diff) that converts the code
in nodeMergeAppend.c to use binaryheap. It passes "make check", and also
the following test (which is planned as a merge append):
CREATE OR REPLACE VIEW gen AS SELECT * FROM
generate_series(1, 100000) g(i) ORDER BY g.i OFFSET 0;
SELECT * FROM (
SELECT * FROM gen UNION ALL SELECT * FROM gen UNION ALL
SELECT * FROM gen UNION ALL SELECT * FROM gen UNION ALL
SELECT * FROM gen UNION ALL SELECT * FROM gen) s
ORDER BY i OFFSET 1000000;
Initially there was a slight performance degradation with my patch, but
I speeded things up and now my code is at least at par with, and maybe
slightly faster than, the old code. On my laptop, both consistently
take ~2.4s on average to execute the above SELECT.
Comments? Suggestions?
-- Abhijit
