TiDB 源代码学习: ranger 模块代码分析-阿里云开发者社区

开发者社区> dasein58> 正文

TiDB 源代码学习: ranger 模块代码分析

简介: 对数据库技术有一定了解的同行们,应该对 索引前缀匹配 的概念不陌生. 在 TiDB 中 ranger 模块在前缀匹配机制中发挥了一定的作用,所以我想好好了解一下这个模块的代码. ranger 模块介绍 ranger 模块重要的入口是 DetachCondAndBuildRangeForIndex 以及 DetachCondAndBuildRangeForTable 两个函数. 本文以 DetachCondAndBuildRangeForIndex 函数为主要的分析对象,下面简称这个函数位 DCBR DCBR 的入参是: 某个索引信息,主要是用里面的列信息(包含哪些列,以及它们在索引当中
+关注继续查看

对数据库技术有一定了解的同行们,应该对 索引前缀匹配 的概念不陌生. 在 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 的合并逻辑

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
MyBatis Generator (MBG) 代码生成器简介
MyBatis Generator(MBG)是MyBatis MyBatis和iBATIS的代码生成器。它将生成所有版本的MyBatis的代码,以及版本2.2.0之后的iBATIS版本。它将内省数据库表(或许多表),并将生成可用于访问表的工件。
1331 0
MyBatis Generator 代码生成器 快速入门指南
要使用MyBatis Generator(MBG)快速启动并运行,请按照下列步骤操作:1、适当地创建并填写配置文件。至少必须指定:一个元素来指定如何连接到目标数据库一个元素来指定生成的Java模型对象的目标包和目标项目用于指定生成的SQL映射文件的目标包和目标项目的元素(可选)一个元素来指定生成的客户端接口和类的目标包和目标项目(如果不希望生成Java客户端代码,则可以省略元素)至少有一个数据库元素有关配置文件的示例,请参阅XML配置文件参考页面。
805 0
干货|如何让机器向“时尚达人”学习?阿里做了个“实用”的图像数据集
阿里资深算法专家雷音带领的团队,有个非常特别的名字,叫做“图像与美”。雷音希望,未来AI产品对衣服的理解不只限于照片和文字,还可以理解衣服本身,进而理解时尚穿搭之道、理解流行风向。
909 0
Android系统源代码下载
引用:http://www.cnblogs.com/mandroid/archive/2011/06/06/2073473.html 一、概述 众所周知,Android移动操作系统是Google花费了很大的财力、物力及人力的前提下,推广到世界各个角落,以开放源代码的方式(当然也不是完全开放所有),使其在世界范围内迅速漫延开来,到目前虽说只有三四年的时间 ,火热程度,也不用我细说了,看看业界新闻就明白了。
827 0
MaxCompute(原ODPS) Studio 2.7.0 版本发布,让代码效率更高
新功能: 作业管理: 显示作业排队队列 作业管理: 显示正在执行作业的历史状态转换序列 SQL编辑器: 跳转到 UDF 和 Table 的声明 SQL编辑器: 代码折叠和括号匹配支持 SQL编辑器: 常用语句模板支持 UDF: UDF 项目模块的 Maven 支持 UDF: UDF 一
3326 0
机器学习实战:基于概率论的分类方法:朴素贝叶斯(源码解析,错误分析)
按照惯例,先把代码粘到这里 from numpy import * def LoadDataSet(): postingList = [['my', 'dog', 'has', 'flea', 'proble...
838 0
SSM框架——使用 MyBatis Generator 生成代码,包括:Model、Dao、Mapping
基于 SSM 框架开发,Mybatis 属于半自动 ORM,如果每个数据表相关的 Model、Dao、Mapping 都要自己动手去写,是不是很麻烦呢?工作量最大的就是书写Mapping的映射文件,而且手动书写很容易出错。
1156 0
Spring Boot项目利用MyBatis Generator进行数据层代码自动生成
概 述 MyBatis Generator (简称 MBG) 是一个用于 MyBatis和 iBATIS的代码生成器。它可以为 MyBatis的所有版本以及 2.2.0之后的 iBATIS版本自动生成 ORM层代码,典型地包括我们日常需要手写的 POJO、mapper xml 以及 mapper 接口等。
1840 0
Python零基础学习代码实践 —— 提取字符串里面的单词数
str = input() str1 = str.strip() index = 0 count = 0 while index < len(str1): while str1[index] != " ": index += 1 if index == le...
1102 0
如何把代码写的更优雅,你需要这一份代码精进书单!
黄小斜写了一年多的代码,渐渐地代码量也上来了,但是,代码写的多就是好吗,简单的数量堆积似乎并不能起到太好的效果,毕竟我们CRUD写多了,也不怎么需要架构设计,甚至连个设计模式都不怎么需要用到。如何开始代码精进之路,其实有很多的过来人早就已经给出了答案,今天就给大家推荐几本帮你精进代码的优质书籍,走过路过可不要错过哦~
310 0
+关注
765
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载