実行エンジンとアクセスメソッド ── 計画を実行に移す

このレイヤーの役割：プランナーが選んだ実行計画を実行し、結果をクライアントに返す。テーブルやインデックスへの実際のアクセスを行う。

---

この章で何ができるようになるか：EXPLAIN の出力に現れる各ノード（Seq Scan, Index Scan, Bitmap Scan, Hash Join 等）が内部で何をしているかを説明できるようになる。

---

Volcano モデル：実行エンジンのアーキテクチャ

PostgreSQL を含む多くの RDBMS は **Volcano モデル（Iterator モデル）**で実行エンジンを構成している。

原理：各ノードが next() メソッドを持ち、
      上位ノードが下位ノードの next() を呼んで1行ずつ取得する
      → パイプライン処理（全行をバッファしない）

# Volcano モデルの概念実装
class SeqScanNode:
    """テーブルの全行を順番に返す"""
    def __init__(self, table):
        self.table = table
        self.cursor = 0

    def next(self):
        if self.cursor >= len(self.table):
            return None
        row = self.table[self.cursor]
        self.cursor += 1
        return row

class FilterNode:
    """子ノードから行を受け取り、条件に合うものだけ返す"""
    def __init__(self, child, predicate):
        self.child = child
        self.predicate = predicate

    def next(self):
        while True:
            row = self.child.next()
            if row is None:
                return None
            if self.predicate(row):
                return row

class SortNode:
    """子ノードの全行をソートして返す（パイプラインを「壊す」）"""
    def __init__(self, child, key):
        self.child = child
        self.key = key
        self.sorted_rows = None
        self.cursor = 0

    def next(self):
        # 初回呼び出し時に全行を取得してソート（ブロッキング操作）
        if self.sorted_rows is None:
            rows = []
            while (row := self.child.next()) is not None:
                rows.append(row)
            self.sorted_rows = sorted(rows, key=self.key)

        if self.cursor >= len(self.sorted_rows):
            return None
        row = self.sorted_rows[self.cursor]
        self.cursor += 1
        return row

# 実行計画の組み立て
# SELECT * FROM users WHERE age > 30 ORDER BY name;
plan = SortNode(
    child=FilterNode(
        child=SeqScanNode(users_table),
        predicate=lambda row: row['age'] > 30
    ),
    key=lambda row: row['name']
)

# 結果の取得
while (row := plan.next()) is not None:
    print(row)

---

スキャン方式の詳細

Seq Scan（Sequential Scan）

テーブルの全ページを先頭から順番に読む。

EXPLAIN SELECT * FROM users WHERE status = 'inactive';
-- Seq Scan on users  (cost=0.00..20000.00 rows=100 width=64)
--   Filter: (status = 'inactive'::text)
--   Rows Removed by Filter: 999900

なぜ Seq Scan が選ばれるか:
  1. インデックスがない
  2. 選択率が高い（テーブルの大部分を返す）
  3. テーブルが小さい（全部読んでも速い）
  4. random_page_cost が高い設定（HDD）

Index Scan

B-Tree インデックスを辿り、該当するタプルを直接取得する。

EXPLAIN SELECT * FROM users WHERE id = 12345;
-- Index Scan using users_pkey on users  (cost=0.43..8.45 rows=1 width=64)
--   Index Cond: (id = 12345)

動作:
  1. B-Tree のルートから葉ノードへ辿る（O(log n)）
  2. 葉ノードに記録された TID（ページ番号, オフセット）でテーブルを直接参照
  3. 該当するタプルを返す

コスト:
  インデックスページの読み込み: O(log n) × random_page_cost
  テーブルページの読み込み: rows × random_page_cost（最悪ケース）

Index Only Scan

インデックスだけで結果が返せる場合（テーブルへのアクセスが不要）。

-- covering index: クエリが必要とするカラムが全てインデックスに含まれている
CREATE INDEX idx_users_email ON users(email);

EXPLAIN SELECT email FROM users WHERE email = '[email protected]';
-- Index Only Scan using idx_users_email on users  (cost=0.43..4.45 rows=1 width=32)
--   Index Cond: (email = '[email protected]'::text)

Visibility Map：Index Only Scan が機能するには、ページ内の全タプルが「全トランザクションから見える」ことが保証されている必要がある。VACUUM が Visibility Map を更新する。

