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 ...
一周排行
  • 1. 泛型Generic 1.1 引入泛型:延遲聲明 泛型方法聲明時,並未寫死類型,在調用的時候再指定類型。 延遲聲明:推遲一切可以推遲的。 1.2 如何聲明和使用泛型 泛型方法:方法名稱後面加上尖括弧,裡面是類型參數 類型參數實際上就是一個類型T聲明,方法就可以用這個類型T了。 如下所示: pub ...
  • 本筆記摘抄自:https://www.cnblogs.com/PatrickLiu/p/7903617.html,記錄一下學習過程以備後續查用。 一、引言 今天我們要講行為型設計模式的第三個模式--迭代器模式,先從名字上來看。迭代是遍歷的意思,迭代器可以理解為是遍歷某某的工具,遍歷什麼呢?在軟 件設 ...
  • 本筆記摘抄自:https://www.cnblogs.com/PatrickLiu/p/7928521.html,記錄一下學習過程以備後續查用。 一、引言 今天我們要講行為型設計模式的第四個模式--觀察者模式,先從名字上來看。觀察者模式可以理解為既然有“觀察者”,那肯定就有“被觀察者”了。“觀察者” ...
  • 先看核心代碼: public List<DataEntity> SearchShopSalesReport(DateTimeOffset? dateFrom, DateTimeOffset? dateTo,string groupBy) { var query = data.DataEntity / ...
  • 首先新建一個項目,名稱叫Caliburn.Micro.ActionConvertions 然後刪掉MainWindow.xaml 然後去app.xaml刪掉StartupUri這行代碼 其次,安裝Caliburn.Micro,Caliburn.Micro.Core,這兩個Nuget包,如下圖 然後新 ...
  • 一文帶你瞭解 C DLR 的世界 在很久之前,我寫了一片文章 "dynamic結合匿名類型 匿名對象傳參" ,裡面我以為DLR內部是用反射實現的。因為那時候是心中想當然的認為只有反射能夠在運行時解析對象的成員信息並調用成員方法。後來也是因為其他的事一直都沒有回過頭來把這一節知識給補上,正所謂亡羊補牢 ...
  • ​ 在C#8.0中,針對介面引入了一項新特性,就是可以指定預設實現,方便對已有實現進行擴展,也對面向Android和Swift的Api進行互操作提供了可能性。下麵我們來看看該特性的具體規則與實現。 一、主要應用場景: 在不破壞影響已有實現的情況下,可以添加新成員。這解決了在第三方已經大量使用了的介面 ...
  • 前言 通常在應用程式開發到正式上線,在這個過程中我們會分為多個階段,通常會有 開發、測試、以及正式環境等。每個環境的參數配置我們會使用不同的參數,因此呢,在ASP.NET Core中就提供了相關的環境API,方便我們更好的去做這些事情。 環境 ASP.NET Core使用ASPNETCORE_ENV ...
  • 擱置了幾天,工作忙的一塌糊塗,今天終於抽空來繼續看看MVC的知識。先來看看MVC的路由是如何處理的。以下為替代的路由: app.UseEndpoints(endpoints => { endpoints.MapControllerRoute( name: "default", pattern: "{ ...
  • 多用www.bing.com國際版解決代碼報錯 代碼運行的時候,報異常,國內的搜索引擎一搜, 浮誇的廣告太多,解決方案准確性不足, 盜版又很嚴重(導致一錯皆錯),方案未及時更新等詬病。 www.bing.com國際版可以關聯到: (1). 外國官網,可以獲得官方的解決方案。 (2). stackov ...
x