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

多表连接查询优化的相关研究吕彬2009.3.5motivation星型连接效果对比图050010001500200025008.00E+045.00E+051.05E+06三元组数时间(ms)Star-join优化前Star-join优化后'Z'型连接效果对比图050001000015000200008.00E+045.00E+051.05E+06三元组数时间(ms)z-join优化前z-join优化后图中表示连接顺序对查询效率的影响：准确估计选择度要考虑属性间的相关性问题关键：高效地计算属性间的相关度AgendaMulti-tablejoinoverview•HeuristicandrandomizedoptimizationforthejoinorderingproblemMichaelSteinbrunn，etal,TheVLDBJournal(1997)6:191–208Attributecorrelationdetection•BHUNT:AutomaticDiscoveryofFuzzyAlgebraicConstraintsinRelationalDataPaulG.BrownPeterJ.Haas,Proceedingsofthe29thVLDBConference,2003•CORDS:AutomaticDiscoveryofCorrelationsandSoftFunctionalDependenciesIhabF.Ilyas，VolkerMarkl,etal,SIGMOD2004,June13–18,2004,•COCA:MoreAccurateMultidimensionalHistogramsoutofMoreAccurateCorrelationsDetectionCAOWei1,QINXiongpai,WANGShan,WAIM2008Starjoin•StarGazingfromatopyourDB2z/OSDatabaseServerTerryPurcell,etal,IntelligentOptimizer•Starjoinrevisited:PerformanceinternalsforclusterarchitecturesJosepAguilar-Saborit,Data&KnowledgeEngineering63(2007)995–1013Heuristicandrandomizedoptimizationforthejoinorderingproblem•Choosingjointypebasedoncost•Solutionspaceforthejoinorderingproblem•Joinorderingstrategies•Quantitativeanalysis•ConclusionMulti-tablejoinoverviewChoosingjointypebasedoncost•Costmodels•Nestedloopjoin•Sort-mergejoin•HashjoinMulti-tablejoinoverviewIOCostElapsedTimeRowCostCPUCostBaseCostScanCostPageCostSolutionspaceforthejoinorderingproblem•Left-deeptreesn!waystoallocatenbaserelationstothetree’sleavesgoodsolutionsbecauseofexploitingthecost-reducingpipeliningtechnique•Bushytreesanadaptableplanenumerationstrategylineargraphs(n3−n)/6stargraphs(n−1)2n−2Multi-tablejoinoverviewJoinorderingstrategies•Deterministicalgorithmsheuristicorexhaustivesearch•RandomizedalgorithmsDefineasetofmoveswhichconstituteedgesbetweenthedifferentsolutionsofthesolutionspaceperformsarandomwalkalongtheedgesaccordingtocertainrules,terminatingassoonasnomoreapplicablemovesexistoratimelimitisexceeded•Geneticalgorithmsmakeuseofarandomizedsearchstrategyverysimilartobiologicalevolution•HybridalgorithmscombinethestrategiesofpuredeterministicandpurerandomizedalgorithmsMulti-tablejoinoverviewQuantitativeanalysis•Classofthejoingraph•RelationcardinalitiesanddomainsizesMulti-tablejoinoverviewQuantitativeanalysis•SolutionspacesMulti-tablejoinoverviewQuantitativeanalysis•deterministicalgorithmsMulti-tablejoinoverviewQuantitativeanalysis•deterministicalgorithmsMulti-tablejoinoverviewQuantitativeanalysis•RandomizedandgeneticalgorithmsMulti-tablejoinoverviewQuantitativeanalysis•RandomizedandgeneticalgorithmsMulti-tablejoinoverviewQuantitativeanalysis•RandomizedandgeneticalgorithmsMulti-tablejoinoverviewQuantitativeanalysis•RandomizedandgeneticalgorithmsMulti-tablejoinoverviewQuantitativeanalysis•Totalrunningtime•FindfinalsolutiontimeMulti-tablejoinoverviewConclusion•HeuristicalgorithmsVsRandomizedandgeneticalgorithmscomputequickly,butfarfromtheoptimum.bettersuitedforjoinoptimizations;althoughrequirealongerrunningtime•SolutionspaceExceptthestarjoingraph,thebushytreeispreferablethanleft-deepprocessingtrees.•TheextensibilityofrandomizedandgeneticalgorithmsMulti-tablejoinoverviewQuery-Drivenapproaches•Queryworkload•Queryfeedback•Multidimensionalhistogram•SASHalgorithm•AdvantageanddisadvantageData-Drivenapproaches•StatisticalChi-squaretest,Log-linearmodel•ProbabilityBayesiannetwork,Markovnetwork•Fullscanvs.Sample•hardFDs,softFDs,CorrelationAttributecorrelationdetectionBHUNT:AutomaticDiscoveryofFuzzyAlgebraicConstraintsinRelationalData•ExampleAttributecorrelationdetectionOverviewofBHUNT•AlgebraicConstraints•Examplea1:deliveries.deliveryDate,a2:orders.shipDate,⊕:asthesubtractionoperator,P:orders.orderID=deliveries.orderID,I={2,3,4,5}∪{12,13,...,19}∪{31,32,33,34,35}.AttributecorrelationdetectionOverviewofBHUNT•GeneratingCandidatesC=(a1,a2,P,⊕).GeneratingPairingRulesTurningPairingRulesIntoCandidates•IdentifyingFuzzyConstraintsConstructingBumpIntervals,byapplyingstatisticalhistogramming,segmentation,orclusteringtechniquestoasampleofthecolumnvaluesChoosingtheSampleSize,Thesamplesizeisselectedtocontrolthenumberof“exception”recordsthatfailtosatisfytheconstraint.•ExploitingtheConstraintsIdentifythemostusefulsetofconstraints,andcreate“exceptiontables”toholdalloftheexceptionrecords.•Modifythequeriestoincorporatetheconstraintstheoptimizerusestheconstraintstoidentifynew,moreefficientaccesspaths.AttributecorrelationdetectionExperimentalresultsofBHUNTAttributecorrelationdetectionCORDS:AutomaticDiscoveryofCorrelationsandSoftFunctionalDependencies•.AttributecorrelationdetectionCORDS:AutomaticDiscoveryofCorrelationsandSoftFunctionalDependencies•softfunctionaldependencies•C1=C2,thevalueofC1determinesthevalueofC2notwithcertainty,butmerelywithhighprobability.•hardfunctionaldependencies•thevalueofC1completelydeterminesthevalueofC2.AttributecorrelationdetectionCORDSoverview•First:EnumeratingandPruning•PruningruleTypeconstraintStatisticalconstraintParingconstraintWorkloadcon