快捷導(dǎo)航

MySQL中Nested-Loop Join算法小結(jié)

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

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

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

Nested-Loop Join基本算法實(shí)現(xiàn)，偽代碼是這樣：

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
  }
 }
}

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

當(dāng)然了，MySQL自己在這個(gè)算法基礎(chǔ)上，演進(jìn)出了Block Nested-Loop join算法，其實(shí)基本上和上面的算法沒(méi)有區(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
  }
 }
}

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

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中的數(shù)量，那么t3表被掃描的次數(shù)應(yīng)該是：

(S * C)/join_buffer_size + 1

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

在有索引的情況下，MySQL會(huì)嘗試去使用Index Nested-Loop Join算法，在有些情況下，可能Join的列就是沒(méi)有索引，那么這時(shí)MySQL的選擇絕對(duì)不會(huì)是最先介紹的Simple Nested-Loop Join算法，因?yàn)槟莻€(gè)算法太粗暴，不忍直視。數(shù)據(jù)量大些的復(fù)雜SQL估計(jì)幾年都可能跑不出結(jié)果，如果你不信，那就是too young too simple。或者Inside君可以給你些SQL跑跑看。

Simple Nested-Loop Join算法的缺點(diǎn)在于其對(duì)于內(nèi)表的掃描次數(shù)太多，從而導(dǎo)致掃描的記錄太過(guò)龐大。Block Nested-Loop Join算法較Simple Nested-Loop Join的改進(jìn)就在于可以減少內(nèi)表的掃描次數(shù)，甚至可以和Hash Join算法一樣，僅需掃描內(nèi)表一次。

您可能感興趣的文章: