《数据库查询优化器的艺术》第三章物理查询优化学习笔记

代价模型

总代价 = IO 代价 + CPU 代价
COST = P * a_page_cpu_time + W * T

P:计划运行时访问的页数,a_page_cpu_time 是每个页读取的时间花费,其积反映了IO代价
T:访问的元组。反映了CPU花费。(存储层是以页面为单位,数据以页面的形式读入内存,每个页面上可能有多个元组,访问元组需要解析元组结构,才能把元组上的字段读出,这消耗的是CPU)。如果是索引扫描,则还会包括索引读取的花费。
W:权重因子。表明IO到CPU的相关性,又称选择率(selectivity)。选择率用于表示在关系R中,满足条件“A<op>a”的元组数与R的所有元组N的比值。

单表扫描算法

全表扫描,局部扫描。单表扫描与IO操作密切相关。

1)顺序扫描(SeqScan)。当无索引可用,或访问表中的大部分数据,或表的数据量很小时,使用顺序扫描效果较好。

2)索引扫描(IndexScan)。根据索引键读索引,找出物理元组的位置。【如果选择率很高,不适宜使用索引扫描】

3)只读索引扫描(IndexOnlyScan)。根据索引键读索引,索引中的数据能够满足条件判断,不需要读取数据页面。比索引扫描少了读取数据的IO花费。

4)行扫描(RowIdScan)。用于直接定位表中的某一行。对于元组,通常为元组增加特殊的列,通过特殊的列计算出元组r物理位置,然后直接读取元组对应的页面,获取元组。在PostgreSQL中称为【Tid】扫描,此种方式是在元组头上增加名为【CTID】的列,用这列的值可直接计算本条元组的物理存储位置。

5)并行表扫描(ParallelTableScan)。对同一个表,并行地、通过顺序的方式获取表的数据,结果是得到一个完整的表数据。

6)并行索引扫描(ParallelIndexScan)。对同一个表,并行地、通过索引的方式获取表的数据,将结果合并在一起。

7)组合多个索引扫描(MultipleIndexScan)。

顺序扫描代价估算公式

COST = N_page * a_tuple_IO_time + N_tuple * a_tuple_CPU_time

索引扫描代价估算公式

COST = C_index + N_page_index * a_tuple_IO_time
C_index:索引的IO花费。C_index = N_page_index * a_page_IO_time
N_page_index:索引作用下的可用元组数。N_page_index = N_tuple * 索引选择率

索引

本质上是通过索引直接定位表的物理元组,加快数据获取的方式,所以索引优化的手段是物理查询优化。

如何利用索引

1)索引列作为条件出现在 WHERE,HAVING, ON 子句中。

2)索引列是被连接的表(内表)对象的列且存在于连接条件中

除了上述两种情况,还有一些特殊情况可以使用索引,如:排序操作、在索引列上求MINMAX值等。

(1)对表做查询,没有列对应作为过滤条件(如出现在WHERE子句中),只能做顺序扫描。

(2)对表做查询,有列对象且索引列作为过滤条件,可做索引扫描。

(3)对表做查询,有列对象作为过滤条件,但索引列被运算符“-”处理,查询优化器不能在执行前进行取反运算,这时不可利用索引扫描,只能做顺序扫描。

(4)对表做查询,有列对象作为过滤条件,且目标列没有超出索引列,可做只读索引扫描,这种扫描方式比单纯的索引扫描的效率更高。

(5)对表做查询,有索引存在,但选择条件不包括索引列对象,只能使用顺序扫描。

(6)对表做查询,有索引存在,选择条件包括索引列对象,可使用索引扫描,对选择条件中不存在索引的列作为过滤器被使用。

(7)对表做查询,有索引存在,选择条件包括索引列对象,但索引列对象位于一个表达式中,参与了运算,不是“key=常量”格式,则索引不可使用,只能是顺序扫描。如:
select a. from a where a.a1 + a.a3 = 2;(a1列是索引),这时只能做顺序扫描。

select a.
from a where a.a1 = 2 - a.a3 ;(a1列是索引),这时只能做顺序扫描。

