1. 數(shù)學(xué)基礎(chǔ)：笛卡爾乘積

笛卡爾乘積是一個(gè)數(shù)學(xué)概念：

笛卡爾乘積是指在數(shù)學(xué)中，兩個(gè)集合 X 和 Y 的笛卡爾積（Cartesian product），又稱直積，表示為 X × Y，第一個(gè)對(duì)象是 X 的成員而第二個(gè)對(duì)象是 Y 的所有可能有序?qū)Φ钠渲幸粋€(gè)成員。公式表示就是如下：

1X×Y = {（x，y）|x∈X，y∈Y}

案例：

1 2 3X = {1，2} Y = {a，b，c} X×Y = {（1，a），（1，b），（1，c），（2，a），（2，b），（2，c）}

如果對(duì)同一個(gè)數(shù)據(jù)庫(kù)的兩張表進(jìn)行 join 操作，例如表 A 記錄 c~1，1~、c~1，2~、c~1，3~，表 B 有 c~2，1~ 以及 c~2，2~ 字段。

那么笛卡爾乘積的結(jié)果是：

c~1，1~+c~2，1~、c~1，1~+c~2，2~、c~1，2~+c~2，1~、c~1，2~+c~2，2~、c~1，3~+c~2，1~、c~1，3~+c~2，2~ 共 6 條記錄。其中 + 的含義是兩條記錄并做一條記錄。

2. join 的作用是什么？

join 是關(guān)系型數(shù)據(jù)庫(kù)在關(guān)系二字上的集中體現(xiàn)，其作用在于將兩張及以上表根據(jù)列中字段間的相關(guān)關(guān)系，將多表中的行融合在一起。

3. 不同的 join 類型的語(yǔ)義

join 類型語(yǔ)義

cross joinCross 即交叉，代表笛卡爾乘積中符號(hào) ×，其也就是兩表的笛卡爾乘積結(jié)果

inner join語(yǔ)義上等效為從笛卡爾乘積中選出符合條件的交集記錄

left join語(yǔ)義上等效為從笛卡爾乘積中選出符合條件的交集記錄+左表剩余的所有記錄（把左表記錄作為基礎(chǔ)，依次添加右表字段，如果符合 ON 記錄，那么賦值為右表字段值，否則賦值為 NULL）

right join語(yǔ)義上等效為從笛卡爾乘積中選出符合條件的交集記錄+右表剩余的所有記錄

full joinMySQL 并不支持 full join，不過(guò)可以等效為相同條件的 left join 與 right 的 union

full join 補(bǔ)充說(shuō)明，在 MySQL 中如下語(yǔ)句是一個(gè)典型的 Full join：

1 2 3select * from t1 left join t2 on t2.name = t1.name union select * from t1 right join t2 on t2.name = t1.name;

也可以用集合的語(yǔ)言來(lái)表示，如下圖所示：

在 SQL 實(shí)際上又把 inner join 稱為內(nèi)連接，其余所有 join 類型都稱為外連接。因此 join 有等效別名關(guān)鍵字：

inner join：join

顯示（explicit） inner join 與隱式（implicit） inner join 性能上沒(méi)有區(qū)別。

left join：left outer join

right join：right outer join

cross join：cross outer join

full join：full outer join

LEFT JOIN 和 RIGHT JOIN沒(méi)什么差別，兩者的結(jié)果差異取決于左右表的放置順序。

4. 典型帶有 join 的 SQL 語(yǔ)法分析

典型帶有 join 的 SQL 語(yǔ)句如下所示：

1 2 3 4 5SELECT 《row_list》 FROM 《left_table》 《inner|left|right》 JOIN 《right_table》 ON 《join condition》 WHERE 《where_condition》

我們按照 SQL 語(yǔ)句的執(zhí)行順序來(lái)對(duì)上述 SQL 語(yǔ)句進(jìn)行說(shuō)明：

注意事項(xiàng)：下面的說(shuō)法僅僅從 MySQL 執(zhí)行語(yǔ)義上進(jìn)行說(shuō)明，實(shí)際上 MySQL 在內(nèi)存中不會(huì)建立 vt1、vt2、vt3 表。

