白色IT商务企划：数据库工程师工作分析SQLQueryO

DavidJ.DeWittMicrosoftJimGraySystemsLabMadison,Wisconsindewitt@©2010MicrosoftCorporation.

Allrightsreserved.

Thispresentationisforinformationalpurposesonly.

Microsoftmakesnowarranties,expressorimpliedinthispresentation.SQLQueryOptimization:WhyIsItSoHardToGetRight?2IamrunningoutofthingstotalkaboutStillnomotorcycletorideacrossthestageMywifedecidedtoshowup&seewhatallthefusswasabout!(Sheisprobablytheonlyonenottweetingbackthere)AThirdKeynote?GeneratingallthisPowerPointtakesmedaysanddays(unlikemyboss,Idonothavepeopletodomyslidedecks)Day3Day2Day1The“ImpressIndex”AThirdKeynote?1GottoshowoffthePDWApplianceCool!Myboss’sboss(TedKummert)2GottotellyouaboutSQL11Awesome!Myboss(QuentinClark)3YouAreHereMe(DavidDeWitt)PossiblyIMPRESSYOU?HowcanIHowAboutaQuiztoStart!4Whopaintedthispicture?Mondrian?Picasso?Ingres?ActuallyitwastheSQLServerqueryoptimizer!!PlanspaceforTPC-Hquery8astheparametervaluesforAcct-BalandExtendedPricearevariedEachcolorrepresentsadifferentqueryplanYikes!P1P2P3P4SQLServerWhoIsThisGuyAgain?DeWittSpent32yearsasacomputerscienceprofessorattheUniversityofWisconsinJoinedMicrosoftinMarch2008RunstheJimGraySystemsLabinMadison,WILabiscloselyaffiliatedwiththeDBgroupatUniversityofWisconsin3facultyand8graduatestudentsworkingonprojectsBuiltanalyticsandsemijoincomponentsofPDWV1.CurrentlyworkingonanumberoffeaturesforPDWV2MToday…IamgoingtotalkaboutSQLqueryoptimizationYouvotedforthistopiconthePASSwebsiteDon’tblamemeifyoudidn’tvoteandwantedtohearaboutmap-reduceandno-sqldatabasesystemsinsteadMyhopeisthatyouwillleaveunderstandingwhyalldatabasesystemssometimesproducereallybadplansStartingwiththefundamentalprincipalsQueryOptimizationMap-ReduceAnonymousQuote “Queryoptimizationisnotrocketscience.Whenyouflunkoutofqueryoptimization,wemakeyougobuildrockets.”7TheRoleoftheQueryOptimizer

(100,000ftview)QueryOptimizerSQLStatementAwesomeQueryPlanMagicHappensWhat’stheMagic?Selecto_year,

sum(casewhennation='BRAZIL'thenvolumeelse0end)/sum(volume)from(selectYEAR(O_ORDERDATE)aso_year,

L_EXTENDEDPRICE*(1-L_DISCOUNT)asvolume,

n2.N_NAMEasnationfromPART,SUPPLIER,LINEITEM,ORDERS,CUSTOMER,NATIONn1,

NATIONn2,REGIONwhereP_PARTKEY=L_PARTKEYandS_SUPPKEY=L_SUPPKEYandL_ORDERKEY=O_ORDERKEYandO_CUSTKEY=C_CUSTKEYandC_NATIONKEY=n1.N_NATIONKEYandn1.N_REGIONKEY=R_REGIONKEY

andR_NAME='AMERICA‘andS_NATIONKEY=n2.N_NATIONKEY

andO_ORDERDATEbetween'1995-01-01'and'1996-12-31'andP_TYPE='ECONOMYANODIZEDSTEEL'andS_ACCTBAL<=constant-1andL_EXTENDEDPRICE<=constant-2)asall_nationsgroupbyo_year

orderbyo_yearConsiderQuery8oftheTPC-Hbenchmark:Plan1Plan2Plan3Plan4Plan522millionplans…Thereabout22million

