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

多表连接查询优化的相关研究 吕彬2009 3 5 motivation 图中表示连接顺序对查询效率的影响 准确估计选择度要考虑属性间的相关性问题关键 高效地计算属性间的相关度 Agenda Multi tablejoinoverviewHeuristicandrandomizedoptimizationforthejoinorderingproblemMichaelSteinbrunn etal TheVLDBJournal 1997 6 191 208AttributecorrelationdetectionBHUNT AutomaticDiscoveryofFuzzyAlgebraicConstraintsinRelationalDataPaulG BrownPeterJ Haas Proceedingsofthe29thVLDBConference 2003CORDS AutomaticDiscoveryofCorrelationsandSoftFunctionalDependenciesIhabF Ilyas VolkerMarkl etal SIGMOD2004 June13 18 2004 COCA MoreAccurateMultidimensionalHistogramsoutofMoreAccurateCorrelationsDetectionCAOWei1 QINXiongpai WANGShan WAIM2008StarjoinStarGazingfromatopyourDB2z OSDatabaseServerTerryPurcell etal IntelligentOptimizerStarjoinrevisited PerformanceinternalsforclusterarchitecturesJosepAguilar Saborit Data KnowledgeEngineering63 2007 995 1013 HeuristicandrandomizedoptimizationforthejoinorderingproblemChoosingjointypebasedoncostSolutionspaceforthejoinorderingproblemJoinorderingstrategiesQuantitativeanalysisConclusion Multi tablejoinoverview ChoosingjointypebasedoncostCostmodelsNestedloopjoinSort mergejoinHashjoin Multi tablejoinoverview SolutionspaceforthejoinorderingproblemLeft deeptreesn waystoallocatenbaserelationstothetree sleavesgoodsolutionsbecauseofexploitingthecost reducingpipeliningtechniqueBushytreesanadaptableplanenumerationstrategylineargraphs n3 n 6stargraphs n 1 2n 2 Multi tablejoinoverview JoinorderingstrategiesDeterministicalgorithmsheuristicorexhaustivesearchRandomizedalgorithmsDefineasetofmoveswhichconstituteedgesbetweenthedifferentsolutionsofthesolutionspaceperformsarandomwalkalongtheedgesaccordingtocertainrules terminatingassoonasnomoreapplicablemovesexistoratimelimitisexceededGeneticalgorithmsmakeuseofarandomizedsearchstrategyverysimilartobiologicalevolutionHybridalgorithmscombinethestrategiesofpuredeterministicandpurerandomizedalgorithms Multi tablejoinoverview QuantitativeanalysisClassofthejoingraphRelationcardinalitiesanddomainsizes Multi tablejoinoverview QuantitativeanalysisSolutionspaces Multi tablejoinoverview Quantitativeanalysisdeterministicalgorithms Multi tablejoinoverview Quantitativeanalysisdeterministicalgorithms Multi tablejoinoverview QuantitativeanalysisRandomizedandgeneticalgorithms Multi tablejoinoverview QuantitativeanalysisRandomizedandgeneticalgorithms Multi tablejoinoverview QuantitativeanalysisRandomizedandgeneticalgorithms Multi tablejoinoverview QuantitativeanalysisRandomizedandgeneticalgorithms Multi tablejoinoverview QuantitativeanalysisTotalrunningtimeFindfinalsolutiontime Multi tablejoinoverview ConclusionHeuristicalgorithmsVsRandomizedandgeneticalgorithmscomputequickly butfarfromtheoptimum bettersuitedforjoinoptimizations althoughrequirealongerrunningtimeSolutionspaceExceptthestarjoingraph thebushytreeispreferablethanleft deepprocessingtrees Theextensibilityofrandomizedandgeneticalgorithms Multi tablejoinoverview Query DrivenapproachesQueryworkloadQueryfeedbackMultidimensionalhistogramSASHalgorithmAdvantageanddisadvantageData DrivenapproachesStatisticalChi squaretest Log linearmodelProbabilityBayesiannetwork MarkovnetworkFullscanvs SamplehardFDs softFDs Correlation Attributecorrelationdetection BHUNT AutomaticDiscoveryofFuzzyAlgebraicConstraintsinRelationalDataExample Attributecorrelationdetection OverviewofBHUNTAlgebraicConstraintsExamplea1 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 OverviewofBHUNTGeneratingCandidatesC a1 a2 P GeneratingPairingRulesTurningPairingRulesIntoCandidatesIdentifyingFuzzyConstraintsConstructingBumpIntervals byapplyingstatisticalhistogramming segmentation orclusteringtechniquestoasampleofthecolumnvaluesChoosingtheSampleSize Thesamplesizeisselectedtocontrolthenumberof exception recordsthatfailtosatisfytheconstraint ExploitingtheConstraintsIdentifythemostusefulsetofconstraints andcreate exceptiontables toholdalloftheexceptionrecords Modifythequeriestoincorporatetheconstraintstheoptimizerusestheconstraintstoidentifynew moreefficientaccesspaths Attributecorrelationdetection ExperimentalresultsofBHUNT Attributecorrelationdetection CORDS AutomaticDiscoveryofCorrelationsandSoftFunctionalDependencies Attributecorrelationdetection CORDS AutomaticDiscoveryofCorrelationsandSoftFunctionalDependenciessoftfunctionaldependenciesC1 C2 thevalueofC1determinesthevalueofC2notwithcertainty butmerelywithhighprobability hardfunctionaldependenciesthevalueofC1completelydeterminesthevalueofC2 Attributecorrelationdetection CORDSoverviewFirst EnumeratingandPruningPruningruleTypeconstraintStatisticalconstraintParingconstraintWorkloadconstraintIdentifytrivialcases Attributecorrelationdetection CORDSoverview Attributecorrelationdetection Analyzedistinctvalueofsampledcolumn totestforSOFTFD SoftFD Chi squaredanalysis totestforstatisticaldependency Correlated ColumnGroup Top kpair YES NO YES CORDSdiscoversthreepropertyandrelationshipTrivialcases soft keys trivial columnSoftFDsC1 C2 C1 C1 C2 CORDSestimatesthe C1 and C1 C2 usingsampleCorrelationsDetectstatisticaldependenceusingthesample basedchi squaredanalysis Attributecorrelationdetection CORDSandqueryoptimizationaqueryhavingaselectionpredicatep1 p2 p1 Make Honda andp2 Model Accord trueselectivity p1 p2 1 10 na veestimate Sp1 p2 1 Make 1 Model 1 7 1 8 1 56 adjustedestimate na veestimate Make Model Make Model 1 56 56 9 1 9 Attributecorrelationdetection CORDSexperimentalresultSyntheticData TheAccidentsdatabaseBenchmarkingData TheTPC HbenchmarkReal worldData includeasubsetoftheCensusdatabaseandtheAutodatabase Attributecorrelationdetection CORDSexperimentalresult Attributecorrelationdetection CORDSexperimentalresult Attributecorrelationdetection COCA MoreAccurateMultidimensionalHistogramsoutofMoreAccurateCorrelationsDetectionrobustandinformativemetric entropycorrelationcoefficientsanovelyetsimplekindofmulti dimensionalsynopses COCA Histtocopewithdifferentcorrelations Attributecorrelationdetection Entropycorrelationcoefficients Attributecorrelationdetection MeritsofCOCASimpleandstraightforwardAccurateandrobustInformativeandunified Attributecorrelationdetection DifferenthistogramsfordifferentdegreesofcorrelationsHistogramsforvaluesparsityMHIST squeezingHistogramsformutualindependenceAVIassumptionHistogramsforothersituationsMHist MaxDiffhistogramsOtherimprovementsdiscardingemptybuckets Attributecorrelationdetection ExperimentsCORDS 1 0 39 0 29 3 0 45 0 58 Attributecorrelationdetection Experiments Attributecorrelationdetection StarGazingfromatopyourDB2z OSDatabaseServerIndexkeyfeedbackTheproblemsare Thecartesianjoindifficulttocreatesuitablemulti columnindexesunlessthecombinationoffilteringdimensionsthatareincludedinthequeriesareknown Starjoin StarGazingfromatopyourDB2z OSDatabaseServerPAIR WISEJOIN Starjoin StarGazingfromatopyourDB2z OSDatabaseServerPerformance Starjoin Starjoinrevisited Performanceinternalsforclusterarchitectures Starjoin Clu