跳至主要内容

Joins Algorithms

在 RDBMS 中，我們常常會依據 normalization 的原則將資料分散到不同的表格中以避免記錄到重複的資料，因此在查詢時，我們就需要透過 Join 來將資料合併。

在這節中，我們主要會討論兩個 table 做 inner join 的情況 (當然這種方法也可以擴展到其他 join 方式及多個 table)，在一般情況下，我們會希望比較小的 table 作為 outer table，而比較大的 table 作為 inner table，

Join​

我們主要要討論兩個部分，分別是 :

  • Output
  • Cost Analysis Criteria

Join

Output​

Join Output

主要有兩種連結方式 :

  • Early Materialization
  • Late Materialization

Early Materialization​

將所有的資料都放到新的 tuple 中，這樣之後就不需要在回去表中讀取資料，較適合 row store。

Early Materialization

Late Materialization​

也可以只複製 join key 跟 record id，之後再去表中讀取資料，較適合 column store。

Late Materialization

Cost Analysis Criteria​

由於資料庫的資料通常無法一次性的讀進記憶體中，因此我們需要透過 join algorithms 來最大化減少硬碟 I/O 的次數，對於 join algorithms 來說，唯一的評論標準就是 I/O 數量。

接下來的資料都是基於以下的假設 :

  • 對 RR 跟 SS 兩個 table 做 join
  • RR 有 MM 個 page， mm 個 tuple
  • SS 有 NN 個 page， nn 個 tuple

Nested Loop Join​

Naive Nested Loop Join​

對於 outer table 的每一個 tuple，都會去 inner table 中找尋符合的 tuple 來比對。

cost 是 M+(m×N)M + (m \times N)

Naive Nested Loop Join

Block Nested Loop Join​

每次取 R 中的所有 tuple 出來，並與 S 的所有 tuple 比對一次。

Block Nested Loop Join

cost 是 M+(M×N)M + (M \times N)

如果我們有 B 塊 buffer ，我們可以將一塊用於 inner table 的讀入，一塊負責寫出，剩下 B - 2 則用於 outer table。

cost 則變為 M+⌈MB−2⌉×NM + \lceil \frac{M}{B-2} \rceil \times N

Index Nested Loop Join​

前面幾種較慢的原因在於我們需要多次對全表掃描，但若 inner table 在 join attribute 上有 index，我們就可以透過 index 來加速，只需掃描一次即可。

Index Nested Loop Join

cost 是 M+m×CM + m \times C，其中 C 是掃描一次 index 的 cost。

Sort-Merge Join​

主要分為兩個步驟 :

  • Sort
    • 將兩個 table 依照 join attribute 排序
  • Merge
    • 從兩個 table 的端點開始進行掃描，並進行比對
    • 如果遇到重複則需要 backtracking

Sort-Merge Join

sort cost (R) : 2M×(1+⌈log⁡B−1⌈MB⌉⌉)2M \times (1 + \lceil \log_{B-1} \lceil\frac{M}{B} \rceil \rceil)
sort cost (S) : 2N×(1+⌈log⁡B−1⌈NB⌉⌉)2N \times (1 + \lceil \log_{B-1} \lceil\frac{N}{B} \rceil \rceil)
merge cost : M+NM + N

最差的情況就是所有的 join attribute 都一樣，此時的 cost 是 M×NM \times N + sort cost。

sort meger 主要適用的情境是 :

  • 當 table 的某個 attribute 已經排好序了，如 clustered index
  • SQL 的輸出必須要排序時

Hash Join​

如果有兩個分別在 R 跟 S 的 tuple 有相同的值，則代表他們 hash 之後的值也必定相等，所以我們也可以只針對 hash 之後相同的值進行處理。

Simple Hash Join​

主要分為兩個階段 :

  • Build
    • 將 outer table 中的 join attribute 透過 hash function h1 進行 hash，並放入 hash table T 中
  • Probe
    • 將 inner table 中的 join attribute 透過 hash function h1 得到這個 tuple 在 T 中的位置，並進行比對

其中 T 的 key 是 join attribute，value 則可以是 early materialization 或 late materialization，在這個方法中，T 有可能沒辦法被放入 memory 中，導致需要進行多次 I/O，如果可以預測 T 的大小，我們也可以使用靜態 hash table。

也可以使用 bloom filter 來幫助我們快速找到不在 T 中的 tuple。

Simple Hash Join

Grace Hash Join / Partitioned Hash Join​

Grace Hash Join Grace Hash Join

主要分為兩個階段

  • Partition
    • 將兩個 table 使用同樣的 hash function 進行 partition，使有機會配對成功的 tuple 進入同一個 partition 中
  • Probe
    • 將每一組 partition 中的 tuple 進行 hash join

如果一次 partition 後還是無法放入 memory 中，我們可以進行多次 partition (recursive partitioning)，如果單一的 key 有太多的 tuple，可以使用 block nested loop join 來處理。

partition cost : 2(M+N)2(M + N) read + write both tables
probe cost : M+NM + N read both tables
total : 3(M+N)3(M + N)

Grace Hash Join

如果有些 key 非常常使用，我們可以將他們放入 memory 中並立即比較，而非溢出到硬碟中。

Conclusion​

對於大部分的 join 來說，hash join 都是比較好的選擇，除非你的 SQL 需要排序才會考慮 sort-merge join。

Join Algorithms

References​