关系查询处理和查询优化关系查询处理和查询优化.ppt

第九章 关系查询处理和查询优化 查询处理与优化 如何以有效的方式处理用户查询是RDBMS有效实现的关键问题之一 数据库的更新运算要么是简单的（如插入一个元组），要么与一个复杂的更新条件相关联（如删除满足某些条件的元组） 复杂的更新首先需要找到要更新的元组，然后才能进行更新。因此，只有能够有效地处理查询，才能有效地实现更新 查询处理的中心任务是把使用诸如SQL这样的说明性语言表达的用户查询转换成一系列能够在物理文件上执行的操作，并执行这些操作得到查询结果 查询优化是查询处理的关键步骤，它从众多的查询执行方案中选择最有效的执行方案 关系查询处理和查询优化 9.1 关系数据库系统的查询处理 9.2 关系数据库系统的查询优化 9.3 代数优化 9.4 物理优化 9.5 小结 9.1 关系数据库系统的查询处理 9.1.1 查询处理步骤 9.1.2 实现查询操作的算法示例 9.1.1 查询处理步骤 RDBMS查询处理过程 查询分析 查询检查 查询优化 查询执行 9.1.1 查询处理步骤（续） 查询分析： 进行词法分析、语法分析和语义分析 词法分析 从查询语句中识别出语言符号，如SQL的保留字、关系名、属性名和各种运算符等其他符号 语法分析 检查用户查询语句的语法格式，确保查询语句语法上的正确性 语义分析 可以与语法分析同时进行，将查询转换成更适合进一步处理的内部表示 9.1.1 查询处理步骤（续） 查询检查 根据数据字典对合法的查询语句进行语义检查 根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查 检查通过后把SQL查询语句转换成等价的关系代数 RDBMS一般都用查询树，也称语法分析树，来表示扩展的关系代数表达式 把数据库对象的外部名称转换成内部表示 9.1.1 查询处理步骤（续） 查询检查——查询树 例9.1 找出提供了P001号零件的供应商名称 SELECT Sname FROM Suppliers, SP WHERE Suppliers.Sno=SP.Sno AND Pno=‘P001’; 转换成下图9.2所示的语法树，或者转换成如下关系代数表达式： Q1：πSname(?Suppliers.Sno=SP.Sno? Pno=P001 (Suppliers×SP)) 9.1.1 查询处理步骤（续） 查询优化 一个给定的查询有多种可能的执行策略 例如，例9.1的查询也可以用如下关系代数表达式计算： Q2：πSname(? Pno=P001 (Suppliers SP)) Q3：πSname(Suppliers ?Pno=P001 (SP)) 每个基本运算也可以有多种不同的实现算法 一个查询执行计划包括计算查询的关系代数表达式和其中每个基本运算的实现算法 查询优化就是从多种可能的查询执行方案中选择一种最有效执行的查询执行计划的过程 对于相同的查询，不同的查询执行计划的时间开销可能相差几个数量级 例如，使用Q1计算例9.1的查询的I/O开销大约是使用Q3的2000倍 9.1.1 查询处理步骤（续） 按照优化层次分为代数优化和物理优化 代数优化vs物理优化 代数优化：找到一个与给定的查询表达式等价、但执行起来更加有效的关系代数表达式 物理优化：为关系代数表达式选择一个详细的策略，包括为特定的操作选择可用的算法（底层操作算法），选择可用的索引（存取路径）等 基于规则的优化vs基于代价的优化 基于规则的优化：根据某些启发式规则，通过关系代数的等价变换，得到更有效的关系代数表达式；或者根据某些启发式规则选择实现基本运算的算法 基于代价的优化：利用元数据中的统计信息，估计不同的查询执行计划的开销，从中选择最优方案 9.1.1 查询处理步骤（续） 查询执行 执行引擎依据优化器得到的查询执行计划生成执行查询计划的代码，执行该代码产生查询结果，并以适当的形式提交用户 查询执行之前还要进行安全性检查，确保执行查询的用户必须具有相应的访问权限。任何违反安全性限制的查询都将被拒绝 对于数据库的更新操作，除了安全性检查之外，还需要进行完整性检查 9.1.1 查询处理步骤（续） 查询代价的估计 为了优化查询，优化器必须知道每个基本运算的代价，进而估计查询执行计划的代价 精确地估计代价是困难的，但是粗略的估计是可能的，并且这种粗略估计可以很好地反映不同查询计划的相对优劣 查询代价包括CPU代价、I/O代价和内存代价 在分布式数据库系统或并行数据库系统中，查询代价还包括通信代价 本章，我们只考虑集中式系统 内存代价 用查询处理所需的内存量度量 最坏的情况：内存缓冲区只能容纳数目不多的数据块——大约每个关系一块或几块 9.1.1 查询处理步骤（续） CPU代价 用查询所需的CPU时间度量