文档章节

TiDB 源码阅读系列文章(十三)索引范围计算简介

TiDB
 TiDB
发布于 07/13 10:45
字数 3091
阅读 5
收藏 0
点赞 0
评论 0

简述

在数据库中处理查询请求时,如果可以尽早的将无关数据过滤掉,那么后续的算子就可以少做无用功,提升整个 SQL 的执行效率。过滤数据最常用的手段是使用索引,TiDB 的优化器也会尽量采用索引过滤的方式处理请求,利用索引有序的特点来提升查询效率。比如当查询条件为 a = 1 时,如果 a 这一列上有索引,我们就可以利用索引很快的把满足 a = 1 的数据拿出来,而不需要逐行检查 a 的值是否为 1。当然是否会选择索引过滤也取决于代价估算。

索引分为单列索引和多列索引(组合索引),筛选条件也往往不会是简单的一个等值条件,可能是非常复杂的条件组合。TiDB 是如何分析这些复杂条件,来得到这些条件在对应的索引上的逻辑区间范围(range),就是本文要介绍的内容。

关于 TiDB 如何构建索引,如何存储索引数据,希望读者能够有基本的了解(参考阅读:三篇文章了解 TiDB 技术内幕 - 说计算 )。

这里是一个例子,展示这里所说的索引范围计算是做什么的,建表语句和查询语句如下:

CREATE TABLE t (a int primary key, b int, c int);
select * from t where ((a > 1 and a < 5 and b > 2) or (a > 8 and a < 10 and c > 3)) and d = 5;

计算索引逻辑区间范围的流程如下:

流程图

从上图可以看出,整个流程分为从 Filter 中抽取可用索引的表达式以及利用选出的表达式构造数据范围两个步骤,接下来分别描述。

抽取表达式

这个步骤是从 Filter 中将能够用上索引的表达式选出来。由于单列索引和多列索引在处理逻辑上有很大的不同,所以会分单列索引和多列索引两中情况进行讲解。

单列索引

单列索引的情况相对来说比较简单。很多满足 Column op Constant 形式的简单表达式都可以用来计算 range,单个表达式的判断逻辑在 checker.go 的 conditionChecker 中。而对于包含了 AND 或者 OR 的复杂情况,我们可以按照下述规则进行处理:

  1. AND 表达式无关的 filter 并不会影响其可以计算 range 的子项。所以直接舍去无关的表示即可。以流程图中的一个子表达式 a > 1 and a < 5 and b > 2 为例,我们只要将 b > 2 扔掉,保留 a > 1 and a < 5 即可。

  2. OR 表达式中,每个子项都要可以用来计算 range,如果有不可以计算 range 的子项,那么这整个表达式都不可用来计算 range。以 a = 1 or b = 2 为例,b = 2 这一子项不可以用来计算 a 的 range,所以这个表达式整体上无法计算 a 的 range。而如果是 a > 1 or ( a < 2 and b = 1),根据 1 中的规则,第二个子项会留下 a < 2 的部分,可以用来计算 a 的 range,因此整个表达式会返回 a > 1 and a < 2 来供接下来计算 range 的部分处理。

这里补充说明一点,TiDB 的主键在实现方式上限定了只有整数类型的单列主键会把主键值当做 RowID,然后编码成 RowKey,和这行数据存储在一起。其他类型的单列主键会作为普通的 unique key 看待,当查询的列包含索引上没有的列时,需要一次查索引 + 一次扫表。所以我们将这种整数类型作为主键的索引处理逻辑单独抽取出来,其入口函数为 DetachCondsForTableRange 。其中对 AND 表达式和 OR 表达式的处理入口分别为 detachColumnCNFConditions 和 detachColumnDNFConditions。这两个函数也用来处理其他类型的主键或者索引的的 range 计算。

多列索引

多列索引的情况较单列索引而言会复杂一些,因为在处理 OR 表达式中列与列之间的关系需要考虑更多情况。TiDB 中为了简化 ranger 的逻辑,目前只考虑下列情况:

  1. AND 表达式中,只有当之前的列均为点查的情况下,才会考虑下一个列。

    e.g. 对于索引 (a, b, c),有条件 a > 1 and b = 1,那么会被选中的只有 a > 1。对于条件 a in (1, 2, 3) and b > 1,两个条件均会被选到用来计算 range。

    由于非点查的部分只会涉及到一个列,所以可以直接复用 detachColumnCNFConditions

  2. OR 表达式中,每个子项会视为 AND 表达式分开考虑。与单列索引的情况一样,如果其中一个子项无法用来计算索引,那么该 OR 表达式便完全无法计算索引。

