結合順序探索：動的計画法と遺伝的/貪欲法

なぜ結合順序が最適化の核心なのか

複数の表を結合するクエリで、結果は結合の順序を変えても同じです（結合の交換律・結合律）。しかし中間結果の行数は順序で桁違いに変わります。先に絞り込める結合を選べば後段が運ぶ行が減り、選び損ねれば巨大な中間結果が膨らみます。クエリオプティマイザにとって、各結合のアルゴリズム選択と並ぶ最大の探索対象がこの結合順序です。本稿では、その候補がなぜ爆発し、どう現実的な時間に収めるかを追います。

探索空間の指数爆発

結合順序は「結合木の形」で表されます。木の形には大きく2系統あります。

左深木に限っても、N 表なら順列の総数 N! 通りです。N=10 で約 360 万、N=12 で約 4.8 億に達します。中間結果同士を結合するブッシー木まで許すと候補数はさらに跳ね上がり、結合木の総数はカタラン数を含む超指数的な増加になります。各候補について物理アルゴリズム（Nested Loop / Hash / Merge）の選択も掛かるので、素朴な全列挙は十数表で破綻します。

System R 流のボトムアップ動的計画法

全列挙を避ける古典的な解が、System R（IBM の初期 RDB）が確立したボトムアップ動的計画法（DP）です。鍵は「同じ表の部分集合に対する最良プランは1つだけ」という観察にあります。例えば {A,B,C} を結合した中間結果の最良プランは、後段でそれをどう使うかと独立に決まります（出力順序を考慮しない単純化では）。ならば部分集合ごとに最良プランを一度だけ求めて記録し、より大きい集合の構築に再利用すればよい——これが最適部分構造の利用です。

# ボトムアップ DP の骨子（左深木の場合）
1. 各単一表 {Ti} の最良アクセス方式（Seq / Index）を求め、表に記録
2. サイズ s = 2 から N まで順に:
     サイズ s の各部分集合 S について:
       S を「サイズ s-1 の部分集合 S' ＋ 残り1表 T」へ分割する全方法を試し、
       (S' の最良プラン) ⋈ T を各結合アルゴリズムで作り、最小コストを S の最良として記録
3. 全表を含む集合 {T1..TN} の最良プランを採用

DP が効くのは、部分集合 {A,B} の最良結合プランを計算するのは一度きりで、{A,B,C} でも {A,B,D} でも同じ結果を参照するからです。素朴な全列挙が同じ部分結合を何度も作り直すのに対し、DP は重複計算を排除します。

カーディナリティ推定がコストを決める

DP の各ステップで「最小コスト」を比較するには、各部分プランの推定コストと出力行数（カーディナリティ）が要ります。コストは下から伝播し、{A,B} の推定行数が次の {A,B,C} のコスト計算に入ります。したがって下流の行数推定が外れると、上流まで誤差が増幅し、DP が「最良」と判断したプランが実際には最悪になり得ます。

推定中間行数(A ⋈ B) ≈ rows(A) × rows(B) × 結合選択率
結合選択率 ≈ 1 / max(distinct(A.key), distinct(B.key))   -- 等値結合・独立の仮定

選択率は統計情報（distinct 値数・ヒストグラム）から見積もります。複数結合をまたぐと推定誤差が掛け合わさって増幅するため、表数が多いほど推定はあてにならなくなります。皮肉なことに、探索空間が最も爆発する「多表結合」こそ、コスト見積もりが最も不正確になる領域です。

貪欲法による枝刈り

DP すら重い大規模結合では、**貪欲法（greedy）**が使われます。原理は単純で、毎ステップ「今ある中で最小コストの結合」を1つ確定し、それを次の候補集合に組み込んで繰り返します。

# 貪欲法の骨子
集合 = {全表}
while 集合の表が 2 つ以上:
    集合内の全ペア（または中間結果と表のペア）の結合コストを見積もる
    最小コストのペアを結合し、その中間結果で2表を置き換える

各ステップで局所的に最良を選ぶだけなので計算量は N の多項式（おおむね N の3乗程度）に収まります。代償は局所最適に陥ることです。今すぐ安い結合が、後段で巨大な中間結果を招くこともあり、貪欲法は大域最適を保証しません。実装によっては複数の開始点から貪欲探索を走らせて最良を採るなど、品質を補う工夫を加えます。

遺伝的アルゴリズムによる近似

PostgreSQL は FROM 句の要素数が geqo_threshold（既定12）以上になると、DP をやめ**遺伝的アルゴリズム（GEQO）**に切り替えます（既定なら12表で切り替わる）。結合順序を「遺伝子」と見なし、自然選択を模した探索で近似最適解を探します。

GA は集団（個体の集まり）を世代交代させ、適応度の高い順序を交叉・突然変異で混ぜながら、限られた評価回数で「十分良い」順序を探します。全列挙も DP もしないため、最適は保証されない代わりに、表数が増えても探索時間を一定に抑えられるのが利点です。

手法の使い分け

実用のオプティマイザは段階的に切り替えます。表数が少なければ DP で厳密に近い最適解を求め、閾値を超えたらヒューリスティック（貪欲法や GA）に落として「最適は捨て、現実的な時間で十分良い解」を得る、という設計です。どこで切り替えるかは、プランニングに使ってよい時間と、誤った計画が招く実行時間の損失とのトレードオフで決まります。

まとめ

• 結合順序の候補は左深木で N! 通り、ブッシー木では超指数的に爆発する。中間結果の行数が順序で桁違いに変わるため、順序選択は最適化の核心。
• System R 流の DP は「部分集合ごとに最良プランを1回だけ計算して再利用」する最適部分構造の利用で、計算量を約 3 の N 乗 に圧縮する。
• それでも DP 表は 2 の N 乗 でメモリが膨らむため、大規模では貪欲法（局所最適・多項式時間）や遺伝的アルゴリズム（近似・時間を制御可能）へ切り替える。
• いずれの手法もコスト比較はカーディナリティ推定に依存し、多表ほど推定誤差が増幅する。統計の鮮度が、どの探索手法を使っても計画品質の前提になる。