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

Edit

Title

Topic

Performance

Created

2016-08-16 00:45:17

Last modified

2018-01-06 00:16:32 (6 years, 3 months ago)

Latest email

2018-02-08 12:45:52 (6 years, 2 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

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