TiDB中的优化器追踪

引言

在计算机技术产业蓬勃发展的大环境下，每天都有成千上万的服务器和服务器集群来处理各行各业运作过程中所产生的海量数据和请求。对于数据的加工处理和请求的快速响应是当今计算机软硬件技术在实际生产中应用时需要解决的最重要的实际问题之一。在传统的信息技术领域里，单机数据库系统承担着大部分数据加工处理以及响应请求的工作。传统的单机数据库通过一台服务器来提供服务，通过单核或多核 CPU 进行计算，单个硬盘或硬盘阵列来进行存储。

当今知名度最高的数据库产品当属 Oracle 旗下的 MySQL。MySQL 是单机环境下基于 SQL 语言标准所开发的单机关系型数据库，被广泛应用于 IT、金融、制造、医疗等行业中。在使用 MySQL 的过程中，数据库管理员（DBA）需要以表（Table）的形式来定义数据的存储格式，然后通过查询语句（Query Statement）根据实际需求来获取数据。其中 SQL 语法只说明了需要的数据满足哪些要求，并没有指明如何取获取这些数据。例如想要获取成绩表中不及格男生的名单，实际执行的时候既可以先筛选男生再筛选不及格的学生，也可以先筛选不及格的学生再筛选男生。在支持 SQL 语法标准的关系型数据库中，具体的数据获取过程由数据库产品的优化器（Optimizer）来决定，然后将选取的执行计划（Plan）交由执行器（Executor）去执行。

因此，关系型数据库中的优化器需要对用户给出的查询语句选取合适的执行计划（Plan）来使得获取所需数据的计算量和内存使用量尽量少。在 MySQL 中提供了优化器追踪功能（Optimizer Trace），用以追踪优化器的整个优化流程。优化追踪使得整个优化流程清晰明了，同时使 DBA 能够在优化器选取的执行计划不太理想的情况下比较轻松地找出错误原因。

随着信息产业的发展，各种大型平台和应用，如微信和淘宝等，每天收到来自世界各地的数据和请求量不断上升。此时 MySQL 等单机数据库已经不能满足这种大规模的需求，于是业界开始使用计算机集群来提供分布式数据库服务。在众多新兴的分布式数据库产品中，TiDB 是近几年蓬勃发展的开源分布式数据库，已经在对国内各大银行以及互联网公司提供数据库服务。TiDB 是基于 SQL 语法，兼容大部分 MySQL 特性的分布式关系型数据库，用户可以很方便地将服务从单机的 MySQL 迁移到分布式的 TiDB 上。然而由于 TiDB 的开发时间不长，产品自身尚不完善，在实际的生产过程中会遇到很多优化器选取执行计划不理想的情况。在 TiDB 中加入类似 MySQL 的优化器追踪功能能够有效地增加 TiDB 的开发和维护效率，对提高产品的使用体验和开发速度能够有很大的帮助。

TiDB 主要优化流程

TiDB 目前采取的主要优化框架分为逻辑计划建立（Logical Plan Build）、逻辑优化（Logical Optimize）、物理优化（Physical Optimize）以及后优化（Post Optimize）四个步骤。下面通过一条 SQL 语句来展开说明：

SELECT student.name, grade.score FROM student, grade WHERE student.id = grade.id AND student.gender='Male' AND grade.score < 60;

直接解释就是连接 student 和 grade 两张表来选取 name 和 score 两列，其中 student 的 id 要和 grade 的 id 相等，而且 student 的 gender 是 Male，同时 grade 中记录的 score 要小于 60。其中 student 表有 id, name, gender 三项，grade 表有 id, score 两项。简单来说就是在引言中所提到的，列出所有不及格的男同学的姓名和成绩。

逻辑计划建立

当 TiDB 的服务器收到一条语句，会对其进行解析，得到对应的抽象语法树（AST），然后在此 AST 的基础上进行构建逻辑计划。

逻辑计划中有这么几个重要的算子：

  • DataSource
  • Projection
  • Join
  • Selection
  • Aggregation

其中 DataSource 表示从一张表中读取数据，Projection 表示对当前的数据进行某种映射，Join 表示将两张表进行连接操作，Selection 表示对当前的数据进行某种筛选操作，Aggregation 表示对某些具有相同特征的数据进行聚合操作来得到方差或者平均数等信息。

在逻辑计划的建立过程中，会从顶向下递归地构建逻辑计划。对于语句(1)，最后构建的逻辑计划为：

[DataSource(student), DataSource(grade)] -> Join -> Selection -> Projection

即从 student 和 grade 两张表里面读取数据，进行连接（Join）操作（此时为笛卡尔积操作），然后在连接的结果上面进行筛选（Selection）操作，然后对通过筛选的数据条目进行映射（Projection）来挑选出所需的 name 和 score 两列。

表达式重写

