数据库教学课件：第6章 查询优化

第6章查询优化本章内容参考数据库概念(第四版)byA.SilberschatzChapter14Optimization简介+自学本章要解决的关键问题如何找到具有最低求值代价的求值计划主要内容概述用于代价估算的统计信息关系代数表达式的转换基于代价的优化算法物化视图与视图维护概述一个给定查询有多种可选择的求值方法等价表达式一个操作有若干不同算法(Chapter5)一个查询求值方法的好坏带来的代价差别可能是巨大的例如:执行rXs后续选择r.A=s.B

比执行一个同样条件的连接慢得多需要估算操作的代价依赖于数据库维护的统计信息例如元组数,连接属性的不同值的数目,等等需要对中间结果估算统计信息以便对复杂表达式计算代价概述概述对一个表达式的查询求值方案的生成涉及几个步骤:生成逻辑上等价的表达式利用等价规则将一个表达式转换成另一个等价的表达式注解(Annotate)结果表达式以得到其他查询计划基于估算代价选择最廉价的计划整个过程称为基于代价的优化SQLConstructsSECLECT(DISTINCT)<listofcolumns>FROM<listoftables>WHERE<listofBooleanFactors>GROUPBY<listofcolumns>HAVING<listofBooleanFactors>ORDERBY<listofcolumns>SQLSemanticsTakeCartesianproductofFROMtablesProjectonlythosereferencedcolumnsWHERE:applyallfiltersinWHEREGROUPBY:formgroupsonresultsHAVING:applyfiltertogroupsORDERBY:makesureresultsinrightorderDISTINCT:removeduplicatesQ:Isthis“operationalsemantics”efficient?Differentplans:mainlydifferentinthefirstthreeOptimization:DifferentStrategiesOptimalapproach:Enumerate(枚举)eachpossibleplanMeasureitsperformancebyrunningitPickthefastestoneHeuristicsapproach:fixedheuristicsallthewaythroughplanconstructione.g.:alwaysnestedloopjoins,indexedrelationasinnere.g.:orderrelationsfromsmallesttobiggestCost-basedOptimizationPlanspace:whatisthespaceofqueryplans?Costestimation:howtoestimatethecost,withoutexecutingeach?Searchalgorithm:howtosearchthespace,asguidedbycostestimatesSpaceofQueryPlansSelections:algorithms:sequential,indexscanJoins:algorithms:nested-loop,sortmerge,hashOrdering/Grouping:canan“interestingorder”beproducedbyjoin/selections?algorithm:sorting,hash-basedTheyinterleavewitheachother!HugeSpace!AssumptionstoHelpTypicalassumptionstohelpreducethespace:Projections:pusheddowntoreduce#ofcolumnsSelections:pusheddowntoreduce#ofrowsJoins:left-deepjoinsavoidCartesianproducts;delayitintheplanQ:howtoavoidCartesianproducts?Maymissanoptimalplan!Cost/SizeEstimationAccuraterelativelygoalistocompareplans,nottopredictexactcostmoreofanartthananexactscienceEachoperator:inputsize,cost,outputsizeestimatecostbasedoninputsizeestimateoutputsize(fornextoperator)orselectivityselectivity=ratioofoutputtoinputCostEstimationInput:simpleDBstatistics#oftuples&diskpages#ofdistinctvaluespercolumnstatisticsupdatedperiodicallyAssumptionofattribute/predicateindependenceWhennoestimateavailable,usemagicnumberNew/Alternativeapproaches:sampling,histogramofDBSelectivityFactors:RangeSelectionWhatisassumedintheseformulas?column>value1:F=(maxValue-value1)/rangeOfValuecolumninvalue1:value2F=(value2-value1)/rangeOfValueSearchthePlanSpaceBaseline:exhaustivesearchenumerateallcombinations,andcomparetheircostSearchmethodparameters:plantreedevelopment:construction:bottom-up,top-downmodification:improveasomehow-constructedtreealgorithms:heuristicselections:makechoicesbasedonheuristicsbranchandbound:searchboundedbythecurrentbesttreehillclimbing:find“nearby”planswithlowestcostdynamicprogramming:constructionbygreedyselectionsWhatYouShouldKnowQueryoptimizationiscriticalforanycommercialDBMSgood/badcanbeordersofmagnitudeThe3componentsoftheSystem-RstyleoptimizationPlanspacedefinitionCostestimationSearchalgorithmhugenumberofalternative,semanticallyequivalentplansIdealgoal:mapadeclarativequerytothemostefficientplanConventionalwisdom:avoidbadplansStateoftheart:industry:mostoptimizersareSystem-Rstyleacademic:alwaysacoredatabaseresearchtopic用于代价估算的统计信息(回顾)(10/14)nr:

关系r中的元组个数br

:包含r中元组的块数sr

:r中元组的大小fr

:r的块因子—即,能放入一块之中的r的元组数V(A,r):r

中出现的A属性上的不同值的个数;等于A(r)的大小SC(A,r):

关系r

中属性A的选择基数,满足A上等值条件的平均记录数若r中元组在文件中连续存放,则:关于索引的目录信息(回顾)fi

:索引i的内节点的平均扇出,适用于树结构索引,如B+树HTi

:索引i的层数—即高度对于关系r上A属性的平衡树索引(如B+-树)

HTi=logfi(V(A,r))对于散列索引,HTi

为1LBi

:索引i的底层索引块数

—即索引叶子层的块数查询代价的度量(回顾)典型地,磁盘存取是决定性的代价,也相对容易估算来自磁盘的块传送次数被用作求值的实际代价的度量假设所有块传送都具有相同代价实际的优化器不作此假设,并区分顺序与随机磁盘存取不包括写输出到磁盘的代价记算法A的代价估算为EA统计信息例faccount=20(一块可放入account的20个元组)V(branch-name,account)=50(50个分行)V(balance,account)=500(500个不同的balance

值)account

=10000(account有10,000条元组)假设account上存在下列索引:属性branch-name上的主B+-树索引属性balance上的辅助B+-树索引选择的大小估算等值选择

A=v(r)SC(A,r):满足选择的记录数SC(A,r)/fr:这些记录将占用的块数二分搜索的代价估算为键属性上的等值条件:SC(A,r)=1选择的大小估算涉及比较的选择形如AV(r)的选择令c表示满足条件的估算元组数若

min(A,r)和

max(A,r)在目录中可得c=0ifv<min(A,r)

c=

若没有统计信息,c可假设为

nr/2AV(r)的情形是对称的复杂选择的实现条件I的选择度是关系r中一条元组满足I的概率,如果si

是r中满足的元组数,则i

的选择度为si/nr合取:12...n(r).结果中元组数的估算值为:

析取:1

2

...

n(r).元组数的估算值为:

否定:(r).元组数的估算值为:

nr

–

size((r))连接的大小的估算卡氏积

rxs包含

nr.ns

元组,每个元组占用sr+ss

字节若

RS=,则

r

s

等同于

rxs若

RS

是R的键,则s

的一条元组将与r的最多一条元组连接因此,rs

中的元组数不大于s中的元组数若

RS

在S中是引用R的外键,则r

s中的元组数正好等于s中的元组数RS

是引用S

的外键的情形是对称的在查询例depositorcustomer中,depositor中的customer-name是customer的外键

因此,结果具有

ndepositor

条元组,即5000连接操作:例子连续用例:

depositor

customer连接例的目录信息:ncustomer=10,000fcustomer=25,这意味着

bcustomer

=10000/25=400ndepositor=5000.fdepositor

=50,这意味着

bdepositor

=

5000/50=100V(customer-name,depositor)=2500,这意味着每个顾客平均有两个depositor还假设depositor中的customer-name是customer上的外键连接的大小的估算若

RS={A}不是R

或S的键如果我们假设R中每个元组t都在RS中产成元组,则R

S中的元组数估算为:

若正好相反,估算值为:

这两个估算值的较小者可能更准确连接的大小的估算例:不利用有关外键的信息计算

depositorcustomer

的大小估算:V(customer-name,depositor)=2500,且

