MySQL join的語義學習

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

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

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

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ù)庫的兩張表進行 join 操作，例如表 A 記錄 c~1，1~、c~1，2~、c~1，3~，表 B 有 c~2，1~ 以及 c~2，2~ 字段。

那么笛卡爾乘積的結果是：

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

3. 不同的 join 類型的語義

join 類型語義

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

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

left join語義上等效為從笛卡爾乘積中選出符合條件的交集記錄+左表剩余的所有記錄（把左表記錄作為基礎，依次添加右表字段，如果符合 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 稱為內連接，其余所有 join 類型都稱為外連接。因此 join 有等效別名關鍵字：

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沒什么差別，兩者的結果差異取決于左右表的放置順序。

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 語句進行說明：

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

FROM：MySQL 中 FROM 子句總是第一個被執(zhí)行的，F(xiàn)ROM 的作用是對 join 涉及的多個表進行笛卡爾乘積 vt1 表，結果有 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 表按照條件進行過濾，滿足條件的行被輸出到 vt4；

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

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

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

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

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

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

5.1 join 可以跨庫嗎？

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

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

在單表查詢中，我們通常會強調兩點：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

student（id，name）

class（id，description）

student_class（student_id，class_id）

如果要查詢一個學生對應的班級描述，那么就需要對上述三標進行 join，join 的性能問題可能會使我們產生擔心。

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

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 比子查詢在空間復雜度上要低，因此很多人建議利用 join 來代替子查詢：

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

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

6. 是否應當使用 join？

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

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

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

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

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

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

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ù)庫索要對應的行數(shù)據(jù)，然后在 service 層完成數(shù)據(jù)行的關聯(lián)與過濾。但是 2*10 W 行數(shù)據(jù)有很大的網(wǎng)絡傳輸壓力，并且會對 service 層所在的服務器內存有一定壓力。而 join 在 mysql server 處實際可能僅僅會得到 100 條符合要求的記錄，那么對比起來，在 service 層的額外開銷更難以接受。

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

SUMMARY

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

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

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

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

作者：spongecaptain

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

責任編輯：haq