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

On Wed, Apr 19, 2023 at 4:02 PM John Naylor
<john(dot)naylor(at)enterprisedb(dot)com> wrote:
>
> 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.
>

I agree that we don't want to make the current patch complex further.

Thinking about the memory limitation more, I think that combination of
the idea of specifying the initial and max DSA segment size and
dsa_set_size_limit() works well. There are two points in terms of
memory limitation; when the memory usage reaches the limit we want (1)
to minimize the last allocated memory block that is allocated but not
used yet and (2) to minimize the amount of memory that exceeds the
memory limit. Since we can specify the maximum DSA segment size, the
last allocated block before reaching the memory limit is small. Also,
thanks to dsa_set_size_limit(), the total DSA size will stop at the
limit, so (memory_usage >= memory_limit) returns true without any
exceeding memory.

Given that we need to configure the initial and maximum DSA segment
size and set the DSA limit for TidStore memory accounting and
limiting, it would be better to create the DSA for TidStore by
TidStoreCreate() API, rather than creating DSA in the caller and pass
it to TidStoreCreate().

Regards,

--
Masahiko Sawada
Amazon Web Services: https://aws.amazon.com