经典的 hash join 算法（又称 Simple Hash Join，SHJ）包括两步：

  • Build：选择两个输入 relation 中 cardinality 较小的一个（一般称其为 build relation），使用一个或一簇 hash 函数将其中的每一条记录的主键 key 值计算为一个 hash 值，然后根据 hash 值将该记录插入到一张表中，这张表就叫做 hash 表；

  • Probe：选择另一个 cardinality 较大的 relation （一般称为 probe relation），针对其中的每一条记录，使用和 build 中相同的 hash 函数，计算出相应的 hash 值，然后根据 hash 值在 hash 表中寻找到需要比较的记录，一一比较，得到最终结果。 经典的 SHJ 算法步骤简单直接，在过去的很长一段时间内是首选的 hash join 算法，但也需要拥抱变化。进入 21 世纪后，随着现代处理器的发展逐渐遇到了 frequency wall, memory wall 等瓶颈，处理器从高频单核架构逐渐演化为较低频的多核架构。此外，随着内存容量的不断增高，纯内存的分析型数据库查询逐渐流行，join 算法的执行开销瓶颈从 I/O 逐渐变为 CPU 和内存开销。因为 SHJ 算法中往 hash 表中插入记录和从 hash 表中读取记录往往都有大量的随机内存读写，而随机访问的代价在各个软硬件层面上都比顺序访问高，SHJ 算法在多核 CPU 处理器上逐渐尽显疲态。

    Partitioned Hash Join

  • 只对单个 relation 进行分区，还是对两个 relation 同时进行分区？

  • 对于一个 relation，将其分出多少个区来？

  • 锁开销：在多线程的 SHJ 算法实现中，由于记录未经过分区，多个线程将操作一个相同的 hash 表，那么很有可能出现多个线程争抢同一个 hash bucket 的情况。为了实现线程间的同步，往往需要为每一个 hash bucket 加锁，那么等锁的开销就会成为一大热点。为了减少锁竞争，可以提高 hash bucket 的数量，减少线程的数量，或者使用乐观的无锁算法。此处往往存在各种 trade-off，比如更多的 hash bucket 数量对于一些 hash 表实现来说（如 linear hash 表）会带来更大的内存空间占用。

  • Cache miss：当 hash 表的数据量超过处理器 cache 大小的时候，对 hash 表的频繁访问有很大概率会遭受 cache miss，不得不访问内存。以 Intel 的某款 CPU 处理器为例，单个 CPU 上，L1 cache 有 32 KB 的数据空间（对比指令 cache），L2 cache 有 256 KB；同时存在多个 CPU 共享的 60 MB 的 L3 cache。对于 GB 级别以上的 hash 表来说，如此的 cache 大小杯水车薪。常见的有效解法就是使用 PHJ 算法，将 relation 不断分区，直至一个分区的 hash 表可以放进 cache 中，但此处分区本身也拥有较高的执行代价开销。实践中依然需要仔细处理此处的 trade-off。有的研究认为在拥有超线程能力的处理器中，因为同个 CPU core 上的多个（如 2 个）硬件线程可以轮流执行，那么可以通过执行一个线程中的计算指令来隐藏另一条线程中的访存 latency 开销，从而减少 cache miss 对总执行代价带来的影响。但对于数据库中的各种操作来说，它们绝大部分的工作往往就是读写数据，这样一来通过计算隐藏访存开销的效果就因为机会不足而十分有限了。
  • TLB miss：在一个 CPU 处理器的内存管理单元（MMU）中，有一个 Translation Lookaside Buffer （TLB）。TLB 往往缓存了最近的从虚拟内存地址到其相应的内存页的转换。如果一个访存操作命中了 TLB，那么就可以直接获得相应的内存页；反之，就必须去内存页表中查询相应的内存页，此处代价就高出很多了。由于 TLB 的 slot 条数是固定的，对于 PHJ 算法来说，如果一次分区操作的扇出（目标分区数量，fanout）高于 TLB 的 slot size，那么除去第一次访存时的 compulsory miss 以后，后续访存也会出现 TLB miss；fanout 越高，TLB miss 越多，多到我们不如我们少分一些区的地步。一种调优办法是进行 multi-pass partition，每个 pass 少分一些区，但是多跑几个 pass 来完成同样的分区总数。显然，multi-pass 会带来更多重复的内存读写，所以此处也存在 trade-off，需要根据实际情况进行优化。

  • ……

    从中可以看出，对于一个装有 16 个 32 位整形数的 512 位向量来说，虽然表面上看一条读指令在这 16 个数（可以理解为地址 offset）应该同时并行执行，但指令内部其实是存在一个 for loop 的。也就是说，假如这个 for loop 的第 5 个和第 10 个 iteration 都往相同的 offset 写入数据，那么靠后的第 10 个 iteration 会覆盖前面的第 5 个 iteration 写入的结果。 利用这个特性，对于一个存储了 16 个 hash 值（每一个 hash 值对应 array 中的一个 offset 位置）的向量 V0 来说，我们只需要把它按照 scatter 的方式先写进内存中，再通过 gather 读回来获得 V1，然后比较 V0 和 V1 的内容，凡是不相等的 SIMD lane 即为因 hash 冲突而被覆盖的地方。我们只需利用 mask 将其标记出来，放在待处理的向量中留到下个 iteration 再插入 hash 表即可。具体的实现举例如下：