Re: Minor performance improvement in transition to external sort

On Thu, Feb 6, 2014 at 4:22 AM, Jeremy Harris <jgh(at)wizmail(dot)org> wrote:
> On 05/02/14 21:56, Robert Haas wrote:
>> On Tue, Feb 4, 2014 at 5:22 PM, Jeremy Harris <jgh(at)wizmail(dot)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).
>
> The patch implements a siftdown. Measurements attached.

Uh, this spreadsheet is useless. You haven't explained how these
numbers were generated, or what the columns in the spreadsheet
actually mean. Ideally, you should include enough information that
someone else can try to reproduce your results.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company