第6章 查询优化.ppt

《第6章 查询优化.ppt》由会员分享，可在线阅读，更多相关《第6章 查询优化.ppt（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6章章 查询优化查询优化Silberschatz,Korth and Sudarshan14.2Database System Concepts 3rd Edition主要内容主要内容n概述概述n用于代价估算的统计信息用于代价估算的统计信息n关系代数表达式的转换关系代数表达式的转换n基于代价的优化算法基于代价的优化算法n物化视图与视图维护物化视图与视图维护Silberschatz,Korth and Sudarshan14.3Database System Concepts 3rd Edition概述概述n一个给定查询有多种可选择的求值方法一个给定查询有多种可选择的求值方法等价表达式等价表

2、达式一个操作有若干不同算法一个操作有若干不同算法(Chapter 5)n一个查询求值方法的好坏带来的代价差别可能是巨大的一个查询求值方法的好坏带来的代价差别可能是巨大的n例如例如:执行执行r X s 后续选择后续选择r.A=s.B 比执行一个同样条比执行一个同样条件的连接慢得多件的连接慢得多n需要估算操作的代价需要估算操作的代价依赖于数据库维护的统计信息依赖于数据库维护的统计信息例如元组数例如元组数,连接属性的不同值的数目连接属性的不同值的数目,等等等等需要对中间结果估算统计信息以便对复杂表达式计算代价需要对中间结果估算统计信息以便对复杂表达式计算代价Silberschatz,Korth an

3、d Sudarshan14.4Database System Concepts 3rd Edition概述概述Silberschatz,Korth and Sudarshan14.5Database System Concepts 3rd Edition概述概述n对一个表达式的查询求值方案的生成涉及几个步对一个表达式的查询求值方案的生成涉及几个步骤骤:1.生成逻辑上等价的表达式生成逻辑上等价的表达式利用等价规则将一个表达式转换成另一个等价的表利用等价规则将一个表达式转换成另一个等价的表达式达式2.注解注解(Annotate)结果表达式以得到其他查询计划结果表达式以得到其他查询计划3.基于估算代

4、价选择最廉价的计划基于估算代价选择最廉价的计划n整个过程称为基于代价的优化整个过程称为基于代价的优化Silberschatz,Korth and Sudarshan14.6Database System Concepts 3rd EditionSQL ConstructsnSECLECT(DISTINCT)nFROM nWHERE nGROUP BY nHAVING nORDER BY Silberschatz,Korth and Sudarshan14.7Database System Concepts 3rd EditionSQL SemanticsnTake Cartesian prod

5、uct of FROM tablesnProject only those referenced columnsnWHERE:apply all filters in WHEREnGROUP BY:form groups on resultsnHAVING:apply filter to groups nORDER BY:make sure results in right ordernDISTINCT:remove duplicatesnQ:Is this“operational semantics”efficient?nDifferent plans:mainly different in

6、 the first threeSilberschatz,Korth and Sudarshan14.8Database System Concepts 3rd EditionOptimization:Different StrategiesnOptimal approach:Enumerate(枚举枚举)each possible planMeasure its performance by running itPick the fastest onenHeuristics approach:fixed heuristics all the way through plan construc

7、tione.g.:always nested loop joins,indexed relation as innere.g.:order relations from smallest to biggestSilberschatz,Korth and Sudarshan14.9Database System Concepts 3rd EditionCost-based OptimizationnPlan space:what is the space of query plans?nCost estimation:how to estimate the cost,without execut

8、ing each?nSearch algorithm:how to search the space,as guided by cost estimatesSilberschatz,Korth and Sudarshan14.10Database System Concepts 3rd EditionSpace of Query PlansnSelections:algorithms:sequential,index scannJoins:algorithms:nested-loop,sort merge,hashnOrdering/Grouping:can an“interesting or

