TiDB 源码阅读系列文章(十一)Index Lookup Join

什么是 Index Lookup Join

Nested Loop Join

在介绍 Index Lookup Join 之前,我们首先看一下什么是 Nested Loop Join(NLJ)。 NLJ 的具体定义可以参考 Wikipedia。NLJ 是最为简单暴力的 Join 算法,其执行过程简述如下:

  • 遍历 Outer 表,取一条数据 r;
  • 遍历 Inner 表,对于 Inner 表中的每条数据,与 r 进行 join 操作并输出 join 结果;
  • 重复步骤 1,2 直至遍历完 Outer 表中的所有数据。

NLJ 算法实现非常简单并且 join 结果的顺序与 Outer 表的数据顺序一致。

但是存在性能上的问题:执行过程中,对于每一条 OuterRow,我们都需要对 Inner 表进行一次全表扫操作,这将消耗大量时间。

为了减少对于 Inner 表的全表扫次数,我们可以将上述步骤 1 优化为每次从 Outer 表中读取一个 batch 的数据,优化后的算法即 Block Nested-Loop Join(BNJ),BNJ 的具体定义可以参考 Wikipedia

Index Lookup Join

对于 BNJ 算法,我们注意到,对于 Outer 表中每个 batch,我们并没有必要对 Inner 表都进行一次全表扫操作,很多时候可以通过索引减少数据读取的代价。Index Lookup Join(ILJ) 在 BNJ 基础上进行了改进,其执行过程简述如下:

  • 从 Outer 表中取一批数据,设为 B;
  • 通过 Join Key 以及 B 中的数据构造 Inner 表取值范围,只读取对应取值范围的数据,设为 S;
  • 对 B 中的每一行数据,与 S 中的每一条数据执行 Join 操作并输出结果;
  • 重复步骤 1,2,3,直至遍历完 Outer 表中的所有数据。

TiDB Index Lookup Join 的实现

TiDB 的 ILJ 算子是一个多线程的实现,主要的线程有: Main Thead,Outer Worker,和 Inner Worker:

  • Outer Worker 一个:
  • 按 batch 遍历 Outer 表,并封装对应的 task
  • 将 task 发送给 Inner Worker 和 Main Thread
  • Inner Worker N 个:
    • 读取 Outer Worker 构建的 task
    • 根据 task 中的 Outer 表数据,构建 Inner 表的扫描范围,并构造相应的物理执行算子读取该范围内的 Inner 表数据
    • 对读取的 Inner 表数据创建对应的哈希表并存入 task
  • Main Thread 一个:
* 启动 Outer Worker 及 Inner Workers
* 读取 Outer Worker 构建的 task,并对每行 Outer 数据在对应的哈希表中 probe
* 对 probe 到的数据进行 join 并返回执行结果

这个算子有如下特点:

  • Join 结果的顺序与 Outer 表的数据顺序一致,这样对上一层算子可以提供顺序保证;
  • 对于 Outer 表中的每个 batch,只在 Inner 表中扫描部分数据,提升单个 batch 的处理效率;
  • Outer 表的读数据操作,Inner 表的读数据操作,及 Join 操作并行执行,整体上是一个并行+Pipeline 的方式,尽可能提升执行效率。

执行阶段详述

TiDB 中 ILJ 的执行阶段可划分为如下图所示的 5 步:

image

1. 启动 Outer Worker 及 Inner Workers

这部分工作由 startWorkers 函数完成。该函数会 启动一个 Outer Worker多个 Inner Worker多个 Inner Worker。Inner Woker 的数量可以通过 tidb_index_lookup_concurrency 这个系统变量进行设置,默认为 4。

2. 读取 Outer 表数据

这部分工作由 buildTask 函数完成。此处主要注意两点:

第一点,对于每次读取的 batch 大小,如果将其设置为固定值,则可能会出现如下问题:

  • 若设置的 batch 值较大,但 Outer 表数据量较小时。各个 Inner Worker 所需处理的任务量可能会不均匀,出现数据倾斜的情况,导致并发整体性能相对单线程提升有限。
  • 若设置的 batch 值较小,但 Outer 表数据量较大时。Inner Worker 处理任务时间短,需要频繁从管道中取任务,CPU 不能被持续高效利用,由此带来大量的线程切换开销。此外, 当 batch 值较小时,同一批 inner 表数据能会被反复读取多次,带来更大的网络开销,对整体性能产生极大影响。

