【SQLチューニング】ネステッドループ・ハッシュ結合・ソートマージ結合とヒント句の活用

### はじめに

SQLでテーブル同士を結合するとき、クエリの書き方(いわゆるINNER JOINやLEFT JOINなど)は開発者が指定しますが、実際にどのような手順（アルゴリズム）で結合するかは、多くの場合データベースのオプティマイザ(クエリプランナー)が自動的に判断してくれます。
しかし、大量データを扱うようになると、オプティマイザの選択が思わぬパフォーマンス低下を招くケースや、ヒント句を使って明示的に結合手法を指定したほうが高速になるケースもあります。

本記事では、データベースで代表的な以下の3つの結合アルゴリズムと、それぞれの特徴・適したケース、そしてヒント句を使った制御方法について解説します。
1. ネステッドループ結合 (Nested Loop Join)
2. ハッシュ結合 (Hash Join)
3. ソートマージ結合 (Sort-Merge Join)

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

#### 1.1 アルゴリズムの概要
- **イメージ:** ループ処理の中で1行ずつ相手テーブルを探す
- **手順**
  1. 外部（ドライビング）テーブルから1行取得。
  2. 結合条件に合う行を内部（ドリブン）テーブルから探す。
  3. 外部テーブルの全行に対して1〜2を繰り返す。

たとえば以下のように、TableAをドライビングテーブル、TableBをドリブンテーブルとして結合するイメージです。

```sql
-- Pseudocode
FOR each row in TableA
    FIND matching rows in TableB
    OUTPUT joined row(s)
END
```

#### 1.2 特徴
- 小さいテーブル×大きいテーブル の場合に有効なケースが多いです。
- 外部テーブルの行数が少なく、内部テーブルの結合キーに**索引（インデックス）**が貼られていると高速化しやすいです。
- 外部テーブルが大きい場合は、内部テーブルアクセスが繰り返されてしまい、パフォーマンスが劣化します。

#### 1.3 よくあるケースや注意点
- OLTP的なシステム（単件問い合わせが多い）だとNested Loopが選ばれがち。
- インデックスを使うメリットが大きい場合はNested Loopに軍配が上がることが多い。
- 大量データ同士を結合するときは、後述のハッシュ結合やソートマージ結合のほうが速いケースも多いので注意。

#### 1.4 ヒント句（例: Oracleの場合）
- USE_NLなどを指定すると、強制的にNested Loopを使わせることが可能。

```sql
SELECT /*+ USE_NL(B) */ A.*, B.*
FROM TableA A
JOIN TableB B ON A.key = B.key;
```

- 他のRDBMS（SQL Server, PostgreSQL等）でも類似のヒントが用意されていたり、JOIN句にLOOP JOINオプションを付けるなどの形で実行計画を制御する方法があります。

### 2. ハッシュ結合 (Hash Join)

#### 2.1 アルゴリズムの概要
- **イメージ:** 片方のテーブル（ビルド入力）でハッシュテーブルを作り、もう片方のテーブル（プローブ入力）をハッシュテーブルに照合して結合する。
- **手順（簡略化）**
  1. ビルドテーブルの結合キーをもとにハッシュ値を計算し、メモリ上にハッシュテーブルを作成（または必要に応じてディスクにスピル）。
  2. プローブテーブルの行を一つずつ取り、結合キーのハッシュ値を計算してハッシュテーブルに突っ込む。
  3. マッチした行同士を結合して出力する。

#### 2.2 特徴
- 大きなテーブル同士の結合に強い場合が多いです。
- 両テーブルをフルスキャンしても高速になることが多く、索引がなくても問題ないケースもあります。
- メモリ量に依存する部分が大きく、ハッシュテーブルを保持するためのワークメモリが足りないとディスクに書き出しが発生し、パフォーマンスが落ちる可能性があります。

#### 2.3 よくあるケースや注意点
- データ量が非常に多い場合に採用されやすい。
- 結合キーにインデックスを貼っていない場合や、貼るメリットが薄い場合はハッシュ結合が効率的なことが多い。
- メモリ状況次第ではハッシュテーブルの作成・検索がボトルネックになり得るので要注意。

#### 2.4 ヒント句（例: Oracleの場合）
- USE_HASHヒントでハッシュ結合を強制することが可能。

```sql
SELECT /*+ USE_HASH(B) */ A.*, B.*
FROM TableA A
JOIN TableB B ON A.key = B.key;
```

- 大量データを結合する際はまずハッシュ結合が選択されることが多いですが、インデックスが効くかどうかや、メモリの状況などを見ながらオプティマイザが判断します。

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

#### 3.1 アルゴリズムの概要
- **イメージ:** 両テーブルを結合キーでソートして、ソート済みデータをマージするように走査。
- **手順（簡略化）**
  1. テーブルA, テーブルBそれぞれを結合キーでソートする。
  2. ソート済みのAとBを左右からマージしながら、キーが一致する行を結合して出力する。
  3. キーが小さい方を進める、などの手順でマージ処理を行う。

#### 3.2 特徴
- 一度ソートさえ終わればマージは線形に行えるので、連続的に結合を進められる。
- テーブルがすでに結合キー順にインデックスで整列されている（もしくはデータ自体がソート済みで取得できる）場合、ソートコストが少なくて済む。
- ハッシュ結合同様、大きなテーブルでもメリットを発揮する場合がある。ただしソートに時間がかかると本末転倒。

