PostgreSQLの動作分析1(Vacuum)

# はじめに
この記事は執筆者がPostgreSQLの理解を深めるために実施している、PostgreSQLのソースコードの分析記事です。
PostgreSQLの知識が不足している執筆者のスキルアップが目的なので、内容が正確ではなかったり、見る観点が偏っていたりと、
PostgreSQL有識者やCS力（ちから）ガチ勢からすると、突っ込みが入るような内容が多々含まれれている可能性があることにご注意ください。
仕事柄、PostgreSQLと戦うことが多いので、基本的な質問に即答できることはもちろん、ややこしいバグと戦えるようになったらいいなと考えています。

# 対象のバージョン
調査開始時点で最新のリリース済みのバージョンであった12.3を基準にしています。
より新しい12.xや開発中の13.x以降とは実装が異なる可能性があることにご注意ください。

# 参考資料
Chapter 6 Vacuum Processing - The Internals of PostgreSQL
http://www.interdb.jp/pg/pgsql06.html

src/backend/storage/buffer/README
https://github.com/postgres/postgres/blob/master/src/backend/storage/buffer/README

src/backend/access/nbtree/README
https://github.com/postgres/postgres/blob/master/src/backend/access/nbtree/README

# 重要な構造体、定数の定義
PageHeader、ページ自体の構造
https://github.com/postgres/postgres/blob/f1f10a1ba9e17e606a7b217ccccdd3cc4d8cb771/src/include/storage/bufpage.h

ItemId, lp_flags
https://github.com/postgres/postgres/blob/7559d8ebfa11d98728e816f6b655582ce41150f3/src/include/storage/itemid.h

HeapTupleHeaderData, t_infomask, t_infomask2
https://github.com/postgres/postgres/blob/7559d8ebfa11d98728e816f6b655582ce41150f3/src/include/access/htup_details.h

BufferTag, BufferDesc
https://github.com/postgres/postgres/blob/3985b600f57d75b9743d86430cb5c21370057a23/src/include/storage/buf_internals.h

BufferTag, BufferDescに関しては、多分こんな感じの関係性になっています。
どうしてもページへのアクセスが多用されるので、buffer pinやロックのプロトコルなどの存在はどうしても意識する必要があります。
![buffer_relationships.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79343/0c769817-a77b-10ed-498a-4f108c662eb1.png)

BTPageOpaqueData, BTMetaPageData
https://github.com/postgres/postgres/blob/4a70f829d86cb8dbd68f561720e6329f5e818c94/src/include/access/nbtree.h

BTVacInfo
https://github.com/postgres/postgres/blob/4a70f829d86cb8dbd68f561720e6329f5e818c94/src/backend/access/nbtree/nbtutils.c#L1892

# 見る際に気にしていたこと
- ページのロックの取得、解放のタイミング(ロックのスコープ)
- 削除すべき行の記録方法
- ページの空き部分のコンパクト化方法
- WALの出力タイミング
- インデックスのエントリの削除方法 ※BTreeのみを対象として扱っています
- HOT chainが発生している行の扱い

# シーケンス図
Vacuum処理の大雑把なシーケンス図です。
執筆者の理解力不足およびシーケンス力図の作図能力が不足しているため、4つに分割する必要がありました。

## Overview
![Vacuum Overview.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79343/e0206114-2509-cd72-c161-08b3b0068835.png)

## Vacuum a page
![Vacuum a page.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79343/ded44027-0ccc-1c39-4a51-b94fa25f1fc0.png)

## lazy_vacuum_index
![Vacuum an index.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79343/7f64e450-c39d-29f7-69fd-2e3bf10b5391.png)

## lazy_vacuum_heap
![Vacuum a heap page.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79343/57e5e176-b4c6-a63c-3fae-ebf225edfb0b.png)

# pageinspectで覗いてみる
削除によりheap tupleではxmaxが設定されるものの、BTreeのleaf pageではヘッダにそのような情報がないのでそのまま残り、Vacuum実施によって不要なtupleが削除されることがわかります。

~~~

postgres=# CREATE TABLE HOGE(id serial primary key, name varchar);
RT INTO HOGE(name) SELECT generate_series(1, 1000);
ALTER TABLE HOGE SET(autovacuum_enabled=false);
ANALYZE hoge;
CREATE TABLE
postgres=# INSERT INTO HOGE(name) SELECT generate_series(1, 1000);
INSERT 0 1000
postgres=# ALTER TABLE HOGE SET(autovacuum_enabled=false);
ALTER TABLE
postgres=# ANALYZE hoge;

postgres=# SELECT * FROM heap_page_items(get_raw_page('hoge', 0)) LIMIT 5;
 lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax | t_field3 | t_ctid | t_infomask2 | t_infomask | t_hoff | t_bits | t_oid |     t_data
----+--------+----------+--------+--------+--------+----------+--------+-------------+------------+--------+--------+-------+----------------
  1 |   8160 |        1 |     30 |    561 |      0 |        0 | (0,1)  |           2 |       2306 |     24 |        |       | \x010000000531
  2 |   8128 |        1 |     30 |    561 |      0 |        0 | (0,2)  |           2 |       2306 |     24 |        |       | \x020000000532
  3 |   8096 |        1 |     30 |    561 |      0 |        0 | (0,3)  |           2 |       2306 |     24 |        |       | \x030000000533
  4 |   8064 |        1 |     30 |    561 |      0 |        0 | (0,4)  |           2 |       2306 |     24 |        |       | \x040000000534
  5 |   8032 |        1 |     30 |    561 |      0 |        0 | (0,5)  |           2 |       2306 |     24 |        |       | \x050000000535
(5 rows)

