Re: Memory usage during sorting

On Tue, Mar 20, 2012 at 12:33 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> On Tue, Mar 20, 2012 at 7:44 AM, Greg Stark <stark@mit.edu> wrote:
>>> Offhand I wonder if this is all because we don't have the O(n) heapify
>>> implemented.
>
>> I'm pretty sure that's not the problem.  Even though our heapify is
>> not as efficient as it could be, it's plenty fast enough.  I thought
>> about writing a patch to implement the better algorithm, but it seems
>> like a distraction at this point because the heapify step is such a
>> small contributor to overall sort time.  What's taking all the time is
>> the repeated siftup operations as we pop things out of the heap.
>
> Right, but wouldn't getting rid of the run-number comparisons provide
> some marginal improvement in the speed of tuplesort_heap_siftup?

No.  It does the opposite: it slows it down.  This is a highly
surprising result but it's quite repeatable: removing comparisons
makes it slower.  As previously pontificated, I think this is probably
because the heap can fill up with next-run tuples that are cheap to
compare against, and that spares us having to do "real" comparisons
involving the actual datatype comparators.

> BTW, there's a link at the bottom of the wikipedia page to a very
> interesting ACM Queue article, which argues that the binary-tree
> data structure isn't terribly well suited to virtual memory because
> it touches random locations in succession.  I'm not sure I believe
> his particular solution, but I'm wondering about B+ trees, ie more
> than 2 children per node.

I don't think virtual memory locality is the problem.  I read
somewhere that a ternary heap is supposed to be about one-eighth
faster than a binary heap, but that's because picking the smallest of
three tuples requires two comparisons, whereas picking the smallest of
four tuples requires three comparisons, which is better.

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