Horton

Re: Memory usage during sorting

Greg Stark <stark@mit.edu>

View thread
From: Greg Stark <stark@mit.edu>
To: Peter Geoghegan <peter@2ndquadrant.com>
Cc: Robert Haas <robertmhaas@gmail.com>, Tom Lane <tgl@sss.pgh.pa.us>, Jeff Janes <jeff.janes@gmail.com>, Hitoshi Harada <umi.tanuki@gmail.com>, pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2012-04-17T12:19:21Z
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 Mon, Apr 16, 2012 at 10:42 PM, Peter Geoghegan <peter@2ndquadrant.com> wrote:
> All but 4 regression tests pass, but they don't really count
> as failures, since they're down to an assumption in the tests that the
> order certain tuples appear should be the same as our current
> quicksort implementation returns them, even though, in these
> problematic cases, that is partially dictated by implementation - our
> quicksort isn't stable, but timsort is.

This is an interesting point. If we use a stable sort we'll probably
be stuck with stable sorts indefinitely. People will start depending
on the stability and then we'll break their apps if we find a faster
sort that isn't stable.

Notably though tapesort is not stable (because heapsort is not stable
so neither the runs nor the merge steps are stable). So people's apps
would appear to work when they're in memory and fail only on large
data sets. It's easily possible for a user's query to never need to go
to tape though.

We don't have the luxury of having a separate sort and stable_sort
though due to the ORDER BY clause.

All in all I think it's handier to have a stable ORDER BY sort than an
unstable one though. So I'm not necessarily opposed to it even if it
means we're stuck using a stable sort indefinitely.
-- 
greg