SQL Server/SQL Database再入門 第6回 結合方法：NESTED LOOP、MERGE、HASH

# いろいろ書いているけど何を気にしておけばいいの？

**APIとかWEBとかのオンライン処理の場合**
基本的にNESTED LOOPになっているはず。
なっていなければ絞り込みできていないかインデックスが足りない。どうしても変な実行計画になってしまう場合はLOOPを名指しする。

**バッチの場合**
データ量が多いテーブルの結合なのにNESTED LOOPになっているなら統計がおかしいか、テーブル関数が原因かも。
MERGE JOINのソートが遅い場合はHASH JOINを名指しするか、並び順を意識してインデックスを見直すと改善する。

# 結合方法の種類：NESTED LOOP、MERGE、HASH

INNERとかOUTERとかCROSSとかでの話ではなくて、NESTED LOOPとかMERGEとかHASHの話です。
この意味での結合はテーブル同士のJOINの場合だけではなく、クラスター化インデックスと非クラスター化インデックスの場合でも出てきます。
公式には以下に説明が掲載されています。

https://docs.microsoft.com/ja-jp/sql/relational-databases/performance/joins?view=sql-server-ver15#understanding-nested-loops-joins

| 結合方法 | 仕組み                                                       | 利用シーン                                                   |
| -------- | ------------------------------------------------------------ | ------------------------------------------------------------ |
| Loop     | 一方を外部テーブル（外側のループ）として使用し、もう一方を内部テーブル（内側のループ）として使用します。 外部ループでは、外部入力テーブルを 1 行ずつ使用します。 内部ループは、外部行の 1 行ごとに実行され、内部入力テーブルで一致行を検索します。 | 一方の結合入力が少なく、他方の結合入力が多く、その結合列にインデックスが設定されている場合 |
| Merge    | 両方の入力がマージ列を基準に並べ替えられていることが必要です。各入力が並べ替えられるので、は各入力から 1 行ずつ取得して、それらを比較します。行が等しい場合、それらの行が返され、 行が等しくない場合は、小さい方の値が含まれる行が破棄されます。 | 結合列に基づいて並べ替えられている場合                       |
| Hash     | まず一方の結合列にハッシュ関数にかけ、ハッシュ・テーブルを作成します。次にもう一方の結合列にもハッシュ関数にかけ、結合できるかをハッシュ・テーブルで確認し、ハッシュ値が等しいレコードを結合して結果を返します。 | 並べ替えられておらず、インデックスが設定されていない大量の入力がある場合。特に複雑なクエリでの中間結果を得る場合。等号での比較が前提 |

# データの準備：クラスタ化インデックスのキーで結合できる場合

それぞれの場合の動作を確認するために、テーブルとデータを準備します。

```sql
CREATE TABLE outertable (
	okey int IDENTITY(1, 1),
	col1 NVARCHAR(10),
	col2 DATETIME,
	CONSTRAINT PK_outertable PRIMARY KEY (okey ASC)
)

CREATE TABLE innertable (
	ikey int IDENTITY(1, 1),
	col1 int,
	col2 NVARCHAR(10),
	col3 DATETIME,
	CONSTRAINT PK_innertable PRIMARY KEY (col1 ASC, ikey ASC)
)

INSERT INTO outertable (col1, col2)
SELECT TOP 100000
LEFT(o1.name + o2.name, 10), DATEADD(DAY, ROW_NUMBER() OVER (ORDER BY o1.name), GETDATE())
FROM sys.all_objects o1, sys.all_objects o2
GO

INSERT INTO innertable (col1, col2, col3)
SELECT
o1.okey, o1.col1, DATEADD(DAY, ROW_NUMBER() OVER (ORDER BY o1.col1), GETDATE())
FROM outertable o1
GO 10
```

クエリを流すと、以下の割合でデータが作られます。
outertable : innertable  = 1 : 10

outertableのページ数は以下のようになっています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/76d768cd-7188-fb4a-ac40-71837916ecc5.png)
innertableのページ数は以下のようになっています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/13e3e5cc-9fe2-9662-1c2f-92c545b3b906.png)

# 全件を結合してみる

一番分かりやすいのは全件結合してみた場合かなと思うので、全件を結合してみます。

