Re: Improving btree performance through specializing by key shape, take 2

On Mon, Sep 18, 2023 at 6:29 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> I also have significant doubts about your scheme for avoiding
> invalidating the bounds of the page based on its high key matching the
> parent's separator. The subtle dynamic prefix compression race
> condition that I was worried about was one caused by page deletion.
> But page deletion doesn't change the high key at all (it does that for
> the deleted page, but that's hardly relevant). So how could checking
> the high key possibly help?

To be clear, page deletion does what I described here (it does an
in-place update of the downlink to the deleted page, so the same pivot
tuple now points to its right sibling, which is our page of concern),
in addition to fully removing the original pivot tuple whose downlink
originally pointed to our page of concern. This is why page deletion
makes the key space "move to the right", very much like a page split
would.

IMV it would be better if it made the key space "move to the left"
instead, which would make page deletion close to the exact opposite of
a page split -- that's what the Lanin & Shasha paper does (sort of).
If you have this symmetry, then things like dynamic prefix compression
are a lot simpler.

ISTM that the only way that a scheme like yours could work, assuming
that making page deletion closer to Lanin & Shasha is not going to
happen, is something even more invasive than that: it might work if
you had a page low key (not just a high key) on every page. You'd have
to compare the lower bound separator key from the parent (which might
itself be the page-level low key for the parent) to the page low key.
That's not a serious suggestion; I'm just pointing out that you need
to be able to compare like with like for a canary condition like this
one, and AFAICT there is no lightweight practical way of doing that
that is 100% robust.

--
Peter Geoghegan