## 課程目標

### 為什么需要 Join?

Join 實際上是關系型數(shù)據(jù)庫系統(tǒng)和范式化(normalize)表(table)時的副產(chǎn)物，通過拆分到不同的表中，減少重復冗余的信息(比如外鍵)

在沒有任何信息丟失的情況下，使用 Join operator 可以對原來的 tuple 進行重組

### Join 算法

在這節(jié)課中，會關注一次只 Join 2 個表的情況，會談到 inner equijoin 算法，這個算法是目前數(shù)據(jù)庫系統(tǒng)中最常見的算法實現(xiàn)

當然也有 Multi-way Join 算法，它可以在同一時間內(nèi)對 3 張以上的表進行 Join 操作(這幾乎只存在理論中，僅有部分高端系統(tǒng)已經(jīng)支持了這個，15-721 課會講到這個算法)

equijoin 指的是，從一個表中拿到一個 tuple，檢查它是否和另一個表中的 tuple 相等，能不能匹配的上(這里不考慮大于小于，也不考慮 anti-join)

那么 Join 操作大致是怎么的呢? —— 始終把更小的表作為 Join 操作中的左表(left table)

想象一下之前提到過的查詢計劃樹(Query Plan Tree)，在這個樹上的 operator 節(jié)點處，它下面有左右 2 個子節(jié)點，這 2 個子節(jié)點作為該 operator 節(jié)點的輸入(遞歸遍歷)。在這 2 個子節(jié)點中，左邊那個節(jié)點就是這個 更小的表，即 左表

> 注意這里說的 outer table，指的也是左表

### Join Operator

Join Operator 是如何工作的??

這個就需要涉及到查詢計劃樹了，基本上原理就是，拿到一個 SQL 查詢中的關系代數(shù)，然后將它轉(zhuǎn)變成一個有向圖/樹

比如上圖中，在葉子節(jié)點處要對表進行訪問，將表中的 tuple 作為輸入，傳給父節(jié)點處的 operator，而這里，就是一個 Join Operator，這個 Join Operator 的左邊就是 outer table 即左表，右邊的就是 inner table

那么 Join Operator 的輸出是什么?

### Join Output

對于所有屬于 R 表中的 tuple，用 r 表示，對于所有屬于 S 表中的 tuple，用 s 表示

在輸出結果時，如果滿足 Join 條件，那么就將符合條件的 tuple 向上傳給樹中的下一個 operator

從更高層面來說，Join 其實就是對 2 個表中的 tuple 進行級聯(lián)

比如上圖中，拿到 R 表和 S 表中的所有屬性，將它們雜糅到一起，然后輸出結果

雖然這個操作在理論上可行(取所有屬性)，但是在實際工程中，需要考慮到磁盤讀取、使用多少內(nèi)存，所以并不會去把所有屬性都拿到

整個流程就是，將當前 operator 的輸出結果發(fā)送給下一個 operator，如何發(fā)送會取決于實現(xiàn)的查詢模型。在這個流程中，輸出的結果的發(fā)送并不會是 一直只發(fā)送一個 tuple，而是也會發(fā)送多個 tuple，發(fā)多發(fā)少也取決于存儲模型，比如是基于行數(shù)據(jù)庫還是基于列數(shù)據(jù)庫

對于發(fā)送 tuple 的屬性來講，發(fā)送對應的 tuple 的屬性的多少取決于查詢計劃樹，在輸出結果的發(fā)送過程中，可能不需要將這 2 個表中所有屬性都發(fā)送出去，而是只需要發(fā)送部分屬性就可以了

#### Join Operator Output: Data

第一個方案就是發(fā)送數(shù)據(jù)，即復制 Join 條件中 tuple 的屬性值，生成一個新的輸出 tuple，然后傳給下一個 operator

如圖所示，上圖中有 R 表和 S 表，當對這 2 個表進行 Join 操作時

其實就是將 S 表中的屬性追加到 R 表屬性的后面，這就是 Join operator 所生成的新的結果

對應于查詢計劃樹，就是上圖中出現(xiàn)的結果(Join operator 對應的地方)

這樣做有優(yōu)勢也有劣勢

1. 優(yōu)勢

? ? 在上述查詢計劃樹中，就不需要回過頭去從基礎表里面去讀取更多數(shù)據(jù)了，因為從 R 表和 S 表中 Join 出來的數(shù)據(jù)會被用來生成 inner join 的輸出

