不知不覺的玩了兩年多的MySQL，發(fā)現(xiàn)很多人都說MySQL對比Oracle來說，優(yōu)化器做的比較差，其實(shí)某種程度上來說確實(shí)是這樣，但是畢竟MySQL才到5.7版本，Oracle都已經(jīng)發(fā)展到12c了，今天我就看了看MySQL的連接算法，嗯，現(xiàn)在來說還是不支持Hash Join，只有Nested-Loop Join，那今天就總結(jié)一下我學(xué)習(xí)的心得吧。
Nested-Loop Join基本算法實(shí)現(xiàn)，偽代碼是這樣：
|
1
2
3
4
5
6
7
8
|
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 } }} |
這段代碼很簡單，雖然我也不怎么會(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)表的概念，那么對應(yīng)過來，驅(qū)動(dòng)表就是偽代碼里的t3表，博文里說MySQL會(huì)自動(dòng)選擇結(jié)果集最小的表作為驅(qū)動(dòng)表，作為算法分析，這樣選擇驅(qū)動(dòng)表確實(shí)是消耗最小的辦法。那么這里還提到了，通過縮小驅(qū)動(dòng)表結(jié)果集進(jìn)行連接優(yōu)化，那么根據(jù)這個(gè)算法來看，結(jié)果集較小的驅(qū)動(dòng)表確實(shí)可以使循環(huán)次數(shù)減少。
當(dāng)然了，MySQL自己在這個(gè)算法基礎(chǔ)上，演進(jìn)出了Block Nested-Loop join算法，其實(shí)基本上和上面的算法沒有區(qū)別，偽代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
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)行對比，從而減少循環(huán)次數(shù)，這樣便可以提高效率。官網(wǎng)上有個(gè)example，我有點(diǎn)沒有看明白：如果有10行被緩存到了buffer里，這10行被傳給了內(nèi)層循環(huán)，內(nèi)層循環(huán)的所有行都會(huì)和buffer中的這10行進(jìn)行對比。原文是這樣的：
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í)候，之后再增大也就沒有什么效果了。
在有索引的情況下，MySQL會(huì)嘗試去使用Index Nested-Loop Join算法，在有些情況下，可能Join的列就是沒有索引，那么這時(shí)MySQL的選擇絕對不會(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)在于其對于內(nèi)表的掃描次數(shù)太多，從而導(dǎo)致掃描的記錄太過龐大。Block Nested-Loop Join算法較Simple Nested-Loop Join的改進(jìn)就在于可以減少內(nèi)表的掃描次數(shù)，甚至可以和Hash Join算法一樣，僅需掃描內(nèi)表一次。
