Minor performance improvement in transition to external sort

From: Jeremy Harris <jgh(at)wizmail(dot)org>
To: "pgsql-hackers(at)postgresql(dot)org" <pgsql-hackers(at)postgresql(dot)org>
Subject: Minor performance improvement in transition to external sort
Date: 2014-02-04 22:22:59
Message-ID: 52F16843.8080001@wizmail.org
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

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)).

--
Cheers,
Jeremy

Attachment Content-Type Size
d text/plain 2.5 KB

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2014-02-04 22:29:54 Re: narwhal and PGDLLIMPORT
Previous Message Jeff Janes 2014-02-04 22:21:51 Re: integrate pg_upgrade analyze_new_cluster.sh into vacuumdb