深入了解 TiDB SQL 优化器

本文将从以下几个方面介绍：首先讲一下 TiDB 的整体架构，接下来就是优化器的两个比较重要的模块，一个是 SQL 优化，做执行计划生成；另一个模块就是统计信息模块，其作用是辅助执行计划生成，为每一个执行计划计算 cost 提供帮助。最后介绍下优化器还有哪些后续工作需要完成。

1. TiDB 的整体架构

TiDB 架构主要分为四个模块：TiDB、TiKV、TiSpark 和 PD，TiKV 是用来做数据存储，是一个带事务的、分布式的 key-value 存储，PD 集群是对原始数据里用来存储 key-value 里每一个范围的的 k-v 存储在每一个具体的 k-v 元数据信息，也会负责做一些热点调度；如热点 region 调度。在 Tikv 中做数据复制和分布式调度都是 rastgroup 做的，每一个读写请求都下放到 Tikv 的 leader 上去，可能会存在某些 Tikv 的 server 或者机器的 region leader 特别多，这个时候 PD 集群就会发挥热点调度功能，将一些热点 leader 调度到其他机器上去。TiDB 是所有场景中对接用户客户端的一层，也负责做 SQL 的优化，也支持所有 SQL 算子实现。Spark 集群是用来做重型 IP 的 SQL 或者作业查询，做一些分布式计算。

刨除 Spark，TiDB 集群主要有三个核心部分。最上层 TiDB 对接用户的各种 My SQL/Maria DB clients，ORMs，JDBC/ODBC，TiDB 的节点与节点之间本身是不做任何数据交互，是无状态的，其节点就是解析用户的 query，query 的执行计划生成。把一些执行计划下推到一些 Tikv 节点，将一些数据从 Tikv 节点拿上来，然后在 PD 中做计算，这就是整个 TiDB 的概览。

讲优化器之前需要讲一下 TiDB 中结构化的数据是如何映射到 K-V 数据的。在 TiDB 中只有两种数据，一种是表数据，一种是为表数据创建的 index 数据。表数据就是 tableID 加 RowID 的形式将其映射为 Key-Value 中的 key，表数据中具体每一行的数据一个 col 的映射为其 value，以 Key-Value 的形式存储到 Tikv 中。索引数据分为两种一种是唯一索引和非唯一索引，唯一索引就是 tableID+IndexID+索引的值构成 Key-Value 中的 key，唯一索引对应的那一行的 RowID，非唯一索引就是将 rowID encode 到 Key 中。

下面是 TiDB SQL 层的应用组件，左边是协议层，主要负责用户的 connect 连接，和 JDBC/ODBC 做一些数据协议，解析用户的 SQL，将处理好的结果数据以 MySQL 的形式 encode 成符合 MySQL 规范的格式化数据返回给客户端。中间的 Session Context 主要负责一个 session 里面需要处理的一些用户设置的各种变量，最右边就是各种权限管理的 manager、源信息管理、DDL Worker，还有 GC Worker 也是在 TiDB 层。

今天主要介绍 SQL 经过 parser 再经过 AST，然后 Optimize，经过 TiDB 的 SQL 执行引擎，还有经过 Tikv 提供的 Coprocessor，Coprocessor 支持简单的表达式计算、data scan、聚合等。Tikv 能让 TiDB 将一些大量操作都下推到 Tikv 上，减少 Tikv 与 TiDB 的数据交互带来的网络开销，也能让一部分计算在 Tikv 上分布式并行执行。

2. Query Optimizer

上图中的执行计划比较简单，就是两个表做 join，然后对 join 的结果做 count（*），join 方式是 merge join。

查询优化器解决的工作很复杂，比如需要考虑算子的下推，比如 filter 的下推，尽量下推到数据源，这样能减少所有执行数据的计算量；还有索引的选择，join Order 和 join 算法的选择，join Order 指的是当有多个表做 join 时以什么样的顺序去执行这些 join，不同的 join Order 意味着有不同大小的中间结果，而且 join Oder 也会去影响某一些 join 节点算法的选择；还有子查询的优化，如硬子查询是将其优化成 inner join 还是嵌套的方式去执行硬子查询而不去 join，这些在各种场景中因为数据源的分布不同，每一种策略都会在一种场景中有它自身的优势，需要考虑的方面很多，实现起来也比较困难。

