这篇文章主要介绍“PostgreSQL中使用动态规划算法构造连接路径的实现函数是哪个”，在日常操作中，相信很多人在PostgreSQL中使用动态规划算法构造连接路径的实现函数是哪个问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”PostgreSQL中使用动态规划算法构造连接路径的实现函数是哪个”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

上节已解读了make_rel_from_joinlist->standard_join_search函数的主实现逻辑,下面重点介绍该函数中的join_search_one_level函数.

/**join_search_one_level*Considerwaystoproducejoinrelationscontainingexactly'level'*jointreeitems.(Thisisonestepofthedynamic-programmingmethod*embodiedinstandard_join_search.)Joinrelnodesforeachfeasible*combinationoflower-levelrelsarecreatedandreturnedinalist.*Implementationpathsarecreatedforeachsuchjoinrel,too.*规划如何生成包含匹配Leve(比如2个关系的连接/3个关系的连接等)连接关系。*(这是在standard_join_search中体现的动态规划算法的一个步骤。)*为较低Leve的关系创建新的连接关系亦即访问路径,通过链表的方式返回(root->join_rel_level)。**level:levelofrelswewanttomakethistime*root->join_rel_level[j],1<=j<level,isalistofrelscontainingjitems*level:关系的level,比如是2个关系还是3个关系的连接**Theresultisreturnedinroot->join_rel_level[level].*结果通过root->join_rel_level[level]*/voidjoin_search_one_level(PlannerInfo*root,intlevel){List**joinrels=root->join_rel_level;ListCell*r;intk;Assert(joinrels[level]==NIL);/*Setjoin_cur_levelsothatnewjoinrelsareaddedtoproperlist*/root->join_cur_level=level;//当前的Level/**First,considerleft-sidedandright-sidedplans,inwhichrelsof*exactlylevel-1memberrelationsarejoinedagainstinitialrelations.*Weprefertojoinusingjoinclauses,butifwefindareloflevel-1*membersthathasnojoinclauses,wewillgenerateCartesian-product*joinsagainstallinitialrelsnotalreadycontainedinit.*首先,规划left-sided和right-sided的计划,这些计划已由初始关系连接为level-1级的Relation.*PG使用连接条件进行连接,但如果发现level-1成员中没有连接条件,那么PG将会*为未包含此条件的初始关系生成笛卡尔积.*/foreach(r,joinrels[level-1])//遍历上一级生成的关系{RelOptInfo*old_rel=(RelOptInfo*)lfirst(r);//获取上一级的RelOptInfoif(old_rel->joininfo!=NIL||old_rel->has_eclass_joins||has_join_restriction(root,old_rel))//存在连接条件{/**Therearejoinclausesorjoinorderrestrictionsrelevantto*thisrel,soconsiderjoinsbetweenthisreland(only)those*initialrelsitislinkedtobyaclauseorrestriction.*存在与此rel相关的连接条件或连接顺序限制，*因此仅规划此rel与通过条件子句或约束条件链接在一起的初始rels.**Atlevel2thisconditionissymmetric,sothereisnoneedto*lookatinitialrelsbeforethisoneinthelist;wealready*consideredsuchjoinswhenwewereattheearlierrel.(The*mirror-imagejoinsarehandledautomaticallybymake_join_rel.)*Inlaterpasses(level>2),wejoinrelsofthepreviouslevel*toeachinitialreltheydon'talreadyincludebuthaveajoin*clauseorrestrictionwith.*leve=2时，这个条件是对称的，所以不需要在关注链表中此rel前的rels;*在处理在此rel前的rels时,已处理这样的连接.(make_join_rel函数自动处理镜像连接)。*level>2时，PG将上一级别生成的rels逐一与尚未处理的初始rel(存在连接条件或约束条件)进行连接.**/ListCell*other_rels;if(level==2)/*considerremaininginitialrels*/other_rels=lnext(r);//level=2,只需关注此rel之后的relelse/*considerallinitialrels*/other_rels=list_head(joinrels[1]);//level>2,从第1级开始尝试make_rels_by_clause_joins(root,old_rel,other_rels);//创建连接}else//不存在连接条件{/**Oops,wehavearelationthatisnotjoinedtoanyother*relation,eitherdirectlyorbyjoin-orderrestrictions.*Cartesianproducttime.*有一个relation与其他relation没有连接条件(直接或通过join-order约束)*笛卡尔时间到了!**Weconsideracartesianproductwitheachnot-already-included*initialrel,whetherithasotherjoinclausesornot.At*level2,iftherearetwoormoreclauselessinitialrels,we*willredundantlyconsiderjoiningtheminbothdirections;but*suchcasesaren'tcommonenoughtojustifyaddingcomplexityto*avoidtheduplicatedeffort.*考察每一个尚未处理的初始rel(无论其是否有约束条件).*在level2,如存在2个或以上的无条件初始rels,PG可能会出现重复处理的情况.*/make_rels_by_clauseless_joins(root,old_rel,list_head(joinrels[1]));//创建无条件连接}}/**Now,consider"bushyplans"inwhichrelationsofkinitialrelsare*joinedtorelationsoflevel-kinitialrels,for2<=k<=level-2.*现在考察"稠密计划",其中klevel的rels与level-k的rel想连接.其中:2<=k<=level-2**Weonlyconsiderbushy-planjoinsforpairsofrelswherethereisa*suitablejoinclause(orjoinorderrestriction),inordertoavoid*unreasonablegrowthofplanningtime.*这里只考虑存在连接条件(或者join-order限制)的关系对,以避免计划时间的大幅增加*/for(k=2;;k++){intother_level=level-k;/**Sincemake_join_rel(x,y)handlesbothx,yandy,xcases,weonly*needtogoasfarasthehalfwaypoint.*/if(k>other_level)break;foreach(r,joinrels[k]){RelOptInfo*old_rel=(RelOptInfo*)lfirst(r);ListCell*other_rels;ListCell*r2;/**Wecanignorerelationswithoutjoinclauseshere,unlessthey*participateinjoin-orderrestrictions---thenwemighthave*toforceabushyjoinplan.*/if(old_rel->joininfo==NIL&&!old_rel->has_eclass_joins&&!has_join_restriction(root,old_rel))continue;if(k==other_level)other_rels=lnext(r);/*同一层次,只考虑余下的rel,onlyconsiderremainingrels*/elseother_rels=list_head(joinrels[other_level]);//不同层次,尝试所有的for_each_cell(r2,other_rels){RelOptInfo*new_rel=(RelOptInfo*)lfirst(r2);if(!bms_overlap(old_rel->relids,new_rel->relids))//relids不存在包含关系{/**OK,wecanbuildareloftherightlevelfromthis*pairofrels.Dosoifthereisatleastonerelevant*joinclauseorjoinorderrestriction.*/if(have_relevant_joinclause(root,old_rel,new_rel)||have_join_order_restriction(root,old_rel,new_rel))//存在连接条件或者join-order约束{(void)make_join_rel(root,old_rel,new_rel);//创建连接}}}}}/*----------*Last-ditcheffort:ifwefailedtofindanyusablejoinssofar,force*asetofcartesian-productjoinstobegenerated.Thishandlesthe*specialcasewherealltheavailablerelshavejoinclausesbutwe*cannotuseanyofthoseclausesyet.Thiscanonlyhappenwhenweare*consideringajoinsub-problem(asub-joinlist)andalltherelsinthe*sub-problemhaveonlyjoinclauseswithrelsoutsidethesub-problem.*Anexampleis**SELECT...FROMaINNERJOINbONTRUE,c,d,...*WHEREa.w=c.xandb.y=d.z;**Ifthe"aINNERJOINb"sub-problemdoesnotgetflattenedintothe*upperlevel,wemustbewillingtomakeacartesianjoinofaandb;*butthecodeabovewillnothavedoneso,becauseitthoughtthatboth*aandbhavejoinclauses.Weconsideronlyleft-sidedandright-sided*cartesianjoinsinthiscase(nobushy).*----------*/if(joinrels[level]==NIL){/**Thisloopisjustlikethefirstone,exceptwealwayscall*make_rels_by_clauseless_joins().*/foreach(r,joinrels[level-1]){RelOptInfo*old_rel=(RelOptInfo*)lfirst(r);make_rels_by_clauseless_joins(root,old_rel,list_head(joinrels[1]));}/*----------*Whenspecialjoinsareinvolved,theremaybenolegalway*tomakeanN-wayjoinforsomevaluesofN.Forexampleconsider**SELECT...FROMt1WHERE*xIN(SELECT...FROMt2,t3WHERE...)AND*yIN(SELECT...FROMt4,t5WHERE...)**Wewillflattenthisquerytoa5-wayjoinproblem,butthereare*no4-wayjoinsthatjoin_is_legal()willconsiderlegal.Wehave*toacceptfailureatlevel4andgoontodiscoveraworkable*bushyplanatlevel5.**However,iftherearenospecialjoinsandnolateralreferences*thenjoin_is_legal()shouldneverfail,andsothefollowingsanity*checkisuseful.*----------*/if(joinrels[level]==NIL&&root->join_info_list==NIL&&!root->hasLateralRTEs)elog(ERROR,"failedtobuildany%d-wayjoins",level);}}//-------------------------------------------------------------------has_join_restriction/**has_join_restriction*Detectwhetherthespecifiedrelationhasjoin-orderrestrictions,*duetobeinginsideanouterjoinoranIN(sub-SELECT),*orparticipatinginanyLATERALreferencesormulti-relPHVs.*判断传入的relation是否含有join-order限制条件.存在于外连接/IN(sub-SELECT)子查询/LATERAL依赖/多关系PHVs**Essentially,thistestswhetherhave_join_order_restriction()could*succeedwiththisrelandsomeotherone.It'sOKifwesometimes*say"true"incorrectly.(Therefore,wedon'tbotherwiththerelatively*expensivehas_legal_joinclausetest.)*/staticboolhas_join_restriction(PlannerInfo*root,RelOptInfo*rel){ListCell*l;if(rel->lateral_relids!=NULL||rel->lateral_referencers!=NULL)returntrue;//存在lateralforeach(l,root->placeholder_list){PlaceHolderInfo*phinfo=(PlaceHolderInfo*)lfirst(l);if(bms_is_subset(rel->relids,phinfo->ph_eval_at)&&!bms_equal(rel->relids,phinfo->ph_eval_at))returntrue;//PHVs}foreach(l,root->join_info_list){SpecialJoinInfo*sjinfo=(SpecialJoinInfo*)lfirst(l);/*ignorefulljoins---othermechanismspreservetheirordering*/if(sjinfo->jointype==JOIN_FULL)continue;//不考虑全外连接/*ignoreifSJisalreadycontainedinrel*/if(bms_is_subset(sjinfo->min_lefthand,rel->relids)&&bms_is_subset(sjinfo->min_righthand,rel->relids))continue;//SJ在rel中,不考虑/*restrictedifitoverlapsLHSorRHS,butdoesn'tcontainSJ*/if(bms_overlap(sjinfo->min_lefthand,rel->relids)||bms_overlap(sjinfo->min_righthand,rel->relids))returntrue;}returnfalse;}//-------------------------------------------------------------------make_rels_by_clause_joins/**make_rels_by_clause_joins*Buildjoinsbetweenthegivenrelation'old_rel'andotherrelations*thatparticipateinjoinclausesthat'old_rel'alsoparticipatesin*(orparticipateinjoin-orderrestrictionswithit).*Thejoinrelsarereturnedinroot->join_rel_level[join_cur_level].*创建old_rel和其他rel的连接(两者存在连接条件)**Note:atlevelsabove2wewillgeneratethesamejoinedrelationin*multipleways---forexample(ajoinb)joincisthesameRelOptInfoas*(bjoinc)joina,thoughthesecondcasewilladdadifferentsetofPaths*toit.Thisisthereasonforusingthejoin_rel_levelmechanism,which*automaticallyensuresthateachnewjoinrelisonlyaddedtothelistonce.*注意:在level>2时,PG会通过多种方式生成同样的连接rel(joinedrelation).*比如:(ajoinb)joinc与(bjoinc)joina最终结果是一样的RelOptInfo,虽然第*2种方法会添加一些不同的访问路径集合在其中.*这其实是使用join_rel_level的原因,确保每个新joinrel只加入到合适的链表中**'old_rel'istherelationentryfortherelationtobejoined*'other_rels':thefirstcellinalinkedlistcontainingtheother*relstobeconsideredforjoining*old-rel:需要连接的rel*other-rel:候选关系链表中的的第一个cell**Currently,thisisonlyusedwithinitialrelsinother_rels,butit*willworkforjoiningtojoinrelstoo.*看起来似乎只对other_rels中的初始rels有用,但其实对于连接生成的joinrels同样会生效.*/staticvoidmake_rels_by_clause_joins(PlannerInfo*root,RelOptInfo*old_rel,ListCell*other_rels){ListCell*l;for_each_cell(l,other_rels)//遍历链表{RelOptInfo*other_rel=(RelOptInfo*)lfirst(l);//获取其中的RelOptInfoif(!bms_overlap(old_rel->relids,other_rel->relids)&&(have_relevant_joinclause(root,old_rel,other_rel)||have_join_order_restriction(root,old_rel,other_rel)))//reldis不同而且存在连接关系&连接顺序约束{(void)make_join_rel(root,old_rel,other_rel);//创建连接}}}//----------------------------------------------------have_relevant_joinclause/**have_relevant_joinclause*Detectwhetherthereisajoinclausethatinvolves*thetwogivenrelations.*给定两个relations,检查两者是否存在连接条件**Note:thejoinclausedoesnothavetobeevaluablewithonlythesetwo*relations.Thisisintentional.Forexampleconsider*SELECT*FROMa,b,cWHEREa.x=(b.y+c.z)*Ifaismuchlargerthantheothertables,itmaybeworthwhileto*cross-joinbandcandthenuseaninnerindexscanona.x.Therefore*weshouldconsiderthisjoinclauseasreasontojoinbtoc,eventhough*itcan'tbeappliedatthatjoinstep.*注意:连接条件不一定是等值连接,*比如:SELECT*FROMa,b,cWHEREa.x=(b.y+c.z),只要a.x大于b.y+c.z即可*/boolhave_relevant_joinclause(PlannerInfo*root,RelOptInfo*rel1,RelOptInfo*rel2){boolresult=false;List*joininfo;Relidsother_relids;ListCell*l;/**Wecouldscaneitherrelation'sjoininfolist;mayaswellusethe*shorterone.*获取relation中joininfo链表较少的那个*/if(list_length(rel1->joininfo)<=list_length(rel2->joininfo)){joininfo=rel1->joininfo;other_relids=rel2->relids;}else{joininfo=rel2->joininfo;other_relids=rel1->relids;}foreach(l,joininfo)//遍历{RestrictInfo*rinfo=(RestrictInfo*)lfirst(l);if(bms_overlap(other_relids,rinfo->required_relids))//存在交集{result=true;//存在连接条件break;}}/**WealsoneedtochecktheEquivalenceClassdatastructure,whichmight*containrelationshipsnotemittedintothejoininfolists.*检查等价类*/if(!result&&rel1->has_eclass_joins&&rel2->has_eclass_joins)result=have_relevant_eclass_joinclause(root,rel1,rel2);//存在等价类连接条件returnresult;}//----------------------------------------------------have_join_order_restriction/**have_join_order_restriction*Detectwhetherthetworelationsshouldbejoinedtosatisfy*ajoin-orderrestrictionarisingfromspecialorlateraljoins.*检查两个relations是否需要连接以满足join-order限制(由于special/lateral连接引起)**Inpracticethisisalwaysusedwithhave_relevant_joinclause(),andso*couldbemergedwiththatfunction,butitseemsclearertoseparatethe*twoconcerns.Weneedthistestbecausetherearedegeneratecaseswhere*aclauselessjoinmustbeperformedtosatisfyjoin-orderrestrictions.*Also,ifonerelhasalateralreferencetotheother,orbothareneeded*tocomputesomePHV,weshouldconsiderjoiningthemevenifthejoinwould*beclauseless.*在实践中，这通常与have_relevance_join子()一起使用，因此可以与该函数合并，*但分离这两个关注点似乎更为清晰。在一些退化的情况下需要这个测试，*必须执行无语法连接以满足连接顺序限制。*另外，如果一个rel与另一个rel有一个lateral引用，*或者两者都需要计算一些PHV，那么我们应该考虑加入它们，即使连接是无连接条件的。**Note:thisisonlyaproblemifonesideofadegenerateouterjoin*containsmultiplerels,oraclauselessjoinisrequiredwithinan*IN/EXISTSRHS;elsewewillfindajoinpathviathe"lastditch"casein*join_search_one_level().Wecoulddispensewiththistestifwewere*willingtotrybushyplansinthe"lastditch"case,butthatseemsmuch*lessefficient.*注意:只有当简并外部连接的一侧包含多个rels时，*或者在IN/EXISTSRHS中需要一个无修饰的连接时，才会出现这个问题;*否则，将通过join_search_one_level()中的“lastditch”*找到连接路径。如果愿意在“稠密计划”的情况下进行大量的尝试，*那么可以省去这个测试，但这似乎效率要低得多。*/boolhave_join_order_restriction(PlannerInfo*root,RelOptInfo*rel1,RelOptInfo*rel2){boolresult=false;ListCell*l;/**Ifeithersidehasadirectlateralreferencetotheother,attemptthe*joinregardlessofouter-joinconsiderations.*/if(bms_overlap(rel1->relids,rel2->direct_lateral_relids)||bms_overlap(rel2->relids,rel1->direct_lateral_relids))returntrue;//relids与lateralrelids存在交集,返回T/**Likewise,ifbothrelsareneededtocomputesomePlaceHolderVar,*attemptthejoinregardlessofouter-joinconsiderations.(Thisisnot*verydesirable,becauseaPHVwithalargeeval_atsetwillcausealot*ofprobably-uselessjoinstobeconsidered,butfailingtodothiscan*causeustofailtoconstructaplanatall.)*/foreach(l,root->placeholder_list)//遍历PHV{PlaceHolderInfo*phinfo=(PlaceHolderInfo*)lfirst(l);if(bms_is_subset(rel1->relids,phinfo->ph_eval_at)&&bms_is_subset(rel2->relids,phinfo->ph_eval_at))returntrue;}/**It'spossiblethattherelscorrespondtotheleftandrightsidesofa*degenerateouterjoin,thatis,onewithnojoinclausementioningthe*non-nullableside;inwhichcaseweshouldforcethejointooccur.**Also,thetworelscouldrepresentaclauselessjointhathastobe*completedtobuilduptheLHSorRHSofanouterjoin.*/foreach(l,root->join_info_list)//遍历连接链表{SpecialJoinInfo*sjinfo=(SpecialJoinInfo*)lfirst(l);/*ignorefulljoins---othermechanismshandlethem*/if(sjinfo->jointype==JOIN_FULL)continue;/*CanweperformtheSJwiththeserels?*/if(bms_is_subset(sjinfo->min_lefthand,rel1->relids)&&bms_is_subset(sjinfo->min_righthand,rel2->relids)){result=true;break;}if(bms_is_subset(sjinfo->min_lefthand,rel2->relids)&&bms_is_subset(sjinfo->min_righthand,rel1->relids)){result=true;break;}/**MightweneedtojointheserelstocompletetheRHS?Wehaveto*use"overlap"testssinceeitherrelmightincludealowerSJthat*hasbeenproventocommutewiththisone.*/if(bms_overlap(sjinfo->min_righthand,rel1->relids)&&bms_overlap(sjinfo->min_righthand,rel2->relids)){result=true;break;}/*LikewisefortheLHS.*/if(bms_overlap(sjinfo->min_lefthand,rel1->relids)&&bms_overlap(sjinfo->min_lefthand,rel2->relids)){result=true;break;}}/**Wedonotforcethejointooccurifeitherinputrelcanlegallybe*joinedtoanythingelseusingjoinclauses.Thisessentiallymeansthat*clauselessbushyjoinsareputoffaslongaspossible.Thereasonis*thatwhenthereisajoinorderrestrictionhighupinthejointree*(thatis,withmanyrelsinsidetheLHSorRHS),wewouldotherwise*expendlotsofeffortconsideringverystupidjoincombinationswithin*itsLHSorRHS.*/if(result){if(has_legal_joinclause(root,rel1)||has_legal_joinclause(root,rel2))result=false;}returnresult;}二、跟踪分析

创建测试数据表并生成测试数据:

droptableifexistsa;droptableifexistsb;droptableifexistsc;droptableifexistsd;droptableifexistse;droptableifexistsf;createtablea(c1int,c2varchar(20));createtableb(c1int,c2varchar(20));createtablec(c1int,c2varchar(20));createtabled(c1int,c2varchar(20));createtablee(c1int,c2varchar(20));createtablef(c1int,c2varchar(20));insertintoaselectgenerate_series(1,100),'TEST'||generate_series(1,100);insertintobselectgenerate_series(1,1000),'TEST'||generate_series(1,1000);insertintocselectgenerate_series(1,10000),'TEST'||generate_series(1,10000);insertintodselectgenerate_series(1,200),'TEST'||generate_series(1,200);insertintoeselectgenerate_series(1,4000),'TEST'||generate_series(1,4000);insertintofselectgenerate_series(1,100000),'TEST'||generate_series(1,100000);

测试脚本:

testdb=#explainverboseselecta.*,b.c1,c.c2,d.c2,e.c1,f.c2fromainnerjoinbona.c1=b.c1,c,d,einnerjoinfone.c1=f.c1ande.c1<100wherea.c1=f.c1andb.c1=c.c1andc.c1=d.c1andd.c1=e.c1;QUERYPLAN----------------------------------------------------------------------------------------------------------NestedLoop(cost=101.17..2218.24rows=2width=42)Output:a.c1,a.c2,b.c1,c.c2,d.c2,e.c1,f.c2JoinFilter:(a.c1=b.c1)->HashJoin(cost=3.25..196.75rows=100width=22)Output:a.c1,a.c2,c.c2,c.c1HashCond:(c.c1=a.c1)->SeqScanonpublic.c(cost=0.00..155.00rows=10000width=12)Output:c.c1,c.c2->Hash(cost=2.00..2.00rows=100width=10)Output:a.c1,a.c2->SeqScanonpublic.a(cost=0.00..2.00rows=100width=10)Output:a.c1,a.c2->Materialize(cost=97.92..2014.00rows=5width=32)Output:b.c1,d.c2,d.c1,e.c1,f.c2,f.c1->HashJoin(cost=97.92..2013.97rows=5width=32)Output:b.c1,d.c2,d.c1,e.c1,f.c2,f.c1HashCond:(f.c1=b.c1)->SeqScanonpublic.f(cost=0.00..1541.00rows=100000width=13)Output:f.c1,f.c2->Hash(cost=97.86..97.86rows=5width=19)Output:b.c1,d.c2,d.c1,e.c1->HashJoin(cost=78.10..97.86rows=5width=19)Output:b.c1,d.c2,d.c1,e.c1HashCond:(b.c1=e.c1)->SeqScanonpublic.b(cost=0.00..16.00rows=1000width=4)Output:b.c1,b.c2->Hash(cost=78.04..78.04rows=5width=15)Output:d.c2,d.c1,e.c1->HashJoin(cost=73.24..78.04rows=5width=15)Output:d.c2,d.c1,e.c1HashCond:(d.c1=e.c1)->SeqScanonpublic.d(cost=0.00..4.00rows=200width=11)Output:d.c1,d.c2->Hash(cost=72.00..72.00rows=99width=4)Output:e.c1->SeqScanonpublic.e(cost=0.00..72.00rows=99width=4)Output:e.c1Filter:(e.c1<100)(38rows)

测试SQL语句的连接关系:a-b,a-f,b-c,c-d,d-e,e-f
注:根据先前章节的知识,该SQL语句存在等价类{a.c1 b.c1 c.c1 d.c1 e.c1 f.c1}

启动gdb跟踪

(gdb)bjoin_search_one_levelBreakpoint1at0x755667:filejoinrels.c,line67.(gdb)cContinuing.Breakpoint1,join_search_one_level(root=0x3006e28,level=2)atjoinrels.c:6767List**joinrels=root->join_rel_level;

查看优化器信息(root)

(gdb)p*root$13={type=T_PlannerInfo,parse=0x2fa3410,glob=0x3008578,query_level=1,parent_root=0x0,plan_params=0x0,outer_params=0x0,simple_rel_array=0x2f510e8,simple_rel_array_size=9,simple_rte_array=0x2f51178,all_baserels=0x2f53dd8,nullable_baserels=0x0,join_rel_list=0x2fcb5c8,join_rel_hash=0x0,join_rel_level=0x2fcafe8,join_cur_level=2,init_plans=0x0,cte_plan_ids=0x0,multiexpr_params=0x0,eq_classes=0x2f52cb8,canon_pathkeys=0x2fcb718,left_join_clauses=0x0,right_join_clauses=0x0,full_join_clauses=0x0,join_info_list=0x0,append_rel_list=0x0,rowMarks=0x0,placeholder_list=0x0,fkey_list=0x0,query_pathkeys=0x0,group_pathkeys=0x0,window_pathkeys=0x0,distinct_pathkeys=0x0,sort_pathkeys=0x0,part_schemes=0x0,initial_rels=0x2fcaf18,upper_rels={0x0,0x0,0x0,0x0,0x0,0x0,0x0},upper_targets={0x0,0x0,0x0,0x0,0x0,0x0,0x0},processed_tlist=0x2f4f718,grouping_map=0x0,minmax_aggs=0x0,planner_cxt=0x2e87040,total_table_pages=627,tuple_fraction=0,limit_tuples=-1,qual_security_level=0,inhTargetKind=INHKIND_NONE,hasJoinRTEs=true,hasLateralRTEs=false,hasDeletedRTEs=false,hasHavingQual=false,hasPseudoConstantQuals=false,hasRecursion=false,wt_param_id=-1,non_recursive_path=0x0,curOuterRels=0x0,curOuterParams=0x0,join_search_private=0x0,partColsUpdated=false}

root->simple_rel_array_size=9,数组中有9个元素,从1-8(下标为0的元素无用)分别是1->RTE_RELATION/16775,2->RTE_RELATION/16778,3->RTE_JOIN,4->RTE_RELATION/16781,5->RTE_RELATION/16784,6->RTE_RELATION/16787,7->RTE_RELATION/16790,8->RTE_JOIN

oid|relname-------+---------16775|a-->116778|b-->216781|c-->416784|d-->516787|e-->616790|f-->7(6rows)

进入join_search_one_level函数,level=2,开始循环遍历joinrels

(gdb)n74root->join_cur_level=level;(gdb)83foreach(r,joinrels[level-1])(gdb)n85RelOptInfo*old_rel=(RelOptInfo*)lfirst(r);(gdb)87if(old_rel->joininfo!=NIL||old_rel->has_eclass_joins||(gdb)105if(level==2)/*considerremaininginitialrels*/(gdb)106other_rels=lnext(r);(gdb)110make_rels_by_clause_joins(root,

[level=2]进入make_rels_by_clause_joins函数

(gdb)stepmake_rels_by_clause_joins(root=0x3006e28,old_rel=0x3008258,other_rels=0x2fcaf48)atjoinrels.c:280280for_each_cell(l,other_rels)

[level=2]由于存在等价类{a.c1 b.c1 c.c1 d.c1 e.c1 f.c1},因此这一步骤会两两连接构造新的关系,ab,ac,ad,ae,af,bc,bd,...

(gdb)n282RelOptInfo*other_rel=(RelOptInfo*)lfirst(l);(gdb)284if(!bms_overlap(old_rel->relids,other_rel->relids)&&(gdb)285(have_relevant_joinclause(root,old_rel,other_rel)||(gdb)284if(!bms_overlap(old_rel->relids,other_rel->relids)&&(gdb)288(void)make_join_rel(root,old_rel,other_rel);(gdb)n280for_each_cell(l,other_rels)

[level=2]调用make_join_rel函数后,查看root->join_rel_level[2],relids=6=2+4,这是1号(关系a)和2号(关系b)RTE的连接.

(gdb)p*root->join_rel_level[2]$6={type=T_List,length=1,head=0x2fcb5f8,tail=0x2fcb5f8}(gdb)p*(Node*)root->join_rel_level[2]->head->data.ptr_value$7={type=T_RelOptInfo}(gdb)p*(RelOptInfo*)root->join_rel_level[2]->head->data.ptr_value$8={type=T_RelOptInfo,reloptkind=RELOPT_JOINREL,relids=0x2fcb050,rows=100,consider_startup=false,consider_param_startup=false,consider_parallel=true,reltarget=0x2fcb068,pathlist=0x2fcba08,ppilist=0x0,partial_pathlist=0x0,cheapest_startup_path=0x0,cheapest_total_path=0x0,cheapest_unique_path=0x0,cheapest_parameterized_paths=0x0,direct_lateral_relids=0x0,lateral_relids=0x0,relid=0,reltablespace=0,rtekind=RTE_JOIN,min_attr=0,max_attr=0,attr_needed=0x0,attr_widths=0x0,lateral_vars=0x0,lateral_referencers=0x0,indexlist=0x0,statlist=0x0,pages=0,tuples=0,allvisfrac=0,subroot=0x0,subplan_params=0x0,rel_parallel_workers=-1,serverid=0,userid=0,useridiscurrent=false,fdwroutine=0x0,fdw_private=0x0,unique_for_rels=0x0,non_unique_for_rels=0x0,baserestrictinfo=0x0,baserestrictcost={startup=0,per_tuple=0},baserestrict_min_security=4294967295,joininfo=0x0,has_eclass_joins=true,top_parent_relids=0x0,part_scheme=0x0,nparts=0,boundinfo=0x0,partition_qual=0x0,part_rels=0x0,partexprs=0x0,nullable_partexprs=0x0,partitioned_child_rels=0x0}(gdb)set$tmp=(RelOptInfo*)root->join_rel_level[2]->head->data.ptr_value(gdb)p*$tmp->relids->words$10=6

[level=2]继续循环,下几组分别是ac,ad,ae,af

(gdb)p*$tmp->relids->words$12=18/34/66/130

[level=2]完成对关系a的两两连接

(gdb)n291}(gdb)join_search_one_level(root=0x3006e28,level=2)atjoinrels.c:8989{(gdb)n83foreach(r,joinrels[level-1])

[level=2]类似的,处理b/c/d/e/f,两两形成连接,一共有15种组合(6!/(2!*(6-2)!))

(gdb)83foreach(r,joinrels[level-1])(gdb)142for(k=2;;k++)(gdb)p*root->join_rel_level[2]$44={type=T_List,length=15,head=0x2fcb5f8,tail=0x2fd7f78}

[level=2]完成level=2的调用,level2的relids组合有1&2,1&4,1&5,1&6,1&7,2&4,2&5,2&6,2&7,4&5,4&6,4&7,5&6,5&7,6&7

(gdb)standard_join_search(root=0x3006e28,levels_needed=6,initial_rels=0x2fcaf18)atallpaths.c:27572757foreach(lc,root->join_rel_level[lev])

开始level=3的调用

(gdb)cContinuing.Breakpoint1,join_search_one_level(root=0x3006e28,level=3)atjoinrels.c:6767List**joinrels=root->join_rel_level;

[level=3]遍历level=2的RelOptInfo(两两连接形成的新关系)

(gdb)83foreach(r,joinrels[level-1])

[level=3]与level=2不同,选择初始的RelOptInfo进行连接,而不是同级的rels

...(gdb)108other_rels=list_head(joinrels[1]);

[level=3]完成第一轮的循环,root->join_rel_level[3]链表中有4个Node(RelOptInfo),其relids分别是22/38/70/134,即1&2&4,1&2&5,1&2&6,1&2&7

(gdb)p*((RelOptInfo*)root->join_rel_level[3]->head->data.ptr_value)->relids->words$55=22(gdb)p*((RelOptInfo*)root->join_rel_level[3]->head->next->data.ptr_value)->relids->words$56=38(gdb)p*((RelOptInfo*)root->join_rel_level[3]->head->next->next->data.ptr_value)->relids->words$57=70(gdb)p*((RelOptInfo*)root->join_rel_level[3]->head->next->next->next->data.ptr_value)->relids->words$58=134

[level=3]完成所有循环后的root->join_rel_level[3],构成连接的relids组合,一共20个(请参照数学组合的计算),包括1&2&4,1&2&5,1&2&6,1&2&7,1&4&5,1&4&6,1&4&7,...

...(gdb)p*root->join_rel_level[3]$68={type=T_List,length=20,head=0x2fd90d8,tail=0x2f7f248}

[level=3]尝试bushy plans,达不到要求,退出循环

142for(k=2;;k++)(gdb)144intother_level=level-k;(gdb)150if(k>other_level)150if(k>other_level)(gdb)n151break;

[level=3]完成level=3的调用,开始level 4调用

(gdb)standard_join_search(root=0x3006e28,levels_needed=6,initial_rels=0x2fcaf18)atallpaths.c:27572757foreach(lc,root->join_rel_level[lev])(gdb)cContinuing.Breakpoint1,join_search_one_level(root=0x3006e28,level=4)atjoinrels.c:6767List**joinrels=root->join_rel_level;

[level=4]完成第一轮循环调用,查看root->join_rel_level[4],relids分别是54/86/150,即1&2&4&5,1&2&4&6,1&2&4&7

...89{(gdb)83foreach(r,joinrels[level-1])(gdb)p*root->join_rel_level[4]$69={type=T_List,length=3,head=0x2f838e0,tail=0x30654d8}(gdb)p*((RelOptInfo*)root->join_rel_level[4]->head->data.ptr_value)->relids->words$70=54(gdb)p*((RelOptInfo*)root->join_rel_level[4]->head->next->data.ptr_value)->relids->words$71=86(gdb)p*((RelOptInfo*)root->join_rel_level[4]->head->next->next->data.ptr_value)->relids->words$72=150

[level=4]所有循环后的root->join_rel_level[4],构成连接的relids组合,一共15个

(gdb)bjoinrels.c:142Breakpoint2at0x75576a:filejoinrels.c,line142.(gdb)cContinuing.Breakpoint2,join_search_one_level(root=0x3006e28,level=4)atjoinrels.c:142142for(k=2;;k++)(gdb)p*root->join_rel_level[4]$73={type=T_List,length=15,head=0x2f838e0,tail=0x307bd78}

[level=4]尝试bushy plans

...(gdb)pk$74=2(gdb)pother_level$75=2

[level=4]遍历k级关系,k=other_level,同一层次的rel,两两组合,即1&2,3&4等尝试两两配对连接

(gdb)n153foreach(r,joinrels[k])...(gdb)168if(k==other_level)

[level=4]如relids=6和relids=48的两个关系

177if(!bms_overlap(old_rel->relids,new_rel->relids))(gdb)184if(have_relevant_joinclause(root,old_rel,new_rel)||(gdb)p*old_rel->relids->words$78=6(gdb)p*new_rel->relids->words$79=48

[level=4]构造新的关系,但该关系无法通过合法连接形成或者已存在,因此没有对root->join_rel_level[4]有所影响(调用前后均为15个Node)

(gdb)n187(void)make_join_rel(root,old_rel,new_rel);(gdb)173for_each_cell(r2,other_rels)(gdb)p*root->join_rel_level[4]$80={type=T_List,length=15,head=0x2f838e0,tail=0x307bd78}

[level=4]完成bushy plans,root->join_rel_level[4]元素个数没有变化

(gdb)cContinuing.Breakpoint3,join_search_one_level(root=0x3006e28,level=4)atjoinrels.c:213213if(joinrels[level]==NIL)(gdb)p*root->join_rel_level[4]$82={type=T_List,length=15,head=0x2f838e0,tail=0x307bd78}

[level=5]进入level=5调用

(gdb)cContinuing.Breakpoint1,join_search_one_level(root=0x3006e28,level=5)atjoinrels.c:6767List**joinrels=root->join_rel_level;

[level=5]完成第一轮循环调用,查看root->join_rel_level[5],relids分别是118/182,即1&2&4&5&6,1&2&4&6&7

(gdb)p*root->join_rel_level[5]$83={type=T_List,length=2,head=0x30931d0,tail=0x3093dc8}(gdb)p*((RelOptInfo*)root->join_rel_level[5]->head->data.ptr_value)->relids->words$85=118(gdb)p*((RelOptInfo*)root->join_rel_level[5]->head->next->data.ptr_value)->relids->words$86=182

[level=5]所有循环后的root->join_rel_level[5],构成连接的relids组合,一共6个

(gdb)p*root->join_rel_level[5]$87={type=T_List,length=6,head=0x30931d0,tail=0x309d188}

[level=5]尝试bushy plans,即2个rels连接生成的关系 join 3个rels连接生成的关系
完成调用

(gdb)cContinuing.Breakpoint3,join_search_one_level(root=0x3006e28,level=5)atjoinrels.c:213213if(joinrels[level]==NIL)(gdb)p*root->join_rel_level[5]$91={type=T_List,length=6,head=0x30931d0,tail=0x309d188}

[level=6]进入level=6调用

(gdb)cContinuing.Breakpoint1,join_search_one_level(root=0x3006e28,level=6)atjoinrels.c:6767List**joinrels=root->join_rel_level;

[level=6]与level=1的rels连接后,形成1个新的关系

(gdb)cContinuing.Breakpoint2,join_search_one_level(root=0x3006e28,level=6)atjoinrels.c:142142for(k=2;;k++)(gdb)p*root->join_rel_level[6]$92={type=T_List,length=1,head=0x3104cf8,tail=0x3104cf8}

[level=6]尝试bushy plans,即2个rels连接生成的关系 join 4个rels连接生成的关系 & 3 join 3
完成调用,生成level=6的结果链表

(gdb)cContinuing.Breakpoint3,join_search_one_level(root=0x3006e28,level=6)atjoinrels.c:213213if(joinrels[level]==NIL)(gdb)p*root->join_rel_level[6]$93={type=T_List,length=1,head=0x3104cf8,tail=0x3104cf8}(gdb)p*(RelOptInfo*)root->join_rel_level[6]->head->data.ptr_value$94={type=T_RelOptInfo,reloptkind=RELOPT_JOINREL,relids=0x3099a80,rows=2,consider_startup=false,consider_param_startup=false,consider_parallel=true,reltarget=0x3104a08,pathlist=0x3104ec0,ppilist=0x0,partial_pathlist=0x0,cheapest_startup_path=0x0,cheapest_total_path=0x0,cheapest_unique_path=0x0,cheapest_parameterized_paths=0x0,direct_lateral_relids=0x0,lateral_relids=0x0,relid=0,reltablespace=0,rtekind=RTE_JOIN,min_attr=0,max_attr=0,attr_needed=0x0,attr_widths=0x0,lateral_vars=0x0,lateral_referencers=0x0,indexlist=0x0,statlist=0x0,pages=0,tuples=0,allvisfrac=0,subroot=0x0,subplan_params=0x0,rel_parallel_workers=-1,serverid=0,userid=0,useridiscurrent=false,fdwroutine=0x0,fdw_private=0x0,unique_for_rels=0x0,non_unique_for_rels=0x0,baserestrictinfo=0x0,baserestrictcost={startup=0,per_tuple=0},baserestrict_min_security=4294967295,joininfo=0x0,has_eclass_joins=false,top_parent_relids=0x0,part_scheme=0x0,nparts=0,boundinfo=0x0,partit

[level=6]查看访问路径

(gdb)set$roi=(RelOptInfo*)root->join_rel_level[6]->head->data.ptr_value(gdb)p*$roi->pathlist$97={type=T_List,length=1,head=0x3104ea0,tail=0x3104ea0}(gdb)p*(Node*)$roi->pathlist->head->data.ptr_value$98={type=T_NestPath}(gdb)p*(NestPath*)$roi->pathlist->head->data.ptr_value$99={path={type=T_NestPath,pathtype=T_NestLoop,parent=0x31047f8,pathtarget=0x3104a08,param_info=0x0,parallel_aware=false,parallel_safe=true,parallel_workers=0,rows=2,startup_cost=101.1725,total_cost=2218.2350000000001,pathkeys=0x0},jointype=JOIN_INNER,inner_unique=false,outerjoinpath=0x2fccd80,innerjoinpath=0x3107820,joinrestrictinfo=0x3107ae0}

该path的innerjoinpath(构造该连接inner关系的path)和outerjoinpath(构造该连接outer关系的path)

(gdb)p*$np->innerjoinpath$109={type=T_MaterialPath,pathtype=T_Material,parent=0x3077c70,pathtarget=0x3077e80,param_info=0x0,parallel_aware=false,parallel_safe=true,parallel_workers=0,rows=5,startup_cost=97.922499999999999,total_cost=2013.9974999999999,pathkeys=0x0}(gdb)p*$np->outerjoinpath$110={type=T_HashPath,pathtype=T_HashJoin,parent=0x2f54050,pathtarget=0x2fcbf88,param_info=0x0,parallel_aware=false,parallel_safe=true,parallel_workers=0,rows=100,startup_cost=3.25,total_cost=196.75,pathkeys=0x0}

到此，关于“PostgreSQL中使用动态规划算法构造连接路径的实现函数是哪个”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！