簡介： 對于 join 操作的實現(xiàn)，大概有 Nested Loop Join (循環(huán)嵌套連接)润绵，Hash Join(散列連接) 和 Sort Merge Join(排序歸并連接) 三種較為常見的算法线椰，它們各有優(yōu)缺點和適用條件，接下來我們會依次來介紹尘盼。

關(guān)于MySQL 的 join憨愉，大家一定了解過很多它的“軼事趣聞”，比如兩表 join 要小表驅(qū)動大表卿捎，阿里開發(fā)者規(guī)范禁止三張表以上的 join 操作配紫，MySQL 的 join 功能弱爆了等等。這些規(guī)范或者言論亦真亦假午阵，時對時錯躺孝，需要大家自己對 join 有深入的了解后才能清楚地理解。

下面底桂，我們就來全面的了解一下 MySQL 的 join 操作植袍。

正文

在日常數(shù)據(jù)庫查詢時，我們經(jīng)常要對多表進(jìn)行連表操作來一次性獲得多個表合并后的數(shù)據(jù)籽懦，這是就要使用到數(shù)據(jù)庫的 join 語法于个。join 是在數(shù)據(jù)領(lǐng)域中十分常見的將兩個數(shù)據(jù)集進(jìn)行合并的操作，如果大家了解的多的話猫十，會發(fā)現(xiàn) MySQL览濒，Oracle，PostgreSQL 和 Spark 都支持該操作拖云。本篇文章的主角是 MySQL贷笛，下文沒有特別說明的話，就是以 MySQL 的 join 為主語宙项。而 Oracle 乏苦，PostgreSQL 和 Spark 則可以算做將其吊打的大boss，其對 join 的算法優(yōu)化和實現(xiàn)方式都要優(yōu)于 MySQL尤筐。

MySQL 的 join 有諸多規(guī)則汇荐，可能稍有不慎，可能一個不好的 join 語句不僅會導(dǎo)致對某一張表的全表查詢盆繁，還有可能會影響數(shù)據(jù)庫的緩存掀淘，導(dǎo)致大部分熱點數(shù)據(jù)都被替換出去，拖累整個數(shù)據(jù)庫性能油昂。

所以革娄，業(yè)界針對 MySQL 的 join 總結(jié)了很多規(guī)范或者原則，比如說小表驅(qū)動大表和禁止三張表以上的 join 操作冕碟。下面我們會依次介紹 MySQL join 的算法拦惋，和 Oracle 和 Spark 的 join 實現(xiàn)對比，并在其中穿插解答為什么會形成上述的規(guī)范或者原則安寺。

對于 join 操作的實現(xiàn)厕妖，大概有 Nested Loop Join (循環(huán)嵌套連接)，Hash Join(散列連接) 和 Sort Merge Join(排序歸并連接) 三種較為常見的算法挑庶，它們各有優(yōu)缺點和適用條件言秸，接下來我們會依次來介紹。

MySQL 中的 Nested Loop Join 實現(xiàn)

Nested Loop Join 是掃描驅(qū)動表挠羔，每讀出一條記錄井仰，就根據(jù) join 的關(guān)聯(lián)字段上的索引去被驅(qū)動表中查詢對應(yīng)數(shù)據(jù)。它適用于被連接的數(shù)據(jù)子集較小的場景破加，它也是 MySQL join 的唯一算法實現(xiàn)俱恶，關(guān)于它的細(xì)節(jié)我們接下來會詳細(xì)講解。

MySQL 中有兩個 Nested Loop Join 算法的變種范舀，分別是 Index Nested-Loop Join 和 Block Nested-Loop Join合是。

Index Nested-Loop Join 算法

下面，我們先來初始化一下相關(guān)的表結(jié)構(gòu)和數(shù)據(jù)

CREATE TABLE `t1` (
  `id` int(11) NOT NULL,
  `a` int(11) DEFAULT NULL,
  `b` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `a` (`a`)
) ENGINE=InnoDB;

delimiter ;;
# 定義存儲過程來初始化t1
create procedure init_data()
begin
  declare i int;
  set i=1;
  while(i<=10000)do
    insert into t1 values(i, i, i);
    set i=i+1;
  end while;
end;;
delimiter ;
# 調(diào)用存儲過來來初始化t1
call init_data();
# 創(chuàng)建并初始化t2
create table t2 like t1;
insert into t2 (select * from t1 where id<=500)

有上述命令可知锭环，這兩個表都有一個主鍵索引 id 和一個索引 a聪全，字段 b 上無索引。存儲過程 init_data 往表 t1 里插入了 10000 行數(shù)據(jù)辅辩，在表 t2 里插入的是 500 行數(shù)據(jù)难礼。

