小編的世界 優質文選 資料
字體大小:
2020年12月01日 -
:
酷扯兒
《酷扯兒》官方帳號
需要注意的是,在第二步中,根據 a 字段去表t1中查詢時,使用了索引,所以每次掃描只會掃描一行(從explain結果得出,根據不同的案例場景而變化)。
假設驅動表的行數是N,被驅動表的行數是 M。因為在這個 join 語句執行過程中,驅動表是走全表掃描,而被驅動表則使用了索引,並且驅動表中的每一行數據都要去被驅動表中進行索引查詢,所以整個 join 過程的近似複雜度是 N2
log2M。顯然,N 對掃描行數的影響更大,因此這種情況下應該讓小表來做驅動表。
當然,這一切的前提是 join 的關聯字段是 a,並且 t1 表的 a 字段上有索引。
如果沒有索引時,再用上圖的執行流程時,每次到 t1 去匹配的時候,就要做一次全表掃描。這也導致整個過程的時間複雜度編程了 N * M,這是不可接受的。所以,當沒有索引時,MySQL 使用 Block Nested-Loop Join 算法。
Block Nested-Loop Join
Block Nested-Loop Join的算法,簡稱 BNL,它是 MySQL 在被驅動表上無可用索引時使用的 join 算法,其具體流程如下所示:
把表 t2 的數據讀取當前線程的 join_buffer 中,在本篇文章的示例 SQL 沒有在 t2 上做任何條件過濾,所以就是講 t2 整張表 放入內存中;
掃描表 t1,每取出一行數據,就跟 join_buffer 中的數據進行對比,滿足 join 條件的,則放入結果集。
比如下面這條 SQL
select * from t2 straight_join t1 on (t2.b=t1.b);
這條語句的 explain 結果如下所示。可以看出
可以看出,這次 join 過程對 t1 和 t2 都做了一次全表掃描,並且將表 t2 中的 500 條數據全部放入內存 join_buffer 中,並且對於表 t1 中的每一行數據,都要去 join_buffer 中遍曆一遍,都要做 500 次對比,所以一共要進行 500 * 10000 次內存對比操作,具體流程如下圖所示。
主要注意的是,第一步中,並不是將表 t2 中的所有數據都放入 join_buffer,而是根據具體的 SQL 語句,而放入不同行的數據和不同的字段
。比如下面這條 join 語句則只會將表 t2 中符合 b >= 100 的數據的 b 字段存入 join_buffer。
select t2.b,t1.b from t2 straight_join t1 on (t2.b=t1.b) where t2.b >= 100;
join_buffer 並不是無限大的,由 join_buffer_size 控制,默認值為 256K。當要存入的數據過大時,就只有分段存儲了,整個執行過程就變成了:
掃描表 t2,將符合條件的數據行存入 join_buffer,因為其大小有限,存到100行時滿了,則執行第二步;
掃描表 t1,每取出一行數據,就跟 join_buffer 中的數據進行對比,滿足 join 條件的,則放入結果集;
清空 join_buffer;
再次執行第一步,直到全部數據被掃描完,由於 t2 表中有 500行數據,所以一共重複了 5次
這個流程體現了該算法名稱中 Block 的由來,分塊去執行 join 操作。因為表 t2 的數據被分成了 5 次存入 join_buffer,導致表 t1 要被全表掃描 5次。
如上所示,和表數據可以全部存入 join_buffer 相比,內存判斷的次數沒有變化,都是兩張表行數的乘積,也就是 10000 * 500,但是被驅動表會被多次掃描,每多存入一次,被驅動表就要掃描一遍,影響了最終的執行效率。
基於上述兩種算法,我們可以得出下面的結論,這也是網上大多數對 MySQL join 語句的規範。
被驅動表上有索引,也就是可以使用Index Nested-Loop Join 算法時,可以使用 join 操作。
無論是Index Nested-Loop Join 算法或者 Block Nested-Loop Join 都要使用小表做驅動表。
因為上述兩個 join 算法的時間複雜度至少
也和涉及表的行數成一階關系,並且要花費大量的內存空間,所以阿裏開發者規範所說的嚴格禁止三張表以上的 join 操作也是可以理解的了。
但是上述這兩個算法只是 join 的算法之一,還有更加高效的 join 算法,比如 Hash Join 和 Sorted Merged join。可惜這兩個算法 MySQL 的主流版本中目前都不提供,而 Oracle ,PostgreSQL 和 Spark 則都支持,這也是網上吐槽 MySQL 弱爆了的原因
(MySQL 8.0 版本支持了 Hash join,但是8.0目前還不是主流版本)。
其實阿裏開發者規範也是在從 Oracle 遷移到 MySQL 時,因為 MySQL 的 join 操作性能太差而定下的禁止三張表以上的 join 操作規定的 。
Hash Join 算法
Hash Join 是掃描驅動表,利用 join 的關聯字段在內存中建立散列表,然後掃描被驅動表,每讀出一行數據,並從散列表中找到與之對應數據。它是大數據集連接操時的常用方式,適用於驅動表的數據量較小,可以放入內存的場景,它對於沒有索引的大表
和並行查詢的場景下能夠提供最好的性能。可惜它只適用於等值連接的場景,比如 on a.id = where b.a_id。
還是上述兩張表 join 的語句,其執行過程如下
將驅動表 t2 中符合條件的數據取出,對其每行的 join 字段值進行 hash 操作,然後存入內存中的散列表中;
遍曆被驅動表 t1,每取出一行符合條件的數據,也對其 join 字段值進行 hash 操作,拿結果到內存的散列表中查找匹配,如果找到,則成為結果集的一部分。
可以看出,該算法和 Block Nested-Loop Join 有類似之處,只不過是將無序的 Join Buffer 改為了散列表 hash table,從而讓數據匹配不再需要將 join buffer 中的數據全部遍曆一遍,而是直接通過 hash,以接近 O(1) 的時間複雜度獲得匹配的行
,這極大地提高了兩張表的 join 速度。
不過由於 hash 的特性,該算法只能適用於等值連接的場景,其他的連接場景均無法使用該算法。
Sorted Merge Join 算法
Sort Merge Join 則是先根據 join 的關聯字段將兩張表排序(如果已經排序好了,比如字段上有索引則不需要再排序),然後在對兩張表進行一次歸並操作。如果兩表已經被排過序,在執行排序合並連接時不需要再排序了,這時Merge Join的性能會優於Hash Join。Merge Join可適於於非等值Join(>,<,>=,<=,但是不包含!=,也即<>)。
需要注意的是,如果連接的字段已經有索引,也就說已經排好序的話,可以直接進行歸並操作,但是如果連接的字段沒有索引的話,則它的執行過程如下圖所示。
遍曆表 t2,將符合條件的數據讀取出來,按照連接字段 a 的值進行排序;
遍曆表 t1,將符合條件的數據讀取出來,也按照連接字段 a 的值進行排序;
將兩個排序好的數據進行歸並操作,得出結果集。
Sorted Merge Join 算法的主要時間消耗在於對兩個表的排序操作,所以如果兩個表已經按照連接字段排序過了,該算法甚至比 Hash Join 算法還要快。在一邊情況下,該算法是比 Nested Loop Join 算法要快的。
下面,我們來總結一下上述三種算法的區別和優缺點。
對於 Join 操作的理解
講完了 Join 相關的算法,我們這裏也聊一聊對於 join 操作的業務理解。
在業務不複雜的情況下,大多數join並不是無可替代。比如訂單記錄裏一般只有訂單用戶的 user_id,返回信息時需要取得用戶姓名,可能的實現方案有如下幾種:
一次數據庫操作,使用 join 操作,訂單表和用戶表進行 join,連同用戶名一起返回;
兩次數據庫操作,分兩次查詢,第一次獲得訂單信息和 user_id,第二次根據 user_id 取姓名,使用代碼程序進行信息合並;
使用冗餘用戶名稱或者從 ES 等非關系數據庫中讀取。
上述方案都能解決數據聚合的問題,而且基於程序代碼來處理,比數據庫 join 更容易調試和優化,比如取用戶姓名不從數據庫中取,而是先從緩存中查找。
當然, join 操作也不是一無是處,所以技術都有其使用場景,上邊這些方案或者規則都是互聯網開發團隊總結出來的,適用於高並發、輕寫重讀、分布式、業務邏輯簡單的情況,這些場景一般對數據的一致性要求都不高,甚至允許髒讀。
但是,在金融銀行或者財務等企業應用場景,join 操作則是不可或缺的,這些應用一般都是低並發、頻繁複雜數據寫入、CPU密集而非IO密集,主要業務邏輯通過數據庫處理甚至包含大量存儲過程、對一致性與完整性要求很高的系統。