データベース結合アルゴリズム(Nested Loop・Sort-Merge・Hash Join)

1. 概要

A. 定義

結合アルゴリズム(Join Algorithm) とは、リレーショナルデータベースにおいて二つ以上のリレーション(テーブル)を結合条件に従って物理的に結合し、結果集合を生成する処理方式を指す。利用者がSQLに FROM A, B WHERE A.k = B.k のように「何を結合するか」だけを宣言すると、どの物理的手順で二つの集合の対を見つけるかは、オプティマイザが結合アルゴリズムを選択して決定する。

結合アルゴリズムを理解する鍵は、「同じ結合結果を生成する方法が複数あり、データ規模・分布・整列状態・インデックスの有無によってどの方法が数十~数千倍速くなり得る」という点にある。リレーショナルモデルにおいて結合は最も高価でありながら最も頻繁な演算である。二つのテーブルを結合するということは、本質的に一方の集合の各行に対して他方の集合で対となる行を探す探索(matching)問題であり、この探索をどう組織するかがすなわちアルゴリズムの差である。何の戦略もなくすべての行の対を比較すると二つのテーブルの積(デカルト積)に比例する費用がかかるが、整列やハッシュテーブルを使えばその費用を線形に近く下げられる。

結合がなぜ本質的に高価な演算であるかは集合論的にも明らかである。二つのリレーションの結合は概念的にデカルト積(すべての行の組合せ)を作った後、結合条件を満たす行だけ残すことと同じである。Aが100万件、Bが100万件であればデカルト積は1兆(10^12)組合せとなり、条件をどれほど効率的に絞っても「積を実際に作って絞る」素朴な方式は現実的に不可能である。三つの結合アルゴリズムはいずれも「積を実際に作らずに条件を満たす対だけを直接見つけ出す」方法であり、その手段がそれぞれインデックス探索・整列順序・ハッシュによる直接番地付けである。結合アルゴリズムを学ぶということは、結局「指数的な探索空間を線形に近く縮める三つの工学的トリック」を理解することである。

リレーショナルDBMSが結合アルゴリズムを自動的に選ぶ理由は、SQLが宣言型言語だからである。利用者は結合の「意味」だけを書くのみで結合の「手順」を指定しないため、データ量と分布が変わるたびに最適な手順も変わる。商用・オープンソースのDBMSが共通して実装する結合アルゴリズムは大きく三つ——ネステッドループ結合(Nested Loop Join)、ソートマージ結合(Sort-Merge Join)、ハッシュ結合(Hash Join)——であり、費用基準オプティマイザ(CBO)は統計情報を根拠にこのうち最も安価な方式を問い合わせごとに選択する。

B. 必要性と位置

結合アルゴリズムの選択は問い合わせ性能を左右する決定的な変数である。例えば注文テーブル(1,000万件)と顧客テーブル(100万件)を結合する問い合わせで、条件がごく少数だけを絞り込む場合はインデックスを経由したNested Loopがミリ秒単位で終わるが、二つのテーブルの大部分を結合しなければならないバッチ性の問い合わせで同じNested Loopを使うと数億回のランダムI/Oが発生し数十分かかる。逆にこのバッチ問い合わせにHash Joinを使えば各テーブルを一度ずつだけスキャンして数秒で終わる。すなわちアルゴリズム選択一つがサービス応答性と資源消費を非線形に変える。

結合アルゴリズムはSQL処理パイプライン(構文解析 → 最適化 → 実行)のうちオプティマイザが立てる実行計画(execution plan) の中核構成要素である。オプティマイザは①アクセス経路(インデックス vs 全件スキャン)、②結合順序(どのテーブルを先に読むか)、③結合方式(アルゴリズム) の三つの軸を組み合わせて候補計画を作り費用を比較する。したがって各アルゴリズムの動作原理・費用構造・前提条件を理解することは、DBチューニング、ヒント設計、実行計画解釈、容量見積りの根幹となる中核能力である。

2. 結合アルゴリズムの全体構造