postgres=# SELECT * FROM bt_metap('hoge_pkey');
-[ RECORD 1 ]-----------+-------
magic                   | 340322
version                 | 4
root                    | 3
level                   | 1
fastroot                | 3
fastlevel               | 1
oldest_xact             | 0
last_cleanup_num_tuples | -1

postgres=#  SELECT * FROM bt_page_items('hoge_pkey', 3);
-[ RECORD 1 ]-----------------------
itemoffset | 1
ctid       | (1,0)
itemlen    | 8
nulls      | f
vars       | f
data       |
-[ RECORD 2 ]-----------------------
itemoffset | 2
ctid       | (2,1)
itemlen    | 16
nulls      | f
vars       | f
data       | 6f 01 00 00 00 00 00 00
-[ RECORD 3 ]-----------------------
itemoffset | 3
ctid       | (4,1)
itemlen    | 16
nulls      | f
vars       | f
data       | dd 02 00 00 00 00 00 00

postgres=# SELECT * FROM bt_page_items('hoge_pkey', 1) WHERE itemoffset BETWEEN 1 AND 3;
-[ RECORD 1 ]-----------------------
itemoffset | 1
ctid       | (1,1)
itemlen    | 16
nulls      | f
vars       | f
data       | 6f 01 00 00 00 00 00 00
-[ RECORD 2 ]-----------------------
itemoffset | 2
ctid       | (0,1)
itemlen    | 16
nulls      | f
vars       | f
data       | 01 00 00 00 00 00 00 00
-[ RECORD 3 ]-----------------------
itemoffset | 3
ctid       | (0,2)
itemlen    | 16
nulls      | f
vars       | f
data       | 02 00 00 00 00 00 00 00

postgres=# DELETE FROM HOGE WHERE id = 1;
DELETE 1

postgres=# SELECT * FROM heap_page_items(get_raw_page('hoge', 0)) LIMIT 5;
 lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax | t_field3 | t_ctid | t_infomask2 | t_infomask | t_hoff | t_bits | t_oid |     t_data
----+--------+----------+--------+--------+--------+----------+--------+-------------+------------+--------+--------+-------+----------------
  1 |   8160 |        1 |     30 |    561 |    564 |        0 | (0,1)  |        8194 |        258 |     24 |        |       | \x010000000531
  2 |   8128 |        1 |     30 |    561 |      0 |        0 | (0,2)  |           2 |       2306 |     24 |        |       | \x020000000532
  3 |   8096 |        1 |     30 |    561 |      0 |        0 | (0,3)  |           2 |       2306 |     24 |        |       | \x030000000533
  4 |   8064 |        1 |     30 |    561 |      0 |        0 | (0,4)  |           2 |       2306 |     24 |        |       | \x040000000534
  5 |   8032 |        1 |     30 |    561 |      0 |        0 | (0,5)  |           2 |       2306 |     24 |        |       | \x050000000535
(5 rows)

postgres=# SELECT itemoffset, ctid FROM bt_page_items('hoge_pkey', 1) WHERE itemoffset BETWEEN 1 AND 5;
 itemoffset | ctid
------------+-------
          1 | (1,1)
          2 | (0,1)
          3 | (0,2)
          4 | (0,3)
          5 | (0,4)
(5 rows)

postgres=# VACUUM HOGE;
VACUUM

postgres=# SELECT * FROM heap_page_items(get_raw_page('hoge', 0)) LIMIT 5;
 lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax | t_field3 | t_ctid | t_infomask2 | t_infomask | t_hoff | t_bits | t_oid |     t_data
----+--------+----------+--------+--------+--------+----------+--------+-------------+------------+--------+--------+-------+----------------
  1 |      0 |        0 |      0 |        |        |          |        |             |            |        |        |       |
  2 |   8160 |        1 |     30 |    561 |      0 |        0 | (0,2)  |           2 |       2306 |     24 |        |       | \x020000000532
  3 |   8128 |        1 |     30 |    561 |      0 |        0 | (0,3)  |           2 |       2306 |     24 |        |       | \x030000000533
  4 |   8096 |        1 |     30 |    561 |      0 |        0 | (0,4)  |           2 |       2306 |     24 |        |       | \x040000000534
  5 |   8064 |        1 |     30 |    561 |      0 |        0 | (0,5)  |           2 |       2306 |     24 |        |       | \x050000000535
(5 rows)

postgres=# SELECT itemoffset, ctid FROM bt_page_items('hoge_pkey', 1) WHERE itemoffset BETWEEN 1 AND 5;
 itemoffset | ctid
------------+-------
          1 | (1,1)
          2 | (0,2)
          3 | (0,3)
          4 | (0,4)
          5 | (0,5)
(5 rows)

~~~

# 感想
並行して実行中のトランザクションの状態が途中で変わることを考慮して似たようなチェックを繰り返し実行したり、ページ数を取得する際にLock:Extendのロックを取得する等、並行して処理が実行されることも考慮しないといけないですし、かといってVacuumにリソースを割かれて通常のクエリの実行が遅延しても困るので(むしろリソースを使いすぎないようにvacuum_delay_pointで処理を休止させる)、考えることが非常に多いですし、匙加減が難しそうです。

また、index tupleにxmin/xmaxが存在せず、heap tuple側でデータの可視性を担保する関係上、処理を複数パスに分けて不要なインデックス側のleaf pageのtupleを削除してからではないとheap tupleの削除が行えない等、インデックス側の実装も考慮しないといけないので非常にややこしいですね。
この動きはIndexOnlyScanの動きにも関わってくるので(VMがALL VISIBLEでないとheap側の確認が必要となる)、Vacuumを実施することは、単にテーブル/インデックスの肥大化を防ぐだけではなくて、IndexOnlyScanの効率性を上げるうえでも重要なようです。

まとめると、RDBは超難しい、手に負えない。。。