為了避免 MySQL 優(yōu)化器會自行選擇表作為驅(qū)動表娃圆，影響分析 SQL 語句的執(zhí)行過程，我們直接使用 straight_join 來讓 MySQL 使用固定的連接表順序進(jìn)行查詢蛾茉，如下語句中讼呢，t1是驅(qū)動表，t2是被驅(qū)動表谦炬。

select * from t2 straight_join t1 on (t2.a=t1.a);

使用我們之前文章介紹的 explain 命令查看一下該語句的執(zhí)行計劃悦屏。

從上圖可以看到，t1 表上的 a 字段是由索引的键思，join 過程中使用了該索引础爬，因此該 SQL 語句的執(zhí)行流程如下：

1. 從 t2 表中讀取一行數(shù)據(jù) L1；
2. 使用L1 的 a 字段吼鳞，去 t1 表中作為條件進(jìn)行查詢看蚜；
3. 取出 t1 中滿足條件的行， 跟 L1組成相應(yīng)的行赔桌，成為結(jié)果集的一部分失乾；
4. 重復(fù)執(zhí)行，直到掃描完 t2 表纬乍。

這個流程我們就稱之為 Index Nested-Loop Join碱茁，簡稱 NLJ，它對應(yīng)的流程圖如下所示仿贬。

需要注意的是纽竣，在第二步中，根據(jù) a 字段去表t1中查詢時茧泪，使用了索引蜓氨，所以每次掃描只會掃描一行(從explain結(jié)果得出，根據(jù)不同的案例場景而變化)队伟。

假設(shè)驅(qū)動表的行數(shù)是N穴吹，被驅(qū)動表的行數(shù)是 M。因為在這個 join 語句執(zhí)行過程中嗜侮，驅(qū)動表是走全表掃描港令，而被驅(qū)動表則使用了索引，并且驅(qū)動表中的每一行數(shù)據(jù)都要去被驅(qū)動表中進(jìn)行索引查詢锈颗，所以整個 join 過程的近似復(fù)雜度是 N2log2M顷霹。顯然，N 對掃描行數(shù)的影響更大击吱，因此這種情況下應(yīng)該讓小表來做驅(qū)動表淋淀。

當(dāng)然，這一切的前提是 join 的關(guān)聯(lián)字段是 a覆醇，并且 t1 表的 a 字段上有索引朵纷。

如果沒有索引時炭臭，再用上圖的執(zhí)行流程時，每次到 t1 去匹配的時候袍辞，就要做一次全表掃描徽缚。這也導(dǎo)致整個過程的時間復(fù)雜度編程了 N * M，這是不可接受的革屠。所以，當(dāng)沒有索引時排宰，MySQL 使用 Block Nested-Loop Join 算法似芝。

Block Nested-Loop Join

Block Nested-Loop Join的算法，簡稱 BNL板甘，它是 MySQL 在被驅(qū)動表上無可用索引時使用的 join 算法党瓮，其具體流程如下所示：

1. 把表 t2 的數(shù)據(jù)讀取當(dāng)前線程的 join_buffer 中，在本篇文章的示例 SQL 沒有在 t2 上做任何條件過濾盐类，所以就是講t2整張表 放入內(nèi)存中寞奸；
2. 掃描表 t1，每取出一行數(shù)據(jù)在跳，就跟 join_buffer 中的數(shù)據(jù)進(jìn)行對比枪萄，滿足 join 條件的，則放入結(jié)果集猫妙。

比如下面這條 SQL

select * from t2 straight_join t1 on (t2.b=t1.b);

這條語句的 explain 結(jié)果如下所示瓷翻。可以看出

可以看出割坠，這次 join 過程對 t1 和 t2 都做了一次全表掃描齐帚，并且將表 t2 中的 500 條數(shù)據(jù)全部放入內(nèi)存 join_buffer 中，并且對于表 t1 中的每一行數(shù)據(jù)彼哼，都要去 join_buffer 中遍歷一遍对妄，都要做 500 次對比，所以一共要進(jìn)行 500 * 10000 次內(nèi)存對比操作敢朱，具體流程如下圖所示剪菱。

主要注意的是，第一步中拴签，并不是將表 t2 中的所有數(shù)據(jù)都放入 join_buffer琅豆，而是根據(jù)具體的 SQL 語句，而放入不同行的數(shù)據(jù)和不同的字段篓吁。比如下面這條 join 語句則只會將表 t2 中符合 b >= 100 的數(shù)據(jù)的 b 字段存入 join_buffer茫因。

select t2.b,t1.b from t2 straight_join t1 on (t2.b=t1.b) where t2.b >= 100;

