Re: Improve search for missing parent downlinks in amcheck

Hi Alexander,

Apologies for the delayed response. I was a little tired from the
deduplication project.

On Mon, Feb 24, 2020 at 2:54 PM Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> Thank you for your review. The revised version is attached.

This has bitrot, because of the deduplication patch. Shouldn't be hard
to rebase, though.

> > 'foo, -inf'
> > 'foo, (1,24)'
> > 'food, -inf'. <-- This pivot tuple's downlink points to the final leaf
> > page that's filled with duplicates of the value 'foo'
> > 'food, (3,19)' <-- This pivot tuple's downlink points to the *first*
> > leaf page that's filled with duplicates of the value 'food'
> > ...

> Thank you for the explanation!

I taught pageinspect to display a "htid" field for pivot tuples
recently, making it easier to visualize this example.

I think that you should say more about how "lowkey" is used here:

> /*
> - * Record if page that is about to become target is the right half of
> - * an incomplete page split. This can go stale immediately in
> - * !readonly case.
> + * Copy current target low key as the high key of right sibling.
> + * Allocate memory in upper level context, so it would be cleared
> + * after reset of target context.
> + *
> + * We only need low key for parent check.
> */
> - state->rightsplit = P_INCOMPLETE_SPLIT(opaque);
> + if (state->readonly && !P_RIGHTMOST(opaque))
> + {

Say something about concurrent page splits, since they're the only
case where we actually use lowkey. Maybe say something like: "We
probably won't end up doing anything with lowkey, but it's simpler for
readonly verification to always have it available".

> Actually, lowkey is used for removing "cousin page verification blind
> spot" when there are incomplete splits. It might happen that we read
> child with hikey matching its parent high key only when
> bt_child_highkey_check() is called for "minus infinity" key of parent
> right sibling. Saving low key helps in this case.

That makes sense to me.

> It appears that these false positives were cause by very basic error made here:
>
> if (!first && !P_IGNORE(opaque))
> {
> /* blkno probably has missing parent downlink */
> bt_downlink_missing_check(state, rightsplit, blkno, page);
> }
>
> actually it should be
>
> if (blkno != downlink && !P_IGNORE(opaque))
> {
> /* blkno probably has missing parent downlink */
> bt_downlink_missing_check(state, rightsplit, blkno, page);
> }
>
> So "blkno == downlink" means blkno has downlink, not being checked
> first in the loop. This is remains of old version of patch which I
> forget to clean. Now the check you've described works for me.
>
> If you still think lowkey check is a problem, please help me figure it out.

* I think that these comments could still be clearer:

> + /*
> + * We're going to try match child high key to "negative
> + * infinity key". This normally happens when the last child
> + * we visited for target's left sibling was an incomplete
> + * split. So, we must be still on the child of target's left
> + * sibling. Thus, we should match to target's left sibling
> + * high key. Thankfully we saved it, it's called a "low key".
> + */

Maybe start with "We cannot try to match child's high key to a
negative infinity key in target, since there is nothing to compare.
However...". Perhaps use terms like "cousin page" and "subtree", which
can be useful. Alternatively, mention this case in the diagram example
at the top of bt_child_highkey_check(). It's tough to write comments
like this, but I think it's worth it.

Note that a high key is also a pivot tuple, so I wouldn't mention high
keys here:

> +/*
> + * Check if two tuples are binary identical except the block number. So,
> + * this function is capable to compare high keys with pivot keys.
> + */
> +static bool
> +bt_pivot_tuple_identical(IndexTuple itup1, IndexTuple itup2)
> +{

v7 looks pretty close to being commitable, though I'll probably want
to update some comments that you haven't touched when you commit this.
I should probably wait until you've committed the patch to go do that.
I'm thinking of things like old comments in bt_downlink_check().

I will test the patch properly one more time when you produce a new
revision. I haven't really tested it since the last time.

--
Peter Geoghegan