对数据库技术有一定了解的同行们,应该对 索引前缀匹配 的概念不陌生. 在 TiDB 中 ranger 模块在前缀匹配机制中发挥了一定的作用,所以我想好好了解一下这个模块的代码.

ranger 模块介绍
ranger 模块重要的入口是 DetachCondAndBuildRangeForIndex 以及 DetachCondAndBuildRangeForTable 两个函数.

本文以 DetachCondAndBuildRangeForIndex 函数为主要的分析对象,下面简称这个函数位 DCBR

DCBR 的入参是:

某个索引信息,主要是用里面的列信息(包含哪些列,以及它们在索引当中的顺序)
扫描时所有可用的筛选条件
它的作用可以细分为 3 点:

根据索引的列信息,从筛选条件当中解析出可以用来做索引扫描的筛选条件,我们称为 accessConds
根据 accessConds 计算索引扫描的 ranges
从筛选条件中保留那些无法作为 accessConds 的条件,并返回
我们称这些条件为 filterConds
如果 DCBR 返回的 filterConds 不为空,那么查询数据时,在完成索引扫描以后,还需要使用 filterConds 过滤一边数据
简单示例
举个简单例子,假如现在有一个表:

create table (a int, b int, c int, index idx_ab(a, b));
我们用下面这条查询语句进行查询:

select * from t where a = 1 and b > 2 and c = 3;
系统在衡量使用索引 idx_ab 扫描的效率时,会调用 DCBR 方法计算 ranges, DCBR 得到的入参是:

索引 idx_ab 的信息,主要是使用里面的列信息
筛选条件 [(a = 1), (b > 2), (c = 3)]
DCBR 方法执行过程中:

会从筛选条件当中提取出 a = 1, b > 2 这两个条件作为 accessConds 返回
c = 3 不在索引列当中,无法用在索引扫描, 放入 filterConds 并返回
根据 a = 1, b > 2 两个条件计算索引扫描的 range (为 [[1 3, 1 +inf)] ) , 并返回
需要补充的是, 即使索引是 (a, b, c), c 列也无法用在索引扫描,这也是前缀匹配原则的缘故.

整体流程
对于像上面提到的这个例子 a = 1 and b > 2 and c = 3, 查询条件比较简单,所以代码中很多特殊的处理逻辑并没有起作用,具体步骤:

应根据索引列的顺序,先依次从条件当中找能够匹配上的 eq/in 条件,直到某一列无法找到这类条件为止
在这个例子里,会依次为 a 列和 b 列找 eq/in 条件, QQ号码买号最后只会找到一个条件 a = 1
如果第 1 步已经为所有的列找到了筛选条件,那么剩余的条件放入 filterConds 中,然后使用找到的 accessConds 计算索引扫描的 ranges,并返回
这个 sql 里,筛选条件并没有匹配到所有的索引列,所以不会在这步结束
如果第 1 步没有为所有列找到筛选条件,那么为第一个没找到条件的列(我们称它为 lastCol)从剩余的条件中寻找非 eq/in 类型的条件
本例里, lastCol 是 b,为 b 找的范围查询类型的条件是 b > 2
lastCol 的条件解析完以后,会根据这些条件来计算 range,并把剩余的条件加入到 filterConds 里
本例里 accessConds 是 a = 1 和 b > 2, filterConds 是 c = 3 , ranges 是 [[1 3, 1 +inf)]
对复杂条件的支持
除了支持上面例子中的简单查询条件(也就是多个条件用 and 串联的情况). DCBR 函数还要支持从多个 and/or 组合的条件中提取 accessConds,计算ranges.比如下面这个语句:

select * from t where (a > 1 and a < 3) or (a > 5 or a < );
需要补充说明的是,数据库会采用树形结构来表示查询条件,这个 sql 中,查询条件会组成下面这样的树形结构.

or
and
a > 1
a < 3
or
a > 2
a < 10
处理这类既有 and 又有 or 的查询条件.会先对条件进行一个 flatten 处理.

flatten 操作会把能够提升层级的 or 节点提升上来,经过 flatten 处理以后,会得到一个条件数组, 本次sql的处理结果是 (a > 1 and a < 3) , a > 2 , a < 10 这三个条件组成的数组

完成 flatten 处理以后,会分别计算数组中每个条件的 accessConds 和 ranges, 计算方式和最开头的简单查询条件的计算方式基本一样.然后把得到的 accessConds 和 ranges 合并,会计算ranges 的并集作为最终的 ranges 结果.

最终得到的 range 结果 (-inf, 0), (1, 3), (5, +inf),为了方便理解,这里只给出了 a 列的范围.

提前终止的场景
有的时候查询条件可能直接可以计算为 false,比如 a > 10 and a < 1；还有 a = 1 and a = 2, ranger 在计算过程中,如果发现某一列的条件计算结果是 false,就会终止整个计算过程,返回空的 ranges.

filterConds 的计算问题
如果是简单的查询条件, accesssConds 和 filterConds 其实很容易分辨,而且彼此互补影响的.但是对于复杂场景 filterConds 就比较难以提取了.

比如下面这个例子:

select * from t where (a > 1 and a < 2 and c > 10) or (a > 5 or a < );
和前面提到的例子相比,查询条件当中多了 c > 10 这个条件. accessConds 并没有发生变化.但是 filterConds 不再为空,而是多了 (a > 1 and a < 2 and c > 10) 这个条件.

ranger 如果在解析 accessConds 时,发现除了解析出来的 accessConds,还剩余了其他条件,这个时候会把整个条件加入到 filterConds 中.

回到这个例子里,ranger 在处理 (a > 1 and a < 2 and c > 10) 这个条件的时候,能够提取出来作为 accessConds 的是 a > 1, a < 2 这两个条件,但是还剩下一个 c > 10 ,这时 ranger 就会把整个 a > 1 and a <2 and c > 10 作为一个 filterConds 保留.

更多的示例
关于 ranger 这块的逻辑,大家可以看一下 TiDB 中提供的 测试用例Range ,里面除了上面描述的场景为还包含了其他一些场景的测试用例:

对 like 条件的 range 计算逻辑
对 not 条件的 range 计算逻辑
同一列有多个 eq/in 条件时,对 accessConds 的合并逻辑