不知不覺的玩了兩年多的MySQL,發現很多人都說MySQL對比Oracle來說,優化器做的比較差,其實某種程度上來說確實是這樣,但是畢竟MySQL才到5.7版本,Oracle都已經發展到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執行計劃層裡,t3就會進行一次全表掃描,我今天在這個地方看到了一個很妖的優化SQL方法,Straight-join:http://hidba.ga/2014/09/26/join-query-in-mysql/,其中提到了驅動表的概念,那麼對應過來,驅動表就是偽代碼裡的t3表,博文裡說MySQL會自動選擇結果集最小的表作為驅動表,作為算法分析,這樣選擇驅動表確實是消耗最小的辦法。那麼這裡還提到了,通過縮小驅動表結果集進行連接優化,那麼根據這個算法來看,結果集較小的驅動表確實可以使循環次數減少。
當然了,MySQL自己在這個算法基礎上,演進出了Block Nested-Loop join算法,其實基本上和上面的算法沒有區別,偽代碼如下:
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 } } }
這個算法,將外層循環的數據緩存在join buffer中,內層循環中的表回合buffer中的數據進行對比,從而減少循環次數,這樣便可以提高效率。官網上有個example,我有點沒有看明白:如果有10行被緩存到了buffer裡,這10行被傳給了內層循環,內層循環的所有行都會和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。或者Inside君可以給你些SQL跑跑看。
Simple Nested-Loop Join算法的缺點在於其對於內表的掃描次數太多,從而導致掃描的記錄太過龐大。Block Nested-Loop Join算法較Simple Nested-Loop Join的改進就在於可以減少內表的掃描次數,甚至可以和Hash Join算法一樣,僅需掃描內表一次。