More than 3 years have passed since last update.

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

Last updated at 2021-07-28Posted at 2021-07-21

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

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

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

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

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

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

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

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

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のページ数は以下のようになっています。

innertableのページ数は以下のようになっています。

全件を結合してみる

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

結合方法	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

SET STATISTICS IO, TIME ON

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

SET STATISTICS IO, TIME OFF

MERGE JOIN

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

SET STATISTICS IO, TIME ON

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

SET STATISTICS IO, TIME OFF

HASH JOIN

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

SET STATISTICS IO, TIME ON

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

SET STATISTICS IO, TIME OFF

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

MERGE JOIN

HASH JOIN

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

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

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