Database Query Optimizer 完全ガイド 2025: Volcano、Cascades、Cost-Based、Cardinality Estimation — PostgreSQL/MySQL 実践分析

はじめに：1行のSQLの魔法

同じクエリ、1000倍の差

次のクエリを見てみよう。

SELECT u.name, o.total
FROM users u JOIN orders o ON u.id = o.user_id
WHERE u.country = 'KR' AND o.created_at > '2025-01-01';

この1行のSQLは少なくとも数十通りの方法で実行できる。

1. usersを先にscan → filter → ordersとnested loop join
2. ordersを先にscan → filter → usersとhash join
3. 両側のindexを利用 → merge join
4. countryのindex + dateのindexの組み合わせ……

各方式の性能差は数百〜数千倍にもなりうる。同じクエリ、同じデータ、まったく違う実行時間。

その選択をする主役がquery optimizerだ。SQLを投入すると、optimizerは以下を行う。

1. クエリをrelational algebraに変換
2. 可能なexecution planを生成
3. 各planのcostを推定
4. 最も安いものを選ぶ

本稿ではこの全工程を解剖する。VolcanoからCascadesまで、cost-based optimizationの原理から現代DBの実践実装まで。

なぜこれを知るべきか

• 遅いクエリのデバッグ：EXPLAINの結果を正確に解釈するにはoptimizerを理解する必要がある。
• index設計：optimizerの選び方を知れば、なぜindexが「使われない」のかが分かる。
• statistics管理：なぜANALYZEが必要か、statisticsがどのように性能を左右するか。
• DB間の違い：PostgreSQL、MySQL、Oracleのoptimizerは互いに大きく異なる。移植時に重要。
• 最新NewSQL：TiDB、CockroachDBのoptimizerはどう違うのか？

1. Optimizerの3つのステージ

ステージ1: Parsing

SQLテキストをAST (Abstract Syntax Tree) に変換する。

SELECT * FROM t WHERE id = 5
        ↓
Select
├── Projection: *
├── From: t
└── Where: Equal(id, 5)

parsingステージでは主に構文チェックを行う。その後にcatalog検証（table/columnの存在確認）も行う。

ステージ2: Rewriting / Logical Optimization

ASTをrelational algebraに変換し、論理的変換を適用する。

• Predicate pushdown：WHERE条件をできる限り内側へ。
• Projection pushdown：必要なcolumnのみ読み取る。
• Constant folding：1 + 2を3に。
• Subquery unnesting：subqueryをjoinに変換。
• View expansion：viewを元のクエリに展開。

このステージは意味を変えない変換群である。

ステージ3: Physical Optimization / Cost-Based

可能なphysical execution planを生成し、costを推定して最も安いものを選ぶ。このステージがoptimizerの真の核心である。

• どのaccess methodを使うか？ (full scan、index scan、index only scan)
• どのjoin algorithmか？ (nested loop、hash join、merge join)
• どのjoin orderか？
• どこでsortするか？

2. Relational Algebraと論理最適化

Relational Algebraの基本

relational algebraは集合論に基づくクエリ言語の数学的モデルである。

• σ (selection)：WHERE (行のフィルタリング)。
• π (projection)：SELECT column (列の選択)。
• ⋈ (join)：table結合。
• ∪ (union)、∩ (intersection)、- (difference)。
• γ (group)：GROUP BY。

SQL：

SELECT name FROM users WHERE age > 30

relational algebra：

π_name(σ_age>30(users))

代数的同値変換

relational algebraには変換規則がある。例：

• Selection分配：σ_p∧q(R) = σ_p(σ_q(R))
• Selection push through join：σ_p(R ⋈ S) = σ_p(R) ⋈ S (pがRのcolumnだけを使う場合)
• Projection push through selection：π_A(σ_p(R)) = π_A(σ_p(π_A∪必要column(R)))
• Join交換：R ⋈ S = S ⋈ R
• Join結合：(R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)

これらの規則を適用すると同じ結果を生む別のクエリになる。

Predicate Pushdownの例

