主要解决的问题

如何找出SQL语句等价的变换形式,使得SQL执行更高效。

#可优化的思路

(1)子句局部优化。
如等价谓词重写,WHERE和HAVING条件化简中的大部分情况。

(2)子句间关联优化。
子句与子句之间关联的语义存在优化的可能,如外连接消除、连接消除、子查询优化、视图重写等。

(3)局部与整体的优化。
协同局部与整体。如OR重写并集规则需要考虑UNION操作(UNION是变换后的整体形式)的花费和OR操作(OR是局部表达式)的花费。

(4)形式变化优化
多个子句存在嵌套,可能通过形式的变化完成优化。如:嵌套连接消除。

(5)语义优化
根据完整性约束,SQL表达的含义等信息对语句进行语义优化

(6)其他优化
根据一些规则对非SPJ做的其他优化,根据硬件环境进行的并行查询优化。

它们都是依据关系代数和启发式规则进行。

#关系模型

关系数据结构

即二维结构,二维表。即数据库中的表。
关系是一种对象
关系即是表
关系的元数据,即表结构,通常称为列或属性。
关系的数据,即表的行数据,通常称为元组(tuple),也称为记录(record)。        

关系操作集合

并,交,差,积,选择,投影,连接,除。。
选择:单个关系中筛选元组。
投影:单个关系中筛选列。
连接:多个关系中根据列间的逻辑运算筛选元组(自然连接,等值连接)
除:多个关系中根据条件筛选元组(NOT EXISTS 的子查询实现除)
并:多个关系合并元组(用UNION实现并)
交:多个关系中根据条件筛选元组(用两次NOT IN 实现交)
差:多个关系中根据条件筛选元组(NOT IN 子查询实现差)
积:无连接条件。N*M条元组

关系类型

R <op> S

自然连接:R和S中“公共属性”,结果包括公共属性名字上相等的所有元组的组合,在结果中把重复的列去掉。(是同时从列和行的角度进行去重)

@-连接:R和S中没有公共属性,结果包括在R和S中满足操作符@的所有组合。@通常包括:< <=, =, =, >=。即从关系R和S的广义笛卡儿积中选取A,B属性相等的那些元组,是从“行”的角度进行运算。

等值连接:操作符是 = 的@-连接。

半连接:结果包括在S中公共属性名字上相等的元组的所有的R中的元组。即结果包括R的部分元组,而R中的部分元组的公共属性的值在S中同样存在。SQL中没有自己的连接操作符,使用EXISTS, IN 关键字做子句的子查询常被查询优化器转换为半连接。

反连接:结果是在S中没有在公共属性名字上相等的元组的R的元组。即为半连接的补集,反连接有时称为反半连接。在SQL中没有自己的连接操作符,使用了 NOT EXISTS 则被查询优化器转换为反半连接。

外连接(左外连接):结果包括R中的所有元组。若在S中有在公共属性名字上相等的元组,则正常连接;若在S中没有公共属性名字上相等的元组,则依旧保留此元组,并将对应的其他列设为NULL

外连接(右外连接):结果包括S中的所有元组。若在R中有在公共属性名字上相等的元组,则正常连接;若在R中没有公共属性名字上相等的元组,则依旧保留此元组,并将对应的其他列设为NULL

外连接(全外连接):结果包括S和R中的所有元组。对于每个元组,若在另一个关系中有在公共属性名字上相等的元组,则正常连接;若在另一人关系中没有公共属性名字上相等的元组,则依旧保留此元组,并将对应的其他列设为NULL

关系完整性约束

查询句与二叉树

叶子是关系(表)

内部结点是运算符(或称算子,操作符,如 LEFT OUT JOIN,表示左右子树的运算方式)

子树是子表达式或SQL片段

根结点是最后运算符的操作符

根结点运算后,得到的是SQL查询优化后的结果

这样一棵树就是一个查询的路径

多个关系连接,连接顺序不同,可以得出多个类似的二叉树

查询优化就是找出代价最小的二叉树,即最优的查询路径。

基于代价估算的查询优化就是通过计算和比较,找出花费最少的是优二叉树。

从运算符的角度考虑优化

不同的运算符优化可c减少中间生成物的大小和数量,节约IO和内存CPU等,从而提高执行速度。前提是优化前和优化后是等价的。

选择 —— 基本选择性质

