On Fri, Jun 26, 2026 at 10:54 AM Robert Haas <[email protected]> wrote: > From a certain point of view, the suspicion that the algorithm may be > incorrect is not at all surprising. The fact that we never merge > nbtree pages to improve space utilization is a limitation we've had > since I first got involved with PostgreSQL which was, at the risk of > dating myself, a long time ago. The fact that nobody's fixed yet means > it's probably really hard.
Page deletion is easily the most complicated part of the nbtree design. That is a natural consequence of the absurdly permissive rules for searchers under the Lehman & Yao design. Searchers never need to lock more than one page at a time, on any level. But they can never have an irredeemably bad picture of the tree structure, even with concurrent page deletions. In short, the eye-watering complexity of page deletion is the exact cost you pay to completely avoid lock coupling with the Lehman & Yao design. If you completely ignore page deletion (as in the original L&Y paper), the concurrency rules are simple and intuitive. Most individual nbtree code paths effectively do just that: they pretend page deletion does not exist. Searchers can just move right (as with a concurrent page split) when they land on a deleted page. Everything works out because the real complexity is confined to the page deletion/page recycling code. Confining the complexity to the page deletion code is a very useful property, and one that I *really* don't want to give up. I'm not prepared to say that it could never make sense, but the bar for accepting such a change is *very* high. > I suspect everyone here would love to see a solution to this problem, > but I would personally be beyond impressed if someone managed to come > up with even a working prototype for this in one summer. Even a > respectable amount of progress on figuring out an algorithm would be a > good result, IMHO. > > I don't know what the rules for GSoC are, but if it's still possible > to switch to a different project, that might be worth considering. +1 -- Peter Geoghegan