三つのアルゴリズムは「どう対を見つけるか」という共通目標を互いに異なる戦略で解く。下記の全体構造図は、結合要求がオプティマイザを経て三つの物理的アルゴリズムに分岐する様子を示す。

flowchart TB
  SQL["結合問い合わせ(FROM A JOIN B ON ...)"] --> OPT["オプティマイザ(CBO)"]
  STAT["統計情報(カーディナリティ・分布・インデックス)"] --> OPT
  OPT --> NL["Nested Loop Join(ネステッドループ)"]
  OPT --> SM["Sort-Merge Join(ソートマージ)"]
  OPT --> HJ["Hash Join(ハッシュ)"]
  NL --> NLU["少量集合・インデックス存在時に有利"]
  SM --> SMU["既に整列済み・不等号結合時に有利"]
  HJ --> HJU["大量等価結合・非整列時に有利"]
  style OPT fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
  style STAT fill:#fef3e8,stroke:#ed8f2f,stroke-width:2px

ここで必ず区別すべきは結合順序(join order) と結合方式(join method) である。結合順序は「どのテーブルを先に読んで結果を減らすか(driving table)」の問題であり、結合方式は「選択された二つの集合をどのアルゴリズムで結合するか」の問題である。テーブルが三つ以上であればオプティマイザは結合を二つずつ段階的に(left-deepまたはbushyツリー)実行し、各段階ごとに順序と方式を共に決定する。中間結果集合の大きさが次の段階の費用を左右するため、「先に小さく絞る順序」を見つけることが方式選択と同じくらい重要である。結合テーブル数が増えるほど可能な順序の組合せが階乗的に爆発するため、オプティマイザは動的計画法・ヒューリスティックで探索空間を制限する。

三つのアルゴリズムの本質的差異は「対探しの費用をどこで減らすか」にある。Nested Loop は一行ずつ他方のテーブルを探索するが、インデックスで探索を加速する——すなわち「探索の局所性」に頼る。Sort-Merge は両方をあらかじめ整列し、一度の同時走査(マージ)で対を見つける——すなわち「整列が作る順序」に頼る。Hash Join は一方でハッシュテーブルを作り定数時間の照会で対を見つける——すなわち「ハッシングが作る直接番地付け」に頼る。この三つの戦略はそれぞれ前提条件(インデックス・整列・メモリ)が異なるため、データ状況によって優劣が逆転する。オプティマイザが一つを固定せず問い合わせごとに選び直す理由がここにある。

3. Nested Loop Join(ネステッドループ結合)

Nested Loop Joinは最も直観的な方式で、外側テーブル(outer, driving)の各行ごとに内側テーブル(inner)を反復探索して結合条件を満たす対を見つける。名前のとおり二重反復文の構造であり、外側ループが先行集合を一行ずつ取り出し、内側ループがその行の結合キーで後行集合を探る。

この構造で外側テーブルを「先行(driving)テーブル」と呼び、先行集合の大きさが全体の反復回数を決定するため、「小さい集合を外側に置く」結合順序が性能の半分を左右する。オプティマイザは統計を見て結果をより少なく作る側を先行として選ぶが、統計が歪むと大きい集合を先行に誤選択し反復が爆発する事故が起きる。

核心は「内側テーブルに結合キーインデックスがあるか」である。インデックスがあれば内側探索が全件スキャンではなくインデックス探索(ランダムアクセス)に変わり、外側一行あたり数回のブロック読取りだけで対を見つける。この場合全体費用はおおよそ「外側件数 × (インデックス探索 + テーブルランダムアクセス)」に比例する。したがって外側集合が少量で内側に適切なインデックスがあるとき圧倒的に有利である。例えば「今日加入した顧客50名」(外側)に対して各自の注文内訳(内側、顧客IDインデックス保有)を付ける問い合わせは50回のインデックス探索だけで終わる。

逆に外側集合が大きいと致命的である。外側が100万件であれば内側インデックス探索を100万回反復するが、このランダムI/Oはディスクヘッド移動(またはSSDのランダムアクセス)を伴い順次I/Oよりはるかに遅い。また内側にインデックスがなければ外側行ごとに内側を全件スキャンするため、費用が二つのテーブル件数の積(デカルト積)に比例して爆発する。これを緩和するため現代のDBMSはブロックNested Loop(複数の外側行を束ねてバッファ単位で処理)、内側ブロックキャッシング、外側キー整列後のアクセス(prefetch)などの変形を用いる。

