SQLは宣言的言語であり、「どう実行するか」ではなく「何を取得するか」を記述します。しかし実際のDB内部では、クエリはそのまま実行されるわけではありません。
データベースはSQLを別の形に書き換え（Rewrite）、より効率的な実行計画へと変換します。この変換ルールこそが、クエリオプティマイザの核心です。
本記事では、SQLがどのように変換され、どのような理論に基づいて最適化されるのかを解説します。
■ クエリ処理の全体フロー
SQLは内部で以下のように処理されます：
SQL ↓ Parse（構文解析） ↓ Rewrite（書き換え） ↓ Optimize（最適化） ↓ Execute（実行） この中で「Rewrite」は、論理的に同値な別のクエリへ変換するフェーズです。
■ Rewrite Rulesとは何か？
Rewriteとは、SQLを意味を変えずに別の構造へ変換することです。
例：
SELECT * FROM A WHERE x IN (SELECT x FROM B); ↓ 書き換え
SELECT A.* FROM A JOIN B ON A.x = B.x; この変換により、JOIN最適化が可能になります。
■ 関係代数による理論基盤
Rewriteは、関係代数（Relational Algebra）の法則に基づいています。
基本演算
- 選択（Selection）: ( \sigma )
- 射影（Projection）: ( \pi )
- 結合（Join）: ( \bowtie )
例：選択の移動（Selection Pushdown）
[ \sigma_{condition}(A \bowtie B) = (\sigma_{condition}(A)) \bowtie B ]
→ フィルタをJOIN前に適用することでデータ量削減
■ 主要なRewriteルール一覧
① Predicate Pushdown（述語プッシュダウン）
WHERE条件を可能な限り早い段階に移動。
-- Before SELECT * FROM A JOIN B ON A.id = B.id WHERE A.age > 30; -- After SELECT * FROM (SELECT * FROM A WHERE age > 30) A JOIN B ON A.id = B.id; 効果： データ量削減 → JOINコスト低下
② Projection Pushdown
必要な列だけ早期に取得。
SELECT A.id FROM A JOIN B ON A.id = B.id; → 不要な列を削除してI/O削減
③ Join Reordering（結合順序最適化）
[ (A \bowtie B) \bowtie C = A \bowtie (B \bowtie C) ]
結合順序を変えて最小コストを選択。
例：
- A: 1,000,000行
- B: 100行
- C: 10行
→ (B JOIN C) → A とする方が効率的
④ Subquery Flattening（サブクエリの平坦化）
SELECT * FROM A WHERE x IN (SELECT x FROM B); ↓
SELECT DISTINCT A.* FROM A JOIN B ON A.x = B.x; 効果： ネスト構造を解消し最適化可能に
⑤ Constant Folding（定数畳み込み）
WHERE price > 100 * 1.1 ↓
WHERE price > 110 コンパイル時に計算
⑥ Common Subexpression Elimination
同じ計算を1回にまとめる
⑦ View / CTE Inlining
ビューやCTEを展開して最適化対象にする
WITH tmp AS (SELECT * FROM A WHERE x > 10) SELECT * FROM tmp WHERE y > 5; ↓
SELECT * FROM A WHERE x > 10 AND y > 5; ■ ルールベース vs コストベース
| 方式 | 特徴 |
|---|---|
| ルールベース（RBO） | 固定ルールで変換 |
| コストベース（CBO） | 複数候補を評価して最適選択 |
現代DBは基本的にCBO（Cost-Based Optimizer）を採用。
Rewriteはその前段として、探索空間を広げる役割を持ちます。
■ 探索空間爆発問題
JOINが増えると、実行計画の組み合わせは爆発します：
[ n! （階乗） ]
例：10テーブル → 約360万通り
→ すべて試すのは不可能
そのため：
- ヒューリスティック（経験則）
- 動的計画法（Dynamic Programming）
で探索空間を削減します。
■ 実務での重要ポイント
① Rewriteされる前提でSQLを書く
SQLの見た目より「オプティマイザがどう解釈するか」が重要。
② CTEは最適化を阻害する場合がある
PostgreSQLではCTEが最適化フェンスになることがある。
③ サブクエリはJOINに変換されることが多い
パフォーマンス問題の原因になることも。
④ Rewriteされないケースを知ることが重要
- 副作用関数
- 非決定関数（random()など）
- LIMIT / OFFSET
→ これらは変換が制限される
■ まとめ
- Rewriteは「同値変換」による最適化の前段階
- 関係代数の法則に基づく
- Pushdown・Join順序・Flattenなどが重要
- 探索空間爆発を抑えるためヒューリスティックが使われる
SQLチューニングの本質は、「SQLを書くこと」ではなく、DBがどう書き換えるかを理解することです。