join_buffer 并不是無限大的，由 join_buffer_size 控制杖剪，默認(rèn)值為 256K冻押。當(dāng)要存入的數(shù)據(jù)過大時驰贷，就只有分段存儲了，整個執(zhí)行過程就變成了：

1. 掃描表 t2洛巢，將符合條件的數(shù)據(jù)行存入 join_buffer括袒，因為其大小有限，存到100行時滿了稿茉，則執(zhí)行第二步锹锰；
2. 掃描表 t1，每取出一行數(shù)據(jù)漓库，就跟 join_buffer 中的數(shù)據(jù)進(jìn)行對比恃慧，滿足 join 條件的，則放入結(jié)果集渺蒿；
3. 清空 join_buffer痢士；
4. 再次執(zhí)行第一步，直到全部數(shù)據(jù)被掃描完茂装，由于 t2 表中有 500行數(shù)據(jù)怠蹂，所以一共重復(fù)了 5次

這個流程體現(xiàn)了該算法名稱中 Block的由來，分塊去執(zhí)行 join 操作少态。因為表 t2 的數(shù)據(jù)被分成了 5 次存入 join_buffer城侧，導(dǎo)致表 t1 要被全表掃描 5次。

如上所示彼妻，和表數(shù)據(jù)可以全部存入 join_buffer 相比赞庶，內(nèi)存判斷的次數(shù)沒有變化，都是兩張表行數(shù)的乘積澳骤，也就是 10000 * 500歧强，但是被驅(qū)動表會被多次掃描，每多存入一次为肮，被驅(qū)動表就要掃描一遍摊册，影響了最終的執(zhí)行效率。

基于上述兩種算法颊艳，我們可以得出下面的結(jié)論茅特，這也是網(wǎng)上大多數(shù)對 MySQL join 語句的規(guī)范。

1. 被驅(qū)動表上有索引棋枕，也就是可以使用Index Nested-Loop Join 算法時白修，可以使用 join 操作。
2. 無論是Index Nested-Loop Join 算法或者 Block Nested-Loop Join 都要使用小表做驅(qū)動表重斑。

因為上述兩個 join 算法的時間復(fù)雜度至少也和涉及表的行數(shù)成一階關(guān)系兵睛，并且要花費大量的內(nèi)存空間，所以阿里開發(fā)者規(guī)范所說的嚴(yán)格禁止三張表以上的 join 操作也是可以理解的了。

但是上述這兩個算法只是 join 的算法之一祖很，還有更加高效的 join 算法笛丙，比如 Hash Join 和 Sorted Merged join〖倨模可惜這兩個算法 MySQL 的主流版本中目前都不提供胚鸯，而 Oracle ，PostgreSQL 和 Spark 則都支持笨鸡，這也是網(wǎng)上吐槽 MySQL 弱爆了的原因(MySQL 8.0 版本支持了 Hash join姜钳，但是8.0目前還不是主流版本)。

其實阿里開發(fā)者規(guī)范也是在從 Oracle 遷移到 MySQL 時形耗，因為 MySQL 的 join 操作性能太差而定下的禁止三張表以上的 join 操作規(guī)定的 哥桥。

Hash Join 算法

Hash Join 是掃描驅(qū)動表，利用 join 的關(guān)聯(lián)字段在內(nèi)存中建立散列表趟脂，然后掃描被驅(qū)動表，每讀出一行數(shù)據(jù)例衍，并從散列表中找到與之對應(yīng)數(shù)據(jù)昔期。它是大數(shù)據(jù)集連接操時的常用方式，適用于驅(qū)動表的數(shù)據(jù)量較小佛玄，可以放入內(nèi)存的場景硼一，它對于沒有索引的大表和并行查詢的場景下能夠提供最好的性能∶吻溃可惜它只適用于等值連接的場景般贼，比如 on a.id = where b.a_id。

還是上述兩張表 join 的語句奥吩，其執(zhí)行過程如下

1. 將驅(qū)動表 t2 中符合條件的數(shù)據(jù)取出哼蛆，對其每行的 join 字段值進(jìn)行 hash 操作，然后存入內(nèi)存中的散列表中霞赫；
2. 遍歷被驅(qū)動表 t1腮介，每取出一行符合條件的數(shù)據(jù)，也對其 join 字段值進(jìn)行hash操作端衰，拿結(jié)果到內(nèi)存的散列表中查找匹配叠洗，如果找到，則成為結(jié)果集的一部分旅东。

