关系系统及其查询优化(4).ppt

关系系统
数据库查询优化
查询处理概述
查询优化问题的提出
关系代数等价变换
查询优化策略
查询优化示例
查询优化步骤
第四章关系系统及其查询优化
作业P166 1、4
§ 关系系统
关系系统的定义
一个系统可定义为关系系统,当且仅当它:
支持关系数据库(关系数据结构)
支持选择、投影和连接运算,对这些运算不必定义任何存取路径
关系系统的分类
表式系统
(最小)关系系统
关系完备系统
全关系系统
§ 关系系统
表式系统
仅支持关系(即表)数据结构,不支持集合级的操作。
(最小)关系系统
即前面定义的关系系统。它们仅支持关系数据结构和三种关系搡作。许多微机关系数据库系统如FoxPro等就属于这一类
关系上完备的系统
这类系统支持关系数据结构和所有的关系代数操作(功能上与关系代数等价)。90年代初的许多关系数据库管理系统属于这一类
全关系系统
这类系统支持关系模型的所有特征
查询优化问题的提出
查询优化策略
关系代数等价变换
查询优化算法
查询优化步骤和示例
§ 数据库查询优化
一个用户查询,系统实现时均使用一个与之相应的关系代数表达式去求解,同一查询等价关系代数表达式的不同,就会出现不同的求解路线。
如:求选修了2号课程的学生姓名,SQL语句
Select sname from s,sc where = AND o=‘2’
等价关系代数表达式如下:
Q1=Пsname ( = ^ o=‘2’(S X SC))
Q2= Пsname ( o=‘2’(S |><| SC) )
Q3= Пsname (S |><| o=‘2’( SC) )
§ 查询优化问题提出
§ 查询优化问题提出
假设1:外存:
Student:1000条,SC:10000条, 选修2号课程:50条
假设2:一个内存块装元组:10个Student, 或100个SC, 内存中一次可以存放: 5块Student元组,
1块SC元组和若干块连接结果元组
假设3:读写速度:20块/秒
假设4:连接方法:基于数据块的嵌套循环法
§ 查询优化问题提出
读取Student和SC表的策略
Student表
SC表
100个SC元组
内存缓冲区
中间文件
10个Student元组
10个连接后的元组
第
一
个
五
块
第
二
个
五
块
…
…共一千个学生记录
…共一万个选课记录
第1-100个元组
第101-200个元组
第1-10个元组
第11-20个元组
第一块
第二块
…
第 n 块
§ 查询优化问题提出
Q1=Пsname ( = ^ o=‘2’(S X SC))
① Student×SC
读取总块数= 读S表块数+ 读SC表遍数* 每遍块数
 =1000/10+(1000/(10×5)) ×(10000/100)
=100+20×100=2100
读数据时间=2100/20=105秒
中间结果大小= 1000*10000 = 107 (1千万条元组)
写中间结果时间= 10000000/10/20 = 50000秒 
②б: 读数据时间= 50000秒 
③П: 总时间=105+50000+50000秒= 100105秒=
Q2= Пsname ( o=‘2’(S |><| SC) )
①
读取总块数= 2100块
读数据时间=2100/20=105秒
中间结果大小=10000 (减少1000倍)
写中间结果时间=10000/10/20=50秒 
②б: 读数据时间=50秒 
③П 
总时间=105+50+50秒=205秒=
§ 查询优化问题提出
Q3= Пsname (S |><| o=‘2’( SC) )
①б
读SC表总块数= 10000/100=100块
读数据时间=100/20=5秒 
中间结果大小=50条不必写入外存 
②
读Student表总块数= 1000/10=100块
读数据时间=100/20=5秒 
③П 
总时间=5+5秒=10秒
§ 查询优化问题提出