注：查询优化器涉及面广且复杂，作者也不完全了解。 本文主要来自图书数据库查询优化的艺术：原理分析和SQL性能优化。 如果涉及版权，请通知作者并删除正文。
另一方面，查询语句执行过程的概要MySQL查询语句在数据库中的执行分为五个阶段，具体为以下：
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 )使用了将三个基本操作(选择、投影、连接)相结合的查询，这种查询被称为SPJ查询。
数据库在查询优化过程中优化这三个基本操作。 优化方法如下：
选择操作：对应于约束条件(field consant形式，field对应于列对象，op对应于运算符(例如=，等) )，优化方式是下推选择操作，以最小化连接操作前的远程组数，并因此，与能够减少IO和CPU消耗的投影操作：对应的选择查询的目标列对象被投影操作压下，以使连接操作前的列数最小化，并使中间的临时关系最小化。 (特别注意，差异：选择操作将元组的数量减少到“最小”，投影操作将元组减少到“最小”(虽然这不能减少IO ) )大多数数据库存储方案是行存储，元组是读取的最基本单元格式类似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.2 单表扫描算法单表扫描需要从表上获取元组，直接关联到物理IO的读取，所以不同的单表扫描方式，有不同的代价。
3.3 索引索引是 建立在表上的，本质上是通过索引直接定位表的物理元组，加快数据获取的方式，所以索引优化的手段应该归属到物理查询优化阶段。
3.4 两表连接算法关系代数的一项重要操作是连接运算，多个表连接是建立在两表之间连接的基础上的。研究两表连接的方式，对连接效率的提高有着直接的影响。
3.5 多表连接算法多表连接算法实现的是在查询路径生成的过程中，根据代价估算，从各种可能的候选路径中找出最优的路径(最优路径是代价最小的路径)。
多表连接算法需要解决两个问题:
在数据库内部，根据功能不同，可以划分出多个模块，不同模块之间有的关系紧密，有的关系松散。查询优化器是其中的一个功能模块，是实现查询优化技术的模块。下面介绍数据库中与查询优化器相关的模块:
4.1 查询优化器与语法分析器语法分析器是查询优化器的输入。理解查询优化器，从语法分析器开始，将是个好的开端。因为不同对象有着不同的数据结构，数据结构成员是对象属性的载体，而语法分析器把一个SQL分解为众多数据结构体并给数据结构赋值，这样才能被查询优化器逐项获取并用与计算，比如逻辑查询优化有一条"常量传递"规则，如果没有语法分析器分解条件，也不可能推知列值是常量，也不可能有此优化。
4.2 优化器与执行器查询优化器是执行器的前端输入部分。查询优化器计划一条SQL的具体执行方式和步骤 ，执行器具体去完成计划中的每一步。
在实践中，一条SQL最耗时的阶段多发生在执行阶段。如果查询计划做得不好，则执行起来非常耗时。
缓冲区有多种多样，比如与数据相关的缓冲区(如从存储设备加载数据到内存)、与实现过程相关的辅助缓冲区(如排序用到的临时表或内存块)，与功能模块相关的缓冲区(如日志缓冲区)等。
优化器主要是对SQL输入进行逻辑方式的变换，没有涉及数据部分，只涉及对数据量的估计。当估算排序空间的时候，会涉及排序缓冲区；当估算数据IO的时候，需要考虑数据是否在数据缓存中。所以，查询优化器与数据缓冲区有一定的关系。
MySQL数据库的查询优化器使用了基于代价的查询执行计划估算，所以依赖于被查对象的各种数据，而数据是动态变化的，如表的元组数。如果实时获取这些数据，系统计算的开销会比较大。为了避免这样的问题，定期或者根据需要统计这些数据，则比较切合实际。
优化器在物理优化阶段，需要对单表读取开销，两表连接开销，多表连接顺序开销等进行比较，比较基于的就是一些基础数据的值，这些数据通常不会被实时更新，所以优化器有时做出的计划未必是最合适的。
优化器做物理查询优化需要利用索引提高单表扫描效率，进而减少了多表连接时的元组数，所以确定哪些索引可用、怎么有效利用索引等都在查询优化器中得到体现。
五、 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性能优化>>