TiDB 源码阅读系列文章(七)基于规则的优化

作者:毛康力

在 TiDB 里面,SQL 优化的过程可以分为逻辑优化和物理优化两个部分。逻辑优化主要是基于规则的优化,简称 RBO(rule based optimization)。物理优化会为逻辑查询计划中的算子选择某个具体的实现,需要用到一些统计信息,决定哪一种方式代价最低,所以是基于代价的优化 CBO(cost based optimization)。

本篇将主要关注逻辑优化。先介绍 TiDB 中的逻辑算子,然后介绍 TiDB 的逻辑优化规则,包括列裁剪、最大最小消除、投影消除、谓词下推、TopN 下推等等。

逻辑算子介绍

在写具体的优化规则之前,先简单介绍查询计划里面的一些逻辑算子。

  • DataSource 这个就是数据源,也就是表,select * from t 里面的 t。
  • Selection 选择,例如 select xxx from t where xx = 5 里面的 where 过滤条件。
  • Projection 投影, select c from t 里面的取 c 列是投影操作。
  • Join 连接, select xx from t1, t2 where t1.c = t2.c 就是把 t1 t2 两个表做 Join。

选择,投影,连接(简称 SPJ) 是最基本的算子。其中 Join 有内连接,左外右外连接等多种连接方式。

select b from t1, t2 where t1.c = t2.c and t1.a > 5

变成逻辑查询计划之后,t1 t2 对应的 DataSource,负责将数据捞上来。上面接个 Join 算子,将两个表的结果按 t1.c = t2.c连接,再按 t1.a > 5 做一个 Selection 过滤,最后将 b 列投影。下图是未经优化的表示:

  • Sort 就是 select xx from xx order by 里面的 order by
  • Aggregation,在 select sum(xx) from xx group by yy 中的 group by 操作,按某些列分组。分组之后,可能带一些聚合函数,比如 Max/Min/Sum/Count/Average 等,这个例子里面是一个 sum。
  • Apply 这个是用来做子查询的。

列裁剪

列裁剪的思想是这样的:对于用不上的列,没有必要读取它们的数据,无谓的浪费 IO 资源。比如说表 t 里面有 a b c d 四列。

select a from t where b > 5

这个查询里面明显只有 a b 两列被用到了,所以 c d 的数据是不需要读取的。在查询计划里面,Selection 算子用到 b 列,下面接一个 DataSource 用到了 a b 两列,剩下 c 和 d 都可以裁剪掉,DataSource 读数据时不需要将它们读进来。

列裁剪的算法实现是自顶向下地把算子过一遍。某个结点需要用到的列,等于它自己需要用到的列,加上它的父亲结点需要用到的列。可以发现,由上往下的结点,需要用到的列将越来越多。代码是在 plan/column_pruning.go 文件里面。

列裁剪主要影响的算子是 Projection,DataSource,Aggregation,因为它们跟列直接相关。Projection 里面会裁掉用不上的列,DataSource 里面也会裁剪掉不需要使用的列。

Aggregation 算子会涉及哪些列?group by 用到的列,以及聚合函数里面引用到的列。比如 select avg(a), sum(b) from t group by c d,这里面 group by 用到的 c 和 d 列,聚合函数用到的 a 和 b 列。所以这个 Aggregation 使用到的就是 a b c d 四列。

Selection 做列裁剪时,要看它父亲要哪些列,然后它自己的条件里面要用到哪些列。Sort 就看 order by 里面用到了哪些列。Join 则要把连接条件中用到的各种列都算进去。具体的代码里面,各个算子都是实现 PruneColumns 接口:

func (p *LogicalPlan) PruneColumns(parentUsedCols []*expression.Column) 

通过列裁剪这一步操作之后,查询计划里面各个算子,只会记录下它实际需要用到的那些列。

最大最小消除

最大最小消除,会对 Min/Max 语句进行改写。

select min(id) from t

我们用另一种写法,可以做到类似的效果:

select id from t order by id desc limit 1

这个写法有什么好处呢?前一个语句,生成的执行计划,是一个 TableScan 上面接一个 Aggregation,也就是说这是一个全表扫描的操作。后一个语句,生成执行计划是 TableScan + Sort + Limit。

在某些情况,比如 id 是主键或者是存在索引,数据本身有序, Sort 就可以消除,最终变成 TableScan 或者 IndexLookUp 接一个 Limit,这样子就不需要全表扫了,只需要读到第一条数据就得到结果!全表扫操作跟只查一条数据,性能上可是天壤之别。

最大最小消除,做的事情就是由 SQL 优化器“自动”地做这个变换。

select max(id) from t

生成的查询树会被转换成下面这种:

