Teach contrib/amcheck's bt_index_parent_check() function to take advantage of the uniqueness property of heapkeyspace indexes in support of a new verification option: non-pivot tuples (non-highkey tuples on the leaf level) can optionally be re-found using a new search for each, that starts from the root page. If a tuple cannot be re-found, report that the index is corrupt.
The new "rootdescend" verification option is exhaustive, and can therefore make a call to bt_index_parent_check() take a lot longer. Re-finding tuples during verification is mostly intended as an option for backend developers, since the corruption scenarios that it alone is uniquely capable of detecting seem fairly far-fetched.
For example, "rootdescend" verification is much more likely to detect corruption of the least significant byte of a key from a pivot tuple in the root page of a B-Tree that already has at least three levels. Typically, only a few tuples on a cousin leaf page are at risk of "getting overlooked" by index scans in this scenario. The corrupt key in the root page is only slightly corrupt: corrupt enough to give wrong answers to some queries, and yet not corrupt enough to allow the problem to be detected without verifying agreement between the leaf page and the root page, skipping at least one internal page level. The existing bt_index_parent_check() checks never cross more than a single level.
Author: Peter Geoghegan
c1afd175b5 Allow amcheck to re-find tuples using new search.
contrib/amcheck/Makefile | 2 +-
contrib/amcheck/amcheck--1.1--1.2.sql | 19 +++++
contrib/amcheck/amcheck.control | 2 +-
contrib/amcheck/expected/check_btree.out | 5 +-
contrib/amcheck/sql/check_btree.sql | 5 +-
contrib/amcheck/verify_nbtree.c | 136 +++++++++++++++++++++++++++++--
doc/src/sgml/amcheck.sgml | 7 +-
7 files changed, 160 insertions(+), 16 deletions(-)