因此,我们通过指数递增的方式动态控制 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 有如下几个步骤:

  • constructDatumLookupKeys 函数计算 Outer 表对应的 Join Keys 的值,我们可以根据 Join Keys 的值从 Inner 表中仅查询所需要的数据即可,而不用对 Inner 表中的所有数据进行遍历。为了避免对同一个 batch 中相同的 Join Keys 重复查询 Inner 表中的数据,sortAndDedupDatumLookUpKeys 会在查询前对前面计算出的 Join Keys 的值进行去重。
  • fetchInnerResult 函数利用去重后的 Join Keys 构造对 Inner 表进行查询的执行器,并读取数据存储于 task.innerResult 中。
  • buildLookUpMap 函数对读取的 Inner 数据按照对应的 Join Keys 构建哈希表,存储于 task.lookupMap 中。

上述步骤完成后,Inner Worker 向 task.doneCh 中发送数据,以唤醒 Main Thread 进行接下来的工作。

5. Main Thread 执行 Join 操作

这部分工作由 prepareJoinResult 函数完成。prepareJoinResult 有如下几个步骤:

  • getFinishedTask 从 resultCh 中读取 task,并等待 task.doneCh 发送来的数据,若该 task 没有完成,则阻塞住;
  • 接下来的步骤与 Hash Join类似(参考 TiDB 源码阅读系列文章(九)),lookUpMatchedInners 取一行 OuterRow 对应的 Join Key,从 task.lookupMap 中 probe 对应的 Inner 表的数据;
  • 主线程对该 OuterRow,与取出的对应的 InnerRows 执行 Join 操作,写满存储结果的 chk 后返回。

示例

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。

查询语句的一种可能的执行流程如下图所示,其中由上往下箭头表示时间线:

image

作者:徐怀宇

延展阅读

(一)序

(二)初识 TiDB 源码

(三)SQL 的一生

(四)Insert 语句概览

(五)TiDB SQL Parser 的实现

(六)Select 语句概览

(七)基于规则的优化

(八)基于代价的优化

(九) Hash Join

(十)Chunk 和执行框架简介

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大内老A

WCF技术剖析之二十一:WCF基本异常处理模式[中篇]

通过WCF基本的异常处理模式[上篇], 我们知道了:在默认的情况下,服务端在执行某个服务操作时抛出的异常(在这里指非FaultException异常),其相关的...

19010
来自专栏木东居士的专栏

Spark源码解析:RDD

2423
来自专栏Spark学习技巧

hashpartitioner-Spark分区计算器

一点点回忆 年初了,帮助大家回忆一下spark的重要知识点。 首先,我们回顾的知识点是RDD的五大特性: 1,一系列的分区。 2,一个函数作用于分区上。 3,R...

3609
来自专栏函数式编程语言及工具

泛函编程(18)-泛函库设计-并行运算组件库

    作为专业的编程人员,我们经常会因为工作需要建立一些工具库。所谓工具库就是针对工作上经常会遇到的一些共性问题预先编制的由一整套函数所组成的函数库。通常这些...

1667
来自专栏数据分析

[数据库基础]——索引

一、引言 对数据库索引的关注从未淡出我的们的讨论,那么数据库索引是什么样的?聚集索引与非聚集索引有什么不同?希望本文对各位同仁有一定的帮助。有不少存疑的地方,...

3237
来自专栏程序员互动联盟

Java高级工程师需要掌握哪些核心点?

每逢长假都会有很多程序员跳槽,十一、过年是跳槽黄金时刻,尤其是过年。过年的时候年终奖到手,没有了多少牵挂,年终同学同事聚会比较多,沟通的就多,各种工作机会的消息...

36610
来自专栏chenssy

【死磕Java并发】-----J.U.C之阻塞队列:LinkedTransferQueue

原文出处http://cmsblogs.com/ 『chenssy』 前面提到的各种BlockingQueue对读或者写都是锁上整个队列,在并发量大的时候,各种...

3295
来自专栏阿杜的世界

AssertJ的介绍参考资料

我们一般使用断言(Assert)进行结果验证,Junit的org.junit.Assert包提供了大量断言API,如:assertEquals、assertTr...

381
来自专栏青枫的专栏

day31_Hibernate学习笔记_03

在数据库表中如何表达多对多关系:   使用中间表,分别引用两方的ID。 在对象中如何表达多对多关系:   两方都使用集合表达。 在配置文件中如何表达一对多关系...

784
来自专栏PingCAP的专栏

TiDB 源码阅读系列文章(六)Select 语句概览

Select 语句只会讲解最简单的情况:全表扫描+过滤,暂时不考虑索引等复杂情况,更复杂的情况会在后续章节中介绍。语句为:

4258

扫码关注云+社区