alternativewaysofexecutingthisquery!AverybighaystacktobesearchingthroughTheQOmustselectaplanthatrunsinsecondsorminutes,notdaysorweeks!Shouldnottakehoursordaystopickaplan!SomeHistoricalBackgroundCost-basedqueryoptimizationwasinventedbyPatSelingeraspartoftheIBMSystemRprojectinthelate1970s(SystemRbecameDB2)RemainsthehardestpartofbuildingaDBMS30+yearslaterProgressishinderedbyfearofregressionsFartoofrequentlytheQOpicksaninefficientplanSituationfurthercomplicatedbyadvancesinhardwareandtherestoftheDBMSsoftwareHardwareis1000XbiggerandfasterDBsoftwareis10XfasterQueriesoverhugeamountsofdataarepossibleIFtheQOpickstherightplan10SystemRHardwareSoftwareQueries1000X10XHuge!DatabaseSystemMorePrecisely:

TheRoleoftheQueryOptimizer11TransformSQLqueriesintoanefficientexecutionplanQueryExecutionEngineQueryOptimizerParserSQLQueryLogicaloperatortreePhysicaloperatortreeLogicaloperators:whattheydoe.g.,union,selection,project,join,groupingPhysicaloperators:howtheydoite.g.,nestedloopjoin,sort-mergejoin,hashjoin,indexjoinAFirstExample12QueryExecutionEngineQueryOptimizerParserSELECT

Average(Rating)FROMReviews

WHEREMID=932ReviewsDateCIDMIDRating…………LogicaloperatortreeAvg(Rating)Select

MID=932ReviewsQueryPlan#1Avg_agg

[Cnt,Sum]ScanReviewsFilter

MID=932Avg_agg

[Cnt,Sum]IndexLookup

MID=932MIDIndexReviewsQueryPlan#2orQueryPlan#1PlanstartsbyscanningtheentireReviewstable#ofdiskI/Oswillbeequaltothe#ofpagesintheReviewstableI/Oswillbesequential.EachI/Owillrequireabout0.1milliseconds(0.0001seconds)Filterpredicate“MID=932”isappliedtoallrowsOnlyrowsthatsatisfythepredicatearepassedontotheaveragecomputation13Avg_agg

[Cnt,Sum]ScanReviewsFilter

MID=932QueryPlan#2MIDindexisusedtoretrieveonlythoserowswhoseMIDfield(attribute)isequalto932Sinceindexisnot“clustered”,aboutonediskI/OwillbeperformedforeachrowEachdiskI/Owillrequirearandomseekandwilltakeabout3milliseconds(ms)Retrievedrowswillbepassedtotheaveragecomputation14Avg_agg

[Cnt,Sum]IndexLookup

MID=932MIDIndexReviewsWhichPlanWillbeFaster?Queryoptimizermustpickbetweenthetwoplansbyestimatingthecost

ofeachToestimatethecostofaplan,theQOmust:EstimatetheselectivityofthepredicateMID=932CalculatethecostofbothplansintermsofCPUtimeandI/OtimeTheQOusesstatistics

abouteachtabletomaketheseestimatesThe“best”plandependsonhowmanyreviewsthereareformoviewithMID=93215QueryPlan#1Avg_agg

[Cnt,Sum]ScanReviewsFilter

MID=932Avg_agg

[Cnt,Sum]IndexLookup

MID=932MIDIndexReviewsQueryPlan#2Vs.HowmanyreviewsforthemoviewithMID=932willtherebe?BestQueryPlanor???ASlightlyMoreComplexQueryConsiderthequery:Optimizermightfirstenumeratethreephysicalplans:16Filter

Rating>9SequentialScanReviewsFilter

7/1<Date>7/31RatingIndexFilter7/1<Date<7/31IndexLookupRating>9ReviewsFilterRating>9

IndexLookup7/1<Date>7/31

ReviewsDateIndexSF=.01SF=.01SF=.10SF=.10Cost=11secondsCost=100secondsCost=25secondsThen,estimateselectivityfactorsThen,calculatetotalcostFinally,picktheplanwiththelowestcostSELECT*FROMReviewsWHERE7/1<date<7/31AND

rating>9EnumeratelogicallyequivalentplansbyapplyingequivalencerulesForeachlogicallyequivalentplan,enumerateallalternativephysicalqueryplansEstimatethecostofeachofthealternativephysicalqueryplansRuntheplanwithlowestestimatedoverallcostQueryOptimization:

TheMainSteps✓2134EquivalenceRules18Selectandjoinoperatorscommute

witheachotherSelectSelectCustomersSelectSelectCustomersJoinCustomersReviewsJoinReviewsCustomersJoinCustomersReviewsJoinMoviesJoinCustomersJoinReviewsMoviesJoinoperatorsareassociativeEquivalenceRules(cont.)19Project

[CID,Name]CustomersProject

[Name]ProjectoperatorscascadeProject

[Name]CustomersSelectoperatordistributesoverjoinsSelectJoinCustomersReviewsSelectJoinCustomersReviewsExampleofEquivalentLogicalPlansSELECTM.Title,M.DirectorFROMMoviesM,ReviewsR,CustomersC

WHEREC.City=“N.Y.”ANDR.Rating>7ANDM.MID=R.MIDANDC.CID=R.CIDOnepossiblelogicalplan:20JoinSelectC.City=“N.Y”SelectR.Rating>7JoinC.CID=R.CIDR.MID=M.MIDCustomersReviewsProjectM.Title,M.DirectorMoviesMIDTitleDirectorEarnings1

2

…

CIDNameAddressCity5

11

…

DateCIDMIDRating7/311287/3524…Findtitlesanddirectornamesofmovieswitharating>7fromcustomersresidinginNYCCustomersReviewsMoviesFiveLogically“Equivalent”Plans21SelectSelectJoinCustomersReviewsProjectJoinMoviesSelectSelectJoinCustomersReviewsProjectJoinMoviesSelectSelectJoinCustomersReviewsProjectJoinMoviesSelectJoinCustomersReviewsJoinMoviesSelectProjectThe“original”planSelectsdistributeoverjoinsruleJoinCustomersReviewsJoinMoviesSelectProjectSelectSelectscommuteruleFourMore!22SelectSelectJoinCustomersReviewsProjectJoinMoviesThe“original”planSelectCustomersSelectReviewsProjectJoinMoviesJoinSelectCustomersSelectReviewsProjectJoinMoviesJoinSelectCustomersSelectReviewsProjectJoinMoviesJoinSelectReviewsJoinMoviesCustomersProjectJoinSelectJoincommutativityruleSelectcommutativityrule9LogicallyEquivalentPlans,

InTotal23SelectSelectJoinCustomersReviewsProjectJoinMoviesSelectSelectJoinCustomersReviewsProjectJoinMoviesSelectSelectJoinCustomersReviewsProjectJoinMoviesSelectJoinCustomersReviewsJoinMoviesSelectProjectSelectCustomersSelectReviewsProjectJoinMoviesJoinSelectCustomersSelectReviewsProjectJoinMoviesJoinSelectReviewsJoinMoviesCustomersProjectJoinSelectSelectCustomersSelectReviewsProjectJoinMoviesJoinJoinCustomersReviewsJoinMoviesSelectProjectSelectAll9logicalplanswillproducethesameresultForeachofthese9plansthereisalargenumberofalternativephysicalplansthattheoptimizercanchoosefromEnumeratelogicallyequivalentplansbyapplyingequivalencerulesForeachlogicallyequivalentplan,enumerateallalternativephysicalqueryplansEstimatethecostofeachofthealternativephysicalqueryplansRuntheplanwithlowestestimatedoverallcostQueryOptimization:

TheMainSteps✓2134✓PhysicalPlanExampleAssumethattheoptimizerhas:Threejoinstrategiesthatitcanselectfrom:nestedloops(NL),sort-mergejoin(SMJ),andhashjoin(HJ)Twoselectionstrategies:sequentialscan(SS)andindexscan(IS)Consideroneofthe9logicalplansHereisonepossiblephysicalplan

25SelectSelectJoinCustomersReviewsProjectJoinMoviesSSISHJCustomersReviewsProjectNLMoviesThereareactually36possiblephysicalalternativesforthissinglelogicalplan.(Iwastoolazytodrawpicturesofall36).With9equivalentlogicalplans,thereare324=(9*36)physicalplansthattheoptimizermustenumerateandcostaspartofthesearchforthebestexecutionplanforthequeryAndthiswasaVERYsimplequery!Laterwewilllookathowdynamicprogrammingisusedtoexplorethespaceoflogicalandphysicalplansw/oenumeratingtheentireplanspaceEnumeratelogicallyequivalentplansbyapplyingequivalencerulesForeachlogicallyequivalentplan,enumerateallalternativephysicalqueryplansEstimatethecostofeachofthealternativephysicalqueryplans.EstimatetheselectivityfactorandoutputcardinalityofeachpredicateEstimatethecostofeachoperatorRuntheplanwithlowestestimatedoverallcostQueryOptimization:

TheMainSteps✓2134✓✓SelectivityEstimationTaskofestimatinghowmanyrowswillsatisfyapredicatesuchasMovies.MID=932Planqualityishighlydependentonqualityoftheestimatesthatthequeryoptimizermakes27Histograms

arethestandardtechniqueusedtoestimateselectivityfactorsforpredicatesonasingletableManydifferentflavors:Equi-WidthEqui-HeightMax-Diff…HistogramMotivation28#ofReviewsforeachcustomer(totalof939rows)CustomerID(CID)valuesinReviewsTableSomeexamples:#1)Predicate:CID=9

ActualSel.Factor=55/939=.059#2)Predicate:2<=CID<=3

ActualSel.Factor=135/939=.144Ingeneral,thereisnotenoughspaceinthecatalogstostoresummarystatisticsforeachdistinctattributevalueThesolution:

histogramsEqui-WidthHistogramExample29CIDValuesCountCount1-417-2013-169-125-8Equi-widthhistogramYikes!8Xerror!!AllbucketscoverroughlythesamekeyrangeExample#1:Predicate:CID=9ActualSel.Factor=55/939=.059EstimatedSel.Factor=(186/4)/939=.050Example#2:Predicate:CID=5ActualSel.Factor=10/939=.011EstimatedSel.Factor=(309/4)/993=.082Equi-HeightHistograms30CountCountEqui-heighthistogramDividerangessothatallbucketscontainroughlythesamenumberofvalues1-516-2012-159-117-86Example#2:Predicate:CID=6ActualSel.Factor=157/939=.167EstimatedSel.Factor=(157/1)/993=.167Example#2:Predicate:CID=6ActualSel.Factor=157/939=.167EstimatedSel.Factor=(309/4)/993=.082Example#1:Predicate:CID=5ActualSel.Factor=10/939=.011EstimatedSel.Factor=(309/4)/993=.082Example#1:Predicate:CID=5ActualSel.Factor=10/939=.011EstimatedSel.Factor=(156/5)/993=.033Equi-widthvs.Equi-Height311-417-2013-169-125-8Equi-widthEqui-height1-516-2012-159-117-86HistogramSummaryHistogramsareacriticaltoolforestimatingselectivityfactorsforselectionpredicates32Errorsstilloccur,however!OtherstatisticsstoredbytheDBMSforeachtableinclude#ofrows,#ofpages,…EnumeratelogicallyequivalentplansbyapplyingequivalencerulesForeachlogicallyequivalentplan,enumerateallalternativephysicalqueryplansEstimatethecostofeachofthealternativephysicalqueryplans.EstimatetheselectivityfactorandoutputcardinalityofeachpredicateEstimatethecostofeachoperatorRuntheplanwithlowestestimatedoverallcostQueryOptimization:

TheMainSteps✓2134✓✓EstimatingCostsTwokeycoststhattheoptimizerconsiders:I/Otime–costofreadingpagesfrommassstorageCPUtime–costofapplyingpredicatesandoperatingontuplesinmemoryActualvaluesarehighlydependentonCPUandI/OsubsystemonwhichthequerywillberunFurthercomplicatingthejobofthequeryoptimizerForaparalleldatabasesystemsuchasPDW,thecostofredistributing/shufflingrowsmustalsobeconsideredWereyoupayingattentionorupdatingyourFacebookpagewhenItalkedaboutparallelqueryprocessing2yearsago?34IO+CPUvs.AnExampleQuery:SELECTAvg(Rating)FROMReviews

WHEREMID=932Twophysicalqueryplans:35ReviewsDateCIDMIDRatingPlan#1Avg_agg

[Cnt,Sum]SequentialScanReviewsFilter

MID=932Avg_agg

[Cnt,Sum]IndexLookup

MID=932MIDIndexReviewsPlan#2Whichplanischeaper???CostXCostYPlan#136Avg_agg

[Cnt,Sum]ScanReviewsFilter

MID=932Filterisappliedto10Mrows

Theoptimizerestimatesthat100rowswillsatisfythepredicateTableis100Kpageswith100rows/pageSortedondateAveragecomputationisappliedto100rows

Reviewsisscannedsequentiallyat

100MB/secondI/Otimeofscanis8secondsAt0.1microseconds/row,filterconsumes1secondofCPUtimeAt0.1microseconds/row,avgconsumes.00001secondsofCPUtimeOptimizerestimatestotalexecutiontimeof9secondsCostofPlan#1Plan#237Avg_agg

[Cnt,Sum]IndexLookup

MID=932MIDIndexReviews

100rowsareestimatedtosatisfythepredicateAveragecomputationisappliedto100rowsAt0.1microseconds/row,averageconsumes.00001seconds

ofCPUtime

100rowsareretrievedusingtheMIDindexSincetableissortedondatefield(andnotMIDfield),eachI/OrequiresarandomdiskI/O–

about.003secondsperdiskI/OI/Otimewillbe.3secondsOptimizerestimatestotalexecutiontimeof0.3secondsTheestimateforPlan#1was9seconds,soPlan#2isclearlythebetterchoiceCostofPlan#2But…WhatiftheestimateofthenumberofrowsthatsatisfythepredicateMID=932isWRONG?E.g.10,000rowsinsteadof100rows38Non-clusteredIndexisbetterhereSequentialscanisbetterhereEstimatingJoinCostsThreebasicjoinmethods:Nested-loopsjoinSort-mergejoinHash-joinVerydifferentperformancecharacteristicsCriticalforoptimizertocarefullypickwhichmethodtousewhen39JoinSelectC.City=“NY”SelectR.Rating>7JoinC.CID=R.CIDR.MID=M.MIDCustomersReviewsProjectM.Title,M.DirectorMoviesSort-MergeJoinAlgorithmSortReviewsonMIDcolumn (unlessalreadysorted)SortMoviesonMIDcolumn (unlessalreadysorted)“Merge”twosortedtables: Scaneachtablesequentialintandem

{ ForcurrentrowrofReviews

ForcurrentrowmofMoviesifr.MID=m.MIDproduceoutputrowAdvancerandmcursors }40Cost=|R|+|M|I/OsMergeJoinSortSortReviews(|R|pages)Movies(|M|pages)Reviews.MID=Movies.MIDCost=4*|M|I/OsTotalI/Ocost=5*|R|+5*|M|I/OsCost=4*|R|I/OsMainIdea:SortRandM

onthejoincolumn(MID),thenscanthemtodoa``merge’’(onjoincolumn),andoutputresulttuples.Nested-LoopsJoinForeachpageRi,1≤i≤|R|,ofReviews{

ReadpageRifromdisk ForeachMj,1≤j≤|M|,ofMovies { ReadpageMjfromdisk ForallrowsronpageRi { ForallrowsmonpageMj { ifr.MID=m.MIDproduceoutputrow } } }}41I/OCost=|R|+|R|*|M|NestedLoopsJoinMovies

(|M|pages)Reviews

(|R|pages)Reviews.MID=Movies.MIDMainIdea:ScanR,andforeachtupleinRprobetuplesinM(byscanningit).Outputresulttuples.MainIdea:ScanR,andforeachtupleinRprobetuplesinM(byprobingitsindex).Outputresulttuples.Index-NestedLoopsForeachpageRi,1≤i≤|R|,ofReviews{

ReadpageRifromdisk ForallrowsronpageRi { UseMIDindexonMovies

tofetchrowswithMIDattributes=r.MID

Formoutputrowforeachreturnedrow}} 42Movies

(|M|pages)NestedLoopsJoinReviews

Reviews.MID=Movies.MIDIndexLookup

usingr.MIDMIDIndex(|R|pages)SortedondatecolumnCost=|R|+|R|*(||R||/|R|)*22I/Os:1indexI/O+1movieI/Oas

Reviewstableissortedondatecolumn

||R||is#ofrowsinR

||R||/|R|givestheaveragenumberof

