Re: Improve search for missing parent downlinks in amcheck

On Tue, Mar 10, 2020 at 3:07 AM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> 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.

Good, thank you.

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

According to context that should be left uncle page. I've changed the
text accordingly.

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

Fixed.

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

Yes, that sounds better. Changed here and in the other places.

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

Yes, current example looks confusing in this aspect. But your comment
spotted to me an algorithmic issue. We don't match highkey of
leftmost child against parent pivot key. But we can. The "if
(!BlockNumberIsValid(blkno))" branch survived from the patch version
when we didn't match high keys. I've revised it. Now we enter the
loop even for leftmost page on child level and match high key for that
page.

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

Yes, but why should it be an assert? We can imagine corruption, when
there is left sibling of first child of leftmost target. I guess,
current code would report such situation as an error, because this
left sibling lacks of parent downlink. I've revised that "if" branch,
so we don't load a child page there anymore. Error reporting is added
to the main loop.

> * 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 comments are revised as you proposed.

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

Thank you. I'd like to have another feedback from you assuming there
are logic changes.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company