优化器进行优化逻辑复杂，进行优化需要进行一些比较重的计算，为了降低一些不必要的计算。比如对一些简单的场景点查，根据一些组件查一条数据，这种就不需要经过特别复杂的计算，这种需要提前标记出来，直接将索引的唯一值 ID 解析出来，变成一次 k-v scan，这种就不需要做复杂的优化，不用去做执行树的迭代。目前 TiDB 中的 update、delete 、scan 都支持 k-v scan，还有 PointGet Plan 也支持这种优化。

TiDB 的 SQL 优化器分为物理优化阶段和逻辑优化阶段，逻辑优化阶段的输入是一个逻辑优化执行计划，有了初始逻辑优化执行计划后，TiDB 的逻辑优化过程需要把这个逻辑执行计划去应用一些 rule，每一个 rule 必须具备的特点是输出的逻辑执行计划与输出的逻辑执行计划在逻辑上是等价的。逻辑优化与物理优化的区别是逻辑优化区别数据的形态是什么，是先 join 再聚合还是先聚合再 join，它并不会去聚合算子是 stream 聚合还好 hash 聚合，也不会去关注 join 算子是哪一种物理算子。同时也要求 rule 将产生的每一个新的逻辑执行计划一定要比原来输入的逻辑执行计划要更优，如将一些算子下推到数据源比不下推下去要更优，下推后上层处理的数据量变少，整体计算量就比原来少。

接下来就讲一下 TiDB 中已经实现的一些逻辑优化规则，如 Column Pruning 就是裁减掉一些不需要的列，Partition Pruning 针对的是分区表，可以依据一些谓词扫描去掉，Group By Elimination 指的是聚合时 Group By 的列是表的唯一索引时可以不用聚合。Project Emination 是消除一些中间的没用的一些投影操作，产生的原因是在一些优化规则以自己实现简单会加一些 Project ，还有就是从 AST 构造到最初逻辑执行计划时也会为了实现上的简单会去添加一些中间节点的投影操作，Outer Join Simplification 主要针对 null objective，如 A>10，而 A 有又是 null 而且又是 inner 表中的列时，Outer Join 就可以转化为 inner join。

Max/Min Eliminatation 在有索引的时候非常有用，如 Max A 是一个索引列，直接在 A 上做一个逆序扫第一行数据就可以对外返回结果，顶层还有一个 Max A，这个是为了处理 join 异常情况，如 Max 和 count 对空输入结果值行为结果是不一样的，需要有一个顶层的聚合函数来处理异常情况，这样就不需要对所有数据做 max，这样做的好处就是不用做全表扫描。

Outer Join Elimination 可以将其转化为只扫描 Outer 表，比如当用户只需要使用 Outer Join 的 Outer 表，如例子中只需要 t1 表中的数据，如何 inner 表上的 key 刚好是 inner 表上的索引，那么这个 inner 表就可以扔掉，因为对于 outer 表中的每一条数据如果能 join 上，只会和 inner 表的一行数据 join 上，因为 inner 表上的 key 是唯一值，如果对应不上就是 null，而返回的数据只需要 outer 表，inner 表上的数据不需要。还有一种情况是父节点只需要 outer 表的唯一值，再做 outer join 如果对应上会膨胀很多值，而上层只需要不同值这样就不需要膨胀，这样就可以消除在 outer 表做一个 select 的 distinct 操作。

Subquery Decorrelation 是一个多年研究的问题，上图例子是先从 t1 表中扫一行数据，去构造 t2 表的 filter，然后去扫描 t2 表中满足这样的数据，对 t2 表的 A 做一个聚合，最终是 t1 表的 A 类数据小于求的和，才把 t1 表的这行数据输出。如果执行计划按照上述逻辑执行，那么每一行 t1 的值都会对 t2 进行全表扫描，这样就会对集群产生非常大的负担，也会做很多无用的计算。因此可以将优化成先聚合再 join，就是先把 t2 表先按过滤的条件的列做一个 group by，每一个 group 求 t2 表 A 的和，将其求得的和再去和 t1 表做 join。上层的 arcconditon，这样就不会对 inner 表频繁的做 inner 操作，从整体上看不用做全表扫描，每一行 outer 都会对 t2 表做扫描。

