文档介绍：4. 关系系统及查询优化
关系系统
关系系统的定义
关系系统分类
查询优化
查询优化概念
查询处理过程
优化原理和技术
软件学院
.
关系系统
关系模型
数据结构
关系操作
完整性
关系系统
笼统讲，支持关系模型的数据然连接运算（假定每秒读写20块）
读块数：100块＋20遍100块＝2100，写块数：1000；
共需时间：3100/20=155秒
选择运算
读块数：1000；共需时间：1000/20=50秒
方案2读写磁盘共需155＋50＝205秒
S1000条
Sc10000条
c02的50条
100条SC
中记录
10条S中记录
读S一次:1000/10=100块
读SC一次:10000/100=100块
完成 需读SC:
10000/10*5=20遍
10条S中记录
10条S中记录
10条S中记录
10条S中记录
块10条记录
写S SC:10000
/10=1000块
S SC有
10000
记录，每
软件学院
.
处理分析
方案3: ∏sname (S =“c02”(SC))
选择运算（假定每秒读写20块）
读块数：100；共需时间：100/20=5秒
自然连接运算
读块数：100，写块数：5；
共需时间：105/20=5秒
方案3读写磁盘共需5＋5＝10秒
S1000条
Sc10000条
c02的50条
100条SC
中记录
10条S
中记录
读S一次:1000/10=100块
读SC一次:10000/100=100块
100条记录
SC有50
记录,每块
完成 需读S一遍
块10条记录
(SC) S有
50记录，每
写 (SC) S:50/10=5块
软件学院
.
一个启发性例子
以上例子中，显然方案3的执行效率更高。
在执行关系代数表达式中的一个很简单的变化，即先做选择后再做连接，而不是先做连接后做选择，就使得执行的性能有了戏剧性的变化。
如果SC表在属性cno上有索引或哈希，那么第一步读入的元组数将从10000降到50，这将使执行性能比原来有进一步的提高。同样如果S表在属性sno上有索引或哈希，那么第二步读入的元组数将从1000降到50，这将使执行性能比原来又有提高。
以上例子，虽然简单，但足以说明为什么查询优化是必要的，也可以说明在实际中什么样的优化是可能的。
软件学院
.
关系系统的查询优化
对于一个给定的查询，尤其是复杂查询，通常会有许多种可能的策略，查询优化就是能从这许多策略中找出最有效的查询执行计划的一种处理过程。
并不要求一般用户能够写出一个高效处理的查询，而是期望系统能够构造一个能最小化查询执行代价的查询执行计划。
优化一方面出现在关系代数级，即系统尝试找出一个与给定的表达式等价但执行起来更为有效的表达式。另一方面是用于对处理查询选择一个详细的策略，比如使用统计信息、选择可用的特定索引，等等。
软件学院
.
关系系统的查询优化
自动优化系统（优化器）可以在查询优化方面做到以下几点：
从数据字典中获得许多统计信息。比如表的记录数、属性中唯一值得个数。
当统计信息改变时，系统可以自动对查询进行重新优化。
优化器可以考虑一个给定查询的成百上千的执行策略。
优化器可以认为是包含着最优秀程序员的技巧和服务的程序。
优化能力是关系系统提供的一种功能，关系数据库查询优化的目标是：为计算所给定的关系表达式选择一个高效（时间和空间）的执行策略。
软件学院
.
查询处理概述
查询处理分为四个大的阶段：
将查询转换为内部格式
将内部格式转换为规范格式
为执行选择底层过程
生成并选择最低代价的查询计划
源查询
DML处理器
编译后查询
优化器
查询计划
运行时管理器
目录表
数据库
元数据
数据
编译
关系代数表达式
表达式转换代价估算及统计数据
优化后代码执行计划
执行引擎
软件学院
.
查询处理概述
将查询转换为内部格式
目的是便于机器处理。
这种内部格式通常为语法树或查询树。
为了说明方便，内部格式可以理解为关系代数。
将内部格式转换为规范格式
目的是找到一种在某些方面比源查询更为高效的表示方法。
规范格式是数学领域的术语：给定对象集Q，并定义它们之间等价规则，称Q的子集C是在等价规则下的规范格式的集合，当且仅当Q中每个对象q都等价于C中的某一对象c，c被称为q的规范格式。
此处规范格式即：使用等价变换规则将阶段1的输出转换为某种等价、但更为高效的格式。
软件学院
.
查询处理