逻辑计划的建立过程中，除了递归地构建逻辑算子之外，还需要对表达式进行重写。TiDB 中的 Expression Rewriter 会进行两类不同的表达式重写。

第一类表达式重写是将 AST 中的表达式处理成 TiDB 后续流程需要用到的表达式对象。在语句(1)中，会将 student.gender = 'Male' 处理成一个可以通过执行器进行计算的 Scalar Function 并将其设为 Selection 算子的筛选条件。这个过程中的表达式重写就属于第一类表达式重写。

第二类表达式重写是将表达式转换为等价的另一个表达式，以方便优化器和执行器的后续操作。比如对于整数 x，表达式 x < 2.3 等价于表达式 x < 3。此外对于形如 a = b AND b = c 的表达式，可以得到一个在后续流程中可能会起到作用的新表达式 a = c。

逻辑优化

在逻辑计划建立完成之后，对逻辑计划进行初步的逻辑优化。TiDB 中的逻辑优化为基于规则的逻辑优化，通过匹配预设好的几条优化规则来对逻辑计划进行等价的变换，使得执行计划的执行效率更高。

当前 TiDB 中支持的逻辑优化规则有以下几条：

  • Column Pruning
  • Predicate Push Down
  • Join Reorder
  • Outer Join Elimination
  • Projection Elimination
  • Aggregation Push Down

其中能够应用在逻辑计划(2)上的有谓词下推（Predicate Push Down）。在谓词下推的过程中，原本 Selection 的筛选条件 student.gender = 'Male' 和 grade.score < 60 会被下推到 Join 和 DataSource 之间。因为可以在两个表做 Join（此处为笛卡尔积）之前先对数据进行筛选。这样一来，在保证数据的正确性的同时，Selection 和 Join 操作需要处理的数据只会变少不会变多，也就是得到了一个严格不差与原本逻辑计划的等价逻辑计划。此外，Selection 的另一个筛选条件 student.id = grade.id 会转化为 Join 算子的等值条件（Equal Condition），可以在做 Join 的时候通过选取合适的 Join 算法来快速地进行连接操作。

最后逻辑计划(2)会在逻辑优化之后得到一个等价的逻辑计划：

(3) {DataSource(student) -> Selection, DataSource(grade) -> Selection} -> Join -> Projection

可以看到原本的 Selection 算子被下推到了 Join 算子的下面。这里看不到的是 Seletion 中的 student.id = grade.id 变成了 Join 算子的等值条件。

物理优化

TiDB 中的物理优化分为统计信息拉取、准备访问路径、物理计划枚举三个部分。接下来对这三个部分依次说明。

统计信息拉取

统计信息拉取是关系型数据库优化器中很关键的一步。统计信息即通过对数据库中已有数据的采样来估计数据的分布情况。通过统计信息我们可以估计某个具体的物理操作可能的运行时间和内存使用开销是多少，以及在操作后大概会有多少行数据保留下来。对于某个物理操作代价的估计是优化器基于代价选取最佳物理计划的关键所在，对于物理操作后有多少条数据保留的估计对于代价的计算也是至关重要的。

统计信息的拉取是自底向上传递的，从最底层的 DataSource 进行采样，并把统计信息根据当前算子的情况向上传递。比如 grade 中 score 大于 30 的记录大约有 1000 行，那么在经过了 grade.score * 2 这么一个 Projection 算子之后，我们可以知道 grade 中 grade.score * 2 大于 60 的记录大约有 1000 行。再比如 student 表有约 1000 行，grade 表有约 100 行，那么我们可以知道 student 表和 grade 表做笛卡尔积得到的结果集会有约 100000 行。TiDB 中优化器所用到的统计信息[1]就是以这样的方式自底向上传递的。

准备访问路径

对于一个给定的表 student，如果 student 表维护了 id 和 name 两个列对应的索引。那么不仅可以按顺序地查询 student 中所有的记录，也可以快速以 id 或者 name 从小到大或者从大到小的顺序访问 student 中的记录，甚至可以快速地有序查找 student 中 id 在某个范围内的记录。此时我们称 student 有直接访问、通过索引 id访问、通过索引 name 访问三种访问路径，其中通过索引 id 访问和通过索引 name 访问可以分别提供 id 列和 name 列的顺序。此外，在 TiDB 中还有联合 id 和 name 两个索引的访问路径，以及合并 id 和 name 两个索引的 Index Merge 访问方式。

在对查询涉及的表所维护的索引进行考察之后，会得到一些可能会用到的访问路径，这些访问路径有各自的代价以及能够提供的顺序信息，这些信息都会被用到后续的物理计划枚举里面。

物理计划枚举

对于逻辑计划中的部分关键算子，需要获取一个具体的对应的物理算子，这个过程称为物理计划枚举。对于 DataSource 我们会根据访问路径的不同细分为 Table Scan，Index Scan 以及 Index Lookup 等不同的物理计划；对于 Join 有 Hash Join，Index Nested Loop Join，Sort Merge Join 三种不同的 Join 算法；对于 Aggregation 有 Hash Aggregation，Stream Aggregation 两种不同的 Aggregation 算法。

