[玩转 MySQL 之六]MySQL 查询优化器

注:由于查询优化器涉及面很广也比较复杂，作者也没有完全领会，本文主要来自书籍 << 数据库查询优化的艺术: 原理解析和 SQL 性能优化 >>，如果涉及到版权，请告知作者，删除本文。

一、查询语句的执行过程简介

MySQL 查询语句在数据库中的执行分为 5 个阶段，具体如下:

1.1 SQL 输入

数据库接收用户输入的 SQL 语句，准备执行。

1.2 语法分析

对输入的 SQL 语句进行词法分析、语法分析，得到语法分析树。在这个阶段，输入的是一条 SQL 语句，输出的是一棵多叉树。

1.3 语义检查

根据语法树和系统的元信息进行语义检查，本阶段是对语法分析树进行逻辑判断，树的结构不发生变化。对语法分析树上的各个节点进行语义分析，判断对象是否存在、是否重名等，对不合语义的地方报告错误。

1.4 SQL 优化

SQL 优化通常包括两项工作:一是逻辑优化、二是物理优化。这两项工作都要对语法分析树的形态进行修改，把语法分析树变为查询树。其中，逻辑查询优化将生成逻辑查询执行计划。在生成逻辑查询执行计划过程中，根据关系代数的原理，把语法分析树变为关系代数语法树的样式，原先 SQL 语义中的一些谓词变化为逻辑代数的操作符等样式，这些样式是一个临时的中间状态，经过进一步的逻辑查询优化，如执行常量传递、选择下推等(如一些节点下移，一些节点上移)，从而生成逻辑查询执行计划。在生成逻辑查询计划后，查询优化器会进一步对查询树进行物理查询优化。物理优化会对逻辑查询进行改造，改造的内容主要是对连接的顺序进行调整。SQL 语句确定的连接顺序经过多表连接算法的处理，可能导致表之间的连接顺序发生变化，所以树的形态有可能调整。物理查询优化除了进行表的连接顺序调整外，还会使用代价估算模型对单个表的扫描方式、两表连接的连接算法进行评估，选择每一项操作中代价最小的操作为下一步优化的基础。物理查询优化的最终结果是生成最终物理查询执行计划。

1.5 SQL 执行

在 SQL 执行阶段，依据物理查询计划执行查询，逐步调用相关算法进行执行。算法包括一趟算法、嵌套循环连接、基于排序的两趟算法、基于散列的两趟算法、基于索引的算法、使用超过两趟的算法等。

二、逻辑查询优化

2.1 逻辑查询优化思路

查询优化器在逻辑优化阶段主要解决的问题是: 如何找出 SQL 语句等价的变换形式，使得 SQL 执行更高效。一条 SQL 查询语句结构复杂，包含多种类型的字句，优化操作依赖于表的一些属性(如索引和约束等)。可用于优化的思路包括:

字句局部优化: 每种类型字句都可能存在优化方式，如等价谓词重写、where 和 having 条件化简中的大部分情况，都属于这种字句范围内的优化。
字句间关联优化: 字句与字句之间关联的语义存在优化的可能，如外连接消除、连接消除、子查询优化、视图重写等都属于字句间的关联优化，因为他们的优化都需要借助其他字句、表定义或列属性等信息进行。
局部与整体的优化: 需要协同考虑局部表达式和整体的关系，如 OR 重写并集规则需要考虑 UNION 操作(UNION 师变换后的整体的形式)的花费和 OR 操作(OR 是局部表达式)的花费。
形式变化优化: 多个字句存在嵌套，可以通过形式的变化完成优化，如嵌套连接消除。
语义优化:根据完整性约束、SQL 表达的含义等信息对语句进行语义优化。

2.2 查询重写规则

传统的联机事务处理(OLTP)使用基于选择(SELECT)、投影(PROJECT)、连接(JOIN)3 种基本操作相结合的查询，这种查询称为 SPJ 查询。数据库在查询优化的过程中，会对这 3 种基本操作进行优化。优化的方式如下:

