MySQL中Join的那些事
大家好，我是黎杜，上一期我們聊了Mysql的索引篇，這一期，我們來聊一聊Mysql中的join原理，join用法基本工作過的都會用，不管是left join、right join、inner join語法都是比較簡單的。
但是，join的原理確實博大精深，對于一些傳統it企業，幾乎是一句sql走天下，join了五六個表，當數據量上來的時候，就會變得非常慢，索引對于掌握join的優化還是非常有必要的。
阿里的開發手冊中規定join不能查過三個，有些互聯網是明確規定不能使用join的的明文規定，那么在實際的場景中，我們真的不能使用join嗎?我們就來詳細的聊一聊。
Mysql的join主要涉及到三種算法，分別是Simple Nested-Loop Join、Block Nested-Loop Join、Index Nested-Loop Join，下面我們就來深入的了解這三種算法的原理、區別、效率。
首先，為了測試先準備兩個表作為測試表，并且使用存儲過程初始化一些測試數據，初始化的表結構sql如下所示：
- CREATE TABLE `testa` (
- `id` int(20) NOT NULL AUTO_INCREMENT COMMENT '活動主鍵',
- `col1` int(20) NOT NULL DEFAULT '0' COMMENT '測試字段1',
- `col2` int(20) NOT NULL DEFAULT '0' COMMENT '測試字段2',
- PRIMARY KEY (`id`),
- KEY `col1` (`idx_col1`)
- )ENGINE=InnoDB AUTO_INCREMENT=782 DEFAULT CHARSET=utf8mb4 COMMENT='測試表1';
- CREATE TABLE `testb` (
- `id` int(20) NOT NULL AUTO_INCREMENT COMMENT '活動主鍵',
- `col1` int(20) NOT NULL DEFAULT '0' COMMENT '測試字段1',
- `col2` int(20) NOT NULL DEFAULT '0' COMMENT '測試字段2',
- PRIMARY KEY (`id`),
- KEY `col1` (`idx_col1`)
- ) ENGINE=InnoDB AUTO_INCREMENT=782 DEFAULT CHARSET=utf8mb4 COMMENT='測試表2';
初始化數據：
- CREATE DEFINER = `root` @`localhost` PROCEDURE `init_data` ()
- BEGIN
- DECLARE i INT;
- SET i = 1;
- WHILE ( i <= 100 ) DO
- INSERT INTO testa VALUES ( i, i, i );
- SET i = i + 1;
- END WHILE;
- SET i = 1;
- WHILE ( i <= 2000) DO
- INSERT INTO test2 VALUES ( i, i, i );
- SET i = i + 1;
- END WHILE;
- END
分別初始化testa表為100條數據，testb為2000條數據
Simple Nested-Loop Join
首先，我們執行如下sql：
- select * from testa ta left join testb tb on (ta.col1=tb.col2);
Simple Nested-Loop Join是最簡單也是最粗暴的join方法，上面的sql在testb 的col2字段是沒有加索引的，所以當testa為驅動表，testb為被驅動表時，就會拿著testa的每一行，然后去testb的全表掃描，執行流程如下：
- 從表testa中取出一行數據，記為ta。
- 從ta中取出col1字段去testb中全表掃描查詢。
- 找到testb中滿足情況的數據與ta組成結果集返回。
- 重復執行1-3步驟，直到把testa表的所有數據都取完。
因此掃描的時間復雜度就是100*2000=20W的行數，所以在被驅動表關聯字段沒有添加索引的時候效率就非常的低下。
假如testb是百萬數據以上，那么掃描的時間復雜度就更恐怖了，但是在Mysql中沒有使用這個算法，而是使用了另一種算法Block Nested-Loop Join，目的就是為了優化驅動表沒有索引時的查詢。
Block Nested-Loop Join
還是上面的sql，不過通過加explain關鍵字來查看這條sql的執行計劃：
- explain select * from testa ta left join testb tb on (ta.col1=tb.col2);
可以看到testb依舊是全表掃描，并且在Extra字段中可以看到testb的Using join buffer(hash join)的字樣，在rows中可以看到總掃描的行數是驅動表行數+被驅動表行數，那么這個算法與Simple Nested-Loop Join有什么區別呢?
Block Nested-Loop Join算法中引入了join buffer區域，而join buffer是一塊內存區域，它的大小由join_buffer_size參數大小控制，默認大小是256k：
在執行上面的sql的時候，它會把testa表的數據全部加載到join buffer區域，因為join buffer是內存操作，因此相對于比上面的simple算法要高效，具體的執行流程如下：
- 首先把testa表的所有數據都加在到join buffer里面，這里的所有數據是select后面的testa的字段，因為這里是select *，所以就是加載所有的testa字段。
- 然后遍歷的取testb表中的每一行數據，并且與join buffer里面的數據濟寧對比，符合條件的，就作為結果集返回。
具體的流程圖如下所示：
所以，從上面的執行的步驟來看(假設驅動表的行數為N，被驅動表的行數據為M)，Block Nested-Loop Join的掃描的行數還是驅動表+被驅動表行數(N+M)，在內存中總的比較次數還是驅動表*被驅動表行數(N*M)
上面我們提到join buffer是一塊內存區域，并且有自己的大小，要是join buffer的大小不足夠容納驅動表的數量級怎么辦呢?
答案就是分段，你要是join buffer沒辦法容納驅動表的所有數據，那么就不把所有的數據加載到join buffer里面，先加載一部分，后面再加載另一部分，比如：先加載testa中的80條數據，與testb比較完數據后，清空再加載testa后20條數據，再與testb進行比較。具體執行流程如下：
- 先加載testa中的80條數據到join buffer
- 然后一次遍歷testb的所有數據，與join buffer里面的數據進行比較，符合條件的組成結果集。
- 清空join buffer，再加載testa后面的20條數據。
- 然后一次遍歷testb的所有數據，與join buffer里面的數據進行比較，符合條件的組成結果集并返回。
執行流程圖如下所示：
從上面的結果來看相對于比內存足夠的join buffer來說，分段的join buffer多了一遍全表全表遍歷testb，并且分的段數越多，多掃描驅動表的次數就越多。，性能就越差，所以在某一些場景下，適當的增大join buffer的值，是能夠提高join的效率。
假如驅動表的行數是N，分段參數為K，被驅動表的行數是M，那么總的掃描行數還是N+K*M，而內存比較的次數還是N*M，沒有變。
其中K段數與N的數據量有關，若是N的數據量越大，那么可能K被分成段數就越多，這樣多次重復掃描的被驅動表的次數就越多。
所以在join buffer不夠的情況小，驅動表是越小越好，能夠減少K值，減少重復掃描被驅動表的次數。這也就是為什么提倡小表要作為驅動表的原因。
那么這里提到小表的概念，是不是就是數據量少的就是認為是小表呢?其實不然，小表的真正的還是是實際參與join的數據量，比如以下的兩條sql：
- select * from testa ta left join testb tb on (ta.col1=tb.col2) where tb.id<=20;
- select * from testb tb left join testa ta on (ta.col1=tb.col2) where tb.id<=20;
在第二條sql中，雖然testb驅動表數據量比較大，但是在where條件中實際參與join的行數也就是id小于等于20的數據，完全小于testa的數據量，所以這里選擇以testb作為驅動表是更加的合適。
在實際的開發中Block Nested-Loop Join也是嚴禁被禁止出現的，嚴格要求關聯條件建索引，所以性能最好的就是Index Nested-Loop Join算法。
Index Nested-Loop Join
當我們執行如下sql時：
- select * from testa ta left join testb tb on (ta.col1=tb.col1);
它的執行流程如下：
- 首先取testa表的一行數據。
- 使用上面的行數據的col1字段去testb表進行查詢。
- 在testb找到符合條件的數據行，并與testa的數據行組合作為結果集。
- 重復執行1-3步驟，直到取完testa表的所有數據。
因為testb的col1字段是建立了索引，所以，當使用testa表的字段col1去testb查找的時候，testb走的是col1索引的b+樹的搜索，時間復雜度近似log2M，并且因為是select*，也就是要查找testb的所有字段，所以這里也涉及到回表查詢，因此就變成了2*log2M，若是不懂回表的，可以參考這一篇文章：十萬個為什么，精通Mysql索引
在這個過程中，testa表的掃描行數是全部，所以需要掃描100行，然后testa的每一行都與testb也是一一對應的，所以col1索引查詢掃描的行數也是100行，所以總的掃描行數就是200行。
我們假設驅動表的數據行位N，被驅動表的數據行為M，那么近似的復雜度為：N+N*2*log M，因為驅動表的掃描行數就是N，然后被驅動表因為每一次都對應驅動表的一次，并且一次的時間復雜度就是近似2*log M，所以被驅動表就是N*2*log M。
明顯N的值對于N+N*2*log M的結果值影響更大，所以N越小越好，所以選擇小表作為驅動表是最優選擇。
在一些情況下的優化，假如join的驅動表所需要的字段很少(兩個)，可以建立聯合索引來優化join查詢，并且如果業務允許的話，可以通過冗余字段，減少join的個數提高查詢的效率。
好了，這一期就分享join的原理，以及join一些優化的手段和注意的事項，我們下一期見。
本文轉載自微信公眾號「黎杜編程」，可以通過以下二維碼關注。轉載本文請聯系黎杜編程公眾號。
