はじめに
プログラマのためのSQL 第4版（以下、「訳書」とする）「25.3.1 外部結合の歴史」には外部結合の実行ステップおよび実行例が記述されています。
なお、該当の記述は4刷で一部訂正が入っています。正誤表は書籍詳細ページよりご確認ください。
プログラマのためのSQL 第4版 すべてを知り尽くしたいあなたに（ジョー・セルコ ミック ミック）｜翔泳社の本
ただ、原書である『Joe Celko's SQL for Smarties』第4版（以下、「原書」とする）と訳書では、訂正結果を踏まえても相違する記述があるようです。
また、原書・訳書共に説明のやや分かり辛い点があるように思われます。
そこで、本の説明をベースとして外部結合の実行ステップについて補足を行います。
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 | 重複行なので削除する |
{2, BBB, NULL, NULL} は8行ありますが、クロス結合の基となった行が異なれば重複行と判定しないため、削除されるのは内6行となります。
(4)
最終的に以下の結果が得られます。
| k3 | v3 | k4 | v4 |
|---|---|---|---|
| 1 | AAA | 1 | aaa |
| 1 | AAA | 1 | aaa |
| 2 | BBB | NULL | NULL |
| 2 | BBB | NULL | NULL |
| NULL | NULL | NULL | NULL |
おわりに
外部結合はクロス結合がベースとなり、そこから保存対象外の行が削除される、という流れを理解することが大切です。これを理解していれば、結果にどのような行が現れるかを説明できます。
ここで取り上げた内容以外にも、ON句の後にWHERE句が実行される、というルールがあります。このため、条件をON句に記述するのか、WHERE句に記述するかで結果が異なってきます。詳細は訳書「25.3.1 外部結合の歴史」の「業者と部品」の例を参照ください。
外部結合の実行ステップについて、原書と訳書の説明に差異があること、また原書においてもクロス結合結果からどの行を削除すべきかの説明にあいまいな点があり、理解し辛くなっていました。この記事が理解の一助となれば幸いです。また、私の解釈に誤りがあればコメントをいただけると大変ありがたいです。
原書と訳書の説明の差異については出版社（翔泳社）に問い合わせを行っています。回答および何かしら公開できる情報がありましたら、ここに追記したいと思います。
