Re: new heapcheck contrib module

On Tue, Aug 4, 2020 at 9:44 AM Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> I think it might be possible to distinguish between different types of
> corruption and to separate, at least to some degree, the checking
> associated with each type. I think one can imagine something that
> checks the structure of a btree without regard to the contents. That
> is, it cares that left and right links are consistent with each other
> and with downlinks from the parent level. So it checks things like the
> left link of the page to which my right link points is pointing back
> to me, and that's also the page to which my parent's next downlink
> points.

I think that this kind of phased approach to B-Tree verification is
possible, more or less, but hard to justify. And it seems impossible
to do with only an AccessShareLock.

It's not clear that what you describe is much better than just
checking a bunch of indexes and seeing what patterns emerge. For
example, the involvement of collated text might be a common factor
across indexes. That kind of pattern is the first thing that I look
for, and often the only thing. It also serves to give me an idea of
how messed up things are. There are not that many meaningful degrees
of messed-up with indexes in my experience. The first error really
does tell you most of what you need to know about any given corrupt
index. Kind of like how you can bucket the number of cockroaches in
your home into perhaps three meaningful buckets: 0 cockroaches, at
least 1 cockroach, and lots of cockroaches. (Even there, if you really
care about the distinction between the second and third bucket,
something has gone terribly wrong -- so even three buckets seems like
a lot to me.)

FWIW, current DEBUG1 + DEBUG2 output for amcheck shows you quite a lot
of details about the tree structure. It's a handy way of getting a
sense of what's going on at a high level. For example, if index
corruption is found very early on, that strongly suggests that it's
pretty pervasive.

> Now a second type of checking, which can also be done without regard
> to keys, is checking that the TIDs in the index point to TIDs that are
> on heap pages that actually exist, and that the corresponding items
> are not unused, nor are they tuples which are not the root of a HOT
> chain. Passing a check of this type doesn't prove that the index and
> heap are consistent, but failing it proves that they are inconsistent.
> This kind of check can be done on every leaf index page you can find
> by any means even if it fails the structural checks described above.
> Failure of these checks on one page does not preclude checking the
> same invariants for other pages. Let's call this kind of thing "basic
> index-heap sanity checking."

One real weakness in the current code is our inability to detect index
tuples that are in the correct order and so on, but point to the wrong
thing -- we can detect that if it manifests itself as the absence of
an index tuple that should be in the index (when you use
heapallindexed verification), but we cannot *reliably* detect the
presence of an index tuple that shouldn't be in the index at all
(though in practice it probably mostly gets caught).

The checks on the tree structure itself are excellent with
bt_index_parent_check() following Alexander's commit d114cc53 (which I
thought was really excellent work). But we still have that one
remaining blind spot in verify_nbtree.c, even when you opt in to every
possible type of verification (i.e. bt_index_parent_check() with all
options). I'd much rather fix that, or help with the new heap checker
stuff.

> A fourth type of checking is to verify the index key against the keys
> in the heap tuples to which they point, but only for index tuples that
> passed the basic index-heap sanity checking and where the tuples have
> not been pruned. This can be sensibly done even if the structural
> checks or index-ordering checks have failed.

That's going to require the equivalent of a merge join, which is
terribly expensive relative to such a small benefit.

> Aside from providing a way to usefully continue after errors, this
> would also be useful in certain scenarios where you want to know what
> kind of corruption you have. For example, suppose that I start getting
> wrong answers from index lookups on a particular index. Upon
> investigation, it turns out that my last glibc update changed my OS
> collation definitions for the collation I'm using, and therefore it is
> to be expected that some of my keys may appear to be out of order with
> respect to the new definitions. Now what I really want to know before
> running REINDEX is that this is the only problem I have. It would be
> amazing if I could run the tool and have it give me a list of problems
> so that I could confirm that I have only index-ordering problems, not
> any other kind, and even more amazing if it could tell me the specific
> keys that were affected so that I could understand exactly how the
> sorting behavior changed.

This detail seems really hard. There are probably lots of cases where
the sorting behavior changed but it just didn't affect you, given the
data you had -- it just so happened that you didn't have exactly the
wrong kind of diacritic mark or whatever. After all, revisions to how
strings in a given natural language are supposed to sort are likely to
be relatively rare and relatively obscure (even among people that
speak the language in question). Also, the task of figuring out if the
tuple to the left or the right is in the wrong order seems kind of
daunting.

Meanwhile, a simple smoke test covering many indexes probably gives
you a fairly meaningful idea of the extent of the damage, without
requiring that we do any hard engineering work.

> I'm speaking here with fairly limited knowledge of the details of how
> all this actually works and, again, I'm not trying to suggest that you
> or anyone is obligated to do any work on this, or that it would be
> easy to accomplish or worth the time it took. I'm just trying to
> sketch out what I see as maybe being theoretically possible, and why I
> think it would be useful if it did.

I don't think that your relatively limited knowledge of the B-Tree
code is an issue here -- your intuitions seem pretty reasonable. I
appreciate your perspective here. Corruption detection presents us
with some odd qualitative questions of the kind that are just awkward
to discuss. Discouraging perspectives that don't quite match my own
would be quite counterproductive.

That having been said, I suspect that this is a huge task for a small
benefit. It's exceptionally hard to test because you have lots of
non-trivial code that only gets used in circumstances that by
definition should never happen. If users really needed to recover the
data in the index then maybe it would happen -- but they don't.

The biggest problem that amcheck currently has is that it isn't used
enough, because it isn't positioned as a general purpose tool at all.
I'm hoping that the work from Mark helps with that.

--
Peter Geoghegan