はじめに
こんにちは。アメリカに住みながら独学でエンジニアを目指しているTairaです。
現在、SQLを勉強しており、その中でも内部結合や外部結合などを学習しています。
これらの結合では、Nested Loops、Hash、Sort Merge といったアルゴリズムが採用されることがあります。
本記事では、その中でもhashについて解説していきます。
ハッシュアルゴリズムとは？
RDBMS（リレーショナルデータベース管理システム）でテーブルを結合する際に使われる代表的な手法のひとつに「ハッシュ結合（Hash Join）」があります。特に**等値結合（equi-join）**において高いパフォーマンスを発揮するこのアルゴリズムは、Nested LoopsやSort-Merge と並ぶ重要な結合戦略のひとつです。
ハッシュ結合の基本手順
- 小さいテーブルAをフルスキャンする
- Aの結合キーをハッシュ化し、ハッシュテーブルを作成する
- 大きいテーブルBをフルスキャンし、Bのキーを使ってハッシュテーブルに照合、一致するレコードを返す
この手順によって、大量のデータから効率的に一致する行を検索できます。
なぜ小さいテーブルから処理するのか？
ハッシュテーブルは一時的にDBMSのワーキングメモリに保存されます。そのため、ハッシュ化されるテーブルが小さいほど、
- メモリ使用量が少なく済む
- ディスクI/Oが発生せず高速に照合できる
といったメリットがあります。
ハッシュ結合の特徴と制約
- メモリ使用量が多い：Nested Loopsと比べ、ハッシュテーブルを保持するために大きなメモリを必要とする。
- ディスクI/Oのリスク：ハッシュテーブルがメモリに収まらない場合はストレージにスピル（退避）され、処理が遅くなる。
- 等値結合専用：ハッシュ値は元の値の順序を保持しないため、範囲条件などの結合には利用できない。
ハッシュ結合が有効なケース
- Nested Loopsで適切な駆動表が存在しない場合
- 小さいテーブルを駆動表にできても、内部表のヒット件数が多い場合
- 内部表にインデックスが存在しない、または作成できない場合
これらのケースでは、ハッシュ結合を使うことでパフォーマンスを大幅に改善できることがあります。
まとめ
ハッシュ結合は、大量データを高速に結合できる強力な手法ですが、十分なメモリの確保や等値結合であることなど、適用条件を意識することが重要です。Nested LoopsやSort-Mergeとの使い分けを理解し、実行計画を読み解く力をつけることで、より効率的なSQLチューニングが可能になります。