FROM：MySQL 中 FROM 子句總是第一個(gè)被執(zhí)行的，F(xiàn)ROM 的作用是對(duì) join 涉及的多個(gè)表進(jìn)行笛卡爾乘積 vt1 表，結(jié)果有 m*n 行（m 為左表的行數(shù)，n 為右表的行數(shù)）；

ON：新建一張 vt2 表，并根據(jù) ON 的條件篩選 vt1 表，符合條件的行加入到 vt2 中；

ON 只有對(duì) Cross join 不是必須的。

JOIN：如果是 left join 或者 right join，那么就需要添加外部行，如果是 inner join 就不需要添加外部行。添加外部行以 left join 為例，首先遍歷左表的每一行，其中不在 vt2 中的行會(huì)被添加到 vt2 中，不屬于左表的字段會(huì)被置為 NULL，最終形成 vt3；

WHERE：對(duì) vt3 表按照條件進(jìn)行過(guò)濾，滿足條件的行被輸出到 vt4；

SELECT：從 vt4 中取出指定的字段到 vt5；

ON 與 WHERE 的區(qū)別是什么？

ON 與 WHERE 在使用 inner join 時(shí)，無(wú)論是在結(jié)果上還是在性能上都沒(méi)有區(qū)別。

從結(jié)果上看，inner join 中無(wú)論條件寫(xiě)在 ON 還是 WHERE 后，結(jié)果相同。在使用 left/left join 時(shí)，結(jié)果有區(qū)別。例如，在 left join 中對(duì) ON 后不符合條件的左表中的行還是會(huì)被納入到結(jié)果中，但是卻可以被 WHERE 后的條件過(guò)濾掉。

從效率的角度上看，雖然很多中文資源認(rèn)為有所區(qū)別，但實(shí)際上沒(méi)區(qū)別，可以參考：SQL JOIN - WHERE clause vs. ON clause，查詢優(yōu)化器會(huì)避免寫(xiě)法的不同導(dǎo)致執(zhí)行效率的不同。

5. join 性能優(yōu)化

5.1 join 可以跨庫(kù)嗎？

MySQL 可以利用 FEDERATED 引擎等方式實(shí)現(xiàn)跨庫(kù) join，但查詢效率實(shí)際上并不高。通常認(rèn)為 MySQL join 操作指的同數(shù)據(jù)庫(kù)的多表 join。

5.2 join 內(nèi)部執(zhí)行過(guò)程與索引

在單表查詢中，我們通常會(huì)強(qiáng)調(diào)兩點(diǎn)：

WHERE 后的字段是否可以走索引，如果不行，那么將直接走簇集索引，進(jìn)行全表掃描，效率很差；

SELECT 后的字段是否可以走覆蓋索引，如果不行，那么則需要回表到簇集索引；

但在 join 多表問(wèn)題中，索引不僅僅需要考慮上述兩個(gè)問(wèn)題。

MySQL 中的 join 操作并不會(huì)在內(nèi)存中構(gòu)造臨時(shí)表，第四節(jié)中的說(shuō)法只是方便從語(yǔ)義上進(jìn)行理解。join 具體如何執(zhí)行取決于查詢優(yōu)化器的選擇。

MySQL 支持如下三種 join 操作（以兩張表 join 為例）：

nested loop join：利用嵌套 for 循環(huán)對(duì)兩張表中的每一行數(shù)據(jù)進(jìn)行兩兩比較。需要遍歷第一張表 n 行，每一行都需要進(jìn)行時(shí)間復(fù)雜度為 O（n） 的非索引查詢，因此總的比較的時(shí)間復(fù)雜度為 O（n^2^）

block nested loop join：對(duì) nested loop join 的優(yōu)化，利用對(duì)第一張表的行進(jìn)行查詢緩存，這樣內(nèi)層 for 循環(huán)中第二張表的每一條行數(shù)據(jù)一次性與第一張表的多條行數(shù)據(jù)進(jìn)行比較，減少了對(duì)內(nèi)表的比較次數(shù)。需要遍歷第一張表 n 行，每 k 行都需要進(jìn)行時(shí)間復(fù)雜度為 O（n） 的非索引查詢，因此總的比較的時(shí)間復(fù)雜度為 O（n^2^/k），k 為常數(shù)。

