ルールベース最適化（Rule-Based Optimization）
データベースのクエリを固定ルールで書き換えて高速化する、古典的なクエリ最適化手法
📌ルールベース最適化とは
ルールベース最適化（Rule-Based Optimization, RBO）は、データベースのクエリを高速に実行できる形に書き換える手法の一つです。 初期のデータベース製品（Oracle v7以前、初期のMySQL）で主に採用されていました。現在はコストベース最適化（CBO）が主流ですが、RBOの概念は今でもCBOの中に部品として残っています。
RBOの最大の特徴は、テーブルの統計情報（行数、カーディナリティなど）を一切使わないことです。 代わりに「Selection Pushdownは常に良い」「Projection Pushdownは常に良い」といった固定のルール（書き換え規則）を優先度順に機械的に適用します。
中でも最も重要なルールはSelection Pushdown（選択プッシュダウン）です。 これはWHERE条件をクエリツリーの下の方（データソースに近い側）に移動させることで、JOINなどの重い処理に渡す行数を早い段階で削減する手法です。 例えば100万行のテーブル同士をJOINした後にWHEREで絞るのではなく、先にWHEREで1000行に絞ってからJOINすれば、処理量は劇的に減ります。
🔍このツールの値は何を表している？
上のビジュアライザーに表示されているツリーは、SQLクエリの実行計画（クエリツリー）を表しています。 各ノードはクエリの中の一つの処理ステップに対応します。
Selection Pushdown のイメージ
⚙️仕組み
料理のレシピを効率化するイメージです。レシピに「野菜を全部洗って、全部切って、必要なものだけ選んで料理する」と書いてあったら、「必要なものだけ先に選んでから洗って切る」方が効率的ですよね？ ルールベース最適化はこのような「明らかに効率的な書き換え」をルールとして持っています。
主なルールと料理での例え
WHERE条件をツリーの下に移動し、不要な行をJOINの前に除外します。100万行をJOINしてから絞るのではなく、先に1000行に絞ってからJOINします。
不要なカラムをできるだけ早い段階で捨てます。10カラムあっても使うのが2カラムなら、最初から2カラムだけ持ち運びます。
WHERE price > 50 + 50 のような定数式を、実行前に WHERE price > 100 に変換します。実行時に毎回計算する無駄を省きます。
ルールベースは「こうしたら必ず速くなる」という確実なルールだけを適用するため、テーブルの大きさを知らなくても使えます。ただし、テーブルの大きさによって最適解が変わるケース（seq_scan vs index_scan）には対応できません。そのような判断には、統計情報を使うコストベース最適化（CBO）が必要になります。
最適化の流れ
Selection Pushdownの具体例
└ FILTER (price > 100)
└ JOIN (orders × products)
├ SCAN (orders) ← 100万行
└ SCAN (products) ← 10万行
└ JOIN (orders × products)
├ SCAN (orders) ← 100万行
└ FILTER (price > 100)
└ SCAN (products) ← 1000行に削減
✅特徴
- 📏決定論的 — 同じクエリには常に同じ変換を適用する。統計情報に依存しないため、結果が予測可能で、デバッグが容易。
- ⚡高速 — 各ルールのパターンマッチと書き換えは O(n)（ツリーのノード数に比例）。コストベースのように複数の実行計画を生成して比較する必要がない。
- 🧱実装がシンプル — ルールを追加・削除するだけで拡張できる。各ルールは独立しており、他のルールの知識を必要としない。
- ⚠️統計を使わない弱点 — 「テーブルが小さいからフルスキャンの方が速い」といった判断ができない。インデックスの有無やデータ分布を考慮できない。
- 🏛️歴史的意義 — Oracle v7以前、初期のMySQL、SQLiteの一部で使われた。現在のCBOにもRBOのルールが「ヒューリスティック段階」として組み込まれている。
💡ユースケース
📖用語解説
📋手順
- 1SQLパーサーがクエリを解析し、クエリツリー（論理演算子のツリー）を構築する。ツリーのルートは最終出力（PROJECT）、葉はテーブルスキャン（SCAN）。
- 2オプティマイザがルールセットを優先度順にソートする。Selection Pushdown（P1）が最も高い優先度を持つ。
- 3P1のルールからツリーを走査し、パターンにマッチするサブツリーを探す。例えば「JOINの上にFILTERがある」パターン。
- 4マッチしたら、ルールに従ってサブツリーを書き換える。FILTERノードをJOINの下に移動する。
- 5P2、P3...と順番にすべてのルールを適用する。各ルールは1回だけ適用される。
- 6すべてのルールの適用が完了したら、書き換え後のクエリツリーが最終的な実行計画として使われる。
⚖️Rule-Based vs Cost-Based 比較
| 観点 | Rule-Based (RBO) | Cost-Based (CBO) |
|---|---|---|
| 判断基準 | 固定ルール（優先度順） | コストモデル（I/O, CPU, メモリ推定値） |
| 統計情報 | 使わない | テーブル行数、カーディナリティ、ヒストグラムなどを使用 |
| 結果の予測性 | 常に同じ結果（決定論的） | 統計が変わると実行計画が変わりうる |
| 最適性 | データ分布を考慮できず、最適とは限らない | より正確にコストを推定し、最適に近い計画を選択 |
| 実装コスト | シンプル・軽量 | 統計収集・コストモデル・探索空間の管理が必要 |
| 代表的なDB | Oracle v7以前、MySQL 3.x、SQLite | Oracle 7+、PostgreSQL、MySQL 5.x+、SQL Server |
| 現在の位置づけ | CBOのヒューリスティック段階として残存 | 主流。ほぼすべての商用・OSSのRDBMSが採用 |
現代のデータベースでは、CBOが主流です。しかしCBOの内部でも、明らかに有利な変換（Selection PushdownやConstant Foldingなど）は ヒューリスティック段階としてRBOのルールが先に適用されます。RBOを学ぶことは、CBOの理解にも直結します。
