On Tue, Feb 4, 2014 at 5:22 PM, Jeremy Harris <j...@wizmail.org> wrote: > The attached patch replaces the existing siftup method for heapify with > a siftdown method. Tested with random integers it does 18% fewer > compares and takes 10% less time for the heapify, over the work_mem > range 1024 to 1048576. > > Both algorithms appear to be O(n) (contradicting Wikipedia's claim > that a siftup heapify is O(n log n)).
I think Wikipedia is right. Inserting an a tuple into a heap is O(lg n); doing that n times is therefore O(n lg n). Your patch likewise implements an outer loop which runs O(n) times and an inner loop which runs at most O(lg n) times, so a naive analysis of that algorithm also comes out to O(n lg n). Wikipedia's article on http://en.wikipedia.org/wiki/Heapsort explains why a tighter bound is possible for the siftdown case. I think I tested something like this at some point and concluded that it didn't really help much, because building the initial heap was a pretty small part of the runtime of a large sort. It may still be worth doing, though. -- 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
