SQL多表连接查询优化的相关研究.ppt

《SQL多表连接查询优化的相关研究.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、多表连接查询优化的相关研究吕彬2009.3.5motivation图中表示连接顺序对查询效率的影响：准确估计选择度要考虑属性间的相关性问题关键：高效地计算属性间的相关度AgendaMulti-tablejoinoverviewHeuristicandrandomizedoptimizationforthejoinorderingproblemMichaelSteinbrunn，etal,TheVLDBJournal(1997)6:191–208AttributecorrelationdetectionBHUNT:AutomaticDiscoveryofFuzzyAlgebraicCo

2、nstraintsinRelationalDataPaulG.BrownPeterJ.Haas,Proceedingsofthe29thVLDBConference,2003CORDS:AutomaticDiscoveryofCorrelationsandSoftFunctionalDependenciesIhabF.Ilyas，VolkerMarkl,etal,SIGMOD2004,June13–18,2004,COCA:MoreAccurateMultidimensionalHistogramsoutofMoreAccurateCorrelationsDetectionCAOWe

3、i1,QINXiongpai,WANGShan,WAIM2008StarjoinStarGazingfromatopyourDB2z/OSDatabaseServerTerryPurcell,etal,IntelligentOptimizerStarjoinrevisited:PerformanceinternalsforclusterarchitecturesJosepAguilar-Saborit,Data&KnowledgeEngineering63(2007)995–1013Heuristicandrandomizedoptimizationforthejoinorderin

4、gproblemChoosingjointypebasedoncostSolutionspaceforthejoinorderingproblemJoinorderingstrategiesQuantitativeanalysisConclusionMulti-tablejoinoverviewChoosingjointypebasedoncostCostmodelsNestedloopjoinSort-mergejoinHashjoinMulti-tablejoinoverviewIOCostElapsedTimeRowCostCPUCostBaseCostScanCostPage

5、CostSolutionspaceforthejoinorderingproblemLeft-deeptreesn!waystoallocatenbaserelationstothetree’sleavesgoodsolutionsbecauseofexploitingthecost-reducingpipeliningtechniqueBushytreesanadaptableplanenumerationstrategylineargraphs(n3−n)/6stargraphs(n−1)2n−2Multi-tablejoinoverviewJoinorderingstrateg

6、iesDeterministicalgorithmsheuristicorexhaustivesearchRandomizedalgorithmsDefineasetofmoveswhichconstituteedgesbetweenthedifferentsolutionsofthesolutionspaceperformsarandomwalkalongtheedgesaccordingtocertainrules,terminatingassoonasnomoreapplicablemovesexistoratimelimitisexceededGeneticalgorithm

7、smakeuseofarandomizedsearchstrategyverysimilartobiologicalevolutionHybridalgorithmscombinethestrategiesofpuredeterministicandpurerandomizedalgorithmsMulti-tablejoinoverviewQuantitativeanalysisClassofthejoingraphRelationcardinaliti