Using quicksort for every external sort run

git remote add commitfest https://github.com/postgresql-cfbot/postgresql.git
git fetch commitfest cf/317
git checkout commitfest/cf/317

Using quicksort and a merge step to significantly improve on tuplesort's single run "external sort" ×

First at 2015-07-30 01:05:59 by Peter Geoghegan <pg at heroku.com>
Latest at 2015-08-07 06:01:26 by Peter Geoghegan <pg at heroku.com>
Latest attachment (regression.diffs) at 2015-07-31 06:56:23 from Peter Geoghegan <pg at heroku.com>

    Attachment (regression.diffs) at 2015-07-31 06:56:23 from Peter Geoghegan <pg at heroku.com> (Patch: Yes)
    Attachment (0001-Quicksort-when-only-one-initial-run-is-produced.patch) at 2015-07-30 01:05:59 from Peter Geoghegan <pg at heroku.com> (Patch: Yes)

Annotations

When	Who	Mail	Annotation
2015-08-20 02:33:18	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@heroku.com> at 2015-07-30 01:05:59	Initial version that just featured "quicksort with spillover", without affecting "multiple on-tape run" case. Superseded by more comprehensive approach. ×

Using quicksort for every external sort run ×

First at 2015-08-20 02:24:26 by Peter Geoghegan <pg at heroku.com>
Latest at 2016-04-08 03:39:43 by Peter Geoghegan <pg at heroku.com>
Latest attachment (0005-Perform-memory-prefetching-when-writing-memtuples.patch) at 2016-04-08 03:39:43 from Peter Geoghegan <pg at heroku.com>

    Attachment (0005-Perform-memory-prefetching-when-writing-memtuples.patch) at 2016-04-08 03:39:43 from Peter Geoghegan <pg at heroku.com> (Patch: Yes)
    Attachment (i5.ods) at 2016-04-02 14:31:45 from Tomas Vondra <tomas.vondra at 2ndquadrant.com> (Patch: No)
    Attachment (results-xeon-10m.ods) at 2016-03-22 21:27:56 from Tomas Vondra <tomas.vondra at 2ndquadrant.com> (Patch: No)
    Attachment (0003-Add-MemoryContextStats-calls-for-debugging.patch) at 2016-03-21 06:01:28 from Peter Geoghegan <pg at heroku.com> (Patch: Yes)
    Attachment (0004-Add-MemoryContextStats-calls-for-debugging.patch) at 2016-03-11 02:54:10 from Peter Geoghegan <pg at heroku.com> (Patch: Yes)
    Attachment (land-registry-data.txt) at 2016-03-08 06:57:38 from Peter Geoghegan <pg at heroku.com> (Patch: No)
    Attachment (Test Queries.sql) at 2016-01-29 11:41:32 from Mithun Cy <mithun.cy at enterprisedb.com> (Patch: No)
    Attachment (0003-Perform-memory-prefetching-when-writing-memtuples.patch) at 2015-12-28 23:03:25 from Peter Geoghegan <pg at heroku.com> (Patch: Yes)
    Attachment (maxorder_theory.patch) at 2015-12-24 03:48:16 from Peter Geoghegan <pg at heroku.com> (Patch: Yes)
    Attachment (simd-sort-test.c) at 2015-12-12 19:47:16 from Greg Stark <stark at mit.edu> (Patch: No)
    Attachment (0001-Add-logical-tape-size-to-TRACE_SORT-output.patch) at 2015-12-09 02:39:13 from Greg Stark <stark at mit.edu> (Patch: Yes)
    Attachment (0003-Perform-memory-prefetching-when-writing-memtuples.patch) at 2015-12-07 00:25:23 from Peter Geoghegan <pg at heroku.com> (Patch: Yes)
    Attachment (sort-benchmarks.tar.gz) at 2015-12-01 00:29:38 from Peter Geoghegan <pg at heroku.com> (Patch: No)
    Attachment (trace_sort_1GB_sort005.txt) at 2015-11-28 22:04:16 from Jeff Janes <jeff.janes at gmail.com> (Patch: No)
    Attachment (0001-Quicksort-when-performing-external-sorts.patch) at 2015-09-06 00:48:10 from Peter Geoghegan <pg at heroku.com> (Patch: Yes)
    Attachment (0001-Quicksort-when-performing-external-sorts.patch) at 2015-08-20 02:24:26 from Peter Geoghegan <pg at heroku.com> (Patch: Yes)

Annotations

When	Who	Mail	Annotation
2015-08-20 02:34:42	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@heroku.com> at 2015-08-20 02:24:26	Far more comprehensive approach, ensuring that quicksort is always used for runs (one way or the other). ×
2015-09-06 00:52:19	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@heroku.com> at 2015-09-06 00:48:10	Revision of patch series adding optimization of final merge phase by making preread "tuple proper" memory access sequential ×
2015-12-07 00:27:33	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@heroku.com> at 2015-12-07 00:25:23	Version with consolidated commits, improved comments, and reduced use of explicit memory prefetching ×
2015-12-28 23:06:51	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@heroku.com> at 2015-12-28 23:03:25	Version that significantly overhauls memory management when merging (revising code for existing batch allocation optimization) ×
2016-03-11 02:57:01	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@heroku.com> at 2016-03-11 02:54:10	Version that significantly simplifies quicksort patch (no more "quicksort with spillover"), and largely fixes "low work_mem, large sort" regressions ×
2016-03-21 07:10:45	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@heroku.com> at 2016-03-21 06:01:28	Following batch memory patch commit, new version of quicksort patch with defensive measure against theoretical int overflow, other small tweaks ×
2016-04-08 03:47:27	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@heroku.com> at 2016-04-08 03:39:43	Revision that changes threshold GUC to govern use of replacement selection using units of tuples, not units of KB of workMem setting ×

Re: Using quicksort for every external sort run ×

First at 2016-04-04 00:46:15 by Peter Geoghegan <pg at heroku.com>
Latest at 2016-04-04 00:46:15 by Peter Geoghegan <pg at heroku.com>