index nested loop join：從第一張表讀一行，然后在第二張表的索引中查找這個(gè)數(shù)據(jù)，索引是 B+ 樹(shù)索引。需要遍歷第一張表 n 行，每一行都需要進(jìn)行時(shí)間復(fù)雜度為 O（logn） 的非索引查詢，因此總的比較的時(shí)間復(fù)雜度為 O（nlogn）。

batched key access join：其也是利用對(duì)外循環(huán)表的字段進(jìn)行緩存，減少對(duì)內(nèi)循環(huán)表的訪問(wèn)次數(shù)。比較次數(shù)得到一定減少，但是比較的時(shí)間復(fù)雜度還是為 O（nlogn/k），k 為常數(shù)。

可見(jiàn)，join 操作的性能非常取決于第二張表是否基于索引進(jìn)行查詢。不過(guò)，為什么不要求第一張表也使用索引？

實(shí)際上，第一張表被稱為驅(qū)動(dòng)表，亦可稱之為基表，MySQL 總是要遍歷該表的所有行，每一行都去第二張表中進(jìn)行匹配查詢。遍歷可以不建立索引，走簇集索引即可，而查詢操作則需要依賴于二級(jí)索引。

那么，MySQL 如何決定將哪一張表作為驅(qū)動(dòng)表呢？

MySQL 選擇驅(qū)動(dòng)表的原則是：在對(duì)最終結(jié)果集沒(méi)影響的前提下，優(yōu)先選擇結(jié)果集最少的那張表作為驅(qū)動(dòng)表。原因在于驅(qū)動(dòng)表的行數(shù)決定了在非驅(qū)動(dòng)表中進(jìn)行查詢的次數(shù)，驅(qū)動(dòng)表行數(shù)越少，進(jìn)行查詢的次數(shù)越少。

如果是 left join，那么基表通常是 left join 左側(cè)表，right join 的基表通常為 right join 右側(cè)表。

因此，我們要非常注意非驅(qū)動(dòng)表的索引，在 ON 以及 WHERE 后的字段都應(yīng)該被索引覆蓋。

5.3 join 與數(shù)據(jù)庫(kù)范式

數(shù)據(jù)庫(kù)范式有若干條［4］，定義偏于學(xué)術(shù)性，但核心思路是簡(jiǎn)潔明了的：數(shù)據(jù)庫(kù)范式目的是使結(jié)構(gòu)更合理，消除存儲(chǔ)異常，使數(shù)據(jù)冗余盡量小，便于插入、刪除和更新。

join 操作的原因就在于多表之間有關(guān)系并且多個(gè)表之間數(shù)據(jù)幾乎沒(méi)有冗余。

舉一個(gè)例子，我們有三個(gè)表：

student（id，name）

class（id，description）

student_class（student_id，class_id）

如果要查詢一個(gè)學(xué)生對(duì)應(yīng)的班級(jí)描述，那么就需要對(duì)上述三標(biāo)進(jìn)行 join，join 的性能問(wèn)題可能會(huì)使我們產(chǎn)生擔(dān)心。

為此，我們可以故意破壞范式，制造出一張存在冗余的“大表”：

student_class_full（student_id， class_id， name， description）

你會(huì)發(fā)現(xiàn)，class 的 description 可能存儲(chǔ)在兩個(gè)表中（student_class_full 與 class），這不符合范式，并且為寫(xiě)操作帶來(lái)了一致性問(wèn)題以及寫(xiě)性能下降。另一方面，我們不再需要使用 join 來(lái)完成查詢，讀性能得到提高。

可見(jiàn)，在一些場(chǎng)景下，我們可以選擇破壞數(shù)據(jù)庫(kù)范式，避免使用 join 來(lái)提高讀性能。代價(jià)是不同表之間出現(xiàn)的字段冗余、寫(xiě)性能下降，寫(xiě)操作出現(xiàn)多表間的一致性問(wèn)題。

