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：
Value=1，Address=0，pos=6， key[pos] == -1 => key[6] = 0 Value=2，Address=1，pos=4， key[4] == -1 => key[4]=1 Value=1，Address=2，pos=6， key[6] != -1 => key[6]=2, positionLinks[2]=0 Value=2，Address=3，pos=4， key[4] != -1 => key[4]=3, positionLinks[3]=1 Value=3，Address=4，pos=3， key[3] == -1 => key[3]=4 Value=4，Address=5，pos=7， key[7] == -1 => key[7]=5 Value=5，Address=6，pos=10，key[10] == -1 => key[10]=6 Value=6，Address=7，pos=9， key[9] == -1 => key[9]=7 Value=7，Address=8，pos=13，key[13] == -1 => key[13]=8 Value=1，Address=9，pos=6， key[6] != -1 => key[6]=9, positionLinks[9]=2
最终得到的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又是如何实现的，请期待后续的文章！
本文作者：刘玉
转载请联系openLooKeng小助手（微信：openLooKengoss）
欢迎关注官方公众号 openLooKeng
openLooKeng是一款开源的高性能大数据多源分析引擎，提供统一的SQL接口，具备跨数据源\数据中心分析能力，为大数据用户提供极简的数据分析体验。如果您有任何想要交流的，欢迎在社区代码仓内提Issue；也欢迎加小助手微信，进入专属技术交流群。
社区官网 https://openlookeng.io
代码仓地址
https://gitee.com/openlookeng
https://github.com/openlookeng
![]()
