第9章数据库查询优化9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3基于半联接的查询优化9.4基于枚举法的查询优化
第9章 数据库查询优化 9.1 关系数据库系统的查询处理 9.2 关系数据库系统的查询优化 9.3 基于半联接的查询优化 9.4 基于枚举法的查询优化
9.1关系数据库系统的套询处理查询语句+词法分析语法分析查询分析语义分析符合名转换安全性检查查询检查完整性检查数据字典查询树T代数优化查询优化物理优化执行策略！<查询执行代码生成执行代码！
9.1 关系数据库系统的查询处理
9.2关系数据库系统的套询优化·查询优化的必要性一查询优化极大地影响RDBMS的性能。·查询优化的可能性一关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义
9.2 关系数据库系统的查询优化 •查询优化的必要性 –查询优化极大地影响RDBMS的性能。 •查询优化的可能性 –关系数据语言的级别很高，使DBMS可 以从关系表达式中分析查询语义
9.2关系数据库系统的套询优化·用户不必考虑如何最好地表达查询以获得较好的效率·系统可以比用户程序的优化做得更好（1）优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息
9.2 关系数据库系统的查询优化 • 用户不必考虑如何最好地表达查询以获 得较好的效率 • 系统可以比用户程序的优化做得更好 (1) 优化器可以从数据字典中获取许多统计信息， 而用户程序则难以获得这些信息
9.2关系数据库系统的查询优化（2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。3优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。4）优化器中包括了很多复杂的优化技术
9.2 关系数据库系统的查询优化 (2)如果数据库的物理统计信息改变了，系统可以自 动对查询重新优化以选择相适应的执行计划。 在非关系系统中必须重写程序，而重写程序在实际 应用中往往是不太可能的。 (3)优化器可以考虑数百种不同的执行计划，而程序 员一般只能考虑有限的几种可能性。 (4)优化器中包括了很多复杂的优化技术
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代价[+ 内存代价] + 通信代价