Bitmap Index Scan + Bitmap Heap Scan

Index Scan と Seq Scan の中間。複数行を返すが Seq Scan ほど多くない場合に選ばれる。

EXPLAIN SELECT * FROM users WHERE age BETWEEN 20 AND 25;
-- Bitmap Heap Scan on users  (cost=50.00..500.00 rows=5000 width=64)
--   Recheck Cond: ((age >= 20) AND (age <= 25))
--   ->  Bitmap Index Scan on idx_users_age  (cost=0.00..48.75 rows=5000 width=0)
--         Index Cond: ((age >= 20) AND (age <= 25))

動作:
  Phase 1: Bitmap Index Scan
    インデックスを走査して、該当する TID を「ビットマップ」に記録
    ビットマップ: [ページ1: ○, ページ2: ×, ページ3: ○, ...]

  Phase 2: Bitmap Heap Scan
    ビットマップに印がついたページだけを順番に読む
    → ランダムアクセスを減らし、シーケンシャルに近い読み方ができる

利点:
  - Index Scan のランダムアクセスを軽減
  - 複数のインデックスを OR / AND で組み合わせられる（BitmapOr / BitmapAnd）

-- 2つのインデックスの AND 結合
EXPLAIN SELECT * FROM users WHERE age > 30 AND city = 'Tokyo';
-- Bitmap Heap Scan on users
--   Recheck Cond: ((age > 30) AND (city = 'Tokyo'))
--   ->  BitmapAnd
--         ->  Bitmap Index Scan on idx_users_age
--         ->  Bitmap Index Scan on idx_users_city

---

集約（Aggregate）の実行方式

HashAggregate

EXPLAIN SELECT city, COUNT(*) FROM users GROUP BY city;
-- HashAggregate  (cost=200.00..210.00 rows=100 width=40)
--   Group Key: city
--   ->  Seq Scan on users  (cost=0.00..150.00 rows=10000 width=32)

動作:
  ハッシュテーブルを構築: {city → (count)}
  各行を読みながらハッシュテーブルを更新
  → 全行を読み終えたら結果を出力

メモリ: work_mem に収まる必要がある（超えるとディスクへスピル）

GroupAggregate

-- 既にソート済みの入力に対して
-- GroupAggregate  (cost=...)
--   Group Key: city
--   ->  Index Scan using idx_users_city on users

動作:
  入力がソート済みなので、同じキーの行が連続する
  → グループの切れ目を検知しながら集約
  → ハッシュテーブル不要（メモリ効率が良い）

---

パラレルクエリ

PostgreSQL 9.6 以降、大きなテーブルへのクエリを複数のワーカーで並列実行できる。

EXPLAIN SELECT COUNT(*) FROM large_table WHERE condition;
-- Finalize Aggregate  (cost=...)
--   ->  Gather  (cost=...)
--         Workers Planned: 4
--         ->  Partial Aggregate  (cost=...)
--               ->  Parallel Seq Scan on large_table  (cost=...)
--                     Filter: condition

動作:
  1. Gather ノードが N 個のワーカーを起動
  2. テーブルを N 分割し、各ワーカーが Partial Aggregate を計算
  3. Gather が各ワーカーの結果を集めて Finalize Aggregate

-- パラレル関連の設定
SET max_parallel_workers_per_gather = 4;  -- クエリあたり最大4ワーカー
SET min_parallel_table_scan_size = '8MB'; -- 8MB 以上のテーブルで並列化
SET parallel_tuple_cost = 0.1;            -- 並列化のコストペナルティ

---

まとめ

スキャン方式	向いているケース	コスト特性
Seq Scan	大部分を返す / テーブルが小さい	全ページ読み込み
Index Scan	少数行を特定する（高選択性）	O(log n) + ランダムI/O
Index Only Scan	必要カラムがインデックス内	テーブル参照不要
Bitmap Scan	中程度の選択性 / 複数条件の組み合わせ	ランダムI/O を軽減

JOIN 方式	向いているケース
Nested Loop	外側が小さい + 内側にインデックス
Hash Join	両テーブルが大きい + 等価条件
Merge Join	入力がソート済み

＋ － ⟳ ✕