Nested Loopは部分範囲処理(partial range) に有利という実務的利点もある。結果を最初から一行ずつ生成するため、ROWNUM <= 10 や LIMIT 10 のように上位少数だけが必要なOLTP問い合わせで全体を処理せず必要なだけ取り出して止められる。そのためOLTPトランザクション・画面ページング・少量結果照会に既定で使われる。

Nested Loopの性能を決めるもう一つの変数はクラスタリングファクタ(clustering factor)、すなわちインデックス順序と実際のテーブル格納順序の整合度である。内側インデックスで見つけた行がテーブルブロックに散らばっていれば(クラスタリングファクタが悪い)、外側行ごとに異なるブロックをランダムアクセスせねばならず、インデックスがあっても体感性能が落ちる。逆に結合キー順序と格納順序が一致すれば同じブロックを再訪する確率が高まり、バッファキャッシュ命中率が上がりランダムI/Oが減る。そのためNested Loopチューニングは「インデックスを作ったか」を越えて「インデックスが指す行が物理的に集まっているか」まで見なければならない。この点で結合アルゴリズム選択はテーブル設計・ロード順序とも接している。

flowchart LR
  O["Outerテーブル(少量・先行)"] --> R1["行1 → 結合キーでInner探索"]
  O --> R2["行2 → 結合キーでInner探索"]
  O --> R3["行N → 結合キーでInner探索"]
  R1 --> IDX["Inner結合キーインデックス"]
  R2 --> IDX
  R3 --> IDX
  IDX --> RES["対(matched row)を返却"]
  style IDX fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px

4. Sort-Merge Join(ソートマージ結合)

Sort-Merge Joinは二つのテーブルをそれぞれ結合キーで整列した後、整列された二つのストリームを同時に走査しながら(merge)対を合わせる方式である。電話帳二冊を並べて同じ名前を探して下っていく様子を思い浮かべればよい。二つの集合が同じ順序で整列されていれば、各集合をただ一度ずつ順次に読みながらポインタを前進させて対を見つけられる。

Sort-Mergeが成立する根拠は「整列された二つの数列で共通要素を見つけるには両方を一度ずつ走査すれば十分である」という性質である。両方が同じキー順序で整列されているため、一方のキーが他方より小さければ小さい側だけ前進させればよく、戻る必要がない。ただし結合キーが重複する(一対多・多対多)場合はマッチング区間で一方のポインタを巻き戻し(rewind)てすべての組合せを出力せねばならないため、重複度が高ければマージ段階でも軽い逆行が発生する。

このアルゴリズムは大きく整列段階(Sort) とマージ段階(Merge) に分かれる。整列段階で二つの集合を結合キー順に整列し、この費用がおおよそ N log N で全体費用を支配する。マージ段階は両方のポインタを比較して小さい側を前進させ、キーが同じなら結果として出力する線形走査(O(N + M))である。したがって整列費用をどれだけ減らすかが要であり、既に整列済みの状態(インデックスフルスキャンで整列順序が保証されるか、前の演算の出力が整列されている場合) であれば整列段階を飛ばして非常に効率的になる。

Sort-Merge Joinの決定的な強みは不等号(非等価)結合を処理できる点である。Hash Joinはハッシュ値の一致のみ判別するため =(等価)条件でのみ動作するが、Sort-Mergeは整列された順序を利用するため >=、BETWEEN、範囲重なりのような条件にも適用できる。例えば「商品価格が特定区間に属する割引政策をマッピングする」範囲結合はSort-Mergeの典型的領域である。また整列結果をそのまま ORDER BY や GROUP BY に再利用でき、後続演算が整列を要求するとき追加の利得を与える。

