SQLの外部結合の実行ステップを理解する

はじめに

プログラマのためのSQL 第4版（以下、「訳書」とする）「25.3.1　外部結合の歴史」には外部結合の実行ステップおよび実行例が記述されています。

プログラマのためのSQL 第4版

作者:ジョー・セルコ,Joe Celko
翔泳社

Amazon

なお、該当の記述は4刷で一部訂正が入っています。正誤表は書籍詳細ページよりご確認ください。
プログラマのためのSQL 第4版すべてを知り尽くしたいあなたに（ジョー・セルコミックミック）｜翔泳社の本

ただ、原書である『Joe Celko's SQL for Smarties』第4版（以下、「原書」とする）と訳書では、訂正結果を踏まえても相違する記述があるようです。

Joe Celko's SQL for Smarties, Fourth Edition: Advanced SQL Programming (The Morgan Kaufmann Series in Data Management Systems)

作者:Celko, Joe
Morgan Kaufmann

Amazon

また、原書・訳書共に説明のやや分かり辛い点があるように思われます。

そこで、本の説明をベースとして外部結合の実行ステップについて補足を行います。

ANSi-89 Standard in SQL Server 2008
この質問スレッドで "Buy me a beer ot three and I will tell the story of the old ANSI X3H2 committee," から始まる回答の書き込みは本の著者であるセルコ自身によるものと思われ、原書の記述とほぼ同じになっています。併せてご参照ください。

外部結合の実行ステップ

外部結合の実行ステップについて、訳書では以下のように説明しています。

まず2つのテーブルをクロス結合する。そして結果セットの行を1行ずつスキャンする。

もし条件が TRUE になる行があればその行を保持する。

もし条件が FALSE または UNKNOWN になれば、その行については保存対象のテーブルの列を保持し、保存対象でないテーブルのすべての列を NULL に変換する。最後に重複行を削除する。

一方、原書では以下の説明となっています。

We build the CROSS JOIN of the two tables. Scan each row in the result set.

If the predicate tests TRUE for that row, then you keep it. You also remove all rows derived from it from the CROSS JOIN.

If the predicate tests FALSE or UNKNOWN for that row, then keep the columns from the preserved table, convert all the columns from the unpreserved table to NULLs, and remove the duplicates.

原書・訳書共にほぼ同じ説明と見えますが、原書の 2. にある "You also remove all rows derived from it from the CROSS JOIN." が訳書にはありません。そして、これは外部結合で重要な処理の一つです。これを次の実行例で確認します。

外部結合の処理例

外部結合の実行ステップを実行例で確認します。

原書・訳書記載の例

以下に示す2つのテーブルがあるとします。

[Table1]

a	b
1	w
2	x
3	y
4	z

[Table2]

a	c
1	r
2	s
3	t

本で例に挙げられている以下の外部結合を考えます。

Table1 
LEFT OUTER JOIN 
Table2
ON Table1.a = Table2.a -- JOIN condition
   AND Table2.c = 't'; -- single table condition

なお、訳書4刷以降では異なった例に修正されていることをご注意ください。今回は原書に倣って説明を進めます。

ここでは "LEFT OUTER JOIN" なので、保存対象のテーブルは演算子左側の "Table1" となります。

(1)
2つのテーブルをクロス結合します。そして結果セットの行を1行ずつON句の条件で評価します。

▲ ＝ "Table1.a = Table2.a" が成立する。
● ＝ "Table2.c = 't'" が成立する。

a	b	a	c	評価結果
1	w	1	r	▲
1	w	2	s
1	w	3	t	●
2	x	1	r
2	x	2	s	▲
2	x	3	t	●
3	y	1	r
3	y	2	s
3	y	3	t	▲● ON句の条件が TRUE になる行集合
4	z	1	r
4	z	2	s
4	z	3	t	●

(2)
ON句の条件が TRUE になる行を保持します。また、その行から派生した (derived) 全ての行を削除します。
「派生した」の解釈ですが、保存対象テーブルでON句の条件が TRUE になったのと同じ行からクロス結合結果が生み出され、かつON句の条件を満たさない行です。

a	b	a	c	評価結果
1	w	1	r
1	w	2	s
1	w	3	t
2	x	1	r
2	x	2	s
2	x	3	t
3	y	1	r	派生した行なので削除する
3	y	2	s	派生した行なので削除する
3	y	3	t	ON句の条件が TRUE になる行集合
4	z	1	r
4	z	2	s
4	z	3	t

クロス結合結果でON句の条件にて TRUE となった行に保存対象テーブルの {3, y} の行が含まれています。この {3, y} の行からクロス結合が生み出され、かつON句の条件を満たさない行が派生した行として削除対象になります。

