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

On Mon, Jul 26, 2021 at 11:01 PM Masahiko Sawada <sawada(dot)mshk(at)gmail(dot)com> wrote:
>
> I'll experiment with the proposed ideas including this idea in more
> scenarios and share the results tomorrow.
>

I've done some benchmarks for proposed data structures. In this trial,
I've done with the scenario where dead tuples are concentrated on a
particular range of table blocks (test 5-8), in addition to the
scenarios I've done in the previous trial. Also, I've done benchmarks
of each scenario while increasing table size. In the first test, the
maximum block number of the table is 1,000,000 (i.g., 8GB table) and
in the second test, it's 10,000,000 (80GB table). We can see how
performance and memory consumption changes with a large-scale table.
Here are the results:

* Test 1
select prepare(
1000000, -- max block
10, -- # of dead tuples per page
1, -- dead tuples interval within a page
1, -- # of consecutive pages having dead tuples
20 -- page interval
);

name | attach | attach | shuffled | size_x10 | attach_x10| shuffled_x10
--------+-----------+--------+----------+------------+-----------+-------------
array | 57.23 MB | 0.040 | 98.613 | 572.21 MB | 0.387 | 1521.981
intset | 46.88 MB | 0.114 | 75.944 | 468.67 MB | 0.961 | 997.760
radix | 40.26 MB | 0.102 | 18.427 | 336.64 MB | 0.797 | 266.146
rtbm | 64.02 MB | 0.234 | 22.443 | 512.02 MB | 2.230 | 275.143
svtm | 27.28 MB | 0.060 | 13.568 | 274.07 MB | 0.476 | 211.073
tbm | 96.01 MB | 0.273 | 10.347 | 768.01 MB | 2.882 | 128.103

* Test 2
select prepare(
1000000, -- max block
10, -- # of dead tuples per page
1, -- dead tuples interval within a page
1, -- # of consecutive pages having dead tuples
1 -- page interval
);

name | attach | attach | shuffled | size_x10 | attach_x10| shuffled_x10
--------+-----------+--------+----------+------------+-----------+-------------
array | 57.23 MB | 0.041 | 4.757 | 572.21 MB | 0.344 | 71.228
intset | 46.88 MB | 0.127 | 3.762 | 468.67 MB | 1.093 | 49.573
radix | 9.95 MB | 0.048 | 0.679 | 82.57 MB | 0.371 | 16.211
rtbm | 34.02 MB | 0.179 | 0.534 | 288.02 MB | 2.092 | 8.693
svtm | 5.78 MB | 0.043 | 0.239 | 54.60 MB | 0.342 | 7.759
tbm | 96.01 MB | 0.274 | 0.521 | 768.01 MB | 2.685 | 6.360

* Test 3
select prepare(
1000000, -- max block
2, -- # of dead tuples per page
100, -- dead tuples interval within a page
1, -- # of consecutive pages having dead tuples
1 -- page interval
);

name | attach | attach | shuffled | size_x10 | attach_x10| shuffled_x10
--------+-----------+--------+----------+------------+-----------+-------------
array | 11.45 MB | 0.009 | 57.698 | 114.45 MB | 0.076 | 1045.639
intset | 15.63 MB | 0.031 | 46.083 | 156.23 MB | 0.243 | 848.525
radix | 40.26 MB | 0.063 | 13.755 | 336.64 MB | 0.501 | 223.413
rtbm | 36.02 MB | 0.123 | 11.527 | 320.02 MB | 1.843 | 180.977
svtm | 9.28 MB | 0.053 | 9.631 | 92.59 MB | 0.438 | 212.626
tbm | 96.01 MB | 0.228 | 10.381 | 768.01 MB | 2.258 | 126.630

* Test 4
select prepare(
1000000, -- max block
100, -- # of dead tuples per page
1, -- dead tuples interval within a page
1, -- # of consecutive pages having dead tuples
1 -- page interval
);

name | attach | attach | shuffled | size_x10 | attach_x10| shuffled_x10
--------+-----------+--------+----------+------------+-----------+-------------
array | 572.21 MB | 0.367 | 78.047 | 5722.05 MB | 3.942 | 1154.776
intset | 93.74 MB | 0.777 | 45.146 | 937.34 MB | 7.716 | 643.708
radix | 40.26 MB | 0.203 | 9.015 | 336.64 MB | 1.775 | 133.294
rtbm | 36.02 MB | 0.369 | 5.639 | 320.02 MB | 3.823 | 88.832
svtm | 7.28 MB | 0.294 | 3.891 | 73.60 MB | 2.690 | 103.744
tbm | 96.01 MB | 0.534 | 5.223 | 768.01 MB | 5.679 | 60.632

* Test 5
select prepare(
1000000, -- max block
150, -- # of dead tuples per page
1, -- dead tuples interval within a page
10000, -- # of consecutive pages having dead tuples
20000 -- page interval
);

There are 10000 consecutive pages that have 150 dead tuples at every
20000 pages.

