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-20T21:06: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

Robert Haas <robertmhaas@gmail.com> writes:
> Yeah, I think I'm going to try implementing
> quicksort-the-whole-batch-and-dump-it-out-as-a-run algorithm, just to
> see how good or bad that is compared to what we have now.  We may not
> end up doing anything that remotely resembles that, in the end, but I
> want to see the numbers.

The reason replacement selection is attractive is that the initial runs
tend to be about twice as long as you can get if you just sort
memory-loads independently.  (And that's for random input, the win can
be a lot more on partially ordered data.)  It seems unlikely that you
will get enough win from quicksorting to overcome that; especially not
if your thesis is correct that all the cost is coming from comparison
infrastructure.

But don't let me discourage you from measuring it ...

			regards, tom lane