可以看出灭抑，該算法和 Block Nested-Loop Join 有類似之處，只不過是將無序的 Join Buffer 改為了散列表 hash table抵代，從而讓數(shù)據(jù)匹配不再需要將 join buffer 中的數(shù)據(jù)全部遍歷一遍腾节，而是直接通過 hash，以接近 O(1) 的時間復(fù)雜度獲得匹配的行，這極大地提高了兩張表的 join 速度禀倔。

不過由于 hash 的特性榄融，該算法只能適用于等值連接的場景，其他的連接場景均無法使用該算法救湖。

Sorted Merge Join 算法

Sort Merge Join 則是先根據(jù) join 的關(guān)聯(lián)字段將兩張表排序(如果已經(jīng)排序好了愧杯，比如字段上有索引則不需要再排序)，然后在對兩張表進(jìn)行一次歸并操作鞋既。如果兩表已經(jīng)被排過序力九，在執(zhí)行排序合并連接時不需要再排序了，這時Merge Join的性能會優(yōu)于Hash Join邑闺。Merge Join可適于于非等值Join（>跌前，<，>=陡舅，<=抵乓，但是不包含!=，也即<>）靶衍。

需要注意的是灾炭，如果連接的字段已經(jīng)有索引，也就說已經(jīng)排好序的話颅眶，可以直接進(jìn)行歸并操作蜈出，但是如果連接的字段沒有索引的話，則它的執(zhí)行過程如下圖所示涛酗。

1. 遍歷表 t2铡原，將符合條件的數(shù)據(jù)讀取出來，按照連接字段 a 的值進(jìn)行排序商叹；
2. 遍歷表 t1燕刻，將符合條件的數(shù)據(jù)讀取出來，也按照連接字段 a 的值進(jìn)行排序剖笙；
3. 將兩個排序好的數(shù)據(jù)進(jìn)行歸并操作酌儒，得出結(jié)果集。

Sorted Merge Join 算法的主要時間消耗在于對兩個表的排序操作枯途，所以如果兩個表已經(jīng)按照連接字段排序過了忌怎，該算法甚至比 Hash Join 算法還要快。在一邊情況下酪夷，該算法是比 Nested Loop Join 算法要快的榴啸。

下面，我們來總結(jié)一下上述三種算法的區(qū)別和優(yōu)缺點晚岭。

對于 Join 操作的理解

講完了 Join 相關(guān)的算法鸥印，我們這里也聊一聊對于 join 操作的業(yè)務(wù)理解。

在業(yè)務(wù)不復(fù)雜的情況下，大多數(shù)join并不是無可替代库说。比如訂單記錄里一般只有訂單用戶的 user_id狂鞋，返回信息時需要取得用戶姓名，可能的實現(xiàn)方案有如下幾種：

1. 一次數(shù)據(jù)庫操作潜的，使用 join 操作骚揍，訂單表和用戶表進(jìn)行 join，連同用戶名一起返回啰挪；
2. 兩次數(shù)據(jù)庫操作信不，分兩次查詢，第一次獲得訂單信息和 user_id亡呵，第二次根據(jù) user_id 取姓名抽活，使用代碼程序進(jìn)行信息合并；
3. 使用冗余用戶名稱或者從 ES 等非關(guān)系數(shù)據(jù)庫中讀取锰什。

上述方案都能解決數(shù)據(jù)聚合的問題下硕，而且基于程序代碼來處理，比數(shù)據(jù)庫 join 更容易調(diào)試和優(yōu)化汁胆，比如取用戶姓名不從數(shù)據(jù)庫中取梭姓，而是先從緩存中查找。

當(dāng)然沦泌， join 操作也不是一無是處糊昙，所以技術(shù)都有其使用場景辛掠，上邊這些方案或者規(guī)則都是互聯(lián)網(wǎng)開發(fā)團(tuán)隊總結(jié)出來的谢谦，適用于高并發(fā)、輕寫重讀萝衩、分布式回挽、業(yè)務(wù)邏輯簡單的情況，這些場景一般對數(shù)據(jù)的一致性要求都不高猩谊，甚至允許臟讀千劈。

但是，在金融銀行或者財務(wù)等企業(yè)應(yīng)用場景牌捷，join 操作則是不可或缺的墙牌，這些應(yīng)用一般都是低并發(fā)、頻繁復(fù)雜數(shù)據(jù)寫入暗甥、CPU密集而非IO密集喜滨，主要業(yè)務(wù)邏輯通過數(shù)據(jù)庫處理甚至包含大量存儲過程、對一致性與完整性要求很高的系統(tǒng)撤防。

最后

感謝大家看到這里虽风，如果本文有什么不足之處，歡迎多多指教；如果你覺得對你有幫助辜膝，請給我點個贊无牵。
也歡迎大家關(guān)注我的公眾號：程序員麥冬，每天更新行業(yè)資訊厂抖！