Speeding up tuplesort merging (shift down, batch memory, maxTapes)

Edit
Title Speeding up tuplesort merging (shift down, batch memory, maxTapes)
Topic Performance
Created 2016-08-16 00:45:17
Last modified 2017-03-20 01:06:55 (5 months ago)
Latest email 2017-03-22 16:26:00 (4 months, 4 weeks ago)
Status
2016-11: Committed
2016-09: Moved to next CF
Authors Peter Geoghegan (pgeoghegan)
Reviewers Heikki Linnakangas (heikki), Claudio Freire (klaussfreire)Become reviewer
Committer Heikki Linnakangas (heikki)
Links
Emails
Parallel tuplesort (for parallel B-Tree index creation)
First at 2016-08-01 22:18:22 by Peter Geoghegan <pg at heroku.com>
Latest at 2017-03-22 16:26:00 by Peter Geoghegan <pg at bowt.ie>
Latest attachment (0001-Add-parallel-B-tree-index-build-sorting.patch.gz) at 2017-03-20 01:03:51 from Peter Geoghegan <pg at bowt.ie>
    Attachment (0001-Add-parallel-B-tree-index-build-sorting.patch.gz) at 2017-03-20 01:03:51 from Peter Geoghegan <pg at bowt.ie> (Patch: No)
    Attachment (0001-Add-parallel-B-tree-index-build-sorting.patch.gz) at 2017-03-12 22:05:40 from Peter Geoghegan <pg at bowt.ie> (Patch: No)
    Attachment (speedup-100.txt) at 2017-02-16 02:05:14 from Thomas Munro <thomas.munro at enterprisedb.com> (Patch: No)
    Attachment (0001-Add-parallel-B-tree-index-build-sorting.patch.gz) at 2017-02-10 00:10:14 from Peter Geoghegan <pg at bowt.ie> (Patch: No)
    Attachment (speedup.txt) at 2017-02-03 13:04:55 from Thomas Munro <thomas.munro at enterprisedb.com> (Patch: No)
    Attachment (0002-Add-temporary-testing-tools.patch.gz) at 2017-01-03 23:53:59 from Peter Geoghegan <pg at heroku.com> (Patch: No)
    Attachment (0002-Add-temporary-testing-tools.patch.gz) at 2016-12-04 01:29:01 from Peter Geoghegan <pg at heroku.com> (Patch: No)
    Attachment (max-sort-tapes.patch) at 2016-11-10 00:01:30 from Robert Haas <robertmhaas at gmail.com> (Patch: Yes)
    Attachment (0001-Cap-the-number-of-tapes-used-by-external-sorts.patch.gz) at 2016-11-08 04:28:35 from Peter Geoghegan <pg at heroku.com> (Patch: No)
    Attachment (0003-Add-force_btree_randomaccess-GUC-for-testing.patch.gz) at 2016-10-25 01:17:41 from Peter Geoghegan <pg at heroku.com> (Patch: No)
    Attachment (0001-Cap-the-number-of-tapes-used-by-external-sorts.patch.gz) at 2016-10-08 00:47:13 from Peter Geoghegan <pg at heroku.com> (Patch: No)
    Attachment (0001-Refactor-LogicalTapeSet-LogicalTape-interface.patch) at 2016-09-21 16:52:00 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (0003-Rearrange-header-file-include-directives.patch.gz) at 2016-09-11 18:05:07 from Peter Geoghegan <pg at heroku.com> (Patch: No)
    Attachment (root_displace_patched_timings.log) at 2016-09-10 00:22:01 from Claudio Freire <klaussfreire at gmail.com> (Patch: No)
    Attachment (0003-Displace-heap-s-root-during-tuplesort-merge.patch) at 2016-08-16 00:33:38 from Peter Geoghegan <pg at heroku.com> (Patch: Yes)
    Attachment (0001-Cap-the-number-of-tapes-used-by-external-sorts.patch.gz) at 2016-08-01 22:18:22 from Peter Geoghegan <pg at heroku.com> (Patch: No)

Annotations