V(customer-name,customer)=10000两个估算为

5000*10000/2500=20,000及

5000*10000/10000=5000我们选择其中的较小估算,在本情形下等于我们以前利用外键的计算结果其他操作的大小估算投影:估算大小A(r)=V(A,r)聚合:估算大小AgF(r)=V(A,r)集合运算

对于同一关系上选择的并/交:重写并利用选择的大小估算例如1(r)2

(r)可重写为1v2

(r)对于在不同关系上的操作:rs的估算大小=r的大小+s的大小rs的估算大小=r的大小与s的大小之最小者r–s的估算大小=r上面这三种估算都可能不精确,但提供了大小的上界其他操作的大小估算外连接:rs的估算大小=rs的大小+r的大小右外连接的情形是对称的rs的估算大小=rs的大小+r的大小+s的大小不同值个数的估算选择:(r)若强制A

取一个特定值(e.g.,A=3)

:V(A,(r))=1若强制A取一个特定集合中的某个值(e.g.,(A=1V

A=3VA=4)):V(A,(r))=指定值的个数若选择条件形如

A

opv,其中op为比较运算符(e.g.,A<=5):估算V(A,(r))=V(A,r)*s其中

s

是本选择的选择度其他情况:利用近似估算

min(V(A,r),n(r)

)更准确的估算可利用概率论得到,但是本估算一般就很管用不同值个数的估算连接:rs若A中所有属性都来自r

估算V(A,rs)=min(V(A,r),nrs)若A包含来自r的属性A1和来自s的属性A2,则估算V(A,rs)=

min(V(A1,r)*V(A2–A1,s),V(A1–A2,r)*V(A2,s),nrs)利用概率论可以得到更精确的估算,但这已经很好了

不同值个数的估算投影的不同值个数的估算是直接的在A(r)

中与在r中是相同的对聚合的分组属性也是一样对于聚合值对min(A)和max(A),不同值个数可估算为min(V(A,r),V(G,r)),其中G表示分组属性对其他聚合函数,假设所有值都不同,并利用V(G,r)关系代数表达式的转换如果在每个合法的数据库实例上,两个关系代数表达式都生成同样的元组集合,则这两个关系代数表达式称为等价的注意:元组次序是无关的在SQL中,输入和输出都是元组的多重集合如果在每个合法的数据库实例上,两个关系代数表达式都生成同样的元组多重集合,则这两个表达式在关系代数的多重集合版本下称为等价的等价规则说明了两种形式的表达式是等价的可以用一个表达式替换另一个等价规则1. 合取选择操作可以分解称个体选择的序列:

2. 选择操作是可交换的:

3. 一个投影操作序列中只有最后一个是必要的,其余皆可省略:

选择可与笛卡儿积及连接结合:(E1

XE2)=E1

E2

1(E1

2E2)=E1

12

E2

等价规则5. 连接操作(及自然连接)可交换:

E1E2=E2

E16. (a)自然连接操作是可结合的: (E1E2)E3=E1(E2E3)

(b)连接按如下方式是可结合的:

(E11E2)2

3

E3=E123(E2

2E3)

其中2

仅涉及来自E2

和E3的属性等价规则

7. 在下面两个条件下,选择操作对连接操作有分配律:

(a)当0中的所有属性仅涉及被连接表达式之一(E1)的属性时:

0E1

E2)=(0(E1))E2

(b)当1仅涉及E1的属性且2仅涉及E2的属性时: 1E1

E2)=(1(E1))((E2))等价规则8. 投影操作对连接操作的分配律如下: (a)若

仅涉及来自L1

L2的属性:

(b)考虑连接

E1

E2若

L1

和

L2

分别是来自E1和E2的属性集合

令L3

是连接条件中涉及的E1的属性,但不在L1

L2中,并且令

L4是连接条件中涉及的E2的属性,但不在L1

L2中等价规则集合运算并和交都是可交换的:

E1

E2=E2

E1

E1

E2=E2

E1

集合差不是可交换的集合并和交都是可结合的: (E1

E2)E3=E1

(E2E3)

(E1

E2)E3=E1

