在两个关系上进行连接用多线程来加速主要有两种方法哈希连接和排序合并连接。
多数OLTP DBMS都没有实现哈希连接
但是少量目标元组的索引嵌套连接和哈希连接是差不多的
连接算法的设计目标：
- 最小化同步：防止执行的时候用latch
- 最小化内存访问开销(减少未命中)：保证对于worker线程数据总是本地化的；重用已在CPU cache的数据
提高cache
影响DBMS cache未命中的因素：
- Cache + TLB容量：TLB是translation and localization buffer，用于将虚拟地址映射到物理地址，可能会因为频繁交换堵塞
- 时间和空间
非随机访问(扫描)：集群数据到cache line；每个cache line执行更多的操作
随机访问(查找)：把数据进行划分适应cache+TLB
并行哈希连接
对于OLAP DBMS哈希连接是最重要的操作
充分利用多核来加速哈希连接算法是至关重要的——让所有的核都跑起来，又不想要内存受限
哈希连接R⨝S氛围三个阶段：划分（可以没有）用哈希函数在连接关键字上将R和S的元组进行分区（为下一步索引的构建以及最后的探查做准备）；构建，扫描关系R在连接关键字上创建一个哈希表；探查，对于S中的每个元组，查找它的连接关键字是不是在R的哈希表中，如果找到，那么输出合并好的元组。
分区阶段
两种方法
Non-Blocking Partitioning
只扫描输入的关系一次，并动态产生输出
shared Partition
所有线程更新在一个全局的分区集合；必须用latch来同步线程；最终的结果是可用的哈希表，传输一次数据
私有分区
每个线程有自己的分区；在所有线程都完成后需要整合，传输两次数据
Blocking Partitioning(Radix)
也叫基数分区，和基数排序的原理很像，都是一位一位数字的来排。
多次扫描输入的关系；只在最后物化结果；也叫基数哈希连接
多步
-
扫描R计算出在某个偏移量基数的每个哈希键的元组数量的直方图
统计第一位的数字，CPU0有两个0两个1，CPU2有1个0,3个1.
-
用直方图通过计算前缀和来决定输出的偏移量
先0后1，按照前缀和计算输出偏移量
-
再次扫描R，根据哈希关键字进行分区
对第二列数字也是递归重复，直到分区的目标数字建立
构建阶段
线程会扫描R(或分区)中的元组
对于每个元组，哈希它的连接属性并把它加入到哈希表中相应的bucket中（bucket只有几个cache line大小）
有两个需要考虑的问题：
- 哈希表：怎么把较大的关键字空间映射到小区域；在快与冲突率之间的取舍
- 哈希方案：链式、线性探测、环...
一些的哈希函数介绍...
Hashing Schemes
1.链式哈希
维持一个bucket的链表
通过把有一样哈希值的元素放到同一个bucket中
在查找时，看一个元素有没有，需要扫描其哈希值对应的bucket；插入和删除也是
- 线性探测哈希
就是一个slots的大表
通过线性探测找下一个空的slot来解决冲突
找一个元素在不在，需要哈希到表中的一个位置开始扫描；表中需要存一个ke知道合适停止，否则需要扫描整个表；插入与删除与查找一致
为了减少连接时的比价，减少哈希值的冲突是至关重要的。
链式哈希大概需要R中元素的一般的slots。
-
Robin Hood Hashing
线性探测哈希的变体，由于不均匀的key，会导致比较密集的key产生大量的冲突，Robin Hood Hashing就是把 空闲的slot转移给冲突较多的slot。
每个key都会track它在表中的最佳位置（哈希值对应的位置）
插入时，如果第一个key比第二个key里最佳位置更远，那么会占住别的key的位置？（使得总体的距离最佳位置的和比较小）
-
Hopscotch哈希
线性探索哈希变体，key可以在邻居内移动
一个邻居是表中的slot的范围
例句的大小是一个可设置的常数
key一定在邻居范围内或不存在。
- Cuckoo 哈希
多个哈希函数多个表
插入时，检查哪个表对应的slot是空的，直接放进去；如果没有空的，就驱除一个，把这个被驱除出去的用其他哈希函数找一个新地方存。
查找的时间复杂度是O(1)因为每个表只用查一个位置。
线程得保证移动key的时候不会陷入无止境的循环。
如果发现循环，可以用新的哈希函数重新构建整个哈希表
Probe阶段
对于S中每个元组，都会哈希它的连接key检查它在由R构建的哈希表中相应的bucket里有没有对应的元组。
如果输入分区了，那么也要给每个线程进行一个独立的分区。否则需要同步他们在访问S时的游标。
在构建阶段当关键字可能在哈希表中可能不存在时创建一个布隆过滤器
在探查哈希表前线程会先检查过滤器；也叫sideways information passing
基于分区的连接在多数情况都要比不分区的算法性能好。
网友评论