Make nbtree keys unique by appending heap TID, suffix truncation

Edit

ID 1787

Title Make nbtree keys unique by appending heap TID, suffix truncation

Topic Performance

Created 2018-08-31 16:27:31

Last modified 2019-03-25 17:05:12 (5 years, 7 months ago)

Latest email 2019-04-01 22:59:14 (5 years, 7 months ago)

Status

2019-03: Committed

2019-01: Moved to next CF

2018-11: Moved to next CF

2018-09: Moved to next CF

Target version 12

Authors Peter Geoghegan (pgeoghegan)

Reviewers Heikki Linnakangas (heikki), Andrei Lepikhov (lepikhov)Become reviewer

Committer Peter Geoghegan (pgeoghegan)

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

Emails

Making all nbtree entries unique by having heap TIDs participate in comparisons

First at 2018-06-14 18:44:46 by Peter Geoghegan <pg at bowt.ie>
Latest at 2019-04-01 22:59:14 by Peter Geoghegan <pg at bowt.ie>
Latest attachment (always-split-after-new-item.patch) at 2019-04-01 22:59:14 from Peter Geoghegan <pg at bowt.ie>

    Attachment (always-split-after-new-item.patch) at 2019-04-01 22:59:14 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v18-heikki-0001-Refactor-nbtree-insertion-scankeys.patch) at 2019-03-18 11:59:45 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (v18-0005-Add-split-after-new-tuple-optimization.patch) at 2019-03-18 00:59:25 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v17-0001-Refactor-nbtree-insertion-scankeys.patch) at 2019-03-16 04:16:23 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v16-heikki-0001-Add-high-key-continuescan-optimization.patch) at 2019-03-14 11:00:25 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (7000_wh_4_hours_patch_2.svg) at 2019-03-12 02:47:29 from Peter Geoghegan <pg at bowt.ie> (Patch: No)
    Attachment (v16-0007-DEBUG-Add-pageinspect-instrumentation.patch) at 2019-03-11 00:17:20 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v15-0001-Refactor-nbtree-insertion-scankeys.patch) at 2019-03-08 04:22:54 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (0008-DEBUG-Force-version-3-artificially.patch) at 2019-03-07 08:23:59 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v14-heikki-2-0001-Refactor-nbtree-insertion-scankeys.patch) at 2019-03-07 06:15:47 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (v14-0001-Refactor-nbtree-insertion-scankeys-HEIKKI-comments.patch) at 2019-03-05 11:37:08 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: Yes)
    Attachment (v14-0001-Refactor-nbtree-insertion-scankeys.patch) at 2019-03-04 21:16:49 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v13-0006-Allow-tuples-to-be-relocated-from-root-by-amchec.patch) at 2019-02-26 04:31:17 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v12-0007-DEBUG-Add-pageinspect-instrumentation.patch) at 2019-02-11 20:54:30 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (nbtsplitloc.c) at 2019-01-28 15:31:56 from Heikki Linnakangas <hlinnaka at iki.fi> (Patch: No)
    Attachment (v11-0002-Paper-over-DEPENDENCY_INTERNAL_AUTO-bug-failures.patch) at 2019-01-24 01:44:41 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v10-0002-Add-pg_depend-index-scan-tiebreaker-column.patch) at 2019-01-09 00:47:55 from Peter Geoghegan <pg at bowt.ie> (Patch: No)
    Attachment (v9-0006-DEBUG-Add-pageinspect-instrumentation.patch) at 2018-12-04 03:10:37 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v8-0003-Pick-nbtree-split-points-discerningly.patch) at 2018-11-24 23:13:42 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v7-0005-Temporarily-paper-over-problematic-regress-output.patch) at 2018-11-13 01:47:45 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v6-0005-DEBUG-Add-pageinspect-instrumentation.patch) at 2018-10-03 23:39:24 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v5-0003-Allow-nbtree-to-use-ASC-heap-TID-attribute-order.patch) at 2018-09-19 18:23:11 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (v4-0001-Make-all-nbtree-index-tuples-have-unique-keys.patch) at 2018-09-12 18:11:18 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (collate_bug.tar.gz) at 2018-08-02 04:48:34 from Andrey Lepikhov <a.lepikhov at postgrespro.ru> (Patch: No)
    Attachment (dell-server.txt) at 2018-07-17 19:21:27 from Peter Geoghegan <pg at bowt.ie> (Patch: No)
    Attachment (v2-0001-Ensure-nbtree-leaf-tuple-keys-are-always-unique.patch) at 2018-07-02 17:43:30 from Peter Geoghegan <pg at bowt.ie> (Patch: Yes)
    Attachment (0001-Ensure-nbtree-leaf-tuple-keys-are-always-unique.patch) at 2018-06-14 18:44:46 from Peter Geoghegan <pg at bowt.ie> (Patch: No)

