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

6.2.2 查询优化一般策略 (1) 选择运算应尽早执行。 (2) 把投影运算和选择运算同时进行。 (3) 把投影操作与它前面或后面的一个双目运算结合起来。 (4) 执行连接运算之前进行预处理。 (5) 把笛卡儿积和其后的选择运算合并成为连接运算 (6) 存储公用子表达式。 6.2.3 关系代数表达式的优化算法 算法：关系表达式的优化 输入：一个关系表达式的语法树。 输出：优化的查询树。 （1）根据SQL语句生成初始查询树。 （2）分解选择运算 利用规则4把形如? F1 ∧F2 ∧ … ∧ Fn (E)变换为 ? F1 (? F2(… (? Fn(E))… )) （3）交换选择运算 通过交换选择运算，将其尽可能移到叶端. 对每一个选择，利用规则4～9尽可能把它移到树的叶端。 （4）交换投影运算 对每一个投影利用规则3，5，l0，11中的一般形式尽可能把它移向树的叶端。 （5）合并串接的选择和投影 以便能同时执行或在一次扫描中完成 利用规则3～5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。 尽管这种变换似乎违背“投影尽可能早做”的原则，但这样做效率更高。 （6）对内结点分组 把上述得到的语法树的内节点分组。 每一双目运算（×， ，∪，－）和它所有的直接祖先为一组（这些直接祖先是? ，π运算）。 如果其后代直到叶子全是单目运算，则也将它们并入该组，但当双目运算是笛卡尔积（×），而且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组。 （7）生成执行程序 生成一个程序，每组结点的计算是程序中的一步。 各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。 【例6.2】 对订单数据库有如下查询，求所有北京客户所订的全部商品名称。 SELECT pdName FROM Product，Customer，Order，OrderDetail WHERE Product.pdID = OrderDetail.pdID AND Customer.custID = Order.custID AND Order.orderID = OrderDetail.orderID AND Customer.custCity = 北京； 初始查询树 变换后的查询树 优化后的查询树 6.3 物理优化 物理优化 代数优化改变查询语句中操作的次序和组合，不涉及底层的存取路径 对于一个查询语句有许多存取方案，它们的执行效率不同， 仅仅进行代数优化是不够的 物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划 选择的方法： 基于规则的启发式优化 基于代价估算的优化 两者结合的优化方法 6.3.1 基于规则的优化方法 选择操作的优化规则 连接操作的优化规则 对于小关系，使用全表顺序扫描，即使选择列上有索引。 选择操作的优化规则: 1. 对于选择条件是主码＝值的查询 查询结果最多是一个元组，可以选择主码索引 一般的RDBMS会自动建立主码索引。 2. 对于选择条件是非主属性＝值的查询，并且选择列上有索引 要估算查询结果的元组数目 如果比例较小(10%)可以使用索引扫描方法 否则还是使用全表顺序扫描 对于大关系： 3. 对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引 要估算查询结果的元组数目 如果比例较小（10%）可以使用索引扫描方法 否则还是使用全表顺序扫描 4. 对于用AND连接的合取选择条件 如果有涉及这些属性的组合索引 优先采用组合索引扫描方法 如果某些属性上有一般的索引 则可以用索引扫描方法 否则使用全表顺序扫描。 5. 对于用OR连接的析取选择条件，一般使用全表顺序扫描 1. 如果2个表都已经按照连接属性排序 选用排序-合并方法 2. 如果一个表在连接属性上有索引 选用索引连接方法 3. 如果上面2个规则都不适用，其中一个表较小 选用Hash join方法 4. 最后可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的块数较少的表，作为外循环的表 。 连接操作的优化规则： 阿尔茨海默症防治相关知识埃及的金字塔有建造方法动画艾司洛尔在神经外科重症中的应用二级二班防溺水等安全教育 第6章 关系查询处理和查询优化 6.1 关系数据库系统的查询处理 6.1.1 查询优化的必要性（一个实例） 【例6.1】对教材预定数据库，查询“217”号教师预定的所有教材名称。 ? SELECT Book.bookname FROM Book，OrderDetail WHERE Book.bookID=OrderDetail.bookID AND OrderDe