Join 是关系数据库中非常重要的一种操作。数据库对于Join通常有三种主要的实现: Merge Join, Nested-loop Join, Hash Join。其中 Hash Join 适用于带有等值条件情况，由于 Hash Join 的算法复杂度在平均情况下是 O(n)，通常在大规模数据做Hash Join是最优的选择。
In-Memory Hash Join
为了减少内存使用量，我们通常选择小表作为 hash 表，大表做为 probe 表。另外我们发现如果 hash 冲突比较严重的话，最极端的例子 hash 表所有的值都一样的话，那么单个 hash bucket (hash桶)内部的 Hash Join 就会退化成 Nested-Loop Join。
Grace Hash Join
当 build 表数据量比较大，无法在内存中全部存下的时候，我们需要利用磁盘来完成 join 操作。最直观的想法，就是分片加载 build 表。每加载一个 build 表的一个分片，然后从头到尾扫描一遍probe表，进行一次 probe 操作，完成 join 操作。这样做的问题是扫描磁盘的次数过多。总的扫描量是build表 + n * probe 表。n 是 build 表的分片个数。
Hybrid Hash Join
Hybrid Hash Join 结合了 In-memory Hash Join 和 Grace Hash Join 的优点。Hybrid Hash Join 是 Grace Hash Join 的一种改进，在 Grace Hash Join 第一张表分片的过程中，尽量把越多的完整的分片保留在内存中。这样在第二张表做分片的过程中，就可以同时对留在内存中的分片做 probe 操作，这样省去了留在内存中分片的刷盘操作，同时第二张表对应的分片也不需要刷盘，提高效率。如果第一张表所有的分片都能留在内存中，其实就是 In-memory Hash Join。我们把第一张表叫做 build table，第一张表分片的过程叫做 build phase。第二张表叫做 probe table，第二张表分片的过程叫做 probe phase。那么我们详细介绍两个过程。
