Horton

Re: Memory usage during sorting

Jeff Janes <jeff.janes@gmail.com>

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

On Tue, Mar 20, 2012 at 6:31 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Greg Stark <stark@mit.edu> writes:
>> Offhand I wonder if this is all because we don't have the O(n) heapify
>> implemented.

I think we do already have it implemented.  1/2 the time the tuple
stays where it is after one comparison, 1/4 it moves up one level with
two comparisons, 1/8 it moves up two levels with 3 comparisons, etc.
That series sums up to a constant.  Maybe there is a worst-case that
makes this fall apart, though.  Heapifying something which is already
reverse sorted, maybe?

> Robert muttered something about that before, but is it real?  If you
> could do that, I'd think you'd have a less-than-n-log-n sorting
> solution.

Turning random tuples into heap can be linear.  Extracting them while
maintaining the heap is NlogN, though.  You can't sort without the
extraction step, so the law is preserved.

Cheers,

Jeff