(8)对表做查询,有索引列对象作为过滤条件,操作符是范围操作符 > 或 < ,可做索引扫描。

(9)对表做查询,有索引列对象作为过滤条件,操作符是范围操作符 <> ,不可做索引扫描。

(10)对表做查询,有索引列对象作为过滤条件,操作符是范围操作符BETWEEN-AND ,可做索引扫描。

索引列的位置对使用索引的影响

1)索引列出现在目标列,通常不可使用索引(但不是全部情况下不能使用索引)

(2)聚集函数MIN / MAX用在索引列上,出现在目标列,可使用索引。

(3)索引列出现在WHERE子句中,可使用索引。

(4)索引列出现在 JOIN / ON 子句中,作为连接条件,有时不可使用索引。(这取决于代价估算模型)

(5)索引列出现在 JOIN / ON 子句中,作为限制条件满足“key <op> 常量 ”格式可用索引。

(6)(5)索引列出现在 WHERE子句中,但与子查询比较,格式上不满足"key <op> 常量",不可用索引。

索引列对GROUP BY子句的影响

1)索引列出现在 group by 子句中,不触发索引扫描。

(2WHERE子句出现索引列,【且】GROUP BY 子句出现索引列,索引扫描被使用。

(3WHERE子句中出现非索引列,且GROUP BY子句出现索引列,索引扫描不被使用。

索引列对HAVING子句的影响

1WHERE子句出现非索引列,且GROUP BY和HAVING子句出现索引列,索引扫描被使用。

索引列对ORDER BY子句的影响

1ORDER BY子句出现索引列,可使用索引。

(2ORDER BY子句使用非索引列,不可使用索引扫描。

索引列对 DISTINCT 的影响

1DISTINCT 子句管辖范围内出现索引列,不可使用索引。

联合索引对索引使用的影响

(1)使用联合索引的全部索引键,可触发索引的使用。

(2)使用联合索引的前缀部分索引键。如:key_part_1 <op> 常量。可触发索引的使用。

(3)使用部分索引,但不是联合索引的前缀部分,如“key_part_2 <op> 常量",不可触发索引的使用。

(4)使用索引索引的全部索引键,但索引键不是AND操作,不可触发索引的使用。

多个索引对索引使用的影响

1WHERE子句出现两个可利用的索引,优选最简单的索引。(但这也是要根据代价估算模型来决定的)

(2WHERE子句出现两个可利用的索引且索引键有重叠部分,优选最简单的索引。

聚簇索引

是指表的一个或多个列作为索引的关键字,以关键字的具体值为依据,把所有具有相同值的元组连续放在外存上。当从磁盘扫描读取的块进入内存时,相同值的其他元组在内存中的概率增大,能有效减少IO。即:聚簇索引确定表中数据的物理顺序。聚簇索引对于那些经常要搜索范围值的列特别有效。使用聚簇索引找到包含第一个值的行后,便可以确保包含后续索引值的行在物理相邻。

《数据库查询优化器的艺术》第二章逻辑查询优化学习笔记

主要解决的问题

如何找出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,则可避免不满足条件的条件参与积的运算,节约时间减少结果的大小。

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

选择 —— 和集合运算

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

选择 —— 和投影

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

投影 —— 和基本投影性质

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

投影 —— 和集合运算。

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

运算规则主导的优化

连接、笛卡儿积 交换律

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

连接、笛卡儿积 结合律

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

投影的串接定律

在同一个关系上,只需要做一次投影运算,且一次投影时选择多列同时完成。所以许多数据库优化引擎为同一个关系收集齐本关系上的所有列(目标列和 WHEREGROUP 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)目标列
这时,只能是标量子查询,否则数据库可能返回类似”错误:子查询必须只能返回一个字段“的提示。

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

3WHERE子句

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

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

6)HAVING子句

7ORDER 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 BYDISTINCT 子句,则子查询只能单独求解,不可以上拉到上层。

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谓词限定的全表扫描,从而提高了查询的效率。

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

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


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

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

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

8OR重写并集规则
如:
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 = -37)不等式变换。化简条件。如: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)如果连接表达式包括外连接,括号不可以去掉,意味着表之间的次序只能按原语义进行,至多能执行的就是外连接向内连接转换。

《数据库查询优化器的艺术》第一章学习笔记

数据库管理系统

数据定义
数据操纵
数据库的运行管理
数据库的建立和维护等

查询优化的目标

使查询优化引擎生成一个执行策略的过程,尽量使查询的总开销(IO,CPU,网络传输等)达到最小。

查询优化技术(广义)

查询重用技术
查询重写规则
查询算法优化技术
并行查询优化技术
分布式查询优化技术
其他方面(如框架结构)的优化技术

查询优化技术(狭义)

查询重写规则
查询算法优化

代数优化(逻辑优化)

主要依据关系代数的等价变换做一些逻辑变换。查询重写规则属于逻辑优化。

非代数优化(物理优化)

主要根据数据读取,表连接方式,表连接顺序,排序等技术对查询进行优化。查询算法优化,属于物理优化。运用了基于代价估算的多表连接算法求解最小花费的技术。

数据库调优

目标是使数据库有更高的吞吐量以及更短的响应时间。它是全局的。而查询优化技术是SQL层面的,局部的优化。

查询重用

指尽可能利用先前的执行结果,以达到节约查询计算全过程的时间并减少资源消耗的目的。
(1)查询结果的重用
在缓冲区分配一块缓冲块,存放该SQL语句文本和最后的结果集,当遇到同样的SQL输入时,可直接把结果返回。它节约了查询计划生成时间和查询执行过程的时间,减少了查询执行全过程的资源消耗。

(2)查询计划的重用
缓存一条查询语句的执行计划及其相应语法树结构。查询计划的重用技术减少了查询计划生成的时间和资源消耗

查询重写规则

它是一种等价转换。即对于任何相关模式的任意状态都会产生相同的结果。目标:
(1)将查询转换为等价的,效率更高的形式。
(2)尽量将查询重写为等价,简单且不受表顺序限制的形式,为物理查询优化阶段提供更多的选择。如:视图的重写,子查询的合并转换等。
重写的主要依据是关系代数。它是查询重写规则的理论支持。
它有3个角度,第4个是物理优化。
(1)语法级
(2)代数级
(3)语义级
(4)物理级:即基于代价估算模型,比较得出代价最小的,是从连接路径中选择代价最小的路径的过程。

主要思路:
1)将过程性查询转换为描述性的查询,如视图重写
2)将复杂的查询(嵌套子查询,外连接,嵌套连接)尽可能转换为多表连接查询
3)将效率低的谓词转换为等价的效率高的谓词(如等价谓词重写)
4)利用等式和不等式的性质,简化 WHERE, HAVING 和 ON 条件