2. 劣勢

? ? 因為 Join operator 生成的這個新的結果，導致這個結果即 tuple 巨大無比(如果 R 表和 S 表中的屬性非常多，這個 tuple 所具備的屬性就變得超級多)，將這樣的結果進行復制并沿著查詢計劃樹向上傳遞，那代價就會變得昂貴

因為這個劣勢存在，所以在執(zhí)行 Join 操作之時，可以內(nèi)嵌執(zhí)行 Projection 操作，過濾掉 R 表和 S 表中那些不需要的屬性和字段，這樣最終生成的 tuple 才是合理的

#### Join Operator Output: Record Ids

第二個方案就是，只發(fā)送所需要的最小限度的信息，即 Join keys。這個最小限度的信息同時也包括 匹配 Join 條件的 tuple 的 record id，通過這個 record id 可以找到表中其他剩余的數(shù)據(jù)

如圖所示，上圖中只在 R.id 和 S.id 上進行 Join 操作，所以在 Join operator 的輸出結果中，其 R.id 要和 R.rid 匹配上，S.id 要和 S.rid 匹配上(rid 即 record id)

有什么用呢? 如果此時需要將 R 表或 S 表中其他屬性的值找到，只需要利用這個對應的 record id，或者 tuple id 中的 page number 以及 offset 值，就可以找到該 tuple 其他剩余的屬性的值

然后經(jīng)過 Join operator 生成一個新的結果

此時如果想要拿到 S.cdate，只需要通過 S.rid 即可找到對應屬性的值

但是，對于列存儲來說，它實際上需要將這些所有不同列的的 tuple 粘接在一起，從列形式變成行形式，然后把生成的這個結果傳給查詢計劃樹，這中間的代價依然非常昂貴(因為要傳遞的屬性依然非常多)

那么怎么解決呢? 就是盡可能的延遲它這種從 列形式 變成 行形式 的操作，那么就不用在查詢計劃樹中向上傳遞一大堆數(shù)據(jù)了

其基本思想有些類似于懶加載，即只有當 query 需要時，在執(zhí)行 Join 操作之后，再去執(zhí)行到磁盤中獲取其他字段數(shù)據(jù)并做粘接的操作(從列形式變成行形式)，比如上圖中需要的 S.cdata，如果沒有它，則不需要再去經(jīng)歷從列形式變成行形式的過程，也就提升了性能

> 但是這里有個問題，一開始就需要把數(shù)據(jù)取出來，經(jīng)歷從列形式變成行形式的過程，代價不是依然很高嗎?這也許是第一個列存儲數(shù)據(jù)庫 Vertica 在 2000 年推出時一直在推崇這個技術，但到后來放棄掉它的原因吧

### I/O 成本分析

如何判斷一個 Join 算法的好壞? 可以見上圖

基本思路就是，**用在計算 Join 操作時所必須使用的 I/O 次數(shù)** 來做判斷

> 注意，這個 *計算 Join 操作* 的過程不包括實際生成最終結果所付出的成本，因為這期間可能要考慮到其他因素

### Join VS. Cross-Product

本節(jié)主要關注的是 inner equijoin，因為這最常見

本節(jié)不會去討論 cross product/cross join 以及 Cartesian products，因為這些東西幾乎很難遇到

> cross join 也沒辦法讓他變得更快，因為這個需要 2 個 for 循環(huán)去遍歷處理這堆匹配上的數(shù)據(jù)，就像是一個不需要條件判斷的 nested-loop join

但是盡管有關于 Join 算法的優(yōu)化，對每種可能的場景、數(shù)據(jù)集、查詢來說，不可能始終有效

## Join 算法

### Nested-Loop Join

顧名思義，它就是在一個 for 里面又嵌了一個 for

上圖就是遍歷 R 表和 S 表，然后看下 SQL 中的 Join 子句和 Where 子句中的條件部分，看看這些 tuple 是否滿足上圖中的條件，如果滿足，則生成輸出，它會作為下一個 tuple 的輸出結果而緩存起來

> Outer 就是在外層的循環(huán)，Inner 就是在里層的循環(huán)

在實際的查詢計劃中，它長啥樣呢?

如上圖所示，左邊 R 代表 Outer Table，右邊 S 代表 Inner Table

