這一篇文章就來介紹一下關聯查詢的優化，文章有點長，請耐心看完，有問題歡迎討論指正。

1 關聯查詢的算法特性總結

要想弄懂關聯查詢的優化，就必須先知道關聯查詢相關的算法：

2 Simple Nested-Loop Join算法

圖片

循環驅動表中的每一行

再到被驅動表找到滿足關聯條件的記錄

因為關聯字段沒索引，所以在被驅動表里的查詢需要全表掃描

這種方法邏輯簡單，但是效率很差

比如驅動表數據量是 m，被驅動表數據量是 n，則掃描行數為 m * n

當然，好在，MySQL也沒有采用這種算法，即使關聯字段沒索引，也會采用Block Nested-Loop Join或者Hash Join，等下會細說。

3 Index Nested-Loop Join算法

剛才我們說的是關聯字段沒索引的情況，假如關聯字段有索引，就會采用Index Nested-Loop Join算法（一般簡寫成：NLJ）

圖片

一次一行循環地從第一張表（稱為驅動表）中讀取行，在這行數據中取到關聯字段，根據關聯字段在另一張表（被驅動表）里，通過索引匹配，取出滿足條件的行，然后取出兩張表的結果合集。

為了方便理解，我們會結合實驗進行講解，先來創建測試表并寫入測試數據：