聚合下推不一定要优，但在某些场景很有用。两个表做 join，以上面一个表为例，join 的结果以 t1 的 a 做一个 group by。如果 t1 表的 t1.a 列重复的值很多，先去做 join 就会导致重复的值和 t2 表能够匹配的值重复很厉害，再去做聚合计算量也非常大，有一种策略是将聚合下推到 t1 表上。将 t1 表上 a 做一个聚合，很多重复的 t1.a 再 join 之间就压缩成一条，join 操作的计算量非常轻，在更上层的聚合相应减轻不少负担。但是不一定每种情况都有用，如果 t1.a 中的数据重复值不多，那么下推下去的聚合将数据过滤一遍又没有起到聚合的效果。Top N Limit Push Down 只需要将其 outer join push 到 outer 端，这是因为 outer 表的数据要输出，只需要拿三条数据和 inner 表做 join，如果有膨胀，再放一个 top/limit 将数据只限制在三条。相反如果将 topN 不 push 下去，那么从 table3 读取的数据会很大。

还有一个难题是 Join Reorder，目前 Join Reorder 的算法有很多。统计信息精准度一定的情况下，选出一个最好的 Join Reorder 算法最好的方式是用 DP 算法。如果两者信息精确，利用动态规划得出的算法一定是最优的，但是现实中统计信息不一定优，如两张表信息是优但是 join 后的结果不一定符合数据真实分布，可能有推导误差。A、B 统计节点是推导出来的，再去推导节点的统计信息，误差就被放大，因此 DP 的 join order 在使用真实的统计信息做 join order 再去推导统计节点的统计信息所做出来的 order 也不一定是好的。

在 TiDB 中使用的 join order 是一个子树，使用状态压缩的方式做的，就是 6 的整数用二进制的形式表示 110， 0 表示节点不存在，1 表示节点存在，第 1、2 节点存在，第 0 号节点不存在。就决定了最优的 join 顺序是什么，这样 DP 算法推导就比较简单，不断的枚举其子集合，6 可以分为 110 和 10，分别 join 两个子集合，选择所有情况中最小的一个；这种方式时间复杂度很高，如果节点过多，做 join reorder 的时间会很长。还有 DP 算法是用整数代替 join 节点，如果 10 个节点就是 2¹⁰，20 个节点就是 1M 内存。因此当节点比较大的时候采用贪心策略做 join reorder，实现原理是先将所有的 join recount 估算，从小打到大排序，一次选择按边相连的节点去做 join，如图一开始初始是 t1 和 t2 做 join 结果估算有 800，由于 t3 的 count 也是 100，也需要考虑 t1 和 t3 做 join，join 出来是 200，则 t1 和 t3 优先做 join，然后再遍历节点数后最小的节点与当前 join 数做 join，当为 join 节点集合为空时整个 join 树就生成了。但是局部最优不一定全局最优，并不能把所有情况都考虑最好的 join 顺序。

接下来是物理优化阶段，逻辑优化并不决定以什么算法去执行，只介绍了 join 顺序，并没有说要用那种 join 方式。物理优化需要考虑不同的节点，不同的算法对输入输出有不同的要求，如 hash 和 merge join 实现的时间复杂度本身不一样。要理解物理优化的过程要理解什么是物理属性。物理属性是一个物理算法所具备的属性，在 TiDB 就有 task type 属性，就是这个算法是应该在 TiDB 中执行还是在 Tikv 中执行；data order 说的是算法所产生的数据应该以什么样的顺序属性，如 merge join 是按 outer join 的 key 有序的。Stream 聚合也是按照 group by 的 column 有序。但是有些算法无法提供 join 顺序，如 hash join，还会破坏数据的顺序，hash join 无法对外提供任何顺序上的保证。在分布式场景中做执行计划时需要考虑分布的属性，如 hash join 在一个分式的节点上执行，考虑的是选表多下搜的方式，如果想正确出结果最好的方式是将小表和大表的数据都按照 join 的 key 下放到不同的机器上，那么分布式的 hash join 特点就是 join 的 key 分布在同一台机器上。在 TiDB 没有考虑数据分布的特性，动态规划的状态就是输入的逻辑状态是什么，实现的逻辑执行计划的物理执行计划需要满足什么样的物理属性，最后推导出一个最佳的物理执行计划。这样同一个逻辑节点可能会多次被父节点以不同路劲访问它，因此需要缓存中间节点，下次父节点以同样的动态规划状态访问直接将之前最佳的结果返回就行。