這種 Join 算法肯定是最蠢的，因為對于每個在 R 表中的 tuple，每次循環(huán)都得將 S 表中的數(shù)據(jù)放入內(nèi)存進行處理(顯然從磁盤到內(nèi)存的 I/O 變多了，所以付出的代價也變的奇高)

那么成本是多少呢?

M + (m x N)

一個鮮明的例子如下

所以這個樸素的 Join 算法需要優(yōu)化，那么怎么優(yōu)化呢? 將更小的表作為 Outer Table 使用對吧?

那么我們再來計算一下成本

可以看到至少要花 1.1 小時才能完成整個 Join 操作，是進步了一點，但還不太夠

假設 page 是 4KB 大小，通過計算可得出這些 page 的總體積為 6MB 左右，而這完全可以放在 L3 Cache 中，這些數(shù)據(jù)放在 CPU Cache / 內(nèi)存中操作當然會很快，但是如果一定要從磁盤上讀取，那就會慢的離譜

### Block Nested-Loop Join

其中一種優(yōu)化方式就是，使用 block 和 page，將多個 tuple 打包進 page 中

基本原理是這樣的

對于 Outer Table 所用的每個 block 而言，每次從 Inner Table 中拿到一個 block 時，會讓 Outer Table block 中的每個 tuple 和 Inner Table block 中的所有 tuple 進行 Join，直到這個 Outer Table block 中所有的 tuple 完成了 Join 操作，才會繼續(xù)和 Inner Table 中下一個 block 的所有 tuple 進行 Join

為什么這種會好點? 因為成本降低了

M + (M x N)

這里的關鍵在于，**現(xiàn)在是讓 Outer Table 中的每個 page 和 Inner Table 中的每個 page 進行 Join**

那么這里哪個是 Outer Table 呢?很顯然是 page 數(shù)最小的那個

一個鮮明的例子如下

雖然優(yōu)化到了 50s 左右，但這依然是一個糟糕的數(shù)字，因為要對 6MB 大小的數(shù)據(jù)進行 Join 處理不應該花上 50s 左右的時間

那么還能怎么繼續(xù)優(yōu)化呢?

上面的算法，對于 Outer Table 和 Inner Table 來說，它們都是使用 1 個 block 來承載數(shù)據(jù)

那么很自然就想到，如果使用 多個 block 來承載數(shù)據(jù)呢?

這個優(yōu)化的基本原理是

對于 Outer Table，盡可能使用內(nèi)存中的 buffer 來保存它，即使用 B-2 個 block。然后用 1 個 block 來負責 Inner Table，再用 1 個 block 用來負責輸出結果

算法如上圖所示

由于此時不需要再進行 m x N 次讀取，所以成本計算如下

對于 Outer Table 處 page 的讀取成本來說，是 M/(B-2)

所以最終為

M + (M/(B-2) x N)

那么如果 Outer Table 能完全放入內(nèi)存中，會發(fā)生什么呢?

這意味著 允許 buffer 的數(shù)量 > M+2

> M+2 中的 2 ，1 個代表的是 Inner Table，另 1 個代表的是輸出結果

如果能把數(shù)據(jù)放入這 B-2 個 buffer 中(這 B-2 個 buffer 包含了 Outer Table 中所有的數(shù)據(jù))，那么現(xiàn)在要做的就只是從 Outer Table 中獲取一次數(shù)據(jù)，然后將該數(shù)據(jù)放入內(nèi)存中，然后再去掃描下 Inner Table，那么成本就會變成

M + N

如下圖所示

其實這里本質(zhì)上就是把原來在磁盤的數(shù)據(jù)丟內(nèi)存處理了，相當于少了很多 I/O，所以速度就變快了

所以如果內(nèi)存足夠，將 Outer Table 相關數(shù)據(jù)放入到這里，可以極大的提升性能(相比于之前的方法而言)

當然如果數(shù)據(jù)庫的數(shù)據(jù)過大(TB/PB)，這個還是不可行的

### 為什么 Nested-Loop Join 系列 sucks?

當然因為這是暴力查詢啊

所以沒有索引存在時，暴力查詢就是一個備選項

那么假如能對進行 Join 操作的 key 建立索引，那么對于 Inner Table，可以將它作為內(nèi)循環(huán)的一部分使用，就沒必要每次都要循序掃描了