多列索引处理的入口函数为 DetachCondAndBuildRangeForIndex,AND 表达式和 OR 表达式的处理入口分别为 detachCNFCondAndBuildRangeForIndex 和 detachDNFCondAndBuildRangeForIndex。(由于多列索引对 range 的处理相对单列索引而言会复杂一些,所以没有拆分为 DetachCondition 和 BuildRange 两部分,而是由 DetachCondAndBuildRangeForIndex 处理。)

由于逻辑进行到了简化,因此目前 TiDB 的 ranger 存在无法正确处理的情况。比如:

  • a = 1 and (b = 1 or b = 2) and c > 1。对于这个式子,当 (a, b ,c) 为索引时,如上述所言,由于 (b = 1 or b = 2) 形式上是 OR 表达式的情况,而非点查。所以会在 b 列停止,不会考虑 c > 1 的情况。所以目前为了兼容 TiDB 的逻辑,遇到这种情况尽量改写为 a = 1 and b in (1, 2) and c > 1 的形式。

  • 类似的如 ((a = 1 and b = 1) or (a = 2 and b = 2)) and c = 1 形式的式子,前段 OR 表达式实际上为点查的行为,但是由于是 OR 连接起来的式子,所以在 TiDB 的逻辑中作为范围查询处理,因此 c = 1 不会作为索引的计算条件处理。而这时改写为 (a, b) in ((1, 1),  (2, 2)) and c = 1 的形式也不会使 c = 1 选入索引计算的条件,原因是多列 in 的函数会被 TiDB 改写为 OR 连接的形式,所以 ((a = 1 and b = 1) or (a = 2 and b = 2)) 和 (a, b) in ((1, 1),  (2, 2)) 在 TiDB 中是完全一致的行为。针对这种情况,目前的办法只有将这些条件都放入 OR 的子项中,针对这里用到的例子,那就是要改写为 ((a = 1 and b = 1 and c = 1) or (a = 2 and b = 2 and c = 1))

计算逻辑区间

这一步骤中,利用上一步抽取出来的表达式估算出数据的逻辑区间范围,后续会根据这个逻辑区间以及数据编码方式构造物理区间进行数据访问。我们仍然分为单列索引和多列索引两个情况来介绍。

单列索引

这种情况下,输入的表达式为 Column op Constant 形式的简单表达式由 OR 以及 AND 连接而成。我们对每一个具体的操作符,都设计了一段对应的计算 range 的逻辑,当遇到 AND 或者 OR 时,会对两个区间求交或者求并。在 point.go 中有一个 builder 的结构体用来处理上述逻辑。

在这个阶段我们记录 range 时用 rangePoint 的结构来存储 range。

// Point is the end point of range interval.
type point struct {
	value types.Datum
	excl  bool // exclude
	start bool
}

每个 point 代表区间的一个端点,其中的 excl 表示端点为开区间的端点还是闭区间的端点。start 表示这个端点是左端点还是右端点。

builder 中每个 buildFromXXX 的方法都是计算一个具体函数的 range 的方法。比如 buildFromIn 便是处理 in 函数 的方法。可以看到它首先对 in 函数的值列表的每个值都构造了一个 rangPoint 的单点区间,然后对这些区间放在一个 slice 中做排序以及去重。最终将去重后的结果输出。

在 pointer.go 中还包含其他各类的函数的处理,具体可以翻阅源代码。

除了对具体函数的处理外,pointer.go 中还有区间交和区间并的操作。intersection 和 union 分别代表区间交和区间并。两个函数的逻辑均通过 merge 方法进行处理,通过传入一个 flag 来区分。merge 函数做了如下两个假设:

  • a, b 两个区间均已经做过去重

  • 单个区间序列内部不会有重叠的部分

merge 函数使用 inRangeCount 来记录当前位置被 a, b 两个区间序列覆盖的情况。区间求并的情况时,只要 a, b 两个区间序列中有一个区间序列覆盖便可以作为解输出,被两个区间同时覆盖的端点必然是属于一个更大的区间的内部不需要输出。所以当 inRangeCount 为 1 时,即为需要输出的区间端点。

当区间求交时,需要两个序列都覆盖到才是可以输出的端点,所以当 inRangeCount 为 2 时,即为需要输出的区间端点。

在得到最后的区间端点序列后,由 points2TableRanges 转化为对外暴露的 range 结构,由 BuildTableRange 输出到 plan package。