对同一个表的同样选择条件,作一次即可。
可优化的原因:
幂等性:多次应用同一个选择有同样的效果
交换性:应用选择的次序在最终结果中没有影响
选择可有效减少在它的操作数中的元组数的运算(元组数减少)

选择 —— 分解有复杂条件的选择

合取:合并多个选择为更少的需求值的选择,多个等式可以合并。它等价于针对这些单独的一系列选择。
析取:分解它们使得其成员选择可被移动或单独优化。它等价于选择的并集。

选择 —— 和叉积

尽可能选做选择:关系有N和M行,先做积运算将包含N*M行。先做选择运算,减少N和M,则可避免不满足条件的条件参与积的运算,节约时间减少结果的大小。

尽可能下推选择:如果积不跟随着选择运算,可尝试使用其他规则从表达式树更高层下推选择。

选择 —— 和集合运算

选择下推到的集合运算中:选择在差集,交集和并集算子上满足分配律。

选择 —— 和投影

在投影之前进行选择:如果选择条件中引用的字段是投影中的字段的子集,则选择与投影满足交换性。

投影 —— 和基本投影性质

尽可能先做投影:投影是幂等性的;投影可以减少元组大小。

投影 —— 和集合运算。

投影下推到集合运算中:投影在差集,交集和并集运算上满足分配律。

运算规则主导的优化

连接、笛卡儿积 交换律

做连接、做积运算,可交换前后位置,其结果不变。如两表连接算法中嵌套连接算法,对外表和内表有要求,外表尽可能小则有利于做“基于块的嵌套循环连接“,所以,通过交换律可以把元组少的表作为外表。

连接、笛卡儿积 结合律

做连接、做积运算,如果新的结合有利于减少中间关系的大小,则可优先处理。

投影的串接定律

在同一个关系上,只需要做一次投影运算,且一次投影时选择多列同时完成。所以许多数据库优化引擎为同一个关系收集齐本关系上的所有列(目标列和 WHERE, GROUP BY 等子句的本关系的列)

选择的串接定律

选择条件可以合并,使得可一次就检查全部条件,不必多次过滤元组,所以可以把同层的合取条件收集在一起,统一判断。

选择与投影的交换律

(1)先投影后选择,可以改为先选择后投影,这对于以行为存储格式的主流数据库而言,很有优化意义。存储方式总是在先获得元组后才能解析得到其中的列。

(2)先择选后投影,可以改为带有选择条件中列的投影后再选择,最后完成最外层的投影,这样,使得内层的选择和投影可以同时进行。

选择与笛卡儿积的分配律

条件下推到相关的关系上,先做选择后做积运算,这样可以减小中间结果的大小。

选择与并的分配律

条件下推到相关的关系上,先做选择后做并运算,可以减小每个关系输出结果的大小。

选择与差的分配律

条件下推到相关的关系上,先做选择后做差运算,可以减小每个关系输出结果的大小。

投影与笛卡儿积的分配律

先做投影后做积,可减少做积前每个元组的长度,使得再做积后得到新元组的长度变短。

投影与并的分配律

先做投影后做并,可减少做并前每个元组的长度。

OLTP

On-line Transaction Processing, OLTP。

SPJ

SELECT, 投影(PROJECT), 连接(JOIN)

查询优化对SPJ的优化方式如下:

1)选择操作。对应的是限制条件(格式类似 field<op>consant)优化方式是选择操作下推,目的是尽量减少连接操作前的元组数,使得中间临时关系尽量少。这可减少IO和CPU等的消耗。

2)投影操作:对应SELECT查询的目的的列对象。优化方式是投影操作下推。目的是尽量减少连接操作前的列数,使得中间临时关系尽量小(选择操作是使元组个数”尽量少“,投影操作,是使一条元组”尽量小“)。这样,虽然不能减少IO(多数数据库存储方式是行存储,元组是读取的最基本单位,所以想要操作列必须读取一行数据)。但可以减少连接后的中间关系的元组大小,节约内存。

3)连接操作:对应的是连接条件。(格式为field1<op>field2, field1和field表示”不同表“上的列对象。表示两个表连接条件。(1)”多表连接中每个表被连接的顺序决定着效率。“,即如果ABC三个表,ABC, ACB, CBA, BCA等不同的连接后结果一样的话,则要计算哪种效率最高。(2)多表连接每个表被连接的顺序由用户语义决定,这决定着表之间的前后连接次序是不能随意更换的。

4)非SPJ(在SPJ的基础上存在 GROUP BY 操作的查询,这是一种复杂的查询)。