某些系統(tǒng)可以在運行時構建索引，比如 Hash Join。在其他系統(tǒng)中，比如 SQL Server，它在運行時可以構建一個名叫 Spooling Index 的 B+ Tree。在系統(tǒng)查詢并進行 Join 操作時，就會去使用這個索引。而當查詢結束，這個索引就會被丟棄掉

### Index Nested-Loop Join

首先對 Outer Table 進行掃描，這個時候可以使用額外的 buffer block，這樣就不用每次都對單個 tuple 進行 I/O (從磁盤到內(nèi)存)獲取了

對于內(nèi)部循環(huán)來說，可以使用索引探針(index probe)，如果條件匹配上了，就可以檢查能否生成一個輸出

那么此時成本是多少呢?

這就取決于使用的索引了

M + (m x C)

> 常量 C 表示索引帶來的成本消耗。如果是 Hash Table，那么時間復雜度最好情況就是 O(1)。如果是 B+ Tree，那么情況就是 log(n)

因為索引是 **有序** 的，知道了這些 tuple 的所在位置，就只需要 N 次 I/O 就能拿到對應的數(shù)據(jù)。所以對于上圖中單個 page，成本是 nxC，對于 N 個 page，成本就是 N + (nxC)。要理解的話，nxC 在這里就相當于一個 offset，因為這里移動的是游標(指針)，用過 C 語言的話這里理解應該不難

現(xiàn)在通過成本的分析可以看到，性能更佳了

### 小結

- Nested-Loop Join 方式就是一種暴力查詢，雖然粗暴但是實現(xiàn)起來簡單

- 始終需要將更小的表作為 Outer Table

- 盡可能將 Outer Table 放入內(nèi)存中，減少冗余 I/O

- 有索引就用索引，加快掃描速度

### Sort-Merge Join 算法

這個所謂的 Sort-Merge Join 算法很想上節(jié)課說過的 external merge sort 算法，這個算法可以在 sort 階段使用。(如果數(shù)據(jù)全在內(nèi)存中可以使用快排)

但是到 merge 階段，就有些不同了

merge 階段，通過游標對這 2 個排好序的的表中的 tuple 逐個對比，如果匹配，就輸出匹配的 tuple

在某些情況下，只需要對 Inner Table 中的 tuple 訪問 1 次就夠了(也就是說可以不需要進行回溯并多次訪問，因為已經(jīng)提前排好序了)

上圖是這個 Join 算法的一種近似實現(xiàn)

以圖舉例

首先，先對數(shù)據(jù)做排序

然后通過游標去遍歷這 2 個表

R 表中的游標指向的是 id=100 的位置，S 表中的游標指向的是 id=100 的位置，此時根據(jù)條件，它倆匹配上了，將這 2 個對應的 tuple 結合在一起，生成一個輸出結果

然后移動 S 表的游標，繼續(xù)匹配下一個，并生成一個結果

然后繼續(xù)移動

此時 S 表中的游標指向的位置的 id 的值是 200，比 R 表中游標指向的 100 要大，所以此時移動 R 表中的游標，直到匹配上對應的條件

此時 2 個表中的游標就沒必要往回走了，因為數(shù)據(jù)已經(jīng)預先排好序了

這就是為什么 Sort-Merge Join 要比 Nested-Loop Join 好的原因

當然有沒有可能存在回溯的情況呢? 有的，比如下圖

R 表中的游標往下移動了，對應的 id = 200，此時如果 S 表依然往下移動，那么它就會錯過此次的匹配機會

那么怎么解決呢?

這個就需要在 Inner Table 中維護一些元數(shù)據(jù)。操作是這樣，如果在 Inner Table 中，上次遇到的這個值是 200，那么在下次 Outer Table 移動游標時，如果此時 Outer Table 游標對應的值是 200，那么如果它能匹配上在 Inner Table 中剛訪問過的最后一個 tuple 的 id 值，就回到第一次在 Inner Table 中看到這個值所在的位置，比如下面

然后再執(zhí)行 Join 操作，生成一個匹配輸出

接下來就是按照上述算法來做匹配輸出了，直到 2 個游標都到達 2 張表的最底部，整個 Join 操作宣告完成

所以這里實際上的優(yōu)勢就在于

**雖然 Inner Table 可回溯，但 Outer Table 不可回溯**

那么這個算法的成本是多少呢?

Inner Table 和 Outer Table 中排序所用的成本跟之前討論過的 external merge sort 所用的成本是一樣的

粗略計算，merge 的成本就是 M+N

一個例子