上图的实例是对两个表做 join，join 后数据按照 join key 排序，假设 t1 和 t2 表都在各自的 join key 上有索引，对于 t1 和 t2 表扫描有两种方式，一种是 index scan 能够满足返回的数据以 index 有序，或者 table scan 不能满足 index scan 有序，nominalsort 是 TiDB 内部优化算子，既不会出现在逻辑执行计划里面也不会出现物理执行计划里面，只是在做物理执行计划辅助作用，从一开始调用动态规划过程，输入逻辑计划要求满足的物理属性是空，接下来可以用物理 sort 算子和 nominalsort 算子，其本身不 排数据，而是将排数据的功能传递给子节点。

在物理优化中比较重要的一点是如何选择索引，没有索引一个慢查询会导致所有集群都慢。最后引入 Skyline index Pruning，当要选择那个选项最优时有多个维度可以考量，访问一个表的方式有多种方式选择，其要求就是父节点要求子节点返回的数据是否有序，还有就是索引能够覆盖多少列，这是因为用户建索引并不是一定按照最优解来建。

从优化过程来说，算法并不是最优的，应用完一个 rule 不会再次去应用，但是实际是会多次使用的。解决有 Memo 优化，就是将所有表达式存储，将等价表达式存储于一个 group 里面，将所有 rule 用最小化、原子化做 group expression。

3. Statistics

统计信息是用来估算 row count，需要估算的 row count 有 filter、join、聚合。TIDB 中存储的统计信息有直方图，主要用于估算范围查询的统计信息，被覆盖的其 count 直接加上去，部分覆盖的桶使用连续均匀分布的假设，被覆盖的部分乘以桶的 rowcount 加上去；另一个是估算点查询的 rowcount，可以理解 Min-Sketch，只是估算的值不再是 0 和 1，数据代表是这个位置被 hash 到了多少次，如一个数据有 D 个 hash 函数，将其 hash 到 D 的某个位置，对具体位置加上 1，查询也做同样的操作，最后取这 D 位置最小的值作为 count 估计，这个估计在实际中精度较高。

TiDB 收集统计信息的方式有很多，首先手动执行 analyze 语句做统计信息的搜集；也可以配置自动 analyze，就是表的更新超过某些行数会自动做 analyze；还有 Query Feedback，就是在查询请求，如果查的数据分布和以前统计的数据分布信息不太匹配回去纠正已有的统计信息。

4. Future Work

接下来一些工作就是查询计划的稳定性，重要的是索引的准确，还有就是有些算法的选择也会影响查询计划的稳定性；The Cascades Planner 就是要解决搜索空间的搜索算法的效率问题，搜索空间导致执行计划不够优的问题。还有快孙 analyze，目前表以亿起步，如果现场采样，会比较慢因此会采取一些手段加速 analyze 过程。Multi-Column Statistics 主要生死用来解决多列之间的相关性，以前做 row count 估算都是基于 column 与 column 间的不相关假设做 row count，这样估计的值比实际值偏大，有多列相关估算准确度会提高很多。

作者介绍：

张建，PingCAP TiDB 优化器与执行引擎技术负责人，前阿里云 MaxCompute SQL 执行引擎研发工程师，目前主要研究 SQL 优化与执行，分布式计算等。

本文来自 张建 在 DataFun 社区的演讲，由 DataFun 编辑整理。