| 結合方法 | CPU時間 | 経過時間 | outer/scan | outer/read | inner/scan | inner/read |
| -------- | ------- | -------- | ------ | ------ | ------ | ------ |
| Loop     | 2047ms  | 6629ms   | 9      | 770    | 100000 | 337710 |
| Merge    | 672ms   | 6232ms   | 1      | 734    | 1      | 12541  |
| Hash     | 2625ms  | 6496ms   | 9      | 770    | 9      | 12671  |

今回の場合、一番効率が良いのはMerge Joinです。
若干ズレる理由はよく分かりませんが、ほぼそれぞれのテーブルのページ数と同じ数の読み取りをしていて、CPU時間ももっとも短くなりました。
これはクラスター化インデックスを使って結合できるので、Merge Joinの前提であるソートの負荷がかからなかったからだろうと思います。
Hash Joinも読み取っているページ数はほぼそれぞれのテーブルのページ数と同じ数ですが、CPU時間が長くなっています。
Nested Loop Joinの場合はoutertableの読み取り数はテーブルのページ数とほぼ同じですが、innertableの読み取り数は圧倒的に多く、outertableの行数×innertableの深さ*1.1くらいの結果になりました。

## NESTED LOOP JOIN

```sql
SET STATISTICS IO, TIME ON

SELECT
*
FROM outertable o 
INNER LOOP JOIN innertable i 
ON o.okey = i.col1

SET STATISTICS IO, TIME OFF
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/f8a2c79f-829b-6484-fb13-3ed441a50517.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/81e47bd3-fef9-e736-1cec-b52accf60bcd.png)

## MERGE JOIN

何も結合方法を指定しない場合、今回はMERGE JOINになるのですが、一応明示的に指定します。

```sql
SET STATISTICS IO, TIME ON

SELECT
*
FROM outertable o 
INNER MERGE JOIN innertable i 
ON o.okey = i.col1

SET STATISTICS IO, TIME OFF
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/ed4cd433-fa7d-f2aa-f2dc-9691475fce30.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/42bc55bd-1d24-d921-4062-2c48c986461b.png)

## HASH JOIN

ハッシュテーブルを作成する必要があるので、 WorktableとWorkfile の作成が行われています。

```sql
SET STATISTICS IO, TIME ON

SELECT
*
FROM outertable o 
INNER HASH JOIN innertable i 
ON o.okey = i.col1

SET STATISTICS IO, TIME OFF
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/c46df4c8-d2c2-d743-b1c5-723f730cab3b.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/9b4fe23a-0a98-2836-e3f2-725b9265ef08.png)

# Outertableから10件を抽出して結合してみる

今回の場合も一番効率が良いのはMerge Joinです。
どの結合方法の実行計画も先にSEEKしてから結合しています。
Merge JoinとHash Joinは読み取っているページ数は同じ数ですが、Hash Joinの方がCPU時間が長くなっています。
Nested Loop Joinの場合は読み取っているページ数は一番多くなっていますが、処理時間とCPU時間はMerge Joinと1ms以下の差しかありません。
特に何も指定しない場合に今回選択されるのはNested Loop Joinです。

| 結合方法 | CPU時間 | 経過時間 | o/scan | o/read | i/scan | i/read |
| -------- | ------- | -------- | ------ | ------ | ------ | ------ |
| Loop     | 0ms  | 0ms   | 1    | 3   | 10 | 31 |
| Merge    | 0ms   | 0ms   | 1      | 3  | 1      | 4 |
| Hash     | 16ms | 0ms   | 1     | 3   | 1     | 4 |

## NESTED LOOP JOIN

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/48ccff59-a6db-669a-414a-4669db6e156a.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/b224d8c7-6886-1796-099c-16b4e040c371.png)

## MERGE JOIN

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/5966d5a4-ac25-3737-ee7f-466404ed98d9.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/dc4a8867-61fb-e3ff-c16f-de2160b404be.png)


## HASH JOIN

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/b18acbe9-46f3-836a-1b4d-6220becc2c01.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/22846c36-9916-b3c4-703e-0ce12d37e440.png)

# データの準備：インデックスのキーで結合できない場合

innertableを利用する際にインデックスが使えないように修正します。
Nested Loop Joinが終わらなくなってしまうのでデータの件数も1/10にしました。

```sql
CREATE TABLE outertable (
    okey int IDENTITY(1, 1),
    col1 NVARCHAR(10),
    col2 DATETIME,
    CONSTRAINT PK_outertable PRIMARY KEY (okey ASC)
)