use martin; 
drop table if exists t1; 
CREATE TABLE `t1` (
`id` int NOT NULL auto_increment,
`a` int DEFAULT NULL,
`b` int DEFAULT NULL,
`create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '記錄創建時間',
`update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP
COMMENT '記錄更新時間',
PRIMARY KEY (`id`),
KEY `idx_a` (`a`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;


drop procedure if exists insert_t1; 


delimiter ;;
create procedure insert_t1()
begin
declare i int; 
set i=1;
while(i<=10000)do
insert into t1(a,b) values(i, i); 
set i=i+1; 
end while;
end;;
delimiter ; 
call insert_t1(); 


drop table if exists t2; 
create table t2 like t1; 
insert into t2 select * from t1 limit 100;

我們來看一個例子：

explain select * from t1 inner join t2 on t1.a = t2.a;

Tips：表 t1 和表 t2 中的 a 字段都有索引。

執行計劃如下：

圖片

從執行計劃中可以看到這些信息：

驅動表是 t2，被驅動表是 t1。原因是：explain 分析 join 語句時，在第一行的就是驅動表；選擇 t2 做驅動表的原因：如果沒固定連接方式（比如沒加 straight_join）,優化器會優先選擇小表做驅動表。所以使用 inner join 時，前面的表并不一定就是驅動表。

使用了 NLJ。原因是：一般 join 語句中，如果執行計劃 Extra 中未出現 Using join buffer （***）；則表示使用的 join 算法是 NLJ。

4 Block Nested-Loop Join算法

如果被驅動表的關聯字段沒索引，在MySQL 8.0.20版本之前，就會使用 Block Nested-Loop Join(簡稱：BNL)

圖片

Block Nested-Loop Join(BNL) 算法的思想是：把驅動表的數據讀入到 join_buffer 中，然后掃描被驅動表，把被驅動表每一行取出來跟 join_buffer 中的數據做對比，如果滿足 join 條件，則返回結果給客戶端。

我們一起看看下面這條 SQL 語句：

select * from t1 inner join t2 on t1.b = t2.b;

Tips：表 t1 和表 t2 中的 b 字段都沒有索引

在 MySQL 5.7 版本下的執行計劃如下：

圖片

在 Extra 發現 Using join buffer (Block Nested Loop)，這個就說明該關聯查詢使用的是 BNL 算法。

在 MySQL 8.0.25 版本下的執行計劃如下：

圖片

在 Extra 發現 Using join buffer (hash join)，因為前面提到，從 MySQL 8.0.20 開始，哈希連接替換了塊嵌套循環。

5 Hash Join算法

從 MySQL 8.0.20 開始，MySQL 不再使用 Block Nested-Loop Join 算法，并且在以前使用 Block Nested-Loop Join 算法的所有情況下都使用 Hash Join 優化。

圖片

核心思想是將驅動表的數據加載到內存中構建哈希表

然后逐行讀取被驅動表的數據，并通過哈希函數將連接條件的列的值映射為哈希值，去之前構建的Hash表查找匹配的記錄

一旦在Hash表中找到匹配的記錄，對這些記錄進行一一比較，得出最終的Join結果

跟Block Nested-Loop Join算法類似，但是不需要將被驅動表的數據塊寫入內存或磁盤，更少的IO以及更節省資源

6 Batched Key Access算法

在學了 NLJ 和 BNL 算法后，你是否有個疑問，如果把 NLJ 與 BNL 兩種算法的一些優秀的思想結合，是否可行呢？

比如 NLJ 的關鍵思想是：被驅動表的關聯字段有索引。

而 BNL 的關鍵思想是：把驅動表的數據批量提交一部分放到 join_buffer 中。

從 MySQL 5.6 開始，確實出現了這種集 NLJ 和 BNL 兩種算法優點于一體的新算法：Batched Key Access(BKA)。

圖片

其原理是：

將驅動表中相關列批量放入 join_buffer 中

批量將關聯字段的值發送到 Multi-Range Read(MRR) 接口

MRR 通過接收到的值，根據其對應的主鍵 ID 進行排序，然后再進行數據的讀取和操作

返回結果給客戶端。

7 補充下MRR相關知識

當表很大并且沒有存儲在緩存中時，使用輔助索引上的范圍掃描讀取行可能導致對表有很多隨機訪問。

而 Multi-Range Read 優化的設計思路是：查詢輔助索引時，對查詢結果先按照主鍵進行排序，并按照主鍵排序后的順序，進行順序查找，從而減少隨機訪問磁盤的次數。

使用 MRR 時，explain 輸出的 Extra 列顯示的是 Using MRR。

控制MRR的參數

optimizer_switch 中 mrr_cost_based 參數的值會影響 MRR。

如果 mrr_cost_based=on，表示優化器嘗試在使用和不使用 MRR 之間進行基于成本的選擇。

如果 mrr_cost_based=off，表示一直使用 MRR。

更多 MRR 信息請參考官方手冊：https://dev.mysql.com/doc/refman/8.0/en/mrr-optimization.html。

8 BKA開啟

先來看下這條SQL的執行計劃：

explain select * from t1 inner join t2 on t1.a = t2.a;

圖片

下面嘗試開啟 BKA ：

set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

這里對上面幾個參數做下解釋：

• mrr=on 開啟 mrr
• mrr_cost_based=off 不需要優化器基于成本考慮使用還是不使用 MRR，也就是一直使用 MRR
• batched_key_access=on 開啟 BKA

然后再看 sql1 的執行計劃：

explain select * from t1 inner join t2 on t1.a = t2.a;

圖片

在 Extra 字段中發現有 Using join buffer (Batched Key Access)，表示確實變成了 BKA 算法。

9 優化關聯查詢

扯了這么多，我們就來講一下：究竟怎樣優化關聯查詢：

關聯字段添加索引

通過上面的內容，我們知道了 BNL、NLJ 和 BKA 的原理，因此讓 BNL（Block Nested-Loop Join）或者Hash Join變成 NLJ （Index Nested-Loop Join）或者 BKA（Batched Key Access），可以提高 join 的效率。我們來看下面的例子

我們構造出兩個算法對于的例子：

Block Nested-Loop Join 的例子：

select * from t1 join t2 on t1.b= t2.b;

需要 0.08 秒。

Index Nested-Loop Join 的例子：

select * from t1 join t2 on t1.a= t2.a;

只需要 0.01 秒。

再對比一下兩條 SQL 的執行計劃：

圖片

前者掃描的行數是 100 和 9963。

對比執行時間和執行計劃，再結合在本節開始講解的兩種算法的執行流程，很明顯 Index Nested-Loop Join 效率更高。

因此建議在被驅動表的關聯字段上添加索引，讓 BNL或者Hash Join變成 NLJ 或者 BKA ，可明顯優化關聯查詢。

選擇小表作為驅動表

從上面幾種Join算法，也能看出來，驅動表需要全表掃描，再存放在內存中

如果小表是驅動表，那遍歷的行也會更少。

來舉個例子，看下大小表做驅動表執行計劃的對比：

我們來看下以 t2 為驅動表的 SQL：

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

這里使用 straight_join 可以固定連接方式，讓前面的表為驅動表。

再看下以 t1 為驅動表的 SQL：

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

我們對比下兩條 SQL 的執行計劃：

圖片

明顯前者掃描的行數少（注意關注 explain 結果的 rows 列），所以建議小表驅動大表。

當然，如果是普通的join語句，一般不需要我們去處理，優化器默認也會選擇小表做為驅動表。

數據集較大可以采用BKA優化

BKA算法采用批量處理機制，利用索引快速定位匹配記錄，適合大型數據集的Join操作

版本升級

前面也提到了，如果被驅動表的關聯字段沒索引，在MySQL 8.0.20版本之前，就會使用 Block Nested-Loop Join(簡稱：BNL)，

從 MySQL 8.0.20 開始，MySQL 不再使用 Block Nested-Loop Join 算法，并且在以前使用 Block Nested-Loop Join 算法的所有情況下都使用 Hash Join 優化。

相對于Block Nested-Loop Join算法，Hash Join不需要將被驅動表的數據塊寫入內存或磁盤，使用更少的IO以及更節省資源。

所以，假如有條件，可以升級到8.0.20之后的版本。