はじめに
こんにちは！今回は、テーブルの結合に焦点を当て、代表的な結合アルゴリズムを紹介します。普段の開発では、SQLのJOIN句を書くことが多いですが、データベース内部ではどのように行が突き合わされているのか、一度知っておくとパフォーマンスチューニングに役立ちます。
本文
1. テーブルの結合とは？
リレーショナルデータベースでは、複数のテーブルに分割されたデータを組み合わせて必要な情報を得るために結合（JOIN） を行います。結合対象となる列を比較し、条件に適合する行同士を連結するのが基本の流れです。
代表的な結合アルゴリズムには以下のようなものがあります。
2. 入れ子ループ法（ネストループ法）
2.1 概要
入れ子ループ法（Nested Loop Join） は、単純に2つのテーブルを二重ループで回し、すべての行同士の組み合わせを比較する方法です。例えば、A表を外側のループ、B表を内側のループとして結合列が一致するか判定します。
FOR each row in A:
FOR each row in B:
IF (結合条件に合致):
結合結果に追加
2.2 時間計算量
A表の行数を M、B表の行数を N とすると、M×N 回の比較が発生するため時間計算量は O(n^2) となります。行数が非常に多い場合は非効率ですが、小規模データや、インデックスで外側ループを適切に絞り込める場合などは一定の効果を発揮することもあります。
3. マージジョイン法
3.1 概要
マージジョイン（Sort Merge Join） は、2つのテーブルが結合列であらかじめソート（整列） されていることを利用して、効率的に結合を行う手法です。両テーブルの先頭行から比較を始め、一致すれば結合結果へ、一致しなければ小さい方を次の行へ進め、という流れを繰り返します。
- AとBを結合列でそれぞれソート
- Aの先頭行とBの先頭行を比較
- 条件合致→結果に追加し、どちらかまたは両方のカーソルを進める
- 不合致→ソート順で小さい側のカーソルを進める
- 繰り返し
3.2 時間計算量
主にソートのコスト（一般的に O(n log n)）と、マージ自体のコスト（O(M+N) 程度）になります。大量データで結合キーにソートが適している場合や、一方のテーブルが既にソート済みのインデックスを持つ場合にメリットが大きいです
4. セミジョイン法
4.1 概要
セミジョイン（Semi Join） は、別の場所にあるデータベース同士で結合するときに活用される手法です。
- 一方（A）の必要な列だけをもう一方（B）へ送る
- Bで結合可能なキーを抽出し、合致するキーのみをAに返す
- 最終的にA側で最終結合を実行
これにより、テーブル全体を丸ごと転送しなくても済むため、通信量を抑えつつ結合を実施できます。分散データベース環境などで有用です。
5. ハッシュジョイン法
5.1 概要
ハッシュジョイン（Hash Join） では、結合対象の列をハッシュ関数で分類し、ハッシュ値をキーとして結合します。
- 小さい方のテーブルに対してハッシュテーブルを作成
- 大きい方のテーブルを読み込み、同じハッシュ値を持つ行同士を結合
5.2 特徴
- 等価結合（
=条件）に強く、大量データの結合を高速に処理できる場合が多い - 範囲指定など、ハッシュ値で扱えない条件は苦手
- メモリ使用量が大きくなることがある
- 時間計算量は O(n)
セミジョイン法とハッシュを組み合わせるハッシュセミジョインも存在し、分散環境での負荷を抑えながら結合を行えます。
まとめ
テーブル結合を内部でどう実装するかは、DBMSのクエリオプティマイザが自動的に選択することが多いですが、下記の点を知っておくとチューニング時に役立ちます。
- 入れ子ループ法: 小規模or インデックスの効果が大きい場合に使われやすい。大規模データには向かない
- マージジョイン: 結合列のソートがカギ。大量データでもソート後のマージ処理が高速
- セミジョイン: 分散DBなど、通信量を減らすために必要な列だけ送受信し、最小限のやり取りで結合
-
ハッシュジョイン: 大量データの
=結合に効果的。ハッシュテーブルを利用して結合を効率化
DBMSは、テーブルの行数やインデックス、統計情報などを基に最適なアルゴリズムを自動選択します。大規模データや分散システムでパフォーマンス問題が起こったときは、実行計画（EXPLAINなど） を参照し、「どの結合方式が使われているか」を確認することで、より的確なチューニングができるようになります。