Join 操作一般有三種實現(xiàn)策略

1. nested loop -- 2層循環(huán) 遍歷 R 和 S 表 (廣泛使用)
2. sort-merge -- 先對R祥山，S 表進行排序瘦真， 在歸并
3. hash-based 基于哈希

Nested Loop Join （連接操作最基本的算法）

Using a page-by-page scan of the outer relation.
For each outer page, do a page-by-page scan of the inner relation
選 R，S 中較小的一個 作為 the outer relation， 較大的作為 the inner relation

Result = {}
// 在 R 表中 讀 1 塊 block 進入內(nèi)存 
for each page i in R {
   pageR = getPage(R,i)
// 在 S表中 讀 1 塊block 進入內(nèi)存
   for each page j in S {
      pageS = getPage(S,j)
      for each pair of tuples tR,tS
                       from pageR,pageS {
         if (tR.a == tS.b)
            Result = Result ∪ (tR:tS)
}  }  }

基于塊的嵌套循環(huán)的連接算法就是，每次讀R表中一個block進入內(nèi)存， 就把S表中备籽，所有block依次讀入內(nèi)存進行比較操作， 所以S表一共被讀入了 次分井。

I/O復(fù)雜度
cost = （一般把小的表 作為）

內(nèi)存需求：
這種算法的內(nèi)存需求很小车猬， 最低只要 3 block , 2塊分別給R，S作為input, 一塊作為output輸出result.

Block Nested Loop Join

如果 兩個關(guān)系 都不能存入內(nèi)存 ,

image.png

1. 將 R表 切分為 大小為 N-2( N：memory buffer ) 的若干個子集合 --- 個子集合
2. 內(nèi)存中 N-2為 , 1 為 , 1 為 output buffer.

Nested Loop join算法內(nèi)存需求很低尺锚，并沒有充分利用內(nèi)存诈唬。
如果能把R，S中較小的一個表完全讀入內(nèi)存缩麸， 那么只要1 個block 遍歷 一遍S表就可以完成join 铸磅， 這也是理論上 R Join S 的最低 I/O 開銷---, 需要滿足 .

如果 , 我們就依次讀入 N-2 塊 R page, 在 遍歷 S 表， 如此重復(fù)杭朱，一共需要 次 讀入 S 表阅仔。
所以總的 I/O 復(fù)雜度為

內(nèi)存需求：
這里明顯是 內(nèi)存拉滿，減少 buffer 會導(dǎo)致 讀入R 表輪次上升弧械，從而導(dǎo)致 cost 上升八酒。

Index Nested Loop Join

上面 2種算法 有一個問題 ， 都要線性的依次讀入整個S表的所有 page 到內(nèi)存與R比較才能防止遺漏刃唐，如果 能在S表上加入索引（稀疏 或者稠密索引）, 依靠索引能減少讀入 S表的page 數(shù)量羞迷， 這樣就可以節(jié)省 I/O開銷。

for each tuple r in relation R {
    use index to select tuples
        from S where s.j = r.i
    for each selected tuple s from S {
        add (r,s) to result
}   }

I/O 復(fù)雜度為

表示根據(jù)索引找到與該 記錄相match的 所需要的一次開銷画饥。 比如衔瓮，S表該連接鍵上有個 cluster B+ 樹索引， 在B+樹上檢索出 相應(yīng)的 地址需要2 次操作抖甘， 根據(jù)地址找到對應(yīng)記錄 并與 相比較需要1 次操作热鞍， 那么 就等于2+1 = 3.

Sort-merge Join

Sort-merge 算法分2步

1. 對 R， S 表進行排序 （多路歸并排序）
   
   
   總cost :

2.兩個排序表的merge
- Best case :
- Worst case:

grace hash join

grace hash join 為了保證散列函數(shù)的性能， 對內(nèi)存有最低要求薇宠，即：
.

1. 使用 散列函數(shù) h1 對 R偷办， S 進行分區(qū)。

   
   
   Partition phase

2. 使用散列函數(shù) h2 把R表的所有分區(qū)都映射入內(nèi)存中 澄港，再依次映射S表的每一個分區(qū).

   
   
   Probe/join

Cost of grace hash join:

1. partition relation R : 一讀一寫
2. partition relation S: 一讀一寫
   3.probe/join :

總開銷：

hybird hash join