Re: [PoC] Improve dead tuple storage for lazy vacuum - Mailing list pgsql-hackers

Hi,

I've dreamed to write more compact structure for vacuum for three
years, but life didn't give me a time to.

Let me join to friendly competition.

I've bet on HATM approach: popcount-ing bitmaps for non-empty elements.

Novelties:
- 32 consecutive pages are stored together in a single sparse array
   (called "chunks").
   Chunk contains:
   - its number,
   - 4 byte bitmap of non-empty pages,
   - array of non-empty page headers 2 byte each.
     Page header contains offset of page's bitmap in bitmaps container.
     (Except if there is just one dead tuple in a page. Then it is
     written into header itself).
   - container of concatenated bitmaps.

   Ie, page metadata overhead varies from 2.4byte (32pages in single 
chunk)
   to 18byte (1 page in single chunk) per page.

- If page's bitmap is sparse ie contains a lot of "all-zero" bytes,
   it is compressed by removing zero byte and indexing with two-level
   bitmap index.
   Two-level index - zero bytes in first level are removed using
   second level. It is mostly done for 32kb pages, but let it stay since
   it is almost free.

- If page's bitmaps contains a lot of "all-one" bytes, it is inverted
   and then encoded as sparse.

- Chunks are allocated with custom "allocator" that has no
   per-allocation overhead. It is possible because there is no need
   to perform "free": allocator is freed as whole at once.

- Array of pointers to chunks is also bitmap indexed. It saves cpu time
   when not every 32 consecutive pages has at least one dead tuple.
   But consumes time otherwise. Therefore additional optimization is 
added
   to quick skip lookup for first non-empty run of chunks.
   (Ahhh, I believe this explanation is awful).

Andres Freund wrote 2021-07-20 02:49:
> Hi,
> 
> On 2021-07-19 15:20:54 +0900, Masahiko Sawada wrote:
>> BTW is the implementation of the radix tree approach available
>> somewhere? If so I'd like to experiment with that too.
>> 
>> >
>> > I have toyed with implementing adaptively large radix nodes like
>> > proposed in https://db.in.tum.de/~leis/papers/ART.pdf - but haven't
>> > gotten it quite working.
>> 
>> That seems promising approach.
> 
> I've since implemented some, but not all of the ideas of that paper
> (adaptive node sizes, but not the tree compression pieces).
> 
> E.g. for
> 
> select prepare(
> 1000000, -- max block
> 20, -- # of dead tuples per page
> 10, -- dead tuples interval within a page
> 1 -- page inteval
> );
>         attach  size    shuffled    ordered
> array    69 ms  120 MB  84.87 s          8.66 s
> intset  173 ms   65 MB  68.82 s         11.75 s
> rtbm    201 ms   67 MB  11.54 s          1.35 s
> tbm     232 ms  100 MB   8.33 s          1.26 s
> vtbm    162 ms   58 MB  10.01 s          1.22 s
> radix    88 ms   42 MB  11.49 s          1.67 s
> 
> and for
> select prepare(
> 1000000, -- max block
> 10, -- # of dead tuples per page
> 1, -- dead tuples interval within a page
> 1 -- page inteval
> );
> 
>         attach  size    shuffled    ordered
> array    24 ms   60MB   3.74s            1.02 s
> intset   97 ms   49MB   3.14s            0.75 s
> rtbm    138 ms   36MB   0.41s            0.14 s
> tbm     198 ms  101MB   0.41s            0.14 s
> vtbm    118 ms   27MB   0.39s            0.12 s
> radix    33 ms   10MB   0.28s            0.10 s
> 
> (this is an almost unfairly good case for radix)
> 
> Running out of time to format the results of the other testcases before
> I have to run, unfortunately. radix uses 42MB both in test case 3 and
> 4.

My results (Ubuntu 20.04 Intel Core i7-1165G7):

Test1.

select prepare(1000000, 10, 20, 1); -- original

        attach  size   shuffled
array   29ms    60MB   93.99s
intset  93ms    49MB   80.94s
rtbm   171ms    67MB   14.05s
tbm    238ms   100MB    8.36s
vtbm   148ms    59MB    9.12s
radix  100ms    42MB   11.81s
svtm    75ms    29MB    8.90s

select prepare(1000000, 20, 10, 1); -- Andres's variant

        attach  size   shuffled
array   61ms   120MB  111.91s
intset 163ms    66MB   85.00s
rtbm   236ms    67MB   10.72s
tbm    290ms   100MB    8.40s
vtbm   190ms    59MB    9.28s
radix  117ms    42MB   12.00s
svtm    98ms    29MB    8.77s

Test2.

select prepare(1000000, 10, 1, 1);

        attach  size   shuffled
array   31ms    60MB    4.68s
intset  97ms    49MB    4.03s
rtbm   163ms    36MB    0.42s
tbm    240ms   100MB    0.42s
vtbm   136ms    27MB    0.36s
radix   60ms    10MB    0.72s
svtm    39ms     6MB    0.19s

(Bad radix result probably due to smaller cache in notebook's CPU ?)

Test3

select prepare(1000000, 2, 100, 1);

        attach  size   shuffled
array    6ms    12MB   53.42s
intset  23ms    16MB   54.99s
rtbm   115ms    38MB    8.19s
tbm    186ms   100MB    8.37s
vtbm   105ms    59MB    9.08s
radix   64ms    42MB   10.41s
svtm    73ms    10MB    7.49s

Test4

select prepare(1000000, 100, 1, 1);

        attach  size   shuffled
array  304ms   600MB   75.12s
intset 775ms    98MB   47.49s
rtbm   356ms    38MB    4.11s
tbm    539ms   100MB    4.20s
vtbm   493ms    42MB    4.44s
radix  263ms    42MB    6.05s
svtm   360ms     8MB    3.49s

Therefore Specialized Vaccum Tid Map always consumes least memory amount
and usually faster.


(I've applied Andres's patch for slab allocator before testing)

Attached patch is against 6753911a444e12e4b55 commit of your pgtools 
with
applied Andres's patches for radix method.

I've also pushed it to github:
https://github.com/funny-falcon/pgtools/tree/svtm/bdbench

regards,
Yura Sokolov