Re: [PoC] Improve dead tuple storage for lazy vacuum

On Mon, Apr 17, 2023 at 8:49 PM Masahiko Sawada <sawada(dot)mshk(at)gmail(dot)com>
wrote:

> > - With lazy expansion and single-value leaves, the root of a radix tree
can point to a single leaf. That might get rid of the need to track
TBMStatus, since setting a single-leaf tree should be cheap.
> >
>
> Instead of introducing single-value leaves to the radix tree as
> another structure, can we store pointers to PagetableEntry as values?

Well, that's pretty much what a single-value leaf is. Now that I've had
time to pause and regroup, I've looked into some aspects we previously put
off for future work, and this is one of them.

The concept is really quite trivial, and it's the simplest and most
flexible way to implement ART. Our, or at least my, documented reason not
to go that route was due to "an extra pointer traversal", but that's
partially mitigated by "lazy expansion", which is actually fairly easy to
do with single-value leaves. The two techniques complement each other in a
natural way. (Path compression, on the other hand, is much more complex.)

> > Note: I've moved the CF entry to the next CF, and set to waiting on
author for now. Since no action is currently required from Masahiko, I've
added myself as author as well. If tackling bitmap heap scan shows promise,
we could RWF and resurrect at a later time.
>
> Thanks. I'm going to continue researching the memory limitation and

Sounds like the best thing to nail down at this point.

> try lazy path expansion until PG17 development begins.

This doesn't seem like a useful thing to try and attach into the current
patch (if that's what you mean), as the current insert/delete paths are
quite complex. Using bitmap heap scan as a motivating use case, I hope to
refocus complexity to where it's most needed, and aggressively simplify
where possible.

--
John Naylor
EDB: http://www.enterprisedb.com