這一篇文章就來介紹一下關(guān)聯(lián)查詢的優(yōu)化，文章有點(diǎn)長，請耐心看完，有問題歡迎討論指正。

1 關(guān)聯(lián)查詢的算法特性總結(jié)

要想弄懂關(guān)聯(lián)查詢的優(yōu)化，就必須先知道關(guān)聯(lián)查詢相關(guān)的算法：

2 Simple Nested-Loop Join算法

圖片

循環(huán)驅(qū)動(dòng)表中的每一行

再到被驅(qū)動(dòng)表找到滿足關(guān)聯(lián)條件的記錄

因?yàn)殛P(guān)聯(lián)字段沒索引，所以在被驅(qū)動(dòng)表里的查詢需要全表掃描

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

比如驅(qū)動(dòng)表數(shù)據(jù)量是 m，被驅(qū)動(dòng)表數(shù)據(jù)量是 n，則掃描行數(shù)為 m * n

當(dāng)然，好在，MySQL也沒有采用這種算法，即使關(guān)聯(lián)字段沒索引，也會(huì)采用Block Nested-Loop Join或者Hash Join，等下會(huì)細(xì)說。

3 Index Nested-Loop Join算法

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

圖片

一次一行循環(huán)地從第一張表（稱為驅(qū)動(dòng)表）中讀取行，在這行數(shù)據(jù)中取到關(guān)聯(lián)字段，根據(jù)關(guān)聯(lián)字段在另一張表（被驅(qū)動(dòng)表）里，通過索引匹配，取出滿足條件的行，然后取出兩張表的結(jié)果合集。

