第九章 关系查询处理和查询优化.ppt

第九章 关系查询处理和查询优化.ppt关系系统的定义
关系系统: 支持关系数据模型的数据库管理系统(粗略)
关系系统(确切定义): 一个系统可以定义为一个关系系统, 当且仅当它:
支持关系数据库
支持选择、投影和连接运算(自然连接), 对这些运算不要求定义任何物理存取路径
关系系统的分类:
许多关系系统的产品
:
表式系统(a)
最小关系系统(b)
关系完备的系统(c)
全关系系统(d)
S
M
I
S
M
I
S
M
I
S
M
I
a
b
c
d
关系系统的查询处理:
查询处理的步骤:
query
Parser &
translator
Relational algebra expression
Optimizer
Execution plan
Evaluation
engine
Query output
data
Statistics
about data
DBMS
关系系统的查询优化:
为什么需要查询优化
关系系统的查询优化由系统完成, 而不是由用户完成
优化器可以数据字典获取许多统计信息
如果数据库的物理统计信息改变了,优化器可以对查询进行重新优化以选择适应的执行计划
优化器可以考虑数百种不同的执行计划
优化器包括了许多复杂的技术
优化目标: 寻求最优的执行计划, 使查询执行开销尽量小
关系系统的查询优化:
查询优化的一般步骤
将查询转化成内部表示--语法树
根据等价变化规则, 将语法树转化成优化形式
选择低层操作算法
生成查询计划
查询执行开销主要包括:
总代价=I/O代价+CPU代价
多用户数据库执行开销:
总代价=I/O代价+CPU代价+内存代价
关系系统的查询优化:
一个查询实例: 求选修2号课程的学生姓名
SQL表示:
select Sname
from Students, SC
where = o=‘2’;
关系代数表示:
Q1= sname(= o=‘2’(StudentsSC))
Q2= sname(Cno=‘2’(Students SC))
Q3= sname( Students Cno=‘2’(SC))
代价计算
Q1代价计算(仅考虑I/O代价)
计算广义笛卡尔积代价
假定: 在内存中, 存放5块Students元组和一块SC元组, 一块可以装10个Students元组或100个SC元组.
假定: Students有1000个元组,SC有10000个元组, 其中选2号课程的有50个元组
数据只有读到内存才能进行连接
Q1= sname(= o=‘2’(StudentsSC))
通过读取块数计算I/O代价
读取块数计算方法:
Students 1000个元组
SC 10000个元组
读取总块数:
若每秒读写20块, 则花费:
10
100
SC
Students
5块
Q1= sname(= o=‘2’(StudentsSC))
连接后的元组个数为: 103 104=107
连接后的中间结果内存放不下, 需暂时写到外存
若每块可装10个元组, 则写出这些元组需:
(107 /10)/20=5  104s
选择操作: 读回需5  104s, 选择后剩50个元组, 假定均可放在内存
投影操作:
查询共花费: 105+2  5  104  105 s
Q1= sname(= o=‘2’(StudentsSC))
Q2= sname(Cno=‘2’(Students SC))
Q2代价计算(仅考虑I/O代价)
计算自然连接代价
也要把数据读到内存进行连接, 但连接结果比笛卡尔积要小得多
读取块数依然为:
花费为2100/20105s
连接结果大小为104个元组, 写到外存需:
(104 /10)/20=50s