选择操作: 对应的是限制条件(格式类似 field consant，field 表示列对象，op 是操作符，如=，> 等)，优化方式是选择操作下推，目的是尽量减少连接操作前的远组数，使得中间临时关系尽量少(元组数少，连接得到的远组数就少)，这样可减少 IO 和 CPU 的消耗，节约内存空间。
投影操作: 对应的 SELECT 查询的目的列对象，优化方式是投影操作下推，目的是尽量减少连接操作前的列数，使得中间临时关系尽量小(特别注意差别:选择操作是使元组的个数"尽量少"，投影操作是使一条元组"尽量小")，这样虽然不能减少 IO(多数数据库存储方式是行存储，元组是读取的最基本单位，所以要想操作列则必须读取一行数据)，但可以减少连接后中间关系的元组大小，节约内存空间)。
连接关系: 对应的是连接条件(格式类似 field_1, field_2，field_1 和 field_2 表示不同表上的列对象，op 是操作符，如=，> 等)，表示两个表连接的条件。这里涉及以下两个子问题:
- 多表连接中每个表被连接的顺序决定着效率。如果一个查询语句只有一个表，则这样的语句很简单；但如果有多个表，则会涉及表之间以什么样的顺序连接效率最高效(如 A、B、C 三表连接，如果 ABC、ACB、BCA 等连接后的结果集一样，则计算哪种连接次序的效率最高，是需要考虑的问题)。
- 多表连接每个表被连接的顺序由用户语义决定。查询语句多表连接有着不同的语义(如笛卡尔积、内连接、还是外连接中的左外连接等)，这决定着表之间的额前后连接次序是不能随意更换的，否则结果集中数据是不同的。因此，表的前后连接次序是不能随意交换的。
根据 SQL 语句的形式特点，可以针对 SPJ 的查询优化，如基于选择、投影、连接 3 种基本操作相结合的查询。

2.3 启发式规则再逻辑优化阶段的应用

逻辑优化阶段使用的启发式规则通常包括如下两类:

2.3.1 一定能带来优化效果的，主要包括:

优先做选择和投影(选择条件在查询树上下推)
子查询的消除
嵌套连接的消除
外连接的消除
连接的消除
使用等价谓词重写，对条件化简
语义优化
剪掉冗余操作(一些剪枝优化技术)、最小化查询块。

2.3.2 变换未必会带来性能的提高，需根据代价选择，主要包括:

分组的合并
借用索引优化分组、排序、DISTINCT 等操作
对视图的查询变为基于表的查询
连接条件的下推
分组的下推
连接提取公共表达式
谓词的上拉
用连接取代集合操作
用 UNIONALL 取代 OR 操作

三、物理优化

查询优化器在物理优化阶段，主要解决的问题如下:

从可选的单表扫描方式中，挑选什么样的单表扫描方式是最优的？
对于两个表连接时，如何选择是最优的？
对多个表连接，连接顺序有多种组合，是否要对每种组合都探索？如果不全部探索，怎么找到最优的一种组合？

在查询优化器实现的早期，使用的是逻辑优化技术，即使用关系代数规则和启发式规则对查询进行优化后，认为生成的执行计划就是最优的。在引入了基于代价的查询优化方式后，对查询执行计划做了定量的分析，对每一个可能的执行方式进行评估，挑出代价最小的作为最优的计划。目前数据库的查询优化器通常融合这两种方式。

3.1 查询代价估算

查询代价估算的重点是代价估算模型，这是物理查询优化的依据。除了代价模型外，选择率对代价求解也起着重要作用。

3.2 单表扫描算法

单表扫描需要从表上获取元组，直接关联到物理 IO 的读取，所以不同的单表扫描方式，有不同的代价。

3.3 索引

索引是建立在表上的，本质上是通过索引直接定位表的物理元组，加快数据获取的方式，所以索引优化的手段应该归属到物理查询优化阶段。

3.4 两表连接算法

关系代数的一项重要操作是连接运算，多个表连接是建立在两表之间连接的基础上的。研究两表连接的方式，对连接效率的提高有着直接的影响。

3.5 多表连接算法

多表连接算法实现的是在查询路径生成的过程中，根据代价估算，从各种可能的候选路径中找出最优的路径(最优路径是代价最小的路径)。多表连接算法需要解决两个问题:

多表连接的顺序: 表的不同连接顺序，会产生许多不同的连接路径；不同的连接路径有不同的效率。
多表连接的搜索空间:因为多表连接的顺序不同，产生的连接组合会有多种，如果这个组合的数据巨大，连接次数会达到一个很高的数量级，最大可能的连接次数是 N！(N 的阶乘)。比如 N=5，连接次数是 120；N=10，连接次数是 362880。所有的连接可能构成一个巨大的"搜索空间"。如何将搜索空间限制在一个可接受的时间范围内，并高效地生成查询执行计划将成为一个难点。

四、查询优化器与其他模块的关系

在数据库内部，根据功能不同，可以划分出多个模块，不同模块之间有的关系紧密，有的关系松散。查询优化器是其中的一个功能模块，是实现查询优化技术的模块。下面介绍数据库中与查询优化器相关的模块:

4.1 查询优化器与语法分析器

语法分析器是查询优化器的输入。理解查询优化器，从语法分析器开始，将是个好的开端。因为不同对象有着不同的数据结构，数据结构成员是对象属性的载体，而语法分析器把一个 SQL 分解为众多数据结构体并给数据结构赋值，这样才能被查询优化器逐项获取并用与计算，比如逻辑查询优化有一条"常量传递"规则，如果没有语法分析器分解条件，也不可能推知列值是常量，也不可能有此优化。