核心是:等价转换,只有等价才能转换。

查询算法优化

查询优化即求解给定查询语句的高效执行计划的过程。

单表结点获取数据的方式有:
(1)直接通过IO获取
(2)通过索引获取数据
(3)通过索引定位数据的位置再经IO到数据块中获取数据
这是从物理存储到内存解析成逻辑字段的过程。

查询计划的策略:
(1)基于规则优化
(2)基于代价优化。
PG和MySQL采取了基于规则和代价估算的查询优化策略。

多表连接优化算法

SYSTEM-R算法
启发式搜索算法 
贪婪算法 
动态规划算法
遗传算法

并行查询优化

单机:找到查询的一个具有最小执行花费的执行计划
并行:寻找具有最小响应时间的查询执行计划

并行查询:
(1)操作内并行:将同一操作,如单表扫描操作,两表连接操作,排序操作等分解成多个独立的子操作,由不同的CPU同时执行。
(2)操作间并行:一条SQL查询语句可以分解成多个子操作,由多个CPU执行。

分布式查询优化

查询策略优化(主要是数据传输策略)和局部处理优化(传统的单结点数据库的查询优化技术)是查询优化的重点。

主要目标:
减少传输的次数和数据量

分布式代价估算模型
总代价 = IO代价 + CPU代价 + 通信代价