SELECT u.name, o.total
FROM users u JOIN orders o ON u.id = o.user_id
WHERE u.country = 'KR';

初期計画：

π_{name,total}(σ_{country='KR'}(users ⋈ orders))

usersとordersを先にjoinしてからcountryでフィルタ → 非効率。

predicate pushdown適用：

π_{name,total}(σ_{country='KR'}(users) ⋈ orders)

usersでKRだけを先にフィルタし、ordersとjoin → はるかに効率的。

現代のoptimizerはこうした変換を数百種類、自動で適用する。

Projection Pushdown

SELECT name FROM users JOIN orders ON users.id = orders.user_id;

初期計画：usersとordersの全columnを取ってきてjoin後にnameだけ抽出。

最適化：joinの前にusersから(id, name)、ordersからuser_idだけを取る。ネットワークとメモリを大幅に節約。

Subquery Unnesting

SELECT * FROM orders
WHERE user_id IN (SELECT id FROM users WHERE country = 'KR');

このクエリは2通りの実行が可能。

1. Correlated：ordersの各行ごとにsubqueryを実行 → N回のusers scan → 非常に遅い。
2. Unnested：joinに変換。

-- optimizerはこのように変換する
SELECT o.* FROM orders o JOIN users u ON o.user_id = u.id
WHERE u.country = 'KR';

良いoptimizerはこの変換を自動で行う。悪い（あるいは古い）optimizerはcorrelated executionをそのまま実行し、極端に遅くなる。

3. 物理オペレータ：実行の基本単位

Access Method：tableを読む

Sequential Scan (Full Table Scan)：

[Page 1][Page 2][Page 3]...
   ↓       ↓       ↓
すべての行を順次読む

• 大きなtable + 条件なし：速い (sequential I/O)。
• 小さな結果 + 条件あり：遅い (すべての行を捨てる必要がある)。

Index Scan：

B-Tree
   ↓ (条件に合うkeyを探索)
Heap → 該当行を読む

• 小さな結果：非常に速い。
• 大きな結果 (選択度が高い)：random I/Oが多くて遅い。
• 通常、全体の10%以上を返すならfull scanの方が速い。

Index Only Scan：

B-Tree
   ↓ (indexだけで答える)
Heapアクセスなし

必要な全columnがindexにあればheapに触れない。最速のアクセス方式。

Bitmap Index Scan：

Index 1 → bitmap 1
Index 2 → bitmap 2
  ↓
AND/OR結合
  ↓
Heap scan (ソート順)

複数indexの結果を結合。順次アクセスパターンに変換してrandom I/Oを減らす。

Join Algorithm

Nested Loop Join (NLJ)：

for r in R:
    for s in S:
        if r.key == s.key:
            output(r, s)

• 計算量：O(|R| × |S|)。
• indexがあれば：O(|R| × log|S|)。
• 小さなouter + indexのあるinnerに最適。

Hash Join：

# Build phase
hash_table = {}
for r in R:
    hash_table[r.key] = r

# Probe phase
for s in S:
    if s.key in hash_table:
        output(hash_table[s.key], s)

• 計算量：O(|R| + |S|)。
• メモリが必要。
• 大きなtable + indexなしに最適。
• parallelに強い。

Sort-Merge Join：

sort(R, by=key)
sort(S, by=key)

i, j = 0, 0
while i < len(R) and j < len(S):
    if R[i].key == S[j].key:
        output(R[i], S[j])
        # 重複処理
    elif R[i].key < S[j].key:
        i += 1
    else:
        j += 1

• 計算量：O(|R| log|R| + |S| log|S|)。
• 既にソート済みなら：O(|R| + |S|)。
• ORDER BYやindexで既にソートされている場合に最適。
• range joinに対応。

選択の基準

どのjoinを選ぶか？ optimizerはcost functionで比較する。

• NLJ cost：|R| × cost_per_probe
• Hash join cost：|R| × hash_cost + |S| × probe_cost + build_memory
• Merge join cost：sort(R) + sort(S) + scan(R) + scan(S)

ここでの核心は**|R|, |S|が分かっていないことだ。optimizerはこれを推定**しなければならない。

