到底能不能用 join

2021 年 10 月 30 日
筆記
MySQL

互聯網上一直流傳著各大公司的 MySQL 軍規，其中關於 join 的描述，有些公司不推薦使用 join，而有些公司則規定有條件的使用 join, 它們都是教條式的規定，也沒有詳細說其中的原因，這就很容出現只知道這麼用，但是不知道為什麼的情況

那到底能不能使用 join, 什麼情況下適合用join，什麼情況下不適合用 join， join 有哪些使用原則呢？

本文將詳細講述 join 的執行流程、分析 join 的複雜度，並解答上面的幾個常見問題，讓讀者能詳細了解 join 的原理，做到知其然，知其所以然

測試數據準備

為了更好的分析 join 的工作原理，需要準備一些測試數據，我們分別創建 ta 和 tb 兩個表，定義 insert_data 函數，然後往 ta 、 tb 表添加測試數據，具體如下所示：

創建測試表

Create Table: CREATE TABLE `ta` (
  `id` int(11) NOT NULL,
  `a` int(11) NOT NULL,
  `b` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `a` (`a`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8


Create Table: CREATE TABLE `tb` (
  `id` int(11) NOT NULL,
  `a` int(11) NOT NULL,
  `b` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `a` (`a`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

定義插入數據函數

定義一個插入數據的函數，用於往 tb 表中插入數據

delimieter ;;

create procedure insert_data()

begin

    declare i int;
    
    set i=1;
    
    while( i <= 1000 ) do
    
        insert into tb values(i,i,i);
        
        set i=i+1;
        
    end while;
    
end;;

delimiter ;

添加測試數據

調用 insert_data 函數往tb 表插入1000條數據，tb表前100條數據插入到 ta 表中

mysql> call insert_data();

mysql> insert into ta (select * from tb where tb.a <= 100);

簡述

MySQL中join主要用到 Simple nested-loop、 Block nested-loop、Index nested-loop 三種演算法，下面針對這幾種演算法的流程逐一進行分析，在這之前，有幾點需要說明下

本文所有測試都是在 mysql5.7 版本上進行的
由於mysql會對join的連接方式做優化，為了便於分析 join 的執行過程，文中的 sql 語句統一使用我們指定的連接方式執行查詢，關鍵字是 straight_join

Simple nested-loop 演算法

在 MySQL中執行 select * from ta straight_join tb on ta.a = tb.b; ，語句的 explain 的結果如下:

在這個語句中，ta 是驅動表，tb 是被驅動表，由於表 tb 上 b 欄位沒有索引，所以針對 tb 表需要走全表掃描

語句的執行流程如下：

從 ta 表讀取一條數據,記為Da
從 Da 中取出欄位 a 去 tb 表查詢
取出 tb 表滿足條件的數據，跟 Da數據組合成一行，作為結果集返回
接著讀取 ta 表剩下的數據，重複執行步驟1 到步驟3，直到讀取完 ta 表記錄

上面的流程是循環讀取 ta 表記錄，把每一行記錄中的 a欄位值，去 tb 表中查詢滿足條件的記錄，這個過程就類似下面程式碼中的嵌套for循環

for each row in ta matching range 
{
     for each row in tb matching 
     {
        if row satisfies join conditions, send to client
     }
}

性能分析

每讀取一條 ta 表記錄，就需要掃描一次 tb 表的記錄並與記錄中 b 欄位的值進行比較

所以總共掃描了 100 * 1000 = 10 萬行記錄，進行了 10萬次比較操作

可以看出，總的掃描行數和總比較次數跟 ta 和 tb 表總記錄數有關，記錄數越大，總掃描行數和比較次數越大

假如 ta 表和 tb 表總記錄數各增加 10 倍，那麼，總的掃描行數和比較次數會增加 100 倍，這個效率就非常低下了

基於以上原因，MySQL 沒有選擇使用 Simple nested-loop 演算法了，而是使用了 Block nested-loop 演算法

Block nested-loop演算法

Block nested-loop 演算法對 Simple nested-loop 演算法進行了優化，它引入了 join buffer

join buffer 主要用於優化不帶索引條件的 join 查詢，它會快取連接過程中的用到的欄位，對於減少掃描次數和比較次數很有幫助

join_buffer_size 參數可以控制 join_buffer 的大小，MySQL 默認的

join_buffer_size 是 256K，可以通過 select @@join_buffer_size

查詢目前設置的大小

現以執行 select * from ta straight_join tb on ta.a = tb.b; 語句為例來說說明 Block nested-loop的執行流程

把 ta 表所有記錄讀入 join buffer 中，join buffer 只快取連接過程中必須的數據，這裡使用了 select * ，所以，ta 表的記錄的所有欄位都會放入 join buffer 中
掃描 tb 表，讀取每一行記錄，跟 join buffer 中的數據對比，滿足條件的數據，將會作為結果集返回

性能分析

整個過程中，讀取 ta 表所有記錄，讀取 tb 表所有記錄，相當於掃描了一遍 ta 表和 tb表，所以掃描總行數是 100 + 1000 = 1100 行

逐行遍歷 tb 表，與 join buffer 中的數據比較，由於 join buffer 是無序的，所以，對於 tb 表每一條記錄，都需要在 join buffer 中比較 100 次，因此總的比較次數是 1000 * 100 = 10萬次

和 Simple nested-loop 比起來，由於有 join buffer 的幫助，Block nested loop 總掃描行數減少了很多,總共掃描了 100 + 1000 = 1100 行

雖然兩者總比較次數都是 10 萬次，但是，Block nested loop 的比較是在記憶體中的 join buffer 中進行的，所以，速度上應該會快很多，性能相對也好一些

如果驅動表 ta 數據行數是 M ，被驅動表 tb 數據行數是 N ，總的掃描行數為 M + N , 總的比較次數為 M * N , 所以整個執行過程 近似的複雜度是：M + N + M * N

上述複雜度公式中，M 和 N 調換的話，複雜度不變，所以，這時候選擇小表還是大表作為驅動表都一樣

join buffer 大小不夠用的問題

上面 Block nested loop 執行流程中，第一步是把整個ta表數據全部讀入 join buffer 中，這裡由於 ta 表數據少，join buffer 可以放得下全部的數據

如果 join buffer 的大小不足以快取 ta表所有數據，該怎麼辦呢？這時候的執行流程又是怎樣的呢？

答案是：join buffer 分段快取 ta 表數據，處理完之後，清空快取，然後再快取 ta 表剩下的數據

現假設 join buffer 只能放得下 60 行 ta 表記錄，執行流程就變成了：

遍歷 ta 表，順序讀取 60 條記錄放入 join buffer 中，此時，join buffer 滿了
遍歷 tb 表，取出得每一行，跟 join buffer 中得數據比較，組合滿足條件得數據，作為結果集返回
清空 join buffer
接著上次的位置繼續順序掃描 ta 表，把剩下得 40行數據讀入 join buffer 中，緊接著執行第 2 步到第 4 步，直到讀取完 ta 表記錄

性能分析

由於 ta 表是分兩次讀入 join buffer 的，所以需要掃描兩次 tb 表，所以總掃描行數是 100 + 1000 * 2 = 2100 行

總的比較次數依然保持不變，是：(60 + 40) * 1000 = 10萬次

從上面的結果可以看出，join buffer 分段快取的性能要比一次快取全部驅動表必需數據的方式要差一些，也就是說，join buffer 分的段數越多，性能相對越差，在驅動表數量行數不變的情況下，分段數的取決於 join_buffer_size 參數的大小，這個參數越大，分段數或越小，反之越大， 所以有些地方建議通過調大 join_buffer_size 參數來提升 join 查詢速度的方法，原因也在於此

如果驅動表 ta 數據行數是 M ，被驅動表 tb 數據行數是 N, join buffer 分段數是 K ，則總掃描行數為 M + K * N , 總的比較次數為 M * N , 所以整個執行過程 近似的複雜度是: M + K * N + M * N

顯然 K 越小，複雜度越小，性能就越好，K 的最小值是 1 ，也就是驅動表中所必需的欄位能全部快取到 join buffer 中

而 K 是與驅動表數據行數 M 和 join_buffer_size 參數相關的，後者通常不會經常變化，所以 M 越小， K 就越小，K 越小，複雜度越小，性能就越好，K 的最小值是 1 ，也就是驅動表中所必需的欄位能全部快取到 join buffer 中

因此，選擇小表作為驅動表，查詢性能更好

Index nested-loop演算法

分析完上面兩種演算法，接著來看下 Index nested-loop 演算法的執行流程

在 MySQL 中執行 select * from ta straight_join tb on ta.a = tb.a;, 語句的 explain 結果如下:

上述結果中，被驅動表 tb 的欄位 a 上有索引，所以，連接的過程中能用上索引，它的執行流程是:

讀取一行 ta 表記錄, 記為 Da
從 Da 中取出 a 欄位去 tb 表查詢
讀取 tb 表中滿足條件的記錄，和 Da 組合，作為結果集返回
重複執行步驟1 到步驟 3，直到讀取完 ta 表的記錄

性能分析

上面的流程是遍歷 ta 表，然後從讀出的每行記錄中取出 a 的值去 tb 表查詢

由於 tb 表的 a 欄位上有索引，所以查詢 tb 表記錄的時候，走的是 B+ 樹的查詢

我們準備的測試數據中 ta 表 a 欄位和tb表 a 欄位是一一對應的，因此對於 ta 表的一行記錄，在 tb 表中需要做兩次 B+ 樹查詢，一次是普通索引樹的查詢，一次是回表查詢

總的掃描行數是: 100 + 100 = 200 行( tb 表的兩次B+樹查詢是由掃描一次表導致的，所以這裡把tb表總掃描次數當作100次)

總的比較次數是: 100 次

如果驅動表 ta 數據行數是 M ，被驅動表 tb 數據行數是 N, 對於驅動表的一行數據，被驅動表需要先查詢 a 索引的 B+ 樹，再查詢主鍵索引 B+ 樹，所以被驅動表查詢一行的複雜度是：2 * log2N

總掃描行數為 M + M * 2 * log2N , 總的比較次數為 M , 所以整個執行過程 近似的複雜度是: M + M * 2 * log2N + M = 2 * M * ( 1 + log2N )

近似複雜度公式中，變數是 M 和 N , 很顯然，M 對結果影響更大，M 表示的是驅動表的數據行數，因此，選擇小表作為驅動表能顯著降低複雜度，提升查詢速度

結果分析

上面分析了 Simple nested loop 、 Block nested loop、Index nested loop 這三種演算法的執行流程，並詳細分析了每種演算法的複雜度，根據分析的結果就可以回答本文開頭的幾個問題了

能不能使用join

如果能用上被驅動表上的索引，即可以用上 Index nested loop 演算法的話，是可以使用 join 的
如果使用 Block nested loop 演算法的話，掃描行數和比較次數比較多，會佔用大量的系統資源，特別是對於大表來說，查詢速度和系統性能是無法接受的，所以，這種情況下，能不用join就不用join了

如果 explain 結果的 Extra 欄位包含 ‘ Using join buffer (Block Nested Loop) ‘ 字元串的話，表示使用了 ‘ Block nested loop ‘ 演算法

join 使用原則

在分析 Index nested loop 的複雜度之後，得出一個結論: 選擇小表作為驅動表，查詢性能更好

對於 Block nested loop 的複雜度分兩種情況

join buffer 沒有分段, 此時不論選擇小表還是大表作為驅動表，複雜度都一樣
join buffer 分段了，此時選擇小表作為驅動表，複雜度更低，查詢性能更好，相比join buffer 沒有分段，實際的場景中，join buffer 分段的情況應該更多

綜合來講: 使用 join 應該選擇小表作為驅動表

如何選擇 “小” 表

上面 join 使用原則 中講到選擇小表作為驅動表，這裡的小表並不是指表數據行數少，而是指參與join的表，按照查詢條件分別得到結果集，結果集小的表作為驅動表

比如：有以下兩個 SQL 語句

語句1：select * from ta straight_join tb on ta.b = tb.b where tb.id <= 20;
語句2：select * from tb straight_join ta on ta.b = tb.b where tb.id <= 20;

ta 表和 tb表么一行數據大小是一樣的，語句1 使用 ta 作為驅動表，需要把 ta 表所有行數據(100行)放入 join buffer 中，但是語句2 使用 tb 作為驅動表，只需要把 tb表前20行數據放入 join buffer，也即 tb 表只有20行數據參與join, 這麼一比較，tb 表查詢的結果集更小，所以應該選擇數據行數更多但是查詢的結果集更小的 tb 表作為驅動表

小結

本文詳細討論了 Simple nested loop 、 Block nested loop、Index nested loop 這三種演算法，根據演算法的執行流程定量的分析了各個演算法的複雜度，再根據複雜度分析了 join 常見的一些問題，更多關於 join 的介紹請參考 MySQL 官網

Tags: MySQL