MySQL优化器
MySQL架构图
讲到MySQL,就绕不开他的架构图。MySQL是一个经典的C/S架构。服务器这边分两层:第一层是Server层,第二层是存储引擎。Server层处理主要的业务操作流程,但不关心具体的存储逻辑。存储逻辑由存储引擎层去实现,常见的存储引擎有InnoDB(默认的)、MyISAM、Memory等。
Server层的连接器负责管理Client的连接、权限检证。客户端的查询请求过来的时,会将查询的SQL语句作为key,去看一下查询缓存里有没有,如果有的话,就直接返回了。如果没有的话,再走正常查询路径。查询缓存用处不是很大,因为如果对表有任何的更新操作,对这个表的所有缓存都有失效,所以这个模块在MySQL8.0之后就直接删掉了。
分析器主要是对SQL语句做一些词法分析、语法分析。判断SQL语句是否合法。
优化器是通过一些计算,生成最佳的执行计划,后面会再细讲。
执行器根据上一步生成的执行计划,调用引擎的API,得出结果,然后返回。
优化器
优化器主要分为两个阶段,首先是逻辑查询优化,这个阶段主要是使用关系代数对SQL语句做一些等价变换,对条件表达式进行等价谓词重写、条件简化,对视图进行重写,对子查询进行优化,对连接语义进行了外连接消除、嵌套连接消除等。
其次是物理查询优化。物理查询优化一般分为两种:
基于规则的优化(RBO,Rule-Based Optimizer)
这种方式主要是基于一些预置的规则对查询进行优化。
基于代价的优化(CBO,Cost-Based Optimizer)
这种方式会根据模型计算出各个可能的执行计划的代价,然后选择代价最少的那个。它会利用数据库里面的统计信息来做判断,因此是动态的。
MySQL查询优化器
一、查询语句的执行过程简介
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子查询进行优化。