4. Cost-Based Optimization：costの数学

Cost Function

各物理オペレータはcost式を持つ。

Sequential Scan：

cost = seq_page_cost × num_pages + cpu_tuple_cost × num_tuples

Index Scan：

cost = random_page_cost × (index_pages + heap_pages) 
     + cpu_index_tuple_cost × num_matched 
     + cpu_tuple_cost × num_matched

パラメータの意味

PostgreSQLのデフォルト：

seq_page_cost = 1.0          # 順次ディスクページI/O
random_page_cost = 4.0       # ランダムディスクページI/O
cpu_tuple_cost = 0.01        # 行処理のCPUコスト
cpu_index_tuple_cost = 0.005 # indexエントリ処理
cpu_operator_cost = 0.0025   # 演算子実行 (=, <, ...)

これらの値は相対的である。seq_page_cost = 1.0は単なる基準にすぎない。

SSD時代の調整

HDD時代はrandom I/Oがsequential I/Oより圧倒的に遅かった (〜100倍)。そのためrandom_page_cost = 4.0に設定されている。しかしSSDでは差は小さく、NVMeではほぼ同等である。

# SSD環境では
random_page_cost = 1.1

この1つの変更だけでoptimizerはindexをより多く使うようになる。

effective_cache_size

effective_cache_size = 4GB

このパラメータは「OS page cache + PostgreSQLのshared buffersに何MBキャッシュできるか」を教える。optimizerはこの値を参照してindex scanの想定I/Oを調整する。大きければindex優先、小さければfull scan優先。

Join Costの例

SELECT * FROM A JOIN B ON A.id = B.a_id

A：10,000行、B：100,000行、Bにa_id indexあり。

NLJ (Aがouter)：

10,000 × (index_lookup_cost + matched_rows_cost)
≈ 10,000 × (4 + 0.01 × 10)  (Aの各行あたり平均10マッチ)
≈ 40,000 + 1000 = 41,000

Hash Join (Bをbuild)：

build: 100,000 × cpu_tuple_cost = 1,000
probe: 10,000 × (hash_cost + matched_cost) ≈ 10,000 × 0.02 = 200
total: 1,200

hashの方がはるかに安い。optimizerはhash joinを選ぶ。

注意：costは相対比較用であって絶対時間ではない。「cost=1,000」は「1秒」ではない。同じクエリ内で代替案の順位付けに使う。

5. Cardinality Estimation：optimizerの生命

「どれだけの行が出るか？」

optimizerのすべてのcost計算は**各オペレータの結果行数 (cardinality)**に依存する。推定が外れれば計画全体が外れる。

SELECT * FROM users WHERE country = 'KR' AND age > 30;

問い：

• 全usersの数：100万
• country='KR'の選択度：20% → 20万
• age > 30の選択度：40% → 40万
• 両方満たす：？

選択度の独立仮定：20% × 40% = 8% → 8万行と推定。

この推定が実際 (例：5万行) に近ければ良い計画。完全に外れると (例：50万行) 大惨事。

Statistics：optimizerの感覚器

statisticsが正確でなければ推定も正確にはならない。PostgreSQLのpg_statisticに保存される情報は：

1. n_distinct：columnの一意値の数。
2. null_frac：NULLの割合。
3. most_common_vals (MCV)：最も頻出する値。
4. most_common_freqs：MCVの頻度。
5. histogram_bounds：値分布のhistogram (等頻度バケット)。
6. correlation：物理順序と論理順序の相関。

Histogram

column ageのhistogram (100バケット)
[0-5][5-12][12-20][20-25][25-28]...[70-120]
 5%   5%     5%     5%      5%       5%

各バケットは全体の等しい比率 (例：1%) を保持する。バケット範囲が狭いほど値が密集している区間。

クエリ WHERE age > 30：

• 30以上のバケットはいくつか？
• 各バケットは全体の1%。
• 推定：バケット数 × 1% × 総行数。

MCV (Most Common Values)

値が極端に偏っている場合 (例：statuscolumnの90%が'active')：

• MCV：['active', 'inactive', 'pending']
• MCV freqs：[0.9, 0.08, 0.02]

