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

Masahiko Sawada писал 2021-07-27 07:06:
> On Mon, Jul 26, 2021 at 11:01 PM Masahiko Sawada 
> <sawada.mshk@gmail.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.

I can evolve svtm to transparent intset replacement certainly. Using
same trick from radix_to_key it will store tids efficiently:

   shift = pg_ceil_log2_32(MaxHeapTuplesPerPage);
   tid_i = ItemPointerGetOffsetNumber(tid);
   tid_i |= ItemPointerGetBlockNumber(tid) << shift;

Will do today's evening.

regards
Yura Sokolov aka funny_falcon