#### 3.3 よくあるケースや注意点
- 両テーブルが大量データで、かつ結合キーでソートするメリットが大きい場合にオプティマイザが選択。
- 既に適切なクラスタインデックスや並び順のインデックスがあれば、ソートコストを低減できる。
- ソートにメモリが必要なので、メモリ不足によるディスクへのスピルが発生すると遅くなる。

#### 3.4 ヒント句（例: Oracleの場合）
- USE_MERGEヒントを指定すると、ソートマージ結合を強制できます。

```sql
SELECT /*+ USE_MERGE(B) */ A.*, B.*
FROM TableA A
JOIN TableB B ON A.key = B.key;
```


### 4. オプティマイザが結合方式を選択するしくみ

データベースのオプティマイザ（プランナー）は、以下のような情報を総合的に判断して、Nested Loop / Hash / Sort-Merge などを選択します。
1. テーブルの統計情報（行数、平均行長、カラムの分布など）
2. インデックスの有無・選択度
3. メモリ設定（ワークメモリ、ソート領域、ハッシュ領域など）
4. コストモデル（試算したI/Oコスト、CPUコスト、ネットワークコストなど）
5. ヒント句（強制された結合方式や結合順序があれば、それを最優先または高い優先度で考慮）

そのため、テーブルの統計情報が古いと誤った結合方式が選択され、パフォーマンスが低下することもあります。定期的な統計情報更新やアナライズ(ANALYZE)が重要です。

### 5. ヒント句を活用したチューニング

#### 5.1 まずはオプティマイザ任せが基本
- 通常はオプティマイザにすべて任せる形が最も楽かつ、将来のデータ量変動にも柔軟に対応しやすいです。
- ヒント句を使って強制すると、データの分布が変わった際にかえってパフォーマンスを落とす可能性も。

#### 5.2 ヒント句が有効なケース
- オプティマイザが誤った統計情報を元に不適切な結合手法を選んでいる。
- バッチ処理などで結合方式を明示的に制御しないと極端に遅くなる場合がある。
- クエリの性質上「この結合方式のほうが確実に速い」とわかっている（ハッシュ結合を選びたい・Nested Loopにしたい等）。

#### 5.3 ヒント句の書き方例
- **Oracle**
  - USE_NL(table_alias), USE_HASH(table_alias), USE_MERGE(table_alias)など。
  - LEADING(table_alias, ...)で結合順序を指定することも可能。
- **SQL Server**
  - JOINヒントとして INNER LOOP JOIN, INNER HASH JOIN, INNER MERGE JOIN など。
  - クエリ末尾に OPTION (LOOP JOIN, MERGE JOIN, HASH JOIN, FORCE ORDER, RECOMPILE, ... ) を付けるやり方も。
- **PostgreSQL**
  - enable_nestloop, enable_hashjoin, enable_mergejoin をOFFにするなど、セッション単位でプランを制御する方法もある。
  - ヒントプラグイン (pg_hint_plan) を使うとより柔軟にヒント句が使える。
- **MySQL**
  - デフォルトでは結合方式が限られており、厳密に強制する仕組みは少ない。
  - インデックスヒント(FORCE INDEX)やSTRAIGHT_JOINなど、ある程度の制御は可能。

### 6. まとめ
- ネステッドループ結合: 小さいテーブル×大きいテーブルで、インデックスが効いている場合は高速。
- ハッシュ結合: 大きなテーブル同士の結合に強い。インデックス不要の場合でも高速になりやすい。
- ソートマージ結合: 両テーブルを結合キーでソートし、マージしながら結合。ソートが終われば効率よく結合できる。

オプティマイザはテーブル統計情報やインデックス状況、メモリ設定などを考慮して最適な結合手法を選択しますが、場合によってはヒント句で制御することも可能です。
ヒント句を多用する前に、最新の統計情報を保つ・インデックス設計を見直す・クエリを最適化するなど、基本的なチューニングから実施することをおすすめします。

#### 6.1 おまけ: チューニングのポイントまとめ
1. **統計情報を最新に**
   - ANALYZEやgather_table_stats(Oracle)などで統計を更新し、オプティマイザが正しく判断できるようにする。
2. **インデックス設計を検討**
   - ネステッドループ結合で特に重要。結合キーに適切なインデックスがあるか確認する。
3. **クエリを単純化・最適化**
   - 不要な結合やサブクエリ、SELECT句の肥大化は避ける。
4. **実行計画を確認**
   - EXPLAINやEXPLAIN ANALYZEなどで実際の結合方式・コストを確認し、現状を把握する。
5. **ヒント句は最終手段**
   - どうしてもうまくいかない場合や、特定のバッチ処理・レポート処理でのみ制御が必要な場合に使用する。

### おわりに

SQLの結合手法は、普段の開発者視点で書くINNER JOINやLEFT JOINといった論理的なものだけではなく、データベース内部でネステッドループ・ハッシュ結合・ソートマージ結合といったアルゴリズムが選択されているという“裏側”を理解することで、パフォーマンスチューニングの引き出しを増やすことができます。

もし「クエリが遅い」「オプティマイザが思ったとおりに動いてくれない」といったシーンに直面したら、まずは
- 統計情報の更新
- 実行計画の確認
- インデックスの再検討

などを行い、それでも改善しない場合はヒント句による制御を試してみてください。

この記事が皆さんのSQLチューニングの一助になれば幸いです。質問や補足などございましたら、ぜひコメントで教えてください！

以上、ネステッドループ / ハッシュ結合 / ソートマージ結合それぞれの特徴と、ヒント句を交えたチューニング方法の解説でした。ご覧いただきありがとうございました。