知识卡片
组合范围的字典序展开
先把前缀点值依次写入范围的低高值向量,再按最后一列的范围数复制并扩展。OR 分支的范围合并按左端排序并维护最右界;这利用的是组合键字典序,不是各列独立区间的任意笛卡尔盒。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 3 处
- TiDB 源码阅读系列文章(十三)索引范围计算简介 · 查看原书依据
在现在的 TiDB 中,单列索引和多列索引使用了相同的 range 结构,所以这里的端点值为 slice 的形式。
- TiDB 源码阅读系列文章(十三)索引范围计算简介 · 查看原书依据
对于多列索引,当其为 AND 表达式时,根据前述我们可以知道,其形式必为索引前缀列上的等值条件再加上关于前缀之后一个列的复杂条件组成。所以我们只需要按顺序处理点查的等值条件部分,将点查的区间依次 append 到 NewRange 中的 LowVal 和 HighVal 两个 Slice
- TiDB 源码阅读系列文章(十三)索引范围计算简介 · 查看原书依据
对于 OR 表达式的情况,由于此时 range 已经无法转回 point 的结构。所以这里重新实现了一下区间并的操作。实现的形式便是比较常见的将区间按左端点排序,在依次扫过区间的同时,记录当前所有重叠过的区间的最右右端点来进行做区间并的算法。区间并的具体的实现可见 unionRanges
参考来源
- 位置:《TiDB源码阅读系列文章》第13章《TiDB 源码阅读系列文章(十三)索引范围计算简介》(来源项目:book-sources;源文件:extracted/TiDB源码阅读系列文章/_epub-src/OEBPS/Text/TiDB 源码阅读系列文章(十三)索引范围计算简介.html;阅读段落 45,47,48;均为书中版本)
- 结论依据:原文对组合范围的字典序展开给出上述机制或边界;本卡把已读说明整理为可独立理解的解释。
- 原始内容:在现在的 TiDB 中,单列索引和多列索引使用了相同的 range 结构,所以这里的端点值为 slice 的形式。 …… 对于多列索引,当其为 AND 表达式时,根据前述我们可以知道,其形式必为索引前缀列上的等值条件再加上关于前缀之后一个列的复杂条件组成。所以我们只需要按顺序处理点查的等值条件部分,将点查的区间依次 append 到 NewRange 中的 LowVal 和 HighVal 两个 Slice …… 对于 OR 表达式的情况,由于此时 range 已经无法转回 point 的结构。所以这里重新实现了一下区间并的操作。实现的形式便是比较常见的将区间按左端点排序,在依次扫过区间的同时,记录当前所有重叠过的区间的最右右端点来进行做区间并的算法。区间并的具体的实现可见 unionRanges