PostgreSQL MVCC の内部構造を徹底解説：Tuple Versioning、Visibility Map、VACUUM まで

はじめに

この記事では、PostgreSQLのMVCC（Multi-Version Concurrency Control）の内部実装を深掘りします。

前回の記事（InnoDB UNDO Log の内部構造を徹底解説）ではMySQLのMVCCを解説しました。PostgreSQLのMVCCはInnoDBと根本的に異なるアプローチを取ります。PostgreSQL 17のソースコードを参照しながら、以下を解説します：

• Tuple Versioning（Heap内にバージョンを保持する方式）
• xmin / xmax によるバージョン管理
• Snapshot（InnoDBのReadViewに相当）
• Visibility Map
• VACUUM（InnoDBのPurgeに相当）

InnoDBとの根本的な違い

InnoDBは「最新版をテーブルに、旧版をUNDO Logに」保持します。PostgreSQLは全バージョンをテーブル（Heap）内に保持します。

InnoDB:
  Clustered Index: [id=1, salary=5000]  ← 最新版のみ
  UNDO Log: salary=4000 → salary=3000   ← 旧版はUNDO領域

PostgreSQL:
  Heap Page: [id=1, salary=3000, xmin=100, xmax=150]  ← 旧版（dead tuple）
             [id=1, salary=4000, xmin=150, xmax=200]  ← 旧版（dead tuple）
             [id=1, salary=5000, xmin=200, xmax=0]    ← 最新版（live tuple）

xmin / xmax：バージョンの生死を管理

PostgreSQLの各タプル（行）にはヘッダにxminとxmaxが記録されます：

typedef struct HeapTupleHeaderData {
    TransactionId t_xmin;   // このタプルを挿入したトランザクションID
    TransactionId t_xmax;   // このタプルを削除/更新したトランザクションID（0=未削除）
    // ... 他のフィールド
} HeapTupleHeaderData;

INSERT

INSERT INTO t VALUES (1, 'Alice');
→ xmin=100（挿入したTxID）, xmax=0（まだ削除されていない）

DELETE

DELETE FROM t WHERE id = 1;
→ 既存タプルの xmax を 200（削除したTxID）に設定
→ タプル自体は消えない（dead tupleになる）

UPDATE = DELETE + INSERT

UPDATE t SET name = 'Bob' WHERE id = 1;

旧タプル: [id=1, name=Alice, xmin=100, xmax=200]  ← xmaxが設定される
新タプル: [id=1, name=Bob,   xmin=200, xmax=0]    ← 新しいタプルが挿入される

InnoDBのUPDATEがin-place更新なのに対し、PostgreSQLは常に新しいタプルを作るのが最大の違いです。

Snapshot：可視性判定

InnoDBのReadViewに相当するのがSnapshotです。

Snapshotの構造

typedef struct SnapshotData {
    TransactionId xmin;        // この値未満のTxIDは確定済み → 見える
    TransactionId xmax;        // この値以上のTxIDは未来 → 見えない
    TransactionId *xip;        // アクティブなTxIDの配列 → 見えない
    uint32        xcnt;        // xip配列の要素数
} SnapshotData;

InnoDBのReadViewとほぼ同じ構造です。

可視性判定のロジック

タプルが見えるか？

1. xmin がコミット済みか？
   → NO: 見えない（挿入トランザクションが未コミット）
   → YES: 次へ

2. xmax が設定されているか？
   → xmax = 0: 見える（削除されていない）
   → xmax > 0: xmax がコミット済みか？
     → YES: 見えない（削除済み）
     → NO: 見える（削除トランザクションが未コミット）

InnoDBがバージョンチェーンを辿るのに対し、PostgreSQLは各タプルのxmin/xmaxを直接チェックします。バージョンチェーンを辿る必要がない分シンプルですが、全バージョンがHeapに散在するため、テーブルスキャンのコストが増えます。

分離レベルとSnapshot

PostgreSQLのSERIALIZABLEはSSI（Serializable Snapshot Isolation）という方式で、ロックではなく依存関係の検出で直列化可能性を保証します。InnoDBのSERIALIZABLEがロックベース（全SELECTがSELECT … FOR SHARE相当）なのとは対照的です。

Visibility Map

全タプルのxmin/xmaxを毎回チェックするのはコストが高いです。Visibility Map（VM）はこれを最適化します。

Heap:
  Page 0: [live tuple, live tuple]        ← 全タプルが全トランザクションから見える
  Page 1: [live tuple, dead tuple]        ← dead tupleあり
  Page 2: [live tuple, live tuple]        ← 全タプルが見える

Visibility Map:
  Page 0: 1  ← all-visible（可視性チェック不要）
  Page 1: 0  ← チェック必要
  Page 2: 1  ← all-visible

• all-visibleなページはIndex Only Scanで直接スキップできる（Heapアクセス不要）
• VACUUMがVisibility Mapを更新する

VACUUM：dead tupleの回収

InnoDBのPurgeに相当するのがVACUUMです。ただし、InnoDBのPurgeが自動的にバックグラウンドで動くのに対し、PostgreSQLのVACUUMはより目に見える存在です。

VACUUMの動作

1. 各ページをスキャン
2. どのSnapshotからも見えないdead tupleを特定
3. dead tupleの領域をFree Spaceとしてマーク（再利用可能に）
4. Visibility Mapを更新

通常のVACUUMはページ内の領域を再利用可能にするだけで、OSにディスク領域を返しません。テーブルのファイルサイズは縮まりません。

VACUUM FULL

テーブル全体を書き直してディスク領域を回収します。ただしテーブル全体をロックするため、本番環境では慎重に使う必要があります。

VACUUM FULL employees;  -- テーブルロックあり、ディスク領域を回収
VACUUM employees;       -- ロックなし、領域を再利用可能にするだけ

autovacuum

PostgreSQLはautovacuumデーモンが自動的にVACUUMを実行します：

-- 主要な設定
autovacuum = on                          -- デフォルトON
autovacuum_vacuum_threshold = 50         -- 最低50行変更で発動
autovacuum_vacuum_scale_factor = 0.2     -- テーブルの20%が変更で発動

InnoDBのPurgeとの比較

まとめ

次回はOracle UNDOを同じ切り口で解説します。

参考文献

• PostgreSQL Documentation: Concurrency Control
• PostgreSQL Documentation: Routine Vacuuming
• PostgreSQL Source Code: src/backend/access/heap/heapam_visibility.c
• PostgreSQL Source Code: src/include/utils/snapshot.h