第九章关系查询与查询优化.ppt

第九章关系查询与查询优化
_I Can Dream About 
关系数据库系统的查询处理
查询分析
查询检查
查询优化
查询执行
词法分析
语法分析
语义转换
符号名转换
安全性检查
完整性检查
查询树
于语法树中的每一个操作
计算各种执行算法的执行代价
选择代价小的执行算法
4. 生成查询计划(查询执行方案)
查询计划是由一系列内部操作组成的。
基于代价模型的优化算法
集中式数据库
单用户系统
总代价 = I/O代价 + CPU代价
多用户系统
总代价 = I/O代价 + CPU代价 + 内存代价
分布式数据库
总代价 = I/O代价 + CPU代价[+ 内存代价] + 通信代价
代价模型
一个实例
[例3] 求选修了课程Ｃ2的学生姓名
  SELECT FROM Student, SC
WHERE = AND ='2';
执行策略
Ｑ1＝ ПＳname(= ∧='2' (Student×SC))
Ｑ2＝ ПＳname(=' 2' (Student SC))  
Ｑ3＝ ПＳname(Student ='2' (SC))
代数优化
基于关系代数等价变换规则的优化方法为代数优化；
代数优化策略是通过对关系代数表达式的等价变换来提高查询效率；
关系代数表达式的等价是指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的；
两个表达式E1和E2是等价的,记为E1 ≡ E2。
7. 选择与并的分配律
假设：E=E1∪E2，E1，E2有相同的属性名
бF(E1∪E2)≡ бF(E1)∪ бF(E2)
 
8. 选择与差运算的分配律
假设：E1与E2有相同的属性名
бF(E1-E2)≡ бF(E1) - бF(E2)
9. 选择对自然连接的分配律
бF(E1∪E2)≡ бF(E1)∪ бF(E2)
  F只涉及E1与E2的公共属性
10. 投影与笛卡尔积的分配
假设：E1和E2是两个关系表达式，
A1，…，An是E1的属性，
B1，…，Bm是E2的属性
π A1,A2, …,An,B1,B2, …,Bm （E1×E2)≡
π A1,A2, …,An（E1)× π B1,B2, …,Bm(E2)
l1. 投影与并的分配
假设：E1和E2 有相同的属性名
πA1,A2, …,An(E1∪E2)≡πA1,A2, …,An(E1)∪πA1,A2, …,An(E2)
查询树的启发式优化
启发式规则的代数优化,是对关系代数表达式的查询树进行优化,其典型的规则有:
选择运算应尽可能先做  
目的：减小中间关系
投影运算和选择运算同时做
目的：避免重复扫描关系
把投影运算与其前面或后面的双目运算结合
目的：减少扫描关系的遍数
某些选择运算＋在其前面执行的笛卡尔积===> 连接运算
例：= (Student×SC)
 
  Student SC
提取公共子表达式
关系代数表达式的优化算法
算法：关系表达式的优化。
输入：一个关系表达式的查询树。
输出：优化的查询树。
方法：
(1) 分解选择运算
利用规则4把形如бF1 ∧F2 ∧ … ∧ Fn (E)变换为
бF1 (бF2(… (бFn(E))… ))
(2) 通过交换选择运算，将其尽可能移到叶端
对每一个选择，利用规则4～8尽可能把它移到树的叶端。
(3) 通过交换投影运算，将其尽可能移到叶端
对每一个投影利用规则3、5、l0、11中的一般形式尽可能把它移向树的叶端。
(4) 利用规则3～5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成，尽管这种变换似乎违背“投影尽可能早做”的原则，但这样做效率更高。
(5) 对内结点分组
把上述得到的语法树的内节点分组。
每一双目运算(×， ，∪，-)和它所有的直接祖先为一组(这些直接祖先是б，π运算)。
如果其后代直到叶子全是单目运算，则也将它们并入该组，但当双目运算是笛卡尔积(×)，而且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组。
例[4] 求选修了课程Ｃ2的学生姓名
SELECT