image.png

設(shè)計(jì)：小艾
審核：丁奇、宇亭
編輯：宇亭

作者一：徐鑫強(qiáng)（花名：無花果）
電子科技大學(xué)-計(jì)算機(jī)技術(shù)-在讀碩士、StoneDB 內(nèi)核研發(fā)實(shí)習(xí)生

作者二：柳湛宇（花名：烏淄）
浙江大學(xué)-軟件工程-在讀碩士、StoneDB 內(nèi)核研發(fā)實(shí)習(xí)生

一、MySQL 連接方式簡介

MySQL 支持自然連接、等值連接（內(nèi)連接）、左連接、右連接、交叉連接五種連接方式，不支持全外連接，全外連接可以通過 Union 并集操作實(shí)現(xiàn)。連接算法：簡單嵌套循環(huán)、索引嵌套循環(huán)、塊嵌套循環(huán)以及哈希連接。

簡單嵌套循環(huán)（Simple Nested-Loop Join，SNLJ）

驅(qū)動(dòng)表中的每一條記錄與被驅(qū)動(dòng)表中的所有記錄依次比較判斷，驅(qū)動(dòng)表遍歷一次，被驅(qū)動(dòng)表遍歷多次。此算法開銷非常大，假設(shè)驅(qū)動(dòng)表的行數(shù)為 M，被驅(qū)動(dòng)表的行數(shù)為 N，則算法時(shí)間復(fù)雜度為 O(M*N)。實(shí)際上，MySQL 并不會使用此算法。

image.png

基于索引的嵌套循環(huán)（Indexed Nested-Loop Join，INLJ）

通過在被驅(qū)動(dòng)表建立索引，減少被驅(qū)動(dòng)表的掃描次數(shù)。一般 B+樹的高度為 3~4 層，也就是說匹配一次的 I/O 消耗也就 3~4 次，因此索引查詢的成本是比較固定的，故優(yōu)化器都傾向于使用記錄數(shù)少的表作為驅(qū)動(dòng)表。在有索引的情況下，MySQL 會嘗試使用此算法。整個(gè)過程如下圖所示：

image.png

基于塊的嵌套循環(huán)（Block Nested-Loop Join，BNLJ）

掃描一個(gè)表的過程其實(shí)是先把這個(gè)表從磁盤上加載到內(nèi)存中，然后在內(nèi)存中比較匹配條件是否滿足。但內(nèi)存里可能并不能完全存放的下表中所有的記錄。為了減少訪問被驅(qū)動(dòng)表的次數(shù)，我們可以首先將驅(qū)動(dòng)表的數(shù)據(jù)批量加載到 Join Buffer（連接緩沖），然后當(dāng)加載被驅(qū)動(dòng)表的記錄到內(nèi)存時(shí)，就可以一次性和多條驅(qū)動(dòng)表中的記錄做匹配，這樣可大大減少被驅(qū)動(dòng)表的掃描次數(shù)，這就是 BNL 算法的思想。當(dāng)被驅(qū)動(dòng)表上沒有建立索引時(shí)，MySQL 會嘗試使用此算法。整體效率比較：INLJ > BNLJ > SNLJ。整個(gè)過程如下圖所示：

image.png

哈希連接（Hash Join）

嵌套循環(huán)連接對于被連接的數(shù)據(jù)集較小的情況是較好的選擇，而對于大數(shù)據(jù)集 Hash Join 是更好的方式。優(yōu)化器使用兩個(gè)表中的較小表在內(nèi)存中依據(jù) Join Key 建立哈希表，然后依次掃描較大表并探測哈希表，找出能與哈希表匹配的行。Hash Join 會破壞表數(shù)據(jù)的有序性和局部性，因此它只能應(yīng)用于等值連接。

二、哈希連接的優(yōu)化方向簡述

隨著 MySQL 8.0 對 Hash Join 支持，在內(nèi)外表均無索引或大表驅(qū)動(dòng)小表的情況下，Hash Join 顯然是比 BNLJ 更好的選擇，而在 AP 場景下，大量數(shù)據(jù)多表 Join 的剛需也使得 Hash Join 有了多種方向的優(yōu)化路徑。本章簡要介紹一部分對 Hash Join 優(yōu)化的方向和思路。

一個(gè)關(guān)鍵的前提是，前述介紹提到了 Hash Join 不適用于非等值連接，因此當(dāng)表連接語句語句中未使用ON <attr1>=<attr2>樣式的等值連接方法或默認(rèn)的自然等值連接時(shí)，MySQL 不會使用 Hash Join。

首先應(yīng)當(dāng)明確 Hash Join 的工作流程，以 MySQL 為例 [1] ，MySQL 就使用了經(jīng)典的單線程 Hash Join 實(shí)現(xiàn)，它有建表（build）和探測（probe）生成結(jié)果兩個(gè)步驟。

1. 「建表」：如下圖所示，建表就是遍歷 OuterTable，將其等值連接鍵計(jì)算哈希值并根據(jù)結(jié)構(gòu)構(gòu)建為一個(gè)哈希表：

