第五章 查询处理与优化 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)连接／笛卡儿积的交换率 RS≡SR R×S≡S×R (6)选择对连接／笛卡儿积的分配率. σF(RS) ≡ (σF(R))S Attr(F)  Attr(R) σF1∧ F2 (RS) ≡σF1(R) σF2(S) Attr(F1)  Attr(R) (7)投影对连接／笛卡儿积的分配率. πL1∪L2(RS) ≡πL1 (R) π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) 、×、∪、∩的结合率 (RS)T≡R(ST) 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)利用索引，散列寻找匹配元组 减少I/O次数 (3)排序归并法 按连接属性对关系排序 算法P125 (4)散列连接法 用散列函数将连接属性散列至文件中（桶Bucket） 启发式规则 P125 5.3.3投影操作 与σ、π同时进行 重复值的消除：排序，散列 算法：P126 5.3.4集合操作 ×：嵌套循环 ∪∩－:发现共同元组 5.3.5组合操作 减少临时文件，尽可能同时执行操作 其他优化方式