rowsofRperpageNoticethatsinceReviewsisorderedontheDatecolumn(andnotMID),soeachrowoftheMoviestableretrievedincurstworandomdiskI/Os:onetotheindexandonetothetableEstimatingResultCardinalitiesConsiderthequerySELECT*FROMReviewsWHERE7/1<date<7/31ANDrating>9AssumeReviewshas1MrowsAssumefollowingselectivityfactors:43Sel.Factor#ofqualifyingrows7/1<date<7/310.1100,000Review>90.0110,000Howmanyoutputrowswillthequeryproduce?Ifpredicatesarenotcorrelated.1*.01*1M=1,000rowsIfpredicatesarecorrelatedcouldbeashighas.1*1M=100,000rowsWhydoesthismatter?ThisisWhy!Assumethat:Reviewstableis10,000pageswith80rows/pageMoviestableis2,000pagesTheprimaryindexonMoviesisontheMIDcolumn44JoinR.MID=M.MIDSelectReviewsProjectMoviesRating>9and

7/1<date<7/31TheconsequencesofincorrectlyestimatingtheselectivityofthepredicateonReviewscanbeHUGEINLNLSMNotethateachjoinalgorithmhasaregionwhereitprovidesthebestperformanceMultidimensionalHistogramsUsedtocapturecorrelationbetweenattributesA2-Dexample451-45-89-1213-1617-2010-2021-3031-4041-5051-6061-70ALittleBitAboutEstimatingJoinCardinalitiesQuestion:GivenajoinofR

