上一小节介绍了函数query_planner中子函数build_base_rel_tlists/find_placeholders_in_jointree/find_lateral_references的实现逻辑,本节介绍deconstruct_jointree函数的主要实现逻辑。

query_planner代码片段:

//... /* * Examine the targetlist and join tree, adding entries to baserel * targetlists for all referenced Vars, and generating PlaceHolderInfo * entries for all referenced PlaceHolderVars. Restrict and join clauses * are added to appropriate lists belonging to the mentioned relations. We * also build EquivalenceClasses for provably equivalent expressions. The * SpecialJoinInfo list is also built to hold information about join order * restrictions. Finally, we form a target joinlist for make_one_rel() to * work from. */ build_base_rel_tlists(root, tlist);//构建"base rels"的投影列 find_placeholders_in_jointree(root);//处理jointree中的PHI find_lateral_references(root);//处理jointree中Lateral依赖 joinlist = deconstruct_jointree(root);//分解jointree /* * Reconsider any postponed outer-join quals now that we have built up * equivalence classes. (This could result in further additions or * mergings of classes.) */ reconsider_outer_join_clauses(root);//已创建等价类,那么需要重新考虑被下推后处理的外连接表达式 /* * If we formed any equivalence classes, generate additional restriction * clauses as appropriate. (Implied join clauses are formed on-the-fly * later.) */ generate_base_implied_equalities(root);//等价类构建后,生成因此外加的约束语句 //...一、重要的数据结构

RelOptInfo
与上节一样,RelOptInfo结构体贯彻逻辑优化和物理优化过程的始终,需不时Review.

