Re: Parallel Sort

On Wed, May 15, 2013 at 11:32 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> I think that this effort could justify itself independently of any
> attempt to introduce parallelism to in-memory sorting. I abandoned a
> patch to introduce timsort to Postgres, because I knew that there was
> no principled way to reap the benefits.

Just for the record, I attach a patch that introduces a timsort_arg
function as a drop-in replacement for quicksort_arg (including
replacing all of the specializations that went into 9.2). It has been
rebased against master. For what it's worth, if anyone wanted to pick
this up, that would be fine with me.

Don't be fooled by the superficial regression test failures. The tests
in question are subtly wrong, because they rely on a certain ordering
that isn't explicitly requested. Timsort is stable, whereas quicksort
generally isn't stable (our implementation certainly isn't).

--
Peter Geoghegan