Horton

Re: Memory usage during sorting

Robert Haas <robertmhaas@gmail.com>

View thread
From: Robert Haas <robertmhaas@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
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:20:29Z
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 12:12 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Greg Stark <stark@mit.edu> writes:
>> http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
>
> Interesting.  I'm pretty sure that idea appears nowhere in Knuth
> (which might mean it's new enough to have a live patent on it ...
> anybody know who invented this?).

It's in every introductory algorithms textbook; I'd be shocked if
anyone could make an IP claim on it.

> But it seems like that should buy
> back enough comparisons to justify leaving the next-run tuples out of
> the heap (unordered) until the heap becomes empty.  You still want to
> insert new tuples into the heap if they can go to the current run, of
> course.

It seems like it should, but if you read (or reread) my long boring
analysis upthread, you'll learn that it doesn't.  It's slower even if
the cost of building a heap is zero.

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