Re: Improve search for missing parent downlinks in amcheck

On Sun, Mar 8, 2020 at 2:52 PM Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> I've revised this comment. Hopefully it's better now.

I think that the new comments about why we need a low key for the page
are much better now.

> I've updated this comment using terms "cousin page" and "subtree". I
> didn't refer the diagram example, because it doesn't contain
> appropriate case. And I wouldn't like this diagram to contain such
> case, because that probably makes this diagram too complex. I've also
> invented term "uncle page". BTW, should it be "aunt page"? I don't
> know.

I have never heard the term "uncle page" before, but I like it --
though maybe say "right uncle page". That happens to be the exact
relationship that we're talking about here. I think any one of
"uncle", "aunt", or "uncle/aunt" are acceptable. We'll probably never
need to use this term again, but it seems like the right term to use
here.

Anyway, this section also seems much better now.

Other things that I noticed:

* Typo:

> + /*
> + * We don't call bt_child_check() for "negative infinity" items.
> + * But if we're performatin downlink connectivity check, we do it
> + * for every item including "negative infinity" one.
> + */

s/performatin/performing/

* Suggest that you say "has incomplete split flag set" here:

> + * - The call for block 4 will initialize data structure, but doesn't do actual
> + * checks assuming page 4 has incomplete split.

* More importantly, is this the right thing to say about page 4? Isn't
it also true that page 4 is the leftmost leaf page, and therefore kind
of special in another way? Even without having the incomplete split
flag set at all? Wouldn't it be better to address the incomplete split
flag issue by making that apply to some other page that isn't also the
leftmost? That would allow you to talk about the leftmost case
directly here. Or it would at least make it less confusing.

BTW, a P_LEFTMOST() assertion at the beginning of
bt_child_highkey_check() would make this easier to follow.

* Correct spelling is "happens" here:

> + * current child page is not incomplete split, then its high key
> + * should match to the target's key of current offset number. This
> + * happends when child page referenced by previous downlink is

* Actually, maybe this whole sentence should be reworded instead --
say "This happens when a previous call here (to
bt_child_highkey_check()) found an incomplete split, and we reach a
right sibling page without a downlink -- the right sibling page's high
key still needs to be matched to a separator key on the parent/target
level".

* Maybe say "Don't apply OffsetNumberNext() to target_downlinkoffnum
when we already had to step right on the child level. Our traversal of
the child level must try to move in perfect lockstep behind (to the
left of) the target/parent level traversal."

I found this detail very confusing at first.

* The docs should say "...relationships, including checking that there
are no missing downlinks in the index structure" here:

> unlike <function>bt_index_check</function>,
> <function>bt_index_parent_check</function> also checks
> - invariants that span parent/child relationships.
> + invariants that span parent/child relationships including check
> + that there are no missing downlinks in the index structure.
> <function>bt_index_parent_check</function> follows the general
> convention of raising an error if it finds a logical
> inconsistency or other problem.

This is very close now. I would be okay with you committing the patch
once you deal with this feedback. If you prefer, I can take another
look at a new revision.

--
Peter Geoghegan