ch06查询处理和优化new.pptVIP

* * * 6.4 代价估算优化 ②利用索引或散列寻找匹配元组法 若内关系上有索引或散列(簇集)，则可利用这样的存取路径来代替顺序扫描。 设关系S的B属性列上有(单表)索引簇集，且： nR—关系R的元组数；nS—关系S的元组数；bR—关系R的物理块数；bS—关系S的物理块数；PS—关系S的块因子（即一块中元组数）； LB—索引B树的深度；NB—属性B在关系S中取多少不同的值； 完成连接的相对代价：C = bR + (nR ×( LB + ( nS / NB)/ PS)) 属性B每种不同值在关系S中所对应的平均元组数 关系S中满足连接条件(S.B=R.A)的元组所占数据块数 关系S中利用索引簇集每次匹配的I/O块数 * 6.4 代价估算优化 ③排序归并法（Sort-merge） 完成连接的相对代价：C = CR排序+ C S排序+ bR + bS ④散列连接法（Hash Join） * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 第6章 查询处理和优化 2012. 03 * 目录 Contents 6.1 概述 6.2 代数优化 6.3 依赖于存取路径的规则优化 6.4 代价估算优化 * 6.1 概述 一、查询与查询处理 查询(Query)：是数据库的最基本、最常用、最复杂的操作。包括： 直接的SELECT： e.g. SELECT…FROM…WHERE…( SELECT… )…; 间接的SELECT： e.g. INSERT INTO…SELECT…; DELETE FROM…WHERE…( SELECT… )…; UPDATE…SET…WHERE…( SELECT… )…; CREATE VIEW…AS SELECT…; * 6.1 概述 一、查询与查询处理(cont.) 查询处理(Query Processing)：从DBMS接受一个查询请求到返回查询结果的处理过程。包括以下步骤： 词法、语法分析 SELECT操作转换为语法树； 权限检查 检查用户是否对有关模式对象有相应的访问权限； 语义分析与查询优化 形成高效／优化的执行计划(execution plan)； 执行查询并返回结果 按执行计划执行查询，并返回结果。 可见，查询处理的关键／核心步骤是查询优化。 * 6.1 概述 二、查询优化及其方法 查询优化(Query Optimization): 为一个查询确定一个效率（较）高的执行计划（即：操作的先后顺序，表数据的I/O方法，等）。 * 6.1 概述 二、查询优化及其方法 (cont.) DBMS为何要进行查询优化? 为了提高数据库的性能 虽然影响数据库性能的因素有很多（如：操作的执行效率、DB的设计质量、通讯开销、硬件性能，…），但在相同环境下，执行效率是关键因素。 为了方便用户 DBMS有了优化机制后，用户可随意表达查询要求，而不必考虑效率问题。这是使用高度非过程化、说明性语言（SQL）的关系数据库环境所必须的。 由系统来“优化”比由用户来“优化”更有效 DBMS可充分利用数据字典（DD）中保存的各种参数进行优化，这比网状／层次数据库系统中由用户来写“优化的”DML语句更为有效。 * 6.1 概述 二、查询优化及其方法 (cont.) 查询优化的方法 两个层次 代数层：将查询所对应的关系代数表达式以抽象的语法树来表示，然后等价变换之，以期减小查询过程中的中间结果大小。 物理层：选择高效的存取路径存取表数据，以期提高磁盘I/O的效率。 两种策略 基于规则（Rule）：运用启发式规则为查询确定一个理论上认为“最优的”执行计划。 基于代价(Cost)估算：为查询确定几个理论上认为“较优的”执行计划，然后根据数据字典中的参数分别估算它们的执行代价(时间开销)，选择代价最小者作为“最优的”执行计划。 * 6.1 概述 二、查询优化及其方法 (cont.) 查询优化的方法(cont.) 实际系统中往往综合运用以上两种策略，在两个层次上进行优化。 DBMS中承担优化工作的部分称优化器(Optimizer)。 一般地，优化器的工作对用户是透明的。 但有的系统允许用户询问优化器为某个查询选择的执行计划(e.g. Oracle中通过EXPLAIN PLAN命令)；还允许用户建议优化器如何优化一个查询(e.g. Oracle中通过在SELECT中插入优化提示)。 * 目录 Contents 6.1 概述 6.2 代数优化 6.3 依赖于存取路径的规则优化 6.4 代价估算优化 * 6.2 代数优化 目标 代数优化是对查询进行等效变换，尽量减小查询中间结果的大