9、der”be produced by join/selections?algorithm:sorting,hash-basednThey interleave with each other!Silberschatz,Korth and Sudarshan14.11Database System Concepts 3rd EditionHuge Space!Assumptions to HelpnTypical assumptions to help reduce the space:Projections:pushed down to reduce#of columnsSelections:

10、pushed down to reduce#of rowsJoins:left-deep joins avoid Cartesian products;delay it in the planQ:how to avoid Cartesian products?May miss an optimal plan!Silberschatz,Korth and Sudarshan14.12Database System Concepts 3rd EditionCost/Size EstimationnAccurate relativelygoal is to compare plans,not to

11、predict exact costmore of an art than an exact sciencenEach operator:input size,cost,output sizeestimate cost based on input sizeestimate output size(for next operator)or selectivityselectivity=ratio of output to inputSilberschatz,Korth and Sudarshan14.13Database System Concepts 3rd EditionCost Esti

12、mationnInput:simple DB statistics#of tuples&disk pages#of distinct values per column statistics updated periodicallynAssumption of attribute/predicate independenceWhen no estimate available,use magic numbernNew/Alternative approaches:sampling,histogram of DBSilberschatz,Korth and Sudarshan14.14Datab

13、ase System Concepts 3rd EditionSelectivity Factors:Range SelectionnWhat is assumed in these formulas?ncolumn value1:F=(maxValue-value1)/rangeOfValuencolumn in value1:value2F=(value2-value1)/rangeOfValueSilberschatz,Korth and Sudarshan14.15Database System Concepts 3rd EditionSearch the Plan SpacenBas

14、eline:exhaustive searchenumerate all combinations,and compare their costnSearch method parameters:plan tree development:construction:bottom-up,top-downmodification:improve a somehow-constructed treealgorithms:heuristic selections:make choices based on heuristicsbranch and bound:search bounded by the

15、 current best treehill climbing:find“nearby”plans with lowest costdynamic programming:construction by greedy selectionsSilberschatz,Korth and Sudarshan14.16Database System Concepts 3rd EditionWhat You Should KnownQuery optimization is critical for any commercial DBMSgood/bad can be orders of magnitu

16、denThe 3 components of the System-R style optimizationPlan space definitionCost estimationSearch algorithmhuge number of alternative,semantically equivalent plansnIdeal goal:map a declarative query to the most efficient plan nConventional wisdom:avoid bad plansnState of the art:industry:most optimiz

17、ers are System-R styleacademic:always a core database research topicSilberschatz,Korth and Sudarshan14.17Database System Concepts 3rd Edition用于代价估算的统计信息用于代价估算的统计信息(回顾回顾)(10/14)nnr:关系关系r 中的元组个数中的元组个数nbr:包含包含r 中元组的块数中元组的块数nsr:r 中元组的大小中元组的大小nfr:r 的块因子的块因子 即即,能放入一块之中的能放入一块之中的r 的元组数的元组数nV(A,r):r 中出现的中出现的

18、A属性上的不同值的个数属性上的不同值的个数;等于等于A(r)的大小的大小nSC(A,r):关系关系r 中属性中属性A的的选择基数选择基数,满足满足A上等值条件上等值条件的平均记录数的平均记录数n若若r 中元组在文件中中元组在文件中连续存放连续存放,则则:Silberschatz,Korth and Sudarshan14.18Database System Concepts 3rd Edition关于索引的目录信息关于索引的目录信息(回顾回顾)nfi:索引索引i 的内节点的平均扇出的内节点的平均扇出,适用于树适用于树结构索引结构索引,如如B+树树nHTi:索引索引i 的层数的层数 即高度即高度