限界は整列費用である。二つの集合がいずれも大きく整列されていなければ、二度の大規模整列(必要時にディスクを使う外部整列)が先行しHash Joinより遅くなり得る。過去にはHash Joinが標準化される前まで大量結合の既定であったが、今日では等価結合の大量処理の座はおおむねHash Joinが取り、Sort-Mergeは「既に整列済み」または「不等号結合」という条件で選択される。

整列段階でメモリが不足すると外部整列(external sort) に切り替わり、中間結果を一時ディスクに複数のラン(run)に分けて書き、再びマージする。このディスク書込み・読取りが加わると整列費用がさらに大きくなるため、Sort-Mergeを使うときも整列作業領域(例:Oracleの SORT_AREA/PGA)の大きさが性能を左右する。逆に結合キーに既にB+Treeインデックスがありインデックスフルスキャンだけで整列順序が保証されれば、整列段階を丸ごと省略しマージ走査だけで終えられる。このように「整列を無料で得られるか」がSort-Merge採用の実質的な判断基準となる。

区分	Nested Loop	Sort-Merge	Hash Join
基本戦略	外側行ごとに内側探索	両方整列後マージ走査	ビルドハッシュテーブル + プローブ
有利な状況	少量集合・インデックス存在	既に整列済み・不等号結合	大量等価結合・非整列
結合条件	等価・不等号いずれも	等価・不等号いずれも	等価(`=`)専用
インデックス依存	高い(内側インデックス必須級)	低い(整列が代替)	なし(ハッシュが代替)
メモリ感度	低い	中間(整列領域)	高い(ハッシュ領域)
部分範囲処理	優秀(早期返却)	不利(整列完了必要)	不利(ビルド完了必要)
代表費用	外側件数 × 内側探索	N log N + M log M	N + M(メモリ十分時)

5. Hash Join(ハッシュ結合)

Hash Joinは小さい側のテーブル(build input)で結合キーのハッシュテーブルをメモリに作った後、大きい側のテーブル(probe input)を一行ずつ読みながら同じハッシュバケットを照会して対を見つける方式である。核心はハッシュテーブル照会が平均定数時間(O(1))という点で、これにより大きいテーブルをただ一度だけ順次スキャンしながら各行の対を即座に見つけられる。全体費用はメモリが十分であればおおよそ二つのテーブルを一度ずつ読む O(N + M) に収束する。

実際の産業事例として、大型電子商取引の日次売上集計バッチを挙げられる。一日数千万件の注文ログ(fact)を商品・会員・地域の次元テーブル(dimension)と結合して集計する典型的なスタースキーマ問い合わせで、次元テーブルは小さくfactは巨大なため、各次元でハッシュテーブルを作りfactを一度走査するHash Joinが数十秒以内に処理を終える。同じ作業をNested Loopで行うと数千万件に対して次元インデックス探索を反復し数時間かかり得る。データウェアハウス・BI集計が事実上Hash Joinの上に立っていると言っても過言ではない理由である。

動作はビルド(Build) とプローブ(Probe) の二段階に分かれる。ビルド段階でオプティマイザは統計を見てより小さい集合を選び、その結合キーにハッシュ関数を適用してバケット別に積載したハッシュテーブルを作る。プローブ段階では大きい集合の各行に同じハッシュ関数を適用して該当バケットを見つけ、バケット内で実際のキー一致を確認して結果を出力する。ビルド集合が小さいほどハッシュテーブルがメモリに丸ごと入り最も速く、そのため「小さいテーブルをビルドとする」選択が性能を左右する。

Hash Joinの決定的な強みは大量データの等価結合でインデックスなしでも速い点である。Nested Loopが外側件数ぶんランダムI/Oを反復するのと異なり、Hash Joinは両方を順次スキャン(sequential I/O)のみするため大容量バッチ・DW集計・ETLで圧倒的に有利である。例えば売上1億件と商品10万件を商品コードで結合する分析問い合わせは、商品10万件でハッシュテーブルを作り売上1億件を一度走査して終える——インデックスが全くなくてよい。