WHERE status = 'active' → 推定：0.9 × 総行数。

MCVにない値はhistogramで推定。

選択度計算の落とし穴

落とし穴1：独立仮定の誤り

WHERE city = 'Seoul' AND country = 'Korea'

optimizer：P(city='Seoul') × P(country='Korea') = 0.1 × 0.2 = 0.02

実際：P(city='Seoul' AND country='Korea') = 0.1 (SeoulはKoreaにしかない)

5倍の差。誤った計画につながる。

解決：Extended Statistics。PostgreSQL 10+で：

CREATE STATISTICS ON (city, country) FROM addresses;
ANALYZE addresses;

これでoptimizerは2つのcolumnの相関を知る。

落とし穴2：LIKEパターン

WHERE name LIKE 'A%'

選択度推定が難しい。optimizerはMCVとhistogramで試みるが、しばしば外す。

落とし穴3：join結果の推定

SELECT * FROM A JOIN B ON A.key = B.key

結果行数推定：

|R ⋈ S| ≈ |R| × |S| / max(n_distinct(A.key), n_distinct(B.key))

この式は「均等分布」の仮定に基づく。実際には偏りがあれば誤差が大きくなる。

ANALYZEの重要性

statisticsはANALYZEコマンドで更新される。

ANALYZE users;  -- 特定table
ANALYZE;        -- 全体

PostgreSQLではautovacuumが定期的にANALYZEを実行する。しかし：

• 大量INSERT/UPDATEの後は手動ANALYZE推奨。
• statisticsが古いとoptimizerが誤った計画を選ぶ。
• 新規tableにANALYZEなしで大量問い合わせを行うとひどい計画が出ることがある。

6. Volcano Optimizer

Goetz Graefeの革新

1993年にGoetz Graefeが発表したVolcano Optimizerは現代query optimizerの起点である。核心のアイデア：

「変換規則の集合であらゆる可能な計画を生成し、最も安いものを選ぶ」

Operator Tree

クエリはlogical operatorのツリーで表現される。

Join
├── Scan(A)
└── Scan(B)

optimizerの目標はこれをcost最小化しつつphysical operatorのツリーに変換することである。

HashJoin
├── SeqScan(A)
└── IndexScan(B)

Transformation Rule

Volcanoは変換規則の集合で探索する。

• Logical → Logical：Join commutativity、associativity。
• Logical → Physical：Join → HashJoin、Join → NestedLoopJoinなど。
• Enforcer：sortが必要ならSortを追加。

Top-down探索

Volcanoは探索をtop-downで進める。

1. ルートオペレータから開始。
2. 各オペレータに可能な物理実装を列挙。
3. 子も再帰的に最適化。
4. すべての部分木のcostを計算して最適を選ぶ。

Memoization

同じ部分問題を何度も扱うと再計算が高コスト。Volcanoはmemoization (計算結果のキャッシュ) を用いる。同じ部分式は一度だけ最適化される。

問題点

Volcanoは優れているが、いくつかの限界があった。

1. Exhaustive search：すべての計画を生成しようとするため、join数が多いと爆発する。
2. Top-downの非効率：上位での決定が下位へ伝播し、複数回再訪する。

これを改善したのがCascadesである。

7. Cascades Optimizer

Graefeの次作

Cascades (1995) もGoetz Graefeの作品である。SQL Server、CockroachDB、Apache Calcite、Greenplumのoptimizerはすべてcascades-based。

主な改良

1. Unified logical/physical transformations：規則を統一的に表現。
2. Memoization構造の改良：「memo」データ構造で重複最適化を防ぐ。
3. Property propagation：sort、distributionなどのpropertyを伝播。
4. Branch-and-bound pruning：明らかに悪い計画は早く諦める。

Memo構造

memoは同値な式のグループの集合である。

Group 1: σ_p(R)
Group 2: σ_p(R) ⋈ S, (R ⋈ S with σ_p pushed)
Group 3: A ⋈ B, B ⋈ A (commutativity)