19、对于关系对于关系r上上A 属性的平衡树索引属性的平衡树索引(如如B+-树树)HTi=logfi(V(A,r)n对于散列索引对于散列索引,HTi 为为1nLBi:索引索引i 的底层索引块数的底层索引块数 即索引叶即索引叶子层的块数子层的块数Silberschatz,Korth and Sudarshan14.19Database System Concepts 3rd Edition查询代价的度量查询代价的度量(回顾回顾)n典型地典型地,磁盘存取是决定性的代价磁盘存取是决定性的代价,也相也相对容易估算对容易估算n来自磁盘的块传送次数被用作求值的实来自磁盘的块传送次数被用作求值的实际代价的度量际代

20、价的度量n假设所有块传送都具有相同代价假设所有块传送都具有相同代价实际的优化器不作此假设实际的优化器不作此假设,并区分顺序与随并区分顺序与随机磁盘存取机磁盘存取n不包括写输出到磁盘的代价不包括写输出到磁盘的代价n记算法记算法A的代价估算为的代价估算为EASilberschatz,Korth and Sudarshan14.20Database System Concepts 3rd Edition统计信息例统计信息例nfaccount=20 (一块可放入account 的20个元组)nV(branch-name,account)=50 (50个分行)nV(balance,account)=50

21、0 (500 个不同的balance 值)naccount =10000 (account 有10,000条元组)n假设account 上存在下列索引:属性branch-name上的主B+-树索引属性balance上的辅助B+-树索引Silberschatz,Korth and Sudarshan14.21Database System Concepts 3rd Edition选择的大小估算选择的大小估算n等值选择等值选择 A=v(r)SC(A,r):满足选择的记录数满足选择的记录数 SC(A,r)/fr :这些记录将占用的块数这些记录将占用的块数二分搜索的代价估算为二分搜索的代价估算为键属性

22、上的等值条件键属性上的等值条件:SC(A,r)=1Silberschatz,Korth and Sudarshan14.22Database System Concepts 3rd Edition选择的大小估算选择的大小估算n涉及比较的选择涉及比较的选择形如形如 A V(r)的选择的选择令令c 表示满足条件的估算元组数表示满足条件的估算元组数若若 min(A,r)和和 max(A,r)在目录中可得在目录中可得c=0 if v min(A,r)c=若没有统计信息若没有统计信息,c 可假设为可假设为 nr/2 A V(r)的情形是对称的的情形是对称的Silberschatz,Korth and S

23、udarshan14.23Database System Concepts 3rd Edition复杂选择的实现复杂选择的实现n条件条件 I 的的选择度选择度是关系是关系r 中一条元组满足中一条元组满足 I 的概率的概率,如果如果si 是是r 中中满足的元组数满足的元组数,则则 i 的选择度为的选择度为si/nrn合取合取:1 2.n(r).结果中元组数的估算值为:n析取析取:1 2.n(r).元组数的估算值为:n否定否定:(r).元组数的估算值为:nr size(r)Silberschatz,Korth and Sudarshan14.24Database System Concepts 3

24、rd Edition连接的大小的估算连接的大小的估算n卡氏积卡氏积 r x s 包含包含 nr.ns 元组元组,每个元组占用每个元组占用sr+ss 字字节节n若若 R S=,则则 r s 等同于等同于 r x sn若若 R S 是是R 的键的键,则则s 的一条元组将与的一条元组将与r 的最多一条的最多一条元组连接元组连接n因此因此,r s 中的元组数不大于中的元组数不大于s 中的元组数中的元组数n若若 R S 在在S 中是引用中是引用R 的外键的外键,则则r s中的元组数中的元组数正好等于正好等于s中的元组数中的元组数R S 是引用是引用S 的外键的情形是对称的的外键的情形是对称的n在查询例在

25、查询例depositor customer 中中,depositor 中的中的customer-name 是是customer 的外键的外键n 因此因此,结果具有结果具有 ndepositor 条元组条元组,即即 5000Silberschatz,Korth and Sudarshan14.25Database System Concepts 3rd Edition连接操作连接操作:例子例子n连续用例连续用例:depositor customern连接例的目录信息连接例的目录信息:ncustomer=10,000fcustomer =25,这意味着这意味着bcustomer=10000/25=

26、400ndepositor=5000.fdepositor =50,这意味着这意味着bdepositor=5000/50=100V(customer-name,depositor)=2500,这意味着每个顾客平均有这意味着每个顾客平均有两个两个depositor还假设还假设depositor 中的中的customer-name是是customer 上的外键上的外键Silberschatz,Korth and Sudarshan14.26Database System Concepts 3rd Edition连接的大小的估算连接的大小的估算n若若 R S=A 不是不是R 或或S的键的键n如果我们

27、假设如果我们假设R 中每个元组中每个元组t 都在都在R S中产成元组中产成元组,则则R S中的中的元组数估算为元组数估算为:n若正好相反若正好相反,估算值为估算值为:n这两个估算值的较小者可能更准确这两个估算值的较小者可能更准确Silberschatz,Korth and Sudarshan14.27Database System Concepts 3rd Edition连接的大小的估算连接的大小的估算n例例:不利用有关外键的信息计算不利用有关外键的信息计算 depositor customer 的大小估算的大小估算:V(customer-name,depositor)=2500,且且V(cu

28、stomer-name,customer)=10000两个估算为两个估算为 5000*10000/2500=20,000 及及 5000*10000/10000=5000我们选择其中的较小估算我们选择其中的较小估算,在本情形下等于我们以前利在本情形下等于我们以前利用外键的计算结果用外键的计算结果Silberschatz,Korth and Sudarshan14.28Database System Concepts 3rd Edition其他操作的大小估算其他操作的大小估算n投影投影:估算大小估算大小 A(r)=V(A,r)n聚合聚合:估算大小估算大小Ag gF(r)=V(A,r)n集合运算集

29、合运算 对于同一关系上选择的并对于同一关系上选择的并/交交:重写并利用选择的大小估算重写并利用选择的大小估算例如例如 1(r)2(r)可重写为可重写为 1v 2(r)对于在不同关系上的操作对于在不同关系上的操作:r s 的估算大小的估算大小=r 的大小的大小+s 的大小的大小r s 的估算大小的估算大小=r 的大小与的大小与s 的大小之最小者的大小之最小者r s 的估算大小的估算大小=r上面这三种估算都可能不精确上面这三种估算都可能不精确,但提供了大小的上界但提供了大小的上界Silberschatz,Korth and Sudarshan14.29Database System Concept

30、s 3rd Edition其他操作的大小估算其他操作的大小估算n外连接外连接:r s 的估算大小的估算大小=r s 的大小的大小+r 的大小的大小右外连接的情形是对称的右外连接的情形是对称的r s的估算大小的估算大小=r s 的大小的大小+r 的大小的大小+s 的大小的大小Silberschatz,Korth and Sudarshan14.30Database System Concepts 3rd Edition不同值个数的估算不同值个数的估算选择选择:(r)n若若 强制强制A 取一个特定值取一个特定值(e.g.,A=3):V(A,(r)=1n若若 强制强制A 取一个特定集合中的某个值取一

31、个特定集合中的某个值(e.g.,(A=1 V A=3 V A=4):V(A,(r)=指定值的个数指定值的个数n若选择条件若选择条件 形如形如 A op v,其中其中op 为比较运算符为比较运算符(e.g.,A 1000 (branch (account depositor)n利用连接结合性(Rule 6a)的转换:customer-name(branch-city=“Brooklyn”balance 1000 (branch (account)depositor)n第二种形式提供了应用“尽早执行选择”规则的机会,导致子表达式 branch-city=“Brooklyn”(branch)bala

32、nce 1000(account)n因此一系列的转换是有用的Silberschatz,Korth and Sudarshan14.42Database System Concepts 3rd Edition多步转换多步转换Silberschatz,Korth and Sudarshan14.43Database System Concepts 3rd Edition投影操作投影操作:例例n当计算(branch-city=“Brooklyn”(branch)account)时得到一个关系,其模式为:(branch-name,branch-city,assets,account-number,ba

33、lance)n利用等价规则8a和8b下推投影;从中间结果删除不必要的属性可得:customer-name(account-number(branch-city=“Brooklyn”(branch)account)depositor)customer-name(branch-city=“Brooklyn”(branch)account)depositor)Silberschatz,Korth and Sudarshan14.44Database System Concepts 3rd Edition连接次序连接次序:例例n对所有关系对所有关系 r1,r2,及及r3(r1 r2)r3 =r1 (r

34、2 r3)n若若r2 r3 很大且很大且r1 r2 较小较小,选择选择(r1 r2)r3 n从而计算并存储一个较小的临时关系从而计算并存储一个较小的临时关系n结合律的使用原则结合律的使用原则:先做连接结果较小的先做连接结果较小的如果先作的这部分小到只有一行或几行，如果先作的这部分小到只有一行或几行，总总运算量小n问题：要机器自动作优化，比较难问题：要机器自动作优化，比较难Silberschatz,Korth and Sudarshan14.45Database System Concepts 3rd Edition连接次序连接次序:例例 n考虑表达式考虑表达式 customer-name (b

35、ranch-city=“Brooklyn”(branch)account depositor)n可以先计算可以先计算account depositor,再将结果与再将结果与 branch-city=“Brooklyn”(branch)连接连接n但但account depositor 可能是个大关系可能是个大关系n由于更可能仅仅少部分银行客户在位于的分行开帐户由于更可能仅仅少部分银行客户在位于的分行开帐户,因此更好的做法是先计算因此更好的做法是先计算:branch-city=“Brooklyn”(branch)accountSilberschatz,Korth and Sudarshan14.4

36、6Database System Concepts 3rd Edition连接次序例连接次序例Silberschatz,Korth and Sudarshan14.47Database System Concepts 3rd Edition等价表达式的枚举等价表达式的枚举n查询优化器利用等价规则来系统地生成等价于给定表达查询优化器利用等价规则来系统地生成等价于给定表达式的表达式式的表达式n从概念上说从概念上说,通过重复执行下列步骤直至找不到更多表达通过重复执行下列步骤直至找不到更多表达式来生成所有等价表达式式来生成所有等价表达式n对每个当前找到的表达式对每个当前找到的表达式,利用所有可用的等价

37、规则利用所有可用的等价规则,并并增加新生成的表达式到当前找到的表达式集合中增加新生成的表达式到当前找到的表达式集合中n上述方法的时间空间代价都很大上述方法的时间空间代价都很大n通过共享通过共享公共子表达式公共子表达式可减少空间需求可减少空间需求:当利用一等价规则可从当利用一等价规则可从E2生成生成E1,通常两者仅有顶层不同通常两者仅有顶层不同,下面下面的子树是相同的的子树是相同的,故可以共享故可以共享例如例如,当应用连接结合律时当应用连接结合律时n通过不生成所有表达式可减少时间需求通过不生成所有表达式可减少时间需求Silberschatz,Korth and Sudarshan14.48Dat

38、abase System Concepts 3rd Edition求值计划求值计划n求值计划确切定义了对每个操作采用什么算法求值计划确切定义了对每个操作采用什么算法,以及各操作的执行是以及各操作的执行是如何协调的如何协调的Silberschatz,Korth and Sudarshan14.49Database System Concepts 3rd Edition求值计划的选择求值计划的选择n选择求值计划时必须考虑求值算法的相互影响选择求值计划时必须考虑求值算法的相互影响n原因：独立地为每个操作都选择最廉价算法未必总体最原因：独立地为每个操作都选择最廉价算法未必总体最佳佳n例如例如归并连接可

39、能比散列连接代价高归并连接可能比散列连接代价高,但是可以提供有序输出但是可以提供有序输出,从而从而减少外层聚合操作的代价减少外层聚合操作的代价嵌套循环连接可能提供流水线化的机会嵌套循环连接可能提供流水线化的机会n实际的查询优化器结合了下列两大类方法的要素实际的查询优化器结合了下列两大类方法的要素:1.搜索所有计划并以基于代价的方式选择最佳计划搜索所有计划并以基于代价的方式选择最佳计划2.利用启发式规则选择计划利用启发式规则选择计划Silberschatz,Korth and Sudarshan14.50Database System Concepts 3rd Edition基于代价的优化基于代

40、价的优化n考虑为考虑为r1 r2 .rn找到最佳连接次序找到最佳连接次序n组合爆炸组合爆炸:上面的表达式共有上面的表达式共有(2(n 1)!/(n 1)!种不同的连接次序种不同的连接次序,当当n=7,即有即有665280,当当n=10,结果大于结果大于1760亿亿!n没有必要生成所有连接次序没有必要生成所有连接次序n利用利用动态规划动态规划,r1,r2,.rn的任何子集的最小的任何子集的最小代价连接次序只计算一次并保存为将来所用代价连接次序只计算一次并保存为将来所用 Silberschatz,Korth and Sudarshan14.51Database System Concepts 3r

41、d Edition优化中的动态规划优化中的动态规划n要找到要找到 n个关系的最佳连接树个关系的最佳连接树:为找到为找到n个关系的集合个关系的集合S 进行连接的最佳方案进行连接的最佳方案,考虑考虑所有可能的形如所有可能的形如S1 (S S1)的方案的方案,其中其中S1 是是S 的任意非空子集的任意非空子集递归计算连接递归计算连接S 的所有子集的代价的所有子集的代价,以找出每个方以找出每个方案的代价案的代价,然后选择然后选择2n 1 种可能方案中代价最小者种可能方案中代价最小者当计算出任意子集的方案当计算出任意子集的方案,保存该方案保存该方案,并在需要的并在需要的时候重用之时候重用之,而不是重新计

42、算而不是重新计算动态规划动态规划Silberschatz,Korth and Sudarshan14.52Database System Concepts 3rd Edition连接次序优化算法连接次序优化算法Silberschatz,Korth and Sudarshan14.53Database System Concepts 3rd Edition左深连接树左深连接树n左深连接树中左深连接树中,每个连接的右手边输入是个关系每个连接的右手边输入是个关系,而不是中间连接的结果而不是中间连接的结果Silberschatz,Korth and Sudarshan14.54Database Sys

43、tem Concepts 3rd Edition优化的代价优化的代价n为找到为找到n个关系的集合的最佳左深连接树个关系的集合的最佳左深连接树:Consider n alternatives with one relation as right-hand side input and the other n-1 relations as left-hand side inputUsing(recursively computed and stored)least-cost join order for each alternative on left-hand-side,choose the c

44、heapest of the n alternativesn利用动态规划利用动态规划,优化的时间复杂度为优化的时间复杂度为O(3n)当n=10,此数为59000而不是1760亿!n空间复杂度为空间复杂度为:O(2n)Silberschatz,Korth and Sudarshan14.55Database System Concepts 3rd Edition基于代价优化中有收益的排序次序基于代价优化中有收益的排序次序n考虑表达式考虑表达式(r1 r2 r3)r4 r5n有收益的排序次序有收益的排序次序是指元组的一个特定排序次序是指元组的一个特定排序次序,对以后的操对以后的操作可能有用作可能有

45、用生成生成 r1 r2 r3 结果时再与结果时再与r4 或或r5的公共属性上排序的公共属性上排序,也许有用也许有用,但在仅与但在仅与r1和和r2公共的属性上排序就没用公共的属性上排序就没用利用归并连接计算利用归并连接计算 r1 r2 r3 可能代价更高可能代价更高,但可能提供按一个但可能提供按一个有有收益收益的次序排序的输出的次序排序的输出n对对n个给定关系集合的每个子集找出最佳连接次序是不够的个给定关系集合的每个子集找出最佳连接次序是不够的,必必须对每个子集的每个须对每个子集的每个有收益有收益排序次序找出最佳连接次序排序次序找出最佳连接次序前面的动态规划算法做简单扩展前面的动态规划算法做简单

46、扩展通常通常,有收益有收益次序的数目很小且不显著影响时间次序的数目很小且不显著影响时间/空间复杂度空间复杂度Silberschatz,Korth and Sudarshan14.56Database System Concepts 3rd Edition启发式优化启发式优化n即使用了动态规划即使用了动态规划,基于代价的优化还是很昂基于代价的优化还是很昂贵贵n系统可以使用系统可以使用启发式启发式来减少在基于代价方式中来减少在基于代价方式中必须考虑的可选方案的数目必须考虑的可选方案的数目n启发性规则启发性规则:来自经验，不保证成功，还可能来自经验，不保证成功，还可能不相容不相容n如如:”三思而后行

47、三思而后行“VS”当断不断，反受其乱当断不断，反受其乱”Silberschatz,Korth and Sudarshan14.57Database System Concepts 3rd Edition启发式优化启发式优化n启发式优化利用一套规则来转换查询树启发式优化利用一套规则来转换查询树,这些这些规则通常规则通常(但不是所有情况但不是所有情况)都能改善执行性能都能改善执行性能尽早执行选择尽早执行选择(减少元组数目减少元组数目)尽早执行投影尽早执行投影(减少属性数目减少属性数目)在其他类似操作之前执行最具限制性的选择和连接在其他类似操作之前执行最具限制性的选择和连接操作操作某些系统只使用启发

48、式某些系统只使用启发式,其他的结合了启发式与部其他的结合了启发式与部分基于代价的优化分基于代价的优化Silberschatz,Korth and Sudarshan14.58Database System Concepts 3rd Edition典型的启发式优化步骤典型的启发式优化步骤1.分解合取选择成为一个单选择操作序列分解合取选择成为一个单选择操作序列(Equiv.rule 1.)2.将选择操作移到查询树下方以便尽早执行将选择操作移到查询树下方以便尽早执行(Equiv.rules 2,7a,7b,11)3.首先执行能产生最小关系的选择和连接操作首先执行能产生最小关系的选择和连接操作(Equ

49、iv.rule 6)4.笛卡儿积操作后接选择条件用连接操作替换笛卡儿积操作后接选择条件用连接操作替换(Equiv.rule 4a)5.将投影属性列表分解并尽可能移到查询树下方将投影属性列表分解并尽可能移到查询树下方,必要时创必要时创建新投影建新投影(Equiv.rules 3,8a,8b,12)6.确认其操作可以流水线化的子树确认其操作可以流水线化的子树,并利用流水线执行之并利用流水线执行之Silberschatz,Korth and Sudarshan14.59Database System Concepts 3rd Edition查询优化器的结构查询优化器的结构nSystem R/Star

50、burst 优化器只考虑优化器只考虑左深连接次序左深连接次序,这这减少了优化复杂性并生成适应流水线求值的方案减少了优化复杂性并生成适应流水线求值的方案nSystem R/Starburst 还利用启发式来在查询树中下推还利用启发式来在查询树中下推选择和投影选择和投影nOracle的某些版本中使用了启发式优化的某些版本中使用了启发式优化:反复选出下一步反复选出下一步“最佳最佳”连接的关系连接的关系从从 n 个开始点的每一个开始个开始点的每一个开始,从中挑选最佳从中挑选最佳n对于使用辅助索引的扫描对于使用辅助索引的扫描,某些优化器考虑了包含元组某些优化器考虑了包含元组的页在缓冲区中的概率的页在缓冲