概述
很長一段時間,MySQL 執行 連接 的唯一算法是 嵌套循環算法 ( nested loop algorithm) 的變體 ,但是 嵌套循環算法 在某些場景下非常低效,也是 MySQL 一直被詬病的一個問題。
隨著 MySQL 8.0.18 的發佈,MySQL Server 可以使用哈希連接(hash join),這篇文章將會簡單介紹下哈希連接如何實現,看看在 MySQL 中它是如何工作的,何時使用它,有什麼限制。
哈希連接簡介
什麼是哈希連接?
哈希連接是一種用於關係型數據庫中的連接算法,只能用於有等連接條件的連接中(on a.b = c.b)。它通常比 嵌套循環 算法 更高效(探測端非常非常小除外),尤其是在沒有命中索引的情況下。
簡單來說,哈希連接算法就是先把一張小表加載到內存哈希表裡,然後遍歷大表的數據,逐行去哈希表中匹配符合條件的數據,返回到客戶端。
(哈希表只是示例,方面理解,實際 hash 的 key 是連接的值,value 是數據行鏈表)
通常將 哈希連接 分為兩個階段,構建階段(build phase)和探測階段(probe phase)。在構建階段,先選擇合適的表作為「構建輸入」,構建哈希表,然後再依次遍歷另一個「探測輸入」表記錄去探測哈希表查找符合連接條件的記錄。
以上圖為例,查詢城市對應的省份。我們假設 city 為 構建輸入,在構建階段,服務器構建一個 city 哈希 表 ,遍歷 city 表,將行依次放進 哈希表,鍵為 hash(province_id),值為對應的 城市行。`
在探測階段,服務器開始從 探測輸入(province) 讀取行。對於每一行都使用 hash(province.province_id) 值作為查找鍵探測哈希表以匹配行。
也就是,構建輸入能全部被加載到內存的情況下,僅掃每個探測行一次,使用常數時間查找就可以查找到兩個輸入之間匹配的行。
數據太多不能放入內存怎麼辦?
將 構建輸入 全部加載到內存中無疑是效率最高的,但在有些情況下,內存不足以將整張表加載到內存中,就需要分批來處理。
常見的做法有兩種:
分批加載到內存處理
- 讀取最大內存可以容納的記錄創建哈希表 構建輸入 生成哈希表;
- 遍歷 探測輸入 對這部分哈希表進行一次全量探測;
- 清理掉哈希表重新進行這個流程,直至全部處理完成。
這種方式會導致探測輸入全表被掃描多次。
寫到文件處理
- 當在構建哈希表階段內存用完時,服務器將會把剩餘的構建輸入寫到磁盤上的許多小文件中,小文件塊經過計算可以全部被讀入內存並創建哈希表(避免文件塊太大後續無法加載到內存還需要再次分隔);
- 在探測階段,由於探測行可能與寫入磁盤的構建輸入的某行匹配,所以也需要將探測輸入寫入到磁盤中;
- 探測階段完成後,從磁盤讀取塊文件並加載到內存散列表中,再從探測輸入讀取響應的塊文件並探測匹配項;
- 處理完後,移動到下一對塊文件,直至全部處理完成。
MySQL 中的哈希連接實現
MySQL 會選擇兩個輸入中較小的一個作為構建輸入(以字節計算),在內存足夠的情況下將構建輸入加載到內存處理,不夠的情況下使用寫入文件的方式處理。
可以使用 join_buffer_size 系統變量控制 哈希連接 的內存使用,哈希連接 使用的內存不能超過這個數量,當超過這個數量時,MySQL 將使用文件來處理。
如果內存超過 join_buffer_size,並且文件超過 open_files_limit ,執行可能失敗。
可以使用如下兩個解決方案:
- 增大 join_buffer_size 來避免 哈希連接 溢出到磁盤
- 增大 open_files_limit
MySQL 什麼情況下會使用哈希連接?
在 MySQL 8.0.18 版本中,如果使用一個或多個等連接條件將表連接在一起,並且沒有可用於連接條件的索引,將使用哈希連接。如果索引可用,MySQL 傾向於使用索引查找來支持嵌套循環。
默認情況下,MySQL 會盡可能使用哈希連接 ,可以通過以下兩種方式啟用或關閉:
- 設置全局或 session 變量 (hash_join = on or hash_join = off); SET optimizer_switch="hash_join=off";
- 使用 hints (HASH_JOIN or NO_HASH_JOIN)。
我們將使用以下查詢作為示例:
<code>EXPLAIN FORMAT = treeSELECT city.name AS city_name, province.name AS province_nameFROM city JOIN province ON city.province_id = province.province_id;/<code>
輸出為:
<code>| -> Inner hash join (city.province_id = province.province_id) (cost=1333.82 rows=1329) -> Table scan on city (cost=0.14 rows=391) -> Hash -> Table scan on province (cost=3.65 rows=34)/<code>
哈希連接 也可以用到多個 join 的查詢中,只要存在等值連接,就可以使用哈希連接。
例如以下查詢:
<code>EXPLAIN FORMAT= TREESELECT city.name AS city_name, province.name AS province_name, country.name AS country_nameFROM city JOIN province ON city.province_id = province.province_id AND city.id < 50 JOIN country ON province.province_id = country.id/<code>
輸出為:
<code>| -> Inner hash join (city.province_id = country.id) (cost=23.27 rows=2) -> Filter: (city.id < 50) (cost=5.32 rows=5) -> Index range scan on city using PRIMARY (cost=5.32 rows=49) -> Hash -> Inner hash join (province.province_id = country.id) (cost=4.00 rows=3) -> Table scan on province (cost=0.59 rows=34) -> Hash -> Table scan on country (cost=0.35 rows=1)/<code>
哈希連接也同樣適用於 「笛卡爾積」,即沒有指定查詢條件,如下:
<code>EXPLAIN FORMAT= TREESELECT *FROM city JOIN province;/<code>
輸出為:
<code>| -> Inner hash join (cost=1333.82 rows=13294) -> Table scan on city (cost=1.17 rows=391) -> Hash -> Table scan on province (cost=3.65 rows=34)/<code>
MySQL 什麼情況下不會使用哈希連接?
- 目前 MySQL 哈希連接只支持內連接,反連接、半連接和外連接仍然使用塊嵌套循環執行。
- 如果索引可用,MySQL 會更傾向於使用索引查找來支持嵌套循環;
- 當不存在等值查詢時,會使用嵌套循環。
如下:
<code>EXPLAIN FORMAT=TREESELECT *FROM city JOIN province ON city.province_id < province.province_id;/<code>
輸出為:
<code>|/<code>
如何查看語句執行是否使用哈希連接?
EXPLAIN FORMAT= TREE 在 MySQL 8.0.16 及之後的版本可以使用,TREE 提供了類似於樹的輸出,對查詢處理的描述比傳統格式更加精確,它是唯一顯示 哈希連接 用法的格式。
除此之外,也可以使用 EXPLAIN ANALYZE 查看 哈希連接 信息。
以上基於 MySQL community Server 8.0.18。
閱讀更多 妖精的雜七雜八 的文章