(E2E3)选择操作对,和–可分配:

(E1–E2)=

(E1)–(E2)

类似地可用和替换–

同样:

(E1–E2)=(E1)–E2

类似地可用替换–

,但不能用12. 投影操作对并可分配:

L(E1

E2)=(L(E1))(L(E2))等价规则的图示转换例查询:找出所有在位于Brooklyn的某分行具有帐户的客户的姓名

customer-name(branch-city=“Brooklyn”

(branch(accountdepositor)))利用规则7a转换.

customer-name

((branch-city=“Brooklyn”(branch))

(account

depositor))尽可能早地执行选择可以减少待连接关系的大小

多步转换例查询:找出所有在位于Brooklyn的某分行具有帐户且帐户余额超过$1000的客户的姓名:

customer-name((branch-city=“Brooklyn”balance>1000

(branch(accountdepositor)))

利用连接结合性(Rule6a)的转换:

customer-name((branch-city=“Brooklyn”balance>1000

(branch(account))depositor)

第二种形式提供了应用“尽早执行选择”规则的机会,导致子表达式branch-city=“Brooklyn”

(branch)balance>1000(account)因此一系列的转换是有用的多步转换投影操作:例当计算 (branch-city=“Brooklyn”(branch)account)

时得到一个关系,其模式为:

(branch-name,branch-city,assets,account-number,balance)利用等价规则8a和8b下推投影;从中间结果删除不必要的属性可得:

customer-name((

account-number

((branch-city=“Brooklyn”(branch)account))

depositor)customer-name((branch-city=“Brooklyn”

(branch)account)depositor)

连接次序:例对所有关系

r1,r2,及r3 (r1

r2)r3=r1(r2

r3)若r2

r3很大且r1

r2

较小,选择

(r1

r2)r3从而计算并存储一个较小的临时关系结合律的使用原则:先做连接结果较小的如果先作的这部分小到只有一行或几行，总运算量小问题：要机器自动作优化，比较难连接次序:例

考虑表达式

customer-name

((branch-city=“Brooklyn”(branch))

accountdepositor)可以先计算accountdepositor,再将结果与

branch-city=“Brooklyn”(branch)

连接但accountdepositor可能是个大关系由于更可能仅仅少部分银行客户在位于的分行开帐户,因此更好的做法是先计算:

branch-city=“Brooklyn”(branch)account连接次序例等价表达式的枚举查询优化器利用等价规则来系统地生成等价于给定表达式的表达式从概念上说,通过重复执行下列步骤直至找不到更多表达式来生成所有等价表达式对每个当前找到的表达式,利用所有可用的等价规则,并增加新生成的表达式到当前找到的表达式集合中上述方法的时间空间代价都很大通过共享公共子表达式可减少空间需求:当利用一等价规则可从E2生成E1,通常两者仅有顶层不同,下面的子树是相同的,故可以共享例如,当应用连接结合律时通过不生成所有表达式可减少时间需求求值计划求值计划确切定义了对每个操作采用什么算法,以及各操作的执行是如何协调的求值计划的选择选择求值计划时必须考虑求值算法的相互影响原因：独立地为每个操作都选择最廉价算法未必总体最佳例如归并连接可能比散列连接代价高,但是可以提供有序输出,从而减少外层聚合操作的代价嵌套循环连接可能提供流水线化的机会实际的查询优化器结合了下列两大类方法的要素:1. 搜索所有计划并以基于代价的方式选择最佳计划2.利用启发式规则选择计划基于代价的优化考虑为r1

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

优化中的动态规划要找到n个关系的最佳连接树:为找到n个关系的集合S进行连接的最佳方案,考虑所有可能的形如S1(S–S1)的方案,其中S1

是S的任意非空子集递归计算连接S的所有子集的代价,以找出每个方案的代价,然后选择2n

–1种可能方案中代价最小者当计算出任意子集的方案,保存该方案,并在需要的时候重用之,而不是重新计算动态规划连接次序优化算法左深连接树左深连接树中,每个连接的右手边输入是个关系,而不是中间连接的结果优化的代价为找到n个关系的集合的最佳左深连接树:Considernalternativeswithonerelationasright-handsideinputandtheothern-1relationsasleft-handsideinputUsing(recursivelycomputedandstored)least-costjoinorderforeachalternativeonleft-hand-side,choosethecheapestofthenalternatives利用动态规划,优化的时间复杂度为O(3n)

当n=10,此数为59000而不是1760亿!空间复杂度为:O(2n)

基于代价优化中有收益的排序次序考虑表达式(r1

r2

r3)r4

r5有收益的排序次序是指元组的一个特定排序次序,对以后的操作可能有用生成

r1

r2

r3

结果时再与r4

或r5的公共属性上排序,也许有用,但在仅与r1和r2公共的属性上排序就没用利用归并连接计算r1

r2

r3可能代价更高,但可能提供按一个有收益的次序排序的输出对n个给定关系集合的每个子集找出最佳连接次序是不够的,必须对每个子集的每个有收益排序次序找出最佳连接次序前面的动态规划算法做简单扩展通常,有收益次序的数目很小且不显著影响时间/空间复杂度启发式优化即使用了动态规划,基于代价的优化还是很昂贵系统可以使用启发式来减少在基于代价方式中必须考虑的可选方案的数目启发性规则:来自经验，不保证成功，还可能不相容如:”三思而后行“VS”当断不断，反受其乱”启发式优化启发式优化利用一套规则来转换查询树,这些规则通常(但不是所有情况)都能改善执行性能尽早执行选择(减少元组数目)尽早执行投影(减少属性数目)在其他类似操作之前执行最具限制性的选择和连接操作某些系统只使用启发式,其他的结合了启发式与部分基于代价的优化典型的启发式优化步骤1. 分解合取选择成为一个单选择操作序列(Equiv.rule1.)2. 将选择操作移到查询树下方以便尽早执行(Equiv.rules2,7a,7b,11)3. 首先执行能产生最小关系的选择和连接操作(Equiv.rule6)4. 笛卡儿积操作后接选择条件用连接操作替换(Equiv.rule4a)5. 将投影属性列表分解并尽可能移到查询树下方,必要时创建新投影(Equiv.rules3,8a,8b,12)6. 确认其操作可以流水线化的子树,并利用流水线执行之查询优化器的结构SystemR/Starburst优化器只考虑左深连接次序,这减少了优化复杂性并生成适应流水线求值的方案SystemR/Starburst还利用启发式来在查询树中下推选择和投影Oracle的某些版本中使用了启发式优化:反复选出下一步“最佳”连接的关系从n个开始点的每一个开始,从中挑选最佳对于使用辅助索引的扫描,某些优化器考虑了包含元组的页在缓冲区中的概率SQL的复杂查询导致了查询优化的复杂如嵌套子查询查询优化器的结构某些查询优化器集成了启发式选择和替换存取方案的生成SystemR和Starburst基于SQL嵌套块概念使用了层次式过程启发式重写后接基于代价的连接次序优化即使使用了启发式,基于代价的查询优化仍然带来大量开销这个开销通常被查询执行时的节省更多地补偿,尤其是较慢的磁盘存取数目的减少OptimizingNestedSubqueries(略)SQL

conceptuallytreatsnestedsubqueriesinthewhereclauseasfunctionsthattakeparametersandreturnasinglevalueorsetofvaluesParametersarevariablesfromouterlevelquerythatareusedinthenestedsubquery;suchvariablesarecalledcorrelationvariablesE.g.

select

customer-name

fromborrower

whereexists(select*

fromdepositor

wheredepositor.customer-name=

borrower.customer-name)OptimizingNestedSubqueries(略)Conceptually,nestedsubqueryisexecutedonceforeachtupleinthecross-productgeneratedbytheouterlevelfromclauseSuchevaluationiscalledcorrelatedevaluationNote:otherconditionsinwhereclausemaybeusedtocomputeajoin(insteadofacross-product)beforeexecutingthenestedsubqueryOptimizingNestedSubqueriesCorrelatedevaluationmaybequiteinefficientsincealargenumberofcallsmaybemadetothenestedquerytheremaybeunnecessaryrandomI/OasaresultSQLoptimizersattempttotransformnestedsubqueriestojoinswherepossible,enablinguseofefficientjointechniquesOptimizingNestedSubqueriesE.g.:earliernestedquerycanberewrittenas

selectcustomer-name

fromborrower,depositor

wheredepositor.customer-name=borrower.customer-nameNote:abovequerydoesn’tcorrectlydealwithduplicates,canbemodifiedtodosoaswewillseeIngeneral,itisnotpossible/straightforwardtomovetheentirenestedsubqueryfromclauseintotheouterlevelqueryfromclauseAtemporaryrelationiscreatedinstead,andusedinbodyofouterlevelqueryOptimizingNestedSubqueriesIngeneral,SQLqueriesoftheformbelowcanberewrittenasshownRewrite:select…

from

L1

where

P1

andexists(select*

from

L2

where

P2)To:createtable

t1as

selectdistinctV

fromL2

whereP21

select…

fromL1,

t1

whereP1

andP22P21containspredicatesinP2thatdonotinvolveanycorrelationvariablesP22reintroducespredicatesinvolvingcorrelationvariables,with

relationsrenamedappropriatelyVcontainsallattributesusedinpredicateswithcorrelationvariablesOptimizingNestedSubqueriesInourexample,theoriginalnestedquerywouldbetransformedto

createtablet1

as

selectdistinctcustomer-name

fromdepositor

selectcustomer-name

fromborrower,t1

wheret1.customer-name=borrower.customer-nameTheprocessofreplacinganestedquerybyaquerywithajoin(possiblywithatemporaryrelation)iscalleddecorrelation.OptimizingNestedSubqueriesDecorrelationismorecomplicatedwhenthenestedsubqueryusesaggregation,orwhentheresultofthenestedsubqueryisusedtotestforequality,orwhentheconditionlinkingthenestedsubquerytotheotherqueryis‘notexists’,andsoon.物化视图物化视图是计算并存储内容的视图考虑视图

createviewbranch-total-loan(branch-name,total-loan)

as

selectbranch-name,sum(amount)

fromloan

groupbybranch-name如果频繁需要总贷款额,那么物化上述视图将很有用节省了查找许多元组并累加其数额的工作物化视图维护保持物化视图相对基础数据为最新的任务称为物化视图维护物化视图可通过每次更新时重新计算得到维护更好的选择是利用增量视图维护利用对数据库关系的改变来计算物化视图的改变,从而得到更新物化视图维护视图维护可通过下列做到手工定义视图定义中每个关系上的插入,删除,修改触发器每当数据库关系被更新时利用手写代码更新视图数据库直接支持增量视图维护对一个关系或表达式的改变(插入和删除)称为其差异从r中插入和删除的元组集合记为ir

及dr为简化描述,只考虑插入和删除更新元组替换为先删除元组再插入更新后元组我们描述当给定输入的改变时,如何计算每个关系操作结果上的改变然后概述如何处理关系代数表达式连接操作考虑物化视图v=rs以及对r的更新令

rold

和

rnew表示关系r的新旧状态考虑对r的插入情况:我们可以将

rnews写为(rold

ir)s并将上式重写为(rold

s)(irs)但(rold

s)正是物化视图的旧值,故视图的增量改变正是

irs因此,对插入

vnew=vold(irs)

类似地对删除

vnew=vold–

(drs)选择和投影操作选择:考虑视图v=(r).vnew=vold(ir)vnew=vold-(dr)投影是更复杂的操作R=(A,B),且r(R)={(a,2),(a,3)}A(r)具有单个元组(a).如果我们从r中删除元组(a,2),我们不能从A(r)中删除元组(a),但是若我们又删除了(a,3),我们就应该删除该元组选择和投影操作对投影A(r)中的每个元组,我们将保存一个计数,即它被导出了多少次当对r插入元组时,如果结果元组已经在A(r)中,我们就递增它的计数,否则加入一条新元组且计数值为1当对r删除元组时,我们递减A(r)中对应元组的计数值若计数值变成0,我们从A(r)中删除该元组聚合操作count:v=Agcount(B)(r).当插入元组集合ir

时对ir中的每条元组r,若对应分组已经存在于v中,我们递增其计数,否则增加一条新元组,其count=1当删除元组集合dr

时对ir中的每条元组,我们查找t.A在v中的分组,并从该组计数中减去1.若计数变成0,从

v

中删除分组t.A的元组sum:v=Agsum(B)(r)

我们以类似于计数的方式来维护总和,只是要加/减B值而非对计数的加/减1另外我们维护计数以便发现没有元组的分组.这样的分组要从v中删除不能简单的测试sum=0(why?)为处理avg,我们维护sum和count

分别聚合值,最后再相除聚合操作min,max:v=Agmin(B)(r).处理r上插入是直截了当的.删除时维护聚合值min及max可能更昂贵.

我们必须检查同组中的r

的其他元组以找出新的最大最小值其他操作集合交:v=rs当插入一条元组到r

时我们检查它是否存在于s中,如果是则加入到v中当从r删除一条元组时,若它存在于交集中则删除之更新s

是对称的其他集合操作(并与差)以类似方式处理外连接的处理方式基本与连接相同,但需要一些额外工作处理表达式为处理整个表达式,我们导出计算对每个子表达式结果的增量改变的表达式,从最小表达式开始例如考虑

E1

E2,其中E1和E2

都可能是复杂表达式假设要插入E1的元组集合由D1给出早先已算出,因为较小子表达式先处理则要插入E1

E2的元组集合为

D1E2这正是维护连接的通常的方法

查询优化与物化视图重写查询以利用物化视图:有物化视图v=rs可用用户提交了查询

rst我们可以重写查询为vt

是否这么做取决于两种选择的代价估算用视图定义代替物化视图的使用:有物化视图v=rs可用,但是上面无任何索引用户提交查询

A=10(v).再假设

s

在公共属性B上有索引,r在属性A上有索引.此查询的最佳方案可能是用rs替换v,这导致查询方案A=10(r)s应该扩展查询优化器以考虑所有上述替代方案并选择最佳总体方案

物化视图选择物化视图选择:“最该物化的视图集合是哪些?”.此决定必须在系统负载的基础上做出索引与物化视图一样,索引选择问题密切相关,尽管更简单些某些数据库系统提供工具来帮助数据库管理员做出索引和物化视图的选择任务:Derby查询优化器实现分析任务:Derby查询优化器实现分析参考资料:DerbyOptimizerDesignDerbyv10sourcecodeEndofChapter(Extraslideswithdetailsofselectioncostestimationfollow)SelectionCostEstimateExampleNumberofblocksisbaccount=500:10,000tuplesintherelation;eachblockholds20tuples.Assumeaccountissortedonbranch-name.V(branch-name,account)is5010000/50=200tuplesoftheaccountrelationpertaintoPerryridgebranch200/20=10blocksforthesetuplesAbinarysearchtofindthefirstrecordwouldtake

log2(500)=9blockaccessesTotalcostofbinarysearchis9+10-1=18blockaccesses(versus500forlinearscan)branch-name=“Perryridge”(account)SelectionsUsingIndicesIndexscan–searchalgorithmsthatuseanindex;conditionisonsearch-keyofindex.A3(primaryindexoncandidatekey,equality).RetrieveasinglerecordthatsatisfiesthecorrespondingequalityconditionEA3=HTi

+1A4(primaryindexonnonkey,equality)Retrievemultiplerecords.Letthesearch-keyattributebeA.

A5(equalityonsearch-keyofsecondaryindex).Retrieveasinglerecordifthesearch-keyisacandidatekey

EA5=HTi

+1Retrievemultiplerecords(eachmaybeonadifferentblock)ifthesearch-keyisnotacandidatekey.EA3=HTi

+SC(A,r)CostEstimateExample(Indices)SinceV(branch-name,account)=50,weexpectthat10000/50=200tuplesoftheaccountrelationpertaintothePerryridgebranch.Sincetheindexisaclusteringindex,200/20=