Horton

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

Masahiko Sawada <sawada.mshk@gmail.com>

View thread View on postgr.es
From: Masahiko Sawada <sawada.mshk@gmail.com>
To: Peter Geoghegan <pg@bowt.ie>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Date: 2021-07-09T08:30:24Z
Lists: pgsql-hackers 
On Thu, Jul 8, 2021 at 7:51 AM Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Wed, Jul 7, 2021 at 1:24 PM Peter Geoghegan <pg@bowt.ie> wrote:
> > I wonder how much it would help to break up that loop into two loops.
> > Make the callback into a batch operation that generates state that
> > describes what to do with each and every index tuple on the leaf page.
> > The first loop would build a list of TIDs, then you'd call into
> > vacuumlazy.c and get it to process the TIDs, and finally the second
> > loop would physically delete the TIDs that need to be deleted. This
> > would mean that there would be only one call per leaf page per
> > btbulkdelete(). This would reduce the number of calls to the callback
> > by at least 100x, and maybe more than 1000x.
>
> Maybe for something like rtbm.c (which is inspired by Roaring
> bitmaps), you would really want to use an "intersection" operation for
> this. The TIDs that we need to physically delete from the leaf page
> inside btvacuumpage() are the intersection of two bitmaps: our bitmap
> of all TIDs on the leaf page, and our bitmap of all TIDs that need to
> be deleting by the ongoing btbulkdelete() call.

Agreed. In such a batch operation, what we need to do here is to
compute the intersection of two bitmaps.

>
> Obviously the typical case is that most TIDs in the index do *not* get
> deleted -- needing to delete more than ~20% of all TIDs in the index
> will be rare. Ideally it would be very cheap to figure out that a TID
> does not need to be deleted at all. Something a little like a negative
> cache (but not a true negative cache). This is a little bit like how
> hash joins can be made faster by adding a Bloom filter -- most hash
> probes don't need to join a tuple in the real world, and we can make
> these hash probes even faster by using a Bloom filter as a negative
> cache.

Agreed.

>
> If you had the list of TIDs from a leaf page sorted for batch
> processing, and if you had roaring bitmap style "chunks" with
> "container" metadata stored in the data structure, you could then use
> merging/intersection -- that has some of the same advantages. I think
> that this would be a lot more efficient than having one binary search
> per TID. Most TIDs from the leaf page can be skipped over very
> quickly, in large groups. It's very rare for VACUUM to need to delete
> TIDs from completely random heap table blocks in the real world (some
> kind of pattern is much more common).
>
> When this merging process finds 1 TID that might really be deletable
> then it's probably going to find much more than 1 -- better to make
> that cache miss take care of all of the TIDs together. Also seems like
> the CPU could do some clever prefetching with this approach -- it
> could prefetch TIDs where the initial chunk metadata is insufficient
> to eliminate them early -- these are the groups of TIDs that will have
> many TIDs that we actually need to delete. ISTM that improving
> temporal locality through batching could matter a lot here.

That's a promising approach.

In rtbm, the pair of one hash entry and one container is used per
block. Therefore, we can skip TID from the leaf page by checking the
hash table, if there is no dead tuple in the block. If there is the
hash entry, since it means the block has at least one dead tuple, we
can look for the offset of TID from the leaf page from the container.

Regards,

--
Masahiko Sawada
EDB:  https://www.enterprisedb.com/

Commits

  1. radixtree: Fix SIGSEGV at update of embeddable value to non-embeddable.

  2. Get rid of anonymous struct

  3. Teach radix tree to embed values at runtime

  4. Teach TID store to skip bitmap for small numbers of offsets

  5. Use bump context for TID bitmaps stored by vacuum

  6. Fix alignment of stack variable

  7. Use TidStore for dead tuple TIDs storage during lazy vacuum.

  8. Rethink create and attach APIs of shared TidStore.

  9. Fix inconsistent function prototypes with function definitions.

  10. Fix a calculation in TidStoreCreate().

  11. Fix potential integer handling issue in radixtree.h.

  12. Add TIDStore, to store sets of TIDs (ItemPointerData) efficiently.

  13. Fix link error for test_radixtree module on Windows

  14. Blind attempt to fix ODR violations

  15. Fix incorrect format specifier for int64

  16. Fix redefinition of typedefs

  17. Add template for adaptive radix tree

  18. Fix signedness error in 9f225e992 for gcc

  19. Introduce helper SIMD functions for small byte arrays

  20. Optimize vacuuming of relations with no indexes.

  21. Add bound check before bsearch() for performance

  22. Allocate consecutive blocks during parallel seqscans