子查询优化

它是一种比较耗时的操作,优化子查询对查询效率的提升有着直接的影响。

子查询可出现的位置及对优化的影响

1)目标列
这时,只能是标量子查询,否则数据库可能返回类似”错误:子查询必须只能返回一个字段“的提示。

2)FROM子句
相关子查询不能出现在FROM子句中;非相关子查询出现在FROM子句中,可上拉子查询到父层,在多表连接时统一考虑连接代价后择优。

3)WHERE子句

4)JOIN/ON子句
它们处理方式同FROM子句和WHERE子句

5)GROUP BY子句
目标列必须和 GROUP BY 关联。可将子查询写在GROUP BY位置,但没有什么实用意义。

6)HAVING子句

7)ORDER BY 子句

子查询优化技术

1)子查询合并
等价的情况下。多个子查询能够合并成一个子查询。这样可以把多次表扫描,多次连接减少为单次表扫描和单次连接。如:

select * from t1 where a1 < 10 and (exists (select a2 from t2 where t2.a2 < 5 and t2.b2 = 1) or exists (select a2 from t2 where t2.a2 < 5 and t2.b2 = 2)

可优化为

select * from t1 where a1 < 10 and ( exists (select a2 from t2 where t2.a2 < 5 and ( t2.b2 = 1 or t2.b2 = 2));

2)子查询展开
又称子查询反嵌套,又称为子查询上拉。把一些子查询置于外层的父查询中,作为连接关系与外层父查询并列。实质上是把某些子查询重写为等价的多表连接操作。如:

select * from t1, ( select * from t2 where t2.a2 > 10) v_t2 where t1.a1 < 10 and v_t2.a2 < 20

可优化为

select * from t1, t2 where t1.a1 < 10 and t2.a2 < 20 and t2.a2 > 10

3)聚集子查询消除
将聚集函数上推,将子查询转变为一个新的不包含聚集函数的子查询,并与父查询的部分或者全部表做左外连接。

4)其他
利用窗口函数消除子查询的技术。子查询推进等技术

子查询展开

1)如果子查询出现了聚集、GROUP BY, DISTINCT 子句,则子查询只能单独求解,不可以上拉到上层。

2)如果子查询只是一个简单格式(SPJ)的查询语句,则可以上拉到上层,这样往往能提高查询效率。

子查询展开的规则

1)如果上层查询的结果没有重复(即SELECT子句中包含主键),则可以展开其子查询,并且展开后的查询的SELECT 子句前就回上 DISTINCT 标志。

2)如果上层有 DISTINCT 标志,则可以直接展开子查询

3)如果内层查询结果没有重复元组,则可以展开。

子查询展开的步骤

1)将子查询和上层查询的FROM子句连接,为同一个FROM子句,并修改相应的运行参数

2)将子查询的谓词符号进行相应修改。如 IN修改为=ANY

3)将子查询的WHERE条件作为一个整体与上层查询的WHERE条件合并,并用AND条件连接词连接。

子查询优化说明

子查询类似: 10 IN (select ...)这不能做上拉操作,所以不能优化
子查询类似:出现 random()等易失函数,子查询结果不能确定,所以查询优化器就不能对子查询优化。

ALL/SOME/ANY类型

如果子查询没有 GROUP BY 子句,也没有聚集函数。则可以使用如下表达式做等价转换:

val > ALL (select ...) 等价为 val > MAX(select ...)

val < ALL (select ...) 等价为 val < min( select ...)

val > any (select ...) 等价为 val > min(select ....)

val < any (select ...) 等价为 val<max(select ....)

val >= ALL 同上
val <= ALL
val >= ANY
val <= ANY

视图重写

就是将视图的引用重写为对基本表的引用。如:
create table t_a ( a int , b int );
create view v_a as select * from t_a;

基于视图的命令:
select col_a from v_a where col_b > 100;
经过视图重写后:
select col_a from ( select col_a , col_b from t_a) where col_b > 100;
再经过优化后,则是:
select col_a from t_a where col_b > 100;

简单的视图(SPJ)可以被查询优化器较好地处理。
但复杂视图则不能被查询优化器很好地处理。

等价谓词重写

