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

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

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

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）}

如果對同一個數(shù)據(jù)庫的兩張表進(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ù)庫在關(guān)系二字上的集中體現(xiàn)，其作用在于將兩張及以上表根據(jù)列中字段間的相關(guān)關(guān)系，將多表中的行融合在一起。

3. 不同的 join 類型的語義

join 類型語義

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

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

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

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

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

full join 補充說明，在 MySQL 中如下語句是一個典型的 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;

也可以用集合的語言來表示，如下圖所示：

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

inner join：join

顯示（explicit） inner join 與隱式（implicit） inner join 性能上沒有區(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沒什么差別，兩者的結(jié)果差異取決于左右表的放置順序。

4. 典型帶有 join 的 SQL 語法分析

典型帶有 join 的 SQL 語句如下所示：

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

我們按照 SQL 語句的執(zhí)行順序來對上述 SQL 語句進(jìn)行說明：

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

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

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

ON 只有對 Cross join 不是必須的。

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

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

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

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

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

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

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

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

5.1 join 可以跨庫嗎？

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

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

在單表查詢中，我們通常會強調(diào)兩點：

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

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

但在 join 多表問題中，索引不僅僅需要考慮上述兩個問題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

舉一個例子，我們有三個表：

student（id，name）

class（id，description）

student_class（student_id，class_id）

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

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

student_class_full（student_id， class_id， name， description）

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

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

5.4 join 來代替子查詢

join 比子查詢在空間復(fù)雜度上要低，因此很多人建議利用 join 來代替子查詢：

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

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

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

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

可見，阿里巴巴的意思是可以用 join，但是不要超過3張表。

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

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

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

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

220*1000，000

3400*1000，000

48000*1000，000

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

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

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

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

SUMMARY

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

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

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

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

作者：spongecaptain

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

責(zé)任編輯：haq