[高级数据库技术6.ppt

UNIT five查询处理 思考几个问题 数据库语言是非过程的语言，而最终这些非过程的语句都将转换为过程性的程序。DBMS是如何进行这种转换的？ 在转换的过程中，有必要进行查询优化吗？ DBMS一定会找到一个最优的执行计划吗？DBMS依靠什么信息找到最优执行计划？所谓的最优是指哪些方面最优？查询优化占用很多系统资源吗？我能要求系统不做查询优化处理吗？ 思考几个问题 对于下面这些等价的查询，DBMS使用同样的执行计划吗？ 本 讲 主 要 目 标 学完本讲后，你应该能够了解： 查询优化的可能性、必要性； 查询处理的过程最终将一个非过程的查询请求转换成一个完全过程性的查询执行计划； 数据库系统中查询执行引擎为每一个关系操作的实现提供多种物理实现方法； 查询优化的目标是找到一个相当好的查询执行计划，使得查询请求的响应时间最小； 三类查询优化器的基本原理 ：穷尽（精确）优化方法、两段优化方法和启发式方法 一．查询优化的可能性 二．查询优化的必要性 三．查询处理的过程 四．查询优化的目标 五．查询优化的基本原理 查询优化的 可能性 查询优化的可能性 1．查询优化的可能性 ● 关系数据库语言的非过程性与查询执行计划的过程性之间的差别； 查询执行计划 ---- 用户的查询请求在数据库系统中的具体执行步骤。 关系数据库的查询操作一般用非过程性的语言描述，查询语句本身重在表达查找条件和结果关系的组成，而把查找的实施过程以及查找策略的选择交给关系数据库管理系统负责。 ● 优化器可从DD中获取很多有用的统计信息。 查询优化的可能性 2．实例 例1 求选修了‘C2’号课程的学生姓名。 用SQL表达： SELECT S.SN FROM S, SC WHERE S.S# = SC.S# AND SC.C# = ‘C2’； 查询优化的 必要性 查询优化的必要性 1．查询优化的优点 ● 用户表达查询时不必考虑效率问题 ● 在寻找有效查询执行计划方面，系统比用户程序做得更好 2. 查询优化的必要性 同一查询请求的不同查询执行计划之间的代价差异巨大。 查询优化的必要性 3．不同查询执行计划的执行时间分析 例1的三种情况： Q1 =πSN(σs.s# = sc.s# ∧ sc.c# = ‘c2’(S×SC)) Q2 =πSN(σsc.c# = ‘c2’(S ? SC)) Q3 =πSN(S ? σsc.c# = ‘c2’(SC)) 查询处理的 过程 查询处理的过程 1．查询处理的过程 RDBMS处理用户查询请求的过程是：接到用高级查询语言书写的查询请求后，首先进行词法分析和语法分析，并确认语义正确后，产生查询的内部表示（通常为查询树或查询图），然后由RDBMS选定一个执行策略（包括操作的执行顺序，如何访问外部文件，存储中间结果），接着由查询执行引擎(query execution engine)负责产生执行查询的代码，交给运行时数据库处理器执行，最终产生查询结果或报告出错信息。 查询处理的过程 查询处理的过程 2．处理过程中的功能模块 ● 词法分析、语法分析、语义确认 ● 查询优化器 ● 查询执行引擎 ● 运行时数据库处理器 查询处理的过程 （1）查询优化器（ query optimizer） 功能：负责产生最有效的查询执行计划（QEP） ● 逻辑转换部分：对于一个语法树，根据关系代数等价变换规则，得到所有的等价的关系代数表达式； ● 物理转换部分：对于每一个关系代数表达式，根据查询引擎提供的物理操作，找出所有可能的查询执行计划 ● 比较和查找：根据代价估计函数，估计每一个查询执行计划的代价，并从中找出代价最小的查询执行计划。 查询处理的过程 （1）查询优化器（ query optimizer） 查询处理的过程 （2）查询执行引擎(query execution engine) 功能： ● 查询执行引擎为每一个关系操作的实现提供多种物理实现方法，如选择操作有二种可能的物理操作：顺序扫描和索引扫描；如连接操作有三种可能的物理操作：嵌套循环连接、合并连接和散列连接。当然查询执行引擎还可以提供更多的物理实现方法。每一种物理实现方法利用不同的存取路径（如索引、数据的存储分布、元组的排序等） ● 负责产生执行查询的代码 查询处理的过程 嵌套循环连接（Nested-loop Join） 将一个表用作外部输入表，另一个表用作内部输入表。外部循环逐行消耗外部输入表。内部循环对于每个外部行，在内部输入表中有哪些信誉好的足球投注网站匹配行。最简单的情况是，有哪些信誉好的足球投注网站时扫描整个表，则称为单纯嵌套循环连