Re: [GSoC 2026] - B-tree Index Bloat Reduction - Approach & Questions

On Fri, Jun 26, 2026 at 10:54 AM Robert Haas <robertmhaas(at)gmail(dot)com> 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