数据库系统概论-第九章-关系查询处理和查询优化

4.1 关系系统

能够在一定程度上支持关系模型的数据库管理系统是关系系统。

由于关系模型中并非每一部分都是同等重要的，并不苛求一个实际的关系系统必须完全支持关系模型。

关系数据结构：

域及域上定义的关系

关系操作：

并、交、差、广义笛卡尔积、选择、投影、连接、除等

关系完整性：

实体完整性、参照完整性、用户自己定义的完整性

一个数据库管理系统可定义为关系系统，当且仅当它至少支持：

1.    关系数据库（即关系数据结构）

系统中只有表这种结构

2.    支持选择、投影和（自然）连接运算

对这些运算不要求用户定义任何物理存取路径、对关系系统的最低要求

4.2 关系系统的查询优化

4.2.1 查询优化概述

查询优化的必要性：查询优化极大地影响    RDBMS 的性能。

查询优化的可能性：关系数据语言的级别很高，使    DBMS 可以从关系表达式中分析查询语义。

用户不必考虑如何最好地表达查询以获得较好的效率，系统可以比用户程序的优化做得更好

(1)    优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息

(2)    如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。

(3)    优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。

(4)    优化器中包括了很多复杂的优化技术

查询优化的总目标：选择有效策略，求得给定关系表达式的值

实际系统的查询优化步骤：

1.    将查询转换成某种内部表示，通常是语法树

2.    根据一定的等价变换规则把语法树转换成标准（优化）形式
 

3.    选择低层的操作算法对于语法树中的每一个操作

计算各种执行算法的执行代价【选择代价小的执行算法】

4.    生成查询计划  (查询执行方案  )

查询计划是由一系列内部操作组成的。

4.2.4 关系代数等价变换规则

关系代数表达式等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的上面的优化策略大部分都涉及到代数表达式的变换

4.2.6 优化的一般步骤

1．把查询转换成某种内部表示

2．代数优化：把语法树转换成标准（优化）形式

3．物理优化：选择低层的存取路径

4．生成查询计划，选择代价最小的 

 

一．关系查询优化的概述

1.    查询优化在关系数据库中的重要性及必要性

关系系统的查询优化既是    RDBMS实现的关键技术又是关系系统的优点所

在。它减轻了用户选择存取路径的负担。查询优化极大地影响    RDBMS的性能。用

户只要提出“干什么”，不必指出“怎么干”。查询优化的优点不仅在于用户不

必考虑如何最好地表达查询以获得较好的效率，    而且在于系统可以比用户程序的

“优化’夕做得更好。

2.查询优化的可能性和优点

1)    优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息

2)    如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。

3)    优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。

4)    优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术；

3.查询优化的一般准则

( l    ）选择运算应尽可能先做；
( 2    ）把投影运算和选择运算同时进行；
( 3    ）把投影同其前或其后的双目运算结合起来执行；
( 4    ）把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算；
( 5    ）找出公共子表达式；
( 6    ）选取合适的连接算法。

4.    查询优化的一般步骤
 

( 1 ）把查询转换成某种内部表示，通常用的内部表示是语法树。
( 2 ）把语法树转换成标准（优化）形式。即利用优化算法，把原始的语法树转换成优化的形式。

( 3 ）选择低层的存取路径。

( 4 ）生成查询计划，选择代价最小的。

5.代价模型

一般 DBMS采用基于代价的优化算法：

集中式数据库

单用户系统

总代价 = I/O  代价 + CPU代价

多用户系统

总代价 = I/O  代价 + CPU代价 +  内存代价

分布式数据库

总代价 = I/O  代价 + CPU代价 [+  内存代价 ] +    通信代价

二．关系数据库查询优化方法

1.代数优化

关系代数表达式等价指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的
1）查询树启发式优化，一般规则有
选择运算应尽可能先做  ( 最重要，最根本 )

目的：减小中间关系

投影运算和选择运算同时做

目的：避免重复扫描关系

将投影运算与其前面或后面的双目运算结合

目的：减少扫描关系的遍数

在执行连接操作前对关系适当进行预处理

按连接属性排序

在连接属性上建立索引

某些选择运算＋在其前面执行的笛卡尔积

===>    连接运算
2）查询树的启发式优化  —算法

（1）分解选择运算

（2）通过交换选择运算，将其尽可能移到叶端

（3）通过交换投影运算，将其尽可能移到叶端

（4）合并串接的选择和投影，以便能同时执行或在一次扫描中完成

（5）对内结点分组

（6）生成程序
 

例： бStudent.Sno=SC.Sno (Student    × SC)Student    SC

提取公共子表达式 ;

例如：查询小***修的所有课程。 可以用关系代数来表达多种不同的查询方法。

S1=π cno（σS.sno=SC.sno ∧ S.sname= “小王” ( S ×SC))

S2=π cno（σ S.sname=“小王”

( S    SC))

S3=π cno（σS.sname=“小王” ( S ）    SC)

三种查询的结果是完全相同的，但三种查询的具体操作、所占用的内存、所消耗的时间是不相同的。显然：

S3    优于  S2    优于 S1

查询优化对减少系统开销、提高运行速度是很重要的。

2.物理优化
物理优化就是要选择高效合理的操作算法或存取路径，球的优化的查询计划，达到查询优化的目标。

1）物理优化可以选择的方法

（1） 基于规则的启发式优化；大多数情况下都适用。

（2） 基于代价估算的优化； 优化器估算不同执行策略的代价，    并选出具有最

小代价的执行计划。

（3） 两者结合的优化方法。

2）选择操作的启发式规则

对于小关系，使用全表顺序扫描，即使选择列上有索引；对于大关系，启发式规则有：

对于选择条件是主码＝值的查询；

查询结果最多是一个元组，可以选择主码索引；

一般的 RDBMS会自动建立主码索引；

对于选择条件是非主属性＝值的查询，并且选择列上有索引要估算查询结果的元组数目

如果比例较小 (<10%)可以使用索引扫描方法

否则还是使用全表顺序扫描

3）全表扫描算法的代价估算公式

如果基本表大小为 B 块，全表扫描算法的代价 cost ＝ B 如果选择条件是码＝值，则平均代价 cost ＝ B/2

4）排序 -合并连接算法的代价估算公式

如 果 连 接 表 已 经 按 照 连 接 属 性 排 好 序 ， 则    cost  ＝

Br+Bs+(Frs*Nr*Ns)/Mrs    。

如果必须对文件排序

需要在代价函数中加上排序的代价

对 于 包 含    B    个 块 的 文 件 排 序 的 代 价 大 约 是

(2*B)+(2*B*log2B)
三. 总结

        对于数据库的设计，数据库的查询优化是必不可少的； 查询处理时 RDBMS的核心，而查询优化技术是查询处理的关键。一个好的查询优化处理能使的执行效率更高，减小程序的设计代价。

查询优化能避免不必要的复杂性， 对于有些查询构建方法， 优化器无法总能给出最优执行计划。

给优化器提供约束和统计信息， 询优化器生成的执行计划的性能和健壮性很大程度上依赖于可获得信息的质量。