MySQL decode，mysql nest loop偽代碼_Nested Loop Join

我們都知道SQL的join關聯表的使用方式，但是這次聊的是實現join的算法，join有三種算法，分別是Nested Loop Join，Hash join，Sort Merge Join。

MySQL官方文檔中提到，MySQL只支持Nested Loop Join這一種join algorithm

MySQL decode。MySQL resolves all joins using a nested-loop join method. This means that MySQL reads a row from the first table, and then finds a matching row in the second table, the third table, and so on. explain-output

所以本篇只聊Nested Loop Join。

NLJ是通過兩層循環，用第一張表做Outter Loop，第二張表做Inner Loop，Outter Loop的每一條記錄跟Inner Loop的記錄作比較，符合條件的就輸出。而NLJ又有3種細分的算法：

nested loops、1、Simple Nested Loop Join(SNLJ)

// 偽代碼

for (r in R) {

MySQL decimal，for (s in S) {

if (r satisfy condition s) {

output ;

MySQL case when？}

}

}

SNLJ就是兩層循環全量掃描連接的兩張表，得到符合條件的兩條記錄則輸出，這也就是讓兩張表做笛卡爾積，比較次數是R * S，是比較暴力的算法，會比較耗時。

2、Index Nested Loop Join(INLJ)

// 偽代碼

for (r in R) {

for (si in SIndex) {

if (r satisfy condition si) {

output ;

}

}

}

INLJ是在SNLJ的基礎上做了優化，通過連接條件確定可用的索引，在Inner Loop中掃描索引而不去掃描數據本身，從而提高Inner Loop的效率。 而INLJ也有缺點，就是如果掃描的索引是非聚簇索引，并且需要訪問非索引的數據，會產生一個回表讀取數據的操作，這就多了一次隨機的I/O操作。

3、Block Nested Loop Join(BNLJ)

一般情況下，MySQL優化器在索引可用的情況下，會優先選擇使用INLJ算法，但是在無索引可用，或者判斷full scan可能比使用索引更快的情況下，還是不會選擇使用過于粗暴的SNLJ算法。 這里就出現了BNLJ算法了，BNLJ在SNLJ的基礎上使用了join buffer，會提前讀取Inner Loop所需要的記錄到buffer中，以提高Inner Loop的效率。

// 偽代碼

for (r in R) {

for (sbu in SBuffer) {

if (r satisfy condition sbu) {

output ;

}

}

}

MySQL中控制join buffer大小的參數名是join_buffer_size。

We only store the used columns in the join buffer, not the whole rows.
join-buffer-size

根據MySQL手冊中的說法，join_buffer_size緩沖的是被使用到的列。

算法比較(外表大小R，內表大小S)：

\algorithm

comparison\

Simple Nested Loop Join

Index Nested Loop Join

Block Nested Loop Join

外表掃描次數

1

1

1

內表掃描次數

R

0

讀取記錄次數

R + R * S

R + RS_Matches

比較次數

R * S

R * IndexHeight

R * S

回表次數

0

RS_Matches

0

在MySQL5.6中，對INLJ的回表操作進行了優化，增加了Batched Key Access Join(批量索引訪問的表關聯方式，這樣翻譯可以不。。。)和Multi Range Read(mrr，多范圍讀取)特性，在join操作中緩存所需要的數據的rowid，再批量去獲取其數據，把I/O從多次零散的操作優化為更少次數批量的操作，提高效率。