Horton

Re: Memory usage during sorting

Tom Lane <tgl@sss.pgh.pa.us>

View thread
From: Tom Lane <tgl@sss.pgh.pa.us>
To: Robert Haas <robertmhaas@gmail.com>
Cc: Greg Stark <stark@mit.edu>, Jeff Janes <jeff.janes@gmail.com>, Hitoshi Harada <umi.tanuki@gmail.com>, pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2012-03-20T16:33:33Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Improve performance of our private version of qsort. Per recent testing,

  2. Further performance improvements in sorting: reduce number of comparisons

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?

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.

			regards, tom lane