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 条评论
登录 后参与评论

相关文章

来自专栏陈本布衣

SQLite 带你入门

SQLite数据库相较于我们常用的Mysql,Oracle而言,实在是轻量得不行(最低只占几百K的内存)。平时开发或生产环境中使用各种类型的数据库,可能都需要...

4365
来自专栏Java帮帮-微信公众号-技术文章全总结

第二十七天 数据库基础&JDBC使用&工具类Properties&连接池&DBUtils【悟空教程】

第二十七天 数据库基础&JDBC使用&工具类Properties&连接池&DBUtils【悟空教程】

1442
来自专栏Java后端生活

JDBC(三)PreparedStatement

SQL 注入是利用某些系统没有对用户输入的数据进行充分的检查,而在用户输入数据中注入非法的 SQL 语句段或命令,从而利用系统的 SQL 引擎完成恶意行为的做法

831
来自专栏杨建荣的学习笔记

Oracle中的PUBLIC(r10笔记第14天)

Oracle中的PUBLIC是一种特殊的存在,总是感觉概念比较模糊,我们就简单通过几个测试来理解吧。 首先我们创建一个public的synonym,我们看看这...

3074
来自专栏Web 开发

在SAE上开发遇到的问题~

添加一个escape_data()的函数,该函数已经会自动识别各种PHP配置环境~

1240
来自专栏数据库

使用VBA创建Access数据表

导读: 本期介绍如何在Access数据库中创建一张空数据表。下期将介绍如何将工作表中的数据存入数据库对应的表中,随后还将介绍如何从数据库的表中取出数据输出到Ex...

2647
来自专栏用户画像

mysql模拟题二

  3) MSSQLServer2005Enterprise Edition是哪一种版本?

1046
来自专栏个人分享

SparkSQL的解析详解

  SparkSQL继承自Hive的接口,由于hive是基于MapReduce进行计算的,在计算过程中大量的中间数据要落地于磁盘,从而消耗了大量的I/O,降低了...

1702
来自专栏Kevin-ZhangCG

[ SSH框架 ] Hibernate框架学习之三

21611
来自专栏更流畅、简洁的软件开发方式

预防SQL注入攻击之我见

1、 SQL注入攻击的本质:让客户端传递过去的字符串变成SQL语句,而且能够被执行。 2、 每个程序员都必须肩负起防止SQL注入攻击的责任。   说起防止SQ...

5216

扫码关注云+社区

领取腾讯云代金券