MySQL8.0 新特性 Hash Join

来源:https://www.cnblogs.com/cchust/archive/2019/11/30/11961851.html

概述&背景 MySQL一直被人詬病沒有實現HashJoin,最新發佈的8.0.18已經帶上了這個功能,令人欣喜。有時候在想,MySQL為什麼一直不支持HashJoin呢?我想可能是因為MySQL多用於簡單的OLTP場景,並且在互聯網應用居多,需求沒那麼緊急。另一方面可能是因為以前完全靠社區,這種演進 ...


概述&背景

MySQL一直被人詬病沒有實現HashJoin,最新發佈的8.0.18已經帶上了這個功能,令人欣喜。有時候在想,MySQL為什麼一直不支持HashJoin呢?我想可能是因為MySQL多用於簡單的OLTP場景,並且在互聯網應用居多,需求沒那麼緊急。另一方面可能是因為以前完全靠社區,這種演進速度畢竟有限,Oracle收購MySQL後,MySQL的發版演進速度明顯加快了很多。

HashJoin本身演算法實現並不複雜,要說複雜,可能是優化器配套選擇執行計劃時,是否選擇HashJoin,選擇外表,內表可能更複雜一點。不管怎樣現在已經有了HashJoin,優化器在選擇Join演算法時又多了一個選擇。MySQL本著實用主義,相信這個功能增強也回應了一些質疑,有些功能不是沒有能力做好,而是有它的優先順序。

在8.0.18之前,MySQL只支持NestLoopJoin演算法,最簡單的就是Simple NestLoop Join,MySQL針對這個演算法做了若幹優化,實現了Block NestLoop Join,Index NestLoop Join和Batched Key Access等,有了這些優化,在一定程度上能緩解對HashJoin的迫切程度。下文會單獨拿一個章節講MySQL的這些Join優化,下麵先講HashJoin。

Hash Join演算法

NestLoopJoin演算法簡單來說,就是雙重迴圈,遍歷外表(驅動表),對於外表的每一行記錄,然後遍歷內表,然後判斷join條件是否符合,進而確定是否將記錄吐出給上一個執行節點。從演算法角度來說,這是一個M*N的複雜度。HashJoin是針對equal-join場景的優化,基本思想是,將外表數據load到記憶體,並建立hash表,這樣只需要遍歷一遍內表,就可以完成join操作,輸出匹配的記錄。如果數據能全部load到記憶體當然好,邏輯也簡單,一般稱這種join為CHJ(Classic Hash Join),之前MariaDB就已經實現了這種HashJoin演算法。如果數據不能全部load到記憶體,就需要分批load進記憶體,然後分批join,下麵具體介紹這幾種join演算法的實現。

In-Memory Join(CHJ)

HashJoin一般包括兩個過程,創建hash表的build過程和探測hash表的probe過程。

1).build phase

遍歷外表,以join條件為key,查詢需要的列作為value創建hash表。這裡涉及到一個選擇外表的依據,主要是評估參與join的兩個表(結果集)的大小來判斷,誰小就選擇誰,這樣有限的記憶體更容易放下hash表。

2).probe phase

hash表build完成後,然後逐行遍歷內表,對於內表的每個記錄,對join條件計算hash值,併在hash表中查找,如果匹配,則輸出,否則跳過。所有內表記錄遍歷完,則整個過程就結束了。過程參照下圖,來源於MySQL官方博客

    

左側是build過程,右側是probe過程,country_id是equal_join條件,countries表是外表,persons表是內表。

On-Disk Hash Join

