深入瞭解MySQL中的join語句演演算法（優化方法介紹）

一、join語句演演算法

建立兩個表t1和t2

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

CREATE DEFINER=`root`@`%` PROCEDURE `idata`()
BEGIN
	declare i int;
  set i=1;
  while(i<=1000)do
    insert into t2 values(i, i, i);
    set i=i+1;
  end while;
END

create table t1 like t2;
insert into t1 (select * from t2 where id<=100);

這兩個表都有一個主鍵索引id和一個索引a，欄位b上無索引。儲存過程idata()往表t2裡插入了1000行資料，在表t1裡插入的是100行資料

1、Index Nested-Loop Join

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

如果直接使用join語句，MySQL優化器可能會選擇表t1或t2作為驅動表，通過straight_join讓MySQL使用固定的連線方式執行查詢，在這個語句裡，t1是驅動表，t2是被驅動表

被驅動表t2的欄位a上有索引，join過程用上了這個索引，因此這個語句的執行流程是這樣的：

1.從表t1中讀入一行資料R

2.從資料行R中，取出a欄位到表t2裡去查詢

3.取出表t2中滿足條件的行，跟R組成一行，作為結果集的一部分

4.重複執行步驟1到3，直到表t1的末尾迴圈結束

這個過程可以用上被驅動表的索引，稱之為Index Nested-Loop Join，簡稱NLJ

在這個流程裡：

1.對驅動表t1做了全表掃描，這個過程需要掃描100行

2.而對於每一行R，根據a欄位去表t2查詢，走的是樹搜尋過程。由於我們構造的資料都是一一對應的，因此每次的搜尋過程都只掃描一行，也是總共掃描100行

3.所以，整個執行流程，總掃描行數是200

假設不使用join，只能用單表查詢：

1.執行select * from t1，查出表t1的所有資料，這裡有100行

2.迴圈遍歷這100行資料：

• 從每一行R取出欄位a的值$R.a
• 執行select * from t2 where a=$R.a
• 把返回的結果和R構成結果集的一行

這個查詢過程，也是掃描了200行，但是總共執行了101條語句，比直接join多了100次互動。使用者端還要自己拼接SQL語句和結果。這麼做還不如直接join好

在可以使用被驅動表的索引的情況下：

• 使用join語句，效能比強行拆成多個單表執行SQL語句的效能要好
• 如果使用join語句的話，需要讓小表做驅動表

2、Simple Nested-Loop Join

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

由於表t2的欄位b上沒有索引，因此每次到t2去匹配的時候，就要做一次全表掃描。這個演演算法叫做Simple Nested-Loop Join

這樣算來，這個SQL請求就要掃描表t2多達100次，總共掃描100*100=10萬行

MySQL沒有使用這個Simple Nested-Loop Join演演算法，而是使用了另一個叫作Block Nested-Loop Join的演演算法，簡稱BNL

3、Block Nested-Loop Join

被驅動表上沒有可用的索引，演演算法的流程如下：

1.把表t1的資料讀入執行緒記憶體join_buffer中，由於這個語句中寫的是select *，因此是把整個表t1放入了記憶體

2.掃描表t2，把表t2中的每一行取出來，跟join_buffer中的資料作比對，滿足join條件的，作為結果集的一部分返回

在這個過程中，對錶t1和表t2都做了一次全表掃描，因此總的掃描行數是1100。由於join_buffer是以無序陣列的方式組織的，因此對錶t2中的每一行，都要做100次判斷，總共需要在記憶體中做的判斷次數是100*1000=10萬次

使用Simple Nested-Loop Join演演算法進行查詢，掃描行數也是10萬行。因此，從時間複雜度上來說，這兩個演演算法是一樣的。但是，Block Nested-Loop Join演演算法的這10萬次判斷是記憶體操作，速度上會快很多，效能也更好

假設小表的行數是N，大表的行數是M，那麼在這個演演算法裡：

1）兩個表都做一次全表掃描，所以總的掃描行數是M + N

2）記憶體中的判斷次數是M ∗ N

這時候選擇大表還是小表做驅動表，執行耗時是一樣的

