On Mon, Sep 18, 2023 at 6:29 PM Peter Geoghegan <p...@bowt.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