CHJ的限制條件在於,要求記憶體能裝下整個外表。在MySQL中,Join可以使用的記憶體通過參數join_buffer_size控制。如果join需要的記憶體超出了join_buffer_size,那麼CHJ將無能為力,只能對外表分成若幹段,每個分段逐一進行build過程,然後遍歷內表對每個分段再進行一次probe過程。假設外表分成了N片,那麼將掃描內表N次。這種方式當然是比較弱的。在MySQL8.0中,如果join需要記憶體超過了join_buffer_size,build階段會首先利用hash算將外表進行分區,並產生臨時分片寫到磁碟上;然後在probe階段,對於內表使用同樣的hash演算法進行分區。由於使用分片hash函數相同,那麼key相同(join條件相同)必然在同一個分片編號中。接下來,再對外表和內表中相同分片編號的數據進行CHJ的過程,所有分片的CHJ做完,整個join過程就結束了。這種演算法的代價是,對外表和內表分別進行了兩次讀IO,一次寫IO。相對於之之前需要N次掃描內表IO,現在的處理方式更好。

                     

                                   

左上側圖是外表的分片過程,右上側圖是內表的分片過程,最下麵的圖是對分片進行build+probe過程。

Grace Hash Join

主流的資料庫Oracle,SQLServer,PostgreSQL早就支持了HashJoin。Join演算法都類似,這裡介紹下Oracle使用的Grace Hash Join演算法。其實整個過程與MySQL的HashJoin類似,主要有一點區別。當出現join_buffer_size不足時,MySQL會對外表進行分片,然後再進行CHJ過程。但是,極端情況下,如果數據分佈不均勻,導致大量的數據hash後都分佈在一個分桶中,導致分片後,join_buffer_size仍然不夠,MySQL的處理方式是一次讀分片讀若幹記錄構建hash表,然後probe對應的外表分片。處理完一批後,清理hash表,重覆上述過程,直到這個分片的所有數據處理完為止。這個過程與CHJ在join_buffer_size不足時,處理邏輯相同。

GraceHash在遇到這種情況時,會繼續分片進行二次Hash,直到記憶體足夠放下一個hash表為止。但是,這裡仍然有極端情況,如果輸入join條件都相同,那麼無論進行多少次Hash,都沒法分開,那麼這個時候GraceHashJoin也退化成和MySQL的處理方式一樣。

hybrid hash join

與GraceHashJoin的區別在於,如果緩存能緩存足夠多的分片數據,會儘量緩存,那麼就不必像GraceHash那樣,嚴格地將所有分片都先讀進記憶體,然後寫到外存,然後再讀進記憶體去走build過程。這個是在記憶體相對於分片比較充裕的情況下的一種優化,目的是為了減少磁碟的讀寫IO。目前Oceanbase的HashJoin採用的是這種join方式。

MySQL-Join演算法優化

在MySQL8.0.18之前,也就是在很長一段時間內,MySQL資料庫並沒有HashJoin,主要的Join演算法是NestLoopJoin。SimpleNestLoopJoin顯然是很低效的,對內表需要進行N次全表掃描,實際複雜度是N*M,N是外表的記錄數目,M是記錄數,代表一次掃描內表的代價。為此,MySQL針對SimpleNestLoopJoin做了若幹優化,下麵貼的圖片均來自網路

BlockNestLoopJoin(BNLJ)

MySQL採用了批量技術,即一次利用join_buffer_size緩存足夠多的記錄,每次遍歷內表時,每條內表記錄與這一批數據進行條件判斷,這樣就減少了掃描內表的次數,如果內表比較大,間接就緩解了IO的讀壓力。

                                                  

IndexNestLoopJoin(INLJ)

如果我們能對內表的join條件建立索引,那麼對於外表的每條記錄,無需再進行全表掃描內表,只需要一次Btree-Lookup即可,整體時間複雜度降低為N*O(logM)。對比HashJoin,對於外表每條記錄,HashJoin是一次HashTable的search,當然HashTable也有build時間,還需要處理記憶體不足的情況,不一定比INLJ好。

Batched Key Access