1)LIKE规则
如:name like 'abc%'
重写为
name >= 'abc' and name < 'abd';
应用like规则的好处:转换前针对 like 谓词只能进行全表扫描。如果name列上存在索引,则转换后可以进行索引范围扫描。

如果没有通配符(%或_)。则是与 = 等价
name like 'abc'
重写为
name = 'abc'

2) BETWEEN-AND规则
sno BETWEEN 10 AND 20 
重写为
sno >= 10 and sno <=20
好处:如果sno建立了索引,则可以用索引扫描代替原来的BETWEEN-AND谓词限定的全表扫描,从而提高了查询的效率。

3)IN转换OR规则
IN只是IN操作符,而不是IN子查询。改为OR可以更好地利用索引进行优化。将IN改为若干个OR可能会提高效率。
age IN (8, 12, 21)
重写为
age = 8 or age = 12 or age = 21
效率是否提高,需要看数据库对IN谓词是否只支持全表扫描。如果数据库对IN谓词只支持全表扫描且OR谓词中表的age列存在索引,则转换后的查询效率会更好。

4)IN转换ANY规则
因为IN可以转换为OR,而OR可转换为ANY,所以可以直接把IN转换为ANY。这可能会提高效率。
age IN (8, 12, 21)
重写为
age any (8, 12, 21)
效率是否提高,依赖于数据库对ANY操作的支持情况。
如:PostgreSQL没有显式支持 ANY 操作,但在内部实现时把IN操作转换为了ANY操作。(通过 explain 知道)


5)OR转换为ANY规则
这样可以更好地利用 MIN/MAX 操作进行优化。但(PG9.2.3 和 MySQL 5.6.10 目前都还没有支持)

6)ALL/ANT 转换为集函数规则
这样可以更好地利用 MIN/MAX 操作进行优化。如:
sno > ANY (10, 2*5+3, sqrt(9))
重写为
sno > sqrt(9)
通常,聚集函数MAX(), MIN()等的效率比ANY, ALL谓词的执行效率高。

7)NOT规则
NOT (col_1 != 2) 重写为 col_1 = 2 其他类似
好处:如果 col_1 上建立了索引,则可以用索引扫描代替原来的全表扫描。

8)OR重写并集规则
如:
select * from student where ( sex = 'f' and sno > 15 ) or age > 18;
这条SQL会强迫查询优化器使用顺序存取,因为这个语句要检索的是OR操作的集合。假设,sex, age 上有索引,则可优化为:
select * from student where sex = 'f' and sno > 15 union select * from student where age > 18;

条件简化

1)把HAVING条件并入WHERE条件。(只有SQL语句不存在 GROUP BY 条件 或聚集函数的情况下才可以使用)

2)去除表达式中冗余的括号。这样子可以减少语法分析时产生的AND和OR树的层次。

3)常量传递。如:col_1 = col_2 and col_2 = 3 。改为:col_1 = 3 and col_2 = 3;

4)消除死码。如:永恒为假的条件。

5)表达式计算:如:where col_1 = 1 + 2 ,改为 where col_1 = 3

6)等式变换:化简条件(如反转关系操作符的操作数顺序)。如: -a = 3; 简化为 a = -3;

7)不等式变换。化简条件。如:a > 10 and b = 6 and a > 2 ,简化为 b = 6 and a > 10

8)布尔表达式变换。

9)谓词传递闭包。

10)任何一个布尔表达式都能被转换为一个等价的合取范式(CNF)。如:and 操作符是可交换的,所以优化器可以按先易后难的顺序计算表达式。

11)索引的利用。

外连接消除

外连接的左右子树不能互换。
查询重写的一项技术就是把外连接,转换为内连接。意义:
1)查询优化器在处理外连接操作时所需要的时间多于内连接

2)优化器在选择表连接顺序时,可以有更多更灵活的选择,从而sk以选择更好的表连接顺序。

3)表的一些连接算法,将规模小的或筛选严格的条件的作为外表,可以减少不必要的IO开销,极大地加快算法执行的速度。

嵌套连接消除

嵌套连接是指:当执行连接操作的次序不是从左到右逐个进行时,就说明这样的连接表达式存在嵌套。

1)如果连接表达式只包括内连接(JOIN ON),括号可以去掉,这意味着表之间的次序可以交换。

2)如果连接表达式包括外连接,括号不可以去掉,意味着表之间的次序只能按原语义进行,至多能执行的就是外连接向内连接转换。