準結合・反結合と EXISTS/IN の実行戦略

準結合と反結合という演算子

EXISTS や IN を書くと、オプティマイザは内部で**準結合（semi join）や反結合（anti join）**という専用の論理演算子を作ります。SQL の構文には現れませんが、実行計画を理解する鍵はこの2つです。

• 準結合（左 ⋉ 右）: 右に1件でも一致する左行を、重複なく最大1回返す。「存在するか」だけが問題で、右の何件と一致したかは無視する。
• 反結合（左 ▷ 右）: 右に1件も一致しない左行を返す。準結合の補集合にあたる。

通常の内部結合と決定的に違うのは、左行の出力が増えないことです。内部結合なら右に3件一致した左行は3回出力されますが、準結合は1回で打ち切ります。これは「最初の一致が見つかった時点で右の探索を止めてよい」という早期終了（short-circuit）の根拠になります。

EXISTS が準結合へ変換される過程

次の相関 EXISTS を例にします。

SELECT c.name
FROM customers c
WHERE EXISTS (
  SELECT 1 FROM orders o
  WHERE o.customer_id = c.id AND o.total > 1000
);

オプティマイザはまず相関（o.customer_id = c.id）を結合条件として外へ引き上げ、サブクエリブロックを上位の結合グラフへ平坦化します。この過程は サブクエリのデコリレーション で扱った代数変換そのものです。結果として論理プランは次の準結合になります。

SemiJoin(customers, orders)
  on orders.customer_id = customers.id and orders.total > 1000

IN も対象列が一意でなければ準結合に落ちますが、右側で重複が生じうるため、実装によっては「右を重複排除してから内部結合」や「マーク付き走査」へ展開されます。いずれも左行が複製されない点は保たれます。

ハッシュ準結合・反結合の実行戦略

論理的な準結合・反結合は、結合アルゴリズム と同じく Nested Loop / Hash / Sort-Merge のいずれでも物理化できます。実務で支配的なのがハッシュ準結合です。

Hash Semi Join
  Hash Cond: (c.id = o.customer_id)
  -> Seq Scan on customers c        -- プローブ側（左）
  -> Hash                            -- ビルド側（右）
       -> Seq Scan on orders o
            Filter: (total > 1000)

動作はハッシュ結合（グレース法・ハイブリッド）と同じく、片側でハッシュテーブルを作り、もう片側で探索します。準結合・反結合に固有なのは探索の終わらせ方です。

準結合は最初の一致で打ち切るため、右に多数一致しても探索コストが膨らみません。反結合は逆に「一致なし」を確定させたいので、原理的には右側のハッシュバケットを最後まで見る必要があります。計算量はどちらもビルド O(M) ＋プローブ O(N) の O(N+M) 級で、左の各行ごとに右を全走査する反復評価の O(N×M) とは桁が違います。

NOT IN が NULL で破綻する仕組み

最大の落とし穴が NOT IN です。NOT EXISTS は素直に反結合へ変換できますが、NOT IN はサブクエリの結果に NULL が混じると反結合と等価でなくなります。

これは 3値論理とNULL の帰結です。x NOT IN (a, b, NULL) は x <> a AND x <> b AND x <> NULL に展開され、最後の x <> NULL は決して TRUE になりません（UNKNOWN になる）。AND に1つでも UNKNOWN があれば全体は TRUE になれないため、サブクエリ側に NULL が1件でもあると述語全体が TRUE を返さなくなり、外側の行がまるごと消えることがあります。

-- orders.customer_id に NULL が1件でもあると…
SELECT c.id FROM customers c
WHERE c.id NOT IN (SELECT customer_id FROM orders);
-- → 結果が0行（誰も該当しない）に化ける

NOT EXISTS が安全なのは、比較が = ベースの結合一致で、NULL は単に「一致しない」と扱われ、反結合の意味（一致が0件の左行）と矛盾しないためです。NOT EXISTS と NOT IN は同じ意図に見えて、NULL の境界条件で結果が割れます。

実行計画から戦略を読む

EXPLAIN を見るときの着眼点を整理します。

Hash Semi Join や Hash Anti Join が出ていれば、内側1回・外側1回のセット実行に変換できた合図です。逆に SubPlan が外側の行数ぶん回っていれば、相関が解けていません。NULL 安全でない NOT IN を NOT EXISTS に書き換える、サブクエリ側の列へ NOT NULL 制約を付ける、といった対処で準結合・反結合化を促せます。詳しい変換判断は クエリオプティマイザの内部 を参照してください。

まとめ

• EXISTS は準結合、NOT EXISTS は反結合へ変換され、左行は最大1回しか出力されない。IN/NOT IN も多くは同じ演算子に落ちる。
• 準結合・反結合はハッシュやマージで物理化でき、左1回＋右1回の走査で O(N+M) 級。準結合は最初の一致で探索を打ち切れるのが固有の利点。
• NOT IN はサブクエリ側に NULL があると反結合と等価でなくなり、結果が空寄りに化ける。NOT NULL を証明できないとオプティマイザは反結合化を諦める。
• EXPLAIN で Hash Semi/Anti Join が出ればセット実行に成功、SubPlan が外側の行数ぶん回っていれば相関が解けていない合図。存在判定は NOT EXISTS が安全。