name | attach | attach | shuffled | size_x10 | attach_x10| shuffled_x10
--------+-----------+--------+----------+------------+-----------+-------------
array | 429.16 MB | 0.274 | 75.664 | 4291.54 MB | 3.067 | 1259.501
intset | 46.88 MB | 0.559 | 36.449 | 468.67 MB | 4.565 | 517.445
radix | 20.26 MB | 0.166 | 8.466 | 196.90 MB | 1.273 | 166.587
rtbm | 18.02 MB | 0.242 | 8.491 | 160.02 MB | 2.407 | 171.725
svtm | 3.66 MB | 0.243 | 3.635 | 37.10 MB | 2.022 | 86.165
tbm | 48.01 MB | 0.344 | 9.763 | 384.01 MB | 3.327 | 151.824

* Test 6
select prepare(
1000000, -- max block
10, -- # of dead tuples per page
1, -- dead tuples interval within a page
10000, -- # of consecutive pages having dead tuples
20000 -- page interval
);

There are 10000 consecutive pages that have 10 dead tuples at every 20000 pages.

name | attach | attach | shuffled | size_x10 | attach_x10| shuffled_x10
--------+-----------+--------+----------+------------+-----------+-------------
array | 28.62 MB | 0.022 | 2.791 | 286.11 MB | 0.170 | 46.920
intset | 23.45 MB | 0.061 | 2.156 | 234.34 MB | 0.501 | 32.577
radix | 5.04 MB | 0.026 | 0.433 | 48.57 MB | 0.191 | 11.060
rtbm | 17.02 MB | 0.074 | 0.533 | 144.02 MB | 0.954 | 11.502
svtm | 3.16 MB | 0.023 | 0.206 | 27.60 MB | 0.175 | 4.886
tbm | 48.01 MB | 0.132 | 0.656 | 384.01 MB | 1.284 | 10.231

* Test 7
select prepare(
1000000, -- max block
150, -- # of dead tuples per page
1, -- dead tuples interval within a page
1000, -- # of consecutive pages having dead tuples
999000 -- page interval
);

There are pages that have 150 dead tuples at first 1000 blocks and
last 1000 blocks.

name | attach | attach | shuffled | size_x10 | attach_x10| shuffled_x10
--------+-----------+--------+----------+------------+-----------+-------------
array | 1.72 MB | 0.002 | 7.507 | 17.17 MB | 0.011 | 76.510
intset | 0.20 MB | 0.003 | 6.742 | 1.89 MB | 0.022 | 52.122
radix | 0.20 MB | 0.001 | 1.023 | 1.07 MB | 0.007 | 12.023
rtbm | 0.15 MB | 0.001 | 2.637 | 0.65 MB | 0.009 | 34.528
svtm | 0.52 MB | 0.002 | 0.721 | 0.61 MB | 0.010 | 6.434
tbm | 0.20 MB | 0.002 | 2.733 | 1.51 MB | 0.015 | 38.538

* Test 8
select prepare(
1000000, -- max block
100, -- # of dead tuples per page
1, -- dead tuples interval within a page
50, -- # of consecutive pages having dead tuples
100 -- page interval
);

There are 50 consecutive pages that have 100 dead tuples at every 100 pages.

name | attach | attach | shuffled | size_x10 | attach_x10| shuffled_x10
--------+-----------+--------+----------+------------+-----------+-------------
array | 286.11 MB | 0.184 | 67.233 | 2861.03 MB | 1.743 | 979.070
intset | 46.88 MB | 0.389 | 35.176 | 468.67 MB | 3.698 | 505.322
radix | 21.82 MB | 0.116 | 6.160 | 186.86 MB | 0.891 | 117.730
rtbm | 18.02 MB | 0.182 | 5.909 | 160.02 MB | 1.870 | 112.550
svtm | 4.28 MB | 0.152 | 3.213 | 37.60 MB | 1.383 | 79.073
tbm | 48.01 MB | 0.265 | 6.673 | 384.01 MB | 2.586 | 101.327

Overall, 'svtm' is faster and consumes less memory. 'radix' tree also
has good performance and memory usage.

From these results, svtm is the best data structure among proposed
ideas for dead tuple storage used during lazy vacuum in terms of
performance and memory usage. I think it can support iteration by
extracting the offset of dead tuples for each block while iterating
chunks.

Apart from performance and memory usage points of view, we also need
to consider the reusability of the code. When I started this thread, I
thought the best data structure would be the one optimized for
vacuum's dead tuple storage. However, if we can use a data structure
that can also be used in general, we can use it also for other
purposes. Moreover, if it's too optimized for the current TID system
(32 bits block number, 16 bits offset number, maximum block/offset
number, etc.) it may become a blocker for future changes.

In that sense, radix tree also seems good since it can also be used in
gist vacuum as a replacement for intset, or a replacement for hash
table for shared buffer as discussed before. Are there any other use
cases? On the other hand, I’m concerned that radix tree would be an
over-engineering in terms of vacuum's dead tuples storage since the
dead tuple storage is static data and requires only lookup operation,
so if we want to use radix tree as dead tuple storage, I'd like to see
further use cases.

Regards,

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