IndexNestLoopJoin利用join條件的索引,通過Btree-Lookup去匹配減少了遍歷內表的代價。如果join條件是非主鍵列,那麼意味著大量的回表和隨機IO。BKA優化的做法是,將滿足條件的一批數據按主鍵排序,這樣回表時,從主鍵的角度來說就相對有序,緩解隨機IO的代價。BKA實際上是利用了MRR特性(MultiRangeRead),訪問數據之前,先將主鍵排序,然後再訪問。主鍵排序的緩存大小通過參數read_rnd_buffer_size控制。

      

總結

MySQL8.0以後,Server層代碼做了大量的重構,雖然優化器相對於Oracle還有很大差距,但一直在進步。HashJoin的支持使得MySQL優化器有更多選擇,SQL的執行路徑也能做到更優,尤其是對於等值join的場景。雖然MySQL之前對於Join做過若幹優化,比如NBLJ,INLJ以及BKA等,但這些代替不了HashJoin的作用。一個好用的資料庫就應該具備豐富的基礎能力,利用優化器分析出合適場景,然後拿出對應的基礎能力以最高效的方式響應請求。

參考文檔

https://en.wikipedia.org/wiki/Hash_join

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

https://dev.mysql.com/worklog/task/?id=2241

https://www.cnblogs.com/qixinbo/p/10524142.html

https://zhuanlan.zhihu.com/p/35040231


您的分享是我們最大的動力!

更多相關文章
  • 在項目中,寫的sql主要以查詢為主,但是數據量一大,就會突出sql性能優化的重要性。其實在數據量2000W以內,可以考慮索引,但超過2000W了,就要考慮分庫分表這些了。本文主要記錄在實際項目中,一個需要查詢很慢的sql的優化過程,如果有更好的方案,請在下麵留言交流。 很多文章都有關於sql優化的方 ...
  • 4個特性 原子性:一個事務中的所有操作,要麼全部完成,要麼全部不完成,不會結束在中間某個環節。事務在執行過程中發生錯誤,會被回滾(rollback)到事務開始前的狀態 一致性:在事務開始前和事務結束以後,資料庫的完整性沒有被破壞。例如A和B之間的轉賬,不論轉多少次,轉多少,兩個人的總金額是不會變的 ...
  • 問題描述:今天在虛擬機下進行startup的操作,但是沒有起來,系統報錯:ORA-00845: MEMORY_TARGET not supported on this system 1.startup啟動,MEMORY_TARGET啟動不起來在系統中,Oracle總共可以使用的共用記憶體大小,這個參數 ...
  • MySQL資料庫備份和恢復 [toc] 備份恢復概述 為什麼要備份 災難恢復:硬體故障、軟體故障、自然災害、黑客攻擊、誤操作測試等數據丟失場景 備份註意要點 能容忍最多丟失多少數據 恢複數據需要在多長時間內完成 需要恢復哪些數據 還原要點 做還原測試,用於測試備份的可用性 還原演練 備份類型: 完全 ...
  • 問題描述:本來配置好的DG第二天重啟之後,發現主備庫數據不能同步,在主庫上執行日誌切換以及創建表操作都傳不到備庫上,造成這種錯誤的原因是主庫實例斷掉後造成備庫日誌與主庫無法實時接收 主庫:orcl 備庫:orclstd 說明:啟動之前主備庫都要開啟監聽,否則接收不到數據 1.在主庫上:啟動主庫,切換 ...
  • [toc] 一、準備工作 先來一段偽代碼,首先你能看懂麽? 繼續做以下的前期準備工作: 新建一個測試資料庫TestDB; 創建測試表table1和table2; 插入測試數據; 準備工作做完以後,table1和table2看起來應該像下麵這樣: 準備SQL邏輯查詢測試語句 Oracle SQL語句執 ...
  • https://www.jianshu.com/p/faa5e852b76b https://bbs.csdn.net/topics/70039385 https://www.runoob.com/sqlite/sqlite-insert.html http://c.biancheng.net/vi ...
  • 基本語法如下 sqlite> select * from tb_user; sqlite> select userid,username from tb_user; 格式化的查詢輸出 sqlite> .header on sqlite> .mode column sqlite> select * f ...
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...