各groupは同じ結果を生む複数の表現方式を含む。optimizerはgroup単位でcost比較を行う。

Property

Physical Propertiesは計画が持つ特性である。

• Ordering：結果がソートされているか？
• Distribution：分散DBでデータがどうパーティションされているか？
• Uniqueness：結果に重複がないか？

親オペレータが特定のpropertyを要求する場合 (例：Merge Joinがソートされた入力を要求する)、子がそれを提供するかenforcerを追加する (Sort)。

Pruning

探索爆発を防ぐためにpruningを行う。

• 既に見つかった最適costより高い部分問題はスキップ。
• branch-and-boundアルゴリズム。

Cascadesベースのoptimizer

• SQL Server：独自のcascadesベース実装。
• PostgreSQL：cascadesではない (dynamic programmingベース)。
• CockroachDB：cascadesベース。
• Apache Calcite：cascadesベース、Hive/Flink/Beamで使用。
• Presto/Trino：Calcite影響 + 独自実装。

8. PostgreSQLのOptimizer

構造

PostgreSQLはVolcano/Cascadesとは少し異なるアプローチを取る。

• Rewriting → Logical plan
• Plan generation：Dynamic programming + Genetic algorithm。
• Cost estimation：離散cost関数。
• Plan selection：最も安いもの。

Dynamic Programming Join Ordering

join順序の決定にDynamic Programming (DP) を使う。各部分集合の最適joinを求めて組み合わせる。

• 計算量：おおよそO(3^n)。
• n ≤ 12：DPで正確な最適。
• n > 12：geqo_thresholdを超える → Genetic Algorithmに切り替え。

Genetic Algorithm (GEQO)

多数のtable join (例：15個) ではDPは遅すぎるため：

1. ランダムなjoin順序を生成。
2. 「適応度」 (推定cost) を評価。
3. 良いものを交叉/突然変異。
4. 複数世代にわたり進化。
5. 最良を選ぶ。

厳密な最適ではないが、妥当な解を速く見つける。geqo = on (デフォルト)。

Generic vs Custom Plan

PostgreSQLはprepared statementに対して特別な動作をする。

• Custom plan：実行ごとにパラメータに基づき最適化。
• Generic plan：一度だけ最適化して再利用。

PostgreSQLは最初の数回はcustom、その後genericの方が安ければgenericに切り替える。これにより**「最初は速いが、急に遅くなる」**現象が発生することがある。

EXPLAIN

optimizerの決定を見るにはEXPLAIN。

EXPLAIN (ANALYZE, BUFFERS, VERBOSE) 
SELECT u.name, o.total 
FROM users u JOIN orders o ON u.id = o.user_id
WHERE u.country = 'KR';

Hash Join  (cost=10.00..250.00 rows=500 width=64) (actual time=0.1..5.0 rows=487 loops=1)
  Hash Cond: (o.user_id = u.id)
  Buffers: shared hit=234
  ->  Seq Scan on orders o  (cost=0.00..150.00 rows=10000 width=16)
  ->  Hash  (cost=8.00..8.00 rows=100 width=56)
        ->  Index Scan using idx_users_country on users u
              Index Cond: (country = 'KR')

解釈：

• cost：推定cost (開始_cost..全体_cost)。
• rows：推定行数。
• actual：実際の実行時測定値。
• loops：このノードが実行された回数。

推定rowsとactual rowsの差が大きいならstatisticsの問題。ANALYZEが必要。

9. MySQLのOptimizer

歴史

MySQLのoptimizerは長い間heuristicsベースだった。

• 常にtableを固定順序でjoin (左深ツリー)。
• index使用可否をルールで決定。

5.6以降cost-based optimizerを導入し、継続的に改良されている。

Histogram

MySQL 8.0からhistogramをサポート。

ANALYZE TABLE users UPDATE HISTOGRAM ON country WITH 100 BUCKETS;

PostgreSQLよりは遅れて追加されたが効果的である。

Optimizer Hint

MySQLはoptimizerにhintを与えられる。

SELECT /*+ INDEX(users idx_country) */ *
FROM users WHERE country = 'KR';

