共计 3675 个字符，预计需要花费 10 分钟才能阅读完成。
Hash Join 是在进行多表连贯时罕用的形式之一。那如何在 openLooKeng 上构建并实现 Hash Join？openLooKeng 反对的 Join 类型有哪些？本期，社区小伙伴将分享[openLooKeng Hash Join 实现原理]，从构建到应用，内容非常具体，心愿对大家有帮忙。
1 openLooKeng Join 概述
为了更好的介绍 join，咱们创立两个非常简单的表 t1 和 t2。执行的 SQL 语句如下：
create table t1(id bigint, value bigint);insert into t1 values(1, 11);insert into t1 values(2, 22);insert into t1 values(3, 33);insert into t1 values(4, 44);
create table t2(id bigint, value bigint);insert into t2 values(1, 111);insert into t2 values(2, 11);insert into t2 values(3, 333);insert into t2 values(4, 33);
openLooKeng 的 join 有四类：
1）Lookup Join 大部分类型的 Join 都由 Lookup Join 实现。例如咱们执行 SQL 语句如下：select * from t1 inner join t2 on t1.value=t2.value;
其中，执行 join 所在 stage 波及算子如下图所示：
▲ 图 1 -1 Lookup Join
实现 Join 的算子是 HashBuilderOperator 和 LookupJoinOperator。而本文行将介绍 Hash Join 的原理，也就是这两个算子的实现原理。
2）Nested Loop Join 执行 SQL 语句“select * from t1 join t2 on t1.value > t2.value;”，join 所在 stage 波及算子如下图所示，其中实现 Join 的算子是 NestedLoopBuilderOperator 和 NestedLoopJoinOperator。
▲ 图 1 -2 Nested Loop Join
3）Hash Semi Join 执行 SQL 语句“select * from t1 where value in (select value from t2);”，join 所在 stage 波及算子如下图所示，其中实现 join 的算子是 SetBuilderOperator 和 HashSemiJoinOperator。
▲ 图 1 -3 Hash Semi Join
4）Spatial Join 执行 SQL 语句“select * from t1, t2 where ST_distance(ST_Point(t1.id, t1.value), ST_Point(t2.id, t2.value)) <= 10;”，join 所在 stage 波及算子如下图所示，其中实现 join 的算子是 SpatialIndexBuilderOperator 和 SpatialJoinOperator。
▲ 图 1 -4 Spatial Join
本博客关注的是 Hash Join 的实现原理剖析，其余类型的 Join 后续开展介绍。
2 openLooKeng Hash Join 实现原理
通常，咱们称 Join 操作的右表为 build 表，左表为 probe 表。Hash Join 对应的逻辑执行打算为 JoinNode，物理执行打算则由两个算子实现工作，其中 HashBuilderOperator 依据 build 表来构建 Hash Table，LookupJoinOperator 实现对 probe 表逐行去 Hash Table 探测，找到匹配行。
2.1 build 侧数据 partition
数据进入 HashBuilderOperator 之前曾经由 LocalExchangeSinkOperator 和 LocalExchangeSourceOperator 实现数据 partition，即 join key 的哈希值雷同的数据进入同一个 HashBuilderOperator。LocalExchangeSinkOperator 和 LocalExchangeSourceOperator 对应的逻辑执行打算的 ExchangeNode。在 openLooKeng 中，ExchangeNode 和 JoinNode 的模型关系如图 2 - 1 所示。
▲ 图 2 -1 LocalExchange 与 LookupJoin 的模型关系
图 2 - 1 中，有 16 个 partition，LocalExchangeSinkOperator 接管 page 后，依据 Join key 计算 hash 值，将 hash 值雷同的数据组成新 page，再依据 hash 值计算 partition index，抉择相应的 LocalExchangeSourceOperator。而 LocalExchangeSourceOperator 是 HashBuilderOperator 的上游算子，因而进入 HashBuilderOperator 的数据是曾经 partition 过后的数据。
2.2 Hash Join 类图
▲ 图 2 -2 Hash Join 类图
图 2 - 2 展现了 Hash Join 所波及的类图，其中比拟重要的类有以下几个：
1）HashBuilderOperatorFactory/HashBuilderOperator，针对 build 表构建 Hash Table；
2）JoinHash，Hash Table 承载类；
3）LookupJoinOperatorFactory/LookupJoinOperator，负责 probe 表逐行探测；
4）LookupJoinPageBuilder，负责构建输入 page。
2.3 Hash Table 构建
HashBuilderOperator 负责对 build 表构建 Hash Table。它的根本流程是：1）addInput() 时将 Page 累积在内存中；
2）finish()时，则创立 Hash Table；
3）不再阻塞 LookupJoinOperator，即 LookupJoinOperator 能够开始解决。咱们重点讲一下 Hash Table 的构建。
JoinHash 中有两个十分重要的类：PagesHash 和 PositionLinks。
咱们先来看 PagesHash。PagesHash 的 field 有：
1）addresses，对 page 内每一行数据进行地址编码，编码公示为“pageIndex « 32 | rowIndex”，如有 2 个 page，每个 page 有 2 行，则 addresses 内寄存的是 0，1，4294967296，4294967297；
2）PageHashStrategy，会将原始的数据保留下来；
3）key 数组，能够了解为 hash 表，依据某行 join key 计算失去 hash 值，再将 hash 值进行 hash 计算失去一个 hash 表的 offset，如果这个 offset 上没有值则寄存该行的 address，例如 addresses 中 1 这个地址对应的行计算出 offset 为 6，而这个地位没有被占用，则 key[6] = 1；
4）mask，掩码，用于对数组 key 求 offset；
5）positionToHashes，byte 数组，依据 join key 计算 hash 值，然而只保留低位的 byte。PositionLinks 解决的是，当 hash 值抵触且原始值也雷同时，将满足这些状况的数据 address 应用数组链起来。外围代码片段如下：
上面咱们举例来说明。
如图所示，join key 只有 1 个，page 只有 1 个，其值如①所示。对这些行进行地址编码，则编码后地址如②所示。Hash table 构建步骤：1）对原始数据进行 hash 计算，后果如③所示；2）逐行解决 addresses：
最终失去的 key 数组如④所示，失去的 positionLinks 如⑤所示。
2.4 Hash Table 应用
HashBuilderOperator 构建完 hash table 后，LookupJoinOperator 能力开始解决数据进行探测。而 LookupJoinOperator 应用 hash table 的外围代码片段如下：
Hash table 应用步骤：
1）对原始数据进行 hash 计算失去 rawHash；
2）对 rawHash 再进行 hash 计算失去其在 hash table 的 offset，即 pos；
3）若 key[pos]为 -1，则没有匹配；
4）若 key[pos]不是 -1，则 hash 值匹配，若原始数据是否相等，相等则齐全匹配上，返回 key[pos]，即原始数据的地址 address；若原始数据不相等则 pos 加 1 再循环判断。
3 总结
本文介绍了 openLooKeng 反对的 join 类型，并开展介绍了 Lookup join 的 partition，而后重点介绍了 hash table 的构建和应用过程，但其实 Lookup Join 的内容不止这些，比方 HashBuilderOperator 和 LookupJoinOperator 如何实现同步，LookupJoinOperator 的 probe 后的输入数据如何结构，非等值的 join 又是如何实现的，请期待后续的文章！
