第五章査询处理与优化 5.1概述 511查询处理的一般过程 512例子 问题:选修了℃CS01的学生姓名? SELECT SNAME FROM SSC WHERE SS#=SC S# AND C#=CSOI 513查询优化 代数优化 依赖于存取路径的优化(物理优化) 规则优化 代价估算优化 52代数优化 521关系代数等价变换规则 (1)选择的串接 0F(0F2(R))≡0F1AF2(R) (2)选择的交换 0F(0P2(R)=0F2(0F(R) (3)投影的串接 TL(π12(..TL1(R).)≡L(R)条件:L1sL2…sLn (4)选择与投影的交换 T(0(R)≡0r(T1(R)F的属性是L的子集 (5)连接/笛卡儿积的交换率 RD<S≡SD<RR×S≡S×R (6)选择对连接/笛卡儿积的分配率 0F(RD<S)≡(0F(R)D<S Attr(F)c Attr(R) o FIA F2 (RDAS)=OFI(R)D4 0 F2(S) Attr(F1c Attr(R) (7)股投影对连接/笛卡儿积的分配率
第五章 查询处理与优化 5.1 概述 5.1.1 查询处理的一般过程 5.1.2 例子 问题：选修了’CS01’的学生姓名？ SELECT SNAME FROM S,SC WHERE S.S# = SC.S# AND C#=’CS01’ 5.1.3 查询优化 ➢ 代数优化 ➢ 依赖于存取路径的优化（物理优化） ➢ 规则优化 ➢ 代价估算优化 5.2 代数优化 5.2.1 关系代数等价变换规则 (1)选择的串接. σF1(σF2(R))≡σF1∧ F2(R) (2)选择的交换 σF1(σF2(R))≡σF2(σF1(R)) (3)投影的串接. πL1(πL2(…πLn(R)…)) ≡πL1(R) 条件：L1 L2 … Ln (4)选择与投影的交换. πL(σF(R))≡σF(πL(R)) F 的属性是 L 的子集 (5)连接／笛卡儿积的交换率 R S≡S R R×S≡S×R (6)选择对连接／笛卡儿积的分配率. σF(R S) ≡ (σF(R)) S Attr(F) Attr(R) σF1∧ F2 (R S) ≡σF1(R) σF2(S) Attr(F1) Attr(R) (7)投影对连接／笛卡儿积的分配率
TLuL2(RD<S)≡rL(R)p<π12(R) Attr(L1 c Attr(R), Attr(L2)g Attr(S), Attr(F)c Attr Li U L2) (8)选择对∪、∩、一的分配率 0F(RUS)≡0F(R)∪0F(S) (9)投影对∪的分配率 TL(RUS)≡πL(R)∪πL(S) (10)D<、×、∪、∩的结合率 (RD<S)<T≡RD<(SD<T) 52,2查询优化的一般策略 (1)0优先 (2)使用频率高的属性建索引 (3)连接属性索引排序 (4)π、0同时进行 5)0+×→D< (6)公共子表达式 523代数优化算法 (1)生成查询语法树 (2)0移至树叶 (3)利用规则(3)合并投影 4)利用×、D<的结合率,调整×、D<的执行顺序 (5)将×与相关操作转换为D4 (6)在叶子节点添加T 524例子 5.3依赖于存取路径的规则优化 531选择操作 最初方法:顺序扫描 存取路径:索引(B+树),动态散列 启发式规则P122 532连接操作 (1)嵌套循环法
πL1∪L2(R F S) ≡πL1 (R) F πL2 (R) Attr(L1) Attr(R)，Attr(L2) Attr(S)，Attr(F) Attr(L1∪L2) (8)选择对∪、∩、－的分配率 σF(R∪S) ≡σF(R) ∪σF(S) (9)投影对∪的分配率. πL (R∪S) ≡πL (R) ∪πL (S) (10) 、×、∪、∩的结合率 (R S) T≡R (S T) 5.2.2 查询优化的一般策略 (1)σ优先 (2)使用频率高的属性建索引 (3)连接属性索引/排序 (4)π、σ同时进行 (5)σ+×→ (6)公共子表达式 5.2.3 代数优化算法 (1)生成查询语法树 (2)σ移至树叶 (3)利用规则(3)合并投影 (4)利用×、 的结合率，调整×、 的执行顺序 (5)将×与相关操作转换为 (6)在叶子节点添加π 5.2.4 例子 5.3 依赖于存取路径的规则优化 5.3.1 选择操作 最初方法：顺序扫描 存取路径：索引（B+树），动态散列 启发式规则 P122 5.3.2 连接操作 (1)嵌套循环法
顺序遍历,一一匹配算法:P123 物理块少的作为外关系 (2)利用索引,散列寻找匹配元组 减少IO次数 (3)排序归并法 按连接属性对关系排序 算法P125 (4)散列连接法 用散列函数将连接属性散列至文件中(桶 Bucket) 启发式规则P125 533投影操作 与0、π同时进行 重复值的消除:排序,散列 算法:P126 53集合操作 ×:嵌套循环 U∩-:发现共同元组 535组合操作 减少临时文件,尽可能同时执行操作 其他优化方式
顺序遍历，一一匹配 算法：P123 物理块少的作为外关系 (2)利用索引，散列寻找匹配元组 减少 I/O 次数 (3)排序归并法 按连接属性对关系排序 算法 P125 (4)散列连接法 用散列函数将连接属性散列至文件中（桶 Bucket） 启发式规则 P125 5.3.3 投影操作 与σ、π同时进行 重复值的消除：排序，散列 算法：P126 5.3.4 集合操作 ×：嵌套循环 ∪∩－:发现共同元组 5.3.5 组合操作 减少临时文件，尽可能同时执行操作 其他优化方式