第九章-关系查询处理和查询优化.ppt

An Introduction to Database System 某些选择运算同它前面要执行的笛卡尔积结合起来成为连接运算，连接运算比产生笛卡尔后进行选择运算要快的多 提取公共子表达式：可把满足公共子表达式的关系（不太大的情况下）读入内存以提高查询效率。 An Introduction to Database System 遵循启发式规则，运用等价变换规则优化关系表达式的算法： 算法：关系代数表达式的优化 算法输入：依据一个关系表达式的查询树。 算法输出：优化的查询树 方法： （1）分解选择运算 利用规则4把形如бF1 ∧F2 ∧ … ∧ Fn (E)变换为 бF1 (бF2(… (бFn(E))… )) ，为（2）做准备。 An Introduction to Database System 关系代数表达式的优化算法 (续) （2）对每一个选择运算，利用规则4～8尽可能把它移到树的叶端。（选择优先） （3）对每一个投影运算，利用规则3，5，l0，11中的一般形式尽可能把它移向树的叶端。（投影优先） 选择和投影运算均能减少中间结果，具体哪个更优先，取决于具体关系中行和列哪个数据量更大。 An Introduction to Database System （4）利用等价变化3-5，合并串接的选择运算成一个选择运算和合并串接的投影运算成一个投影运算，以便能在一次扫描中完成运算，如： бA3 (бA5(E) )? бA3 (E) π A1(πA1,A2(E))?π A1(E) An Introduction to Database System 关系代数表达式的优化算法 (续) （5）对内结点（除叶结点外的所有结点）分组： 每一双目运算(×， ，∪，-)和它所有的直接祖先为一组(这些直接祖先是б，π运算)，如下例第1，3组；如果其后代直到叶子全是单目运算，则也将它们并入该组。如下例第1组。 当双目运算是笛卡尔积(×)，而且其后的选择不能与它结合为等值连接时，可把这些单目运算单独分为一组。 如下例中注释部分。 每组结点对应计算程序中的一步，各步程序的顺序可任意，但任何一组的计算必须在它的父代组之前计算。如下例中第1和第2组结果必须在第3组计算之间产生。 An Introduction to Database System 分组实例：查询男同学选课学分大于4分的姓名和课程名 student course sc б б π 第1组 π 第3组 第2组 π 若为“X”，则下面可分成两组 ssex=‘男’ Sno,cno sname,cno Ccredit4 Sname,cname π sno,sname,ssex An Introduction to Database System 9.4 物理优化 物理优化指存取路径和底层操作算法的选择，主要研究根据查询的不同特点，选择操作和连接操作中对9.1.2中各种算法的选择。 有基于启发式、基于代价估算和两者结合的优化方法。 An Introduction to Database System 基于启发式的优化： 一.选择操作的优化规则 对于小关系，不论是否有索引，均使用全表扫描。下面规则则对大关系而言。 包含主码等值的查询，一定使用主码索引。 包含非主属性等值查询，若有关于该非主属性的索引，则估算查询结果的元组数量，与整个元组数量比例大的话，使用全表扫描，否则使用索引扫描。 An Introduction to Database System 对and连接的条件，若有相应的组合索引，则使用索引扫描；若部分有索引，则先使用索引扫描，选出符合部分条件的元组，在其中再选出符合其他条件的元组。 对or连接的条件，一般使用全表扫描。例如关于A,B有索引，（not A） or （not B）可优化为not (A and B)，事实上一些DBMS也会作此优化(前者若使用索引，必须两次全表扫描，而后者一次全表，一次在前一次结果上再扫描)。 …… An Introduction to Database System 二.连接操作的优化规则 连接属性均排序，使用排序-合并方法 仅一个表的连接属性有索引，使用索引连接方法。 上述条件均不满足，若一个表较小，则可以选用Hash join方法 嵌套循环方法不需要任何前提条件，但较小的表的扫描应作为外循环，可减少读块的次数。（极端情况下，小表只要读一次） An Introduction to Database System 基于代价估算的优化 根据数据库的状态计算各种操作算法的执行代价，选择代价最小的算法。 执行代价的计算方法： 在数据字典中存放优化器所需要的统计信息，如表的元组数，元组长度、列值个数、最大、最小值、列上是否