サブクエリのデコリレーションとフラット化

相関サブクエリはなぜ遅いのか

サブクエリには2種類あります。外側の行に依存しない非相関サブクエリは一度だけ評価して結果を使い回せます。問題は相関サブクエリで、内側が外側の列を参照するため、概念的には外側の1行ごとに内側を評価し直します。

-- 相関サブクエリ: 内側が外側の o.customer_id を参照する
SELECT c.name
FROM customers c
WHERE EXISTS (
  SELECT 1 FROM orders o
  WHERE o.customer_id = c.id      -- ← ここが相関
    AND o.total > 1000
);

素朴に実行すると、外側 customers が N 行、EXISTS の評価1回が内側 M 行の走査だとして、全体は O(N×M) になります。N=10万・M=100万なら反復評価は天文学的な回数に達します。**デコリレーション（decorrelation）**は、この相関を取り除いて結合へ書き換え、セットベースの1回処理に変える最適化です。

デコリレーションの代数規則

中核は、相関サブクエリが論理的にsemi join / anti joinと等価だという事実です。semi join（⋉）は「右に一致する左行を、重複なく1回だけ返す」結合です。

先ほどの EXISTS は、次の semi join へ平坦化されます。customers 側の重複は生まれず、各 customers 行は最大1回しか出力されません。

-- デコリレーション後（semi join をオプティマイザが内部生成）
SELECT c.name
FROM customers c
SEMI JOIN orders o ON o.customer_id = c.id AND o.total > 1000;

SQL に SEMI JOIN 構文はありませんが、オプティマイザは論理プラン上で semi join 演算子を生成します。重要なのは、この演算子が Hash Semi Join や Merge Semi Join として物理化できる点です。つまり結合キー（customer_id）でハッシュテーブルを1回作り、左を1回流すだけで済み、計算量は O(N+M) 級に落ちます。

スカラ相関サブクエリの書き換え

SELECT 句や WHERE 句で単一値を返すスカラ相関サブクエリは、集約を先に済ませてから外部結合する形へ変換します。

-- 変換前: 行ごとに COUNT を計算（外側の各行で内側を再走査）
SELECT c.name,
       (SELECT count(*) FROM orders o WHERE o.customer_id = c.id) AS cnt
FROM customers c;

-- 変換後: 先に集約してから1回だけ結合
SELECT c.name, COALESCE(g.cnt, 0) AS cnt
FROM customers c
LEFT JOIN (
  SELECT customer_id, count(*) AS cnt
  FROM orders GROUP BY customer_id
) g ON g.customer_id = c.id;

変換後は orders を1回だけスキャンしてグループ集約し、その結果を customers に結合します。COALESCE が要るのは、一致しない customers 行で外部結合が NULL を返すのに対し、スカラサブクエリ版は内側0行で count(*)=0 を返すという意味の差を埋めるためです。この種の NULL／空集合の境界条件を保存することが、等価変換の正しさの肝になります。

NULL がデコリレーションを壊す場面

NOT IN は anti join に見えますが、NULL を含む集合では意味が変わります。SQL の3値論理では、サブクエリの結果に NULL が1つでもあると x NOT IN (... NULL ...) は決して TRUE を返さず、外側の行がまるごと消えることがあります。

なぜセットベースが反復より桁違いに速いのか

書き換えで速くなる理由は構文の好みではなく、実行モデルの違いにあります。

上の比較を分解すると、効くポイントは主に3つです。

• 計算量: 反復評価は外側 N 行 × 内側評価で O(N×M)。semi/anti join + ハッシュなら、ハッシュ構築 O(M) と探索 O(N) で O(N+M)。N が大きいほど差が開きます。
• アルゴリズムの選択肢: 結合に変われば、オプティマイザは 結合アルゴリズム の3方式（Nested Loop / Hash / Sort-Merge）から最小コストを選べます。相関のままでは事実上 Nested Loop 相当に固定されます。詳しくは Hash Join の内部 を参照してください。
• キャッシュとパイプライン効率: 内側を1回だけ連続スキャンすればバッファとCPUキャッシュのヒット率が上がり、ベクトル化された 実行モデル の恩恵を受けられます。反復評価は同じページを何度も引き直し、分岐予測も崩れがちです。

セットベース実行が前提になって初めて、行数の推定（カーディナリティ推定）に基づくコスト比較が意味を持ちます。相関のままでは内側の総評価回数が見えにくく、コスト見積もりも荒くなります。

まとめ

• 相関サブクエリは外側の行ごとに内側を再評価するため O(N×M) に膨らむ。デコリレーション／フラット化はこれを結合へ書き換える。
• EXISTS→semi join、NOT EXISTS→anti join、スカラ相関サブクエリ→「集約 + 外部結合」が基本の代数規則。NULL と空集合の境界条件を保存することが正しさの条件。
• NOT IN はサブクエリ側に NULL があると anti join と等価でなくなるため、書き換えが抑止されることがある。存在判定は NOT EXISTS が安全。
• 速さの本質は反復評価をセットベースの1回処理に変える点。結合化でアルゴリズムの選択肢が開き、内側の重複スキャンとキャッシュミスが消えて桁違いに速くなる。