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又是如何实现的，请期待后续的文章！