// NewRange represents a range generated in physical plan building phase.
type NewRange struct {
	LowVal  []types.Datum
	HighVal []types.Datum

	LowExclude  bool // Low value is exclusive.
	HighExclude bool // High value is exclusive.
}

在现在的 TiDB 中,单列索引和多列索引使用了相同的 range 结构,所以这里的端点值为 slice 的形式。

多列索引

对于多列索引,当其为 AND 表达式时,根据前述我们可以知道,其形式必为索引前缀列上的等值条件再加上关于前缀之后一个列的复杂条件组成。所以我们只需要按顺序处理点查的等值条件部分,将点查的区间依次 append 到 NewRange 中的 LowVal 和 HighVal 两个 Slice 中即可(appendPoints2Ranges)。处理到最后一列时,将之前的 NewRange 按最后非点查列所计算得到的区间个数拷贝一下,再依次 append 即可。具体代码可见 buildCNFIndexRange

对于 OR 表达式的情况,由于此时 range 已经无法转回 point 的结构。所以这里重新实现了一下区间并的操作。实现的形式便是比较常见的将区间按左端点排序,在依次扫过区间的同时,记录当前所有重叠过的区间的最右右端点来进行做区间并的算法。区间并的具体的实现可见 unionRanges 方法。

Future Plan

  • 目前 TiDB 对单列索引的处理在逻辑上已经非常完备,在实际表现上可能由于没有对部分函数实现计算 range 的逻辑而有遗漏。这部分会根据情况进行优化。

  • 如上文提到的,目前 TiDB 为了简化 ranger 的逻辑,对多列索引做了一些假设。未来会尝试去掉或者弱化这些假设,或者在前期对 SQL 进行更充分的改写使得 SQL 不会触发这些假设,来提供更加强大的功能,免于手动 rewrite 的麻烦。

  • 目前 TiDB 对简单式子的形式的检查限定在了 Column op Constant 的形式。所以诸如 from_unixtime(timestamp_col) op datetime_constant 形式的条件是无法计算索引的,也需要手动 rewrite 为 timestamp_col op timestamp_constant 才可以使用到索引。这部分也会考虑进行改进以提升用户体验。

作者:崔一丁

© 著作权归作者所有

共有 人打赏支持
TiDB
粉丝 95
博文 101
码字总数 258813
作品 0
海淀
TiDB 源码阅读系列文章(十一)Index Lookup Join

什么是 Index Lookup Join Nested Loop Join 在介绍 Index Lookup Join 之前,我们首先看一下什么是 Nested Loop Join(NLJ)。 NLJ 的具体定义可以参考 Wikipedia。NLJ 是最为简单暴力的 Jo...

TiDB
06/28
0
0
TiDB 源码阅读系列文章(十)Chunk 和执行框架简介

什么是 Chunk TiDB 2.0 中,我们引入了一个叫 Chunk 的数据结构用来在内存中存储内部数据,用于减小内存分配开销、降低内存占用以及实现内存使用量统计/控制,其特点如下: 只读 不支持随机写...

TiDB
06/19
0
0
TiDB 源码阅读系列文章(十二)统计信息(上)

作者: 谢海滨 在 TiDB 里,SQL 优化的过程可以分为逻辑优化和物理优化两个部分,在物理优化阶段需要为逻辑查询计划中的算子估算运行代价,并选择其中代价最低的一条查询路径作为最终的查询计...

TiDB
07/06
0
0
TiDB 在饿了么归档环境的应用

背景 随着业务增长,公司数据规模不断膨胀,表变多、变大。一方面占用的磁盘、CPU 等物理资源疾速上涨,另一方面大表性能下降且变更困难。实际上,很多大表的数据无需保留很久,比如某些业务...

TiDB
04/26
0
0
开源分布式 NewSQL 关系型数据库 - TiDB

TiDB 是国内 PingCAP 团队开发的一个分布式 SQL 数据库。其灵感来自于 Google 的 F1 和 Google spanner, TiDB 支持包括传统 RDBMS 和 NoSQL 的特性。 TiDB 的源码已经托管在 Git@OSC 上,详情...

goroutine
2015/09/06
0
37
重磅!开源分布式 NewSQL 数据库 TiDB 2.0 正式发布

去年十月,TiDB 1.0 版本发布,在接下来的六个月中,开发团队一方面在维护 1.0 版本的稳定性并且增加必要的新特性,另一方面马不停蹄的开发 2.0 版本。经过 6 个 RC 版本,TiDB 2.0 GA 版本于...

雨田桑
04/28
0
19
UCloud 与 PingCAP 达成合作 Cloud TiDB 全球正式发布

