Re: Using quicksort for every external sort run

On Wed, Nov 18, 2015 at 3:29 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>> Overall this is very nice. Doing some real world index builds of
>> short text (~20 bytes ascii) identifiers, I could easily get speed ups
>> of 40% with your patch if I followed the philosophy of "give it as
>> much maintenance_work_mem as I can afford". If I fine-tuned the
>> maintenance_work_mem so that it was optimal for each sort method, then
>> the speed up quite a bit less, only 22%. But 22% is still very
>> worthwhile, and who wants to spend their time fine-tuning the memory
>> use for every index build?
>
> Thanks, but I expected better than that.

It also might have been that you used a "quicksort with spillover".
That still uses a heap to some degree, in order to avoid most I/O, but
with a single backend sorting that can often be slower than the
(greatly overhauled) "external merge" sort method (both of these
algorithms are what you'll see in EXPLAIN ANALYZE, which can be a
little confusing because it isn't clear what the distinction is in
some cases).

You might also very occasionally see an "external sort" (this is also
a description from EXPLAIN ANALYZE), which is generally slower (it's a
case where we were unable to do a final on-the-fly merge, either
because random access is requested by the caller, or because multiple
passes were required -- thankfully this doesn't happen most of the
time).

--
Peter Geoghegan