MySQL中Nested-Loop Join算法小結

更新時間：2015年12月10日 11:37:33 投稿：hebedich

數據庫中JOIN操作的實現主要有三種：嵌套循環(huán)連接（Nested Loop Join），歸并連接（Merge Join）和散列連接或者哈稀連接（Hash Join）。其中嵌套循環(huán)連接又視情況又有兩種變形：塊嵌套循環(huán)連接和索引嵌套循環(huán)連接。

不知不覺的玩了兩年多的MySQL，發(fā)現很多人都說MySQL對比Oracle來說，優(yōu)化器做的比較差，其實某種程度上來說確實是這樣，但是畢竟MySQL才到5.7版本，Oracle都已經發(fā)展到12c了，今天我就看了看MySQL的連接算法，嗯，現在來說還是不支持Hash Join，只有Nested-Loop Join，那今天就總結一下我學習的心得吧。

Nested-Loop Join基本算法實現，偽代碼是這樣：

for each row in t1 matching range {
 for each row in t2 matching reference key {
  for each row in t3 {
   if row satisfies join conditions,
   send to client
  }
 }
}

這段代碼很簡單，雖然我也不怎么會寫代碼，但是我還是看得懂的。這里假設有三張表，t1, t2, t3，這段代碼，分別會展現出explain計劃里的range, ref和ALL，表現在SQL執(zhí)行計劃層里，t3就會進行一次全表掃描，我今天在這個地方看到了一個很妖的優(yōu)化SQL方法，Straight-join：http://hidba.ga/2014/09/26/join-query-in-mysql/，其中提到了驅動表的概念，那么對應過來，驅動表就是偽代碼里的t3表，博文里說MySQL會自動選擇結果集最小的表作為驅動表，作為算法分析，這樣選擇驅動表確實是消耗最小的辦法。那么這里還提到了，通過縮小驅動表結果集進行連接優(yōu)化，那么根據這個算法來看，結果集較小的驅動表確實可以使循環(huán)次數減少。

當然了，MySQL自己在這個算法基礎上，演進出了Block Nested-Loop join算法，其實基本上和上面的算法沒有區(qū)別，偽代碼如下：

for each row in t1 matching range {
 for each row in t2 matching reference key {
  store used columns from t1, t2 in join buffer
  if buffer is full {
   for each row in t3 {
    for each t1, t2 combination in join buffer {
     if row satisfies join conditions,
     send to client
    }
   }
   empty buffer
  }
 }
}

if buffer is not empty {
 for each row in t3 {
  for each t1, t2 combination in join buffer {
   if row satisfies join conditions,
   send to client
  }
 }
}

這個算法，將外層循環(huán)的數據緩存在join buffer中，內層循環(huán)中的表回合buffer中的數據進行對比，從而減少循環(huán)次數，這樣便可以提高效率。官網上有個example，我有點沒有看明白：如果有10行被緩存到了buffer里，這10行被傳給了內層循環(huán)，內層循環(huán)的所有行都會和buffer中的這10行進行對比。原文是這樣的：

For example, if 10 rows are read into a buffer and the buffer is passed to the next inner loop, each row read in the inner loop can be compared against all 10 rows in the buffer
如果S指的是t1, t2組合在緩存中的大小，C是這些組合在buffer中的數量，那么t3表被掃描的次數應該是：

(S * C)/join_buffer_size + 1

根據這個算式，join_buffer_size越大，掃描的次數越小，如果join_buffer_size到了能緩存所有之前的行組合，那么這時就是性能最好的時候，之后再增大也就沒有什么效果了。

在有索引的情況下，MySQL會嘗試去使用Index Nested-Loop Join算法，在有些情況下，可能Join的列就是沒有索引，那么這時MySQL的選擇絕對不會是最先介紹的Simple Nested-Loop Join算法，因為那個算法太粗暴，不忍直視。數據量大些的復雜SQL估計幾年都可能跑不出結果，如果你不信，那就是too young too simple?；蛘逫nside君可以給你些SQL跑跑看。

Simple Nested-Loop Join算法的缺點在于其對于內表的掃描次數太多，從而導致掃描的記錄太過龐大。Block Nested-Loop Join算法較Simple Nested-Loop Join的改進就在于可以減少內表的掃描次數，甚至可以和Hash Join算法一樣，僅需掃描內表一次。

您可能感興趣的文章: