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

多表连接查询优化的相关研究,吕彬2009.3.5,1,motivation,图中表示连接顺序对查询效率的影响：准确估计选择度要考虑属性间的相关性问题关键：高效地计算属性间的相关度,2,Agenda,Multi-tablejoinoverviewHeuristicandrandomizedoptimizationforthejoinorderingproblemMichaelSteinbrunn，etal,TheVLDBJournal(1997)6:191208AttributecorrelationdetectionBHUNT:AutomaticDiscoveryofFuzzyAlgebraicConstraintsinRelationalDataPaulG.BrownPeterJ.Haas,Proceedingsofthe29thVLDBConference,2003CORDS:AutomaticDiscoveryofCorrelationsandSoftFunctionalDependenciesIhabF.Ilyas，VolkerMarkl,etal,SIGMOD2004,June1318,2004,COCA:MoreAccurateMultidimensionalHistogramsoutofMoreAccurateCorrelationsDetectionCAOWei1,QINXiongpai,WANGShan,WAIM2008StarjoinStarGazingfromatopyourDB2z/OSDatabaseServerTerryPurcell,etal,IntelligentOptimizerStarjoinrevisited:PerformanceinternalsforclusterarchitecturesJosepAguilar-Saborit,DataalthoughrequirealongerrunningtimeSolutionspaceExceptthestarjoingraph,thebushytreeispreferablethanleft-deepprocessingtrees.Theextensibilityofrandomizedandgeneticalgorithms,Multi-tablejoinoverview,17,Query-DrivenapproachesQueryworkloadQueryfeedbackMultidimensionalhistogramSASHalgorithmAdvantageanddisadvantageData-DrivenapproachesStatisticalChi-squaretest,Log-linearmodelProbabilityBayesiannetwork,MarkovnetworkFullscanvs.SamplehardFDs,softFDs,Correlation,Attributecorrelationdetection,18,BHUNT:AutomaticDiscoveryofFuzzyAlgebraicConstraintsinRelationalDataExample,Attributecorrelationdetection,19,OverviewofBHUNTAlgebraicConstraintsExamplea1:deliveries.deliveryDate,a2:orders.shipDate,:asthesubtractionoperator,P:orders.orderID=deliveries.orderID,I=2,3,4,512,13,.,1931,32,33,34,35.,Attributecorrelationdetection,20,OverviewofBHUNTGeneratingCandidatesC=(a1,a2,P,).GeneratingPairingRulesTurningPairingRulesIntoCandidatesIdentifyingFuzzyConstraintsConstructingBumpIntervals,byapplyingstatisticalhistogramming,segmentation,orclusteringtechniquestoasampleofthecolumnvaluesChoosingtheSampleSize,Thesamplesizeisselectedtocontrolthenumberof“exception”recordsthatfailtosatisfytheconstraint.ExploitingtheConstraintsIdentifythemostusefulsetofconstraints,andcreate“exceptiontables”toholdalloftheexceptionrecords.Modifythequeriestoincorporatetheconstraintstheoptimizerusestheconstraintstoidentifynew,moreefficientaccesspaths.,Attributecorrelationdetection,21,ExperimentalresultsofBHUNT,Attributecorrelationdetection,22,CORDS:AutomaticDiscoveryofCorrelationsandSoftFunctionalDependencies.,Attributecorrelationdetection,23,CORDS:AutomaticDiscoveryofCorrelationsandSoftFunctionalDependenciessoftfunctionaldependenciesC1=C2,thevalueofC1determinesthevalueofC2notwithcertainty,butmerelywithhighprobability.hardfunctionaldependenciesthevalueofC1completelydeterminesthevalueofC2.,Attributecorrelationdetection,24,CORDSoverviewFirst:EnumeratingandPruningPruningruleTypeconstraintStatisticalconstraintParingconstraintWorkloadconstraintIdentifytrivialcases,Attributecorrelationdetection,25,CORDSoverview,Attributecorrelationdetection,Analyzedistinctvalueofsampledcolumn(totestforSOFTFD),SoftFD?,Chi-squaredanalysis(totestforstatisticaldependency),Correlated?,ColumnGroup(Top-kpair),YES,NO,YES,26,CORDSdiscoversthreepropertyandrelationshipTrivialcases“soft”keys“trivial”columnSoftFDsC1=C2|C1|/|C1,C2|CORDSestimatesthe|C1|and|C1,C2|usingsampleCorrelationsDetectstatisticaldependenceusingthesample-basedchi-squaredanalysis,Attributecorrelationdetection,27,CORDSandqueryoptimizationaqueryhavingaselectionpredicatep1p2,p1=“Make=Honda”andp2=“Model=Accord”.trueselectivity:p1p2=1/10.naveestimate:Sp1p2=1/|Make|1/|Model|=1/71/8=1/56,adjustedestimate:naveestimate*|Make|Model|/|Make,Model|=1/56*56/9=1/9,Attributecorrelationdetection,28,CORDSexperimentalresultSyntheticData:TheAccidentsdatabaseBenchmarkingData:TheTPC-HbenchmarkReal-worldData:includeasubsetoftheCensusdatabaseandtheAutodatabase,Attributecorrelationdetection,29,CORDSexperimentalresult,Attributecorrelationdetection,30,CORDSexperimentalresult,Attributecorrelationdetection,31,COCA:MoreAccurateMultidimensionalHistogramsoutofMoreAccurateCorrelationsDetectionrobustandinformativemetricentropycorrelationcoefficientsanovelyetsimplekindofmulti-dimensionalsynopsesCOCA-Histtocopewithdifferentcorrelations,Attributecorrelationdetection,32,Entropycorrelationcoefficients,Attributecorrelationdetection,33,MeritsofCOCASimpleandstraightforwardAccurateandrobustInformativeandunified,Attributecorrelationdetection,34,DifferenthistogramsfordifferentdegreesofcorrelationsHistogramsforvaluesparsityMHIST+squeezingHistogramsformutualindependenceAVIassumptionHistogramsforothersituationsMHist-MaxDiffhistogramsOtherimprovementsdiscardingemptybuckets,Attributecorrelationdetection,35,ExperimentsCORDS:#1(0.39,0.29),#3(0.45,0.58),Attributecorrelationdetection,36,Experiments,Attributecorrelationdetection,37,StarGazingfromatopyourDB2z/OSDatabaseServerIndexkeyfeedbackTheproblemsare:Thecartesianjoindifficulttocreatesuitablemulti-columnindexesunlessthecombinationoffilteringdimensionsthatareincludedinthequeriesareknown.,Starjoin,38,StarGazingfromatopyourDB2z/OSDatabaseServerPAIR-WISEJOIN,Starjoin,39,StarGazingfromatopyourDB2z/OSDatabaseServerPerformance,Starjoin,40,Starjoinrevisited:Performanceinternalsforclusterarchitectures,Starjoin,41,Clusterarchitecturesandhorizontalpartitioningpartitioningschemes:roundrobin,rangepartitioninghashpartitioningCollocatedandnon-collocatedRepartitioningOperator,Starjoin,42,StarjoinprocessingtechniquesBitmapjoin(BJ)size|T|S|bitslargesizeoftheindicesthemaintenanceoftheseindicesMultihierarchicalclustering(MHC)reducingthenumberofI/Oaccessestothefacttable.achunk-basedfilesystemspeci