When Who Mail Annotation
2016-09-11 18:07:19 Peter Geoghegan (pgeoghegan) From Peter Geoghegan <pg@heroku.com>
at 2016-09-11 18:05:07
V2 -- uses maintenance_work_mem as budget for entire CREATE INDEX, regardless of number of workers
2016-10-08 00:49:11 Peter Geoghegan (pgeoghegan) From Peter Geoghegan <pg@heroku.com>
at 2016-10-08 00:47:13
V3 -- rebased on top of Heikki's logtape.c preload memory patch
2016-10-25 02:06:25 Peter Geoghegan (pgeoghegan) From Peter Geoghegan <pg@heroku.com>
at 2016-10-25 01:17:41
V4 -- mechanical rebase on top of refactoring commit b75f467b6eec0678452fd8d7f8d306e6df3a1076
2016-10-26 16:42:26 Peter Geoghegan (pgeoghegan) From Peter Geoghegan <pg@heroku.com>
at 2016-10-26 16:02:21
Do-over of original benchmark from August 1, showing how preloading work from Heikki (and other improvements) have increased scalability of parallel CREATE INDEX
2016-11-08 04:35:03 Peter Geoghegan (pgeoghegan) From Peter Geoghegan <pg@heroku.com>
at 2016-11-08 04:28:35
V5 -- Overhaul to cost model, new testing tool
2016-12-04 01:30:15 Peter Geoghegan (pgeoghegan) From Peter Geoghegan <pg@heroku.com>
at 2016-12-04 01:29:01
V6 -- tuplesort.c now uses condition variables
2017-01-03 23:57:44 Peter Geoghegan (pgeoghegan) From Peter Geoghegan <pg@heroku.com>
at 2017-01-03 23:53:59
V7 -- rebased on top of logtape.c simplifications, pg_restore avoids using parallel CREATE INDEX unless storage parameter was used, refactoring
2017-02-10 00:12:17 Peter Geoghegan (pgeoghegan) From Peter Geoghegan <pg@bowt.ie>
at 2017-02-10 00:10:14
V8 -- rebased on top of logtape.c bugfix, implements BufFile refcount mechanism
2017-03-12 22:11:30 Peter Geoghegan (pgeoghegan) From Peter Geoghegan <pg@bowt.ie>
at 2017-03-12 22:05:40
V9 -- Bulletproof resource management, significantly simplified cost model
2017-03-20 01:06:55 Peter Geoghegan (pgeoghegan) From Peter Geoghegan <pg@bowt.ie>
at 2017-03-20 01:03:51
V10 -- Fixes bug caused by commit 2609e91fc, bitrot
Tuplesort merge pre-reading
First at 2016-09-06 12:20:30 by Heikki Linnakangas <hlinnaka at iki.fi>
Latest at 2016-10-03 11:51:54 by Peter Geoghegan <pg at heroku.com>
Latest attachment (0001-Change-the-way-pre-reading-in-external-sort-s-merge-4.patch) at 2016-09-29 15:10:03 from Heikki Linnakangas <hlinnaka at iki.fi>
    Attachment (0001-Change-the-way-pre-reading-in-external-sort-s-merge-4.patch) at 2016-09-29 15:10:03 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (0001-Change-the-way-pre-reading-in-external-sort-s-merge-3.patch) at 2016-09-29 14:41:25 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (logtape_preload_timings.ods) at 2016-09-22 00:40:23 from Claudio Freire <klaussfreire at gmail.com> (Patch: No)
    Attachment (logtape_preload_timings.ods) at 2016-09-20 18:34:29 from Claudio Freire <klaussfreire at gmail.com> (Patch: No)
    Attachment (0001-Change-the-way-pre-reading-in-external-sort-s-merge-2.patch) at 2016-09-14 17:43:36 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (0001-Change-the-way-pre-reading-in-external-sort-s-merge-.patch) at 2016-09-12 19:07:40 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (regression.diffs) at 2016-09-12 15:47:28 from Claudio Freire <klaussfreire at gmail.com> (Patch: Yes)
    Attachment (0001-Change-the-way-pre-reading-in-external-sort-s-merge-.patch) at 2016-09-11 15:47:21 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (trace-logtape.patch) at 2016-09-09 12:01:06 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (trace-logtape.patch) at 2016-09-09 11:55:40 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (results-large-master.txt) at 2016-09-09 11:13:49 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: No)
    Attachment (0001-Don-t-bother-to-pre-read-tuples-into-SortTuple-slots.patch) at 2016-09-08 18:59:41 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (0001-Don-t-bother-to-pre-read-tuples-into-slots-during-me.patch) at 2016-09-06 12:20:30 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)

