Thread: External Sort performance patch

The enclosed patch substantially improves large sort performance, in the
general case

cvstip:    elapsed 5693 sec, CPU 196 sec
patch:    elapsed 4132 sec, CPU 90 sec

The patch implements dynamically increasing number of logical tapes when
sufficient memory is available to make that efficient. cvstip runs with
a static number of tapes (7) whereas the patch was able to allocate 104
tapes to the task. This has the effect of almost completely removing
intermediate merge runs and hence the increased performance.

From Jeffrey W. Baker's original idea
http://archives.postgresql.org/pgsql-performance/2005-09/msg00430.php
and followup comments
http://archives.postgresql.org/pgsql-hackers/2005-10/msg00015.php

It is expected this will substantially improve performance for large
ORDER BY, GROUP BY and CREATE INDEX statements.

The guesstimated default setting of the OPTIMAL_MERGE_BUFFER_SIZE of
262144 means that the default setting of work_mem will still use only 7
tapes, though setting work_mem > 2MB will yield improvements.

Further testing and/or patch comments are requested.

All changes are isolated to src/backend/utils/sort/tuplesort.c
Patch applies cleanly and passes make check on cvstip (though this code
path is not tested in the regression tests anyway).

Test details:
Run the following sort on my laptop (512MB RAM)

postgres=# set work_mem=65536;
SET
Time: 0.801 ms
postgres=# select * from d order by 1,2 limit 1;
 col1 |          col2
------+-------------------------
    1 | eeeeeeseeeeeeeeeeeeeeee
(1 row)

Time: 4133122.769 ms

postgres=# \d d
       Table "public.d"
 Column |  Type   | Modifiers
--------+---------+-----------
 col1   | integer |
 col2   | text    |

postgres=# select count(*) from d;
   count
-----------
 100000000
(1 row)

Time: 248283.128 ms
postgres=# select pg_relation_size('d');
 pg_relation_size
------------------
       6450397184
(1 row)

Time: 98.629 ms
postgres=#

trace_sort was enabled for both runs and these are attached as files to
this mail. Test data was anti-sorted, but the ordering of data is not
relevant to the algorithm anyway, except when the data is already almost
perfectly sorted, in which case there is typically only one run anyway.

Best Regards, Simon Riggs

On Thu, 2006-01-26 at 00:33 +0000, Simon Riggs wrote:
> The enclosed patch substantially improves large sort performance, in the
> general case
>
> cvstip:    elapsed 5693 sec, CPU 196 sec
> patch:    elapsed 4132 sec, CPU 90 sec
>

Following patch implements matching sort cost calculations in the
planner in sort_cost()

This patch is in-addition to the previous patch.

Best Regards, Simon Riggs

Simon Riggs <simon@2ndquadrant.com> writes:
> The enclosed patch substantially improves large sort performance,

Applied with revisions.  I thought the addition of the Tapestate structs
complicated the notation considerably without really buying anything,
so instead I just made the fixed-size arrays into pointers.  A more
serious objection was that MaxTapes and TapeRange can't be globals,
they have to be struct fields, unless you want to assume that all sorts
in progress at a given time must use identical memory settings.

I also fixed some off-by-one logic in determining the appropriate number
of tapes, and added accounting for tape buffer space.  It was somewhat
reasonable to ignore the LogicalTapeSet space when the number of tapes
was fixed and small, but in the new regime I think it's necessary to
account for the tape buffers while computing memory use.

            regards, tom lane

Simon Riggs <simon@2ndquadrant.com> writes:
> Following patch implements matching sort cost calculations in the
> planner in sort_cost()

As given, this didn't even compile.  Cleaned up and applied.

            regards, tom lane

On Sun, 2006-02-19 at 01:16 -0500, Tom Lane wrote:
> Simon Riggs <simon@2ndquadrant.com> writes:
> > Following patch implements matching sort cost calculations in the
> > planner in sort_cost()
>
> As given, this didn't even compile.  Cleaned up and applied.

Well given it was a patch-on-patch, I guess I did cause you more
difficulty than was necessary. I'll submit combined patches only in
future. If this truly didn't compile, then I must have submitted an
earlier version in error when transferring the patch between machines.

Best Regards, Simon Riggs