Horton

Re: Memory usage during sorting

Jim Nasby <jim@nasby.net>

View thread
From: Jim Nasby <jim@nasby.net>
To: Greg Stark <stark@mit.edu>
Cc: Peter Geoghegan <peter@2ndquadrant.com>, 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-05-01T16:57:39Z
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 4/17/12 7:19 AM, Greg Stark wrote:
> 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.

I have often wished that I could inject entropy into a test database to ferret out these kinds of issues. In particular I worry about things like users depending on specific values for serial types or depending on the order of data in the heap.

I would find it useful if Postgres had an option to intentionally inject more randomness in areas at the cost of some performance. IE: have nextval() burn through a small, random number of values before returning one, and have scan operators do some re-ordering of tuples where appropriate.

If we had such an option and encouraged users to use it in testing, it would reduce the risk of people depending on behavior that they shouldn't be.
-- 
Jim C. Nasby, Database Architect                   jim@nasby.net
512.569.9461 (cell)                         http://jim.nasby.net