andS,whatistherangeofpossibleresultsizes(in#oftuples)?SupposethejoinisonakeyforR

andS

Students(sid,sname,did),Dorm(did,d.addr)SelectS.sid,D.addressFromStudentsS,DormsDWhereS.did=D.didWhatisthecardinality?46Astudentcanonlyliveinatmost1dorm:eachStuplecanmatchwithatmost1Dtuplecardinality(SjoinD)=cardinalityofSGeneralcase:joinon{A}(where{A}iskeyforneither)estimateeachtuplerofRgeneratesuniformnumberofmatchesinSandeachtuplesofSgeneratesuniformnumberofmatchesinR,e.g.

SF=min(||R||*||S||/NKeys(A,S)

||S||*||R||/NKeys(A,R))e.g.,SELECTM.title,R.titleFROMMoviesM,ReviewsRWHEREM.title=R.titleMovies:100tuples,75uniquetitles

1.3rowsforeachtitleReviews:20tuples,10uniquetitles

2rowsforeachtitleEstimatingJoinCardinality=100*20/10=200=20*100/75=26.6EnumeratelogicallyequivalentplansbyapplyingequivalencerulesForeachlogicallyequivalentplan,enumerateallalternativephysicalqueryplansEstimatethecostofeachofthealternativephysicalqueryplans.EstimatetheselectivityfactorandoutputcardinalityofeachpredicateEstimatethecostofeachoperatorRuntheplanwithlowestestimatedoverallcostQueryOptimization:

TheMainSteps✓2134✓✓EnumerateHowbigistheplanspaceforaqueryinvolvingNtables?enumerateItturnsoutthattheanswerdependsonthe“shape”ofthequeryTwoCommonQuery“Shapes”49ABJoinJoinJoinJoinCDF“Star”JoinQueriesABCDFJoinJoinJoinJoin“Chain”JoinQueriesNumberoflogicallyequivalentalternatives#ofTablesStarChain22

244840538422463,8401,3448645,12054,9121018,579,4502,489,344Inpractice,“typical”queriesfallsomewherebetweenthesetwoextremesPruningthePlanSpaceConsideronlyleft-deepqueryplanstoreducethesearchspace50ABCJoinJoinJoinJoinEDLeftDeepJoinJoinJoinJoinEDABCBushy

StarJoinQueriesChainJoinQueries#ofTablesBushyLeft-DeepBushyLeftDeep2222244812

4085384482241663,8402401,344328645,12010,08054,9121281018,579,450725,7602,489,344512Thesearecountsoflogicalplansonly!With:3joinmethodsnjoinsinaqueryTherewillbe3nphysicalplansforeachlogicalplanExample:Foraleft-deep,8tablestarjoinquerytherewillbe:10,080differentlogicalplans22,044,960differentphysicalplans!!Solution:Usesomeformofdynamicprogramming

(eitherbottomuportopdown)tosearchtheplanspaceheuristicallySometimestheseheuristicswillcausethebestplantobemissed!!OptimizationisperformedinNpasses(ifNrelationsarejoined):Pass1:

Findthebest(lowestcost)1-relationplanforeachrelation.Pass2:Findthebestwaytojointheresultofeach1-relationplan(astheouter/lefttable)toanotherrelation(astheinner/righttable)togenerate

all2-relationplans.PassN:Findbestwaytojoinresultofa(N-1)-relationplan(asouter)totheN’threlationtogenerateallN-relationplans.Ateachpass,foreachsubsetofrelations,pruneallplansexceptthoseLowestcostplanoverall,plusLowestcostplanforeachinterestingorderoftherowsOrderby,groupby,aggregatesetc.handledasthefinalstepBottom-UpQOUsingDynamicProgrammingInspiteofpruningplanspace,thisapproachisstillexponentialinthe#oftables.

Interestingordersincludeordersthatfacilitatetheexecutionofjoins,aggregates,andorderbyclausessubsequentlybythequery52AASSAISBBSSCCSSCISDDSSDIS27387313429518AllsinglerelationplansAlltablesFirst,generateallsinglerelationplans:ASelectJoinJoinCSelectJoinDBSelectAnExample:Legend:SS–sequentialscan

IS–indexscan

–cost5Prune53BSS73ASSAIS2713DSS42CIS18AllsinglerelationplansafterpruningThen,AllTwoRelationPlansTwoRelationPlansStartingWithA54BSS73AIS27ASS13DSS42CIS18ASelectJoinJoinCSelectJoinDBSelectASSBSSNLJAISBSSNLJAISBSSSMJASSBSSSMJJoinSelectABA.a=B.a1013822315293SinglerelationplansPruneLet’sassumethereare2alternativejoinmethodsfortheQOtoselectfrom:NLJ=NestedLoopsJoinSMJ=SortMergeJoinTwoRelationPlansStartingWithB55SelectABJoinA.A=B.aBSSASSNLJBSSASSSMJBSSNLJAISBSSSMJAISSelectDBJoinB.b=D.bSelectCBJoinB.C=C.cBSSDSSNLJBSSDSSSMJNLJBSSCISBSSSMJCISASelectJoinJoinCSelectJoinDBSelect101331575629315204322321932SinglerelationplansBSS73AIS27ASS13DSS42CIS18PruneTwoRelationPlansStartingWithC56SelectCBJoinB.C=C.cNLJBSSCISBSSSMJCISASelectJoinJoinCSelectJoinDBSelect6520932SinglerelationplansBSS73AIS27ASS13DSS42CIS18PruneTwoRelationPlansStartingWithD57SelectDBJoinB.b=D.bDSSBSSNLJDSSBSSSMJASelectJoinJoinCSelectJoinDBSelect1520432SinglerelationplansBSS73AIS27ASS13DSS42CIS18PruneNext,AllThreeRelationPlans58AISBSSSMJDSSBSSSMJPrunedtworelationplansBSSSMJCISBSSSMJAISBSSDSSSMJBSSSMJCISASelectJoinJoinCSelectJoinDBSelectNext,AllThreeRelationPlans59AISBSSSMJFullyprunedtworelationplansBSSSMJCISBSSDSSSMJASelectJoinJoinCSelectJoinDBSelectNLJCISAISBSSSMJSMJCISAISBSSSMJDSSNLJAISBSSSMJDSSSMJAISBSSSMJ1)ConsideringtheTwoRelationPlansThatStartedWithANext,AllThreeRelationPlans60AISBSSSMJFullyprunedtworelationplansBSSSMJCISBSSDSSSMJASelectJoinJoinCSelectJoinDBSelectBSSDSSSMJASSNLJBSSDSSSMJASSSMJNLJAISBSSDSSSMJSMJAISBSSDSSSMJNLJCISBSSDSSSMJSMJCISBSSDSSSMJ2)ConsideringtheTwoRelationPlansThatStartedWithBNext,AllThreeRelationPlans61