那么 sort-merge 會有最糟糕的情況嗎?

有的

一個極端情況是，Outer Table 中每個值都和 Inner Table 中的每個值相同(比如 Table 中每個值都是 1)，那這樣排序就失去了意義，同時也是在浪費時間，這種情況下，其實就跟 Nested-Loop Join 算法差不多了

當然，如果發(fā)現(xiàn)都是這一類型的數(shù)據(jù)，直接做笛卡爾積就好了(即直接生成輸出結果，不需要任何經(jīng)過任何排序算法)

### 為什么 Sort-Merge Join 算法有用?

如果 id 已經(jīng)排好序，那就不需要再經(jīng)歷一次排序

如果查詢語句中包含 ORDER BY 子句，那么它就會基于要進行的 Join 操作的 key 來對表或者結果進行排序。排序之后就是做合并操作(因為在做 Sort-Merge Join 操作)，最終輸出結果的排序順序和 ORDER BY 子句的排序順序是一樣的

## Hash Join

重點算法來了

Hash Join 跟 Hash Aggregation 類似，眾所周知，hash 函數(shù)是確定的，如果將同一個輸入傳給該 hash 函數(shù)，那么它生成的值始終都是相同的

所以，如果將 Outer Table 以及 Inner Table 中的 value 進行 hash 處理，讓它 mapping 到某個值上，這樣的話就能對對應的數(shù)據(jù)進行分區(qū)(partition)，然后在查數(shù)據(jù)時只需要在同一個 hash bucket 中查就好了

所以基本原理就是，基于 hash key 將 Outer Table 以及 Inner Table 拆分為多個分區(qū)

- 如果這些數(shù)據(jù)都能放在內(nèi)存中，就可以使用之前講過的 linear hash table(linear probing hash table、static hash table)

- 如果必須將數(shù)據(jù)溢出到磁盤，那么就可以使用之前講過的 bucket chain hash table 進行遞歸分區(qū)

分區(qū)的好處在于，在查數(shù)據(jù)時，只需要關心同一個分區(qū)中的數(shù)據(jù)就行了，就不用去看整張表了

### Hash Join 算法

基本的 Hash Join 算法有 2 個階段

1. build

? ? 拿到 Outer Table，并對其進行循序掃描，然后對要 Join 的那個屬性進行 hash 處理，將數(shù)據(jù)填入 hash table

2. probe

? ? 對 Inner Table 進行循序掃描，用 build 階段相同的 hash 函數(shù)對 Inner Table 中每個 tuple 進行 hash 處理，然后檢查是否有匹配的 tuple

最終，如果匹配成功，就生成輸出結果

例子如下

首當其沖的就是，通過 Outer Table，用一個 hash 函數(shù)構建一個 hash table

然后就是上面提到的 build 階段，將數(shù)據(jù)填入 hash table

然后就是 probe 階段

### Hash Table 的內(nèi)容

主要就分 2 個，key 和 value

1. key

? ? 要進行 Join 操作的那些屬性

2. value

? ? 取決于要往查詢計劃上傳遞的信息結構

### Hash Table 的 Value

這個 Value 的結構可以是怎么樣的呢?

1. 存整個 tuple

? ? 這意味著所有的 tuple 屬性都能拿到，無須做回表 I/O，但同時 hash table 會變得很大，這意味著可能需要將數(shù)據(jù)溢出到磁盤，雖然查找數(shù)據(jù)是變快了

2. 只存 tuple 的標識符

? ? 這個 tuple 的標識符就是 tuple 的 record ID，這種方式適用于列存儲，不要數(shù)據(jù)時可以不用到磁盤去取。但對于行存儲，即便是通過 record ID 去找，還是需要先拿到包含這個 tuple 的那個 page(這中間需要從磁盤加載到內(nèi)存)，然后再能對這個 tuple 做操作

### Probe 階段優(yōu)化

在 build 階段，把一個 hash table 構建好后，可以去構建一個輔助數(shù)據(jù)結構/filter，通過它，在沒有查看 這個 hash table 的情況下，可以判斷要查找的 tuple 是否在這個 hash table 中

那么怎么做呢?

答案是弄一個 **布隆過濾器(Bloom Filter)**

那么什么是布隆過濾器呢? 見下圖

> 又是一個在 1970 年代發(fā)明的算法，發(fā)明人就叫 Bloom

