多数OLTP DBMS都没有实现哈希连接
但是少量目标元组的索引嵌套连接和哈希连接是差不多的
连接算法的设计目标：
提高cache
影响DBMS cache未命中的因素：
对于OLAP DBMS哈希连接是最重要的操作
充分利用多核来加速哈希连接算法是至关重要的——让所有的核都跑起来，又不想要内存受限
哈希连接R⨝S氛围三个阶段：划分（可以没有）用哈希函数在连接关键字上将R和S的元组进行分区（为下一步索引的构建以及最后的探查做准备）；构建，扫描关系R在连接关键字上创建一个哈希表；探查，对于S中的每个元组，查找它的连接关键字是不是在R的哈希表中，如果找到，那么输出合并好的元组。
两种方法
只扫描输入的关系一次，并动态产生输出
所有线程更新在一个全局的分区集合；必须用latch来同步线程；最终的结果是可用的哈希表，传输一次数据
每个线程有自己的分区；在所有线程都完成后需要整合，传输两次数据
也叫基数分区，和基数排序的原理很像，都是一位一位数字的来排。
多次扫描输入的关系；只在最后物化结果；也叫基数哈希连接
多步
对第二列数字也是递归重复，直到分区的目标数字建立
线程会扫描R(或分区)中的元组
对于每个元组，哈希它的连接属性并把它加入到哈希表中相应的bucket中（bucket只有几个cache line大小）
有两个需要考虑的问题：
一些的哈希函数介绍...
1.链式哈希
维持一个bucket的链表
通过把有一样哈希值的元素放到同一个bucket中
在查找时，看一个元素有没有，需要扫描其哈希值对应的bucket；插入和删除也是
为了减少连接时的比价，减少哈希值的冲突是至关重要的。
链式哈希大概需要R中元素的一般的slots。
key一定在邻居范围内或不存在。
对于S中每个元组，都会哈希它的连接key检查它在由R构建的哈希表中相应的bucket里有没有对应的元组。
如果输入分区了，那么也要给每个线程进行一个独立的分区。否则需要同步他们在访问S时的游标。
在构建阶段当关键字可能在哈希表中可能不存在时创建一个布隆过滤器
在探查哈希表前线程会先检查过滤器；也叫sideways information passing
基于分区的连接在多数情况都要比不分区的算法性能好。
slots/meter槽/表
slots[英][s'lɒts][美][s'lɒts]
n.（机器或工具上的）狭缝( slot的名词复数 )<非正>（在表册、系统等中所占的）位置（投放或插入东西的）窄缝（名单、日程安排或广播节目表中的）位置
v.把…放入狭长开口中( slot的第三人称单数 )把…纳入其中
meter[英][ˈmi:tə(r)][美][ˈmitɚ]
n.计量器计量仪
v.用仪表测量
