这篇文章主要讲解了“PostgreSQL中sort_inner_and_outer函数分析”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“PostgreSQL中sort_inner_and_outer函数分析”吧！

merge join的算法实现伪代码如下:
READ data_set_1 SORT BY JOIN KEY TO temp_ds1
READ data_set_2 SORT BY JOIN KEY TO temp_ds2
READ ds1_row FROM temp_ds1
READ ds2_row FROM temp_ds2
WHILE NOT eof ON temp_ds1,temp_ds2 LOOP
IF ( temp_ds1.key = temp_ds2.key ) OUTPUT JOIN ds1_row,ds2_row
ELSIF ( temp_ds1.key <= temp_ds2.key ) READ ds1_row FROM temp_ds1
ELSIF ( temp_ds1.key => temp_ds2.key ) READ ds2_row FROM temp_ds2
END LOOP

Cost相关
注意:实际使用的参数值通过系统配置文件定义,而不是这里的常量定义!

typedefdoubleCost;/*executioncost(inpage-accessunits)*//*defaultsforcostsize.c'sCostparameters*//*NB:cost-estimationcodeshouldusethevariables,nottheseconstants!*//*注意:实际值通过系统配置文件定义,而不是这里的常量定义!*//*Ifyouchangethese,updatebackend/utils/misc/postgresql.sample.conf*/#defineDEFAULT_SEQ_PAGE_COST1.0//顺序扫描page的成本#defineDEFAULT_RANDOM_PAGE_COST4.0//随机扫描page的成本#defineDEFAULT_CPU_TUPLE_COST0.01//处理一个元组的CPU成本#defineDEFAULT_CPU_INDEX_TUPLE_COST0.005//处理一个索引元组的CPU成本#defineDEFAULT_CPU_OPERATOR_COST0.0025//执行一次操作或函数的CPU成本#defineDEFAULT_PARALLEL_TUPLE_COST0.1//并行执行,从一个worker传输一个元组到另一个worker的成本#defineDEFAULT_PARALLEL_SETUP_COST1000.0//构建并行执行环境的成本#defineDEFAULT_EFFECTIVE_CACHE_SIZE524288/*先前已有介绍,measuredinpages*/doubleseq_page_cost=DEFAULT_SEQ_PAGE_COST;doublerandom_page_cost=DEFAULT_RANDOM_PAGE_COST;doublecpu_tuple_cost=DEFAULT_CPU_TUPLE_COST;doublecpu_index_tuple_cost=DEFAULT_CPU_INDEX_TUPLE_COST;doublecpu_operator_cost=DEFAULT_CPU_OPERATOR_COST;doubleparallel_tuple_cost=DEFAULT_PARALLEL_TUPLE_COST;doubleparallel_setup_cost=DEFAULT_PARALLEL_SETUP_COST;inteffective_cache_size=DEFAULT_EFFECTIVE_CACHE_SIZE;Costdisable_cost=1.0e10;//1后面10个0,通过设置一个巨大的成本,让优化器自动放弃此路径intmax_parallel_workers_per_gather=2;//每次gather使用的worker数二、源码解读

sort_inner_and_outer函数尝试构造merge join访问路径.
构造过程中的成本估算实现函数initial_cost_mergejoin和final_cost_mergejoin在下一节介绍.

