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

On Tue, Jul 21, 2026 at 8:08 PM Andrey Borodin <x4mmm(at)yandex-team(dot)ru> wrote:

Hi Andrey!

> 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:
>
[..]
>
> 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().

Awesome, great!

> > 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.
>

Thanks for positive response, incorporation this small beyond EOF checking
idea into the patchset and for those many plenty fixes and ideas :) I'm
most happy about the conclustion that ShareUpdateExclusiveLock is not need.

It's been some time, so I've reviewed it from scratch and found only mostly
minor stuff:

000[23]: I think they somehwat redundant in terms of beyond EOF error. The
0003's check in bt_target_page_check() always runs, so the beyond-EOF
detection in bt_report_dangling_index_entrybecomes() from 0002 is not
reachable when both are enabled. Maybe we could merge those two patches into
one ?

0004 (docs):

a. Altough we say 'an additional phase verifies that each index tuple points
to a heap tuple', but I'm wondering - even if the commitmsg mention it - if
we shouldn't put into the docs that this means additional heap sequential
scan as for for multi-TB tables, this will be a big cost. I propose simply
writing
'A <new>additional dedicated</new> heap scan is ...'

b. The docs within indexallkeysmatch tags reads as if the beyond-EOF check
would be only happening with indexallkeysmatch enabled, but it's not.

0001:

a. it seems that ordering of verify_common.h may be flagged as an
potential issue by committer (?)

b. it adds pg_surgery into Makefile, but doesn't seem to use it? Is it
leftover or was the intention to use it to test something?
BTW: we seem to miss tests for those LP_UNUSED errors in 0002, not
sure maybe that's related and You misseds some tests there?

0002:

Altough I remember stress-testing this on standby, now I'm not really sure now
today, if we don't need to invalidate the cached file size in recovery. I mean
that state->heapnblocks = RelationGetNumberOfBlocks(state->heaprel) might
still get cached and old value from smgr_cached_nblocks as it's an lseek()
optimization. One way to do that would be to 'reln->smgr_cached_nblocks[forknum]
= InvalidBlockNumber', thoughts on this?

> 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).[..]

It's way outside of my typical area, can You please share some sample pointer or
link?

-J.