Re: btree: downlink right separator/HIKEY optimization

On Fri, Mar 8, 2024 at 2:14 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> What benchmarking have you done here?

I think that the memcmp() test is subtly wrong:

> + if (PointerIsValid(rightsep))
> + {
> + /*
> + * Note: we're not in the rightmost page (see branchpoint earlier in
> + * the loop), so we always have a HIKEY on this page.
> + */
> + ItemId hikeyid = PageGetItemId(page, P_HIKEY);
> + IndexTuple highkey = (IndexTuple) PageGetItem(page, hikeyid);
> +
> + if (ItemIdGetLength(hikeyid) == IndexTupleSize(rightsep) &&
> + memcmp(&highkey[1], &rightsep[1],
> + IndexTupleSize(rightsep) - sizeof(IndexTupleData)) == 0)
> + {
> + break;
> + }
> + }

Unlike amcheck's bt_pivot_tuple_identical, your memcmp() does not
compare relevant metadata fields from struct IndexTupleData. It
wouldn't make sense for it to compare the block number, of course (if
it did then the optimization would simply never work), but ISTM that
you still need to compare ItemPointerData.ip_posid.

Suppose, for example, that you had two very similar pivot tuples from
a multicolumn index on (a int4, b int2) columns. The first/earlier
tuple is (a,b) = "(42, -inf)", due to the influence of suffix
truncation. The second/later tuple is (a,b) = "(42, 0)", since suffix
truncation couldn't take place when the second pivot tuple was
created. (Actually, suffix truncation would have been possible, but it
would have only managed to truncate-away the tiebreak heap TID
attribute value in the case of our second tuple).

There'll be more alignment padding (more zero padding bytes) in the
second tuple, compared to the first. But the tuples are still the same
size. When you go to you memcmp() this pair of tuples using the
approach in v3, the bytes that are actually compared will be
identical, despite the fact that these are really two distinct tuples,
with distinct values. (As I said, you'd have to actually compare the
ItemPointerData.ip_posid metadata to notice this small difference.)

--
Peter Geoghegan