join_buffer的大小是由引數join_buffer_size設定的，預設值是256k。如果放不下表t1的所有資料話，策略很簡單，就是分段放

1）掃描表t1，順序讀取資料行放入join_buffer中，假設放到第88行join_buffer滿了

2）掃描表t2，把t2中的每一行取出來，跟join_buffer中的資料做對比，滿足join條件的，作為結果集的一部分返回

3）清空join_buffer

4）繼續掃描表t1，順序讀取最後的12行放入join_buffer中，繼續執行第2步

由於表t1被分成了兩次放入join_buffer中，導致表t2會被掃描兩次。雖然分成兩次放入join_buffer，但是判斷等值條件的此時還是不變的

假設，驅動表的資料行數是N，需要分成K段才能完成演演算法流程，被驅動表的資料行數是M 。這裡的K不是常數，N越大K 就會越大，因此把K表示為λ ∗ N ，λ的取值範圍是(0,1)。所以，在這個演演算法的執行過程中：

1.掃描行數是N + λ ∗ N ∗ M

2.記憶體判斷N ∗ M

考慮到掃描行數，N 小一些，整個算式的結果會更小。所以應該讓小表當驅動表

4、能不能使用join語句？

1.如果可以使用Index Nested-Loop Join演演算法，也就是說可以用上被驅動表上的索引，其實是沒問題的

2.如果使用Block Nested-Loop Join演演算法，掃描行數就會過多。尤其是在大表上的join操作，這樣可能要掃描被驅動表很多次，會佔用大量的系統資源。所以這種join儘量不要用

5、如果使用join，應該選擇大表做驅動表還是選擇小表做驅動表

1.如果是Index Nested-Loop Join演演算法，應該選擇小表做驅動表

2.如果是Block Nested-Loop Join演演算法：

• 在join_buffer_size足夠大的時候，是一樣的
• 在join_buffer_size不夠大的時候，應該選擇小表做驅動表

在決定哪個表做驅動表的時候，應該是兩個表按照各自的條件過濾，過濾完成以後，計算引數join的各個欄位的總資料量，資料量小的那個表，就是小表，應該作為驅動表

二、join語句優化

建立兩個表t1、t2

create table t1(id int primary key, a int, b int, index(a));
create table t2 like t1;

CREATE DEFINER = CURRENT_USER PROCEDURE `idata`()
BEGIN
	declare i int;
  set i=1;
  while(i<=1000)do
    insert into t1 values(i, 1001-i, i);
    set i=i+1;
  end while;
  
  set i=1;
  while(i<=1000000)do
    insert into t2 values(i, i, i);
    set i=i+1;
  end while;

END;

在表t1中，插入了1000行資料，每一行的a=1001-id的值。也就是說，表t1中欄位a是逆序的。同時，在表t2中插入了100萬行資料

1、Multi-Range Read優化

Multi-Range Read（MRR）優化主要的目的是儘量使用順序讀盤

select * from t1 where a>=1 and a<=100;

主鍵索引是一棵B+樹，在這棵樹上，每次只能根據一個主鍵id查到一行資料。因此，回表是一行行搜尋主鍵索引的

如果隨著a的值遞增順序查詢的話，id的值就變成隨機的，那麼就會出現隨機存取，效能相對較差

因為大多數的資料都是按照主鍵遞增順序插入得到的，所以如果按照主鍵的遞增順序查詢，對磁碟的讀比較接近順序讀，能夠提升讀效能

這就是MRR優化的設計思路，語句的執行流程如下：

1.根據索引a，定位到滿足條件的記錄，將id值放入read_rnd_buffer中

2.將read_rnd_buffer中的id進行遞增排序

3.排序後的id陣列，依次到主鍵id索引中查記錄，並作為結果返回

read_rnd_buffer的大小是由read_rnd_buffer_size引數控制的。如果步驟1中，read_rnd_buffer放滿了，就會先執行完步驟2和3，然後清空read_rnd_buffer。之後繼續找索引a的下個記錄，並繼續迴圈

如果想要穩定地使用MRR優化的話，需要設定set optimizer_switch="mrr_cost_based=off"

