在介绍 Index Lookup Join 之前,我们首先看一下什么是 Nested Loop Join(NLJ)。 NLJ 的具体定义可以参考 Wikipedia。NLJ 是最为简单暴力的 Join 算法,其执行过程简述如下:
NLJ 算法实现非常简单并且 join 结果的顺序与 Outer 表的数据顺序一致。
但是存在性能上的问题:执行过程中,对于每一条 OuterRow,我们都需要对 Inner 表进行一次全表扫操作,这将消耗大量时间。
为了减少对于 Inner 表的全表扫次数,我们可以将上述步骤 1 优化为每次从 Outer 表中读取一个 batch 的数据,优化后的算法即 Block Nested-Loop Join(BNJ),BNJ 的具体定义可以参考 Wikipedia。
对于 BNJ 算法,我们注意到,对于 Outer 表中每个 batch,我们并没有必要对 Inner 表都进行一次全表扫操作,很多时候可以通过索引减少数据读取的代价。Index Lookup Join(ILJ) 在 BNJ 基础上进行了改进,其执行过程简述如下:
TiDB 的 ILJ 算子是一个多线程的实现,主要的线程有: Main Thead,Outer Worker,和 Inner Worker:
* 启动 Outer Worker 及 Inner Workers
* 读取 Outer Worker 构建的 task,并对每行 Outer 数据在对应的哈希表中 probe
* 对 probe 到的数据进行 join 并返回执行结果
这个算子有如下特点:
TiDB 中 ILJ 的执行阶段可划分为如下图所示的 5 步:
1. 启动 Outer Worker 及 Inner Workers
这部分工作由 startWorkers 函数完成。该函数会 启动一个 Outer Worker 和多个 Inner Worker 和 多个 Inner Worker。Inner Woker 的数量可以通过 tidb_index_lookup_concurrency
这个系统变量进行设置,默认为 4。
2. 读取 Outer 表数据
这部分工作由 buildTask 函数完成。此处主要注意两点:
第一点,对于每次读取的 batch 大小,如果将其设置为固定值,则可能会出现如下问题:
因此,我们通过指数递增的方式动态控制 batch 的大小(由函数 increaseBatchSize 完成),以避免上述问题,batch size 的最大值由 session 变量 tidb_index_join_batch_size
控制,默认是 25000。读取到的 batch 存储在 lookUpJoinTask.outerResult 中。
第二点,如果 Outer 表的过滤条件不为空,我们需要对 outerResult 中的数据进行过滤(由函数 VectorizedFilter 完成)。outerResult 是 Chunk 类型(Chunk 的介绍请参考 TiDB 源码阅读系列文章(十)),如果对满足过滤条件的行进行提取并重新构建对象进行存储,会带来不必要的时间和内存开销。VectorizedFilter
函数通过一个长度与 outerResult 实际数据行数相等的 bool slice 记录 outerResult 中的每一行是否满足过滤条件以避免上述开销。 该 bool slice 存储在 lookUpJoinTask.outerMatch 中。
3. Outer Worker 将 task 发送给 Inner Worker 和 Main Thread
Inner Worker 需要根据 Outer 表每个 batch 的数据,构建 Inner 表的数据扫描范围并读取数据,因此 Outer Worker 需要将 task 发送给 Inner Worker。
如前文所述,ILJ 多线程并发执行,且 Join 结果的顺序与 Outer 表的数据顺序一致。 为了实现这一点,Outer Worker 通过管道将 task 发送给 Main Thread,Main Thread 从管道中按序读取 task 并执行 Join 操作,这样便可以实现在多线程并发执行的情况下的保序需求。
4. Inner Worker 读取 inner 表数据
这部分工作由 handleTask 这个函数完成。handleTask 有如下几个步骤:
task.innerResult
中。task.lookupMap
中。上述步骤完成后,Inner Worker 向 task.doneCh
中发送数据,以唤醒 Main Thread 进行接下来的工作。
5. Main Thread 执行 Join 操作
这部分工作由 prepareJoinResult 函数完成。prepareJoinResult 有如下几个步骤:
CREATE TABLE `t` (
`a` int(11) DEFAULT NULL,
`pk` int(11) NOT NULL AUTO_INCREMENT,
PRIMARY KEY (`pk`)
);
CREATE TABLE `s` (
`a` int(11) DEFAULT NULL,
KEY `idx_s_a` (`a`)
);
insert into t(`a`) value(1),(1),(1),(4),(4),(5);
insert into s value(1),(2),(3),(4);
select /*+ TIDB_INLJ(t) */ * from t left join s on t.a = s.a;
在上例中, t
为 Outer 表,s
为 Inner 表。 /* TIDN_INLJ / 可以让优化器尽可能选择 Index Lookup Join 算法。
设 Outer 表读数据 batch 的初始大小为 2 行,Inner Worker 数量为 2。
查询语句的一种可能的执行流程如下图所示,其中由上往下箭头表示时间线:
作者:徐怀宇
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。