(3)
条件が FALSE または UNKNOWN の行について、保存対象のテーブルの列を保持し、保存対象でないテーブルのすべての列を NULL に変換します。最後に重複行を削除します。
重複行の判定は保存対象テーブルの同じ行から生み出されたクロス結合結果の行同士で行います。

a	b	a	c	評価結果
1	w	NULL	NULL
1	w	NULL	NULL	重複行なので削除する
1	w	NULL	NULL	重複行なので削除する
2	x	NULL	NULL
2	x	NULL	NULL	重複行なので削除する
2	x	NULL	NULL	重複行なので削除する
3	y	3	t	ON句の条件が TRUE になる行集合
4	z	NULL	NULL
4	z	NULL	NULL	重複行なので削除する
4	z	NULL	NULL	重複行なので削除する

(4)
最終的に以下の結果が得られます。

a	b	a	c
1	w	NULL	NULL
2	x	NULL	NULL
3	y	3	t
4	z	NULL	NULL

この結果は訳書と異なりますが、原書とは一致しており、ジョー・セルコが本来意図したものとなります。

なお、訳書には原書と異なった結果と共に『あとは、この結果に「Table2.c = 't'」というSARGの条件を適用すれば、最終結果は1行に絞り込まれる。』とありますが、この説明は原書に見当たりませんでした。

より複雑な例

同じ値の行が複数あったり、NULLの行が含まれている例を考えます。

[Table3]

k3	v3
1	AAA
2	BBB
2	BBB
NULL	NULL

[Table4]

k4	v4
1	aaa
1	aaa
3	ccc
NULL	NULL

Table3 
LEFT OUTER JOIN 
Table4
ON Table3.k3 = Table4.k4;

(1)
2つのテーブルをクロス結合します。そして結果セットの行を1行ずつON句の条件で評価します。

k3	v3	k4	v4	評価結果
1	AAA	1	aaa	ON句の条件が TRUE になる行集合
1	AAA	1	aaa	ON句の条件が TRUE になる行集合
1	AAA	3	ccc
1	AAA	NULL	NULL
2	BBB	1	aaa
2	BBB	1	aaa
2	BBB	3	ccc
2	BBB	NULL	NULL
2	BBB	1	aaa
2	BBB	1	aaa
2	BBB	3	ccc
2	BBB	NULL	NULL
NULL	NULL	1	aaa
NULL	NULL	1	aaa
NULL	NULL	3	ccc
NULL	NULL	NULL	NULL

NULL = NULL は UNKNOWN となります。

(2)
ON句の条件が TRUE になる行を保持します。また、その行から派生した (derived) 全ての行を削除します。

k3	v3	k4	v4	評価結果
1	AAA	1	aaa	ON句の条件が TRUE になる行集合
1	AAA	1	aaa	ON句の条件が TRUE になる行集合
1	AAA	3	ccc	派生した行なので削除する
1	AAA	NULL	NULL	派生した行なので削除する
2	BBB	1	aaa
2	BBB	1	aaa
2	BBB	3	ccc
2	BBB	NULL	NULL
2	BBB	1	aaa
2	BBB	1	aaa
2	BBB	3	ccc
2	BBB	NULL	NULL
NULL	NULL	1	aaa
NULL	NULL	1	aaa
NULL	NULL	3	ccc
NULL	NULL	NULL	NULL

{1, AAA} は4行ありますが、内2行は「ON句の条件が TRUE になる行集合」のため、残り2行が「派生した行」として削除されます。

(3)
条件が FALSE または UNKNOWN の行について、保存対象のテーブルの列を保持し、保存対象でないテーブルのすべての列を NULL に変換します。最後に重複行を削除します。

k3	v3	k4	v4	評価結果
1	AAA	1	aaa	ON句の条件が TRUE になる行集合
1	AAA	1	aaa	ON句の条件が TRUE になる行集合
2	BBB	NULL	NULL
2	BBB	NULL	NULL	重複行なので削除する
2	BBB	NULL	NULL	重複行なので削除する
2	BBB	NULL	NULL	重複行なので削除する
2	BBB	NULL	NULL
2	BBB	NULL	NULL	重複行なので削除する
2	BBB	NULL	NULL	重複行なので削除する
2	BBB	NULL	NULL	重複行なので削除する
NULL	NULL	NULL	NULL
NULL	NULL	NULL	NULL	重複行なので削除する
NULL	NULL	NULL	NULL	重複行なので削除する
NULL	NULL	NULL	NULL	重複行なので削除する