Re: Boundary value check in lazy_tid_reaped()

On Tue, 1 Sep 2020 at 05:56, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
>
> 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.)

Very interesting.

Before getting into CRoaring bitmap, I've done some experiments with
three different methods of recording dead tuple TIDs: array,
array-minmax, and integer set.

'array' is the current method lazy vacuum uses. It just adds dead
tuple TIDs to the simple array of ItemPointerData.
'array-minmax' is the same as 'array' method except for checking min
and max boundaries when deleting index dead tuples (i.g., in
lazy_tid_reaped()).
'intset' uses the integer set (src/backend/lib/integerset.c) to record
dead tuples TIDs. It's an in-memory data structure to hold 64-bit
integers.

In the experiments, I created the table with 4GB and made 20% of total
tuples dirty in all test cases while changing the distribution of
where dead tuples exist within the table. The table has only one
index, therefore I did't use parallel vacuum. I set enough
maintenance_work_mem so that the index scan runs only once. Here is
the result, showing the "total execution time in second (heap scan
time/index vacuum time/table vacuum time/memory usage in MB)”. The
numbers are round down to the nearest decimal.

1. Updated evenly the table (every block has at least one dead tuple).
array : 22 (8/12/2/114)
array-minmax : 20 (8/11/2/114)
intset : 17 (7/8/1/19)

2. Updated the middle of the table.
array : 25 (6/19/0/114)
array-minmax : 17 (6/11/0/114)
intset : 17 (6/11/0/7)

3. Updated the tail of the table.
array : 25 (6/19/0/114)
array-minmax : 18 (6/11/0/114)
intset : 18 (6/11/0/5)

4. Updated both the beginning and the tail of the table.
array : 25 (6/19/0/114)
array-minmax : 23 (6/17/0/114)
intset : 21 (6/14/0/6)

The memory usage is calculated by (# of dead tuples *
sizeof(ItemPointerData)) in both ‘array’ and ‘array-minmax’ case,
although the actual amount of palloc'd memory is different, and by
intset_memory_usage() in ‘intset’ case.

Using the integer set is very memory efficient (5MB vs. 114MB in the
base case) and there is no 1GB limitation. Looking at the execution
time, I had expected that using the integer set is slower on recording
TIDs than using the simple array but in this experiment, there is no
big difference among methods. Perhaps the result will vary if vacuum
needs to record much more dead tuple TIDs. From the results, I can see
a good improvement in the integer set case and probably a good start
but if we want to use it also for lazy vacuum, we will need to improve
it so that it can be used on DSA for the parallel vacuum.

I've attached the patch I used for the experiment that adds xx_vacuum
GUC parameter that controls the method of recording TIDs. Please note
that it doesn't support parallel vacuum.

Regards,

--
Masahiko Sawada http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services