select max(id) from (select id from t order by id desc limit 1 where id is not null) t

这个变换复杂一些是要处理 NULL 的情况。经过这步变换之后,还会执行其它变换。所以中间生成的额外的算子,可能在其它变换里面被继续修改掉。

min 也是类似的语句替换。相应的代码是在 max_min_eliminate.go 文件里面。实现是一个纯粹的 AST 结构的修改。

投影消除

投影消除可以把不必要的 Projection 算子消除掉。那么,什么情况下,投影算子是可消除的呢?

首先,如果 Projection 算子要投影的列,跟它的孩子结点的输出列,是一模一样的,那么投影步骤就是一个无用操作,可以消除。比如 select a,b from t 在表 t 里面就正好就是 a b 两列,那就没必要 TableScan 上面再做一次 Projection。

然后,投影算子下面的孩子结点,又是另一个投影算子,那么孩子结点的投影操作就没有意义,可以消除。比如 Projection(A) -> Projection(A,B,C) 只需要保留 Projection(A) 就够了。

类似的,在投影消除规则里面,Aggregation 跟 Projection 操作很类似。因为从 Aggregation 结点出来的都是具体的列,所以 Aggregation(A) -> Projection(A,B,C) 中,这个 Projection 也可以消除。

代码是在 eliminate_projection.go 里面。

func eliminate(p Plan, canEliminate bool) {
          对 p 的每个孩子,递归地调用 eliminate
          如果 p 是 Project 
              如果 canEliminate 为真 消除 p
              如果 p 的孩子的输出列,跟 p 的输出列相同,消除 p
    }

注意 canEliminate 参数,它是代表是否处于一个可被消除的“上下文”里面。比如 Projection(A) -> Projection(A, B, C) 或者 Aggregation -> Projection 递归调用到孩子结点 Projection 时,该 Projection 就处理一个 canEliminate 的上下文。

简单解释就是,一个 Projection 结点是否可消除:

  • 一方面由它父结点告诉它,它是否是一个冗余的 Projection 操作。
  • 另一方面由它自己和孩子结点的输入列做比较,输出相同则可消除。

谓词下推

谓词下推是非常重要的一个优化。比如

select * from t1, t2 where t1.a > 3 and t2.b > 5

假设 t1 和 t2 都是 100 条数据。如果把 t1 和 t2 两个表做笛卡尔集了再过滤,我们要处理 10000 条数据,而如果能先做过滤条件,那么数据量就会大量减少。谓词下推会尽量把过滤条件,推到靠近叶子节点,从而减少数据访问,节省计算开销。这就是谓词下推的作用。

谓词下推的接口函数类似是这样子的:

func (p *baseLogicalPlan) PredicatePushDown(predicates []expression.Expression) ([]expression.Expression, LogicalPlan)

PredicatePushDown 函数处理当前的查询计划 p,参数 predicates 表示要添加的过滤条件。函数返回值是无法下推的条件,以及生成的新 plan。

这个函数会把能推的条件尽量往下推,推不下去的条件,做到一个 Selection 算子里面,然后连接在节点 p 上面,形成新的 plan。比如说现在有条件 a > 3 AND b = 5 AND c < d,其中 a > 3 和 b = 5 都推下去了,那剩下就接一个 c < d 的 Selection。

我们看一下 Join 算子是如何做谓词下推的。代码是在 plan/predicate_push_down.go 文件。

首先会做一个简化,将左外连接和右外连接转化为内连接。

什么情况下外连接可以转内连接?左向外连接的结果集包括左表的所有行,而不仅仅是连接列所匹配的行。如果左表的某行在右表中没有匹配的行,则在结果集右边补 NULL。做谓词下推时,如果我们知道接下来的的谓词条件一定会把包含 NULL 的行全部都过滤掉,那么做外连接就没意义了,可以直接改写成内连接。

什么情况会过滤掉 NULL 呢?比如,某个谓词的表达式用 NULL 计算后会得到 false;或者谓词里面用 OR 条件连接,其中一个会过滤 NULL;又或者用 AND 条件连接,其中每个都是过滤 NULL 的。术语里面 OR 条件连接叫做析取范式 DNF (disjunctive normal form)。对应的还有合取范式 CNF (conjunctive normal form)。TiDB 的代码里面用到这种缩写。

接下来,把所有条件全收集起来,然后区分哪些是 Join 的等值条件,哪些是 Join 需要用到的条件,哪些全部来自于左孩子,哪些全部来自于右孩子。

区分之后,对于内连接,可以把左条件,和右条件,分别向左右孩子下推。等值条件和其它条件保留在当前的 Join 算子中,剩下的返回。

