知识卡片
嵌套循环到索引连接
普通嵌套循环为每个 Outer 行扫描 Inner;分块版本用一批 Outer 行摊薄重复扫描。索引连接进一步由这一批连接键构建 Inner 的取值范围,只读相关记录,适合有可用索引且范围选择性合算的场景。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 7 处
- TiDB 源码阅读系列文章(十一)Index Lookup Join · 查看原书依据
但是存在性能上的问题:执行过程中,对于每一条 OuterRow,我们都需要对 Inner 表进行一次全表扫操作,这将消耗大量时间。
- TiDB 源码阅读系列文章(十一)Index Lookup Join · 查看原书依据
为了减少对于 Inner 表的全表扫次数,我们可以将上述步骤 1 优化为每次从 Outer 表中读取一个 batch 的数据,优化后的算法即 Block Nested-Loop Join(BNJ),BNJ 的具体定义可以参考 Wikipedia。
- TiDB 源码阅读系列文章(十一)Index Lookup Join · 查看原书依据
对于 BNJ 算法,我们注意到,对于 Outer 表中每个 batch,我们并没有必要对 Inner 表都进行一次全表扫操作,很多时候可以通过索引减少数据读取的代价。Index Lookup Join(ILJ) 在 BNJ 基础上进行了改进,其执行过程简述如下:
- TiDB 源码阅读系列文章(十一)Index Lookup Join · 查看原书依据
从 Outer 表中取一批数据,设为 B;
- TiDB 源码阅读系列文章(十一)Index Lookup Join · 查看原书依据
通过 Join Key 以及 B 中的数据构造 Inner 表取值范围,只读取对应取值范围的数据,设为 S;
- TiDB 源码阅读系列文章(十一)Index Lookup Join · 查看原书依据
对 B 中的每一行数据,与 S 中的每一条数据执行 Join 操作并输出结果;
- TiDB 源码阅读系列文章(十一)Index Lookup Join · 查看原书依据
重复步骤 1,2,3,直至遍历完 Outer 表中的所有数据。
参考来源
- 位置:《TiDB源码阅读系列文章》第11章《TiDB 源码阅读系列文章(十一)Index Lookup Join》(来源项目:book-sources;源文件:extracted/TiDB源码阅读系列文章/_epub-src/OEBPS/Text/TiDB 源码阅读系列文章(十一)Index Lookup Join.html;阅读段落 8,9,11,12,13,14,15;均为书中版本)
- 结论依据:原文对嵌套循环到索引连接给出上述机制或边界;本卡把已读说明整理为可独立理解的解释。
- 原始内容:但是存在性能上的问题:执行过程中,对于每一条 OuterRow,我们都需要对 Inner 表进行一次全表扫操作,这将消耗大量时间。 …… 为了减少对于 Inner 表的全表扫次数,我们可以将上述步骤 1 优化为每次从 Outer 表中读取一个 batch 的数据,优化后的算法即 Block Nested-Loop Join(BNJ),BNJ 的具体定义可以参考 Wikipedia。 …… 对于 BNJ 算法,我们注意到,对于 Outer 表中每个 batch,我们并没有必要对 Inner 表都进行一次全表扫操作,很多时候可以通过索引减少数据读取的代价。Index Lookup Join(ILJ) 在 BNJ 基础上进行了改进,其执行过程简述如下: …… 从 Outer 表中取一批数据,设为 B; …… 通过 Join Key 以及 B 中的数据构造 Inner 表取值范围,只读取对应取值范围的数据,设为 S; …… 对 B 中的每一行数据,与 S 中的每一条数据执行 Join 操作并输出结果; …… 重复步骤 1,2,3,直至遍历完 Outer 表中的所有数据。