Using quicksort for every external sort run

Edit

317

Title

CI (CFBot)

Not processed

Stats (from CFBot)

Unknown

Topic

Performance

Created

2015-07-30 01:07:03

Last modified

2016-04-08 06:40:09 (9 years ago)

Latest email

2016-04-08 03:39:43 (9 years ago)

Status

2016-03: Committed

2016-01: Moved to next CF

2015-11: Moved to next CF

2015-09: Moved to next CF

Target version

Authors

Peter Geoghegan (pgeoghegan)

Reviewers

Robert Haas (rhaas), Greg Stark (stark), Jeff Janes (jjanes), Tomas Vondra (fuzzycz)Become reviewer

Committer

Robert Haas (rhaas)

Links

Emails

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>

History

When	Who	What
2016-04-08 06:40:09	Robert Haas (rhaas)	Closed in commitfest 2016-03 with status: Committed
2016-04-08 03:47:30	Peter Geoghegan (pgeoghegan)	New status: Needs review
2016-04-08 03:47:27	Peter Geoghegan (pgeoghegan)	Added annotation "Revision that changes threshold GUC to govern use of replacement selection using units of tuples, not units of KB of workMem setting" to CAM3SWZQU8=9T+gCV4icxdQ21iBhX9QJk24RNdifwPU2OURvGcg@mail.gmail.com
2016-04-07 18:15:06	Robert Haas (rhaas)	New status: Waiting on Author
2016-04-05 04:52:41	Peter Geoghegan (pgeoghegan)	Changed reviewers to Robert Haas (rhaas), Tomas Vondra (fuzzycz), Jeff Janes (jjanes), Greg Stark (stark)
2016-04-05 04:52:02	Peter Geoghegan (pgeoghegan)	Changed reviewers to Robert Haas (rhaas)
2016-04-04 00:56:58	Peter Geoghegan (pgeoghegan)	Attached mail thread CAM3SWZR5rwzBEZunjNE-OM=xVwmbaBOkVasePXuGFqBcNwg7dw@mail.gmail.com
2016-03-21 07:10:45	Peter Geoghegan (pgeoghegan)	Added annotation "Following batch memory patch commit, new version of quicksort patch with defensive measure against theoretical int overflow, other small tweaks" to CAM3SWZS3ttv3_AjGw_BmRRd3QML3YZ9FueN=bwQ0r6dZVS2mDA@mail.gmail.com
2016-03-21 07:08:07	Peter Geoghegan (pgeoghegan)	New status: Needs review
2016-03-19 14:51:04	Robert Haas (rhaas)	New status: Waiting on Author
2016-03-17 22:45:47	Peter Geoghegan (pgeoghegan)	Changed reviewers to Robert Haas (rhaas), Constantin Pan (kvap)
2016-03-17 22:45:47	Peter Geoghegan (pgeoghegan)	Changed committer to rhaas
2016-03-11 21:56:07	Constantin Pan (kvap)	Added kvap as reviewer
2016-03-11 02:57:01	Peter Geoghegan (pgeoghegan)	Added annotation "Version that significantly simplifies quicksort patch (no more "quicksort with spillover"), and largely fixes "low work_mem, large sort" regressions" to CAM3SWZRFzg1LUK8FBg_goZ8zL0n7k6q83qQjhOV8NDZioA5TEQ@mail.gmail.com
2016-02-03 17:27:14	Peter Geoghegan (pgeoghegan)	Closed in commitfest 2016-01 with status: Moved to next CF
2016-02-03 16:37:59	Álvaro Herrera (alvherre)	Closed in commitfest 2016-01 with status: Returned with feedback
2016-02-01 23:02:41	Álvaro Herrera (alvherre)	Changed name to Using quicksort for every external sort run
2015-12-28 23:06:51	Peter Geoghegan (pgeoghegan)	Added annotation "Version that significantly overhauls memory management when merging (revising code for existing batch allocation optimization)" to CAM3SWZS4Mr-k6nUFBPcYkCoSQsjHXVJDqDa=PN_56Fiy1dsFgA@mail.gmail.com
2015-12-24 02:39:31	Michael Paquier (michael-kun)	Closed in commitfest 2015-11 with status: Moved to next CF
2015-12-07 00:27:33	Peter Geoghegan (pgeoghegan)	Added annotation "Version with consolidated commits, improved comments, and reduced use of explicit memory prefetching" to CAM3SWZTx-RuMny3Bo0tiQCz-Kbqpkrxkse6DvsGoaG0vX+uSdw@mail.gmail.com
2015-10-30 23:28:39	Michael Paquier (michael-kun)	Closed in commitfest 2015-09 with status: Moved to next CF
2015-09-06 00:52:19	Peter Geoghegan (pgeoghegan)	Added annotation "Revision of patch series adding optimization of final merge phase by making preread "tuple proper" memory access sequential" to CAM3SWZRiHaF7jdf923ZZ2qhDJiErqP5uU_+JPuMvUmeD0z9fFA@mail.gmail.com
2015-08-20 02:34:42	Peter Geoghegan (pgeoghegan)	Added annotation "Far more comprehensive approach, ensuring that quicksort is always used for runs (one way or the other)." to CAM3SWZQVSpNeHHKKq-rjJddOcbpdmyHDJUMBBL2-AP2R+4YCHg@mail.gmail.com
2015-08-20 02:33:18	Peter Geoghegan (pgeoghegan)	Added annotation "Initial version that just featured "quicksort with spillover", without affecting "multiple on-tape run" case. Superseded by more comprehensive approach." to CAM3SWZTzLT5Y=VY320NznAyz2z_em3us6x=7rXMEUma9Z9yN6Q@mail.gmail.com
2015-08-20 02:31:12	Peter Geoghegan (pgeoghegan)	Changed name to Using quicksort for every external sort run (Was: Using quicksort and a merge step to significantly improve on tuplesort's single run "external sort")
2015-08-20 02:30:12	Peter Geoghegan (pgeoghegan)	Attached mail thread CAM3SWZQVSpNeHHKKq-rjJddOcbpdmyHDJUMBBL2-AP2R+4YCHg@mail.gmail.com
2015-07-30 01:07:12	Peter Geoghegan (pgeoghegan)	Changed authors to Peter Geoghegan (pgeoghegan)
2015-07-30 01:07:03	Peter Geoghegan (pgeoghegan)	Attached mail thread CAM3SWZTzLT5Y=VY320NznAyz2z_em3us6x=7rXMEUma9Z9yN6Q@mail.gmail.com
2015-07-30 01:07:03	Peter Geoghegan (pgeoghegan)	Created patch record

Edit