2017 年 10 月,国内领先的中立云计算厂商 UCloud 与国内开源分布式 NewSQL 数据库 TiDB 团队 PingCAP 正式达成合作,双方将联手在 UCloud 全球数据中心逐步推出新一代 TiDB 的云端版本——C...

TiDB
2017/10/30
0
0
TiDB 分布式数据库在转转公司的应用实践

作者:孙玄,转转公司首席架构师;陈东,转转公司资深工程师;冀浩东,转转公司资深 DBA。 公司及业务架构介绍 转转二手交易网 —— 把家里不用的东西卖了变成钱,一个帮你赚钱的网站。由腾讯...

TiDB
05/30
0
0
TIDB集群安装部署方案————————下篇

=================== 下面进入真正的实施部署阶段了=== 概述 Ansible 是一款自动化运维工具,TiDB-Ansible 是 PingCAP 基于 Ansible playbook 功能编写的集群部署工具。使用 TiDB-Ansible 可...

叶海无崖
07/14
0
0
易观 OLAP 大赛揭晓 PingCAP 斩获商业组桂冠

28 日,在 2017 易观 A10 大数据应用峰会上,针对“有序漏斗”难题进行行业攻坚的“2017 易观 OLAP 算法大赛”公布了最终结果。PingCAP 参赛组以超过原始基准测试近 30 倍的成绩,获得了商业...

TiDB
2017/10/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

about git flow

  昨天元芳做了git分支管理规范的分享,为了拓展大家关于git分支的认知,这里我特意再分享这两个关于git flow的链接,大家可以看一下。 Git 工作流程 Git分支管理策略   git flow本质上是...

qwfys
今天
2
0
Linux系统日志文件

/var/log/messages linux系统总日志 /etc/logrotate.conf 日志切割配置文件 参考https://my.oschina.net/u/2000675/blog/908189 dmesg命令 dmesg’命令显示linux内核的环形缓冲区信息,我们可...

chencheng-linux
今天
1
0
MacOS下给树莓派安装Raspbian系统

下载镜像 前往 树莓派官网 下载镜像。 点击 最新版Raspbian 下载最新版镜像。 下载后请,通过 访达 双击解压,或通过 unzip 命令解压。 检查下载的文件 ls -lh -rw-r--r-- 1 dingdayu s...

dingdayu
今天
1
0
spring boot使用通用mapper(tk.mapper) ,id自增和回显等问题

最近项目使用到tk.mapper设置id自增,数据库是mysql。在使用通用mapper主键生成过程中有一些问题,在总结一下。 1、UUID生成方式-字符串主键 在主键上增加注解 @Id @GeneratedValue...

北岩
今天
2
0
告警系统邮件引擎、运行告警系统

告警系统邮件引擎 cd mail vim mail.py #!/usr/bin/env python#-*- coding: UTF-8 -*-import os,sysreload(sys)sys.setdefaultencoding('utf8')import getoptimport smtplibfr......

Zhouliang6
今天
1
0
Java工具类—随机数

Java中常用的生成随机数有Math.random()方法及java.util.Random类.但他们生成的随机数都是伪随机的. Math.radom()方法 在jdk1.8的Math类中可以看到,Math.random()方法实际上就是调用Random类...

PrivateO2
今天
3
0
关于java内存模型、并发编程的好文

Java并发编程:volatile关键字解析    volatile这个关键字可能很多朋友都听说过,或许也都用过。在Java 5之前,它是一个备受争议的关键字,因为在程序中使用它往往会导致出人意料的结果。在...

DannyCoder
昨天
1
0
dubbo @Reference retries 重试次数 一个坑

在代码一中设置 成retries=0,也就是调用超时不用重试,结果DEBUG的时候总是重试,不是0吗,0就不用重试啊。为什么还是调用了多次呢? 结果在网上看到 这篇文章才明白 https://www.cnblogs....

奋斗的小牛
昨天
2
0
数据结构与算法3

要抓紧喽~~~~~~~放羊的孩纸回来喽 LowArray类和LowArrayApp类 程序将一个普通的Java数组封装在LowArray类中。类中的数组隐藏了起来,它是私有的,所以只有类自己的方法才能访问他。 LowArray...

沉迷于编程的小菜菜
昨天
1
0
spring boot应用测试框架介绍

一、spring boot应用测试存在的问题 官方提供的测试框架spring-boot-test-starter,虽然提供了很多功能(junit、spring test、assertj、hamcrest、mockito、jsonassert、jsonpath),但是在数...

yangjianzhou
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部