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

关系查询处理和查询优化
第1页，共31页，编辑于2022年，星期五
第九章 关系查询处理及其查询优化
关系数据库系统的查询处理
关系数据库系统的查询优化
代数优化 ---关系代数表 + 内存代价
分布式数据库
总代价 = I/O代价 + CPU代价+ 内存代价 + 通信代价
查询优化的总目标：
选择有效策略,求得给定关系表达式的值,使得查询代价最小。
第10页，共31页，编辑于2022年，星期五
一个实例
例：求选修了课程Ｃ2的学生姓名 
SELECT
FROM Student, SC
WHERE = AND ='2';
假设1：外存：
Student:1000条,SC:10000条, 选修2号课程:50条
假设2：
一个内存块装元组:10个Student, 或100个SC或10个连接结果元组 ; 内存中一次可以存放: 5块Student元组, 1块SC元组
假设3：读写速度：20块/秒
假设4：连接方法：基于数据块的嵌套循环法
第11页，共31页，编辑于2022年，星期五
执行策略1
Ｑ1＝ ПＳname(= ∧='2' (Student×SC)) 
① Student×SC
读取总块数= 读Student表块数 + 读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秒 =
第12页，共31页，编辑于2022年，星期五
执行策略2
Ｑ2＝ ПＳname(=' 2' (Student SC))
①
读取总块数= 2100块
读数据时间=2100/20=105秒
中间结果大小
=10000 （减少1000倍）
写中间结果时间
=10000/10/20=50秒 
②б
读数据时间=50秒 
③П 
总时间＝105＋50＋50秒＝205秒=
第13页，共31页，编辑于2022年，星期五
执行策略3
Ｑ2＝ ПSname(Student =' 2' (SC)) 
①б
读SC表总块数= 10000/100=100块
读数据时间=100/20=5秒 
中间结果大小=50条 不必写入外存 
②
读Student表总块数= 1000/10=100块
读数据时间=100/20=5秒 
③ П 
总时间＝5＋5秒＝10秒
第14页，共31页，编辑于2022年，星期五
执行策略4
Ｑ2＝ ПＳname(Student ='2' (SC))
假设SC表在Cno上有索引，Student表在Sno上有索引
 ①б
读SC表索引
读SC表总块数
= 50/100<1块
读数据时间 
中间结果大小=50条 不必写入外存
②
读Student表索引= 读Student表总块数= 50/10=5块
读数据时间
③ П
总时间<10秒
第15页，共31页，编辑于2022年，星期五
代数优化
代数优化：基于关系代数等价变换规则的优化方法
关系代数表达式等价
指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的
第16页，共31页，编辑于2022年，星期五

设E1、E2等是关系代数表达式，F是条件表达式
l. 连接、笛卡尔积交换律
E1× E2≡ E2×E1
E1 E2≡E2 E1
E1 F E2≡E2 F E1
2. 连接、笛卡尔积的结合律
(E1×E2) × E3 ≡ E1 × (E2×E3)
(E1 E2) E3 ≡ E1 (E2