9.2关系数据库系统的询优化查询优化的总目标选择有效策略，求得给定关系表达式的值实际系统的查询优化步骤1.将查询转换成某种内部表示，通常是语法树2.根据一定的等价变换规则把语法树转换成标准（优化）形式
9.2 关系数据库系统的查询优化 查询优化的总目标 选择有效策略，求得给定关系表达式的值 实际系统的查询优化步骤 1. 将查询转换成某种内部表示，通常是语法树 2. 根据一定的等价变换规则把语法树转换成标准 （优化）形式
查询树例：有查询Q,：查询北部地区（AREA="North'）所属部门发出订单的供应商号。这里涉及两个全局关系DeptD#DNAME，MGTRSSNAREA）和Sp(S#，P#，D#，QUAN），SQL表达式为：Select S#FromDept,SpWhereSp·D#=Dept.·D#AndAREA='North'其相应的代数表达式为：(Sp 00 Dept)元s#AREA=North'D#=D#其相应的查询树如下：元s#6 AREA-'Nouth'显然，边为E,（oo，Sp）D#=D#8时，则Sp是非叶节点80的分量。D#-D#SpDept
例：有查询Q1：查询北部地区（AREA=‘North’）所属部门发出订单的供应商号。这里 涉及两个全局关系Dept(D#,DNAME,MGTRSSN,AREA)和Sp(S#,P#,D#,QUAN)，SQL表达 式为： Select S＃ From Dept, Sp Where Sp•D＃=Dept.•D＃ And AREA=‘North’; 其相应的代数表达式为： πS#σAREA=‘North’（Sp ∞ Dept） D＃=D＃ 其相应的查询树如下： πs# бAREA=‘Nouth’ ∞ D＃=D＃ Sp Dept 查询树 显然，边为 E1（∞ ，Sp ） D＃=D＃ 时，则Sp是非叶节点 ∞ 的分量
查询表达式的等价性[例]：对关系Emp,有如下SQL查询表达式Select ENAME,DNOFromEmp(4-1)Where DNO=‘15'其相应的代数操作表达式为：(4-2)元 ENAME, DNO （α DNO=15, Emp)或Emp)(4-3) DNO=15'(元 ENAME, DNO本例表示了不同的操作顺序仍可获得相同的结果。这就是等价的概念。[定义4.2]：两个查询表达式E1和E2是等价的，如果其查询的结果是相同的，记为E1三E2
查询表达式的等价性 [例]：对关系 Emp,有如下SQL查询表达式 Select ENAME,DNO From Emp Where DNO=‘15’; （4-1） 其相应的代数操作表达式为： πENAME，DNO（σDNO=’15’ Emp） （4-2） 或 σDNO=‘15’（πENAME，DNO Emp） （4-3） 本例表示了不同的操作顺序仍可获得相同的结果。这就是等价的概念。 [定义4.2]：两个查询表达式 E1 和 E2 是等价的，如果其 查询的结果是相同的，记为 E1 ≡ E2
9.2关系数据库系统的询优化3.选择低层的操作算法查询树可以理解为全局查询树对于语法树中的每一个操作根据等价定义，可用三种方式描述查询：·计算各种执行算法的执行代价SOL表达式（查询语句）·选择代价小的执行算法4.生成查询计划（查询执行方案）代数表达式·查询计划是由一系列内部操作组成的查询树
9.2 关系数据库系统的查询优化 3. 选择低层的操作算法 对于语法树中的每一个操作 • 计算各种执行算法的执行代价 • 选择代价小的执行算法 4. 生成查询计划(查询执行方案) • 查询计划是由一系列内部操作组 成的 查询树可以理解为全局查 询树 根据等价定义，可用三种 方式描述查询： SQL表达式（查询语句） 代数表达式 查询树
代价模型·集中式数据库·单用户系统总代价=/O代价+CPU代价·多用户系统总代价=/O代价+CPU代价+内存代价·分布式数据库总代价=VO代价+CPU代价[+内存代价】+通信代价
代价模型 • 集中式数据库 •单用户系统 总代价 = I/O代价 + CPU代价 •多用户系统 总代价 = I/O代价 + CPU代价 + 内存代价 • 分布式数据库 总代价 = I/O代价 + CPU代价[+ 内存代价] + 通信代价