設計：小艾
稽核：丁奇、宇亭
編輯：宇亭
作者一：徐鑫強（花名：無花果）
電子科技大學-計算機技術-在讀碩士、StoneDB 核心研發實習生
作者二：柳湛宇（花名：烏淄）
浙江大學-軟體工程-在讀碩士、StoneDB 核心研發實習生
一、MySQL 連接配接方式簡介
MySQL 支援自然連接配接、等值連接配接（内連接配接）、左連接配接、右連接配接、交叉連接配接五種連接配接方式，不支援全外連接配接，全外連接配接可以通過 Union 并集操作實作。連接配接算法：簡單嵌套循環、索引嵌套循環、塊嵌套循環以及哈希連接配接。
簡單嵌套循環（Simple Nested-Loop Join，SNLJ）
驅動表中的每一條記錄與被驅動表中的所有記錄依次比較判斷，驅動表周遊一次，被驅動表周遊多次。此算法開銷非常大，假設驅動表的行數為 M，被驅動表的行數為 N，則算法時間複雜度為 O(M*N)。實際上，MySQL 并不會使用此算法。
基于索引的嵌套循環（Indexed Nested-Loop Join，INLJ）
通過在被驅動表建立索引，減少被驅動表的掃描次數。一般 B+樹的高度為 3~4 層，也就是說比對一次的 I/O 消耗也就 3~4 次，是以索引查詢的成本是比較固定的，故優化器都傾向于使用記錄數少的表作為驅動表。在有索引的情況下，MySQL 會嘗試使用此算法。整個過程如下圖所示：
基于塊的嵌套循環（Block Nested-Loop Join，BNLJ）
掃描一個表的過程其實是先把這個表從磁盤上加載到記憶體中，然後在記憶體中比較比對條件是否滿足。但記憶體裡可能并不能完全存放的下表中所有的記錄。為了減少通路被驅動表的次數，我們可以首先将驅動表的資料批量加載到 Join Buffer（連接配接緩沖），然後當加載被驅動表的記錄到記憶體時，就可以一次性和多條驅動表中的記錄做比對，這樣可大大減少被驅動表的掃描次數，這就是 BNL 算法的思想。當被驅動表上沒有建立索引時，MySQL 會嘗試使用此算法。整體效率比較：INLJ > BNLJ > SNLJ。整個過程如下圖所示：
哈希連接配接（Hash Join）
嵌套循環連接配接對于被連接配接的資料集較小的情況是較好的選擇，而對于大資料集 Hash Join 是更好的方式。優化器使用兩個表中的較小表在記憶體中依據 Join Key 建立哈希表，然後依次掃描較大表并探測哈希表，找出能與哈希表比對的行。Hash Join 會破壞表資料的有序性和局部性，是以它隻能應用于等值連接配接。
二、哈希連接配接的優化方向簡述
随着 MySQL 8.0 對 Hash Join 支援，在内外表均無索引或大表驅動小表的情況下，Hash Join 顯然是比 BNLJ 更好的選擇，而在 AP 場景下，大量資料多表 Join 的剛需也使得 Hash Join 有了多種方向的優化路徑。本章簡要介紹一部分對 Hash Join 優化的方向和思路。
一個關鍵的前提是，前述介紹提到了 Hash Join 不适用于非等值連接配接，是以當表連接配接語句語句中未使用ON <attr1>=<attr2>樣式的等值連接配接方法或預設的自然等值連接配接時，MySQL 不會使用 Hash Join。
首先應當明确 Hash Join 的工作流程，以 MySQL 為例 [1] ，MySQL 就使用了經典的單線程 Hash Join 實作，它有建表（build）和探測（probe）生成結果兩個步驟。
- 「建表」：如下圖所示，建表就是周遊 OuterTable，将其等值連接配接鍵計算哈希值并根據結構建構為一個哈希表：
- 「探測」：如下圖所示，探測步驟就是周遊 InnerTable，計算每個 tuple 的值連接配接鍵的哈希值并從哈希表中找到對應的桶（bucket），并通過對比決定是否能進行哈希連接配接，進而完成整個 Hash Join 過程 [2] 。
2.1 雜湊演算法的選取
雜湊演算法是 Hash Join 的基礎，好的雜湊演算法可以極大提升依賴哈希操作的程式的效率。優秀的哈希函數會在随機性（展現發生哈希沖突的機率）和計算效率（單詞計算哈希的速度）之間做 trade-off，是以不同側重方向的資料庫也應當選擇合适的哈希函數，如 Apache Doris[3]選擇了 CRC32 這一計算速度很快且可以通過 SIMD 加速的哈希函數，而 DuckDB 選擇了随機性更高的 MurmurHash[4]。
但時至今日，随着 XXhash[5]的問世，哈希函數的選取似乎真正擁有了銀彈。對于絕大多數的 HashTable 這種哈希長度相對較小的場景，XXHash 的不同長度變種似乎都是最佳選擇：
2.2 哈希表的基礎結構設計
哈希表基礎結構設計的一個基礎點就是其處理沖突的方法，經典的處理方法有開放尋址法（即在哈希沖突時使用線性探測、平方探測、重哈希等方法繼續在哈希表中搜尋）和拉鍊法（在 bucket 中存儲連結清單或平衡二叉樹代表的沖突子項）。拉鍊法是更直覺和更低哈希沖突率的做法，是以其多見于 Java/Go 等程式設計語言的哈希表實作。然而對于資料庫核心中的哈希表，應用大資料量、控制記憶體使用量和 Cache Miss 率等都是優先級更高的需求，是以線性探測等開放尋址的沖突處理方法是構架哈希表的更優解。
另一個關鍵的基礎結構設計是哈希表擴容的機制，大部分哈希表的擴容機制是在當已有元素站總容量比例超過一定門檻值（對于 DuckDB，這個門檻值是預設是 50%，對于 Java 的 HashMap，這個門檻值預設是 75%）後進行擴容。但是顯然對于線性探測的沖突處理方法，哈希沖突的機率由于哈希聚集（hash clustering）的原因會随占用率提高而迅速增加，是以一般線性探測的沖突處理方法設定的門檻值較低，這也導緻了記憶體的浪費。是以有一系列的工作[6] 通過 rehash 或維護細粒度資料結構等方法改善這一情況。
對于資料庫核心這一領域，核心的優化器可以為哈希表提供可用的結構優化和先驗知識。如對于列式存儲資料庫，可以通過 build 過程下推，直接以核心中讀取的壓縮後的鍵進行哈希表的建構合并，減少序列化和反序列化開銷并減小 hash key 長度。此外，可以通過優化器的統計資料，将需要建表的資料剪去字首，這也能進一步地減少 hash key 長度，進而加速哈希函數計算速度。
2.3 對探測過程的優化
由上節可以看出，對于線性探測方法建構的哈希表，哈希沖突是探測操作是的性能瓶頸，是以可以引入一層過濾層，盡早過濾掉不在哈希表中的探測鍵值，進而減少探測的次數，這一過濾層最經典的實作就是如下圖所示的布隆過濾器[7]。
本文不再深入闡述布隆過濾器的算法原理和優化方法，讀者隻需要知道，布隆過濾器可以通過若幹個哈希函數（實踐上，它們由一個基礎哈希函數和位移、累加操作得到）操作一個 bitmap，通過對 OuterTable 的等值鍵周遊進行建構并由 Inner Table 探測。其特點是存在假陽性（False Positive），但不存在假陰性（False Negative），即通過布隆過濾器的記錄并不一定真的能夠比對（可能存在哈希沖突），但被過濾掉的記錄一定不比對。
在布隆過濾器的基礎上，還有一系列的機率資料結構變種，如 Block Bloom Filter，Cuckoo Filter[8]等 。不過對于不需要删除，操作相對固定的 Hash Join 場景，實作簡單，占用記憶體少的布隆過濾器是大部分情況下的最佳選擇。
2.4 對 Cache Miss 的優化
哈希表訪存的随機性不可避免地會提升 cache miss 率而不得不通過頁表通路記憶體，這會使得 Hash Join 遭遇性能瓶頸。現代計算機處理器的最大緩存粒度是 LLC（Last Layer Cache，在廣泛應用的 Intel/AMD 處理器上，它是 L3 緩存），是以以 LLC 大小為單元的記憶體區域操作是對 Cache Miss 率優化的出發點。一個簡單的方法是條件化預讀取（Conditional Pre-fetching）：哈希表可以維護關于哈希沖突數量、占有率以及哈希沖突熱點區域的中繼資料，并根據這些中繼資料判斷一次 probe 是否可能産生大量的哈希沖突，并在可能産生沖突時以 LLC 大小為機關預讀取若幹個 bucket 到記憶體，這樣線性探測方法将可以減少 cache miss 數量。
更複雜的方法則是按如下圖的方式建構分區哈希表（Partitioned Hash Table），即按照一定的标準（這個标準可以參考優化器提供的統計資料）将 Outer Table 在建表時放入不同的子哈希表（稱為 Partition），而周遊 Inner Table 時，可以使用同樣的标準将比較的 key 路由到對應的 Partition 中進行哈希查找和比對。這樣做意義有三點
- 首先就是通過讓每個 Partition 能夠被裝入 LLC，使得處理一個 Partition 的建構和探測任務時大大降低 Cache Miss 率；
- 可以更細粒度地管理哈希表的記憶體使用，哈希表可以不以 2 的幂的形式配置設定記憶體（以 Partition 為基本配置設定機關），同時在極限情況下也可以釋放部分空的 Partition 以移作他用；
- 使得并行建構哈希表成為可能，這部分由 2.5 節闡述。
接下來的問題是，如果快速且有效地将整個哈希表且分為若幹分區表，為了保證這一過程的效率，Radix Hash Join[9]的流程被提出。
2.5 多線程哈希連接配接的優化
MySQL 的 Hash Join 是單線程執行的。但通過例如上述建構布隆過濾器和分區哈希表的方法，我們可以實作多線程執行。
布隆過濾器本身的建構和探測類似于哈希表的建構和探測，是以二者可以類比分析。布隆過濾器的變種 Blocked Bloom Filter 通過數學證明可以與布隆過濾器有類似的效能，但可以通過開多線程并行建構每個 Block，并空值 Block 大小适配 CPU 核的緩存，并通過 SIMD 加速探測操作。Hash Join 的探測操作類似，将 Inner Table 的記錄切為若幹個線程并發處理的任務段後，并行地對哈希表進行探測，并在需要時将最後的結果進行 Merge 操作以保證資料有序性，這一點類似于排序-歸并連接配接的算法。
而建構操作則先得到更加複雜，因為它存在寫操作寫操作，即使是對 Partitioned Hash Table，仍然要進行 Partition-wise 或 Bucket-wise 的加鎖-解鎖操作才能并行執行。是以需要同步措施來保證線程之間資料的一緻性和正确性，在目前的工業實踐上，通過被大部分主流處理器支援的cmpxchg指令實作的 CAS（Compare And Swap）操作是 CPU 密集操作的最佳實踐：
本圖引用自網際網路，侵權聯系删除