Re: Boundary value check in lazy_tid_reaped()

On Mon, Aug 31, 2020 at 12:22 PM Thomas Munro <thomas(dot)munro(at)gmail(dot)com> wrote:
> On Sun, Aug 30, 2020 at 11:08 PM Masahiko Sawada
> <masahiko(dot)sawada(at)2ndquadrant(dot)com> wrote:
> > So my proposal is to add boundary value check in lazy_tid_reaped()
> > before executing bsearch(3). This will help when index vacuum happens
> > multiple times or when garbage tuples are concentrated to a narrow
> > range.
>
> Makes sense if it's often out of range.

I also think this is a good idea. But I also wonder if it goes far
enough. Only one or two dead TIDs in inconvenient heap pages can
completely defeat the optimization.

A related problem with the TID list is that it is very space
inefficient. It would be nice to fix that problem at some point. We
could make multiple index scans by VACUUM operations much rarer if we
tried. But how can we do all of this together?

I wonder if Roaring bitmaps would work well for this:

https://arxiv.org/abs/1709.07821

This data structure looks like it might work well in lazy_tid_reaped()
(for the TID array), because it offers effective bitmap compression
without compromising on binary search speed. Of course, you'd have to
encode TIDs as bitmaps to make use of the data structure, much like
tidbitmap.c. I imagine that the Roaring bitmap indirection would be
very CPU cache efficient in cases that are similar to the cases
Sawada-san is worried about, but a bit more complicated.

VACUUM would be able to make the summarizing information for the TID
bitmap resident in CPU cache. Only this well-cached summarizing
information (the top-level bitmap range indirection) will need to be
accessed by most individual calls to a Roaring-bitmap-aware
lazy_tid_reaped() that return false (i.e. calls that say "don't kill
this TID, it's alive"). These performance characteristics seem likely
when a certain amount of clustering of dead tuples takes place in the
heap. I bet having completely random positions for dead TIDs almost
never happens -- *some* clustering is practically certain to take
place, even without natural locality in the data (which is itself very
common). Think about how opportunistic pruning accumulates many
LP_DEAD items in heap pages.

There is a reference Roaring bitmap implementation in C, so it's
probably not that hard to experimentally determine how well it would
work:

https://github.com/RoaringBitmap/CRoaring

Lots of open source projects already use it, so there are no problems
with patents. Seems worth investigating. (I also wonder if we could
use it for clog.)

--
Peter Geoghegan