弱点はメモリと等価結合専用という制約である。ビルド集合が利用可能メモリ(ハッシュ領域)より大きいとハッシュテーブルがメモリに全部入らず、データを複数パーティションに分けてディスクに降ろしてから再び読むGrace Hash Join / ハイブリッドハッシュに切り替わる。このときディスクI/Oが増えて性能が落ちるため、ハッシュ領域(例:Oracle PGA、PostgreSQL work_mem)の大きさ設定が重要である。またハッシュは値の一致のみ判別するため = 条件でのみ使え、>・BETWEEN のような不等号結合には適用できず、その場合Sort-MergeやNested Loopに移る。データ偏向(skew)が激しく特定バケットに値が集まるとハッシュ衝突が増えて性能が低下する点も留意せねばならない。

Grace Hash Joinの動作をもう少し解くと、ビルド・プローブ両方を同じハッシュ関数でN個のパーティションに分割してディスクに保存した後、同じ番号のパーティション対どうしだけを再び読んで結合する。対になり得る行は必ず同じハッシュパーティションに入るため、メモリに一度に全部載せられない大容量も「パーティション単位に刻んでメモリ内結合」を反復して処理できる。ハイブリッドハッシュはこれに加えて最初のパーティションはディスクに降ろさずメモリに維持し、可能な範囲でディスク往復を減らす折衷である。このような仕組みのおかげでHash Joinは「メモリが十分なら非常に速く、不足しても緩やかに遅くなる」安定した拡張性を持つ——これが大容量DWが結合の既定の武器としてHash Joinを採用する理由である。

6. 比較と選択基準:差が生じる理由

三つのアルゴリズムの優劣が状況によって逆転する根本原因は、「対探しの支配的費用が何か」がデータ規模・整列・インデックス・メモリによって変わるからである。少量結果を取り出すOLTP問い合わせでは「どれだけ少なく触れるか」が重要なため、外側少量集合だけ処理して早期返却するNested Loopが勝つ。逆に大量をすべて結合するOLAP・バッチ問い合わせでは「全体を何度読むか」が重要なため、二つのテーブルを一度ずつだけ順次スキャンするHash Joinが勝つ。Sort-Mergeはその間で「既に整列され整列費用がないか、不等号ゆえハッシュを使えない」隙間を埋める。

この観点で見れば「どのアルゴリズムがより良いか」という問い自体が成立しない。三つのアルゴリズムは優劣関係ではなく適用領域が異なる相補関係であり、それぞれの前提条件(インデックス・整列・メモリ)が満たされる区間でのみ最善となる。オプティマイザが一つを永久に採用せず問い合わせごと・統計変化ごとに選び直すこと、そして適応型実行が実行時に切替えまで行うことは、まさにこの相補性のためである。エンジニアの役割は「最高のアルゴリズムを選ぶこと」ではなく「各問い合わせが正しいアルゴリズム区間に置かれるようデータと統計を整えること」である。

実務的含意は明らかである。第一に、インデックス戦略と結合アルゴリズムは一体である。Nested Loopを意図するなら内側結合キーインデックスが必須であり、Hash Joinを意図するならむしろインデックスより順次スキャン効率(パーティショニング・圧縮)が重要である。第二に、統計の鮮度がアルゴリズム選択を変える。 統計が古く大量集合を少量と誤判定すればオプティマイザがHash Joinの代わりにNested Loopを選び、数秒の問い合わせが数十分になる典型的障害が発生する——そのため実行計画が急に遅くなれば真っ先に統計と結合方式を確認する。第三に、オプティマイザヒント(USE_NL、USE_HASH、USE_MERGE など) でアルゴリズムを強制できるが、これは統計が歪んだ状況の一時的な処方にすぎず、根本的な解法は統計・インデックス・問い合わせ構造の是正である点を忘れてはならない。

具体的な数値感覚を加えると、1,000万件 ⨝ 100万件の等価結合で結果が全体の大部分を占めるとき、Hash Joinは二度の順次スキャン(数秒)で終わるが、同じ問い合わせをNested Loopに強制すると1,000万回のインデックス探索ランダムI/Oで数十分かかる。逆に「たった今加入した顧客10名の注文」を探す問い合わせではNested Loopが10回のインデックス探索(ミリ秒)で終わるが、Hash Joinに強制すると1,000万件の注文全体をスキャンしてハッシュテーブルを作るのに数秒が浪費される。同じ二つのテーブルでも「結果の選択度(selectivity)」がアルゴリズムの優劣を完全に逆転させるのである。