typedef struct RelOptInfo { NodeTag type;//节点标识 RelOptKind reloptkind;//RelOpt类型 /* all relations included in this RelOptInfo */ Relids relids; /*Relids(rtindex)集合 set of base relids (rangetable indexes) */ /* size estimates generated by planner */ double rows; /*结果元组的估算数量 estimated number of result tuples */ /* per-relation planner control flags */ bool consider_startup; /*是否考虑启动成本?是,需要保留启动成本低的路径 keep cheap-startup-cost paths? */ bool consider_param_startup; /*是否考虑参数化?的路径 ditto, for parameterized paths? */ bool consider_parallel; /*是否考虑并行处理路径 consider parallel paths? */ /* default result targetlist for Paths scanning this relation */ struct PathTarget *reltarget; /*扫描该Relation时默认的结果 list of Vars/Exprs, cost, width */ /* materialization information */ List *pathlist; /*访问路径链表 Path structures */ List *ppilist; /*路径链表中使用参数化路径进行 ParamPathInfos used in pathlist */ List *partial_pathlist; /* partial Paths */ struct Path *cheapest_startup_path;//代价最低的启动路径 struct Path *cheapest_total_path;//代价最低的整体路径 struct Path *cheapest_unique_path;//代价最低的获取唯一值的路径 List *cheapest_parameterized_paths;//代价最低的参数化?路径链表 /* parameterization information needed for both base rels and join rels */ /* (see also lateral_vars and lateral_referencers) */ Relids direct_lateral_relids; /*使用lateral语法,需依赖的Relids rels directly laterally referenced */ Relids lateral_relids; /* minimum parameterization of rel */ /* information about a base rel (not set for join rels!) */ //reloptkind=RELOPT_BASEREL时使用的数据结构 Index relid; /* Relation ID */ Oid reltablespace; /* 表空间 containing tablespace */ RTEKind rtekind; /* 基表?子查询?还是函数等等?RELATION, SUBQUERY, FUNCTION, etc */ AttrNumber min_attr; /* 最小的属性编号 smallest attrno of rel (often <0) */ AttrNumber max_attr; /* 最大的属性编号 largest attrno of rel */ Relids *attr_needed; /* 数组 array indexed [min_attr .. max_attr] */ int32 *attr_widths; /* 属性宽度 array indexed [min_attr .. max_attr] */ List *lateral_vars; /* 关系依赖的Vars/PHVs LATERAL Vars and PHVs referenced by rel */ Relids lateral_referencers; /*依赖该关系的Relids rels that reference me laterally */ List *indexlist; /* 该关系的IndexOptInfo链表 list of IndexOptInfo */ List *statlist; /* 统计信息链表 list of StatisticExtInfo */ BlockNumber pages; /* 块数 size estimates derived from pg_class */ double tuples; /* 元组数 */ double allvisfrac; /* ? */ PlannerInfo *subroot; /* 如为子查询,存储子查询的root if subquery */ List *subplan_params; /* 如为子查询,存储子查询的参数 if subquery */ int rel_parallel_workers; /* 并行执行,需要多少个workers? wanted number of parallel workers */ /* Information about foreign tables and foreign joins */ //FWD相关信息 Oid serverid; /* identifies server for the table or join */ Oid userid; /* identifies user to check access as */ bool useridiscurrent; /* join is only valid for current user */ /* use "struct FdwRoutine" to avoid including fdwapi.h here */ struct FdwRoutine *fdwroutine; void *fdw_private; /* cache space for remembering if we have proven this relation unique */ //已知的,可保证唯一的Relids链表 List *unique_for_rels; /* known unique for these other relid * set(s) */ List *non_unique_for_rels; /* 已知的,不唯一的Relids链表 known not unique for these set(s) */ /* used by various scans and joins: */ List *baserestrictinfo; /* 如为基本关系,存储约束条件 RestrictInfo structures (if base rel) */ QualCost baserestrictcost; /* 解析约束表达式的成本? cost of evaluating the above */ Index baserestrict_min_security; /* 最低安全等级 min security_level found in * baserestrictinfo */ List *joininfo; /* 连接语句的约束条件信息 RestrictInfo structures for join clauses * involving this rel */ bool has_eclass_joins; /* 是否存在等价类连接? T means joininfo is incomplete */ /* used by partitionwise joins: */ bool consider_partitionwise_join; /* 分区? consider partitionwise * join paths? (if * partitioned rel) */ Relids top_parent_relids; /* Relids of topmost parents (if "other" * rel) */ /* used for partitioned relations */ //分区表使用 PartitionScheme part_scheme; /* 分区的schema Partitioning scheme. */ int nparts; /* 分区数 number of partitions */ struct PartitionBoundInfoData *boundinfo; /* 分区边界信息 Partition bounds */ List *partition_qual; /* 分区约束 partition constraint */ struct RelOptInfo **part_rels; /* 分区的RelOptInfo数组 Array of RelOptInfos of partitions, * stored in the same order of bounds */ List **partexprs; /* 非空分区键表达式 Non-nullable partition key expressions. */ List **nullable_partexprs; /* 可为空的分区键表达式 Nullable partition key expressions. */ List *partitioned_child_rels; /* RT Indexes链表 List of RT indexes. */ } RelOptInfo;

PostponedQual

/* Elements of the postponed_qual_list used during deconstruct_recurse */ typedef struct PostponedQual { Node *qual; /* 待处理的表达式,a qual clause waiting to be processed */ Relids relids; /* 该表达式依赖的baserel 集合,the set of baserels it references */ } PostponedQual;二、源码解读

deconstruct_jointree函数:

/******************************************* deconstruct_jointree *********************递归搜索查询树中jointree中的WHERE/JOIN/ON表达式,把它们加入到相应的base RelOptInfos的约束条件和连接条件链表中同时,对于外连接,添加SpecialJoinInfo节点到root->join_info_list中返回joinlist数据结构,要求函数make_one_rel确定连接顺序其中:joinlist是元素为RTR或者sub-joinlist的链表*/ /* * deconstruct_jointree * Recursively scan the query's join tree for WHERE and JOIN/ON qual * clauses, and add these to the appropriate restrictinfo and joininfo * lists belonging to base RelOptInfos. Also, add SpecialJoinInfo nodes * to root->join_info_list for any outer joins appearing in the query tree. * Return a "joinlist" data structure showing the join order decisions * that need to be made by make_one_rel(). * * The "joinlist" result is a list of items that are either RangeTblRef * jointree nodes or sub-joinlists. All the items at the same level of * joinlist must be joined in an order to be determined by make_one_rel() * (note that legal orders may be constrained by SpecialJoinInfo nodes). * A sub-joinlist represents a subproblem to be planned separately. Currently * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of * subproblems is stopped by join_collapse_limit or from_collapse_limit. * * NOTE: when dealing with inner joins, it is appropriate to let a qual clause * be evaluated at the lowest level where all the variables it mentions are * available. However, we cannot push a qual down into the nullable side(s) * of an outer join since the qual might eliminate matching rows and cause a * NULL row to be incorrectly emitted by the join. Therefore, we artificially * OR the minimum-relids of such an outer join into the required_relids of * clauses appearing above it. This forces those clauses to be delayed until * application of the outer join (or maybe even higher in the join tree). */ List * deconstruct_jointree(PlannerInfo *root) { List *result; Relids qualscope; Relids inner_join_rels; List *postponed_qual_list = NIL; /* Start recursion at top of jointree */ Assert(root->parse->jointree != NULL && IsA(root->parse->jointree, FromExpr)); /* this is filled as we scan the jointree */ root->nullable_baserels = NULL; result = deconstruct_recurse(root, (Node *) root->parse->jointree, false, &qualscope, &inner_join_rels, &postponed_qual_list); /* Shouldn't be any leftover quals */ Assert(postponed_qual_list == NIL); return result; } /* * deconstruct_recurse * One recursion level of deconstruct_jointree processing. * * Inputs:输入 * jtnode is the jointree node to examine * 待处理的jointree * below_outer_join is true if this node is within the nullable side of a * higher-level outer join,在高层外连接的nullable端 * * Outputs:输出 * *qualscope gets the set of base Relids syntactically included in this * jointree node (do not modify or free this, as it may also be pointed * to by RestrictInfo and SpecialJoinInfo nodes) * jointree节点中base Relids的集合 * * *inner_join_rels gets the set of base Relids syntactically included in * inner joins appearing at or below this jointree node (do not modify * or free this, either) * 内连接jointree节点或该节点中的base Relids集合 * * *postponed_qual_list is a list of PostponedQual structs, which we can * add quals to if they turn out to belong to a higher join level * PostponedQual结构体链表,如果表达式属于更高层次的连接,可以在其中添加此表达式 * * Return value is the appropriate joinlist for this jointree node * 返回值为该jointree节点相应的joinlist * * In addition, entries will be added to root->join_info_list for outer joins. */ static List * deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join, Relids *qualscope, Relids *inner_join_rels, List **postponed_qual_list) { List *joinlist; if (jtnode == NULL) { *qualscope = NULL; *inner_join_rels = NULL; return NIL; } if (IsA(jtnode, RangeTblRef))//RTR { int varno = ((RangeTblRef *) jtnode)->rtindex; /* qualscope is just the one RTE */ *qualscope = bms_make_singleton(varno);//添加到qualscope中 /* Deal with any securityQuals attached to the RTE */ if (root->qual_security_level > 0) process_security_barrier_quals(root, varno, *qualscope, below_outer_join); /* A single baserel does not create an inner join */ *inner_join_rels = NULL;//inner_join_rels设置为NULL joinlist = list_make1(jtnode);//添加到joinlist中 } else if (IsA(jtnode, FromExpr))//FromExpr { FromExpr *f = (FromExpr *) jtnode; List *child_postponed_quals = NIL; int remaining; ListCell *l; /* * First, recurse to handle child joins. We collapse subproblems into * a single joinlist whenever the resulting joinlist wouldn't exceed * from_collapse_limit members. Also, always collapse one-element * subproblems, since that won't lengthen the joinlist anyway. */ *qualscope = NULL; *inner_join_rels = NULL;//初始化 joinlist = NIL;//初始化 remaining = list_length(f->fromlist); foreach(l, f->fromlist) { Relids sub_qualscope; List *sub_joinlist; int sub_members; sub_joinlist = deconstruct_recurse(root, lfirst(l), below_outer_join, &sub_qualscope, inner_join_rels, &child_postponed_quals);//递归调用 *qualscope = bms_add_members(*qualscope, sub_qualscope);//添加到qualscope中 sub_members = list_length(sub_joinlist);//sub-joinlist中的元素个数 remaining--;//计数 if (sub_members <= 1 || list_length(joinlist) + sub_members + remaining <= from_collapse_limit) joinlist = list_concat(joinlist, sub_joinlist);// else joinlist = lappend(joinlist, sub_joinlist);// } /* * A FROM with more than one list element is an inner join subsuming * all below it, so we should report inner_join_rels = qualscope. If * there was exactly one element, we should (and already did) report * whatever its inner_join_rels were. If there were no elements (is * that possible?) the initialization before the loop fixed it. */ if (list_length(f->fromlist) > 1) *inner_join_rels = *qualscope;//JOIN /* * Try to process any quals postponed by children. If they need * further postponement, add them to my output postponed_qual_list. */ foreach(l, child_postponed_quals) { PostponedQual *pq = (PostponedQual *) lfirst(l); if (bms_is_subset(pq->relids, *qualscope))//pq依赖的relids是qualscope的子集 distribute_qual_to_rels(root, pq->qual, false, below_outer_join, JOIN_INNER, root->qual_security_level, *qualscope, NULL, NULL, NULL, NULL);//可以分发到Rels中,构建约束条件等 else *postponed_qual_list = lappend(*postponed_qual_list, pq);//添加到postponed_qual_list链表 } /* * Now process the top-level quals. */ foreach(l, (List *) f->quals)//处理表达式 { Node *qual = (Node *) lfirst(l); distribute_qual_to_rels(root, qual, false, below_outer_join, JOIN_INNER, root->qual_security_level, *qualscope, NULL, NULL, NULL, postponed_qual_list);//分发到Rels中,构建约束条件等 } } else if (IsA(jtnode, JoinExpr))//JoinExpr { JoinExpr *j = (JoinExpr *) jtnode; List *child_postponed_quals = NIL; Relids leftids, rightids, left_inners, right_inners, nonnullable_rels, nullable_rels, ojscope; List *leftjoinlist, *rightjoinlist; List *my_quals; SpecialJoinInfo *sjinfo;//特殊连接信息 ListCell *l; /* * Order of operations here is subtle and critical. First we recurse * to handle sub-JOINs. Their join quals will be placed without * regard for whether this level is an outer join, which is correct. * Then we place our own join quals, which are restricted by lower * outer joins in any case, and are forced to this level if this is an * outer join and they mention the outer side. Finally, if this is an * outer join, we create a join_info_list entry for the join. This * will prevent quals above us in the join tree that use those rels * from being pushed down below this level. (It's okay for upper * quals to be pushed down to the outer side, however.) */ switch (j->jointype) { case JOIN_INNER://内连接 leftjoinlist = deconstruct_recurse(root, j->larg, below_outer_join, &leftids, &left_inners, &child_postponed_quals);//递归调用 rightjoinlist = deconstruct_recurse(root, j->rarg, below_outer_join, &rightids, &right_inners, &child_postponed_quals); *qualscope = bms_union(leftids, rightids); *inner_join_rels = *qualscope; /* Inner join adds no restrictions for quals */ nonnullable_rels = NULL; /* and it doesn't force anything to null, either */ nullable_rels = NULL; break; case JOIN_LEFT: case JOIN_ANTI://左连接或者反连接 leftjoinlist = deconstruct_recurse(root, j->larg, below_outer_join, &leftids, &left_inners, &child_postponed_quals); rightjoinlist = deconstruct_recurse(root, j->rarg, true, &rightids, &right_inners, &child_postponed_quals); *qualscope = bms_union(leftids, rightids); *inner_join_rels = bms_union(left_inners, right_inners); nonnullable_rels = leftids; nullable_rels = rightids; break; case JOIN_SEMI://半连接 leftjoinlist = deconstruct_recurse(root, j->larg, below_outer_join, &leftids, &left_inners, &child_postponed_quals); rightjoinlist = deconstruct_recurse(root, j->rarg, below_outer_join, &rightids, &right_inners, &child_postponed_quals); *qualscope = bms_union(leftids, rightids); *inner_join_rels = bms_union(left_inners, right_inners); /* Semi join adds no restrictions for quals */ nonnullable_rels = NULL; /* * Theoretically, a semijoin would null the RHS; but since the * RHS can't be accessed above the join, this is immaterial * and we needn't account for it. */ nullable_rels = NULL; break; case JOIN_FULL://全连接 leftjoinlist = deconstruct_recurse(root, j->larg, true, &leftids, &left_inners, &child_postponed_quals); rightjoinlist = deconstruct_recurse(root, j->rarg, true, &rightids, &right_inners, &child_postponed_quals); *qualscope = bms_union(leftids, rightids); *inner_join_rels = bms_union(left_inners, right_inners); /* each side is both outer and inner */ nonnullable_rels = *qualscope; nullable_rels = *qualscope; break; default: /* JOIN_RIGHT was eliminated during reduce_outer_joins() */ elog(ERROR, "unrecognized join type: %d", (int) j->jointype); nonnullable_rels = NULL; /* keep compiler quiet */ nullable_rels = NULL; leftjoinlist = rightjoinlist = NIL; break; } /* Report all rels that will be nulled anywhere in the jointree */ root->nullable_baserels = bms_add_members(root->nullable_baserels, nullable_rels);//nullable-side rels /* * Try to process any quals postponed by children. If they need * further postponement, add them to my output postponed_qual_list. * Quals that can be processed now must be included in my_quals, so * that they'll be handled properly in make_outerjoininfo. */ my_quals = NIL;//添加到表达式链表中 foreach(l, child_postponed_quals) { PostponedQual *pq = (PostponedQual *) lfirst(l); if (bms_is_subset(pq->relids, *qualscope)) my_quals = lappend(my_quals, pq->qual); else { /* * We should not be postponing any quals past an outer join. * If this Assert fires, pull_up_subqueries() messed up. */ Assert(j->jointype == JOIN_INNER); *postponed_qual_list = lappend(*postponed_qual_list, pq); } } /* list_concat is nondestructive of its second argument */ my_quals = list_concat(my_quals, (List *) j->quals); /* * For an OJ, form the SpecialJoinInfo now, because we need the OJ's * semantic scope (ojscope) to pass to distribute_qual_to_rels. But * we mustn't add it to join_info_list just yet, because we don't want * distribute_qual_to_rels to think it is an outer join below us. * * Semijoins are a bit of a hybrid: we build a SpecialJoinInfo, but we * want ojscope = NULL for distribute_qual_to_rels. */ if (j->jointype != JOIN_INNER)//非内连接 { sjinfo = make_outerjoininfo(root, leftids, rightids, *inner_join_rels, j->jointype, my_quals);//构建特殊连接信息 if (j->jointype == JOIN_SEMI) ojscope = NULL;//半连接 else ojscope = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); } else { sjinfo = NULL;//内连接,设置为NULL ojscope = NULL; } /* Process the JOIN's qual clauses */ foreach(l, my_quals)//处理JOIN中的qual表达式 { Node *qual = (Node *) lfirst(l); distribute_qual_to_rels(root, qual, false, below_outer_join, j->jointype, root->qual_security_level, *qualscope, ojscope, nonnullable_rels, NULL, postponed_qual_list);//处理表达式 } /* Now we can add the SpecialJoinInfo to join_info_list */ if (sjinfo)//特殊连接信息 { root->join_info_list = lappend(root->join_info_list, sjinfo); /* Each time we do that, recheck placeholder eval levels */ update_placeholder_eval_levels(root, sjinfo); } /* * Finally, compute the output joinlist. We fold subproblems together * except at a FULL JOIN or where join_collapse_limit would be * exceeded. */ if (j->jointype == JOIN_FULL) { /* force the join order exactly at this node */ joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist)); } else if (list_length(leftjoinlist) + list_length(rightjoinlist) <= join_collapse_limit) { /* OK to combine subproblems */ joinlist = list_concat(leftjoinlist, rightjoinlist); } else { /* can't combine, but needn't force join order above here */ Node *leftpart, *rightpart; /* avoid creating useless 1-element sublists */ if (list_length(leftjoinlist) == 1) leftpart = (Node *) linitial(leftjoinlist); else leftpart = (Node *) leftjoinlist; if (list_length(rightjoinlist) == 1) rightpart = (Node *) linitial(rightjoinlist); else rightpart = (Node *) rightjoinlist; joinlist = list_make2(leftpart, rightpart); } } else { elog(ERROR, "unrecognized node type: %d", (int) nodeTag(jtnode)); joinlist = NIL; /* keep compiler quiet */ } return joinlist; } /* * distribute_qual_to_rels * Add clause information to either the baserestrictinfo or joininfo list * (depending on whether the clause is a join) of each base relation * mentioned in the clause. A RestrictInfo node is created and added to * the appropriate list for each rel. Alternatively, if the clause uses a * mergejoinable operator and is not delayed by outer-join rules, enter * the left- and right-side expressions into the query's list of * EquivalenceClasses. Alternatively, if the clause needs to be treated * as belonging to a higher join level, just add it to postponed_qual_list. * * 为每个base relation的base relsbaserestrictinfo或者joininfo链表(取决于子句是否是连接)中添加相关子句信息; * RestrictInfo节点创建并添加到每个合适的Rel中;或者如果子句为可合并操作符并且没有被外连接所Delayed,则 * 把左右两侧的表达式放到查询的等价类链表中; * 或者,如果该子句属于更高的连接级别,只需将其添加到postponed_qual_list中 * * 'clause': the qual clause to be distributed,待分配的表达式子句 * 'is_deduced': true if the qual came from implied-equality deduction,如果表达式来自于隐含等式推导,则为true * 'below_outer_join': true if the qual is from a JOIN/ON that is below the * nullable side of a higher-level outer join 来自高层外连接的nullable端的JOIN/ON条件,则为true * 'jointype': type of join the qual is from (JOIN_INNER for a WHERE clause),qual来自何种连接类型 * 'security_level': security_level to assign to the qual,安全等级 * 'qualscope': set of baserels the qual's syntactic scope covers,表达式的base rels范围 * 'ojscope': NULL if not an outer-join qual, else the minimum set of baserels * needed to form this join,非外连接->NULL,否则为组成该join的最小baserels集合 * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of * baserels appearing on the outer (nonnullable) side of the join * (for FULL JOIN this includes both sides of the join, and must in fact * equal qualscope),非外连接->NULL,否则为出现在nonnullable端的base rels集合 * 'deduced_nullable_relids': if is_deduced is true, the nullable relids to * impute to the clause; otherwise NULL,推导出来的nullable端的relids,否则为NULL * 'postponed_qual_list': list of PostponedQual structs, which we can add * this qual to if it turns out to belong to a higher join level.PostponedQual结构体链表 * Can be NULL if caller knows postponement is impossible. * * 'qualscope' identifies what level of JOIN the qual came from syntactically. * 定义了在语法上表达式来自于哪个层次的JOIN * 'ojscope' is needed if we decide to force the qual up to the outer-join * level, which will be ojscope not necessarily qualscope. * 在我们强制把表达式上推至外连接时所需要的信息 * * In normal use (when is_deduced is false), at the time this is called, * root->join_info_list must contain entries for all and only those special * joins that are syntactically below this qual. But when is_deduced is true, * we are adding new deduced clauses after completion of deconstruct_jointree, * so it cannot be assumed that root->join_info_list has anything to do with * qual placement. */ static void distribute_qual_to_rels(PlannerInfo *root, Node *clause, bool is_deduced, bool below_outer_join, JoinType jointype, Index security_level, Relids qualscope, Relids ojscope, Relids outerjoin_nonnullable, Relids deduced_nullable_relids, List **postponed_qual_list) { Relids relids; bool is_pushed_down; bool outerjoin_delayed; bool pseudoconstant = false; bool maybe_equivalence; bool maybe_outer_join; Relids nullable_relids; RestrictInfo *restrictinfo; /* * Retrieve all relids mentioned within the clause. */ relids = pull_varnos(clause);//遍历,获取该节点中的所有relids /* * In ordinary SQL, a WHERE or JOIN/ON clause can't reference any rels * that aren't within its syntactic scope; however, if we pulled up a * LATERAL subquery then we might find such references in quals that have * been pulled up. We need to treat such quals as belonging to the join * level that includes every rel they reference. Although we could make * pull_up_subqueries() place such quals correctly to begin with, it's * easier to handle it here. When we find a clause that contains Vars * outside its syntactic scope, we add it to the postponed-quals list, and * process it once we've recursed back up to the appropriate join level. */ if (!bms_is_subset(relids, qualscope))//不是qualscope的子集 { PostponedQual *pq = (PostponedQual *) palloc(sizeof(PostponedQual)); Assert(root->hasLateralRTEs); /* shouldn't happen otherwise */ Assert(jointype == JOIN_INNER); /* mustn't postpone past outer join */ Assert(!is_deduced); /* shouldn't be deduced, either */ pq->qual = clause; pq->relids = relids; *postponed_qual_list = lappend(*postponed_qual_list, pq);//添加到postponed_qual_list中,返回 return; } /* * If it's an outer-join clause, also check that relids is a subset of * ojscope. (This should not fail if the syntactic scope check passed.) */ if (ojscope && !bms_is_subset(relids, ojscope)) elog(ERROR, "JOIN qualification cannot refer to other relations"); /* * If the clause is variable-free, our normal heuristic for pushing it * down to just the mentioned rels doesn't work, because there are none. * * If the clause is an outer-join clause, we must force it to the OJ's * semantic level to preserve semantics. * * Otherwise, when the clause contains volatile functions, we force it to * be evaluated at its original syntactic level. This preserves the * expected semantics. * * When the clause contains no volatile functions either, it is actually a * pseudoconstant clause that will not change value during any one * execution of the plan, and hence can be used as a one-time qual in a * gating Result plan node. We put such a clause into the regular * RestrictInfo lists for the moment, but eventually createplan.c will * pull it out and make a gating Result node immediately above whatever * plan node the pseudoconstant clause is assigned to. It's usually best * to put a gating node as high in the plan tree as possible. If we are * not below an outer join, we can actually push the pseudoconstant qual * all the way to the top of the tree. If we are below an outer join, we * leave the qual at its original syntactic level (we could push it up to * just below the outer join, but that seems more complex than it's * worth). */ if (bms_is_empty(relids))//空的relids { if (ojscope)//外连接 { /* clause is attached to outer join, eval it there */ relids = bms_copy(ojscope); /* mustn't use as gating qual, so don't mark pseudoconstant */ } else//非外连接 { /* eval at original syntactic level */ relids = bms_copy(qualscope); if (!contain_volatile_functions(clause))//不存在易变函数 { /* mark as gating qual */ pseudoconstant = true; /* tell createplan.c to check for gating quals */ root->hasPseudoConstantQuals = true; /* if not below outer join, push it to top of tree */ if (!below_outer_join) { relids = get_relids_in_jointree((Node *) root->parse->jointree, false); qualscope = bms_copy(relids); } } } } /*---------- * Check to see if clause application must be delayed by outer-join * considerations. * * A word about is_pushed_down: we mark the qual as "pushed down" if * it is (potentially) applicable at a level different from its original * syntactic level. This flag is used to distinguish OUTER JOIN ON quals * from other quals pushed down to the same joinrel. The rules are: * WHERE quals and INNER JOIN quals: is_pushed_down = true. * Non-degenerate OUTER JOIN quals: is_pushed_down = false. * Degenerate OUTER JOIN quals: is_pushed_down = true. * A "degenerate" OUTER JOIN qual is one that doesn't mention the * non-nullable side, and hence can be pushed down into the nullable side * without changing the join result. It is correct to treat it as a * regular filter condition at the level where it is evaluated. * * Note: it is not immediately obvious that a simple boolean is enough * for this: if for some reason we were to attach a degenerate qual to * its original join level, it would need to be treated as an outer join * qual there. However, this cannot happen, because all the rels the * clause mentions must be in the outer join's min_righthand, therefore * the join it needs must be formed before the outer join; and we always * attach quals to the lowest level where they can be evaluated. But * if we were ever to re-introduce a mechanism for delaying evaluation * of "expensive" quals, this area would need work. * * Note: generally, use of is_pushed_down has to go through the macro * RINFO_IS_PUSHED_DOWN, because that flag alone is not always sufficient * to tell whether a clause must be treated as pushed-down in context. * This seems like another reason why it should perhaps be rethought. *---------- */ if (is_deduced)//推导出来? { /* * If the qual came from implied-equality deduction, it should not be * outerjoin-delayed, else deducer blew it. But we can't check this * because the join_info_list may now contain OJs above where the qual * belongs. For the same reason, we must rely on caller to supply the * correct nullable_relids set. */ Assert(!ojscope);//非外连接 is_pushed_down = true;//可以被下推 outerjoin_delayed = false;//无需外连接延迟 nullable_relids = deduced_nullable_relids;//nullable端的relids /* Don't feed it back for more deductions */ maybe_equivalence = false;//不需要反馈更多的推导 maybe_outer_join = false; } else if (bms_overlap(relids, outerjoin_nonnullable))//与外连接nonnullable端有交集 { /* * The qual is attached to an outer join and mentions (some of the) * rels on the nonnullable side, so it's not degenerate. * * We can't use such a clause to deduce equivalence (the left and * right sides might be unequal above the join because one of them has * gone to NULL) ... but we might be able to use it for more limited * deductions, if it is mergejoinable. So consider adding it to the * lists of set-aside outer-join clauses. */ is_pushed_down = false;//不能被下推 maybe_equivalence = false; maybe_outer_join = true;//可能是外连接 /* Check to see if must be delayed by lower outer join */ outerjoin_delayed = check_outerjoin_delay(root, &relids, &nullable_relids, false);//检查外连接延迟 /* * Now force the qual to be evaluated exactly at the level of joining * corresponding to the outer join. We cannot let it get pushed down * into the nonnullable side, since then we'd produce no output rows, * rather than the intended single null-extended row, for any * nonnullable-side rows failing the qual. * * (Do this step after calling check_outerjoin_delay, because that * trashes relids.) */ Assert(ojscope); relids = ojscope; Assert(!pseudoconstant); } else//常规的情况 { /* * Normal qual clause or degenerate outer-join clause. Either way, we * can mark it as pushed-down. */ is_pushed_down = true;//可以下推 /* Check to see if must be delayed by lower outer join */ outerjoin_delayed = check_outerjoin_delay(root, &relids, &nullable_relids, true);//检查是否被下层的外连接所延迟 if (outerjoin_delayed)//需延迟 { /* Should still be a subset of current scope ... */ Assert(root->hasLateralRTEs || bms_is_subset(relids, qualscope)); Assert(ojscope == NULL || bms_is_subset(relids, ojscope)); /* * Because application of the qual will be delayed by outer join, * we mustn't assume its vars are equal everywhere. */ maybe_equivalence = false; /* * It's possible that this is an IS NULL clause that's redundant * with a lower antijoin; if so we can just discard it. We need * not test in any of the other cases, because this will only be * possible for pushed-down, delayed clauses. */ if (check_redundant_nullability_qual(root, clause)) return; } else//无需延迟 { /* * Qual is not delayed by any lower outer-join restriction, so we * can consider feeding it to the equivalence machinery. However, * if it's itself within an outer-join clause, treat it as though * it appeared below that outer join (note that we can only get * here when the clause references only nullable-side rels). */ maybe_equivalence = true;//可能会出现等价类 if (outerjoin_nonnullable != NULL) below_outer_join = true; } /* * Since it doesn't mention the LHS, it's certainly not useful as a * set-aside OJ clause, even if it's in an OJ. */ maybe_outer_join = false;//不会是外连接 } /* * Build the RestrictInfo node itself. */ restrictinfo = make_restrictinfo((Expr *) clause, is_pushed_down, outerjoin_delayed, pseudoconstant, security_level, relids, outerjoin_nonnullable, nullable_relids);//构造约束条件 /* * If it's a join clause (either naturally, or because delayed by * outer-join rules), add vars used in the clause to targetlists of their * relations, so that they will be emitted by the plan nodes that scan * those relations (else they won't be available at the join node!). * * Note: if the clause gets absorbed into an EquivalenceClass then this * may be unnecessary, but for now we have to do it to cover the case * where the EC becomes ec_broken and we end up reinserting the original * clauses into the plan. */ if (bms_membership(relids) == BMS_MULTIPLE)//存在多个relids { List *vars = pull_var_clause(clause, PVC_RECURSE_AGGREGATES | PVC_RECURSE_WINDOWFUNCS | PVC_INCLUDE_PLACEHOLDERS);//遍历获取Vars add_vars_to_targetlist(root, vars, relids, false);//添加到相应的投影列中 list_free(vars); } /* * We check "mergejoinability" of every clause, not only join clauses, * because we want to know about equivalences between vars of the same * relation, or between vars and consts. */ check_mergejoinable(restrictinfo);//检查是否可以合并 /* * If it is a true equivalence clause, send it to the EquivalenceClass * machinery. We do *not* attach it directly to any restriction or join * lists. The EC code will propagate it to the appropriate places later. * * If the clause has a mergejoinable operator and is not * outerjoin-delayed, yet isn't an equivalence because it is an outer-join * clause, the EC code may yet be able to do something with it. We add it * to appropriate lists for further consideration later. Specifically: * * If it is a left or right outer-join qualification that relates the two * sides of the outer join (no funny business like leftvar1 = leftvar2 + * rightvar), we add it to root->left_join_clauses or * root->right_join_clauses according to which side the nonnullable * variable appears on. * * If it is a full outer-join qualification, we add it to * root->full_join_clauses. (Ideally we'd discard cases that aren't * leftvar = rightvar, as we do for left/right joins, but this routine * doesn't have the info needed to do that; and the current usage of the * full_join_clauses list doesn't require that, so it's not currently * worth complicating this routine's API to make it possible.) * * If none of the above hold, pass it off to * distribute_restrictinfo_to_rels(). * * In all cases, it's important to initialize the left_ec and right_ec * fields of a mergejoinable clause, so that all possibly mergejoinable * expressions have representations in EquivalenceClasses. If * process_equivalence is successful, it will take care of that; * otherwise, we have to call initialize_mergeclause_eclasses to do it. */ if (restrictinfo->mergeopfamilies)//可以 { if (maybe_equivalence)//存在合并的可能 { if (check_equivalence_delay(root, restrictinfo) && process_equivalence(root, &restrictinfo, below_outer_join)) return; /* EC rejected it, so set left_ec/right_ec the hard way ... */ if (restrictinfo->mergeopfamilies) /* EC might have changed this */ initialize_mergeclause_eclasses(root, restrictinfo); /* ... and fall through to distribute_restrictinfo_to_rels */ } else if (maybe_outer_join && restrictinfo->can_join)//可能是外连接而且约束条件can_join? { /* we need to set up left_ec/right_ec the hard way */ initialize_mergeclause_eclasses(root, restrictinfo); /* now see if it should go to any outer-join lists */ if (bms_is_subset(restrictinfo->left_relids, outerjoin_nonnullable) && !bms_overlap(restrictinfo->right_relids, outerjoin_nonnullable)) { /* we have outervar = innervar */ root->left_join_clauses = lappend(root->left_join_clauses, restrictinfo); return; } if (bms_is_subset(restrictinfo->right_relids, outerjoin_nonnullable) && !bms_overlap(restrictinfo->left_relids, outerjoin_nonnullable)) { /* we have innervar = outervar */ root->right_join_clauses = lappend(root->right_join_clauses, restrictinfo); return; } if (jointype == JOIN_FULL) { /* FULL JOIN (above tests cannot match in this case) */ root->full_join_clauses = lappend(root->full_join_clauses, restrictinfo); return; } /* nope, so fall through to distribute_restrictinfo_to_rels */ } else { /* we still need to set up left_ec/right_ec */ initialize_mergeclause_eclasses(root, restrictinfo);//初始化合并语句的等价类 } } /* No EC special case applies, so push it into the clause lists */ distribute_restrictinfo_to_rels(root, restrictinfo);//分发到PlannerInfo中的子句中 } /* * distribute_restrictinfo_to_rels * Push a completed RestrictInfo into the proper restriction or join * clause list(s). * * 下推完整的约束条件到合适的约束语句或连接语句链表中 * * This is the last step of distribute_qual_to_rels() for ordinary qual * clauses. Clauses that are interesting for equivalence-class processing * are diverted to the EC machinery, but may ultimately get fed back here. */ void distribute_restrictinfo_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo) { Relids relids = restrictinfo->required_relids; RelOptInfo *rel; switch (bms_membership(relids)) { case BMS_SINGLETON: /* * There is only one relation participating in the clause, so it * is a restriction clause for that relation. */ rel = find_base_rel(root, bms_singleton_member(relids)); /* Add clause to rel's restriction list */ rel->baserestrictinfo = lappend(rel->baserestrictinfo, restrictinfo); /* Update security level info */ rel->baserestrict_min_security = Min(rel->baserestrict_min_security, restrictinfo->security_level); break; case BMS_MULTIPLE: /* * The clause is a join clause, since there is more than one rel * in its relid set. */ /* * Check for hashjoinable operators. (We don't bother setting the * hashjoin info except in true join clauses.) */ check_hashjoinable(restrictinfo); /* * Add clause to the join lists of all the relevant relations. */ add_join_clause_to_rels(root, restrictinfo, relids); break; default: /* * clause references no rels, and therefore we have no place to * attach it. Shouldn't get here if callers are working properly. */ elog(ERROR, "cannot cope with variable-free clause"); break; } } 三、跟踪分析

测试脚本:

testdb=# explain verbose select a.*,b.grbh,b.je testdb-# from t_dwxx a,lateral (select t1.dwbh,t1.grbh,t2.je from t_grxx t1 inner join t_jfxx t2 on t1.dwbh = a.dwbh and t1.grbh = t2.grbh) btestdb-# where a.dwbh = '1001'testdb-# order by b.dwbh; QUERY PLAN ------------------------------------------------------------------------------------ Nested Loop (cost=15.03..36.10 rows=7 width=558) Output: a.dwmc, a.dwbh, a.dwdz, t1.grbh, t2.je, t1.dwbh -> Seq Scan on public.t_dwxx a (cost=0.00..1.04 rows=1 width=474) Output: a.dwmc, a.dwbh, a.dwdz Filter: ((a.dwbh)::text = '1001'::text) -> Hash Join (cost=15.03..34.99 rows=7 width=84) Output: t1.grbh, t1.dwbh, t2.je Hash Cond: ((t2.grbh)::text = (t1.grbh)::text) -> Seq Scan on public.t_jfxx t2 (cost=0.00..17.20 rows=720 width=46) Output: t2.grbh, t2.ny, t2.je -> Hash (cost=15.00..15.00 rows=2 width=76) Output: t1.grbh, t1.dwbh -> Seq Scan on public.t_grxx t1 (cost=0.00..15.00 rows=2 width=76) Output: t1.grbh, t1.dwbh Filter: ((t1.dwbh)::text = '1001'::text) -- 谓词下推(15 rows)

在deconstruct_jointree上设置断点,启动gdb跟踪:

(gdb) b deconstruct_jointreeBreakpoint 1 at 0x7660e3: file initsplan.c, line 718.(gdb) cContinuing.Breakpoint 1, deconstruct_jointree (root=0x1a498f0) at initsplan.c:718718 List *postponed_qual_list = NIL;

进入函数deconstruct_jointree

718 List *postponed_qual_list = NIL;(gdb) n725 root->nullable_baserels = NULL;(gdb) #递归调用deconstruct_recurse727 result = deconstruct_recurse(root, (Node *) root->parse->jointree, false,(gdb)

进入deconstruct_recurse函数

(gdb) stepdeconstruct_recurse (root=0x1a498f0, jtnode=0x1a473e0, below_outer_join=false, qualscope=0x7ffe02efe0a0, inner_join_rels=0x7ffe02efe098, postponed_qual_list=0x7ffe02efe090) at initsplan.c:765765 if (jtnode == NULL)(gdb) p *jtnode$1 = {type = T_FromExpr}

处理逻辑进入FromExpr节点

...804 foreach(l, f->fromlist)(gdb) #递归调用deconstruct_recurse810 sub_joinlist = deconstruct_recurse(root, lfirst(l),(gdb) #进入deconstruct_recurse(gdb) stepdeconstruct_recurse (root=0x1a498f0, jtnode=0x19bb600, below_outer_join=false, qualscope=0x7ffe02efdfa0, inner_join_rels=0x7ffe02efe098, postponed_qual_list=0x7ffe02efdfa8) at initsplan.c:765765 if (jtnode == NULL)(gdb) p *jtnode#FromExpr->fromlist->head的类型是FromExpr$2 = {type = T_RangeTblRef}...(gdb) n#返回joinlist(varno=1)1094 return joinlist;...回到FromExpr处理逻辑815 *qualscope = bms_add_members(*qualscope, sub_qualscope);(gdb) p *qualscope$8 = (Relids) 0x0(gdb) p *sub_qualscope$9 = {nwords = 1, words = 0x1a920c4}(gdb) p *sub_qualscope->words$10 = 2...#循环继续处理FromExpr->fromlist804 foreach(l, f->fromlist)...#FromExpr#1->fromlist.2的类型是FromExpr(gdb) p *jtnode$15 = {type = T_FromExpr}...

第2个FromExpr中的fromlist,第1个元素为JoinExpr

#即:FromExpr#2->fromlist.1的类型是JoinExpr...(gdb)810 sub_joinlist = deconstruct_recurse(root, lfirst(l),#直接执行,处理JoinExpr,返回结果#24=8+16(即3/4号rtindex)(gdb) p sub_qualscope->words[0]$22 = 24815 *qualscope = bms_add_members(*qualscope, sub_qualscope);...#处理完JoinExpr后...843 if (bms_is_subset(pq->relids, *qualscope))(gdb) p *qualscope->words$38 = 24(gdb) p *pq->relids->words$41 = 10#不是子集,添加到postponed_qual_list,由上层负责处理(gdb) n850 *postponed_qual_list = lappend(*postponed_qual_list, pq);856 foreach(l, (List *) f->quals)(gdb) #第2个FromExpr没有qual,直接返回1094 return joinlist;...

回到第1个FromExpr的处理逻辑

(gdb) 815 *qualscope = bms_add_members(*qualscope, sub_qualscope);(gdb) p *qualscope->words$42 = 2(gdb) p *sub_qualscope->words$44 = 24(gdb) n816 sub_members = list_length(sub_joinlist);#拼入到qualscope中,26=2+8+16(1/3/4号rte)(gdb) p *qualscope->words$45 = 26...843 if (bms_is_subset(pq->relids, *qualscope))#这时候10是26的子集,因此可以调用distribute_qual_to_rels了(gdb) n844 distribute_qual_to_rels(root, pq->qual,(gdb) stepdistribute_qual_to_rels (root=0x1a498f0, clause=0x1a56ab0, is_deduced=false, below_outer_join=false, jointype=JOIN_INNER, security_level=0, qualscope=0x1a920d8, ojscope=0x0, outerjoin_nonnullable=0x0, deduced_nullable_relids=0x0, postponed_qual_list=0x0) at initsplan.c:16561656 bool pseudoconstant = false;#进入distribute_qual_to_rels#clause是t_dwxx.dwbh = t_grxx.dwbh...(gdb) n

构造约束条件

1897 restrictinfo = make_restrictinfo((Expr *) clause,...(gdb) p *restrictinfo$63 = {type = T_RestrictInfo, clause = 0x1a56ab0, is_pushed_down = true, outerjoin_delayed = false, can_join = true, pseudoconstant = false, leakproof = false, security_level = 0, clause_relids = 0x1a92840, required_relids = 0x1a926e8, outer_relids = 0x0, nullable_relids = 0x0, left_relids = 0x1a92810, right_relids = 0x1a92828, orclause = 0x0, parent_ec = 0x0, eval_cost = {startup = -1, per_tuple = 0}, norm_selec = -1, outer_selec = -1, mergeopfamilies = 0x1a92878, left_ec = 0x0, right_ec = 0x0, left_em = 0x0, right_em = 0x0, scansel_cache = 0x0, outer_is_left = false, hashjoinoperator = 0, left_bucketsize = -1, right_bucketsize = -1, left_mcvfreq = -1, right_mcvfreq = -1}(gdb) n1971 if (check_equivalence_delay(root, restrictinfo) &&(gdb) 1972 process_equivalence(root, &restrictinfo, below_outer_join))(gdb) 1971 if (check_equivalence_delay(root, restrictinfo) &&(gdb)

检查&处理等价类,如OK,则返回

1973 return;(gdb) deconstruct_recurse (root=0x1a498f0, jtnode=0x1a473e0, below_outer_join=false, qualscope=0x7ffe02efe0a0, inner_join_rels=0x7ffe02efe098, postponed_qual_list=0x7ffe02efe090) at initsplan.c:839839 foreach(l, child_postponed_quals)(gdb) 856 foreach(l, (List *) f->quals)#处理第1个FromExpr的quals(即dwbh='1001')(gdb) n858 Node *qual = (Node *) lfirst(l);(gdb) 860 distribute_qual_to_rels(root, qual,(gdb) 856 foreach(l, (List *) f->quals)(gdb) #返回joinlist(3个RTR)1094 return joinlist;(gdb) n1095 }(gdb) deconstruct_jointree (root=0x1a498f0) at initsplan.c:734734 return result;

执行完毕,在PlannerInfo中产生了两个等价类

(gdb) p *root$85 = {type = T_PlannerInfo, parse = 0x19bb1a0, glob = 0x1a53ee8, query_level = 1, parent_root = 0x0, plan_params = 0x0, outer_params = 0x0, simple_rel_array = 0x1a90568, simple_rel_array_size = 6, simple_rte_array = 0x1a905b8, all_baserels = 0x0, nullable_baserels = 0x0, join_rel_list = 0x0, join_rel_hash = 0x0, join_rel_level = 0x0, join_cur_level = 0, init_plans = 0x0, cte_plan_ids = 0x0, multiexpr_params = 0x0, eq_classes = 0x1a92650, canon_pathkeys = 0x0, 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 = 0x0, upper_rels = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, upper_targets = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, processed_tlist = 0x1a56160, grouping_map = 0x0, minmax_aggs = 0x0, planner_cxt = 0x1997040, total_table_pages = 0, tuple_fraction = 0, limit_tuples = -1, qual_security_level = 0, inhTargetKind = INHKIND_NONE, hasJoinRTEs = true, hasLateralRTEs = true, 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}(gdb) p *root->eq_classes$86 = {type = T_List, length = 2, head = 0x1a92630, tail = 0x1a92ad0}(gdb) p *(Node *)root->eq_classes->head->data.ptr_value$87 = {type = T_EquivalenceClass}(gdb) p *(EquivalenceClass *)root->eq_classes->head->data.ptr_value$88 = {type = T_EquivalenceClass, ec_opfamilies = 0x1a92350, ec_collation = 100, ec_members = 0x1a92590, ec_sources = 0x1a924d8, ec_derives = 0x0, ec_relids = 0x1a92558, ec_has_const = false, ec_has_volatile = false, ec_below_outer_join = false, ec_broken = false, ec_sortref = 0, ec_min_security = 0, ec_max_security = 0, ec_merged = 0x0}(gdb) p *(EquivalenceClass *)root->eq_classes->head->next->data.ptr_value$89 = {type = T_EquivalenceClass, ec_opfamilies = 0x1a92878, ec_collation = 100, ec_members = 0x1a92a30, ec_sources = 0x1a92978, ec_derives = 0x0, ec_relids = 0x1a929f8, ec_has_const = true, ec_has_volatile = false, ec_below_outer_join = false, ec_broken = false, ec_sortref = 0, ec_min_security = 0, ec_max_security = 0, ec_merged = 0x0}(gdb)

第1个等价类有2个Member

(gdb) p *((EquivalenceClass *)root->eq_classes->head->data.ptr_value)->ec_members$91 = {type = T_List, length = 2, head = 0x1a92570, tail = 0x1a92610}

第2个等价类有3个Member

(gdb) p *((EquivalenceClass *)root->eq_classes->head->next->data.ptr_value)->ec_members$97 = {type = T_List, length = 3, head = 0x1a92a10, tail = 0x1a92d08}

等价类的解释下节再行介绍.

initsplan.c