CREATE TABLE innertable (
    ikey int IDENTITY(1, 1),
    col1 int,
    col2 NVARCHAR(10),
    col3 DATETIME,
    CONSTRAINT PK_innertable PRIMARY KEY (ikey ASC)
)

INSERT INTO outertable (col1, col2)
SELECT TOP 10000
LEFT(o1.name + o2.name, 10), DATEADD(DAY, ROW_NUMBER() OVER (ORDER BY o1.name), GETDATE())
FROM sys.all_objects o1, sys.all_objects o2
GO

INSERT INTO innertable (col1, col2, col3)
SELECT
o1.okey, o1.col1, DATEADD(DAY, ROW_NUMBER() OVER (ORDER BY o1.col1), GETDATE())
FROM outertable o1
GO 10
```

# 全件を結合してみる

今回の場合、一番効率が良いのはHash Joinです。
並び替えをしなければならないのでMerge JoinはHash Joinよりも効率が悪くなっています。
予想どおり悲惨な結果になったのはNested Loop Joinでした。

| 結合方法 | CPU時間  | 経過時間 | o/scan | o/read | i/scan | i/read | w/scan | w/read  |
| -------- | -------- | -------- | ------ | ------ | ------ | ------ | ------ | ------- |
| Loop     | 595825ms | 89940ms  | 9      | 220    | 8      | 6288   | 8      | 8691960 |
| Merge    | 457ms    | 1001ms   | 9      | 220    | 9      | 825    |        |         |
| Hash     | 125ms    | 966ms    | 1      | 75     | 1      | 786    |        |         |


## NESTED LOOP JOIN

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/1c619ad5-4c9a-d060-de90-04986b7c8752.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/4bf7ac6f-d3ad-cace-0d87-2640f8750bd6.png)

## MERGE JOIN

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/b1787aa3-0fb8-5fb1-a80e-9d073d3cd9d7.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/7a376c9e-7b65-3eac-9c26-5b6c10953c00.png)

## HASH JOIN

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/982813bb-07ad-00fa-8bdf-4aebc0278e50.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/b817ef01-a654-b3a2-43e5-dce002971785.png)

# Outertableから10件を抽出して結合してみる

今回のケースの結果は微妙ですが、リソースの効率が良いのはHash Joinです。
Merge JoinもNested Loop Joinも全件の場合とほぼ同じ流れで処理しているのが分かります。


| 結合方法 | CPU時間 | 経過時間 | o/scan | o/read | i/scan | i/read | w/scan | w/read |
| -------- | ------- | -------- | ------ | ------ | ------ | ------ | ------ | ------ |
| Loop     | 15ms    | 10ms     | 1      | 2      | 1      | 786    | 8      | 219    |
| Merge    | 16ms    | 10ms     | 1      | 2      | 1      | 786    |        |        |
| Hash     | 0ms     | 12ms     | 1      | 2      | 1      | 786    |        |        |

## NESTED LOOP JOIN

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/9d7fb4d5-4ede-9751-333c-5200944f9952.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/dbb6158e-62ce-ba5d-add0-4a41eb767b4a.png)

## MERGE JOIN

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/b2ca1448-0eb9-0758-d549-b49545a2d5d7.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/5fe9740b-07b9-0db7-e7e4-c0c85d52323b.png)

## HASH JOIN

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/681f613c-a527-44f1-c53f-ceb261f80368.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/16609/510d6ae9-d3af-ba51-7835-01b541993f99.png)

# シリーズ SQL Server/SQL Database再入門

なんとなくならSQL Serverを使えている人のためのSQL Server/SQL DatabaseのTips集です。

1. [Decimal型とMoney型の違い](https://qiita.com/yyukawa/items/c1e23a97d4170edba23f)
1. [Index SeekとIndex Scan](https://qiita.com/yyukawa/items/4cc1cd5e447b5a5d1b48)
1. [クエリ毎の性能指標の確認方法を知る](https://qiita.com/yyukawa/items/c80151bb9db98de491a2)
1. [SQL Databaseでパーティション テーブルとパーティション インデックス](https://qiita.com/yyukawa/items/902a166c2520793b8116#%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-sql-serversql-database%E5%86%8D%E5%85%A5%E9%96%80)
1. [統計とクエリの関係](https://qiita.com/yyukawa/items/f05b8a2b89e955c94299)
1. [結合方法：NESTED LOOP、MERGE、HASH](https://qiita.com/yyukawa/items/706291047576a654f1e1#merge-join-3)