在两个关系上进行连接用多线程来加速主要有两种方法哈希连接和排序合并连接。

多数OLTP DBMS都没有实现哈希连接
但是少量目标元组的索引嵌套连接和哈希连接是差不多的

连接算法的设计目标：

提高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的哈希表中，如果找到，那么输出合并好的元组。

分区阶段

两种方法

只扫描输入的关系一次，并动态产生输出

所有线程更新在一个全局的分区集合；必须用latch来同步线程；最终的结果是可用的哈希表，传输一次数据

每个线程有自己的分区；在所有线程都完成后需要整合，传输两次数据

也叫基数分区，和基数排序的原理很像，都是一位一位数字的来排。
多次扫描输入的关系；只在最后物化结果；也叫基数哈希连接
多步

对第二列数字也是递归重复，直到分区的目标数字建立

线程会扫描R(或分区)中的元组
对于每个元组，哈希它的连接属性并把它加入到哈希表中相应的bucket中（bucket只有几个cache line大小）
有两个需要考虑的问题：

一些的哈希函数介绍...

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一定在邻居范围内或不存在。

对于S中每个元组，都会哈希它的连接key检查它在由R构建的哈希表中相应的bucket里有没有对应的元组。
如果输入分区了，那么也要给每个线程进行一个独立的分区。否则需要同步他们在访问S时的游标。

在构建阶段当关键字可能在哈希表中可能不存在时创建一个布隆过滤器
在探查哈希表前线程会先检查过滤器；也叫sideways information passing

基于分区的连接在多数情况都要比不分区的算法性能好。