4.2 优化器与执行器

查询优化器是执行器的前端输入部分。查询优化器计划一条 SQL 的具体执行方式和步骤，执行器具体去完成计划中的每一步。在实践中，一条 SQL 最耗时的阶段多发生在执行阶段。如果查询计划做得不好，则执行起来非常耗时。

4.3 优化器与缓冲区

缓冲区有多种多样，比如与数据相关的缓冲区(如从存储设备加载数据到内存)、与实现过程相关的辅助缓冲区(如排序用到的临时表或内存块)，与功能模块相关的缓冲区(如日志缓冲区)等。优化器主要是对 SQL 输入进行逻辑方式的变换，没有涉及数据部分，只涉及对数据量的估计。当估算排序空间的时候，会涉及排序缓冲区；当估算数据 IO 的时候，需要考虑数据是否在数据缓存中。所以，查询优化器与数据缓冲区有一定的关系。

4.4 优化器与统计

MySQL 数据库的查询优化器使用了基于代价的查询执行计划估算，所以依赖于被查对象的各种数据，而数据是动态变化的，如表的元组数。如果实时获取这些数据，系统计算的开销会比较大。为了避免这样的问题，定期或者根据需要统计这些数据，则比较切合实际。优化器在物理优化阶段，需要对单表读取开销，两表连接开销，多表连接顺序开销等进行比较，比较基于的就是一些基础数据的值，这些数据通常不会被实时更新，所以优化器有时做出的计划未必是最合适的。

4.5 优化器与索引

优化器做物理查询优化需要利用索引提高单表扫描效率，进而减少了多表连接时的元组数，所以确定哪些索引可用、怎么有效利用索引等都在查询优化器中得到体现。

五、 MySQL 查询优化器概述

MySQL 查询优化器的主要功能是完成 SELECT 语句的执行，在保证 SELECT 语句正确执行之外，还有一个重要的功能，就是使用关系代数、启发式规则、代价估值模型等不同种类的技术，提高 SELECT 语句的执行效率。

MySQL 查询优化器实现第 2 章介绍的大多数查询优化技术，这些技术，用于对 SPJ 和非 SPJ 类型的查询语句进行优化。

下面将从整体上介绍 MySQL 查询优化器，分别对 MySQL 查询优化器的执行过程、架构、层次、设计思想、主要概念、代码结构上宏观探讨 MySQL 查询优化器的实现。

5.1 MySQL 查询执行过程

MySQL 查询执行过程分为 4 个阶段，如下所示:

语法分析阶段: 将 SQL 查询语句经词法和语法分析后变换成为一棵查询树 st_select_lex 传给优化器，并对 SQL 表达的语义进行检查。
生成逻辑查询执行计划阶段: 优化器在查询树中遍历每个关系，确定关系是否是常量表、为每个关系查找可用的索引、运用关系代数原理和启发式规则进行逻辑上的查询优化(如消除子查询、消除外连接等)。
生成物理查询执行计划阶段: 优化器对各个连接的表进行排序，然后求解多表连接最优路径，对于每个关系尽量利用索引计算其代价，找出代价最小的路径后保存到 JOIN 类的 bets_positions
执行查询执行计划阶段: 把查询执行计划传到执行器进行执行。

MySQL 查询优化器在逻辑查询执行计划阶段，机遇关系代数规则和启发式规则，把用户指定的 SQL 经过"等价"的代数转换，变为一种更节省 IO 的执行序列，执行起来更为高效。

MySQL 查询优化器在物理查询执行计划阶段，在解决多表连接的问题时，有两套算法:一是用户指定表连接次序的算法；二是混杂了贪婪和穷举思想的算法，解决的是较多表的连接和非用户指定连接次序的多表连接，但不能保证得到最优的查询执行计划。

5.2 MySQL 查询优化器的架构和设计思想

MySQL 查询优化器设计精巧，但层次不够清晰，V5.6 之后的版本，混乱状态有所改善，但 MySQL 查询优化器实用而高效，在充分利用索引的基础上，实现了很多查询优化技术，有很多精巧之处值得学习探索。

