数据库系统概念全套配套课件PPT ch13.ppt

《数据库系统概念全套配套课件PPT ch13.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter13:QueryOptimizationChapter13:QueryOptimizationIntroductionTransformationofRelationalExpressionsCatalogInformationforCostEstimationStatisticalInformationforCostEstimationCost-basedoptimizationDynamicProgrammingforChoosingEvaluationPlansMaterializedview

2、sIntroductionAlternativewaysofevaluatingagivenqueryEquivalentexpressionsDifferentalgorithmsforeachoperationIntroduction(Cont.)Anevaluationplandefinesexactlywhatalgorithmisusedforeachoperation,andhowtheexecutionoftheoperationsiscoordinated.Findouthowtoviewquer

3、yexecutionplansonyourfavoritedatabaseIntroduction(Cont.)CostdifferencebetweenevaluationplansforaquerycanbeenormousE.g.secondsvs.daysinsomecasesStepsincost-basedqueryoptimizationGeneratelogicallyequivalentexpressionsusingequivalencerulesAnnotateresultantexpres

4、sionstogetalternativequeryplansChoosethecheapestplanbasedonestimatedcostEstimationofplancostbasedon:Statisticalinformationaboutrelations.Examples:numberoftuples,numberofdistinctvaluesforanattributeStatisticsestimationforintermediateresultstocomputecostofcompl

5、exexpressionsCostformulaeforalgorithms,computedusingstatisticsGeneratingEquivalentExpressionsTransformationofRelationalExpressionsTworelationalalgebraexpressionsaresaidtobeequivalentifthetwoexpressionsgeneratethesamesetoftuplesoneverylegaldatabaseinstanceNote

6、:orderoftuplesisirrelevantwedon’tcareiftheygeneratedifferentresultsondatabasesthatviolateintegrityconstraintsInSQL,inputsandoutputsaremultisetsoftuplesTwoexpressionsinthemultisetversionoftherelationalalgebraaresaidtobeequivalentifthetwoexpressionsgeneratethes

7、amemultisetoftuplesoneverylegaldatabaseinstance.AnequivalencerulesaysthatexpressionsoftwoformsareequivalentCanreplaceexpressionoffirstformbysecond,orviceversaEquivalenceRules1.Conjunctiveselectionoperationscanbedeconstructedintoasequenceofindividualselections

8、.2.Selectionoperationsarecommutative.3.Onlythelastinasequenceofprojectionoperationsisneeded,theotherscanbeomitted.SelectionscanbecombinedwithCartesianproductsandthetajoins.(E1XE2)=E1E2