クエリオプティマイザの内部

オプティマイザは何を決めているのか

同じ結果を返す SQL でも、表をどの順で結合し、各表をどの方式で読むかによって速度は桁違いに変わります。クエリオプティマイザは、論理的に等価な無数の実行方法の中から、推定コストが最小のものを1つ選ぶコンポーネントです。EXPLAIN（→ クエリ最適化）で見える実行計画は、この選択の最終結果にすぎません。本稿では「どう選ばれるか」を内部から追います。

4段階の変換パイプライン

オプティマイザを含む処理系は、SQL を次の順で変換します。

論理プランは関係代数の木で、ノードは選択（σ）・射影（π）・結合（⋈）・集約などの論理演算子です。これは「意味」だけを表し、まだアルゴリズムを含みません。一方、物理プランの各ノードは Seq Scan / Index Scan / Hash Join / Merge Join のような物理演算子で、CPU とディスクが実際に行う手続きに対応します。1つの論理演算子（例：結合）は複数の物理演算子（Nested Loop / Hash / Merge）に展開でき、ここに選択の自由度が生まれます。

論理プランの書き換え（等価変換）

物理化の前に、オプティマイザは関係代数の等価規則でプランを整形します。結果を変えずに、後段が扱いやすい・コストが下がりやすい形へ寄せる前処理です。

• 述語のプッシュダウン: σ（選択）を結合より下、表の走査直後へ押し下げ、早い段階で行数を絞る。
• 射影のプッシュダウン: 不要な列を早く落とし、中間結果の幅を狭める。
• 結合の交換・結合律: A ⋈ B = B ⋈ A、(A ⋈ B) ⋈ C = A ⋈ (B ⋈ C) を使い、後の探索で結合順序を自由に組み替えられるようにする。
• 副問い合わせの平坦化: 相関サブクエリを結合（semi join / anti join）へ書き換え、N+1 的な反復を避ける。

コストベース最適化の中身

物理プランの候補それぞれに対し、オプティマイザは推定コストを計算します。コストは実時間（ms）ではなく、I/O と CPU の作業量を見積もった相対値です。PostgreSQL を例にすると、概念的には次の合算です。

推定コスト ≈ (読むページ数 × ページI/O単価)
           + (処理する行数 × 行あたりCPU単価)
           + (評価する式の数 × 式CPU単価)

各単価はパラメータ（seq_page_cost、random_page_cost、cpu_tuple_cost など）で、ランダム読みは逐次読みより高く見積もられます。重要なのは、これらの式に入る「ページ数」「行数」が統計情報からの推定値だという点です。つまりコスト計算の精度は、後述する統計の鮮度と精度に完全に依存します。

オプティマイザは候補プランを木の下から組み立て、部分プランごとに「コスト」と「出力推定行数（カーディナリティ）」を伝播させます。親ノードのコストは子のコストと自分の処理コストの和で決まるため、下流の行数推定が狂うと上流まで誤差が増幅します。

統計情報とカーディナリティ推定

統計情報は、各列の値の分布を要約したメタデータです。代表的に次を保持します。

選択率（selectivity） は、ある条件が全体の何割を通すかの推定値です。例えば n_distinct が 1000 の列に等値条件を掛ければ、一様分布の仮定では選択率は約 1/1000、推定出力行数は「全行数 ÷ 1000」となります。範囲条件はヒストグラムの該当区間を数えて推定します。これらを掛け合わせて結合後のカーディナリティを見積もるのが、最適化の数値的な土台です。

探索空間と枝刈り

最大の難所は結合順序です。N 個の表の結合順序の候補数は、木の形まで含めると N とともに階乗的に増えます（結合木の総数は超指数的）。全列挙は数十表で非現実的になるため、探索空間を縮める仕組みが必須です。

代表的なのが System R 由来の**動的計画法（DP）**です。要点は「部分問題の最適解を再利用する」こと。

# ボトムアップDPの骨子（概念）
1. 各表の最良アクセス方式（Seq / Index）を確定
2. サイズ2の全部分集合について最良の結合プランを求めて表に記録
3. サイズkのプランを、サイズk-1の最良プラン＋1表 から合成
4. 最後に全表を含む集合の最良プランを採用

DP は同じ部分集合（例：{A,B}）の最適プランを一度だけ計算して共有するため、素朴な全列挙より大幅に小さい計算量で済みます。それでも表数が増えると DP 表が爆発するため、さらに次の枝刈り・近似を併用します。

• 興味のある順序（interesting orders）: ある結合や ORDER BY で後段が活かせる並び順を持つ部分プランは、コストが多少高くてもソート省略の見込みで残す。これにより Merge Join の機会を逃さない。
• 劣プランの即時破棄: 同じ部分集合・同じ出力順序で、より高コストのプランは捨てる（支配関係による枝刈り）。
• 探索の打ち切り: 表数がしきい値（PostgreSQL の geqo_threshold など）を超えると、DP をやめ遺伝的アルゴリズムなどのヒューリスティック探索に切り替え、最適でなくとも十分良い解を現実的な時間で得る。

物理演算子の選択例

論理的な1つの結合に対し、物理化では複数アルゴリズムが候補になります。どれが最小コストかは入力サイズと統計で決まります。

例えば結合の片側が数十行なら Nested Loop（→ JOIN の仕組み）が、両側が大きく等値結合なら Hash Join が選ばれやすくなります。入力が既にキー順なら Merge Join がソートを省けて有利です。ここでも判断材料は統計由来の推定行数であり、推定が外れると不適切な演算子が選ばれます。

まとめ：EXPLAIN を原理から読む

オプティマイザは、SQL を関係代数へ落とし、等価変換で形を整え、統計から各候補のコストを見積もり、枝刈り付きの探索で最小コストの物理プランを選びます。したがって EXPLAIN ANALYZE で推定行数（estimated rows）と実測行数（actual rows）が大きく食い違う箇所を見つけたら、それは統計の誤差が悪い計画を招いているサインです。ANALYZE での統計更新や拡張統計の追加が、ヒントの乱用よりも本質的な対処になります。並行する書き込みとの兼ね合い（→ ロックと MVCC）や、巨大表の分割（→ パーティショニング）も、最終的にはオプティマイザが扱う統計とコストを通じて計画に効いてきます。