explain結果中，Extra欄位多了Using MRR，表示的是用上了MRR優化。由於在read_rnd_buffer中按照id做了排序，所以最後得到的結果也是按照主鍵id遞增順序的

MRR能夠提升效能的核心在於，這條查詢語句在索引a上做的是一個範圍查詢，可以得到足夠多的主鍵id。這樣通過排序以後，再去主鍵索引查資料，才能體現出順序性的優勢

2、Batched Key Access

MySQL5.6引入了Batched Key Access（BKA）演演算法。這個BKA演演算法是對NLJ演演算法的優化

NLJ演演算法流程圖：

NLJ演演算法執行的邏輯是從驅動表t1，一行行地取出a的值，再到被驅動表t2去做join

BKA演演算法流程圖：

BKA演演算法執行的邏輯是把表t1的資料取出來一部分，先放到一個join_buffer，一起傳給表t2。在join_buffer中只會放入查詢需要的欄位，如果join_buffer放不下所有資料，就會將資料分成多段執行上圖的流程

如果想要使用BKA優化演演算法的話，執行SQL語句之前，先設定

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

其中前兩個引數的作用是啟用MRR，原因是BKA演演算法的優化要依賴與MRR

3、BNL演演算法的效能問題

InnoDB對Buffer Pool的LRU演演算法做了優化，即：第一次從磁碟讀入記憶體的資料頁，會先放在old區域。如果1秒之後這個資料頁不再被存取了，就不會被移動到LRU連結串列頭部，這樣對Buffer Pool的命中率影響就不大

如果一個使用BNL演演算法的join語句，多次掃描一個冷表，而且這個語句執行時間超過1秒，就會在再次掃描冷表的時候，把冷表的資料頁移到LRU連結串列頭部。這種情況對應的，是冷表的資料量小於整個Buffer Pool的3/8，能夠完全放入old區域的情況

如果這個冷表很大，就會出現另外一種情況：業務正常存取的資料頁，沒有機會進入young區域。

由於優化機制的存在，一個正常存取的資料頁，要進入young區域，需要隔1秒後再次被存取到。但是，由於join語句在迴圈讀磁碟和淘汰記憶體頁，進入old區域的資料頁，很可能在1秒之內就被淘汰了。這樣就會導致MySQL範例的Buffer Pool在這段時間內，young區域的資料頁沒有被合理地淘汰

BNL演演算法對系統的影響主要包括三個方面：

1.可能會多次掃描被驅動表，佔用磁碟IO資源

2.判斷join條件需要執行$M\ast N$次對比，如果是大表就會佔用非常多的CPU資源

3.可能會導致Buffer Pool的熱資料被淘汰，影響記憶體命中率

4、BNL轉BKA

一些情況下，我們可以直接在被驅動表上建索引，這時就可以直接轉成BKA演演算法了

如果碰到一些不適合在被驅動表上建索引的情況，可以考慮使用臨時表。大致思路如下：

select * from t1 join t2 on (t1.b=t2.b) where t2.b>=1 and t2.b<=2000;

1）把表t2中滿足條件的資料放在臨時表tmp_t中

2）為了讓join使用BKA演演算法，給臨時表tmp_t的欄位b加上索引

3）讓表t1和tmp_t做join操作

SQL語句寫法如下：

create temporary table temp_t(id int primary key, a int, b int, index(b))engine=innodb;insert into temp_t select * from t2 where b>=1 and b<=2000;select * from t1 join temp_t on (t1.b=temp_t.b);

5、擴充套件hash join

MySQL的優化器和執行器不支援雜湊join，可以自己實現在業務端，實現流程大致如下：

1.select * from t1;取得表t1的全部1000行資料，在業務端存入一個hash結構

2.select * from t2 where b>=1 and b<=2000;獲取表t2中滿足條件的2000行資料

3.把這2000行資料，一行一行地取到業務端，到hash結構的資料表中尋找匹配的資料。滿足匹配的條件的這行資料，就作為結果集的一行

【相關推薦：】

以上就是深入瞭解MySQL中的join語句演演算法（優化方法介紹）的詳細內容，更多請關注TW511.COM其它相關文章！