Annotations

When	Who	Mail	Annotation
2018-08-31 16:29:57	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2018-07-17 19:21:27	v3 of patch, plus benchmark information
2018-09-12 18:12:55	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2018-09-12 18:11:18	v4 of the patch, which has the logic for picking a split point consider suffix truncation specifically
2018-09-19 18:29:37	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2018-09-19 18:23:11	v5 of the patch, which greatly simplifies the logic to make picking a split point care about the needs of suffix truncation
2018-10-03 23:52:00	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2018-10-03 23:39:24	v6 of the patch, which greatly helps with TPC-C index bloat, and fixes a significant regression against master with unique indexes
2018-11-13 01:50:01	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2018-11-13 01:47:45	v7 of the patch, which adds pg_upgrade support, and sorts heap TIDs in ASC order
2018-11-24 23:17:33	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2018-11-24 23:13:42	v8 of the patch, which properly addresses pg_depend-related test instability
2018-12-04 03:15:34	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2018-12-04 03:10:37	v9 of the patch, which fixes the Windows build
2019-01-09 00:50:09	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2019-01-09 00:47:55	v10 of the patch, which does some minor refactoring requested by Heikki
2019-01-24 01:48:27	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2019-01-24 01:44:41	v11 of the patch, which entirely avoids buffer locking metapage and system catalog index pages in new and possibly risky ways
2019-02-11 20:58:59	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2019-02-11 20:54:30	v12 of the patch, which tweaks the "cache binary search" mechanism used by unique index insertions, and improves test coverage
2019-02-14 20:26:49	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2019-02-14 06:47:03	TPC-C style benchmark result that demonstrates the effectiveness of the patch at controlling index bloat, and its positive impact on performance in general
2019-02-26 04:34:39	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2019-02-26 04:31:17	v13 of the patch, which takes a "top down" approach to page splits involving materializing all legal splits up front, per suggestion from Heikki
2019-03-04 21:20:53	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2019-03-04 21:16:49	v14 of the patch, which makes some additional changes to how a split point is chosen based on recent feedback from Heikki

"Write amplification" is made worse by "getting tired" while inserting into nbtree secondary indexes (Was: Why B-Tree suffix truncation matters)

First at 2018-07-08 23:59:32 by Peter Geoghegan <pg at bowt.ie>
Latest at 2018-08-30 16:15:56 by Peter Geoghegan <pg at bowt.ie>
Latest attachment (testcase.sql) at 2018-07-08 23:59:32 from Peter Geoghegan <pg at bowt.ie>

Attachment (testcase.sql) at 2018-07-08 23:59:32 from Peter Geoghegan <pg at bowt.ie> (Patch: No)

Annotations

When	Who	Mail	Annotation
2018-09-02 23:31:06	Peter Geoghegan (pgeoghegan)	From Peter Geoghegan <pg@bowt.ie> at 2018-07-08 23:59:32	Motivating example. Master branch churn with many duplicates fails to recycle space. Patch is shown to fix the problem, leaving much smaller index.

On-disk compatibility for nbtree-unique-key enhancement

