外部結合がどういう流れで処理されるか、調べてみた

LEFT JOINについて、内部でテーブルのレコードがどう処理されているのか、
細かく調査してみました。そのメモ。

#### 事前準備

■使用するテーブル
　・T1テーブル
　・T2テーブル
![使うテーブル.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/a5dc3c1d-8701-41a7-fabd-763648c09841.png)

■使用するSQL文
```SQL
  SELECT T1.id, T1.col1, T2.col2
    FROM T1 LEFT JOIN T2
      ON T1.id = T2.id
```


■出力結果
![SQL実行結果.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/a8c2c0a6-df78-a8e7-6bc3-ad69a456f5ee.png)

#### 疑問
【疑問】
・4,5行目は、条件を満たしていないのではないか
　例えば4行目、T1のidは「4」,T2のidは「NULL」なので、
　「4 = NULL」でfalseになるので、ON句の条件「T1.id = T2.id」を満たしていない??
　なぜこれらレコードが出力されるのか。

…そして、そもそもの話になりますが、LEFT JOINの実行ステップがわからないという問題もあります。
よくSQLのテキストやWebサイトでは「左側のテーブルのレコードを全て出力する」と説明がありますが、正直意味がよくわかっていないところもあります。。
その他にも、結合後のNULLさんはどこからやってきたのか?など、個人的に外部結合の中身は
もはやブラックボックスと化してしまい、気になって夜も眠れます。

そして、この不明瞭なところが解決できれば、この疑問も解消されそうな気がします。
少し遠回りかもしれないですが、実行ステップがどうなっているかを
本やサイトを参考に調べてみました。


#### 調査結果
LEFT JOIN、RIGHT JOINONの実行ステップは手順が多く、
ON句の条件式の前後に「隠れた処理」があるようです。

```SQL
  SELECT T1.id, T1.col1, T2.col2
    FROM T1 LEFT JOIN T2
-- ① CROSS JOIN を行う
-- ② ON句条件による判定
    ON T1.id = T2.id
-- ③ 派生行の削除（ON句でFALSEになった行の削除）
-- ④ 対象行以外の行のNULL変換
-- ⑤ 重複行の削除
```
順番よく見ていきましょう。
###### ① CROSS JOINを行う
この処理は、ON句でレコードをふるいにかける前に行われます。
左側のT1テーブルを軸に、Nested Loopしていき、２つのテーブルの直積を求めます。
![① CROSS JOINを行う.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/5f5f23e5-d1cd-2748-0419-ab0864767645.gif)

↓出来上がった一時テーブル
![CROSS JOINで作成された一時TBL.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/a4372da2-7b15-61f8-b3be-0b2d5e80f4b6.png)

※補足：
　・Nested Loopとは、結合アルゴリズムの一種で、手続き型的に言えば「２重のループ文」になります。
　　ここで話すと、少し脱線しそうなので別の機会に説明させていただきます。

###### ② ON T1.id = T2.id の条件に合致するか１行ずつ判定
ここで、SQL分に記載の ON句の登場です。①で出したレコードに対して
ひとつずつ条件に当てはまるか見ていきます。
下図では、条件がTRUEのレコードを赤色で示しています。
![ON句条件判定.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/d68f9179-13b2-f560-8aee-155a8bb98238.gif)


###### ③ 派生行を削除する
【フェーズ１】：各レコードをグループ単位で分ける。

【フェーズ２】：各グループごとに派生行の判定を行う
　１．グループ内のレコードに一つでもON句条件がTRUEのレコードがいた場合、そのグループの行は
　　ON句条件がTRUEのレコードを除き、全て派生行対象になります。
　２．上記１の派生行対象外のレコード以外、かつ②のON句条件にてFALSEのレコードは、
　　派生行定対象になります。


フェーズごとに順番に見ていきましょう。
【フェーズ１】：各レコードをグループ単位で分ける。
![派生行のイメージ.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/c2de3838-ccd7-df7e-ffa8-8d7c48024f58.gif)

【フェーズ２】：各グループごとに派生行の判定を行う
・ON句条件で全てFALSEだったグループ（グレー部分のグループ）→派生行対象外
・グレー部分のグループ以外かつ、ON句条件がTRUEのレコードが存在しているグループ→派生行対象
![外部結合 のコピー20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/60a39936-eb63-e785-ffa4-0209e8dc866c.png)
派生行は下図のようになります。
※注：下の方の「ON句条件で全てFALSEなので派生行対象外」はフェーズ１で対象外なので、
　　削除されずにそのまま残ります。
![外部結合 のコピー.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/9c9643ff-b94f-1d05-48e5-407f360e003d.png)
派生行を削除します。↓派生行削除後の一時テーブル
![外部結合 のコピー (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/c172eb1d-3d9f-4a9c-796d-460bd0f7c146.png)

②のまとめ
・「派生行」は、①のCROSS JOINにて矢印の根本が一緒のグループで分けた際に、
　　ON句条件がFALSEのレコードのことです。ただし、グループ内全てのレコードのON句条件がFALSEの場合、そのグループのレコードは全て派生行対象外となります。

###### ④ NULLへの変換
③のフェーズ１で派生行対象外となったレコードのカラムの値を全てNULLに変換します。
ただし、左側（RIGHT JOINなら右側）に対応するカラムは変換対象外です。
![外部結合 のコピー (2).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/848251bc-a7f0-aa81-ca86-f96ee99c5c2d.png)


###### ⑤ 重複行の削除
④で変換した行に対し、重複行を削除します。
![外部結合 のコピー27.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/dc99b567-8822-f1d2-9906-20a0828fedb0.png)
![外部結合 のコピー28.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/9b716b54-d47a-d47f-7e16-400be8956dc1.png)


最後にSELECT句で欲しい情報だけを表示して完了です。
![外部結合 のコピー30.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/0a8b4d45-1548-f7f4-b99e-6617787cb2bc.png)
![外部結合 のコピー31.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/676976/cd0bfafa-bab4-ea4a-a035-c0dd846cd909.png)



【疑問への回答】
・出力されたテーブルの値が、LEFT JOINのON句の条件に当てはまらないのは、
　DBが、ON句前後で「見えない処理」を行なっている為。詳しく説明すると、
　ON句の条件が走るタイミングはCROSS JOINの直後であり、
　それ以降の「対象行以外の行のNULL変換」、「重複行の削除」では
　ON句による条件による判定は行われない。なので、NULLが含まれる行が出力される
　スッキリしました!!

ちなみに、当記事に書いた実行ステップは、LEFT JOINを「手計算」したものです。
実際の処理は、DBの製品やオプティマイザなどによって異なると思います。
なので、この記事はあくまでJOIN句の動きを説明する際や、
SQLの読解力を深めるための参考知識として見ていただければと思います。

以上

※参考文庫、サイト
・プログラマのためのSQL 第2版 P220, 221
https://www.amazon.co.jp/exec/obidos/ASIN/4798128023/patotaityo-22/
・SQLの外部結合の実行ステップを理解する
https://taityo-diary.hatenablog.jp/entry/2019/09/24/060108