MySQL 查询优化过程中，查询优化器通过 JOIN 对象的方法，如 JOIN.prepare()、JOIN.optimize()，完成优化工作。JOIN.prepare()完成的查询优化主要包括：子查询的冗余子句消除、IN 类型子查询优化、将 ALL/ANY 等类型的子查询转换为 MIN/MAX 等操作，这是对简单子查询进行的优化；JOIN.optimize()函数完成的查询优化主要包括：子查询上拉，把外连接优 > 化为内连接，把嵌套连接消除，WHRER 子句、JOIN/ON 子句、HAVING 子句条件表达式的化简（尤其是对含有常量的表达式的化简、等式合并），优化没有 GROUPBY 子句情况下的 COUNT(*)、MIN()、MAX()，裁剪分区 partition（如果查询的表是分区表），确定多表的连接路径（单表是多表的特例，统计 join 的代价，两种多表连接算法选其一搜索最优的 join 顺序、生成执行计划）、优化等式谓词、优化 DISTINCT、创建临时表存储临时结果优化分组排序等操作。在这样的过程中，MySQL 没有把优化过程明显地分为逻辑查询优化阶段和物理查询优化阶段，而是互为混杂，在物理查询优化之后，继续进行了部分逻辑查询优化。这是 MySQL 查询优化器的一大特点。

5.3 MySQL 查询优化器架构

MySQL 查询优化器为 SQL 查询语句求解最优的执行方式。MySQL 查询优化器架构和执行过程如下图所示。

MSQL 查询语句的执行主要历经 4 个过程，分别如下:

P1 过程：SQL 语句输入变为语法查询树。
P2 过程：查询预处理，优化相关的内容主要是子查询优化。
P3 过程：语法树变为逻辑关系查询树，进而变为物理查询执行计划，挑出最优计划。
P4 过程：依据最优查询执行计划得到查询结果。

MySQL 查询语句的执行，主要历经以下 4 个模块。

M1 模块：语法分析模块，执行过程 P1 的任务。
M2 模块：查询预处理模块，执行过程 P2 的任务。
M3 模块：查询优化模块，执行过程 P3 的任务。
M4 模块：查询执行模块，执行过程 P4 的任务。

实现 MySQL 查询优化器功能的主要是 M3 模块，其主要有以下两个子阶段的工作。

M3-S1 逻辑查询优化阶段：把语法查询树通过关系代数原理，优化为关系代数查询树，关系代数的原理在这个阶段运用；
M3-S2 物理查询优化阶段：把关系代数查询树用于贪婪算法，生成最优执行计划。

5.4 MySQL 查询优化器的层次

MySQL 整个查询优化器从代码层面看，逻辑结构不是很清晰，但是从技术层面看，还是能够分为两个阶段，一是逻辑查询优化阶段，二是物理查询优化阶段。

逻辑查询优化阶段主要依据关系代数可以推知的规则和启发式规则，对 SQL 语句进行等价变换。MySQL 淋漓尽致地使用了关系代数中可推定的各项规则，对投影、选择等操作进行句式的优化；对条件表达式进行了谓词的优化、条件化简；对连接语义进行了外连接、嵌套连接的优化；对集合、GROUPBY 等尽量利用索引、排序算法进行优化。另外还利用子查询优化、视图重写、语义优化等技术对查询语句进行了优化。
在物理查询优化阶段，通过贪婪算法，并依据代价估算模型，在求解多表连接顺序的过程中，对多个连接的表进行排序并探索连接方式，找出花费最小的路径，据此生成查询执行计划。在这个阶段，对于单表扫描和两表连接的操作，高效地使用了索引，提高了查询语句的执行速度。

六、从功能角度看 MySQL 查询优化

MySQL 的查询优化技术的实现，基本也可以分为逻辑优化和物理优化两个阶段，只是和 PostgreSQL 相比，界线没有那么清晰。MySQL 的查询优化过程概述如下:

优先处理集合操作，把集合操作分解为普通的 SPJ 和非 SPJ 操作。
应用子查询优化技术，去除子查询中冗余部分，转换为半连接、用物化操作优化子查询、执行 In 向 EXISTS 转换、优化 ALL/ANY 等类型的子查询向 MIN/MAX 转换等。
消除外连接、消除嵌套连接。
利用等价谓词重写优化技术，优化 WHERE、JOIN/ON、 HAVING 等条件中的表达式，尤其是常量表达式和多重等式。
利用索引优化 count(*)，MIN()，MAX()。
进行多表连接的顺序确定。
- 找出常量表，求解多表连接的过程中不使用常量表作为连接的表(减少搜索空间)。
- 尽量利用索引优化 GROUP BY、DISTINCT 结合的操作
- 利用代价估算模型，评估连接的花费，找出最优连接。
- 用物化优化半连接嵌套的形式。
- 从两种多表连接的算法中任选其一: 一是用户指定连接顺序，二是使用贪婪和穷尽结合的方式。
- "选择"、"投影"操作下推
- 利用索引对 ORDER BY 进行优化
- 对 GROUP BY/DISTINCT 的组合情况进行优化
- 确定半连接优化策略，从 5 种备选策略选择其中之一。
- 对没有 GROUP BY 和 ORDER BY 字句的 IN 子查询进行优化。

七、参考文献

书籍: << 数据库查询优化的艺术: 原理解析和 SQL 性能优化 >>