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

Edit

ID 714

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

Topic Performance

Created 2016-08-16 00:45:17

Last modified 2018-01-06 00:16:32 (6 years, 10 months ago)

Latest email 2018-02-08 12:45:52 (6 years, 9 months ago)

Status

2016-11: Committed

2016-09: Moved to next CF

Target version

Authors Peter Geoghegan (pgeoghegan)

Reviewers Heikki Linnakangas (heikki), Claudio Freire (klaussfreire)Become reviewer

Committer Heikki Linnakangas (heikki)

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/714
git checkout commitfest/cf/714

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 2018-02-08 12:45:52 by Robert Haas <robertmhaas at gmail.com>
Latest attachment (0001-Mark-logtape.c-buffer-s-tail-as-defined-to-Valgrind.patch) at 2018-02-06 18:33:45 from Peter Geoghegan <pg at bowt.ie>

    Attachment (0001-Mark-logtape.c-buffer-s-tail-as-defined-to-Valgrind.patch) at 2018-02-06 18:33:45 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (0001-Add-logtape.c-Valgrind-suppression.patch) at 2018-02-03 03:26:59 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (0001-Add-parallel-B-tree-index-build-sorting.patch) at 2018-02-02 16:16:50 from Peter Geoghegan <pg at bowt.ie> (Patch: No)
    Attachment (0001-Chaos-monkey-fork-failure.patch) at 2018-01-25 01:31:19 from Thomas Munro <thomas.munro at enterprisedb.com> (Patch: Yes)
    Attachment (pessimistic-fork-failure-detector-v2.patch) at 2018-01-24 20:13:10 from Thomas Munro <thomas.munro at enterprisedb.com> (Patch: Yes)
    Attachment (0001-Add-parallel-B-tree-index-build-sorting.patch) at 2018-01-20 01:33:28 from Peter Geoghegan <pg at bowt.ie> (Patch: No)
    Attachment (propagate-reindex-state-v1.patch) at 2018-01-17 18:40:14 from Robert Haas <robertmhaas at gmail.com> (Patch: Yes)
    Attachment (0001-Add-parallel-B-tree-index-build-sorting.patch) at 2018-01-16 00:54:40 from Peter Geoghegan <pg at bowt.ie> (Patch: No)
    Attachment (0001-Add-parallel-B-tree-index-build-sorting.patch) at 2018-01-05 22:17:51 from Peter Geoghegan <pg at bowt.ie> (Patch: No)
    Attachment (0004-Calculate-parallel-worker-inside-index_create.patch) at 2018-01-02 09:38:14 from Rushabh Lathia <rushabh.lathia at gmail.com> (Patch: Yes)
    Attachment (0003-Adjust-planner-code-to-consider-parallel_leader_part.patch) at 2017-12-12 10:09:29 from Rushabh Lathia <rushabh.lathia at gmail.com> (Patch: Yes)
    Attachment (0002-Adjust-planner-code-to-consider-parallel_leader_part.patch) at 2017-12-08 07:28:59 from Rushabh Lathia <rushabh.lathia at gmail.com> (Patch: Yes)
    Attachment (barrier-forget-participants-v1.patch) at 2017-12-08 02:03:50 from Thomas Munro <thomas.munro at enterprisedb.com> (Patch: Yes)
    Attachment (0001-Add-parallel-B-tree-index-build-sorting_v14.patch) at 2017-12-07 08:25:06 from Rushabh Lathia <rushabh.lathia at gmail.com> (Patch: Yes)
    Attachment (0001-Add-parallel-B-tree-index-build-sorting_v13.patch) at 2017-11-14 09:41:39 from Rushabh Lathia <rushabh.lathia at gmail.com> (Patch: Yes)
    Attachment (0001-Add-parallel-B-tree-index-build-sorting_v12_rebase.patch) at 2017-10-26 11:22:16 from Rushabh Lathia <rushabh.lathia at gmail.com> (Patch: Yes)
    Attachment (0001-Add-parallel-B-tree-index-build-sorting_v12.patch) at 2017-10-10 09:23:41 from Rushabh Lathia <rushabh.lathia at gmail.com> (Patch: Yes)
    Attachment (0001-Add-parallel-B-tree-index-build-sorting_v11.patch) at 2017-09-19 10:21:29 from Rushabh Lathia <rushabh.lathia at gmail.com> (Patch: Yes)
    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
2017-11-14 22:55:27	Peter Geoghegan (pgeoghegan)	From Rushabh Lathia <rushabh.lathia@gmail.com> at 2017-11-14 09:41:39	v13 -- Contains fixes requested by Peter following adopting patch to parallel hash join BufFile infrastructure
2018-01-06 00:16:32	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2018-01-05 22:17:51	Revision of Rushabh's most recent patch -- mostly just polishing.

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
2018-01-06 00:16:32	Peter Geoghegan (pgeoghegan)	Added annotation "Revision of Rushabh's most recent patch -- mostly just polishing." to CAH2-Wzk66gCxRjs8tQWQwBc8kg1VG9+KNitutjg3K=jsYL+euA@mail.gmail.com
2017-11-14 22:55:27	Peter Geoghegan (pgeoghegan)	Added annotation "v13 -- Contains fixes requested by Peter following adopting patch to parallel hash join BufFile infrastructure" to CAGPqQf17vxDXFi=u9yf=aDF_0LJ+NGmRKJ0fUJYVUtzseQm6Zw@mail.gmail.com
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