結合方式の主なコスト

結合の性能は、表全体の大きさだけでなく、絞込み後の行数、結合キーの分布、索引、出力行数、メモリ量で変わります。SQLの見た目から方式を決めつけず、実行計画と実測値を比べて、どこで処理量が増えたかを追います。特定の結合方式が常に最速になることはありません。

Nested Loops：外側の行ごとに内側を探す

外側の行を1件取り出すたびに、対応する内側の行を探します。外側がN行、内側がM行で、毎回内側を全走査する単純な実装なら比較は概ねN×M回です。内側の結合キーに適切なB+木索引があれば、探索量を減らせます。ただし索引探索だけでなく、一致する全行の取得、キャッシュ、ランダムI/Oもコストになります。

外側を少数に絞れる検索では有利になりやすいですが、内側が極めて小さい場合やMaterializeで再利用できる場合など、索引がなくても妥当な計画があります。「索引なしなら必ず破綻」「小さい方を必ず外側」と単純化しないようにします。

Hash JoinとMerge Join

Hash Joinは、ビルド側の結合キーからハッシュ表を作り、プローブ側の各行から一致候補を探します。主に等値結合に使われます。作業領域に収まらない場合、複数バッチに分けて一時領域を使う実装があり、I/Oが増えます。行数だけでなく行幅や分布の偏りもビルド側のメモリに影響します。

Merge Joinは、結合キー順の入力を突き合わせます。入力が適切な索引などで既に順序付けされていればソートを省ける場合があります。重複キーから多数の結果が出る場合はその出力処理も必要です。範囲結合にソートを利用する方式はありますが、PostgreSQLのMerge Joinを任意の不等値結合に使えると考えてはいけません。対応する演算子・型・DBMSに依存します。

結合方式の主なコスト

代表的な着眼点です。実際の方式選択はデータ分布やDBMSの実装によって変わります。

実行計画は木構造として読む

親ノードは子ノードから得た行を処理します。Hashはビルド完了まで行を返せず、Sortは通常入力を蓄積してから返すなど、ノードによって動作が異なります。Nested Loopの内側は外側の行に応じて何度も実行されるため、「最も深いインデントから一度ずつ順番に実行」という規則では説明できません。

text

Nested Loop
  -> Index Scan on customers
       Index Cond: (region_code = 1)
  -> Index Scan on orders
       Index Cond: (customer_id = customers.id)

PostgreSQLではEXPLAINのcostは推定コストで、ミリ秒ではありません。EXPLAIN ANALYZEで実測を取ると、actual rowsやloopsを確認できます。反復されたノードの行数・時間は1回当たりの平均として表示されるため、総処理量を見るときはloopsも考慮します。

統計情報と索引を、結果の意味を保って改善する

推定行数と実測行数が大きくずれると、結合順序や方式が不適切になることがあります。統計情報の更新だけでなく、列同士の相関、値の偏り、パラメータによる選択率も確認します。大量ロード後に統計が古いことはありますが、常に0行と誤認するとは限りません。

顧客が500行に絞られ、注文日で200,000行に絞った注文を顧客ごとに反復走査する計画なら、注文候補の確認は概ね100,000,000回です。注文側に（顧客ID,注文日）の索引を設けると、顧客の等値条件と日付範囲で候補を絞れる可能性があります。Hash Joinとの比較も含め、追加後の計画と更新コストを確認します。

演習1：反復走査の量

条件：外側は500行。各行について内側の候補200,000行を検査する。キャッシュや再利用はないものとする。

問い：候補行の検査回数を求めよう。

解答例：100,000,000回。

根拠：500×200,000。実際のI/O回数と同じとは限らないが、反復処理量が大きいことを示す。

演習2：改善する索引

条件：注文を顧客IDの等値条件と注文日の範囲条件で取得する。

問い：検討する複合索引の列順を答えよう。（35字以内）

解答例：顧客ID、注文日の順に複合索引を検討する。（21字）

根拠：同じ顧客の中で日付範囲を絞れる。実行計画で採用と効果を確認する。

復習で確かめること

例の数値や業務条件を変えて同じ結論になるか確認してください。用語の定義だけでなく、問題文のどの条件から、どの制約・SQL・対策を選んだのかを自分の言葉で説明できれば、次の過去問に進みます。

出典と仕様を確認する

IPA：DBシラバス Ver.4.1

PostgreSQL 18：EXPLAINの読み方

PostgreSQL 18：統計情報

SQL結合アルゴリズム（Nested Loops・Hash・Sort Merge）と実行計画