它是一種概率數(shù)據(jù)結構，一個 bitmap，可以用來響應 set membership 查詢

set membership 查詢可以做什么事情? 它可以判斷某個 key 是否存在于要查找的集合中，來回應你 yes or no

但因為它是這種概率數(shù)據(jù)結構，所以可能會出現(xiàn) 假陽性 的情況

> 即它會對傳入的 key 進行 2 次 hash，hash 后結果為真，但實際上 2 次 hash 可能都屬于 **碰撞為真**，而那個要查找的 key 實際上并不存在

基本的布隆過濾器只做 2 件事情

1. 插入 key

2. 查找 key

不能去 刪除 key

那么它是怎么運作的呢?

一個典型的 8 bit 布隆過濾器如下

比如這里要 insert 一個 'RZA' 這個 key，那么就會對 'RZA' 這個 key 進行多次 hash

hash 結果出來之后，就會去修改過濾器中所擁有的 bit 數(shù)量，如下所示(4 對應的位置和 6 對應的位置，將對應的 bit 翻轉(zhuǎn))

接著 insert 一個 'GZA' 這個 key，相似的操作

修改過濾器對應 bit 中的值

接著，查找 'Raekwon' 這個 key

經(jīng)過 hash 后的結果為

3 對應的位置是 1，5 對應的位置是 0，因為 1&0 === false，所以 'Raekwon' 這個 key 就不存在

接著，查找 'ODB' 這個 key，并對其做 hash 處理

這里可以看到過濾器中 3 和 6 的位置都是 1，但是這倆位置之前已經(jīng)用 'RZA' 和 'GZA' 填充過了，雖然這里面之前并沒有插入過 'ODB'，但顯示的結果依然為真。這就是所謂的 假陽性 的情況

所以使用布隆過濾器的 插入 操作的次數(shù)越多，hash 函數(shù)越多，那么最終結果中獲得假陽性的概率就會越大。所以在數(shù)據(jù)量比較小的場景是合適的，因為這樣 hash 碰撞的概率會小些

那么回到 probe 優(yōu)化這里來，布隆過濾器在這里的作用是什么?

在 probe 階段，構建 hash table 時，這個 hash table 會變得很大，并且可能會溢出到磁盤。這個時候可以為這個 hash table 的 key 構建一個布隆過濾器，因為它的體積非常小，所以可以放到內(nèi)存中

如下圖

這個布隆過濾器會傳到 Join 里，并且在對 hash table 進行檢測(key)前，要通過過濾器來做一次檢測(key)(因為是在內(nèi)存中，所以速度會非?？?

如果 key 匹配不上 hash table 中的任何東西，那么過濾器中也沒有相應能匹配的 key

過濾器提前知道了這個 key 是否在 hash table 里存在，也就避免了在 hash table 中的查找操作，同時也能避免接下來要跳到想要找的數(shù)據(jù)對應的位置時，發(fā)生的磁盤 I/O

否則，如果過濾器知道這個 key 在 hash table 中存在，那么就需要去在 hash table 中進行查找操作

因為過濾器提供的結果可能是假的(假陽性)

當然，可以通過調(diào)整布隆過濾器的大小，來避免所有位置上的數(shù)字都被設置成 1

### 無法在內(nèi)存中處理的 Hash Join

如果所有數(shù)據(jù)都能放在內(nèi)存中，那可以使用 linear probing hash table，基于數(shù)據(jù)大小來預估所需要的 hash table 的大小，速度會很快

但是如果現(xiàn)在開始要往磁盤上溢出數(shù)據(jù)，那么 hash table 處理起來就有些麻煩了(因為這樣就要進行隨機 I/O 了，需要對獲取到的 key 進行 hash 處理到 hash table 上某個 slot 處，對于那些 miss cache 的 key 來說，就得到一個個 page 上去找)

怎么優(yōu)化呢?

轉(zhuǎn)變?yōu)?隨機訪問模式(random access pattern)，即使用 hash 索引

### Grace Hash Join

> Grace 這個詞來源于東京大學在 1980 年代開發(fā)的一個學術項目，一個叫 Grace 的數(shù)據(jù)庫機器。雖然項目不在了，但是其相關的 paper 有。作為項目的一部分，該 paper 討論了當數(shù)據(jù)無法放在內(nèi)存中時，該如何進行 hash join

那么上圖中提到的 數(shù)據(jù)庫機器 是什么?