First at 2018-09-20 23:18:37 by Peter Geoghegan <pg at bowt.ie>
Latest at 2018-09-28 20:03:01 by Peter Geoghegan <pg at bowt.ie>

History

When	Who	What
2019-03-25 17:05:12	Peter Geoghegan (pgeoghegan)	Closed in commitfest 2019-03 with status: Committed
2019-03-25 17:05:12	Peter Geoghegan (pgeoghegan)	Changed committer to pgeoghegan
2019-03-18 23:13:52	Peter Eisentraut (petere)	Removed petere from reviewers
2019-03-04 21:20:53	Peter Geoghegan (pgeoghegan)	Added annotation "v14 of the patch, which makes some additional changes to how a split point is chosen based on recent feedback from Heikki" to CAH2-Wz=Dhkbguk31kCgs62Uj6cqsQn3GA3SYBDp-FWidKncwYA@mail.gmail.com
2019-02-26 04:34:39	Peter Geoghegan (pgeoghegan)	Added annotation "v13 of the patch, which takes a "top down" approach to page splits involving materializing all legal splits up front, per suggestion from Heikki" to CAH2-Wzn3g7TyaU7C40heNM9fEaDAezECM0RC3e_MC+8CW7tk4g@mail.gmail.com
2019-02-21 02:22:01	Peter Geoghegan (pgeoghegan)	Removed pgeoghegan from reviewers
2019-02-21 02:21:57	Peter Geoghegan (pgeoghegan)	Added pgeoghegan as reviewer
2019-02-14 20:26:49	Peter Geoghegan (pgeoghegan)	Added annotation "TPC-C style benchmark result that demonstrates the effectiveness of the patch at controlling index bloat, and its positive impact on performance in general" to CAH2-WzmsK-1qVR8xC86DXv8U0cHwfPcuH6hhA740fCeEu3XsVg@mail.gmail.com
2019-02-11 20:58:59	Peter Geoghegan (pgeoghegan)	Added annotation "v12 of the patch, which tweaks the "cache binary search" mechanism used by unique index insertions, and improves test coverage" to CAH2-Wz=yTWnVu+HeHGKb2AGiADL9eprn-cKYAto4MkKOuiGtRQ@mail.gmail.com
2019-02-11 20:56:35	Peter Geoghegan (pgeoghegan)	New status: Needs review
2019-02-07 21:20:19	Peter Geoghegan (pgeoghegan)	New status: Waiting on Author
2019-02-07 21:19:44	Peter Geoghegan (pgeoghegan)	Changed reviewers to Heikki Linnakangas (heikki), Peter Eisentraut (petere), Andrey Lepikhov (lepikhov)
2019-02-07 21:19:44	Peter Geoghegan (pgeoghegan)	Changed targetversion to 12
2019-02-04 05:24:20	Michael Paquier (michael-kun)	Closed in commitfest 2019-01 with status: Moved to next CF
2019-01-24 01:48:27	Peter Geoghegan (pgeoghegan)	Added annotation "v11 of the patch, which entirely avoids buffer locking metapage and system catalog index pages in new and possibly risky ways" to CAH2-Wzmr=kobQx11s7UvqjYVx9Y49GhPpVxL7C8S36ayTUqVWQ@mail.gmail.com
2019-01-09 00:50:41	Peter Geoghegan (pgeoghegan)	New status: Needs review
2019-01-09 00:50:09	Peter Geoghegan (pgeoghegan)	Added annotation "v10 of the patch, which does some minor refactoring requested by Heikki" to CAH2-Wzm_nBWnbO8wG+zvHHF2QA9j=BOByXZcmhPK1PBii859Kg@mail.gmail.com
2019-01-04 09:41:41	Peter Eisentraut (petere)	New status: Waiting on Author
2018-12-04 03:15:34	Peter Geoghegan (pgeoghegan)	Added annotation "v9 of the patch, which fixes the Windows build" to CAH2-Wz=apbKyaFhEfRN3UK_yXZ8DSE4Ybr0A3D87=4JWyy1QPA@mail.gmail.com
2018-12-01 12:09:47	Dmitry Dolgov (erthalion)	Closed in commitfest 2018-11 with status: Moved to next CF
2018-11-24 23:17:33	Peter Geoghegan (pgeoghegan)	Added annotation "v8 of the patch, which properly addresses pg_depend-related test instability" to CAH2-WznXpL_1ybkNNj-29V6Jrd_p0KBpj2AN=xahBDiNaU1Kfg@mail.gmail.com
2018-11-13 01:50:01	Peter Geoghegan (pgeoghegan)	Added annotation "v7 of the patch, which adds pg_upgrade support, and sorts heap TIDs in ASC order" to CAH2-WzkOmUduME31QnuTFpimejuQoiZ-HOf0pOWeFZNhTMctvA@mail.gmail.com
2018-11-02 09:03:06	Andrei Lepikhov (lepikhov)	Added lepikhov as reviewer
2018-10-03 23:52:00	Peter Geoghegan (pgeoghegan)	Added annotation "v6 of the patch, which greatly helps with TPC-C index bloat, and fixes a significant regression against master with unique indexes" to CAH2-WzkpKeZJrXvR_p7VSY1b-s85E3gHyTbZQzR0BkJ5LrWF_A@mail.gmail.com
2018-10-02 04:40:13	Michael Paquier (michael-kun)	Closed in commitfest 2018-09 with status: Moved to next CF
2018-09-20 23:23:25	Peter Geoghegan (pgeoghegan)	Attached mail thread CAH2-WzmjgBz-RL2-nyPc+NRZnU73YSLGEwZRyB2DhUQEdkEujg@mail.gmail.com
2018-09-19 18:29:37	Peter Geoghegan (pgeoghegan)	Added annotation "v5 of the patch, which greatly simplifies the logic to make picking a split point care about the needs of suffix truncation" to CAH2-WzkfK=JVHjkd17TLDvsFb6psduTt5WYiT8dg+-UFc+rSSQ@mail.gmail.com
2018-09-12 18:12:55	Peter Geoghegan (pgeoghegan)	Added annotation "v4 of the patch, which has the logic for picking a split point consider suffix truncation specifically" to CAH2-WzmmoLNQOj9mAD78iQHfWLJDszHEDrAzGTUMG3mVh5xWPw@mail.gmail.com
2018-09-07 10:08:12	Peter Eisentraut (petere)	Added petere as reviewer
2018-09-02 23:31:06	Peter Geoghegan (pgeoghegan)	Added annotation "Motivating example. Master branch churn with many duplicates fails to recycle space. Patch is shown to fix the problem, leaving much smaller index." to CAH2-Wzmf0fvVhU+SSZpGW4Qe9t--j_DmXdX3it5JcdB8FF2EsA@mail.gmail.com
2018-09-02 23:27:01	Peter Geoghegan (pgeoghegan)	Attached mail thread CAH2-Wzmf0fvVhU+SSZpGW4Qe9t--j_DmXdX3it5JcdB8FF2EsA@mail.gmail.com
2018-08-31 16:29:57	Peter Geoghegan (pgeoghegan)	Added annotation "v3 of patch, plus benchmark information" to CAH2-WzkmTRXh=zyMAUHyG3=O-QQip6CJc2VyNijRO-vzgPxmoQ@mail.gmail.com
2018-08-31 16:28:08	Peter Geoghegan (pgeoghegan)	Changed authors to Peter Geoghegan (pgeoghegan)
2018-08-31 16:27:31	Peter Geoghegan (pgeoghegan)	Attached mail thread CAH2-WzkVb0Kom=R+88fDFb=JSxZMFvbHVC6Mn9LJ2n=X=kS-Uw@mail.gmail.com
2018-08-31 16:27:31	Peter Geoghegan (pgeoghegan)	Created patch record

Edit