為了方便理解，我們會(huì)結(jié)合實(shí)驗(yàn)進(jìn)行講解，先來創(chuàng)建測試表并寫入測試數(shù)據(jù)：

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 '記錄創(chuàng)建時(shí)間',
`update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP
COMMENT '記錄更新時(shí)間',
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;

我們來看一個(gè)例子：

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

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

執(zhí)行計(jì)劃如下：

圖片

從執(zhí)行計(jì)劃中可以看到這些信息：

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

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

4 Block Nested-Loop Join算法

如果被驅(qū)動(dòng)表的關(guān)聯(lián)字段沒索引，在MySQL 8.0.20版本之前，就會(huì)使用 Block Nested-Loop Join(簡稱：BNL)

圖片

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

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

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

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

在 MySQL 5.7 版本下的執(zhí)行計(jì)劃如下：

圖片

在 Extra 發(fā)現(xiàn) Using join buffer (Block Nested Loop)，這個(gè)就說明該關(guān)聯(lián)查詢使用的是 BNL 算法。

在 MySQL 8.0.25 版本下的執(zhí)行計(jì)劃如下：

圖片

在 Extra 發(fā)現(xiàn) Using join buffer (hash join)，因?yàn)榍懊嫣岬剑瑥?MySQL 8.0.20 開始，哈希連接替換了塊嵌套循環(huán)。

5 Hash Join算法

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

圖片

核心思想是將驅(qū)動(dòng)表的數(shù)據(jù)加載到內(nèi)存中構(gòu)建哈希表

然后逐行讀取被驅(qū)動(dòng)表的數(shù)據(jù)，并通過哈希函數(shù)將連接條件的列的值映射為哈希值，去之前構(gòu)建的Hash表查找匹配的記錄

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

跟Block Nested-Loop Join算法類似，但是不需要將被驅(qū)動(dòng)表的數(shù)據(jù)塊寫入內(nèi)存或磁盤，更少的IO以及更節(jié)省資源

6 Batched Key Access算法

在學(xué)了 NLJ 和 BNL 算法后，你是否有個(gè)疑問，如果把 NLJ 與 BNL 兩種算法的一些優(yōu)秀的思想結(jié)合，是否可行呢？

比如 NLJ 的關(guān)鍵思想是：被驅(qū)動(dòng)表的關(guān)聯(lián)字段有索引。

而 BNL 的關(guān)鍵思想是：把驅(qū)動(dòng)表的數(shù)據(jù)批量提交一部分放到 join_buffer 中。

從 MySQL 5.6 開始，確實(shí)出現(xiàn)了這種集 NLJ 和 BNL 兩種算法優(yōu)點(diǎn)于一體的新算法：Batched Key Access(BKA)。

圖片

其原理是：

將驅(qū)動(dòng)表中相關(guān)列批量放入 join_buffer 中

批量將關(guān)聯(lián)字段的值發(fā)送到 Multi-Range Read(MRR) 接口

MRR 通過接收到的值，根據(jù)其對應(yīng)的主鍵 ID 進(jìn)行排序，然后再進(jìn)行數(shù)據(jù)的讀取和操作

返回結(jié)果給客戶端。

7 補(bǔ)充下MRR相關(guān)知識(shí)

當(dāng)表很大并且沒有存儲(chǔ)在緩存中時(shí)，使用輔助索引上的范圍掃描讀取行可能導(dǎo)致對表有很多隨機(jī)訪問。

而 Multi-Range Read 優(yōu)化的設(shè)計(jì)思路是：查詢輔助索引時(shí)，對查詢結(jié)果先按照主鍵進(jìn)行排序，并按照主鍵排序后的順序，進(jìn)行順序查找，從而減少隨機(jī)訪問磁盤的次數(shù)。

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

控制MRR的參數(shù)

optimizer_switch 中 mrr_cost_based 參數(shù)的值會(huì)影響 MRR。

如果 mrr_cost_based=on，表示優(yōu)化器嘗試在使用和不使用 MRR 之間進(jìn)行基于成本的選擇。

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

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

8 BKA開啟

先來看下這條SQL的執(zhí)行計(jì)劃：

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';

這里對上面幾個(gè)參數(shù)做下解釋：

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

然后再看 sql1 的執(zhí)行計(jì)劃：

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

圖片

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

9 優(yōu)化關(guān)聯(lián)查詢

扯了這么多，我們就來講一下：究竟怎樣優(yōu)化關(guān)聯(lián)查詢：

關(guān)聯(lián)字段添加索引

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

我們構(gòu)造出兩個(gè)算法對于的例子：

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 的執(zhí)行計(jì)劃：

圖片

前者掃描的行數(shù)是 100 和 9963。

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

因此建議在被驅(qū)動(dòng)表的關(guān)聯(lián)字段上添加索引，讓 BNL或者Hash Join變成 NLJ 或者 BKA ，可明顯優(yōu)化關(guān)聯(lián)查詢。

選擇小表作為驅(qū)動(dòng)表

從上面幾種Join算法，也能看出來，驅(qū)動(dòng)表需要全表掃描，再存放在內(nèi)存中

如果小表是驅(qū)動(dòng)表，那遍歷的行也會(huì)更少。

來舉個(gè)例子，看下大小表做驅(qū)動(dòng)表執(zhí)行計(jì)劃的對比：

我們來看下以 t2 為驅(qū)動(dòng)表的 SQL：

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

這里使用 straight_join 可以固定連接方式，讓前面的表為驅(qū)動(dòng)表。

再看下以 t1 為驅(qū)動(dòng)表的 SQL：

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

我們對比下兩條 SQL 的執(zhí)行計(jì)劃：

圖片

明顯前者掃描的行數(shù)少（注意關(guān)注 explain 結(jié)果的 rows 列），所以建議小表驅(qū)動(dòng)大表。

當(dāng)然，如果是普通的join語句，一般不需要我們?nèi)ヌ幚?，?yōu)化器默認(rèn)也會(huì)選擇小表做為驅(qū)動(dòng)表。

數(shù)據(jù)集較大可以采用BKA優(yōu)化

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

版本升級

前面也提到了，如果被驅(qū)動(dòng)表的關(guān)聯(lián)字段沒索引，在MySQL 8.0.20版本之前，就會(huì)使用 Block Nested-Loop Join(簡稱：BNL)，

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

相對于Block Nested-Loop Join算法，Hash Join不需要將被驅(qū)動(dòng)表的數(shù)據(jù)塊寫入內(nèi)存或磁盤，使用更少的IO以及更節(jié)省資源。

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