これは「countryのindexを使え」という指示である。PostgreSQLはhintを公式にはサポートしない (哲学的な違い)。

ICP (Index Condition Pushdown)

MySQLの便利な機能。WHERE条件の一部をindexレベルで評価する。

SELECT * FROM users WHERE country = 'KR' AND age > 30;

index (country, age)がある場合：

1. 通常：country='KR'をindexマッチ → 行をfetch → ageを検査。
2. ICP：country='KR'をindexマッチ → ageの条件をindexレベルでチェック → 通過したものだけfetch。

random I/Oを大きく減らす。

Join Buffer (Block Nested Loop)

indexがない場合、MySQLのデフォルトjoinはBlock Nested Loopである。

join_buffer_sizeだけouterの複数行をメモリに集める
  ↓
inner tableを1回scanして各outer blockとマッチ
  ↓
I/O削減

hash joinはMySQL 8.0.18から追加された。それ以前はblock NLJが唯一の代替手段だった。

10. Optimizerの限界と実戦テクニック

限界1：statisticsが無いか古い

症状：EXPLAINのrows推定が実際とひどく違う。

解決：

ANALYZE my_table;  -- PostgreSQL
ANALYZE TABLE my_table;  -- MySQL

自動ANALYZEが動いているか確認。大きな更新後は手動で実行。

限界2：join数の爆発

20tableのjoinはoptimizerを疲弊させる。時間が指数関数的に増える。

解決：

• viewで分解：よく使う組み合わせをviewに。
• subqueryで分離：部分的に先に計算。
• PostgreSQL：join_collapse_limit、from_collapse_limitの調整。
• MySQL：optimizer_search_depthの調整。

限界3：相関column

WHERE city = 'Seoul' AND country = 'Korea'

独立仮定が外れて推定誤差。extended statistics (PostgreSQL) またはhistogram + correlation情報が必要。

限界4：Skewed data

特定の値が極端に多い場合：

status column: 'active' 99%, 'deleted' 1%

「all-or-nothing」クエリで問題が起こる。

SELECT * FROM t WHERE status = 'deleted';

• statisticsなし：「行数の50%」と推定 → full scan。
• MCVで：「1%」と推定 → index使用。

MCVを正確に捕らえる必要がある。

限界5：パラメータ依存クエリ

PREPARE p AS SELECT * FROM t WHERE x = $1 AND y > $2;

$1 = 'rare_value'と$1 = 'common_value'では最適計画が異なる可能性がある。generic planは両方に最適にはなれない。

解決：

• custom plan強制：PostgreSQLのplan_cache_mode = force_custom_plan。
• 動的SQL：パラメータ化を諦める。

実戦テクニック：Query Rewriting

optimizerが解けない問題をSQL書き換えで解決する。

元 (遅い)：

SELECT * FROM orders
WHERE EXISTS (
  SELECT 1 FROM users
  WHERE users.id = orders.user_id AND users.country = 'KR'
);

書き換え (速い)：

SELECT o.* FROM orders o
INNER JOIN users u ON o.user_id = u.id
WHERE u.country = 'KR';

現代のoptimizerはほとんど自動で変換するが、常にではない。

実戦テクニック：Materialized View

よく実行される重いクエリを事前計算して保存。

CREATE MATERIALIZED VIEW user_order_summary AS
SELECT u.id, u.name, COUNT(o.id) as order_count, SUM(o.total) as total_spent
FROM users u LEFT JOIN orders o ON u.id = o.user_id
GROUP BY u.id, u.name;

REFRESH MATERIALIZED VIEW user_order_summary;

optimizerは (PostgreSQLのデフォルトでは) 自動で活用しないが、アプリケーションから直接使用可能。

実戦テクニック：HintまたはPlan Pinning

最終手段：特定の計画を強制する。

Oracle：

SELECT /*+ INDEX(t idx_t_name) */ * FROM t WHERE name = 'foo';

PostgreSQL (pg_hint_plan拡張)：

/*+ IndexScan(t idx_t_name) */
SELECT * FROM t WHERE name = 'foo';

MySQL：

