設(shè)計(jì)：小艾

審核：丁奇、宇亭

編輯：宇亭

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

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

一、MySQL 連接方式簡(jiǎn)介

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

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

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

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

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

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

掃描一個(gè)表的過(guò)程其實(shí)是先把這個(gè)表從磁盤(pán)上加載到內(nèi)存中，然后在內(nèi)存中比較匹配條件是否滿足。但內(nèi)存里可能并不能完全存放的下表中所有的記錄。為了減少訪問(wèn)被驅(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)表上沒(méi)有建立索引時(shí)，MySQL 會(huì)嘗試使用此算法。整體效率比較：INLJ > BNLJ > SNLJ。整個(gè)過(guò)程如下圖所示：

哈希連接（Hash Join）

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

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

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

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

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

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

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

2.1 哈希算法的選取

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

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

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

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

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

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

2.3 對(duì)探測(cè)過(guò)程的優(yōu)化

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

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

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

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

哈希表訪存的隨機(jī)性不可避免地會(huì)提升 cache miss 率而不得不通過(guò)頁(yè)表訪問(wèn)內(nèi)存，這會(huì)使得 Hash Join 遭遇性能瓶頸?，F(xiàn)代計(jì)算機(jī)處理器的最大緩存粒度是 LLC（Last Layer Cache，在廣泛應(yīng)用的 Intel/AMD 處理器上，它是 L3 緩存），因此以 LLC 大小為單元的內(nèi)存區(qū)域操作是對(duì) Cache Miss 率優(yōu)化的出發(fā)點(diǎn)。一個(gè)簡(jiǎn)單的方法是條件化預(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)存，這樣線性探測(cè)方法將可以減少 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 路由到對(duì)應(yīng)的 Partition 中進(jìn)行哈希查找和比對(duì)。這樣做意義有三點(diǎn)

1. 首先就是通過(guò)讓每個(gè) Partition 能夠被裝入 LLC，使得處理一個(gè) Partition 的構(gòu)建和探測(cè)任務(wù)時(shí)大大降低 Cache Miss 率；

2. 可以更細(xì)粒度地管理哈希表的內(nèi)存使用，哈希表可以不以 2 的冪的形式分配內(nèi)存（以 Partition 為基本分配單位），同時(shí)在極限情況下也可以釋放部分空的 Partition 以移作他用；

3. 使得并行構(gòu)建哈希表成為可能，這部分由 2.5 節(jié)闡述。

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

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

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

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

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

本圖引用自互聯(lián)網(wǎng)，侵權(quán)聯(lián)系刪除