此外 TiDB 架构中计算与存储分离，负责数据存储的模块有 Key-Value 型的 KV 存储引擎 TiKV 以及按列存储的存储引擎 TiFlash。对于一个表的读取可以选择通过不同的存储引擎来读取，同时有些聚合、筛选、映射等操作可以在从存储引擎读取数据的时候去完成。因此 TiDB 中的物理计划枚举除了需要决定通过哪个的访问路径来访问数据以及采取哪个的算法之外，还需要决定通过哪个存储引擎来读取数据以及具体的聚合、筛选、映射等操作在 TiDB 进行还是下推到存储引擎来进行。

例子分析

逻辑计划(3)在经过整个物理优化流程后可能会得到这样一个具体的执行计划：

(4) [TableScan(student)[TiKV] -> Selection[TiKV], IndexLookup(grade)[TiFlash] -> Selection[TiDB]] -> HashJoin[TiDB] -> Projection[TiDB]

该执行计划具体地指出了各个操作之间的顺序，每个表的访问方式以及所属的存储引擎，每个操作具体执行所在的模块。

后优化

后优化阶段会对执行计划进行微小的调整，当前 TiDB 的后优化阶段只会消除无用的 Projection 算子。

TiDB 中的优化器追踪方案

大致分析了 TiDB 的优化流程之后，可以清晰地看到优化流程中需要追踪的关键信息。在逻辑计划建立阶段，需要跟踪整个逻辑计划递归建立的过程，以及关注表达式重写对表达式做的处理以及等价转换。在逻辑优化阶段，需要关注每个逻辑优化规则是否得到了应用，同时对于成功应用的逻辑优化规则需要展示出其对逻辑计划产生的影响。在物理优化阶段，需要关注拉取统计信息的过程、每个算子上具体的统计信息数据、各个表上可用的访问路径、各个算子的子节点可以提供给父亲节点的数据顺序、关键算子物理计划的枚举过程、枚举过程中根据代价来选择最优物理算法的过程、决定每个表从哪个存储引擎读取的以及决定每个物理算子在哪个模块运行的过程。

优化器追踪结果的展示

对于优化器追踪的结果，借鉴 MySQL 中的优化器[2]实现。使用系统变量来作为优化器追踪功能的开关，以 JSON 格式将优化器追踪信息记录在指定的文本文件中。对于优化的不同阶段，以及每个细节的步骤通过 JSON 不同的字段来展示，整个追踪的生成过程具有较高的灵活性，对于用户的可读性也能得到很好的保证。

具体 JSON 字段设计

首先需要有 Original Statement 字段表示原本的语句，然后根据优化流程分出 Logical Plan Build，Logical Optimize，Physical Optimize，Post Optimize 四个字段。整个追踪结果的 JSON Object 对外展示为：

{ 
  Original_Statement: {},
  Logical_Plan_Build: {},
  Logical_Optimize: {},
  Physical_Optimize: {},
  Post_Optimize: {},
}

其中 Original_Statement 即为原始的语句。

相关工作

当前的关系型数据库产品中提供完整的优化器追踪功能的只有 MySQL。MySQL 从 5.6 版本起开始提供优化器追踪[2]，能够大致地追踪整个优化流程。其开源的代码实现对于在其他关系型数据库产品中加入这一功能提供了极大的参考价值，对笔者的这一设计工作也有很大的启发作用。

但是遗憾的是这一优化器追踪模型不能很方便地地移植到一些较新的优化器框架，如 Cascading Planner[3] 中。如何设计一个灵活性高可扩展性强的优化器追踪模型也是一个值得进一步探讨的课题。

总结

这篇文章主要介绍了在 TiDB 中加入优化器追踪的相关功能设计。从关系型数据库的基本特点开始分析，介绍了 TiDB 这一分布式关系型数据库产品的优化器基本流程。对优化流程中的关键步骤进行了简要的分析，并指出了在实际生产环境中 DBA 和开发者会关注的重要信息。此外，参考 MySQL 中的优化器追踪设计了适用于 TiDB 的基本优化器追踪功能使用和结果展示方案，对整体的 JSON 对象字段进行了初步的设计。

下一步需要研究的内容是更加具体的细节设计以及在 TiDB 这一开源项目中的实际代码落地。同时可用进一步探讨类似的优化器追踪模型如何扩展到其他的优化器框架当中。

参考文献

[1] TiDB 源码阅读系列文章（十二）统计信息(上)，https://pingcap.com/blog-cn/tidb-source-code-reading-12
[2] MySQL: The Optimizer Trace, https://dev.mysql.com/doc/dev/mysql-server/latest/PAGE_OPT_TRACE.html
[3] Cascading Planner, https://www.cascading.org

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容