提示：公众号展示代码会自动折行，建议横屏阅读
「第一部分 查询优化器框架」
关系型数据库是一个通用系统软件，SQL作为一种结构化查询语言，用户不需要关注怎么做，只需要描述做什么，然后交由SQL引擎来处理。因为关系代数提供的等价性，同一个查询可以用不同的SQL语句描述。为防止用户所写的"不好的"SQL执行慢，这就需要查询优化器快速而准确地选择出一个效率较高的执行计划。
一般的查询优化器基于代价计算模型，包含SQL形态的变换，确定访问路径和多表连接顺序等几个重要的步骤。这些步骤被统一在一个优化器框架之内，相互配合将用户SQL生成最有效率的执行计划。Cascades是很多数据库都会采用的优化器框架，MySQL的官方并未说明用的何种优化器框架，但主要流程和经典的Cascades框架有明显的区别。MySQL的优化器更像是一种两阶段的模式，分为形态变化和代价计算。
TXSQL承袭MySQL优化器框架。本篇文章为优化器系列文章的开篇，以MySQL8.0.22版本为基线，简要介绍MySQL优化器的部分工作原理。
1.1 主要流程
如图1-1所示，TXSQL在接受一条SQL命令后，先将SQL解析成server认识的抽象语法树。随后优化器对抽象语法树做基本变换，包括对表达式做预处理，对SELECT_LEX结构做改写。在基本变换后，利用cost-based optimizer选择访问路径和找出最优的多表连接顺序。当优化器"认为"找出了最优的执行计划，再将逻辑执行计划转换成物理执行计划最终执行。
在一般经典的数据库优化器框架中，上述过程是一个迭代收敛过程，执行足够的次数或者迭代计算代价直至收敛。MySQL未采用这种方式，在优化过程中，现有的MySQL优化器框架仅执行一次优化，这是框架层面还欠改进的地方。但这满足云环境快速响应数据库的需求，牺牲一部分准确度，达到快速响应的目标。
1.2 主要数据结构
MySQL 8.0 server层有优化执行相关的多个重要的数据结构，这些数据结构描述了从解析到执行的各个逻辑：
「第二部分 transformation算法」
transformation又称为改写，改写算法将逻辑执行计划变换成语义相同的另一种形式，以达到计划层面提升效率的目的。MySQL优化器已经实现的改写算法包含子查询展平，外连接消除，衍生条件下推，谓词转换及推导和物化子查询等。
改写算法一般分为基于规则和基于代价两类，现阶段MySQL主要以基于规则的改写算法为主，下面介绍三种基本的改写算法。
2.1 外连接消除
外连接消除改写将外连接转换为内连接。这将会扩大算法的计划空间，参与连接的两张表的连接顺序会变得多样化，以便选择出扫描效率和连接效率最高的策略。该算法需要在以下至少一个条件为真的前提下触发执行：
- where条件包含至少一个inner table相关的空值拒绝条件。
- outer join包含在一个含有inner table相关的空值拒绝条件的JOIN之内。
举个例子：
select * from t1 left join t2 on t1.a = t2.a left join t3 on t2.a = t3.a where t3.b = 1;该SQL语句中，由于t3.b = 1对于`left join t3 on t2.a = t3.a`来讲是一个空值拒绝条件，即将输出带有t3.b为NULL值的记录直接过滤掉。与`inner join t3 on t2.a = t3.a`的输出结果完全一致。这符合条件1。
同样地，由于`left join t3 on t2.a = t3.a`的连接条件`t2.a = t3.a`是`t1 left join t2`的空值拒绝条件，由于`t1 left join t2`被嵌套在`left join t3 on t2.a = t3.a`之内，所以`t1 left join t2`与`t1 inner join t2`的输出结果完全一致。这符合条件2。
因此该SQL最终的执行计划为：
-> Inner hash join (t3.a = t1.a) (cost=1.05 rows=1) -> Filter: (t3.b = 1) (cost=0.35 rows=1) -> Table scan on t3 (cost=0.35 rows=1) -> Hash -> Inner hash join (t2.a = t1.a) (cost=0.70 rows=1) -> Table scan on t2 (cost=0.35 rows=1) -> Hash -> Table scan on t1 (cost=0.35 rows=1)2.2 子查询展平
MySQL优化器为了提升子查询处理的速度，会将含有in/exists/not in/not exists的子查询转成semi-join或者anti-join的等价表示，通过table pullout将子查询中的表拉到外query block，提升执行效率。
下面介绍该算法可以处理的几种形式：
形式一：select t1.a from t1 where t1.a in (select t2.a from t2); → select t1.a from t1 semi join t2 on t1.a = t2.a;形式一含有in subquery的语句可以转换成semi-join的物理算子，所以将会提升效率，同样地还有如下含有exists subquery的形式二。
形式二：select t1.a from t1 where exists (select 1 from t2 where t1.a = t2.a); → select t1.a from t1 semi join t2 on t1.a = t2.a;与in subquery/exists subquery稍有不同的是，not in/not exists的转换并非完全相同，这与NULL值的性质有关系。
形式三：select t1.a from t1 where not exists (select 1 from t2 where t1.a = t2.a); → select t1.a from t1 anti join t2 on t1.a = t2.a where t2.a is not null;形式三将改写成含有多一个where条件，将空值记录过滤掉，但对于not in subquery，在子查询中有空集，所以可以直接转成anti-join。
形式一：select t1.a from t1 where t1.a not in (select a from t2); → select t1.a from t1 anti join t2 on t1.a = t2.a;数据库中的NULL一般代表不确定状态，或者无意义。想要判断一个值是不是NULL，MySQL提供了is null或者is not null的语法来运算，返回TRUE或者FALSE。而如果NULL参与一般运算，运算过程NULL会表现的更像FALSE。比如NULL与其他值进行比较或者算数运算(如大于小于等于不等于加减乘除)，结果为NULL，如果作为where谓词，和FALSE的效果一样。下面是一个NULL参与逻辑运算的结果。
在MySQL最新版本的优化器中，以上转换也可以应用到单个表组成的update或者delete语句，这些语句同样需要含有[not] in或者[not] exists子查询，同时子查询中不应该含有order by或limit。
2.3 衍生条件下推
衍生条件下推是将外部条件下推至子查询中以减少需要处理的数据行数的改写。MySQL优化器对该条规则的作用限定了一些场景：
- 当内部子查询没有聚合或者窗口函数时，可以将外部衍生条件下推至内部子查询中。
select * from (select a,b from t1) as dt where a > 10 and b < 11 --> select * from (select a,b from t1 where a > 10 and b < 11) as dt;- 当内部子查询含有group by但没有窗口函数，且外部条件列非group by时，外部条件可以下推到内部子查询变成having。
select * from (select a,b,sum(c) as sum from t1 group by a,b) as dt where sum > 100 --> select * from (select a,b,sum(c) as sum from t1 group by a,b having sum > 100) as dt;- 当内部子查询含有group by且外部条件列是内部子查询的group by列时，外部条件可以下推到内部子查询。
select * from (select a,b,sum(c) as sum from t1 group by a,b) as dt where a > 10 --> select * from (select a,b,sum(c) as sum from t1 where a > 10 group by a,b) as dt;MySQL在8.0.22版本中推出了衍生条件下推算法，满足以上三种场景的任一种情况均可以通过该算法转换执行计划。
现在MySQL优化器中改写算法并不太健全，很多成熟数据库中的算法还没有。比如连接消除执行过程中不必要的表扫描，win-magic算法将特定形式的SQL转成含有窗口函数的形态，标量相关子查询转换等。
由于实际需求，我们团队也将考虑增强TXSQL的优化器transformation能力。
「第三部分 join reorder算法」
对多表连接来讲，如果一条含有N个表做连接的SQL，仅仅是左深规则就有差不多N!种连接顺序。若N等于10，单单左深连接的计划空间就是3628800，可见这是一个指数级别增涨的计划空间，因此枚举所有的计划是不现实的。MySQL采用的是贪心算法加剪枝的方法确定连接顺序，即下一步的选择是基于前一步操作的局部最优值。下一步的选择是有控制地尽可能广泛地搜索，选择当前最优结果。
t1 has 17 found rows; t2 has 4 found rows; t3 has 2 found rows; t4 has 3 found rows;SQL-1: select * from t2 inner join t1 on t1.a = t2.a inner join t3 on t1.a = t3.a inner join t4 on t3.a = t4.a;SQL-2: select * from t2 inner join t1 on t1.a = t2.a inner join t3 on t1.a = t3.a straight_join t4 on t3.a = t4.a;SQL-3: select /* join_order(t1,t2,t3,t4) */ * from t2, t1, t3, t4 where t1.a = t2.a and t1.a = t3.a and t3.a = t4.a;3.1 启发式剪枝规则
MySQL通过两个参数控制基于代价的启发式剪枝和遍历深度。
- optimizer_prune_level，默认为1(打开)，表示在制定连接顺序时搜索过程根据代价做一些剪枝。剪枝规则是如果计算出的代价比之前同一层节点代价大，就删掉这一分枝。这种剪枝虽然可能剪掉一个最优连接顺序的分支，但它大大减少了时间花销。如果你认为优化器错过了一个更好的查询方案，则可以选择将该选项关闭(设置为0)。
- optimizer_search_depth，默认为62，该变量代表每次局部最优地确定一个表连接顺序之后，优化器确定下一个表时深度优先搜索的深度。将此参数设置小一点对于表数目偏多的查询可以大大减小搜索空间。默认值62在包含表数目较多的查询中会耗时严重。
结合以上两个参数，我们通过一个简单的例子来描述一下MySQL制定连接顺序的贪心算法。首先MySQL对所有表做启发式的排序。这里的排序规则包括：
- 依赖关系，如derived table应该排在被依赖表的前面。
- 记录条数，记录条数比较少的小表应该排在前面，因为中间结果可能会少。
- 出现顺序，如果上面两条都一样就再根据连接条件中的出现顺序决定。
如图3-1所示，第一步中，优化器对每张表关于行数做排序，获得(t3, t4, t2, t1)的顺序。
然后从每一步待优化的表中找到所有M个表中代价最小的。
这里M等于optimizer_search_depth，如果M大于当时剩余表的数目，就全部搜索。在此期间如果正在搜索的路径比同层已经搜索过的路径的代价大，或者比目前最优计划的代价大，就将其剪枝掉。
因为图3-1中例子中设置的optimizer_search_depth为2，在确定t3之后还要向下搜索深度为2的两张表的顺序。第三步同理，当发现(t3, t4, t1)的计算代价比同层的(t3, t4, t2)的代价大时，将其剪枝掉。最终得到连接顺序为(t3, t4, t2, t1)。
3.2 指定连接顺序
使用者也可以通过人为指定的方式去确定连接顺序，这里也分为两种方式：
- straight_join的连接方式，优化器会根据straight_join的顺序去设置对应表的连接顺序。
- join_order hint，优化器提供comment style的hint去让用户指定一个特定的连接顺序，从而避开优化器再计算。
以上两种方式使优化器省略或者全部省略多表连接算法的贪心搜索。SQL-2将最终连接顺序指定为(t3, t2, t1, t4)，而SQL-3将最终的连接顺序指定为(t1, t2, t3, t4)。
「第四部分 代价模型」
4.1 权重可调整
MySQL计算代价的总体思路是首先给每个算子赋予一个cost，然后给每部分计划都赋予一个cost，然后查找多个计划的cost最低的方案。以上这些不同层次的代价主要用来计算扫描操作(table scan，index scan，range scan，index lookup)，连接顺序选择和子查询策略选择等。MySQL 5.7版本开始已经对各个原子操作的代价做了两张系统表，允许数据库管理员根据自己的硬件人为配置各个原子操作的单位代价。在start_lex初始化时，这些单位代价用来初始化权重变量。
可以通过下面两张表查看：
mysql> select * from mysql.server_cost; ------------------------------ ------------ --------------------- --------- --------------- | cost_name | cost_value | last_update | comment | default_value | ------------------------------ ------------ --------------------- --------- --------------- | disk_temptable_create_cost | NULL | 2021-03-25 23:07:10 | NULL | 20 || disk_temptable_row_cost | NULL | 2021-03-25 23:07:10 | NULL | 0.5 || key_compare_cost | NULL | 2021-03-25 23:07:10 | NULL | 0.05 || memory_temptable_create_cost | NULL | 2021-03-25 23:07:10 | NULL | 1 || memory_temptable_row_cost | NULL | 2021-03-25 23:07:10 | NULL | 0.1 || row_evaluate_cost | NULL | 2021-03-25 23:07:10 | NULL | 0.1 | ------------------------------ ------------ --------------------- --------- --------------- mysql> select * from mysql.engine_cost; ------------- ------------- ------------------------ ------------ --------------------- --------- --------------- | engine_name | device_type | cost_name | cost_value | last_update | comment | default_value | ------------- ------------- ------------------------ ------------ --------------------- --------- --------------- | default | 0 | io_block_read_cost | NULL | 2021-03-25 23:07:10 | NULL | 1 || default | 0 | memory_block_read_cost | NULL | 2021-03-25 23:07:10 | NULL | 0.25 | ------------- ------------- ------------------------ ------------ --------------------- --------- --------------- 4.2 代价查看方式
由于MySQL在8.0对执行计划框架做了较大的修改，采用了volcano的执行框架，将执行计划用树结构组织，explain format=tree使得执行计划的查看较为方便。
在详细查看计划选择时的代价计算方面，MySQL也提供了trace的查看方案：
SET session OPTIMIZER_TRACE="enabled=on"之后通过查找
select * from information_schema.optimizer_trace可以显示optimizer工作的流程及代价计算明细。
「第五部分 查询执行」
在MySQL 5.7版本中，物理执行层没有算子的概念。逻辑散落在各个执行层代码中，这不利于计划的存储，复制及并行执行等高级功能。从8.0开始，MySQL引入了volcano的执行框架，对物理执行逻辑进行了物化。抽象成了扫描(scan)，过滤(filter)，排序(sort)，聚合(aggregate)，连接(join)这些基本算子，对优化和执行进行解耦。
更进一步地，8.0版本对表达式也做了一定程度的优化，在经典的volcano模型中，每个算子实现open-next-close模型，next函数传递中间结果数据，但MySQL延后了表达式计算。在每个"阻塞"(收集数据)的操作结束时，或者发送结果数据时才启动表达式计算。
5.1 查询执行框架
MySQL 8.0 volcano框架的引入，使得server层对优化和执行的工作更解耦合，查询的处理显得更直观。比如下面这条带有连接和聚合操作的SQL，引擎将它转换成含有5个物理算子组成的二叉树，这些物理算子又根据是否为"阻塞"算子，将整个执行计划切分成多个"阶段"。这是volcano架构的基本思想，MySQL也将遵循这个做法。
如图所示，SQL-4的执行计划经过逻辑计划转成物理执行计划之后，由"阻塞"算子切分成了三个"阶段"，这三个"阶段"分别以不同的颜色表示。
SQL-4: select t1.b, sum(t1.c) from t1 inner join t2 on t1.a = t2.a where t1.a = 100 group by t1.b
5.2 执行前移
MySQL在优化器阶段会将const table提前计算，const table包含几类：1. 只有一条记录或者含有0条记录的表; 2. 过滤条件是唯一键或者主键的表。const table将在优化阶段计算，但为了保持物理执行层生成执行计划的统一，const table在物理层会生成空的执行算子。
对于一些子查询来讲，也会存在提前计算。比如一些非相关子查询，MySQL采用"持久化"的方式将子查询的结果缓存，避免每条外层记录都引发对子查询做重复计算。这种情况下，子查询的计算也会前移到优化器阶段。
这类优化器阶段做执行层工作，对有些explain来讲是稍不友好的。
「第六部分 MySQL优化器增强」
SQL Outline
MySQL优化器偶尔有执行计划选错的问题。有时候是各种原子操作的权重没有正确地赋值，比如SQL中含有长度较长的字符串比较，compare的权重偏小了。有些是代价估算中算法不太精确，比如通过REF扫描的行数取的平均值在倾斜场景下可能会失真。这些问题都可能会导致MySQL选择自认为代价比较低的计划，但实际执行过程中，耗时却不受控制。
这类问题，我们无法通过调整索引数据解决，因为用户建的就是最合适的索引。而进行server层代价模型的变动又需要很长的上线周期，而且测试过程繁杂冗长。为解决这类问题，我们将会提供一种outline机制让用户在不修改线上SQL的情况下改变执行计划。让SQL执行计划按照客户的意愿去执行。
如图6-1所示，server在没有选择走i1索引的计划后，客户数据库管理员打开cdb_opt_outline_enabled开关，强制将use index(i1)绑定到表t1上。执行原始时，server将会采用客户指定的计划去执行，走i1索引。
「第七部分 小结」
以上简要介绍了TXSQL优化器的主要模块的一些算法，我们将在之后的文章中每次单独拿出一块优化器的详细实现过程，帮助读者了解TXSQL优化器的原理，和我们团队正在做的工作。
腾讯数据库技术团队对内支持QQ空间、微信红包、腾讯广告、腾讯音乐、腾讯新闻等公司自研业务，对外在腾讯云上依托于CBS CFS的底座，支持TencentDB相关产品，如TDSQL-C(原CynosDB)、TencentDB for MySQL(CDB)、CTSDB、MongoDB、CES等。腾讯数据库技术团队专注于持续优化数据库内核和架构能力，提升数据库性能和稳定性，为腾讯自研业务和腾讯云客户提供“省心、放心”的数据库服务。此公众号旨在和广大数据库技术爱好者一起推广和分享数据库领域专业知识，希望对大家有所帮助。