數(shù)據(jù)庫機器/設備是一種專門為數(shù)據(jù)庫定制的一套硬件，這套硬件由那些供應商提供，該硬件能針對數(shù)據(jù)庫系統(tǒng)進行調(diào)整

> IBM: Netezza(現(xiàn)在無了)、AOL(已被 Percona 收購): Clustrix、Oracle: Oracle Exadata、Yellowbrick(2018 年初創(chuàng)公司)

它也有 2 個階段

> 在普通 Hash Join 中，只對 Outer Table 進行 hash，并為其構建一個 hash table，然后檢測 Inner Table 是否有符合 Join 條件的 tuple，如果有則進行 Join

1. build 階段

? ? 基于 hash key 來對 2 個表拆分成不同的分區(qū)，也就是 Outer Table 和 Inner Table 各自都有構建對應的 hash table，然后對匹配的分區(qū)進行 Nested-Loop Join 操作

2. probe 階段

例子

對 Outer Table 中的值進行 hash 處理，構建它的 hash table(一個 bucket chain hash table)

> linear probe hash table 中已經(jīng)存在的數(shù)據(jù)，可能會提前占據(jù)新數(shù)據(jù) hash 過后的位置，這個已經(jīng)存在的數(shù)據(jù)現(xiàn)在的位置，也不一定是當初它經(jīng)過 hash 后所在的位置(可能有過移動)，新數(shù)據(jù)經(jīng)過 hash 過后也可能會出現(xiàn)在 hash table 中很底層的位置，會觸發(fā)循序掃描

對 Inner Table 中的值進行 hash 處理，構建它的 hash table(一個 bucket chain hash table)

然后對每個分區(qū)(這里的分區(qū)就是在 hash table 里面的位置)進行編號

當構建完 hash table 后，取出同一分區(qū)中所有的 bucket，并使用一個內(nèi)嵌 for 循環(huán)對它們進行遍歷

因為已經(jīng)提前做好了 hash 分片，那么 Outer Table 就能知道它匹配的 tuple 的邊界在哪兒了

那么這里可能會出現(xiàn) hash 碰撞嗎?

可能的，因為使用的是同一個 hash 函數(shù)，2 個不同的值是有可能會 hash 到同一個 bucket 中

這個時候怎么解決呢? 可以在內(nèi)存中對這個 bucket 使用暴力查找(避開這些存在沖突的 bucket)

但是如果所有的值都 hash 到同一位置，就會產(chǎn)生溢出，這個時候又如何去解決呢?

可以通過遞歸分區(qū)(recursive partitioning)來解決

例子

首先，對 Outer Table 進行 hash，創(chuàng)建一堆 bucket，并對其進行分區(qū)

如果數(shù)據(jù)已經(jīng)溢出到很多 page/bucket 中時，就可以對這個 page/bucket 中的數(shù)據(jù)再進行一次 hash 處理(圖中的 h1 和 h2 相同，但是 hash seed 不同)，然后拆分出更多子 page/bucket

而對于 Inner Table，同樣的，要對其進行 hash(這里跟 Outer Table 用同樣的 h1 hash 函數(shù))

對于類似的值，會落在相應的分區(qū)中(比如分區(qū) 0 和分區(qū) n)，但是如果此時如果 hash 到分區(qū) 1

由于在 build 階段已經(jīng)將 Outer Table 的分區(qū) 1 拆分了，所以此時需要使用 h2 hash 函數(shù)再對分區(qū) 1 做一個 hash 處理，就可以找到需要找的那個分區(qū)

所以整體的效果如下

### Grace Hash Join 成本

3x(M + N)

> 注意這里計算的是 I/O 成本

3 是來自于 build 階段，分區(qū)時，要對 Outer Table 中 M 個 page 以及 Inner Table 中 N 個 page 進行 1 輪處理。1 輪讀取(Inner Table 的相關 page)，1 輪寫入(根據(jù) Outer Table 將結果寫入到另一個 page 上)。

然后就是進行 join，在同一分區(qū)內(nèi)對里面的 bucket 進行 Nested-Loop Join，這里要對所有的 page 進行 1 輪處理

所以加起來就是 3

對應于下圖

數(shù)字舉例

可以看到比 Sort-Merge Join 還要快一點

### 小結

算法快慢比較

## 結論

除非所操作的數(shù)據(jù)已經(jīng)提前排好序，不然 hash join 永遠比其他 join 算法要好