在兩個(gè)關(guān)系上進(jìn)行連接用多線程來(lái)加速主要有兩種方法哈希連接和排序合并連接。
多數(shù)OLTP DBMS都沒(méi)有實(shí)現(xiàn)哈希連接
但是少量目標(biāo)元組的索引嵌套連接和哈希連接是差不多的
連接算法的設(shè)計(jì)目標(biāo)：
- 最小化同步：防止執(zhí)行的時(shí)候用latch
- 最小化內(nèi)存訪問(wèn)開(kāi)銷(減少未命中)：保證對(duì)于worker線程數(shù)據(jù)總是本地化的；重用已在CPU cache的數(shù)據(jù)
提高cache
影響DBMS cache未命中的因素：
- Cache + TLB容量：TLB是translation and localization buffer，用于將虛擬地址映射到物理地址，可能會(huì)因?yàn)轭l繁交換堵塞
- 時(shí)間和空間
非隨機(jī)訪問(wèn)(掃描)：集群數(shù)據(jù)到cache line；每個(gè)cache line執(zhí)行更多的操作
隨機(jī)訪問(wèn)(查找)：把數(shù)據(jù)進(jìn)行劃分適應(yīng)cache+TLB
并行哈希連接
對(duì)于OLAP DBMS哈希連接是最重要的操作
充分利用多核來(lái)加速哈希連接算法是至關(guān)重要的——讓所有的核都跑起來(lái)，又不想要內(nèi)存受限
哈希連接R?S氛圍三個(gè)階段：劃分（可以沒(méi)有）用哈希函數(shù)在連接關(guān)鍵字上將R和S的元組進(jìn)行分區(qū)（為下一步索引的構(gòu)建以及最后的探查做準(zhǔn)備）；構(gòu)建，掃描關(guān)系R在連接關(guān)鍵字上創(chuàng)建一個(gè)哈希表；探查，對(duì)于S中的每個(gè)元組，查找它的連接關(guān)鍵字是不是在R的哈希表中，如果找到，那么輸出合并好的元組。
分區(qū)階段
兩種方法
Non-Blocking Partitioning
只掃描輸入的關(guān)系一次，并動(dòng)態(tài)產(chǎn)生輸出
shared Partition
所有線程更新在一個(gè)全局的分區(qū)集合；必須用latch來(lái)同步線程；最終的結(jié)果是可用的哈希表，傳輸一次數(shù)據(jù)
私有分區(qū)
每個(gè)線程有自己的分區(qū)；在所有線程都完成后需要整合，傳輸兩次數(shù)據(jù)
Blocking Partitioning(Radix)
也叫基數(shù)分區(qū)，和基數(shù)排序的原理很像，都是一位一位數(shù)字的來(lái)排。
多次掃描輸入的關(guān)系；只在最后物化結(jié)果；也叫基數(shù)哈希連接
多步
-
掃描R計(jì)算出在某個(gè)偏移量基數(shù)的每個(gè)哈希鍵的元組數(shù)量的直方圖
統(tǒng)計(jì)第一位的數(shù)字，CPU0有兩個(gè)0兩個(gè)1，CPU2有1個(gè)0,3個(gè)1.
-
用直方圖通過(guò)計(jì)算前綴和來(lái)決定輸出的偏移量
先0后1，按照前綴和計(jì)算輸出偏移量
-
再次掃描R，根據(jù)哈希關(guān)鍵字進(jìn)行分區(qū)
對(duì)第二列數(shù)字也是遞歸重復(fù)，直到分區(qū)的目標(biāo)數(shù)字建立
構(gòu)建階段
線程會(huì)掃描R(或分區(qū))中的元組
對(duì)于每個(gè)元組，哈希它的連接屬性并把它加入到哈希表中相應(yīng)的bucket中（bucket只有幾個(gè)cache line大?。?br>
有兩個(gè)需要考慮的問(wèn)題：
- 哈希表：怎么把較大的關(guān)鍵字空間映射到小區(qū)域；在快與沖突率之間的取舍
- 哈希方案：鏈?zhǔn)健⒕€性探測(cè)、環(huán)...
一些的哈希函數(shù)介紹...
Hashing Schemes
1.鏈?zhǔn)焦?br>
維持一個(gè)bucket的鏈表
通過(guò)把有一樣哈希值的元素放到同一個(gè)bucket中
在查找時(shí)，看一個(gè)元素有沒(méi)有，需要掃描其哈希值對(duì)應(yīng)的bucket；插入和刪除也是
- 線性探測(cè)哈希
就是一個(gè)slots的大表
通過(guò)線性探測(cè)找下一個(gè)空的slot來(lái)解決沖突
找一個(gè)元素在不在，需要哈希到表中的一個(gè)位置開(kāi)始掃描；表中需要存一個(gè)ke知道合適停止，否則需要掃描整個(gè)表；插入與刪除與查找一致
為了減少連接時(shí)的比價(jià)，減少哈希值的沖突是至關(guān)重要的。
鏈?zhǔn)焦４蟾判枰猂中元素的一般的slots。
-
Robin Hood Hashing
線性探測(cè)哈希的變體，由于不均勻的key，會(huì)導(dǎo)致比較密集的key產(chǎn)生大量的沖突，Robin Hood Hashing就是把 空閑的slot轉(zhuǎn)移給沖突較多的slot。
每個(gè)key都會(huì)track它在表中的最佳位置（哈希值對(duì)應(yīng)的位置）
插入時(shí)，如果第一個(gè)key比第二個(gè)key里最佳位置更遠(yuǎn)，那么會(huì)占住別的key的位置？（使得總體的距離最佳位置的和比較?。?/p>
Hopscotch哈希
線性探索哈希變體，key可以在鄰居內(nèi)移動(dòng)
一個(gè)鄰居是表中的slot的范圍
例句的大小是一個(gè)可設(shè)置的常數(shù)
key一定在鄰居范圍內(nèi)或不存在。
- Cuckoo 哈希
多個(gè)哈希函數(shù)多個(gè)表
插入時(shí)，檢查哪個(gè)表對(duì)應(yīng)的slot是空的，直接放進(jìn)去；如果沒(méi)有空的，就驅(qū)除一個(gè)，把這個(gè)被驅(qū)除出去的用其他哈希函數(shù)找一個(gè)新地方存。
查找的時(shí)間復(fù)雜度是O(1)因?yàn)槊總€(gè)表只用查一個(gè)位置。
線程得保證移動(dòng)key的時(shí)候不會(huì)陷入無(wú)止境的循環(huán)。
如果發(fā)現(xiàn)循環(huán)，可以用新的哈希函數(shù)重新構(gòu)建整個(gè)哈希表
Probe階段
對(duì)于S中每個(gè)元組，都會(huì)哈希它的連接key檢查它在由R構(gòu)建的哈希表中相應(yīng)的bucket里有沒(méi)有對(duì)應(yīng)的元組。
如果輸入分區(qū)了，那么也要給每個(gè)線程進(jìn)行一個(gè)獨(dú)立的分區(qū)。否則需要同步他們?cè)谠L問(wèn)S時(shí)的游標(biāo)。
在構(gòu)建階段當(dāng)關(guān)鍵字可能在哈希表中可能不存在時(shí)創(chuàng)建一個(gè)布隆過(guò)濾器
在探查哈希表前線程會(huì)先檢查過(guò)濾器；也叫sideways information passing
基于分區(qū)的連接在多數(shù)情況都要比不分區(qū)的算法性能好。