//------------------------------------------------sort_inner_and_outer/**sort_inner_and_outer*Createmergejoinjoinpathsbyexplicitlysortingboththeouterand*innerjoinrelationsoneachavailablemergeordering.*显式排序outer和inner表,创建mergejoin连接路径.**'joinrel'isthejoinrelation*joinrel-连接后新生成的relation*'outerrel'istheouterjoinrelation*outerrel-参与连接的outerrelation(俗称外表,驱动表)*'innerrel'istheinnerjoinrelation*innerrel-参与连接的innerrelation(俗称内表)*'jointype'isthetypeofjointodo*jointype-连接类型*'extra'containsadditionalinputvalues*extra-额外的输入参数*/staticvoidsort_inner_and_outer(PlannerInfo*root,RelOptInfo*joinrel,RelOptInfo*outerrel,RelOptInfo*innerrel,JoinTypejointype,JoinPathExtraData*extra){JoinTypesave_jointype=jointype;Path*outer_path;Path*inner_path;Path*cheapest_partial_outer=NULL;Path*cheapest_safe_inner=NULL;List*all_pathkeys;ListCell*l;/**Weonlyconsiderthecheapest-total-costinputpaths,sinceweare*assumingherethatasortisrequired.Wewillconsider*cheapest-startup-costinputpathslater,andonlyiftheydon'tneeda*sort.*由于我们假定排序是必须的,只考虑总成本最低的路径。*后续会尝试启动成本最低的路径，并且只在它们不需要排序的情况下。**Thisfunctionintentionallydoesnotconsiderparameterizedinput*paths,exceptwhenthecheapest-totalisparameterized.Ifwedidso,*we'dhaveacombinatorialexplosionofmergejoinpathsofdubious*value.Thisinteractswithdecisionselsewherethatalsodiscriminate*againstmergejoinswithparameterizedinputs;seecommentsin*src/backend/optimizer/README.*该函数特意不考虑参数化输入路径，除非成本最低路径是参数化的。*如果考虑了参数化输入路径,mergejoin将有一个数量巨大的组合,成本上划不来。*而且这将与其他地方的决策相互作用，这些决策同样会"歧视"使用参数化输入的mergejoin;*请参阅src/backend/optimizer/README中的注释。*/outer_path=outerrel->cheapest_total_path;inner_path=innerrel->cheapest_total_path;/**Ifeithercheapest-totalpathisparameterizedbytheotherrel,we*can'tuseamergejoin.(There'snouselookingforalternativeinput*paths,sincetheseshouldalreadybetheleast-parameterizedavailable*paths.)*如果任意一个总成本最低的路径使用了参数化访问路径，那么不能使用合并连接。*(没有必要寻找替代的输入路径，因为这些路径已经是参数化最少的可用路径了。)*/if(PATH_PARAM_BY_REL(outer_path,innerrel)||PATH_PARAM_BY_REL(inner_path,outerrel))return;/**Ifunique-ificationisrequested,doitandthenhandleasaplain*innerjoin.*如果需要保证唯一,创建唯一性访问路径并设置为JOIN_INNER连接类型*/if(jointype==JOIN_UNIQUE_OUTER){outer_path=(Path*)create_unique_path(root,outerrel,outer_path,extra->sjinfo);Assert(outer_path);jointype=JOIN_INNER;}elseif(jointype==JOIN_UNIQUE_INNER){inner_path=(Path*)create_unique_path(root,innerrel,inner_path,extra->sjinfo);Assert(inner_path);jointype=JOIN_INNER;}/**Ifthejoinrelisparallel-safe,wemaybeabletoconsiderapartial*mergejoin.However,wecan'thandleJOIN_UNIQUE_OUTER,becausethe*outerpathwillbepartial,andthereforewewon'tbeabletoproperly*guaranteeuniqueness.Similarly,wecan'thandleJOIN_FULLand*JOIN_RIGHT,becausetheycanproducefalsenullextendedrows.Also,*theresultingpathmustnotbeparameterized.*如果连接可以并行执行，那么可以考虑并行合并连接。*但是，PG不能处理JOIN_UNIQUE_OUTER，因为外部路径是部分的，因此不能正确地保证惟一性。*类似地，PG不能处理JOIN_FULL和JOIN_RIGHT，因为它们会产生假空扩展行。*此外，生成的路径不能被参数化。*/if(joinrel->consider_parallel&&save_jointype!=JOIN_UNIQUE_OUTER&&save_jointype!=JOIN_FULL&&save_jointype!=JOIN_RIGHT&&outerrel->partial_pathlist!=NIL&&bms_is_empty(joinrel->lateral_relids)){cheapest_partial_outer=(Path*)linitial(outerrel->partial_pathlist);if(inner_path->parallel_safe)cheapest_safe_inner=inner_path;elseif(save_jointype!=JOIN_UNIQUE_INNER)cheapest_safe_inner=get_cheapest_parallel_safe_total_inner(innerrel->pathlist);}/**Eachpossibleorderingoftheavailablemergejoinclauseswillgenerate*adifferently-sortedresultpathatessentiallythesamecost.Wehave*nobasisforchoosingoneoveranotheratthislevelofjoining,but*somesortordersmaybemoreusefulthanothersforhigher-level*mergejoins,soit'sworthconsideringmultipleorderings.*可用的mergejoin子句的每一种可能的排序都将以基本相同的代价生成不同的排序结果路径。*在这种连接级别上，我们没有选择一个排序的基础，但是对于更高层的合并，*某些排序顺序可能比其他更有用，因此值得考虑多种排序的顺序。**Actually,it'snotquitetruethateverymergeclauseorderingwill*generateadifferentpathorder,becausesomeoftheclausesmaybe*partiallyredundant(refertothesameEquivalenceClasses).Therefore,*whatwedoisconvertthemergeclauselisttoalistofcanonical*pathkeys,andthenconsiderdifferentorderingsofthepathkeys.*实际上，并不是每个mergeclause都会生成不同的路径顺序，因为有些子句可能是部分冗余的(请参阅等价类)。*因此，要做的是将mergeclause列表转换为一个规范路径键列表，然后考虑路径键的不同顺序。**Generatingapathfor*every*permutationofthepathkeysdoesn'tseem*likeawinningstrategy;thecostinplanningtimeistoohigh.For*now,wegenerateonepathforeachpathkey,listingthatpathkeyfirst*andtherestinrandomorder.Thisshouldallowatleastaone-clause*mergejoinwithoutre-sortingagainstanyotherpossiblemergejoin*partnerpath.Butifwe'venotguessedtherightorderingofsecondary*keys,wemayendupevaluatingclausesasqpqualswhentheycouldhave*beendoneasmergeclauses.(Inpractice,it'srarethatthere'smore*thantwoorthreemergeclauses,soexpendingahugeamountofthought*onthatisprobablynotworthit.)*为每个路径键的排列生成路径似乎不是一个好的策略,因为计划时间成本太高了。*现在，我们为每个pathkey生成一个路径，首先列出这个pathkey，然后按随机顺序列出其余的路径。*这应该至少允许一个单子句的mergejoin，而不需要对任何其他可能的mergejoin路径进行重新排序。*但如果没有正确判断二级键的顺序，那么可能会以qpquals的形式计算条件子句，而这些子句本可以作为mergeclauses完成。*(实际上，很少有两个或三个以上的mergeclauses，所以花大量时间在这上面可能不值得)。**Thepathkeyorderreturnedbyselect_outer_pathkeys_for_merge()has*someheuristicsbehindit(seethatfunction),sobesuretotryit*exactlyas-isaswellasmakingvariants.*通过调用select_outer_pathkeys_for_merge函数返回的排序键顺序pathkey*背后有一些启发式函数(请参阅该函数)，所以一定要按原样尝试它，并创建变体。*/all_pathkeys=select_outer_pathkeys_for_merge(root,extra->mergeclause_list,joinrel);foreach(l,all_pathkeys)//遍历所有可用的排序键{List*front_pathkey=(List*)lfirst(l);List*cur_mergeclauses;List*outerkeys;List*innerkeys;List*merge_pathkeys;/*Makeapathkeylistwiththisguyfirst*/if(l!=list_head(all_pathkeys))outerkeys=lcons(front_pathkey,list_delete_ptr(list_copy(all_pathkeys),front_pathkey));elseouterkeys=all_pathkeys;/*noworkatfirstone...*//*Sortthemergeclausesintothecorrespondingordering*/cur_mergeclauses=find_mergeclauses_for_outer_pathkeys(root,outerkeys,extra->mergeclause_list);/*Shouldhaveusedthemall...*/Assert(list_length(cur_mergeclauses)==list_length(extra->mergeclause_list));/*Buildsortpathkeysfortheinnerside*/innerkeys=make_inner_pathkeys_for_merge(root,cur_mergeclauses,outerkeys);/*Buildpathkeysrepresentingoutputsortorder*/merge_pathkeys=build_join_pathkeys(root,joinrel,jointype,outerkeys);/**Andnowwecanmakethepath.**Note:it'spossiblethatthecheapestpathswillalreadybesorted*properly.try_mergejoin_pathwilldetectthatcaseandsuppressan*explicitsortstep,soweneedn'tdosohere.*注意:成本最低的路径可能已被正确排序。*try_mergejoin_path将检测这种情况并禁止显式排序步骤，因此在这里不需要这样做。*/try_mergejoin_path(root,joinrel,outer_path,inner_path,merge_pathkeys,cur_mergeclauses,outerkeys,innerkeys,jointype,extra,false);/**Ifwehavepartialouterandparallelsafeinnerpaththentry*partialmergejoinpath.*并行处理*/if(cheapest_partial_outer&&cheapest_safe_inner)try_partial_mergejoin_path(root,joinrel,cheapest_partial_outer,cheapest_safe_inner,merge_pathkeys,cur_mergeclauses,outerkeys,innerkeys,jointype,extra);}}//-----------------------------------try_mergejoin_path/**try_mergejoin_path*Consideramergejoinpath;ifitappearsuseful,pushitinto*thejoinrel'spathlistviaadd_path().*尝试mergejoinpath,如可用,则把该路径通过add_path函数放在joinrel的pathlist链表中*/staticvoidtry_mergejoin_path(PlannerInfo*root,RelOptInfo*joinrel,Path*outer_path,Path*inner_path,List*pathkeys,List*mergeclauses,List*outersortkeys,List*innersortkeys,JoinTypejointype,JoinPathExtraData*extra,boolis_partial){Relidsrequired_outer;JoinCostWorkspaceworkspace;if(is_partial){try_partial_mergejoin_path(root,joinrel,outer_path,inner_path,pathkeys,mergeclauses,outersortkeys,innersortkeys,jointype,extra);//并行执行return;}/**Checktoseeifproposedpathisstillparameterized,andrejectifthe*parameterizationwouldn'tbesensible.*检查建议的路径是否仍然参数化，如果参数化不合理，则舍弃。*/required_outer=calc_non_nestloop_required_outer(outer_path,inner_path);if(required_outer&&!bms_overlap(required_outer,extra->param_source_rels)){/*Wastenomemorywhenwerejectapathhere*/bms_free(required_outer);return;}/**Ifthegivenpathsarealreadywellenoughordered,wecanskipdoing*anexplicitsort.*如果给定的路径已完成排序,则跳过显式排序.*/if(outersortkeys&&pathkeys_contained_in(outersortkeys,outer_path->pathkeys))outersortkeys=NIL;if(innersortkeys&&pathkeys_contained_in(innersortkeys,inner_path->pathkeys))innersortkeys=NIL;/**Seecommentsintry_nestloop_path().*/initial_cost_mergejoin(root,&workspace,jointype,mergeclauses,outer_path,inner_path,outersortkeys,innersortkeys,extra);//初始化mergejoinif(add_path_precheck(joinrel,workspace.startup_cost,workspace.total_cost,pathkeys,required_outer))//执行前置检查{add_path(joinrel,(Path*)create_mergejoin_path(root,joinrel,jointype,&workspace,extra,outer_path,inner_path,extra->restrictlist,pathkeys,required_outer,mergeclauses,outersortkeys,innersortkeys));//创建并添加路径}else{/*Wastenomemorywhenwerejectapathhere*/bms_free(required_outer);}}//-----------------------create_mergejoin_path/**create_mergejoin_path*Createsapathnodecorrespondingtoamergejoinjoinbetween*tworelations*创建mergejoin访问路径**'joinrel'isthejoinrelation*joinrel-连接后新生成的relation*'jointype'isthetypeofjoinrequired*jointype-连接类型*'workspace'istheresultfrominitial_cost_mergejoin*workspace-通过函数initial_cost_mergejoin返回的结果*'extra'containsvariousinformationaboutthejoin*extra-额外的输入参数*'outer_path'istheouterpath*outer_path-outerrelation访问路径*'inner_path'istheinnerpath*inner_path-innerrelation访问路径*'restrict_clauses'aretheRestrictInfonodestoapplyatthejoin*restrict_clauses-约束条件子句*'pathkeys'arethepathkeysofthenewjoinpath*pathkeys-排序键*'required_outer'isthesetofrequiredouterrels*required_outer-如需要outerrels,则在此保存relids*'mergeclauses'aretheRestrictInfonodestouseasmergeclauses*(thisshouldbeasubsetoftherestrict_clauseslist)*mergeclauses-合并连接条件子句*'outersortkeys'arethesortvarkeysfortheouterrelation*outersortkeys-outerrelation的排序键*'innersortkeys'arethesortvarkeysfortheinnerrelation*innersortkeys-innerrelation的排序键*/MergePath*create_mergejoin_path(PlannerInfo*root,RelOptInfo*joinrel,JoinTypejointype,JoinCostWorkspace*workspace,JoinPathExtraData*extra,Path*outer_path,Path*inner_path,List*restrict_clauses,List*pathkeys,Relidsrequired_outer,List*mergeclauses,List*outersortkeys,List*innersortkeys){MergePath*pathnode=makeNode(MergePath);pathnode->jpath.path.pathtype=T_MergeJoin;pathnode->jpath.path.parent=joinrel;pathnode->jpath.path.pathtarget=joinrel->reltarget;pathnode->jpath.path.param_info=get_joinrel_parampathinfo(root,joinrel,outer_path,inner_path,extra->sjinfo,required_outer,&restrict_clauses);pathnode->jpath.path.parallel_aware=false;pathnode->jpath.path.parallel_safe=joinrel->consider_parallel&&outer_path->parallel_safe&&inner_path->parallel_safe;/*Thisisafoolishwaytoestimateparallel_workers,butfornow...*/pathnode->jpath.path.parallel_workers=outer_path->parallel_workers;pathnode->jpath.path.pathkeys=pathkeys;pathnode->jpath.jointype=jointype;pathnode->jpath.inner_unique=extra->inner_unique;pathnode->jpath.outerjoinpath=outer_path;pathnode->jpath.innerjoinpath=inner_path;pathnode->jpath.joinrestrictinfo=restrict_clauses;pathnode->path_mergeclauses=mergeclauses;pathnode->outersortkeys=outersortkeys;pathnode->innersortkeys=innersortkeys;/*pathnode->skip_mark_restorewillbesetbyfinal_cost_mergejoin*//*pathnode->materialize_innerwillbesetbyfinal_cost_mergejoin*/final_cost_mergejoin(root,pathnode,workspace,extra);//估算成本returnpathnode;}三、跟踪分析

