Using quicksort for every external sort run

Edit
ID 317
Title Using quicksort for every external sort run
Topic Performance
Created 2015-07-30 01:07:03
Last modified 2016-04-08 06:40:09 (8 years, 5 months ago)
Latest email 2016-04-08 03:39:43 (8 years, 5 months 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 CFbot results (CirrusCI) CFbot GitHub
Checkout latest CFbot patchset Go to your local checkout of the PostgreSQL repository and run:
git remote add commitfest https://github.com/postgresql-cfbot/postgresql.git
git fetch commitfest cf/317
git checkout commitfest/cf/317
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