谓词下推不能推过 MaxOneRow 和 Limit 节点。因为先 Limit N 行,然后再做 Selection 操作,跟先做 Selection 操作,再 Limit N 行得到的结果是不一样的。比如数据是 1 到 100,先 Limit 10 再 Select 大于 5,得到的是 5 到 10,而先做 Selection 再做 Limit 得到的是 5 到 15。MaxOneRow 也是同理,跟 Limit 1 效果一样。

DataSource 算子很简单,会直接把过滤条件加入到 CopTask 里面。最后会被通过 coprocessor 推给 TiKV 去做。

构建节点属性

build_key_info.go 文件里面,会构建 unique key 和 MaxOneRow 属性。这一步不是在做优化,但它是在构建优化过程需要用到的一些信息。

build_key_info 是在收集关于唯一索引的信息。我们知道某些列是主键或者唯一索引列,这种情况该列不会在多个相同的值。只有叶子节点知道这个信息。build_key_info 就是要将这个信息,从叶子节点,传递到 LogicalPlan 树上的所有节点,让每个节点都知道这些属性。

对于 DataSource,对于主键列,和唯一索引列,都是 unique key。注意处理 NULL,需要列是带有 NotNull 标记的,以及考虑联合索引。

对于 Projection,它的孩子中的唯一索引列信息,跟它的投影表达式的列取交集。比如 a b c 列都是唯一索引,投影其中的 b 列,输入的 b 列仍然具有值唯一的属性。

如果一个节点输出肯定只有一行,这个节点会设置一个 MaxOneRow 属性。哪些情况节点输出只有一行呢?

  • 如果一个算子的孩子是 MaxOneRow 算子。
  • 如果是 Limit 1,可以设置 MaxOneRow。
  • 如果是 Selection,并且过滤条件是一个唯一索引列等于某常量。
  • Join 算子,如果它的左右孩子都是 MaxOneRow 属性。

总结

这是基于规则优化(RBO)的上篇。介绍了逻辑查询计划里面基本的算子,以及一部分的优化规则。后续我们还将介绍更多的优化规则,以及基于代价的优化(CBO)。

延展阅读

TiDB 源码阅读系列文章(一)序

TiDB 源码阅读系列文章(二)初识 TiDB 源码

TiDB 源码阅读系列文章(三)SQL 的一生

TiDB 源码阅读系列文章(四)Insert 语句概览

TiDB 源码阅读系列文章(五)TiDB SQL Parser 的实现

TiDB 源码阅读系列文章(六)Select 语句概览

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序猿

SQL优化法则小记

SQL优化技巧 1.选择最有效率的表名顺序(只在基于规则的优化器中有效): oracle的解析器按照从右到左的顺序处理 from 子句中的表名,...

3699
来自专栏跟着阿笨一起玩NET

C#常用工具类——Excel操作类

1201
来自专栏铭毅天下

干货 | 通透理解Elasticsearch聚合

使用Elasticsearch的过程中,除了全文检索,或多或少会做统计操作,而做统计操作势必会使用Elasticsearch聚合操作。

2523
来自专栏腾讯云流计算

Apache Calcite 功能简析及在 Flink 的应用

• Apache Calcite 是一个动态数据的管理框架,可以用来构建数据库系统的语法解析模块

1.1K7
来自专栏项勇

笔记30 | 数据存储之SQLite的介绍及使用

2598
来自专栏北京马哥教育

必备神技能 | MySQL 查找删除重复行

来源:码农有道 ID:b497155298 本文讲述如何查找数据库里重复的行。这是初学者十分普遍遇到的问题。方法也很简单。这个问题还可以有其他演变,例如,如何...

4719
来自专栏恰同学骚年

Hadoop学习笔记—8.Combiner与自定义Combiner

  在第四篇博文《初识MapReduce》中,我们认识了MapReduce的八大步凑,其中在Map阶段总共五个步骤,如下图所示:

941
来自专栏大内老A

在Entity Framework中使用存储过程(二):具有继承关系实体的存储过程如何定义?

在《实现存储过程的自动映射》中,我通过基于T4的代码生成实现了CUD存储过程的自动映射。由于映射的都是基于数据表结构的标准的存储过程,所以它们适合概念模型和存储...

1959
来自专栏Jackson0714

基础很重要~~04.表表达式-下篇

36716
来自专栏维C果糖

史上最简单的 MySQL 教程(二十四)「数据的高级操作 之 查询(中)」

where字句:用来判断数据和筛选数据,返回的结果为0或者1,其中0代表false,1代表true,where是唯一一个直接从磁盘获取数据的时候就开始判断的条件...

4166

扫码关注云+社区