5.4 join 來(lái)代替子查詢

join 比子查詢?cè)诳臻g復(fù)雜度上要低，因此很多人建議利用 join 來(lái)代替子查詢：

子查詢：執(zhí)行子查詢時(shí)，MYSQL 需要?jiǎng)?chuàng)建臨時(shí)表，查詢完畢后再刪除這些臨時(shí)表，所以，子查詢的速度會(huì)受到一定的影響，這里多了一個(gè)創(chuàng)建和銷毀臨時(shí)表的過(guò)程。

join：正如 5.3 小節(jié)所述，join 走嵌套查詢。小表驅(qū)動(dòng)大表，通過(guò)索引字段進(jìn)行關(guān)聯(lián)。

6. 是否應(yīng)當(dāng)使用 join？

阿里巴巴在 Java 開(kāi)發(fā)手冊(cè)中建議［8］：超過(guò)三個(gè)表禁止 join。需要 join 的字段，數(shù)據(jù)類型保持絕對(duì)一致。

可見(jiàn)，阿里巴巴的意思是可以用 join，但是不要超過(guò)3張表。

（1）為什么 join 表的個(gè)數(shù)不能太多？

雖然我們可以利用索引來(lái)優(yōu)化查詢，但是如果是 k 張 n 行的數(shù)據(jù)庫(kù)進(jìn)行 join 查詢，最壞的情況下時(shí)間復(fù)雜度為 O（n*（logn）^k-1^），因此 join 表的數(shù)量應(yīng)當(dāng)?shù)玫娇刂啤?/p>

例如，我們假設(shè)每一張表的行數(shù)為 1000，000 行，那么時(shí)間復(fù)雜度有：

join 表的數(shù)量（k）時(shí)間復(fù)雜度

220*1000，000

3400*1000，000

48000*1000，000

kO（n*（logn）^k-1^）

（2）為什么可以使用 join？

很多場(chǎng)景下 join 是最優(yōu)選擇。例如兩張表各有 10W 條數(shù)據(jù)，我們的確可以利用 service 層，分兩步向兩個(gè)數(shù)據(jù)庫(kù)索要對(duì)應(yīng)的行數(shù)據(jù)，然后在 service 層完成數(shù)據(jù)行的關(guān)聯(lián)與過(guò)濾。但是 2*10 W 行數(shù)據(jù)有很大的網(wǎng)絡(luò)傳輸壓力，并且會(huì)對(duì) service 層所在的服務(wù)器內(nèi)存有一定壓力。而 join 在 mysql server 處實(shí)際可能僅僅會(huì)得到 100 條符合要求的記錄，那么對(duì)比起來(lái)，在 service 層的額外開(kāi)銷更難以接受。

當(dāng)然，分庫(kù)的 join 避免不了網(wǎng)絡(luò)傳輸?shù)念~外開(kāi)銷（排除一機(jī)多庫(kù)）。

SUMMARY

基于笛卡爾乘積，我們能夠方便地從語(yǔ)義上理解 MySQL 各種 join 語(yǔ)義；

第 4 節(jié)從語(yǔ)義上說(shuō)明了典型帶有 join 的 SQL 語(yǔ)法的執(zhí)行過(guò)程，但是注意其內(nèi)部并不會(huì)建立多個(gè)虛擬表；

第 5 節(jié)分析了 join 操作的內(nèi)部機(jī)制：join 基于小表驅(qū)動(dòng)大表地進(jìn)行嵌套查詢，被驅(qū)動(dòng)表是否能夠走索引進(jìn)行查詢將決定整個(gè) join 語(yǔ)句的執(zhí)行效率；

第 6 節(jié)分析了 join 使用建議，并給出其時(shí)間復(fù)雜度模型，解釋了阿里巴巴建議 join 表數(shù)量不應(yīng)當(dāng)超過(guò) 3 張的原因；

作者：spongecaptain

https://spongecaptain.cool/post/mysql/joininmysql/

責(zé)任編輯：haq