Re: amcheck: add index-all-keys-match verification for B-Tree

Hi Jakub,

Many thanks for your reviews, patches and performance measurements!
Sorry for the long pause. Attached is v6, a reworked patchset that
incorporates your work and Wenbo's findings. It consists of 4 steps:

0001 - core indexallkeysmatch verification
0002 - detection of dangling index entries (based on your "take 2")
0003 - detection of lost heap segments (your patch)
0004 - documentation

Below is how your notes were addressed.

> Here's my attempt at the fixing the LP_DEAD tuples being reported as false
> positives by the v4 patchset as stated earlier.

I took a slightly different route in 0001. The root cause of Wenbo's
false positive was using SnapshotAny to make an existence check that
a regular index scan never makes. In v6 the heap lookup mirrors an
index scan exactly: table_index_fetch_tuple() with the same MVCC
snapshot used for fingerprinting. It follows LP_REDIRECT and HOT
chains (which table_tuple_fetch_row_version() does not - a redirected
HOT chain root would previously return "not found" and never get its
keys verified), and a "not found" result is simply skipped, just like
an index scan would do. This kills the LP_DEAD race by construction:
no page state inspection is needed on the common path.

Your line pointer inspection can be found as 0002, a follow-up check
when the MVCC fetch finds nothing. There I had to restrict it
somewhat:

* beyond-EOF TIDs are reported at any lock level - relation extension
only grows the heap and truncation requires AccessExclusiveLock,
which our AccessShareLock blocks;

* out-of-range offsets and LP_UNUSED slots are reported only under
ShareLock, i.e. bt_index_parent_check(). Under AccessShareLock
there is a narrow race: we verify a copy of the index page, so
concurrent VACUUM phase 2 may have already removed the index entry
we are holding and set the heap slot LP_UNUSED (or truncated the
line pointer array). We cannot distinguish that from corruption, so
bt_index_check() stays silent. Under ShareLock VACUUM is blocked,
and opportunistic pruning only sets LP_UNUSED for HOT chain member
slots, which are never referenced from indexes - so there the
report is reliable.

So the answer to your question about taking ShareUpdateExclusiveLock
in bt_index_check() is: with the MVCC approach it is not needed. The
key-match verification itself works fine under AccessShareLock; only
the LP_UNUSED detection needs the stronger lock, and users who want
it can run bt_index_parent_check().

> Note that the pg_amcheck/003_check (not contrib/amcheck) still blows-up:
> [...] IMHO, we should remove that tes there, but I have not done so far this
> far as I simply do not know if that's acceptable.

I think I found a way that does not require touching the test. In
0003 the beyond-EOF checks are now disabled in one narrow case: when
the first segment of the heap's main fork is missing entirely
(smgrexists() returns false). That case is different from the silent
data loss your patch targets: with segment 0 gone, every heap access
already fails loudly with "could not open file", so there is nothing
silent to detect. The silent case - a missing or truncated
higher-numbered segment, where mdnblocks() happily returns a short
size without any error - is still detected exactly as in your patch.

It is worth spelling out that today PostgreSQL simply has no way to
notice that a relation file is missing or shorter than it should be:
the relation size is defined by whatever files are present, there is
no record of the expected size to compare against. This patchset
creates the first such way, by cross-checking heap size against
index TIDs.

The reason for the skip is that bt_index_check() without heap-related
options historically never touches the heap at all, and pg_amcheck
relies on that: in the 003_check test the user explicitly excludes
the corrupt tables with --exclude-table but still checks their
indexes. Failing the pure index-structure check because the
(deliberately excluded) heap is unreadable would be a behavior
regression. With this change the whole pg_amcheck test suite passes.

As for your question whether to make this an option of
indexallkeysmatch: I kept the check unconditional instead. It is a
simple comparison of a leaf tuple's TID against a cached block count,
so it costs nearly nothing on top of the index scan that
bt_index_check() performs anyway, and hiding a cheap check behind an
expensive option (indexallkeysmatch or heapallindexed both read the
whole heap) would make it much less likely to actually run.

I also made the 008 TAP test skip unless the server was built with
--with-segsize-blocks - otherwise the test tables have no second
segment to lose, and the test failed on a standard build.

> 3. This is more a question than finding: assuming extremly big tables, wouldn't
> we benefit from some form of caching for EState in
> bt_verify_index_tuple_points_to_heap()?

Good point, fixed in 0001. The executor state, the slot and the index
fetch context are now created once per verification and reused across
all heap lookups (with ResetPerTupleExprContext() per lookup), so
index expressions are compiled only once.

While rebasing I also noticed that the v4-0005 documentation patch
(two Bloom filters each up to maintenance_work_mem, ~2% probability
of missing an inconsistency) was lost from the v5b series, so 0004
restores those notes and documents which dangling entry cases are
reported at which lock level.

One thing still on my TODO list for a next version: the key
comparison relies on bt_normalize_tuple(), and normalization has
historically been a rich source of subtle bugs for heapallindexed
(TOAST compression differences, and a whole series of follow-up
fixes for various datum representations). indexallkeysmatch compares
freshly formed index tuples against on-page ones from the other
direction, so the same corner cases - and possibly new ones - apply.
I want to go through those known heapallindexed normalization issues
carefully and add targeted tests before we consider this ready, but
I would rather do that as a separate step on top of this patchset
than hold up review of the overall structure. Pointers to cases you
think are most likely to bite here are very welcome.

Best regards, Andrey Borodin.