SELECT * FROM t USE INDEX (idx_t_name) WHERE name = 'foo';

hintは魅力的だが危険である。データ分布が変われば最適ではなくなる可能性がある。最後の手段として。

11. 分散DBのOptimizer

追加の考慮事項

分散DB (CockroachDB、TiDB、Spanner) のoptimizerは追加の考慮がある。

• データlocality：どのノードにどのデータがあるか。
• ネットワークcost：joinをどこで行うか？
• 並列性：複数ノードでの同時実行。
• Exchangeオペレータ：ノード間のデータ移動。

Distributed Join Strategy

Broadcast Join：小さなtableを全ノードに複製。

Small table → broadcast → 各ノードでlocal join

Shuffle Join (Hash Redistribution)：join keyのhashでノードに再分配。

両tableをjoin keyでhash → 同じkeyを同じノードへ

Collocated Join：2つのtableが既に同じkeyでパーティションされていれば、localで即実行。

optimizerはこれらのcostを比較して選択する。

TiDBのOptimizer

TiDBはCost-Based + Rule-Basedのハイブリッド。

• Rule-based：常に適用される変換 (predicate pushdownなど)。
• Cost-based：計画選択にcardinality + costモデル。
• Statistics：histogram + Count-Min Sketchでskew対応。

分散環境の追加の複雑度を克服するために多くの研究が続いている。

クイズで復習

WHERE city = 'Seoul' AND country = 'Korea'

CREATE STATISTICS stat_addr (dependencies) ON city, country FROM addresses;
CREATE STATISTICS stat_addr_ndist (ndistinct) ON city, country FROM addresses;
ANALYZE addresses;

SELECT last_analyze, last_autoanalyze FROM pg_stat_user_tables WHERE relname='mytable';

SELECT attname, n_distinct, most_common_vals, histogram_bounds
FROM pg_stats WHERE tablename = 'mytable';

CREATE STATISTICS s ON col1, col2 FROM mytable;

おわりに：optimizerは協力者だ

重要なまとめ

1. optimizerはstatisticsに依存する。ANALYZEを怠るな。
2. cost基盤である。costパラメータは環境に合わせてチューニング。
3. cardinality estimationが生命である。相関columnにはextended statistics。
4. EXPLAINを読め。estimated vs actualの差が診断の始まり。
5. join順序はoptimizerの難題。table数が多ければhintや書き換えを検討。
6. Cascadesが現代の標準だが、PostgreSQLは独自のDP。
7. hintは最後の手段。statisticsと構造から直せ。

optimizerとの協力

optimizerを敵ではなく協力者と考えよう。

• statisticsを与える：ANALYZE、extended statistics。
• 明確なクエリを書く：optimizerが理解しやすいSQL。
• indexを提供する：必要なaccess pathを確保。
• 測る：EXPLAIN ANALYZEで現実を確認。
• 信じろ、しかし検証せよ：ほとんどの場合、optimizerは正しい。

最後の教訓

optimizerは数十年の研究と数万人のエンジニアの努力の結晶である。勝とうとせず、代わりにoptimizerが正しい判断を下せるよう手伝う。正確なstatistics、適切なindex、明瞭なクエリ。この3つが揃えばSQLは魔法のように速く動く。

次に遅いクエリに出会ったら、まず問おう。

• 「statisticsは最新か？」
• 「optimizerが見ているcardinalityは実際と合っているか？」
• 「私が提供したindexとstatisticsで最適化できる構造か？」

答えが「イエス」なら、optimizerはほぼ常に正しい答えを返す。

参考資料

• The Volcano Optimizer Generator (Graefe, 1993)
• The Cascades Framework for Query Optimization (Graefe, 1995)
• Access Path Selection in a Relational Database Management System (Selinger et al., 1979) - System Rの古典
• PostgreSQL Query Planner
• How PostgreSQL's Query Planner Works (Interdb)
• MySQL Query Optimization
• Apache Calcite Documentation
• CockroachDB SQL Optimizer (Cascades-based)
• Database Internals (Alex Petrov), Chapter 12
• Use the Index, Luke! - index使用法の完全ガイド