Annotations

When Who Mail Annotation
2016-09-12 04:07:11 Peter Geoghegan (pgeoghegan) From Heikki Linnakangas <hlinnaka@iki.fi>
at 2016-09-06 12:20:30
Heikki's proposed alternative to patch 0002-* from original patch set (batch memory patch)
2016-09-12 04:09:30 Peter Geoghegan (pgeoghegan) From Heikki Linnakangas <hlinnaka@iki.fi>
at 2016-09-11 15:47:21
Latest version from Heikki -- applies on top master branch on 2016-09-11 (with Peter's 0003-* merge heap patch committed)
2016-09-12 04:10:02 Peter Geoghegan (pgeoghegan) From Peter Geoghegan <pg@heroku.com>
at 2016-09-11 22:13:55
Review
History
When Who What
2017-03-20 01:06:55 Peter Geoghegan (pgeoghegan) Added annotation "V10 -- Fixes bug caused by commit 2609e91fc, bitrot" to CAH2-WznqgFJVb0OpbrS445TnyS8ib8kSxAASvLqLCaSnQeyd0Q@mail.gmail.com
2017-03-12 22:11:30 Peter Geoghegan (pgeoghegan) Added annotation "V9 -- Bulletproof resource management, significantly simplified cost model" to CAH2-Wznuf2nwsr6=4n8aRQtqCu3PaFYuvDEoYeEenYK-bXYX4w@mail.gmail.com
2017-02-10 00:12:17 Peter Geoghegan (pgeoghegan) Added annotation "V8 -- rebased on top of logtape.c bugfix, implements BufFile refcount mechanism" to CAH2-WzmWtorLU0qi63dTgNbBJPds1wRLDtoZSDRwkRWdvBnMww@mail.gmail.com
2017-01-03 23:57:44 Peter Geoghegan (pgeoghegan) Added annotation "V7 -- rebased on top of logtape.c simplifications, pg_restore avoids using parallel CREATE INDEX unless storage parameter was used, refactoring" to CAM3SWZRkQ64nhFiWeGTx4CUuvCaL8m+GSg8PhssHY=E-_wNpBA@mail.gmail.com
2016-12-04 01:30:15 Peter Geoghegan (pgeoghegan) Added annotation "V6 -- tuplesort.c now uses condition variables" to CAM3SWZQ0EgCxs2NoEUwB6BACi-pp5qVmp432i+Wh_XyUrg1FbQ@mail.gmail.com
2016-11-08 05:52:54 Peter Geoghegan (pgeoghegan) Deleted annotation ""shift down" merge heap patch committed" from 19f05353-9514-9139-619a-dbaa7a0e5e78@iki.fi
2016-11-08 05:52:37 Peter Geoghegan (pgeoghegan) Deleted annotation "This is a spin-off of the parallel CREATE INDEX stuff, intended to represent 3 patches that are helpful with merging. Merge performance is particularly important for parallel tuplesort, but is independently useful." from CAM3SWZRhBhiknTF_=NjDSnNZ11hx=U_SEYwbc5vd=x7M4mMiCw@mail.gmail.com
2016-11-08 05:52:12 Peter Geoghegan (pgeoghegan) Deleted annotation "Patch has bitrot. New version pending." from CAM3SWZTjULhhHPMYb9KYKD48rs_RgnMQPMZMdf0dqkRpZoY_ZA@mail.gmail.com
2016-11-08 04:35:03 Peter Geoghegan (pgeoghegan) Added annotation "V5 -- Overhaul to cost model, new testing tool" to CAM3SWZSA_+CBsaYyb22cdqwkfNgD9vQL74NVYnbu62ZqhLD4Og@mail.gmail.com
2016-10-26 16:42:26 Peter Geoghegan (pgeoghegan) Added annotation "Do-over of original benchmark from August 1, showing how preloading work from Heikki (and other improvements) have increased scalability of parallel CREATE INDEX" to CAM3SWZSsvig8eZtxCG1L9bZZw+-uWdJ48yxSM41QmNLtJeQSyA@mail.gmail.com
2016-10-25 16:29:03 Peter Geoghegan (pgeoghegan) Closed in commitfest 2016-11 with status: Committed
2016-10-25 16:29:03 Peter Geoghegan (pgeoghegan) Changed committer to heikki
2016-10-25 02:06:25 Peter Geoghegan (pgeoghegan) Added annotation "V4 -- mechanical rebase on top of refactoring commit b75f467b6eec0678452fd8d7f8d306e6df3a1076" to CAM3SWZStcX5DNxRvjGTj4KRvjg+sV2CdxJvL9S4cksbRumVmhA@mail.gmail.com
2016-10-08 00:49:11 Peter Geoghegan (pgeoghegan) Added annotation "V3 -- rebased on top of Heikki's logtape.c preload memory patch" to CAM3SWZTmkOFEiCDpUNaO4n9-1xcmWP-1NXmT7h0Pu3gM2YuHvg@mail.gmail.com
2016-10-03 03:37:27 Michael Paquier (michael-kun) Closed in commitfest 2016-09 with status: Moved to next CF
2016-09-12 04:17:42 Peter Geoghegan (pgeoghegan) Added annotation ""shift down" merge heap patch committed" to 19f05353-9514-9139-619a-dbaa7a0e5e78@iki.fi
2016-09-12 04:10:52 Peter Geoghegan (pgeoghegan) Attached mail thread f298f77a-cf06-e70c-d5a4-a20b472b4627@iki.fi
2016-09-11 23:06:51 Peter Geoghegan (pgeoghegan) New status: Needs review
2016-09-11 18:07:19 Peter Geoghegan (pgeoghegan) Added annotation "V2 -- uses maintenance_work_mem as budget for entire CREATE INDEX, regardless of number of workers" to CAM3SWZTW+3vmZugxhy=_jdm5YxNXGdAEHv5Sz6jBpdyfsJVkRg@mail.gmail.com
2016-09-10 00:22:11 Claudio Freire (klaussfreire) New status: Waiting on Author
2016-09-07 00:40:55 Peter Geoghegan (pgeoghegan) Changed reviewers to Heikki Linnakangas (heikki), Claudio Freire (klaussfreire)
2016-09-05 23:35:00 Claudio Freire (klaussfreire) Added klaussfreire as reviewer
2016-08-22 21:50:52 Peter Geoghegan (pgeoghegan) Added annotation "Patch has bitrot. New version pending." to CAM3SWZTjULhhHPMYb9KYKD48rs_RgnMQPMZMdf0dqkRpZoY_ZA@mail.gmail.com
2016-08-16 00:47:06 Peter Geoghegan (pgeoghegan) Added annotation "This is a spin-off of the parallel CREATE INDEX stuff, intended to represent 3 patches that are helpful with merging. Merge performance is particularly important for parallel tuplesort, but is independently useful." to CAM3SWZRhBhiknTF_=NjDSnNZ11hx=U_SEYwbc5vd=x7M4mMiCw@mail.gmail.com
2016-08-16 00:45:30 Peter Geoghegan (pgeoghegan) Changed authors to Peter Geoghegan (pgeoghegan)
2016-08-16 00:45:17 Peter Geoghegan (pgeoghegan) Attached mail thread CAM3SWZQKM=Pzc=CAHzRixKjp2eO5Q0Jg1SoFQqeXFQ647JiwqQ@mail.gmail.com
2016-08-16 00:45:17 Peter Geoghegan (pgeoghegan) Created patch record
Edit