選択の指針を一文で要約すればこうである。「選択度が低く(結果少量)先行集合を小さくでき、後行にインデックスがあればNested Loop、選択度が高く(結果大量)両方を全部読むべき等価結合であればHash Join、一方が既に整列されているか結合条件が不等号であればSort-Merge。」実務チューニングではこの指針を逆に利用する——すなわち「望むアルゴリズムが出るようインデックス・統計・問い合わせ構造を設計する」ことである。例えば少量結果のOLTP問い合わせが妙にHash Joinで解かれるなら、先行集合を狭める条件と後行結合キーインデックスを補強してオプティマイザがNested Loopを選ぶよう誘導する。逆に大量バッチがNested Loopで解かれて遅ければ、統計を更新するか USE_HASH ヒントでHash Joinを誘導する。このようにアルゴリズムの原理を知れば「なぜ遅いか」を診断し「どう誘導するか」を設計できるようになる。

7. 深化:現代DBMSの結合処理の進化と実務適用

結合アルゴリズムの基本三つは数十年間変わらなかったが、その上に積み重ねられた最適化技法は着実に発展してきた。実務で出会う最新動向を三つに整理する。

この三つの流れはいずれも「結合費用をさらに減らそうとする」共通目標の下、互いに異なる地点を攻める。適応型結合は選択の正確性を、並列・分散結合は処理の拡張性を、結合除去・事前集計は作業量そのものの削減を狙う。技術士試験と実務の双方でこの三つの軸を共に編み「なぜ遅いか → どの水準(選択・拡張・除去)で手を入れるか」を設計できねばならない。

第一に、適応型結合(Adaptive Join) である。Oracle 12cのAdaptive Plan、SQL ServerのAdaptive Joinのように、オプティマイザが実行前に一つの方式に確定せず実行中の実際の処理行数を見てNested LoopとHash Joinの間を動的に切り替える。これは統計誤差による「推定カーディナリティと実際の乖離」問題を実行時に補正しようとする試みで、統計が多少不正確でも深刻な誤判定を防ぐ安全装置の役割をする。同じ文脈でPostgreSQLは実行中に収集した統計で次の実行を改善する方向を広げてきた。

第二に、並列結合と分散結合である。大容量分析環境(MPP DW、Spark、Presto/Trinoなど)ではハッシュ結合を複数ノードに刻んで並列実行する。このとき結合キーで両方を再分配するシャッフル結合(shuffle/repartition join) と、小さいテーブルをすべてのノードに複製してシャッフルをなくすブロードキャスト結合(broadcast join) の選択が分散性能を左右する。一方が十分小さければブロードキャストがネットワークシャッフル費用をなくして圧倒的に速く、これは単一ノードHash Joinの「小さい側をビルドに」原理が分散環境に拡張された形である。データ偏向(skew)が激しい結合キーでは特定ノードに作業が集まる「skew join」問題が生じ、ホットキーを別途処理するskew最適化が適用される。

あわせて結合演算の種類(semi/anti/outer join)による専用処理も重要である。EXISTS・IN は対が一つあればよいセミ結合(semi join) で、最初のマッチングで探索を止めて費用を減らす。NOT EXISTS はアンチ結合(anti join) で逆の論理を使い、OUTER JOIN は対のない行もNULLで埋めて保存せねばならないためアルゴリズム実装が少しずつ異なる。オプティマイザはこれらをサブクエリ平坦化(unnesting)で通常の結合のように変えて三つのアルゴリズムを再利用するが、セミ/アンチの「早期終了」特性を活かして追加最適化する。同じHash Joinでもセミ結合であればビルド側のマッチング有無だけ表示して止める形である。

