关系查询处理和查询优化.pptx

1
本章要点
关系系统的查询步骤
查询优化的引例
优化的准则
优化的步骤
小结
2
关系数据库系统的查询处理
查询处理步骤
查询分析:词法、语法分析
查询检查:语义检查,语法分析树
查询优化:
查询执行:代码生成器
查询操作算法
选择操作:
全表扫描,索引(散列)扫描
连接操作:
嵌套循环,排序-合并,索引连接,hash join
3
关系数据库系统的查询优化
查询优化的好处:
查询优化是RDBMS的关键技术,好的系统是能够减轻用户负担的
对使用系统的用户来说,只需提出“做什么”,而不必考虑如何表达查询能达到最好的效率,一切都由关系系统来实现
查询优化的总目标
选择有效的策略,求得给定关系表达式的值
实现查询优化的一般步骤(4步)
生成语法树
标准化语法树
选择低层算法
生成查询计划
4
一个实例
有如下关系:S(Sno,Sname,SEX,AGE,…)和SC(o,Grade),查询选修了001号课程的学生姓名
用关系代数表达式来完成此查询可以选多种方案:
Q1=Sname(= o=“001”(SSC))
Q2=Sname(o=“001”(S SC))
Q3=Sname(S o=“001”(SC))
5
比较三种查询方案的效率
设S表中有1000条学生记录, SC表中有10000条选课记录,而选了001号课程的记录有50条,则三种方案的查询效率是不同的
步骤
方案1
方案2
方案3

读S和SC表
105 s
读S和SC表
105 s
仅读SC表,选出50个满足条件的元组
5 s
连接后结果为107个元组
5104 s
自然连接后为104个元组
50 s

依次读入107个元组,选择满足条件的50个
5104 s
读取自然连接后的104个元组,选择其中50条满足要求
50 s
读取S表与内存中的50个SC元组连接
5 s

在内存中的50个元组上投影输出
投影输出上步的结果
投影输出结果
6
优化的一般准则
由上例可以看出:遇到有选择和连接操作时,应先做选择以减少连接的元组
优化准则:
先做选择,以减少元组
预处理,在连接属性上建立索引和对关系排序
投影和选择同时进行,避免对同一关系的重复扫描
投影和双目运算结合
结合选择和在其之前执行的笛卡儿积成为连接运算,如前例把方案1的SSC和选择运算结合成方案2的自然连接运算
找出公共子表达式,如定义视图的表达式
7
代数优化
查询优化的基础:关系表达式的优化
变换规则:
交换率:连接、笛卡儿积的两端可交换;选择与笛卡儿积、与并、与差运算的交换;投影与笛卡儿积、与并的交换
结合率:连接、笛卡儿积的结合率
串接率:投影、选择的串接
优化算法
输入:关系表达式的语法树
算法:关系表达式的优化
输出:计算该表达式的程序
8
优化的一般步骤
将查询转化成语法树
把语法树优化,采用关系代数表达式的优化算法:
选择和投影尽可能提前,即移到树的叶端;
多个选择和投影的串接,使之同时执行;
内节点分组。
选择低层的存取路径,如索引的选择等
生成查询计划,选择代价最小的
9
习题
P275-2题:该查询转化成关系代数表达式为
Cname(=  o=o  =‘IS’(StudentSCCourse))
转化成关系代数语法树为:
=‘IS’
Student
o=o
Course



Cname
 =
SC
优化后的语法树为
Cname
 =
SC
=‘IS’
Student

Course
o=o

10
物理优化
基于启发式规则的存取路径选择优化
基于代价的优化