测试脚本如下

selecta.*,b.grbh,b.jefromt_dwxxa,lateral(selectt1.dwbh,t1.grbh,t2.jefromt_grxxt1innerjoint_jfxxt2ont1.dwbh=a.dwbhandt1.grbh=t2.grbh)borderbyb.dwbh;

启动gdb,设置断点

(gdb)bsort_inner_and_outerBreakpoint1at0x7af63a:filejoinpath.c,line888.(gdb)cContinuing.Breakpoint1,sort_inner_and_outer(root=0x1a4a278,joinrel=0x1aa7180,outerrel=0x1a55700,innerrel=0x1a56c30,jointype=JOIN_INNER,extra=0x7ffca933f880)atjoinpath.c:888888JoinTypesave_jointype=jointype;(gdb)

新生成的joinrel是1号和3号RTE的连接,类型为JOIN_INNER

(gdb)p*joinrel->relids->words$1=10(gdb)pjointype$2=JOIN_INNER

获取排序键,PathKey中的等价类EC,成员为t_grxx.dwbh和t_dwxx.dwbh

...(gdb)993all_pathkeys=select_outer_pathkeys_for_merge(root,(gdb)n997foreach(l,all_pathkeys)(gdb)p*all_pathkeys$3={type=T_List,length=1,head=0x1a69490,tail=0x1a69490}(gdb)p*(PathKey*)all_pathkeys->head->data.ptr_value$5={type=T_PathKey,pk_eclass=0x1a60e08,pk_opfamily=1994,pk_strategy=1,pk_nulls_first=false}...(gdb)set$rt=(RelabelType*)((EquivalenceMember*)$ec->ec_members->head->data.ptr_value)->em_expr(gdb)p*$rt->arg$14={type=T_Var}(gdb)p*(Var*)$rt->arg$15={xpr={type=T_Var},varno=3,varattno=1,vartype=1043,vartypmod=14,varcollid=100,varlevelsup=0,varnoold=3,varoattno=1,location=208}(gdb)set$rt2=(RelabelType*)((EquivalenceMember*)$ec->ec_members->head->next->data.ptr_value)->em_expr(gdb)p*(Var*)$rt2->arg$16={xpr={type=T_Var},varno=1,varattno=2,vartype=1043,vartypmod=24,varcollid=100,varlevelsup=0,varnoold=1,varoattno=2,location=218}

开始遍历all_pathkeys

(gdb)n999List*front_pathkey=(List*)lfirst(l);

获取连接条件子句,t_dwxx.dwbh=t_grxx.dwbh

(gdb)p*cur_mergeclauses$17={type=T_List,length=1,head=0x1a694f0,tail=0x1a694f0}

构建outer和inner relation的排序键

(gdb)p*(PathKey*)innerkeys->head->data.ptr_value$22={type=T_PathKey,pk_eclass=0x1a60e08,pk_opfamily=1994,pk_strategy=1,pk_nulls_first=false}(gdb)p*(PathKey*)merge_pathkeys->head->data.ptr_value$25={type=T_PathKey,pk_eclass=0x1a60e08,pk_opfamily=1994,pk_strategy=1,pk_nulls_first=false}

尝试merge join,进入函数try_mergejoin_path

(gdb)1038try_mergejoin_path(root,(gdb)steptry_mergejoin_path(root=0x1a4dcc0,joinrel=0x1a68e20,outer_path=0x1a62288,inner_path=0x1a62320,pathkeys=0x1a694b8,mergeclauses=0x1a69518,outersortkeys=0x1a694b8,innersortkeys=0x1a69578,jointype=JOIN_INNER,extra=0x7ffca933f880,is_partial=false)atjoinpath.c:572572if(is_partial)

初始merge join成本

...(gdb)615initial_cost_mergejoin(root,&workspace,jointype,mergeclauses,(gdb)pworkspace$26={startup_cost=10861.483356195882,total_cost=11134.203356195881,run_cost=24.997499999999999,inner_run_cost=247.72250000000003,inner_rescan_run_cost=1.3627136827435593e-316,outer_rows=9999,inner_rows=100000,outer_skip_rows=0,inner_skip_rows=911,numbuckets=27665584,numbatches=0,inner_rows_total=1.3681950446447804e-316}

构造merge join

...(gdb)n625create_mergejoin_path(root,(gdb)624add_path(joinrel,(Path*)(gdb)644}(gdb)p*joinrel->pathlist$28={type=T_List,length=1,head=0x1a6a180,tail=0x1a6a180}(gdb)p*(Node*)joinrel->pathlist->head->data.ptr_value$29={type=T_MergePath}(gdb)p*(MergePath*)joinrel->pathlist->head->data.ptr_value$30={jpath={path={type=T_MergePath,pathtype=T_MergeJoin,parent=0x1a68e20,pathtarget=0x1a69058,param_info=0x0,parallel_aware=false,parallel_safe=true,parallel_workers=0,rows=100000,startup_cost=10863.760856195882,total_cost=12409.200856195883,pathkeys=0x1a694b8},jointype=JOIN_INNER,inner_unique=false,outerjoinpath=0x1a62288,innerjoinpath=0x1a62320,joinrestrictinfo=0x1a692f8},path_mergeclauses=0x1a69518,outersortkeys=0x1a694b8,innersortkeys=0x1a69578,skip_mark_restore=false,materialize_inner=false}

完成调用

(gdb)nsort_inner_and_outer(root=0x1a4dcc0,joinrel=0x1a68e20,outerrel=0x1a4d700,innerrel=0x1a4d918,jointype=JOIN_INNER,extra=0x7ffca933f880)atjoinpath.c:10541054if(cheapest_partial_outer&&cheapest_safe_inner)(gdb)997foreach(l,all_pathkeys)(gdb)1066}(gdb)nadd_paths_to_joinrel(root=0x1a4dcc0,joinrel=0x1a68e20,outerrel=0x1a4d700,innerrel=0x1a4d918,jointype=JOIN_INNER,sjinfo=0x7ffca933f970,restrictlist=0x1a692f8)atjoinpath.c:279279if(mergejoin_allowed)(gdb)280match_unsorted_outer(root,joinrel,outerrel,innerrel,...

感谢各位的阅读，以上就是“PostgreSQL中sort_inner_and_outer函数分析”的内容了，经过本文的学习后，相信大家对PostgreSQL中sort_inner_and_outer函数分析这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！