第三に、結合除去と事前集計である。オプティマイザは外部キー-主キー整合性が保証されれば結果に影響がない結合を丸ごと除去(join elimination)し、よく使う結合結果を実体化ビュー(Materialized View) であらかじめ計算しておく戦略がDWで標準である。またカラム型格納・ベクトル化実行エンジンと結合し、ハッシュ結合をSIMD単位で処理してCPU効率を高めるハードウェア親和的な実装も一般化した。実務では実行計画(EXPLAIN、EXPLAIN ANALYZE、Oracle DBMS_XPLAN)でどの結合方式が選ばれたかと推定対比の実際の行数の差を必ず確認することがチューニングの出発点である。

8. 考慮事項と示唆点

結合アルゴリズムは単なる理論ではなく性能・資源・運用安定性を分ける実務の核であるため、技術士の観点から次を総合的に考慮せねばならない。特に結合は「設計時点で決まるインデックス・パーティション・統計」と「実行時点で選択されるアルゴリズム」が互いを制約する関係であることを念頭に置き、物理設計段階から想定問い合わせパターンに合う結合戦略を先行反映することが望ましい。

適用戦略 — 問い合わせの性格に合わせたアルゴリズム誘導: OLTP(少量・高同時性)はNested Loopとインデックス設計に、OLAP・バッチ(大量・集計)はHash Joinと順次スキャン効率(パーティショニング・圧縮・並列度)にそれぞれ最適化する。一つのDBMSをOLTP/OLAPが混在するワークロードで使うときは各問い合わせ群の特性を分離してインデックス・統計・メモリ戦略を差等適用せねばならない。
トレードオフ — メモリ vs I/O、応答性 vs スループット: Hash Joinはメモリを使ってI/Oを減らす交換であり、ハッシュ領域が不足すればディスクベースに転落して利得が消える。Nested Loopはメモリに鈍感だが大量でランダムI/Oが爆発する。またNested Loopは最初の結果を速く与える(応答性)一方、Hash/Sort-Mergeは全体を処理せねばならない(スループット)ため、SLAが「初回応答時間」か「全体完了時間」かによって選択が変わる。
運用安定性 — 統計管理と計画安定化: 結合方式の誤判定の90%は「古いか不正確な統計」に起因するため、定期・自動の統計収集とヒストグラム(偏向分布の表現)が先行せねばならない。重要な問い合わせにはSQL Plan Baseline・計画固定、ヒント、結果キャッシュなどで計画が急に変わって障害になるのを防ぐ「計画安定化(plan stability)」装置を置く。
診断能力 — 実行計画の読解: 障害対応の出発点は EXPLAIN/EXPLAIN ANALYZE で「オプティマイザがどの結合方式を選び、推定行数(estimated rows)と実際の行数(actual rows)がどれだけ開いたか」を読むことである。両者の乖離が大きければ統計・カーディナリティ推定誤りを疑い、遅い段階がNested Loopの過度な反復か、Hash Joinのディスクスピル(spill)か、Sort-Mergeの外部整列かを識別して原因別に処方せねばならない。
展望と連携技術: 適応型実行とベクトル化・GPU加速、分散問い合わせエンジンの普及により結合処理は「静的選択」から「実行時適応」へ移動している。結合アルゴリズムの知識は [db-optimizer]、[btree-bplus-index]、[db-tuning]、[materialized-view]、[columnar-storage]と緊密に連携し、これらを一つの性能体系に統合して理解・設計することが技術士に求められる能力である。

参考資料

Oracle Database SQL Tuning Guide — Joins, https://docs.oracle.com/en/database/oracle/oracle-database/19/tgsql/joins.html
PostgreSQL Documentation — Planner/Optimizer, https://www.postgresql.org/docs/current/planner-optimizer.html
Microsoft SQL Server — Adaptive Query Processing, https://learn.microsoft.com/en-us/sql/relational-databases/performance/intelligent-query-processing

一言まとめ: 結合アルゴリズムは二つのテーブルの対を見つける物理的戦略であり、少量・インデックスにはNested Loop、既に整列済み・不等号にはSort-Merge、大量等価結合にはHash Joinが有利で、その選択の品質は結局、正確な統計と適切なインデックス・メモリ設計にかかっている。