作者：Erik Frøseth 翻譯：管長龍

原文：https://mysqlserverteam.com/hash-join-in-mysql-8/

長期以來，在 MySQL 中執行 join 查詢的只是嵌套循環算法的變體。隨著 MySQL 8.0.18 的發佈，現在可以使用 Hash join 執行 joins。這篇博客文章將介紹它的工作原理，使用時間以及在性能方面與 MySQL 中舊的 join 算法的比較。

什麼是 Hash join？

Hash join 是一種執行 join 的方式，其中哈希表用於查找兩個輸入之間的匹配行（一個輸入是一個或多個表）。它通常比嵌套循環 join 更有效，特別是如果其中一個輸入可以容納在內存中時。為了查看其工作方式，我們將使用以下查詢作為示例：

SELECT given_name, country_nameFROM persons JOIN countries ON persons.country_id = countries.country_id;

① 構建階段

通常 Hash join 分為兩個階段：構建階段和探測階段。

在構建階段，服務使用聯接屬性作為哈希表鍵，構建一個內存中的哈希表，其中存儲來自輸入之一的行。此輸入也稱為構建輸入，讓我們假設將 countries 指定為構建輸入。理想情況下，服務將選擇兩個輸入中較小的一個作為構建輸入（以字節為單位，而不是行數）。

由於 countries.country_id 是屬於構建輸入的聯接條件，因此將其用作哈希表中的鍵。一旦所有行都存儲在哈希表中，就完成了構建階段。

② 探測階段

在探測階段，服務開始從探測輸入（在我們的示例中為 persons ）讀取行。對於每一行，服務都會使用 persons.country_id 中的值作為查找鍵來探測哈希表是否匹配行。對於每個匹配項，將向客戶端發送一個合併的行。最後，服務僅掃描每個輸入一次，使用恆定時間查找來查找兩個輸入之間的匹配行。

假設服務可以將整個構建輸入存儲在內存中，則此方法非常有效。可用的內存量由系統變量 join_buffer_size 控制，可以在運行時進行調整。但是，如果構建輸入大於可用內存，會發生什麼？我們溢出到磁盤上！

③ 溢出到磁盤

在構建階段內存已滿時，服務器會將其餘的構建輸入寫出到磁盤上的多個塊文件中。服務器試圖設置塊的數量，以使最大的塊恰好適合內存（我們很快就會知道為什麼），但每次輸入的塊文件個數嚴格上限是 128。通過計算 join 屬性的哈希值來確定將行寫入哪個塊文件。請注意，在圖示中，使用了與內存構建階段中使用的哈希函數不同的哈希函數。稍後我們將瞭解原因。

在探測階段，服務器會探測哈希表中的匹配行，就像所有內容都適合內存一樣。但是除此之外，一行還可能與寫入磁盤的構建輸入中的一行匹配。因此，來自探測輸入的每一行也被寫入一組塊文件。使用將構建輸入寫入磁盤時使用的哈希函數和公式確定將行寫入哪個塊文件。這樣，我們可以確定兩個輸入之間的匹配行將位於同一對塊文件中。

探測階段完成後，我們開始從磁盤讀取塊文件。通常，服務器使用第一組塊文件作為構建和探測輸入來執行構建和探測階段。我們將構建輸入中的第一個塊文件加載到內存中的哈希表中。這解釋了為什麼我們希望最大的塊恰好適合內存。如果塊文件太大，我們需要將其分成更小的塊。加載構建塊後，我們從探測輸入讀取相應的塊文件，並在哈希表中探測匹配項，就像所有內容都適合內存一樣。處理完第一對塊文件後，我們將移至下一對塊文件，繼續進行直到所有對塊文件都已處理為止。

您現在可能已經猜到了為什麼在將行劃分為塊文件並將行寫入哈希表時，為什麼應該使用兩個不同的哈希函數。如果我們要對兩個操作使用相同的哈希函數，則在將構建塊文件加載到哈希表中時，將得到一個非常糟糕的哈希表，因為同一塊文件中的所有行都將哈希成相同的值。

這麼贊，我該如何使用？

Hash join 默認情況下處於啟用狀態，因此無需執行任何操作即可使用哈希聯接。值得注意的是，Hash join 建立在新的迭代器執行器上，這意味著您必須使用 EXPLAIN FORMAT=tree 來查看是否將使用 Hash join：

mysql> EXPLAIN FORMAT=tree -> SELECT -> given_name, country_name -> FROM -> persons JOIN countries ON persons.country_id = countries.country_id;+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| EXPLAIN |+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| -> Inner hash join (countries.country_id = persons.country_id) (cost=0.70 rows=1) -> Table scan on countries (cost=0.35 rows=1) -> Hash -> Table scan on persons (cost=0.35 rows=1) |+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+1 row in set (0.01 sec)

通常，如果使用一個或多個等聯接條件將表聯接在一起，並且聯接條件沒有索引，則將使用 Hash join。如果索引可用，則 MySQL 傾向於使用帶有索引查找的嵌套循環。

我們引入了一個新的優化器開關，使您可以對任何查詢禁用 Hash join：

mysql> SET optimizer_switch="hash_join=off";Query OK, 0 rows affected (0.00 sec)
mysql> EXPLAIN FORMAT=tree -> SELECT -> given_name, country_name -> FROM -> persons JOIN countries ON persons.country_id = countries.country_id;+----------------------------------------+| EXPLAIN |+----------------------------------------+| |+----------------------------------------+1 row in set (0.00 sec)

禁用 Hash join 後，MySQL 將退回到塊嵌套循環，從而使用舊的執行程序（迭代器執行程序不支持塊嵌套循環）。此開關使比較 Hash join 和塊嵌套循環的性能變得容易。

如果由於構建輸入太大而導致無法容納在內存中並使用磁盤。則可以增加連接緩衝區的大小。與塊嵌套循環相反，Hash join 將遞增地分配內存，這意味著它將永遠不會使用超出其需求的內存。因此，使用 Hash join 時，使用較大的連接緩衝區大小更安全。

性能數據！

我們做了一些基準測試以查看 Hash join 與塊嵌套循環相比如何，結果看起來像這樣：

您可以在此處查看結果的演示。首先，我必須提到在此測試中我們確實禁用了所有索引。這是為了使優化器使用塊嵌套循環和 Hash join 來創建執行計劃，因此您在此處看到的數字不會顯示出對 DBT-3 執行時間的總體改進。進行此測試是為了突出塊嵌套循環和 Hash join 之間的區別。但是我們可以看到，在所有使用 Hash join 的查詢中，Hash join 顯然都優於塊嵌套循環。調整了緩衝池的大小，以便所有數據都在內存中，並且連接緩衝區的大小與默認值（約 250kB）保持不變。顯著的改進是由於以下事實：每次輸入 Hash join 僅掃描一次，並且它使用恆定時間查找來查找兩個表之間的匹配行。

遺憾的是，當前 Hash join 的實現存在一些限制：

MySQL 僅支持內部 Hash join，這意味著反，半和外部聯接仍使用塊嵌套循環執行。

優化器/計劃器使用塊嵌套循環執行連接。但應該更頻繁地使用 Hash join。

我們希望將來消除這兩個限制，但是即使存在這兩個限制，哈希聯接也應使您的查詢運行更快。

閱讀更多 愛可生 的文章

關鍵字: 算法 技術 作者