第6章: クエリプランナとオプティマイザ — 宣言性を支える頭脳

SQLクエリ実行の5段階

SELECT * FROM users WHERE age > 30 と書いてエンターを押した瞬間、 データベースエンジンの中では5つのステージが走ります。 この流れを押さえると、なぜオプティマイザが重要なのか、どこで何が書き換わるのかが一気にクリアになります。

flowchart LR
    Q[SQL文字列] --> P["① パーサ<br/>(構文解析)"]
    P --> A["② アナライザ<br/>(意味解析・型検査)"]
    A --> R["③ リライタ<br/>(ビュー展開・書き換え)"]
    R --> O["④ プランナ/オプティマイザ<br/>(実行計画選択)"]
    O --> E["⑤ エグゼキュータ<br/>(実行)"]
    E --> RES[結果セット]
    style P fill:#3b82f6,color:#fff
    style O fill:#f59e0b,color:#fff
    style RES fill:#10b981,color:#fff

CBO — Cost-Based Optimizerの基本原理

現代のSQLオプティマイザの主流はコスト基盤最適化（Cost-Based Optimization, CBO）です。 対義語のRBO（Rule-Based Optimization, ルール基盤）が「常にインデックスがあれば使う」のような固定ルールで動くのに対し、 CBOは統計情報から各候補プランのコストを見積もり、最安のものを選びます。

CBOの動作を簡略化すると以下のループです:

flowchart TD
    S[クエリツリー] --> G["候補プラン生成<br/>(JOIN順, 走査方法, 結合アルゴリズム)"]
    G --> C["各候補のコスト計算<br/>= f(I/O, CPU, メモリ, 統計)"]
    C --> B[最安プランを選択]
    B --> E[エグゼキュータへ]
    style B fill:#10b981,color:#fff

1979年 System R 論文 — CBOの元祖

CBOの歴史的起点は1979年のPatricia G. Selinger et al. "Access Path Selection in a Relational Database Management System"という論文です。 SIGMOD '79 で発表されたこの論文は、IBMのSystem Rプロジェクト内で開発されたオプティマイザの設計を記述しており、 今日のOracle / DB2 / PostgreSQL / SQL Server などほぼすべての主要RDBMSがこの系譜を受け継いでいます。

Selingerは1996年にACMの特別名誉会員になり、2022年にはIEEE John von Neumann Medalを受賞しています。 Selingerアルゴリズムの論文は「関係DB研究で最も引用された論文の1つ」で、現代でも学部のDB授業では必読とされます。

Volcano / Cascades — 現代の拡張可能オプティマイザ

Selingerアルゴリズムはbottom-upの動的計画法でしたが、1990年代にGoetz Graefeが Volcano Optimizer Generator（1993）とCascades Framework（1995）という 「拡張可能オプティマイザフレームワーク」を発表しました。

JOINアルゴリズム3選 — Nested Loop / Hash / Sort Merge

オプティマイザが選ぶ最も重要な選択のひとつが「JOINアルゴリズム」です。 SQLで A JOIN B ON ... と書いても、物理的には3つのアルゴリズムから選ばれます。

▼ Nested Loop Join — 最もシンプル、小さいテーブル向き
  for each row r in A:
    for each row s in B:
      if condition(r, s): emit (r, s)

▼ Hash Join — 等結合で強力
  hash = {}
  for each row b in B:          # ビルドフェーズ(小さい方)
    hash[b.key].append(b)
  for each row a in A:          # プローブフェーズ(大きい方)
    for b in hash.get(a.key, []):
      emit (a, b)

▼ Sort Merge Join — 両方ソートされてるなら最強
  sort A by key; sort B by key
  i = j = 0
  while i < len(A) and j < len(B):
    if A[i].key == B[j].key: emit (A[i], B[j])
    elif A[i].key < B[j].key: i += 1
    else: j += 1

オプティマイザの書き換えテクニック

実行計画生成に入る前に、リライタは関係代数の等価変換則(第3章)を使ってクエリを「最適化しやすい形」に整えます。

ヒント — オプティマイザを手動で制御する

CBOは基本的に賢いですが、まれに間違った選択をします。そんなとき、最終手段として「ヒント」でオプティマイザに指示できます。 ただしヒントはDBに強く依存し、SQL標準にはありません。

-- Oracle: コメント形式
SELECT /*+ USE_HASH(orders customers) */ *
FROM orders JOIN customers ON orders.customer_id = customers.id;

-- MySQL 8+: ヒント風コメント
SELECT /*+ INDEX(orders idx_customer_id) */ *
FROM orders WHERE customer_id = 100;

-- PostgreSQL: 標準のヒントは無い(哲学的に拒否)
-- 代わりに pg_hint_plan 拡張モジュールを使うか、
-- SET enable_nestloop = off; のようなセッションフラグ、
-- またはクエリを物理的に書き換えて誘導する

第6章のまとめ

• SQL実行はパース→解析→リライト→プランニング→実行の5段階で進む。オプティマイザはプランニング段階の心臓部
• CBO（Cost-Based Optimization）は統計情報をもとに候補プランのコストを見積もり最安を選ぶ。統計が古いと悪いプランが選ばれる
• 1979年 System R論文(Selinger)がCBOの元祖。動的計画法によるJOIN順選択、統計ベースコスト見積、interesting orderの3本柱
• Cascades Framework（Graefe, 1995）が現代の拡張可能オプティマイザの標準。SQL Server/CockroachDB/DuckDB/Calciteなどが採用
• JOINはNested Loop / Hash Join / Sort Merge Joinの3種類。データサイズ・インデックス・メモリでオプティマイザが選ぶ
• 主な書き換えはpredicate/projection pushdown, join reordering, subquery unnesting, partition pruning

次章では、オプティマイザが最もよく利用する武器であるインデックスと、 実行計画を読むためのツールEXPLAINの世界に進みます。 B-tree、Hash、GiST、GIN、BRINの違いから「なぜLIKE '%foo'はインデックスが効かないか」まで徹底解剖します。