image.png

2. 「探測」：如下圖所示，探測步驟就是遍歷 InnerTable，計(jì)算每個(gè) tuple 的值連接鍵的哈希值并從哈希表中找到對應(yīng)的桶（bucket），并通過對比決定是否能進(jìn)行哈希連接，進(jìn)而完成整個(gè) Hash Join 過程 [2] 。

image.png

2.1 哈希算法的選取

哈希算法是 Hash Join 的基礎(chǔ)，好的哈希算法可以極大提升依賴哈希操作的程序的效率。優(yōu)秀的哈希函數(shù)會在隨機(jī)性（體現(xiàn)發(fā)生哈希沖突的概率）和計(jì)算效率（單詞計(jì)算哈希的速度）之間做 trade-off，因此不同側(cè)重方向的數(shù)據(jù)庫也應(yīng)當(dāng)選擇合適的哈希函數(shù)，如 Apache Doris[3]選擇了 CRC32 這一計(jì)算速度很快且可以通過 SIMD 加速的哈希函數(shù)，而 DuckDB 選擇了隨機(jī)性更高的 MurmurHash[4]。

但時(shí)至今日，隨著 XXhash[5]的問世，哈希函數(shù)的選取似乎真正擁有了銀彈。對于絕大多數(shù)的 HashTable 這種哈希長度相對較小的場景，XXHash 的不同長度變種似乎都是最佳選擇：

image.png

2.2 哈希表的基礎(chǔ)結(jié)構(gòu)設(shè)計(jì)

哈希表基礎(chǔ)結(jié)構(gòu)設(shè)計(jì)的一個(gè)基礎(chǔ)點(diǎn)就是其處理沖突的方法，經(jīng)典的處理方法有開放尋址法（即在哈希沖突時(shí)使用線性探測、平方探測、重哈希等方法繼續(xù)在哈希表中搜索）和拉鏈法（在 bucket 中存儲鏈表或平衡二叉樹代表的沖突子項(xiàng)）。拉鏈法是更直觀和更低哈希沖突率的做法，因此其多見于 Java/Go 等編程語言的哈希表實(shí)現(xiàn)。然而對于數(shù)據(jù)庫內(nèi)核中的哈希表，應(yīng)用大數(shù)據(jù)量、控制內(nèi)存使用量和 Cache Miss 率等都是優(yōu)先級更高的需求，因此線性探測等開放尋址的沖突處理方法是構(gòu)架哈希表的更優(yōu)解。

另一個(gè)關(guān)鍵的基礎(chǔ)結(jié)構(gòu)設(shè)計(jì)是哈希表擴(kuò)容的機(jī)制，大部分哈希表的擴(kuò)容機(jī)制是在當(dāng)已有元素站總?cè)萘勘壤^一定閾值（對于 DuckDB，這個(gè)閾值是默認(rèn)是 50%，對于 Java 的 HashMap，這個(gè)閾值默認(rèn)是 75%）后進(jìn)行擴(kuò)容。但是顯然對于線性探測的沖突處理方法，哈希沖突的概率由于哈希聚集（hash clustering）的原因會隨占用率提高而迅速增加，因此一般線性探測的沖突處理方法設(shè)定的閾值較低，這也導(dǎo)致了內(nèi)存的浪費(fèi)。因此有一系列的工作[6] 通過 rehash 或維護(hù)細(xì)粒度數(shù)據(jù)結(jié)構(gòu)等方法改善這一情況。

對于數(shù)據(jù)庫內(nèi)核這一領(lǐng)域，內(nèi)核的優(yōu)化器可以為哈希表提供可用的結(jié)構(gòu)優(yōu)化和先驗(yàn)知識。如對于列式存儲數(shù)據(jù)庫，可以通過 build 過程下推，直接以內(nèi)核中讀取的壓縮后的鍵進(jìn)行哈希表的構(gòu)建合并，減少序列化和反序列化開銷并減小 hash key 長度。此外，可以通過優(yōu)化器的統(tǒng)計(jì)數(shù)據(jù)，將需要建表的數(shù)據(jù)剪去前綴，這也能進(jìn)一步地減少 hash key 長度，進(jìn)而加速哈希函數(shù)計(jì)算速度。

2.3 對探測過程的優(yōu)化

由上節(jié)可以看出，對于線性探測方法構(gòu)建的哈希表，哈希沖突是探測操作是的性能瓶頸，因此可以引入一層過濾層，盡早過濾掉不在哈希表中的探測鍵值，從而減少探測的次數(shù)，這一過濾層最經(jīng)典的實(shí)現(xiàn)就是如下圖所示的布隆過濾器[7]。

image.png

本文不再深入闡述布隆過濾器的算法原理和優(yōu)化方法，讀者只需要知道，布隆過濾器可以通過若干個(gè)哈希函數(shù)（實(shí)踐上，它們由一個(gè)基礎(chǔ)哈希函數(shù)和位移、累加操作得到）操作一個(gè) bitmap，通過對 OuterTable 的等值鍵遍歷進(jìn)行構(gòu)建并由 Inner Table 探測。其特點(diǎn)是存在假陽性（False Positive），但不存在假陰性（False Negative），即通過布隆過濾器的記錄并不一定真的能夠匹配（可能存在哈希沖突），但被過濾掉的記錄一定不匹配。

