On Mon, Apr 17, 2023 at 8:49 PM Masahiko Sawada <
sawada.mshk@gmail.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