SQL 层功能改进 - lookupJoin 的优化

一、传统 join 算法

lookupJoin 是 join 查询的一种，传统 join 算法为：

1. 遍历 A 表，读取一条数据 r

2. 遍历 B 表，对于每条数据，与 r 进行 join 操作

3. 重复 1、2 操作，直到 A 表遍历完所有数据

二、lookupJoin

现有的 lookupJoin 流程为：

1. 遍历 A 表，读取一条数据 r

2. 通过 join key 以及数据 r 构造 B 表数据取值范围

3. 通过构造的取值范围对 B 表进行读取操作，将读取出的数据与 r 进行 join 操作，返回结果

通过这样的做法，join 可减少对 B 表全表扫描的操作，提升执行效率。但是执行 lookupJoin 操作的前提是在 B 表中存在 join key 的索引，否则无法对 B 表构造取值范围。

三、分布式 lookupJoin

1. 分布式 lookupJoin 介绍：

以往 KaiwuDB 集群在执行 lookupJoin 操作时，会提取 A 数据，根据 A 表数据发送 scan 请求去别的节点读取数据。这样会导致大量结果数据集中在 A 表分布的节点，没有充分利用多节点并行执行的优势。

现在，我们将 A 表数据提前通过 hash 重分布路由到多个节点再并行执行 lookupJoin 操作；这样不仅可以提高执行效率，还可以使结果集在多个节点按照 hash key 预分布。

图 1

如图 1 所示，执行 select * from a join b on a.a = b.a 的操作时 B 表中有 join key 的索引 b_a_idx，改进后单节点 lookupJoin 变为三节点执行 lookupJoin 操作，并且使 join 结果集按照 join 列在节点间 hash 分布。

2. 分布式 lookupJoin 对分布式执行产生的效果：

分布式 lookupJoin 可以使 join 结果集按照 join 列在节点间呈现 hash 分布，大大提高了集群节点算力利用率，减少 hash 重分布的次数，缩短整体 query 执行时间。

图 2

如图 2 所示，在图 1 的基础上把 join 结果与 C 表再进行 join 查询：select * from a,b,c where a.a=b.a and a.a = c.a ，模拟复杂查询场景。由于在分布式 lookupJoin 查询后，数据按照 join key 已经在三节点上 hash 分布了，所以在执行与 C 表的 join 操作时，只需要 hash 重分布 C 表的数据，减少了 hash 重分布的次数，提高了执行效率。

3. 分布表的 lookupJoin：

分布表是一种特殊表，表中数据按某列的 hash 值分布在各个节点上，如果分布表的分布列与 hash join 列正好一致，在执行分布式 lookupJoin 时可以直接在各个节点并行执行 lookupJoin，省去了 hash 分布的操作。