Re: Boundary value check in lazy_tid_reaped()

On Mon, Aug 31, 2020 at 1:56 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> I wonder if Roaring bitmaps would work well for this:
>
> https://arxiv.org/abs/1709.07821

Alternatively, perhaps we could use a negative cache of heap blocks
that have no tuples to kill at all. Maybe just a simple array whose
elements are BlockNumber pairs. Each pair represents a range of blocks
known to contain heap pages that *don't* have any TIDs for VACUUM to
kill. The array could be size limited to 8KB, allowing it to be
accessed in L1 cache throughout vacuuming. When the representation
cannot fit in 8KB, maybe we disable the negative cache for the rest of
the VACUUM operation.

This is a bit like Masahiko's min_blkno + max_blkno idea, except: 1).
It's a negative cache, and 2.) There are perhaps as many as 1024
min/max pairs -- not just 1.

It's pretty clear that more than 90% of all calls to lazy_tid_reaped()
return false unless vacuum is running behind (false means "don't kill
this TID, it's alive"). But it could be much more than 90%. This may
be because autovacuum is configured to run more aggressively than the
default settings allow. But it may also happen when LP_DEAD killing in
indexes works well enough to do most of the cleanup needed in
practice. I bet pgbench finds that ~99% of all calls to
lazy_tid_reaped() that take place during index vacuuming find that the
TID doesn't need to be killed. So negative caching could really help.

--
Peter Geoghegan