在布隆過濾器的基礎(chǔ)上，還有一系列的概率數(shù)據(jù)結(jié)構(gòu)變種，如 Block Bloom Filter，Cuckoo Filter[8]等 。不過對于不需要?jiǎng)h除，操作相對固定的 Hash Join 場景，實(shí)現(xiàn)簡單，占用內(nèi)存少的布隆過濾器是大部分情況下的最佳選擇。

2.4 對 Cache Miss 的優(yōu)化

哈希表訪存的隨機(jī)性不可避免地會提升 cache miss 率而不得不通過頁表訪問內(nèi)存，這會使得 Hash Join 遭遇性能瓶頸?，F(xiàn)代計(jì)算機(jī)處理器的最大緩存粒度是 LLC（Last Layer Cache，在廣泛應(yīng)用的 Intel/AMD 處理器上，它是 L3 緩存），因此以 LLC 大小為單元的內(nèi)存區(qū)域操作是對 Cache Miss 率優(yōu)化的出發(fā)點(diǎn)。一個(gè)簡單的方法是條件化預(yù)讀?。–onditional Pre-fetching）：哈希表可以維護(hù)關(guān)于哈希沖突數(shù)量、占有率以及哈希沖突熱點(diǎn)區(qū)域的元數(shù)據(jù)，并根據(jù)這些元數(shù)據(jù)判斷一次 probe 是否可能產(chǎn)生大量的哈希沖突，并在可能產(chǎn)生沖突時(shí)以 LLC 大小為單位預(yù)讀取若干個(gè) bucket 到內(nèi)存，這樣線性探測方法將可以減少 cache miss 數(shù)量。

更復(fù)雜的方法則是按如下圖的方式構(gòu)建分區(qū)哈希表（Partitioned Hash Table），即按照一定的標(biāo)準(zhǔn)（這個(gè)標(biāo)準(zhǔn)可以參考優(yōu)化器提供的統(tǒng)計(jì)數(shù)據(jù)）將 Outer Table 在建表時(shí)放入不同的子哈希表（稱為 Partition），而遍歷 Inner Table 時(shí)，可以使用同樣的標(biāo)準(zhǔn)將比較的 key 路由到對應(yīng)的 Partition 中進(jìn)行哈希查找和比對。這樣做意義有三點(diǎn)

1. 首先就是通過讓每個(gè) Partition 能夠被裝入 LLC，使得處理一個(gè) Partition 的構(gòu)建和探測任務(wù)時(shí)大大降低 Cache Miss 率；
2. 可以更細(xì)粒度地管理哈希表的內(nèi)存使用，哈希表可以不以 2 的冪的形式分配內(nèi)存（以 Partition 為基本分配單位），同時(shí)在極限情況下也可以釋放部分空的 Partition 以移作他用；
3. 使得并行構(gòu)建哈希表成為可能，這部分由 2.5 節(jié)闡述。

image.png

接下來的問題是，如果快速且有效地將整個(gè)哈希表且分為若干分區(qū)表，為了保證這一過程的效率，Radix Hash Join[9]的流程被提出。

2.5 多線程哈希連接的優(yōu)化

MySQL 的 Hash Join 是單線程執(zhí)行的。但通過例如上述構(gòu)建布隆過濾器和分區(qū)哈希表的方法，我們可以實(shí)現(xiàn)多線程執(zhí)行。

布隆過濾器本身的構(gòu)建和探測類似于哈希表的構(gòu)建和探測，因此二者可以類比分析。布隆過濾器的變種 Blocked Bloom Filter 通過數(shù)學(xué)證明可以與布隆過濾器有類似的效能，但可以通過開多線程并行構(gòu)建每個(gè) Block，并空值 Block 大小適配 CPU 核的緩存，并通過 SIMD 加速探測操作。Hash Join 的探測操作類似，將 Inner Table 的記錄切為若干個(gè)線程并發(fā)處理的任務(wù)段后，并行地對哈希表進(jìn)行探測，并在需要時(shí)將最后的結(jié)果進(jìn)行 Merge 操作以保證數(shù)據(jù)有序性，這一點(diǎn)類似于排序-歸并連接的算法。

而構(gòu)建操作則先得到更加復(fù)雜，因?yàn)樗嬖趯懖僮鲗懖僮?，即使是?Partitioned Hash Table，仍然要進(jìn)行 Partition-wise 或 Bucket-wise 的加鎖-解鎖操作才能并行執(zhí)行。因此需要同步措施來保證線程之間數(shù)據(jù)的一致性和正確性，在目前的工業(yè)實(shí)踐上，通過被大部分主流處理器支持的cmpxchg指令實(shí)現(xiàn)的 CAS（Compare And Swap）操作是 CPU 密集操作的最佳實(shí)踐：

image.png