On Mon, Aug 31, 2020 at 12:22 PM Thomas Munro <thomas.mu...@gmail.com> wrote: > On Sun, Aug 30, 2020 at 11:08 PM Masahiko Sawada > <masahiko.saw...@2ndquadrant.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
