diff options
Diffstat (limited to 'src/backend/optimizer/plan')
| -rw-r--r-- | src/backend/optimizer/plan/analyzejoins.c | 61 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/createplan.c | 17 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/initsplan.c | 1121 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/planner.c | 7 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/setrefs.c | 234 |
5 files changed, 1113 insertions, 327 deletions
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c index d657e8f601a..fbb652e7b05 100644 --- a/src/backend/optimizer/plan/analyzejoins.c +++ b/src/backend/optimizer/plan/analyzejoins.c @@ -34,7 +34,7 @@ /* local functions */ static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo); -static void remove_rel_from_query(PlannerInfo *root, int relid, +static void remove_rel_from_query(PlannerInfo *root, int relid, int ojrelid, Relids joinrelids); static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved); static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel); @@ -70,6 +70,7 @@ restart: foreach(lc, root->join_info_list) { SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc); + Relids joinrelids; int innerrelid; int nremoved; @@ -84,9 +85,12 @@ restart: */ innerrelid = bms_singleton_member(sjinfo->min_righthand); - remove_rel_from_query(root, innerrelid, - bms_union(sjinfo->min_lefthand, - sjinfo->min_righthand)); + /* Compute the relid set for the join we are considering */ + joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); + if (sjinfo->ojrelid != 0) + joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid); + + remove_rel_from_query(root, innerrelid, sjinfo->ojrelid, joinrelids); /* We verify that exactly one reference gets removed from joinlist */ nremoved = 0; @@ -188,6 +192,8 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo) /* Compute the relid set for the join we are considering */ joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); + if (sjinfo->ojrelid != 0) + joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid); /* * We can't remove the join if any inner-rel attributes are used above the @@ -248,6 +254,17 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo) RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l); /* + * If the current join commutes with some other outer join(s) via + * outer join identity 3, there will be multiple clones of its join + * clauses in the joininfo list. We want to consider only the + * has_clone form of such clauses. Processing more than one form + * would be wasteful, and also some of the others would confuse the + * RINFO_IS_PUSHED_DOWN test below. + */ + if (restrictinfo->is_clone) + continue; /* ignore it */ + + /* * If it's not a join clause for this outer join, we can't use it. * Note that if the clause is pushed-down, then it is logically from * above the outer join, even if it references no other rels (it might @@ -306,10 +323,12 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo) * no longer treated as a baserel, and that attributes of other baserels * are no longer marked as being needed at joins involving this rel. * Also, join quals involving the rel have to be removed from the joininfo - * lists, but only if they belong to the outer join identified by joinrelids. + * lists, but only if they belong to the outer join identified by ojrelid + * and joinrelids. */ static void -remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) +remove_rel_from_query(PlannerInfo *root, int relid, int ojrelid, + Relids joinrelids) { RelOptInfo *rel = find_base_rel(root, relid); List *joininfos; @@ -346,10 +365,20 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) { otherrel->attr_needed[attroff] = bms_del_member(otherrel->attr_needed[attroff], relid); + otherrel->attr_needed[attroff] = + bms_del_member(otherrel->attr_needed[attroff], ojrelid); } } /* + * Update all_baserels and related relid sets. + */ + root->all_baserels = bms_del_member(root->all_baserels, relid); + root->outer_join_rels = bms_del_member(root->outer_join_rels, ojrelid); + root->all_query_rels = bms_del_member(root->all_query_rels, relid); + root->all_query_rels = bms_del_member(root->all_query_rels, ojrelid); + + /* * Likewise remove references from SpecialJoinInfo data structures. * * This is relevant in case the outer join we're deleting is nested inside @@ -365,6 +394,14 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) sjinfo->min_righthand = bms_del_member(sjinfo->min_righthand, relid); sjinfo->syn_lefthand = bms_del_member(sjinfo->syn_lefthand, relid); sjinfo->syn_righthand = bms_del_member(sjinfo->syn_righthand, relid); + sjinfo->min_lefthand = bms_del_member(sjinfo->min_lefthand, ojrelid); + sjinfo->min_righthand = bms_del_member(sjinfo->min_righthand, ojrelid); + sjinfo->syn_lefthand = bms_del_member(sjinfo->syn_lefthand, ojrelid); + sjinfo->syn_righthand = bms_del_member(sjinfo->syn_righthand, ojrelid); + /* relid cannot appear in these fields, but ojrelid can: */ + sjinfo->commute_above_l = bms_del_member(sjinfo->commute_above_l, ojrelid); + sjinfo->commute_above_r = bms_del_member(sjinfo->commute_above_r, ojrelid); + sjinfo->commute_below = bms_del_member(sjinfo->commute_below, ojrelid); } /* @@ -396,8 +433,10 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) else { phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid); + phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, ojrelid); Assert(!bms_is_empty(phinfo->ph_eval_at)); phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid); + phinfo->ph_needed = bms_del_member(phinfo->ph_needed, ojrelid); } } @@ -422,7 +461,12 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) remove_join_clause_from_rels(root, rinfo, rinfo->required_relids); - if (RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)) + /* + * If the qual lists ojrelid in its required_relids, it must have come + * from above the outer join we're removing (so we need to keep it); + * if it does not, then it didn't and we can discard it. + */ + if (bms_is_member(ojrelid, rinfo->required_relids)) { /* Recheck that qual doesn't actually reference the target rel */ Assert(!bms_is_member(relid, rinfo->clause_relids)); @@ -434,6 +478,8 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) rinfo->required_relids = bms_copy(rinfo->required_relids); rinfo->required_relids = bms_del_member(rinfo->required_relids, relid); + rinfo->required_relids = bms_del_member(rinfo->required_relids, + ojrelid); distribute_restrictinfo_to_rels(root, rinfo); } } @@ -548,6 +594,7 @@ reduce_unique_semijoins(PlannerInfo *root) /* Compute the relid set for the join we are considering */ joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); + Assert(sjinfo->ojrelid == 0); /* SEMI joins don't have RT indexes */ /* * Since we're only considering a single-rel RHS, any join clauses it diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index cd68942af0b..4c99b28d0a0 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -4158,15 +4158,23 @@ create_foreignscan_plan(PlannerInfo *root, ForeignPath *best_path, /* * Likewise, copy the relids that are represented by this foreign scan. An - * upper rel doesn't have relids set, but it covers all the base relations - * participating in the underlying scan, so use root's all_baserels. + * upper rel doesn't have relids set, but it covers all the relations + * participating in the underlying scan/join, so use root->all_query_rels. */ if (rel->reloptkind == RELOPT_UPPER_REL) - scan_plan->fs_relids = root->all_baserels; + scan_plan->fs_relids = root->all_query_rels; else scan_plan->fs_relids = best_path->path.parent->relids; /* + * Join relid sets include relevant outer joins, but FDWs may need to know + * which are the included base rels. That's a bit tedious to get without + * access to the plan-time data structures, so compute it here. + */ + scan_plan->fs_base_relids = bms_difference(scan_plan->fs_relids, + root->outer_join_rels); + + /* * If this is a foreign join, and to make it valid to push down we had to * assume that the current user is the same as some user explicitly named * in the query, mark the finished plan as depending on the current user. @@ -5806,8 +5814,9 @@ make_foreignscan(List *qptlist, node->fdw_private = fdw_private; node->fdw_scan_tlist = fdw_scan_tlist; node->fdw_recheck_quals = fdw_recheck_quals; - /* fs_relids will be filled in by create_foreignscan_plan */ + /* fs_relids, fs_base_relids will be filled by create_foreignscan_plan */ node->fs_relids = NULL; + node->fs_base_relids = NULL; /* fsSystemCol will be filled in by create_foreignscan_plan */ node->fsSystemCol = false; diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index d60398f1c62..7db82915493 100644 --- a/src/backend/optimizer/plan/initsplan.c +++ b/src/backend/optimizer/plan/initsplan.c @@ -40,7 +40,43 @@ int from_collapse_limit; int join_collapse_limit; -/* Elements of the postponed_qual_list used during deconstruct_recurse */ +/* + * deconstruct_jointree requires multiple passes over the join tree, because we + * need to finish computing JoinDomains before we start distributing quals. + * As long as we have to do that, other information such as the relevant + * qualscopes might as well be computed in the first pass too. + * + * deconstruct_recurse recursively examines the join tree and builds a List + * (in depth-first traversal order) of JoinTreeItem structs, which are then + * processed iteratively by deconstruct_distribute. If there are outer + * joins, non-degenerate outer join clauses are processed in a third pass + * deconstruct_distribute_oj_quals. + * + * The JoinTreeItem structs themselves can be freed at the end of + * deconstruct_jointree, but do not modify or free their substructure, + * as the relid sets may also be pointed to by RestrictInfo and + * SpecialJoinInfo nodes. + */ +typedef struct JoinTreeItem +{ + /* Fields filled during deconstruct_recurse: */ + Node *jtnode; /* jointree node to examine */ + bool below_outer_join; /* is it below an outer join? */ + Relids qualscope; /* base+OJ Relids syntactically included in + * this jointree node */ + Relids inner_join_rels; /* base+OJ Relids syntactically included + * in inner joins appearing at or below + * this jointree node */ + Relids left_rels; /* if join node, Relids of the left side */ + Relids right_rels; /* if join node, Relids of the right side */ + Relids nonnullable_rels; /* if outer join, Relids of the + * non-nullable side */ + /* Fields filled during deconstruct_distribute: */ + SpecialJoinInfo *sjinfo; /* if outer join, its SpecialJoinInfo */ + List *oj_joinclauses; /* outer join quals not yet distributed */ +} JoinTreeItem; + +/* Elements of the postponed_qual_list used during deconstruct_distribute */ typedef struct PostponedQual { Node *qual; /* a qual clause waiting to be processed */ @@ -52,25 +88,46 @@ static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex); static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join, - Relids *qualscope, Relids *inner_join_rels, - List **postponed_qual_list); + List **item_list); +static void deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem, + List **postponed_qual_list); static void process_security_barrier_quals(PlannerInfo *root, int rti, Relids qualscope, bool below_outer_join); static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root, Relids left_rels, Relids right_rels, Relids inner_join_rels, - JoinType jointype, List *clause); + JoinType jointype, Index ojrelid, + List *clause); static void compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *clause); +static void deconstruct_distribute_oj_quals(PlannerInfo *root, + List *jtitems, + JoinTreeItem *jtitem); +static void distribute_quals_to_rels(PlannerInfo *root, List *clauses, + bool below_outer_join, + SpecialJoinInfo *sjinfo, + Index security_level, + Relids qualscope, + Relids ojscope, + Relids outerjoin_nonnullable, + bool allow_equivalence, + bool has_clone, + bool is_clone, + List **postponed_qual_list, + List **postponed_oj_qual_list); static void distribute_qual_to_rels(PlannerInfo *root, Node *clause, bool below_outer_join, - JoinType jointype, + SpecialJoinInfo *sjinfo, Index security_level, Relids qualscope, Relids ojscope, Relids outerjoin_nonnullable, - List **postponed_qual_list); + bool allow_equivalence, + bool has_clone, + bool is_clone, + List **postponed_qual_list, + List **postponed_oj_qual_list); static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p, Relids *nullable_relids_p, bool is_pushed_down); static bool check_equivalence_delay(PlannerInfo *root, @@ -248,10 +305,16 @@ add_vars_to_targetlist(PlannerInfo *root, List *vars, attno -= rel->min_attr; if (rel->attr_needed[attno] == NULL) { - /* Variable not yet requested, so add to rel's targetlist */ - /* XXX is copyObject necessary here? */ - rel->reltarget->exprs = lappend(rel->reltarget->exprs, - copyObject(var)); + /* + * Variable not yet requested, so add to rel's targetlist. + * + * The value available at the rel's scan level has not been + * nulled by any outer join, so drop its varnullingrels. + * (We'll put those back as we climb up the join tree.) + */ + var = copyObject(var); + var->varnullingrels = NULL; + rel->reltarget->exprs = lappend(rel->reltarget->exprs, var); /* reltarget cost and width will be computed later */ } rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno], @@ -547,8 +610,10 @@ create_lateral_join_info(PlannerInfo *root) varno = -1; while ((varno = bms_next_member(eval_at, varno)) >= 0) { - RelOptInfo *brel = find_base_rel(root, varno); + RelOptInfo *brel = find_base_rel_ignore_join(root, varno); + if (brel == NULL) + continue; /* ignore outer joins in eval_at */ brel->lateral_relids = bms_add_members(brel->lateral_relids, phinfo->ph_lateral); } @@ -639,7 +704,10 @@ create_lateral_join_info(PlannerInfo *root) { RelOptInfo *brel2 = root->simple_rel_array[rti2]; - Assert(brel2 != NULL && brel2->reloptkind == RELOPT_BASEREL); + if (brel2 == NULL) + continue; /* must be an OJ */ + + Assert(brel2->reloptkind == RELOPT_BASEREL); brel2->lateral_referencers = bms_add_member(brel2->lateral_referencers, rti); } @@ -683,9 +751,9 @@ List * deconstruct_jointree(PlannerInfo *root) { List *result; - Relids qualscope; - Relids inner_join_rels; + List *item_list = NIL; List *postponed_qual_list = NIL; + ListCell *lc; /* * After this point, no more PlaceHolderInfos may be made, because @@ -699,98 +767,143 @@ deconstruct_jointree(PlannerInfo *root) Assert(root->parse->jointree != NULL && IsA(root->parse->jointree, FromExpr)); - /* this is filled as we scan the jointree */ + /* These are filled as we scan the jointree */ + root->all_baserels = NULL; + root->outer_join_rels = NULL; root->nullable_baserels = NULL; - result = deconstruct_recurse(root, (Node *) root->parse->jointree, false, - &qualscope, &inner_join_rels, - &postponed_qual_list); + /* Perform the initial scan of the jointree */ + result = deconstruct_recurse(root, (Node *) root->parse->jointree, + false, + &item_list); + + /* Now we can form the value of all_query_rels, too */ + root->all_query_rels = bms_union(root->all_baserels, root->outer_join_rels); - /* Shouldn't be any leftover quals */ + /* Now scan all the jointree nodes again, and distribute quals */ + foreach(lc, item_list) + { + JoinTreeItem *jtitem = (JoinTreeItem *) lfirst(lc); + + deconstruct_distribute(root, jtitem, + &postponed_qual_list); + } + + /* Shouldn't be any leftover postponed quals */ Assert(postponed_qual_list == NIL); + /* + * However, if there were any special joins then we may have some + * postponed LEFT JOIN clauses to deal with. + */ + if (root->join_info_list) + { + /* + * XXX hack: when we call distribute_qual_to_rels to process one of + * these clauses, neither the owning SpecialJoinInfo nor any later + * ones can appear in root->join_info_list, else the wrong things will + * happen. Fake it out by emptying join_info_list and rebuilding it + * as we go. This works because join_info_list is only appended to + * during deconstruct_distribute, so we know we are examining + * SpecialJoinInfos bottom-up, just like the first time. We can get + * rid of this hack later, after fixing things so that + * distribute_qual_to_rels doesn't have that requirement about + * join_info_list. + */ + root->join_info_list = NIL; + + foreach(lc, item_list) + { + JoinTreeItem *jtitem = (JoinTreeItem *) lfirst(lc); + + if (jtitem->oj_joinclauses != NIL) + deconstruct_distribute_oj_quals(root, item_list, jtitem); + + /* XXX Rest of hack: rebuild join_info_list as we go */ + if (jtitem->sjinfo) + root->join_info_list = lappend(root->join_info_list, + jtitem->sjinfo); + } + } + + /* Don't need the JoinTreeItems any more */ + list_free_deep(item_list); + return result; } /* * deconstruct_recurse - * One recursion level of deconstruct_jointree processing. + * One recursion level of deconstruct_jointree's initial jointree scan. * * Inputs: * jtnode is the jointree node to examine * below_outer_join is true if this node is within the nullable side of a * higher-level outer join - * 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) - * *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) - * *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 - * Return value is the appropriate joinlist for this jointree node * - * In addition, entries will be added to root->join_info_list for outer joins. + * item_list is an in/out parameter: we add a JoinTreeItem struct to + * that list for each jointree node, in depth-first traversal order. + * (Hence, after each call, the last list item corresponds to its jtnode.) + * + * Return value is the appropriate joinlist for this jointree node. */ static List * -deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join, - Relids *qualscope, Relids *inner_join_rels, - List **postponed_qual_list) +deconstruct_recurse(PlannerInfo *root, Node *jtnode, + bool below_outer_join, + List **item_list) { List *joinlist; + JoinTreeItem *jtitem; + + Assert(jtnode != NULL); + + /* Make the new JoinTreeItem, but don't add it to item_list yet */ + jtitem = palloc0_object(JoinTreeItem); + jtitem->jtnode = jtnode; + jtitem->below_outer_join = below_outer_join; - if (jtnode == NULL) - { - *qualscope = NULL; - *inner_join_rels = NULL; - return NIL; - } if (IsA(jtnode, RangeTblRef)) { int varno = ((RangeTblRef *) jtnode)->rtindex; + /* Fill all_baserels as we encounter baserel jointree nodes */ + root->all_baserels = bms_add_member(root->all_baserels, varno); /* qualscope is just the one RTE */ - *qualscope = bms_make_singleton(varno); - /* Deal with any securityQuals attached to the RTE */ - if (root->qual_security_level > 0) - process_security_barrier_quals(root, - varno, - *qualscope, - below_outer_join); + jtitem->qualscope = bms_make_singleton(varno); /* A single baserel does not create an inner join */ - *inner_join_rels = NULL; + jtitem->inner_join_rels = NULL; joinlist = list_make1(jtnode); } else if (IsA(jtnode, 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. + * Recurse to handle child nodes, and compute output joinlist. 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; + jtitem->qualscope = NULL; + jtitem->inner_join_rels = NULL; joinlist = NIL; remaining = list_length(f->fromlist); foreach(l, f->fromlist) { - Relids sub_qualscope; + JoinTreeItem *sub_item; 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); + item_list); + sub_item = (JoinTreeItem *) llast(*item_list); + jtitem->qualscope = bms_add_members(jtitem->qualscope, + sub_item->qualscope); + jtitem->inner_join_rels = sub_item->inner_join_rels; sub_members = list_length(sub_joinlist); remaining--; if (sub_members <= 1 || @@ -808,115 +921,90 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join, * that still possible?) the initialization before the loop fixed it. */ if (list_length(f->fromlist) > 1) - *inner_join_rels = *qualscope; - - /* - * 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)) - distribute_qual_to_rels(root, pq->qual, - below_outer_join, JOIN_INNER, - root->qual_security_level, - *qualscope, NULL, NULL, - NULL); - else - *postponed_qual_list = lappend(*postponed_qual_list, pq); - } - - /* - * Now process the top-level quals. - */ - foreach(l, (List *) f->quals) - { - Node *qual = (Node *) lfirst(l); - - distribute_qual_to_rels(root, qual, - below_outer_join, JOIN_INNER, - root->qual_security_level, - *qualscope, NULL, NULL, - postponed_qual_list); - } + jtitem->inner_join_rels = jtitem->qualscope; } else if (IsA(jtnode, JoinExpr)) { JoinExpr *j = (JoinExpr *) jtnode; - List *child_postponed_quals = NIL; - Relids leftids, - rightids, - left_inners, - right_inners, - nonnullable_rels, - nullable_rels, - ojscope; + Relids nullable_rels; + JoinTreeItem *left_item, + *right_item; 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: + /* Recurse */ leftjoinlist = deconstruct_recurse(root, j->larg, below_outer_join, - &leftids, &left_inners, - &child_postponed_quals); + item_list); + left_item = (JoinTreeItem *) llast(*item_list); rightjoinlist = deconstruct_recurse(root, j->rarg, below_outer_join, - &rightids, &right_inners, - &child_postponed_quals); - *qualscope = bms_union(leftids, rightids); - *inner_join_rels = *qualscope; + item_list); + right_item = (JoinTreeItem *) llast(*item_list); + /* Compute qualscope etc */ + jtitem->qualscope = bms_union(left_item->qualscope, + right_item->qualscope); + jtitem->inner_join_rels = jtitem->qualscope; + jtitem->left_rels = left_item->qualscope; + jtitem->right_rels = right_item->qualscope; /* Inner join adds no restrictions for quals */ - nonnullable_rels = NULL; + jtitem->nonnullable_rels = NULL; /* and it doesn't force anything to null, either */ nullable_rels = NULL; break; case JOIN_LEFT: case JOIN_ANTI: + /* Recurse */ leftjoinlist = deconstruct_recurse(root, j->larg, below_outer_join, - &leftids, &left_inners, - &child_postponed_quals); + item_list); + left_item = (JoinTreeItem *) llast(*item_list); 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; + item_list); + right_item = (JoinTreeItem *) llast(*item_list); + /* Compute qualscope etc */ + jtitem->qualscope = bms_union(left_item->qualscope, + right_item->qualscope); + /* caution: ANTI join derived from SEMI will lack rtindex */ + if (j->rtindex != 0) + { + jtitem->qualscope = bms_add_member(jtitem->qualscope, + j->rtindex); + root->outer_join_rels = bms_add_member(root->outer_join_rels, + j->rtindex); + } + jtitem->inner_join_rels = bms_union(left_item->inner_join_rels, + right_item->inner_join_rels); + jtitem->left_rels = left_item->qualscope; + jtitem->right_rels = right_item->qualscope; + jtitem->nonnullable_rels = left_item->qualscope; + nullable_rels = right_item->qualscope; break; case JOIN_SEMI: + /* Recurse */ leftjoinlist = deconstruct_recurse(root, j->larg, below_outer_join, - &leftids, &left_inners, - &child_postponed_quals); + item_list); + left_item = (JoinTreeItem *) llast(*item_list); 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); + item_list); + right_item = (JoinTreeItem *) llast(*item_list); + /* Compute qualscope etc */ + jtitem->qualscope = bms_union(left_item->qualscope, + right_item->qualscope); + /* SEMI join never has rtindex, so don't add to anything */ + Assert(j->rtindex == 0); + jtitem->inner_join_rels = bms_union(left_item->inner_join_rels, + right_item->inner_join_rels); + jtitem->left_rels = left_item->qualscope; + jtitem->right_rels = right_item->qualscope; /* Semi join adds no restrictions for quals */ - nonnullable_rels = NULL; + jtitem->nonnullable_rels = NULL; /* * Theoretically, a semijoin would null the RHS; but since the @@ -926,27 +1014,37 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join, nullable_rels = NULL; break; case JOIN_FULL: + /* Recurse */ leftjoinlist = deconstruct_recurse(root, j->larg, true, - &leftids, &left_inners, - &child_postponed_quals); + item_list); + left_item = (JoinTreeItem *) llast(*item_list); 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); + item_list); + right_item = (JoinTreeItem *) llast(*item_list); + /* Compute qualscope etc */ + jtitem->qualscope = bms_union(left_item->qualscope, + right_item->qualscope); + Assert(j->rtindex != 0); + jtitem->qualscope = bms_add_member(jtitem->qualscope, + j->rtindex); + root->outer_join_rels = bms_add_member(root->outer_join_rels, + j->rtindex); + jtitem->inner_join_rels = bms_union(left_item->inner_join_rels, + right_item->inner_join_rels); + jtitem->left_rels = left_item->qualscope; + jtitem->right_rels = right_item->qualscope; /* each side is both outer and inner */ - nonnullable_rels = *qualscope; - nullable_rels = *qualscope; + jtitem->nonnullable_rels = jtitem->qualscope; + nullable_rels = jtitem->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 */ + leftjoinlist = rightjoinlist = NIL; /* keep compiler quiet */ nullable_rels = NULL; - leftjoinlist = rightjoinlist = NIL; break; } @@ -955,17 +1053,145 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join, nullable_rels); /* + * 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 */ + } + + /* Finally, we can add the new JoinTreeItem to item_list */ + *item_list = lappend(*item_list, jtitem); + + return joinlist; +} + +/* + * deconstruct_distribute + * Process one jointree node in phase 2 of deconstruct_jointree processing. + * + * Distribute quals of the node to appropriate restriction and join lists. + * In addition, entries will be added to root->join_info_list for outer joins. + * + * Inputs: + * jtitem is the JoinTreeItem to examine + * Input/Outputs: + * *postponed_qual_list is a list of PostponedQual structs + * + * On entry, *postponed_qual_list contains any quals that had to be postponed + * out of lower join levels (because they contain lateral references). + * On exit, *postponed_qual_list contains quals that can't be processed yet + * (because their lateral references are still unsatisfied). + */ +static void +deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem, + List **postponed_qual_list) +{ + Node *jtnode = jtitem->jtnode; + + if (IsA(jtnode, RangeTblRef)) + { + int varno = ((RangeTblRef *) jtnode)->rtindex; + + /* Deal with any securityQuals attached to the RTE */ + if (root->qual_security_level > 0) + process_security_barrier_quals(root, + varno, + jtitem->qualscope, + jtitem->below_outer_join); + } + else if (IsA(jtnode, FromExpr)) + { + FromExpr *f = (FromExpr *) jtnode; + List *new_postponed_quals = NIL; + ListCell *l; + + /* + * Try to process any quals postponed by children. If they need + * further postponement, add them to my output postponed_qual_list. + */ + foreach(l, *postponed_qual_list) + { + PostponedQual *pq = (PostponedQual *) lfirst(l); + + if (bms_is_subset(pq->relids, jtitem->qualscope)) + distribute_qual_to_rels(root, pq->qual, + jtitem->below_outer_join, + NULL, + root->qual_security_level, + jtitem->qualscope, NULL, NULL, + true, false, false, + NULL, NULL); + else + new_postponed_quals = lappend(new_postponed_quals, pq); + } + *postponed_qual_list = new_postponed_quals; + + /* + * Now process the top-level quals. + */ + distribute_quals_to_rels(root, (List *) f->quals, + jtitem->below_outer_join, + NULL, + root->qual_security_level, + jtitem->qualscope, NULL, NULL, + true, false, false, + postponed_qual_list, NULL); + } + else if (IsA(jtnode, JoinExpr)) + { + JoinExpr *j = (JoinExpr *) jtnode; + List *new_postponed_quals = NIL; + Relids ojscope; + List *my_quals; + SpecialJoinInfo *sjinfo; + List **postponed_oj_qual_list; + ListCell *l; + + /* * 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) + foreach(l, *postponed_qual_list) { PostponedQual *pq = (PostponedQual *) lfirst(l); - if (bms_is_subset(pq->relids, *qualscope)) + if (bms_is_subset(pq->relids, jtitem->qualscope)) my_quals = lappend(my_quals, pq->qual); else { @@ -974,16 +1200,15 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join, * If this Assert fires, pull_up_subqueries() messed up. */ Assert(j->jointype == JOIN_INNER); - *postponed_qual_list = lappend(*postponed_qual_list, pq); + new_postponed_quals = lappend(new_postponed_quals, pq); } } + *postponed_qual_list = new_postponed_quals; 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. + * For an OJ, form the SpecialJoinInfo now, so that we can pass it to + * distribute_qual_to_rels. We must compute its ojscope too. * * Semijoins are a bit of a hybrid: we build a SpecialJoinInfo, but we * want ojscope = NULL for distribute_qual_to_rels. @@ -991,15 +1216,33 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join, if (j->jointype != JOIN_INNER) { sjinfo = make_outerjoininfo(root, - leftids, rightids, - *inner_join_rels, + jtitem->left_rels, + jtitem->right_rels, + jtitem->inner_join_rels, j->jointype, + j->rtindex, my_quals); + jtitem->sjinfo = sjinfo; if (j->jointype == JOIN_SEMI) ojscope = NULL; else + { ojscope = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); + + /* + * Add back any commutable lower OJ relids that were removed + * from min_lefthand or min_righthand, else the ojscope + * cross-check in distribute_qual_to_rels will complain. If + * any such OJs were removed, we will postpone processing of + * non-degenerate clauses, so this addition doesn't affect + * anything except that cross-check and some Asserts. Real + * clause positioning decisions will be made later, when we + * revisit the postponed clauses. + */ + if (sjinfo->commute_below) + ojscope = bms_add_members(ojscope, sjinfo->commute_below); + } } else { @@ -1007,68 +1250,43 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join, ojscope = NULL; } - /* Process the JOIN's qual clauses */ - foreach(l, my_quals) - { - Node *qual = (Node *) lfirst(l); - - distribute_qual_to_rels(root, qual, - below_outer_join, j->jointype, - root->qual_security_level, - *qualscope, - ojscope, nonnullable_rels, - postponed_qual_list); - } + /* + * If it's a left join with a join clause that is strict for the LHS, + * then we need to postpone handling of any non-degenerate join + * clauses, in case the join is able to commute with another left join + * per identity 3. (Degenerate clauses need not be postponed, since + * they will drop down below this join anyway.) + */ + if (j->jointype == JOIN_LEFT && sjinfo->lhs_strict) + postponed_oj_qual_list = &jtitem->oj_joinclauses; + else + postponed_oj_qual_list = NULL; - /* Now we can add the SpecialJoinInfo to join_info_list */ + /* Process the JOIN's qual clauses */ + distribute_quals_to_rels(root, my_quals, + jtitem->below_outer_join, + sjinfo, + root->qual_security_level, + jtitem->qualscope, + ojscope, jtitem->nonnullable_rels, + true, /* allow_equivalence */ + false, false, /* not clones */ + postponed_qual_list, + postponed_oj_qual_list); + + /* And 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; } /* @@ -1102,27 +1320,24 @@ process_security_barrier_quals(PlannerInfo *root, foreach(lc, rte->securityQuals) { List *qualset = (List *) lfirst(lc); - ListCell *lc2; - foreach(lc2, qualset) - { - Node *qual = (Node *) lfirst(lc2); - - /* - * We cheat to the extent of passing ojscope = qualscope rather - * than its more logical value of NULL. The only effect this has - * is to force a Var-free qual to be evaluated at the rel rather - * than being pushed up to top of tree, which we don't want. - */ - distribute_qual_to_rels(root, qual, - below_outer_join, - JOIN_INNER, - security_level, - qualscope, - qualscope, - NULL, - NULL); - } + /* + * We cheat to the extent of passing ojscope = qualscope rather than + * its more logical value of NULL. The only effect this has is to + * force a Var-free qual to be evaluated at the rel rather than being + * pushed up to top of tree, which we don't want. + */ + distribute_quals_to_rels(root, qualset, + below_outer_join, + NULL, + security_level, + qualscope, + qualscope, + NULL, + true, + false, false, /* not clones */ + NULL, + NULL); security_level++; } @@ -1135,10 +1350,11 @@ process_security_barrier_quals(PlannerInfo *root, * Build a SpecialJoinInfo for the current outer join * * Inputs: - * left_rels: the base Relids syntactically on outer side of join - * right_rels: the base Relids syntactically on inner side of join - * inner_join_rels: base Relids participating in inner joins below this one + * left_rels: the base+OJ Relids syntactically on outer side of join + * right_rels: the base+OJ Relids syntactically on inner side of join + * inner_join_rels: base+OJ Relids participating in inner joins below this one * jointype: what it says (must always be LEFT, FULL, SEMI, or ANTI) + * ojrelid: RT index of the join RTE (0 for SEMI, which isn't in the RT list) * clause: the outer join's join condition (in implicit-AND format) * * The node should eventually be appended to root->join_info_list, but we @@ -1152,7 +1368,8 @@ static SpecialJoinInfo * make_outerjoininfo(PlannerInfo *root, Relids left_rels, Relids right_rels, Relids inner_join_rels, - JoinType jointype, List *clause) + JoinType jointype, Index ojrelid, + List *clause) { SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo); Relids clause_relids; @@ -1200,6 +1417,11 @@ make_outerjoininfo(PlannerInfo *root, sjinfo->syn_lefthand = left_rels; sjinfo->syn_righthand = right_rels; sjinfo->jointype = jointype; + sjinfo->ojrelid = ojrelid; + /* these fields may get added to later: */ + sjinfo->commute_above_l = NULL; + sjinfo->commute_above_r = NULL; + sjinfo->commute_below = NULL; /* this always starts out false */ sjinfo->delay_upper_joins = false; @@ -1247,6 +1469,7 @@ make_outerjoininfo(PlannerInfo *root, foreach(l, root->join_info_list) { SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l); + bool have_unsafe_phvs; /* * A full join is an optimization barrier: we can't associate into or @@ -1262,6 +1485,9 @@ make_outerjoininfo(PlannerInfo *root, otherinfo->syn_lefthand); min_lefthand = bms_add_members(min_lefthand, otherinfo->syn_righthand); + if (otherinfo->ojrelid != 0) + min_lefthand = bms_add_member(min_lefthand, + otherinfo->ojrelid); } if (bms_overlap(right_rels, otherinfo->syn_lefthand) || bms_overlap(right_rels, otherinfo->syn_righthand)) @@ -1270,35 +1496,71 @@ make_outerjoininfo(PlannerInfo *root, otherinfo->syn_lefthand); min_righthand = bms_add_members(min_righthand, otherinfo->syn_righthand); + if (otherinfo->ojrelid != 0) + min_righthand = bms_add_member(min_righthand, + otherinfo->ojrelid); } /* Needn't do anything else with the full join */ continue; } /* + * If our join condition contains any PlaceHolderVars that need to be + * evaluated above the lower OJ, then we can't commute with it. + */ + if (otherinfo->ojrelid != 0) + have_unsafe_phvs = + contain_placeholder_references_to(root, + (Node *) clause, + otherinfo->ojrelid); + else + have_unsafe_phvs = false; + + /* * For a lower OJ in our LHS, if our join condition uses the lower * join's RHS and is not strict for that rel, we must preserve the * ordering of the two OJs, so add lower OJ's full syntactic relset to * min_lefthand. (We must use its full syntactic relset, not just its * min_lefthand + min_righthand. This is because there might be other * OJs below this one that this one can commute with, but we cannot - * commute with them if we don't with this one.) Also, if the current - * join is a semijoin or antijoin, we must preserve ordering - * regardless of strictness. + * commute with them if we don't with this one.) Also, if we have + * unsafe PHVs or the current join is a semijoin or antijoin, we must + * preserve ordering regardless of strictness. * * Note: I believe we have to insist on being strict for at least one * rel in the lower OJ's min_righthand, not its whole syn_righthand. + * + * When we don't need to preserve ordering, check to see if outer join + * identity 3 applies, and if so, remove the lower OJ's ojrelid from + * our min_lefthand so that commutation is allowed. */ if (bms_overlap(left_rels, otherinfo->syn_righthand)) { if (bms_overlap(clause_relids, otherinfo->syn_righthand) && - (jointype == JOIN_SEMI || jointype == JOIN_ANTI || + (have_unsafe_phvs || + jointype == JOIN_SEMI || jointype == JOIN_ANTI || !bms_overlap(strict_relids, otherinfo->min_righthand))) { + /* Preserve ordering */ min_lefthand = bms_add_members(min_lefthand, otherinfo->syn_lefthand); min_lefthand = bms_add_members(min_lefthand, otherinfo->syn_righthand); + if (otherinfo->ojrelid != 0) + min_lefthand = bms_add_member(min_lefthand, + otherinfo->ojrelid); + } + else if (jointype == JOIN_LEFT && + otherinfo->jointype == JOIN_LEFT && + bms_overlap(strict_relids, otherinfo->min_righthand)) + { + /* Identity 3 applies, so remove the ordering restriction */ + min_lefthand = bms_del_member(min_lefthand, otherinfo->ojrelid); + /* Add commutability markers to both SpecialJoinInfos */ + otherinfo->commute_above_l = + bms_add_member(otherinfo->commute_above_l, ojrelid); + sjinfo->commute_below = + bms_add_member(sjinfo->commute_below, otherinfo->ojrelid); } } @@ -1313,8 +1575,8 @@ make_outerjoininfo(PlannerInfo *root, * up with SpecialJoinInfos with identical min_righthands, which can * confuse join_is_legal (see discussion in backend/optimizer/README). * - * Also, we must preserve ordering anyway if either the current join - * or the lower OJ is either a semijoin or an antijoin. + * Also, we must preserve ordering anyway if we have unsafe PHVs, or + * if either this join or the lower OJ is a semijoin or antijoin. * * Here, we have to consider that "our join condition" includes any * clauses that syntactically appeared above the lower OJ and below @@ -1326,21 +1588,43 @@ make_outerjoininfo(PlannerInfo *root, * join condition are not affected by them. The net effect is * therefore sufficiently represented by the delay_upper_joins flag * saved for us by check_outerjoin_delay. + * + * When we don't need to preserve ordering, check to see if outer join + * identity 3 applies, and if so, remove the lower OJ's ojrelid from + * our min_righthand so that commutation is allowed. */ if (bms_overlap(right_rels, otherinfo->syn_righthand)) { if (bms_overlap(clause_relids, otherinfo->syn_righthand) || !bms_overlap(clause_relids, otherinfo->min_lefthand) || + have_unsafe_phvs || jointype == JOIN_SEMI || jointype == JOIN_ANTI || otherinfo->jointype == JOIN_SEMI || otherinfo->jointype == JOIN_ANTI || !otherinfo->lhs_strict || otherinfo->delay_upper_joins) { + /* Preserve ordering */ min_righthand = bms_add_members(min_righthand, otherinfo->syn_lefthand); min_righthand = bms_add_members(min_righthand, otherinfo->syn_righthand); + if (otherinfo->ojrelid != 0) + min_righthand = bms_add_member(min_righthand, + otherinfo->ojrelid); + } + else if (jointype == JOIN_LEFT && + otherinfo->jointype == JOIN_LEFT && + otherinfo->lhs_strict) + { + /* Identity 3 applies, so remove the ordering restriction */ + min_righthand = bms_del_member(min_righthand, + otherinfo->ojrelid); + /* Add commutability markers to both SpecialJoinInfos */ + otherinfo->commute_above_r = + bms_add_member(otherinfo->commute_above_r, ojrelid); + sjinfo->commute_below = + bms_add_member(sjinfo->commute_below, otherinfo->ojrelid); } } } @@ -1565,6 +1849,221 @@ compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *clause) sjinfo->semi_rhs_exprs = semi_rhs_exprs; } +/* + * deconstruct_distribute_oj_quals + * Adjust LEFT JOIN quals to be suitable for commuted-left-join cases, + * then push them into the joinqual lists and EquivalenceClass structures. + * + * This runs immediately after we've completed the deconstruct_distribute scan. + * jtitems contains all the JoinTreeItems (in depth-first order), and jtitem + * is one that has postponed oj_joinclauses to deal with. + */ +static void +deconstruct_distribute_oj_quals(PlannerInfo *root, + List *jtitems, + JoinTreeItem *jtitem) +{ + SpecialJoinInfo *sjinfo = jtitem->sjinfo; + Relids qualscope, + ojscope, + nonnullable_rels; + + /* Recompute syntactic and semantic scopes of this left join */ + qualscope = bms_union(sjinfo->syn_lefthand, sjinfo->syn_righthand); + qualscope = bms_add_member(qualscope, sjinfo->ojrelid); + ojscope = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); + nonnullable_rels = sjinfo->syn_lefthand; + + /* + * If this join can commute with any other ones per outer-join identity 3, + * and it is the one providing the join clause with flexible semantics, + * then we have to generate variants of the join clause with different + * nullingrels labeling. Otherwise, just push out the postponed clause + * as-is. + */ + Assert(sjinfo->lhs_strict); /* else we shouldn't be here */ + if (sjinfo->commute_above_r || + bms_overlap(sjinfo->commute_below, sjinfo->syn_lefthand)) + { + Relids joins_above; + Relids joins_below; + Relids joins_so_far; + List *quals; + int save_last_rinfo_serial; + ListCell *lc; + + /* + * Put any OJ relids that were removed from min_righthand back into + * ojscope, else distribute_qual_to_rels will complain. + */ + ojscope = bms_join(ojscope, bms_intersect(sjinfo->commute_below, + sjinfo->syn_righthand)); + + /* Identify the outer joins this one commutes with */ + joins_above = sjinfo->commute_above_r; + joins_below = bms_intersect(sjinfo->commute_below, + sjinfo->syn_lefthand); + + /* + * Generate qual variants with different sets of nullingrels bits. + * + * We only need bit-sets that correspond to the successively less + * deeply syntactically-nested subsets of this join and its + * commutators. That's true first because obviously only those forms + * of the Vars and PHVs could appear elsewhere in the query, and + * second because the outer join identities do not provide a way to + * re-order such joins in a way that would require different marking. + * (That is, while the current join may commute with several others, + * none of those others can commute with each other.) To visit the + * interesting joins in syntactic nesting order, we rely on the + * jtitems list to be ordered that way. + * + * We first strip out all the nullingrels bits corresponding to + * commutating joins below this one, and then successively put them + * back as we crawl up the join stack. + */ + quals = jtitem->oj_joinclauses; + if (!bms_is_empty(joins_below)) + quals = (List *) remove_nulling_relids((Node *) quals, + joins_below, + NULL); + + /* + * Each time we produce RestrictInfo(s) from these quals, reset the + * last_rinfo_serial counter, so that the RestrictInfos for the "same" + * qual condition get identical serial numbers. (This relies on the + * fact that we're not changing the qual list in any way that'd affect + * the number of RestrictInfos built from it.) This'll allow us to + * detect duplicative qual usage later. + */ + save_last_rinfo_serial = root->last_rinfo_serial; + + joins_so_far = NULL; + foreach(lc, jtitems) + { + JoinTreeItem *otherjtitem = (JoinTreeItem *) lfirst(lc); + SpecialJoinInfo *othersj = otherjtitem->sjinfo; + bool below_sjinfo = false; + bool above_sjinfo = false; + Relids this_qualscope; + Relids this_ojscope; + bool allow_equivalence, + has_clone, + is_clone; + + if (othersj == NULL) + continue; /* not an outer-join item, ignore */ + + if (bms_is_member(othersj->ojrelid, joins_below)) + { + /* othersj commutes with sjinfo from below left */ + below_sjinfo = true; + } + else if (othersj == sjinfo) + { + /* found our join in syntactic order */ + Assert(bms_equal(joins_so_far, joins_below)); + } + else if (bms_is_member(othersj->ojrelid, joins_above)) + { + /* othersj commutes with sjinfo from above */ + above_sjinfo = true; + } + else + { + /* othersj is not relevant, ignore */ + continue; + } + + /* Reset serial counter for this version of the quals */ + root->last_rinfo_serial = save_last_rinfo_serial; + + /* + * When we are looking at joins above sjinfo, we are envisioning + * pushing sjinfo to above othersj, so add othersj's nulling bit + * before distributing the quals. + */ + if (above_sjinfo) + quals = (List *) + add_nulling_relids((Node *) quals, + othersj->min_righthand, + bms_make_singleton(othersj->ojrelid)); + + /* Compute qualscope and ojscope for this join level */ + this_qualscope = bms_union(qualscope, joins_so_far); + this_ojscope = bms_union(ojscope, joins_so_far); + if (above_sjinfo) + { + /* othersj is not yet in joins_so_far, but we need it */ + this_qualscope = bms_add_member(this_qualscope, + othersj->ojrelid); + this_ojscope = bms_add_member(this_ojscope, + othersj->ojrelid); + /* sjinfo is in joins_so_far, and we don't want it */ + this_ojscope = bms_del_member(this_ojscope, + sjinfo->ojrelid); + } + + /* + * We generate EquivalenceClasses only from the first form of the + * quals, with the fewest nullingrels bits set. An EC made from + * this version of the quals can be useful below the outer-join + * nest, whereas versions with some nullingrels bits set would not + * be. We cannot generate ECs from more than one version, or + * we'll make nonsensical conclusions that Vars with nullingrels + * bits set are equal to their versions without. Fortunately, + * such ECs wouldn't be very useful anyway, because they'd equate + * values not observable outside the join nest. (See + * optimizer/README.) + * + * The first form of the quals is also the only one marked as + * has_clone rather than is_clone. + */ + allow_equivalence = (joins_so_far == NULL); + has_clone = allow_equivalence; + is_clone = !has_clone; + + distribute_quals_to_rels(root, quals, + true, + sjinfo, + root->qual_security_level, + this_qualscope, + this_ojscope, nonnullable_rels, + allow_equivalence, + has_clone, + is_clone, + NULL, NULL); /* no more postponement */ + + /* + * Adjust qual nulling bits for next level up, if needed. We + * don't want to put sjinfo's own bit in at all, and if we're + * above sjinfo then we did it already. + */ + if (below_sjinfo) + quals = (List *) + add_nulling_relids((Node *) quals, + othersj->min_righthand, + bms_make_singleton(othersj->ojrelid)); + + /* ... and track joins processed so far */ + joins_so_far = bms_add_member(joins_so_far, othersj->ojrelid); + } + } + else + { + /* No commutation possible, just process the postponed clauses */ + distribute_quals_to_rels(root, jtitem->oj_joinclauses, + true, + sjinfo, + root->qual_security_level, + qualscope, + ojscope, nonnullable_rels, + true, /* allow_equivalence */ + false, false, /* not clones */ + NULL, NULL); /* no more postponement */ + } +} + /***************************************************************************** * @@ -1573,48 +2072,102 @@ compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *clause) *****************************************************************************/ /* + * distribute_quals_to_rels + * Convenience routine to apply distribute_qual_to_rels to each element + * of an AND'ed list of clauses. + */ +static void +distribute_quals_to_rels(PlannerInfo *root, List *clauses, + bool below_outer_join, + SpecialJoinInfo *sjinfo, + Index security_level, + Relids qualscope, + Relids ojscope, + Relids outerjoin_nonnullable, + bool allow_equivalence, + bool has_clone, + bool is_clone, + List **postponed_qual_list, + List **postponed_oj_qual_list) +{ + ListCell *lc; + + foreach(lc, clauses) + { + Node *clause = (Node *) lfirst(lc); + + distribute_qual_to_rels(root, clause, + below_outer_join, + sjinfo, + security_level, + qualscope, + ojscope, + outerjoin_nonnullable, + allow_equivalence, + has_clone, + is_clone, + postponed_qual_list, + postponed_oj_qual_list); + } +} + +/* * 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. + * mergejoinable operator, enter its left- and right-side expressions into + * the query's EquivalenceClasses. + * + * In some cases, quals will be added to postponed_qual_list or + * postponed_oj_qual_list instead of being processed right away. + * These will be dealt with in later steps of deconstruct_jointree. * * 'clause': the qual clause to be distributed * 'below_outer_join': true if the qual is from a JOIN/ON that is below the * nullable side of a higher-level outer join - * 'jointype': type of join the qual is from (JOIN_INNER for a WHERE clause) + * 'sjinfo': join's SpecialJoinInfo (NULL for an inner join or WHERE clause) * 'security_level': security_level to assign to the qual - * 'qualscope': set of baserels the qual's syntactic scope covers - * 'ojscope': NULL if not an outer-join qual, else the minimum set of baserels - * needed to form this join + * 'qualscope': set of base+OJ rels the qual's syntactic scope covers + * 'ojscope': NULL if not an outer-join qual, else the minimum set of base+OJ + * rels needed to form this join * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of - * baserels appearing on the outer (nonnullable) side of the join + * base+OJ rels 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) + * 'allow_equivalence': true if it's okay to convert clause into an + * EquivalenceClass + * 'has_clone': has_clone property to assign to the qual + * 'is_clone': is_clone property to assign to the qual * '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. * Can be NULL if caller knows postponement is impossible. + * 'postponed_oj_qual_list': if not NULL, non-degenerate outer join clauses + * should be added to this list instead of being processed (list entries + * are just the bare clauses) * * 'qualscope' identifies what level of JOIN the qual came from syntactically. * 'ojscope' is needed if we decide to force the qual up to the outer-join * level, which will be ojscope not necessarily qualscope. * * 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. + * all and only those special joins that are syntactically below this qual; + * in particular, the passed-in SpecialJoinInfo isn't yet in that list. */ static void distribute_qual_to_rels(PlannerInfo *root, Node *clause, bool below_outer_join, - JoinType jointype, + SpecialJoinInfo *sjinfo, Index security_level, Relids qualscope, Relids ojscope, Relids outerjoin_nonnullable, - List **postponed_qual_list) + bool allow_equivalence, + bool has_clone, + bool is_clone, + List **postponed_qual_list, + List **postponed_oj_qual_list) { Relids relids; bool is_pushed_down; @@ -1646,7 +2199,7 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, PostponedQual *pq = (PostponedQual *) palloc(sizeof(PostponedQual)); Assert(root->hasLateralRTEs); /* shouldn't happen otherwise */ - Assert(jointype == JOIN_INNER); /* mustn't postpone past outer join */ + Assert(sjinfo == NULL); /* mustn't postpone past outer join */ pq->qual = clause; pq->relids = relids; *postponed_qual_list = lappend(*postponed_qual_list, pq); @@ -1708,7 +2261,7 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, { relids = get_relids_in_jointree((Node *) root->parse->jointree, - false); + true, false); qualscope = bms_copy(relids); } } @@ -1751,8 +2304,18 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, { /* * The qual is attached to an outer join and mentions (some of the) - * rels on the nonnullable side, so it's not degenerate. - * + * rels on the nonnullable side, so it's not degenerate. If the + * caller wants to postpone handling such clauses, just add it to + * postponed_oj_qual_list and return. (The work we've done up to here + * will have to be redone later, but there's not much of it.) + */ + if (postponed_oj_qual_list != NULL) + { + *postponed_oj_qual_list = lappend(*postponed_oj_qual_list, clause); + return; + } + + /* * 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 @@ -1818,6 +2381,11 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, if (check_redundant_nullability_qual(root, clause)) return; } + else if (!allow_equivalence) + { + /* Caller says it mustn't become an equivalence class */ + maybe_equivalence = false; + } else { /* @@ -1852,11 +2420,22 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, outerjoin_nonnullable, nullable_relids); + /* Apply appropriate clone marking, too */ + restrictinfo->has_clone = has_clone; + restrictinfo->is_clone = is_clone; + /* - * 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!). + * If it's a join clause, 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!). + * + * Normally we mark the vars as needed at the join identified by "relids". + * However, if this is a clone clause then ignore the outer-join relids in + * that set. Otherwise, vars appearing in a cloned clause would end up + * marked as having to propagate to the highest one of the commuting + * joins, which would often be an overestimate. For such clauses, correct + * var propagation is ensured by making ojscope include input rels from + * both sides of the join. * * 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 @@ -1869,8 +2448,13 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, PVC_RECURSE_AGGREGATES | PVC_RECURSE_WINDOWFUNCS | PVC_INCLUDE_PLACEHOLDERS); + Relids where_needed; - add_vars_to_targetlist(root, vars, relids); + if (is_clone) + where_needed = bms_intersect(relids, root->all_baserels); + else + where_needed = relids; + add_vars_to_targetlist(root, vars, where_needed); list_free(vars); } @@ -1930,14 +2514,19 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, /* 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 */ + Assert(sjinfo != NULL); if (bms_is_subset(restrictinfo->left_relids, outerjoin_nonnullable) && !bms_overlap(restrictinfo->right_relids, outerjoin_nonnullable)) { /* we have outervar = innervar */ + OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo); + + ojcinfo->rinfo = restrictinfo; + ojcinfo->sjinfo = sjinfo; root->left_join_clauses = lappend(root->left_join_clauses, - restrictinfo); + ojcinfo); return; } if (bms_is_subset(restrictinfo->right_relids, @@ -1946,15 +2535,23 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, outerjoin_nonnullable)) { /* we have innervar = outervar */ + OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo); + + ojcinfo->rinfo = restrictinfo; + ojcinfo->sjinfo = sjinfo; root->right_join_clauses = lappend(root->right_join_clauses, - restrictinfo); + ojcinfo); return; } - if (jointype == JOIN_FULL) + if (sjinfo->jointype == JOIN_FULL) { /* FULL JOIN (above tests cannot match in this case) */ + OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo); + + ojcinfo->rinfo = restrictinfo; + ojcinfo->sjinfo = sjinfo; root->full_join_clauses = lappend(root->full_join_clauses, - restrictinfo); + ojcinfo); return; } /* nope, so fall through to distribute_restrictinfo_to_rels */ @@ -2348,7 +2945,7 @@ process_implied_equality(PlannerInfo *root, { relids = get_relids_in_jointree((Node *) root->parse->jointree, - false); + true, false); } } } diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 05f44faf6eb..320caebd874 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -627,6 +627,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse, root->multiexpr_params = NIL; root->eq_classes = NIL; root->ec_merging_done = false; + root->last_rinfo_serial = 0; root->all_result_relids = parse->resultRelation ? bms_make_singleton(parse->resultRelation) : NULL; root->leaf_result_relids = NULL; /* we'll find out leaf-ness later */ @@ -912,7 +913,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse, */ if (rte->lateral && root->hasJoinRTEs) rte->subquery = (Query *) - flatten_join_alias_vars(root->parse, + flatten_join_alias_vars(root, root->parse, (Node *) rte->subquery); } else if (rte->rtekind == RTE_FUNCTION) @@ -1110,7 +1111,7 @@ preprocess_expression(PlannerInfo *root, Node *expr, int kind) kind == EXPRKIND_VALUES || kind == EXPRKIND_TABLESAMPLE || kind == EXPRKIND_TABLEFUNC)) - expr = flatten_join_alias_vars(root->parse, expr); + expr = flatten_join_alias_vars(root, root->parse, expr); /* * Simplify constant expressions. For function RTEs, this was already @@ -2246,7 +2247,7 @@ preprocess_rowmarks(PlannerInfo *root) * make a bitmapset of all base rels and then remove the items we don't * need or have FOR [KEY] UPDATE/SHARE marks for. */ - rels = get_relids_in_jointree((Node *) parse->jointree, false); + rels = get_relids_in_jointree((Node *) parse->jointree, false, false); if (parse->resultRelation) rels = bms_del_member(rels, parse->resultRelation); diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index 85ba9d1ca1e..4348bfef601 100644 --- a/src/backend/optimizer/plan/setrefs.c +++ b/src/backend/optimizer/plan/setrefs.c @@ -30,11 +30,21 @@ #include "utils/syscache.h" +typedef enum +{ + NRM_EQUAL, /* expect exact match of nullingrels */ + NRM_SUBSET, /* actual Var may have a subset of input */ + NRM_SUPERSET /* actual Var may have a superset of input */ +} NullingRelsMatch; + typedef struct { int varno; /* RT index of Var */ AttrNumber varattno; /* attr number of Var */ AttrNumber resno; /* TLE position of Var */ +#ifdef USE_ASSERT_CHECKING + Bitmapset *varnullingrels; /* Var's varnullingrels */ +#endif } tlist_vinfo; typedef struct @@ -60,6 +70,7 @@ typedef struct indexed_tlist *inner_itlist; Index acceptable_rel; int rtoffset; + NullingRelsMatch nrm_match; double num_exec; } fix_join_expr_context; @@ -69,6 +80,7 @@ typedef struct indexed_tlist *subplan_itlist; int newvarno; int rtoffset; + NullingRelsMatch nrm_match; double num_exec; } fix_upper_expr_context; @@ -159,7 +171,12 @@ static indexed_tlist *build_tlist_index(List *tlist); static Var *search_indexed_tlist_for_var(Var *var, indexed_tlist *itlist, int newvarno, - int rtoffset); + int rtoffset, + NullingRelsMatch nrm_match); +static Var *search_indexed_tlist_for_phv(PlaceHolderVar *phv, + indexed_tlist *itlist, + int newvarno, + NullingRelsMatch nrm_match); static Var *search_indexed_tlist_for_non_var(Expr *node, indexed_tlist *itlist, int newvarno); @@ -172,14 +189,18 @@ static List *fix_join_expr(PlannerInfo *root, indexed_tlist *outer_itlist, indexed_tlist *inner_itlist, Index acceptable_rel, - int rtoffset, double num_exec); + int rtoffset, + NullingRelsMatch nrm_match, + double num_exec); static Node *fix_join_expr_mutator(Node *node, fix_join_expr_context *context); static Node *fix_upper_expr(PlannerInfo *root, Node *node, indexed_tlist *subplan_itlist, int newvarno, - int rtoffset, double num_exec); + int rtoffset, + NullingRelsMatch nrm_match, + double num_exec); static Node *fix_upper_expr_mutator(Node *node, fix_upper_expr_context *context); static List *set_returning_clause_references(PlannerInfo *root, @@ -1118,13 +1139,13 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset) fix_join_expr(root, splan->onConflictSet, NULL, itlist, linitial_int(splan->resultRelations), - rtoffset, NUM_EXEC_QUAL(plan)); + rtoffset, NRM_EQUAL, NUM_EXEC_QUAL(plan)); splan->onConflictWhere = (Node *) fix_join_expr(root, (List *) splan->onConflictWhere, NULL, itlist, linitial_int(splan->resultRelations), - rtoffset, NUM_EXEC_QUAL(plan)); + rtoffset, NRM_EQUAL, NUM_EXEC_QUAL(plan)); pfree(itlist); @@ -1181,6 +1202,7 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset) NULL, itlist, resultrel, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST(plan)); /* Fix quals too. */ @@ -1189,6 +1211,7 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset) NULL, itlist, resultrel, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL(plan)); } } @@ -1334,6 +1357,7 @@ set_indexonlyscan_references(PlannerInfo *root, index_itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST((Plan *) plan)); plan->scan.plan.qual = (List *) fix_upper_expr(root, @@ -1341,6 +1365,7 @@ set_indexonlyscan_references(PlannerInfo *root, index_itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) plan)); plan->recheckqual = (List *) fix_upper_expr(root, @@ -1348,6 +1373,7 @@ set_indexonlyscan_references(PlannerInfo *root, index_itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) plan)); /* indexqual is already transformed to reference index columns */ plan->indexqual = fix_scan_list(root, plan->indexqual, @@ -1554,6 +1580,7 @@ set_foreignscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST((Plan *) fscan)); fscan->scan.plan.qual = (List *) fix_upper_expr(root, @@ -1561,6 +1588,7 @@ set_foreignscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) fscan)); fscan->fdw_exprs = (List *) fix_upper_expr(root, @@ -1568,6 +1596,7 @@ set_foreignscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) fscan)); fscan->fdw_recheck_quals = (List *) fix_upper_expr(root, @@ -1575,6 +1604,7 @@ set_foreignscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) fscan)); pfree(itlist); /* fdw_scan_tlist itself just needs fix_scan_list() adjustments */ @@ -1603,6 +1633,7 @@ set_foreignscan_references(PlannerInfo *root, } fscan->fs_relids = offset_relid_set(fscan->fs_relids, rtoffset); + fscan->fs_base_relids = offset_relid_set(fscan->fs_base_relids, rtoffset); /* Adjust resultRelation if it's valid */ if (fscan->resultRelation > 0) @@ -1635,6 +1666,7 @@ set_customscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST((Plan *) cscan)); cscan->scan.plan.qual = (List *) fix_upper_expr(root, @@ -1642,6 +1674,7 @@ set_customscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) cscan)); cscan->custom_exprs = (List *) fix_upper_expr(root, @@ -1649,6 +1682,7 @@ set_customscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) cscan)); pfree(itlist); /* custom_scan_tlist itself just needs fix_scan_list() adjustments */ @@ -1835,6 +1869,7 @@ set_hash_references(PlannerInfo *root, Plan *plan, int rtoffset) outer_itlist, OUTER_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL(plan)); /* Hash doesn't project */ @@ -2170,6 +2205,7 @@ fix_scan_expr_mutator(Node *node, fix_scan_expr_context *context) /* At scan level, we should always just evaluate the contained expr */ PlaceHolderVar *phv = (PlaceHolderVar *) node; + Assert(phv->phnullingrels == NULL); return fix_scan_expr_mutator((Node *) phv->phexpr, context); } if (IsA(node, AlternativeSubPlan)) @@ -2227,6 +2263,7 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) inner_itlist, (Index) 0, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) join)); /* Now do join-type-specific stuff */ @@ -2239,11 +2276,21 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) { NestLoopParam *nlp = (NestLoopParam *) lfirst(lc); + /* + * Because we don't reparameterize parameterized paths to match + * the outer-join level at which they are used, Vars seen in the + * NestLoopParam expression may have nullingrels that are just a + * subset of those in the Vars actually available from the outer + * side. Not checking this exactly is a bit grotty, but the work + * needed to make things match up perfectly seems well out of + * proportion to the value. + */ nlp->paramval = (Var *) fix_upper_expr(root, (Node *) nlp->paramval, outer_itlist, OUTER_VAR, rtoffset, + NRM_SUBSET, NUM_EXEC_TLIST(outer_plan)); /* Check we replaced any PlaceHolderVar with simple Var */ if (!(IsA(nlp->paramval, Var) && @@ -2261,6 +2308,7 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) inner_itlist, (Index) 0, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) join)); } else if (IsA(join, HashJoin)) @@ -2273,6 +2321,7 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) inner_itlist, (Index) 0, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) join)); /* @@ -2284,45 +2333,27 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) outer_itlist, OUTER_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) join)); } /* * Now we need to fix up the targetlist and qpqual, which are logically - * above the join. This means they should not re-use any input expression - * that was computed in the nullable side of an outer join. Vars and - * PlaceHolderVars are fine, so we can implement this restriction just by - * clearing has_non_vars in the indexed_tlist structs. - * - * XXX This is a grotty workaround for the fact that we don't clearly - * distinguish between a Var appearing below an outer join and the "same" - * Var appearing above it. If we did, we'd not need to hack the matching - * rules this way. + * above the join. This means that, if it's not an inner join, any Vars + * and PHVs appearing here should have nullingrels that include the + * effects of the outer join, ie they will have nullingrels equal to the + * input Vars' nullingrels plus the bit added by the outer join. We don't + * currently have enough info available here to identify what that should + * be, so we just tell fix_join_expr to accept superset nullingrels + * matches instead of exact ones. */ - switch (join->jointype) - { - case JOIN_LEFT: - case JOIN_SEMI: - case JOIN_ANTI: - inner_itlist->has_non_vars = false; - break; - case JOIN_RIGHT: - outer_itlist->has_non_vars = false; - break; - case JOIN_FULL: - outer_itlist->has_non_vars = false; - inner_itlist->has_non_vars = false; - break; - default: - break; - } - join->plan.targetlist = fix_join_expr(root, join->plan.targetlist, outer_itlist, inner_itlist, (Index) 0, rtoffset, + (join->jointype == JOIN_INNER ? NRM_EQUAL : NRM_SUPERSET), NUM_EXEC_TLIST((Plan *) join)); join->plan.qual = fix_join_expr(root, join->plan.qual, @@ -2330,6 +2361,7 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) inner_itlist, (Index) 0, rtoffset, + (join->jointype == JOIN_INNER ? NRM_EQUAL : NRM_SUPERSET), NUM_EXEC_QUAL((Plan *) join)); pfree(outer_itlist); @@ -2384,6 +2416,7 @@ set_upper_references(PlannerInfo *root, Plan *plan, int rtoffset) subplan_itlist, OUTER_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST(plan)); } else @@ -2392,6 +2425,7 @@ set_upper_references(PlannerInfo *root, Plan *plan, int rtoffset) subplan_itlist, OUTER_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST(plan)); tle = flatCopyTargetEntry(tle); tle->expr = (Expr *) newexpr; @@ -2405,6 +2439,7 @@ set_upper_references(PlannerInfo *root, Plan *plan, int rtoffset) subplan_itlist, OUTER_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL(plan)); pfree(subplan_itlist); @@ -2605,7 +2640,7 @@ set_dummy_tlist_references(Plan *plan, int rtoffset) * tlist_member() searches. * * The result of this function is an indexed_tlist struct to pass to - * search_indexed_tlist_for_var() or search_indexed_tlist_for_non_var(). + * search_indexed_tlist_for_var() and siblings. * When done, the indexed_tlist may be freed with a single pfree(). */ static indexed_tlist * @@ -2637,6 +2672,9 @@ build_tlist_index(List *tlist) vinfo->varno = var->varno; vinfo->varattno = var->varattno; vinfo->resno = tle->resno; +#ifdef USE_ASSERT_CHECKING + vinfo->varnullingrels = var->varnullingrels; +#endif vinfo++; } else if (tle->expr && IsA(tle->expr, PlaceHolderVar)) @@ -2689,6 +2727,9 @@ build_tlist_index_other_vars(List *tlist, int ignore_rel) vinfo->varno = var->varno; vinfo->varattno = var->varattno; vinfo->resno = tle->resno; +#ifdef USE_ASSERT_CHECKING + vinfo->varnullingrels = var->varnullingrels; +#endif vinfo++; } } @@ -2708,10 +2749,17 @@ build_tlist_index_other_vars(List *tlist, int ignore_rel) * modified varno/varattno (to wit, newvarno and the resno of the TLE entry). * Also ensure that varnosyn is incremented by rtoffset. * If no match, return NULL. + * + * In debugging builds, we cross-check the varnullingrels of the subplan + * output Var based on nrm_match. Most call sites should pass NRM_EQUAL + * indicating we expect an exact match. However, there are places where + * we haven't cleaned things up completely, and we have to settle for + * allowing subset or superset matches. */ static Var * search_indexed_tlist_for_var(Var *var, indexed_tlist *itlist, - int newvarno, int rtoffset) + int newvarno, int rtoffset, + NullingRelsMatch nrm_match) { int varno = var->varno; AttrNumber varattno = var->varattno; @@ -2727,6 +2775,27 @@ search_indexed_tlist_for_var(Var *var, indexed_tlist *itlist, /* Found a match */ Var *newvar = copyVar(var); + /* + * Assert that we kept all the nullingrels machinations straight. + * + * XXX we skip the check for system columns and whole-row Vars. + * That's because such Vars might be row identity Vars, which are + * generated without any varnullingrels. It'd be hard to do + * otherwise, since they're normally made very early in planning, + * when we haven't looked at the jointree yet and don't know which + * joins might null such Vars. Doesn't seem worth the expense to + * make them fully valid. (While it's slightly annoying that we + * thereby lose checking for user-written references to such + * columns, it seems unlikely that a bug in nullingrels logic + * would affect only system columns.) + */ + Assert(varattno <= 0 || + (nrm_match == NRM_SUBSET ? + bms_is_subset(var->varnullingrels, vinfo->varnullingrels) : + nrm_match == NRM_SUPERSET ? + bms_is_subset(vinfo->varnullingrels, var->varnullingrels) : + bms_equal(vinfo->varnullingrels, var->varnullingrels))); + newvar->varno = newvarno; newvar->varattno = vinfo->resno; if (newvar->varnosyn > 0) @@ -2739,15 +2808,63 @@ search_indexed_tlist_for_var(Var *var, indexed_tlist *itlist, } /* - * search_indexed_tlist_for_non_var --- find a non-Var in an indexed tlist + * search_indexed_tlist_for_phv --- find a PlaceHolderVar in an indexed tlist * * If a match is found, return a Var constructed to reference the tlist item. * If no match, return NULL. * - * NOTE: it is a waste of time to call this unless itlist->has_ph_vars or - * itlist->has_non_vars. Furthermore, set_join_references() relies on being - * able to prevent matching of non-Vars by clearing itlist->has_non_vars, - * so there's a correctness reason not to call it unless that's set. + * Cross-check phnullingrels as in search_indexed_tlist_for_var. + * + * NOTE: it is a waste of time to call this unless itlist->has_ph_vars. + */ +static Var * +search_indexed_tlist_for_phv(PlaceHolderVar *phv, + indexed_tlist *itlist, int newvarno, + NullingRelsMatch nrm_match) +{ + ListCell *lc; + + foreach(lc, itlist->tlist) + { + TargetEntry *tle = (TargetEntry *) lfirst(lc); + + if (tle->expr && IsA(tle->expr, PlaceHolderVar)) + { + PlaceHolderVar *subphv = (PlaceHolderVar *) tle->expr; + Var *newvar; + + /* + * Analogously to search_indexed_tlist_for_var, we match on phid + * only. We don't use equal(), partially for speed but mostly + * because phnullingrels might not be exactly equal. + */ + if (phv->phid != subphv->phid) + continue; + + /* Assert that we kept all the nullingrels machinations straight */ + Assert(nrm_match == NRM_SUBSET ? + bms_is_subset(phv->phnullingrels, subphv->phnullingrels) : + nrm_match == NRM_SUPERSET ? + bms_is_subset(subphv->phnullingrels, phv->phnullingrels) : + bms_equal(subphv->phnullingrels, phv->phnullingrels)); + + /* Found a matching subplan output expression */ + newvar = makeVarFromTargetEntry(newvarno, tle); + newvar->varnosyn = 0; /* wasn't ever a plain Var */ + newvar->varattnosyn = 0; + return newvar; + } + } + return NULL; /* no match */ +} + +/* + * search_indexed_tlist_for_non_var --- find a non-Var/PHV in an indexed tlist + * + * If a match is found, return a Var constructed to reference the tlist item. + * If no match, return NULL. + * + * NOTE: it is a waste of time to call this unless itlist->has_non_vars. */ static Var * search_indexed_tlist_for_non_var(Expr *node, @@ -2854,6 +2971,7 @@ search_indexed_tlist_for_sortgroupref(Expr *node, * 'acceptable_rel' is either zero or the rangetable index of a relation * whose Vars may appear in the clause without provoking an error * 'rtoffset': how much to increment varnos by + * 'nrm_match': as for search_indexed_tlist_for_var() * 'num_exec': estimated number of executions of expression * * Returns the new expression tree. The original clause structure is @@ -2866,6 +2984,7 @@ fix_join_expr(PlannerInfo *root, indexed_tlist *inner_itlist, Index acceptable_rel, int rtoffset, + NullingRelsMatch nrm_match, double num_exec) { fix_join_expr_context context; @@ -2875,6 +2994,7 @@ fix_join_expr(PlannerInfo *root, context.inner_itlist = inner_itlist; context.acceptable_rel = acceptable_rel; context.rtoffset = rtoffset; + context.nrm_match = nrm_match; context.num_exec = num_exec; return (List *) fix_join_expr_mutator((Node *) clauses, &context); } @@ -2896,7 +3016,8 @@ fix_join_expr_mutator(Node *node, fix_join_expr_context *context) newvar = search_indexed_tlist_for_var(var, context->outer_itlist, OUTER_VAR, - context->rtoffset); + context->rtoffset, + context->nrm_match); if (newvar) return (Node *) newvar; } @@ -2907,7 +3028,8 @@ fix_join_expr_mutator(Node *node, fix_join_expr_context *context) newvar = search_indexed_tlist_for_var(var, context->inner_itlist, INNER_VAR, - context->rtoffset); + context->rtoffset, + context->nrm_match); if (newvar) return (Node *) newvar; } @@ -2932,22 +3054,25 @@ fix_join_expr_mutator(Node *node, fix_join_expr_context *context) /* See if the PlaceHolderVar has bubbled up from a lower plan node */ if (context->outer_itlist && context->outer_itlist->has_ph_vars) { - newvar = search_indexed_tlist_for_non_var((Expr *) phv, - context->outer_itlist, - OUTER_VAR); + newvar = search_indexed_tlist_for_phv(phv, + context->outer_itlist, + OUTER_VAR, + context->nrm_match); if (newvar) return (Node *) newvar; } if (context->inner_itlist && context->inner_itlist->has_ph_vars) { - newvar = search_indexed_tlist_for_non_var((Expr *) phv, - context->inner_itlist, - INNER_VAR); + newvar = search_indexed_tlist_for_phv(phv, + context->inner_itlist, + INNER_VAR, + context->nrm_match); if (newvar) return (Node *) newvar; } /* If not supplied by input plans, evaluate the contained expr */ + /* XXX can we assert something about phnullingrels? */ return fix_join_expr_mutator((Node *) phv->phexpr, context); } /* Try matching more complex expressions too, if tlists have any */ @@ -3006,6 +3131,7 @@ fix_join_expr_mutator(Node *node, fix_join_expr_context *context) * 'subplan_itlist': indexed target list for subplan (or index) * 'newvarno': varno to use for Vars referencing tlist elements * 'rtoffset': how much to increment varnos by + * 'nrm_match': as for search_indexed_tlist_for_var() * 'num_exec': estimated number of executions of expression * * The resulting tree is a copy of the original in which all Var nodes have @@ -3018,6 +3144,7 @@ fix_upper_expr(PlannerInfo *root, indexed_tlist *subplan_itlist, int newvarno, int rtoffset, + NullingRelsMatch nrm_match, double num_exec) { fix_upper_expr_context context; @@ -3026,6 +3153,7 @@ fix_upper_expr(PlannerInfo *root, context.subplan_itlist = subplan_itlist; context.newvarno = newvarno; context.rtoffset = rtoffset; + context.nrm_match = nrm_match; context.num_exec = num_exec; return fix_upper_expr_mutator(node, &context); } @@ -3044,7 +3172,8 @@ fix_upper_expr_mutator(Node *node, fix_upper_expr_context *context) newvar = search_indexed_tlist_for_var(var, context->subplan_itlist, context->newvarno, - context->rtoffset); + context->rtoffset, + context->nrm_match); if (!newvar) elog(ERROR, "variable not found in subplan target list"); return (Node *) newvar; @@ -3056,13 +3185,15 @@ fix_upper_expr_mutator(Node *node, fix_upper_expr_context *context) /* See if the PlaceHolderVar has bubbled up from a lower plan node */ if (context->subplan_itlist->has_ph_vars) { - newvar = search_indexed_tlist_for_non_var((Expr *) phv, - context->subplan_itlist, - context->newvarno); + newvar = search_indexed_tlist_for_phv(phv, + context->subplan_itlist, + context->newvarno, + context->nrm_match); if (newvar) return (Node *) newvar; } /* If not supplied by input plan, evaluate the contained expr */ + /* XXX can we assert something about phnullingrels? */ return fix_upper_expr_mutator((Node *) phv->phexpr, context); } /* Try matching more complex expressions too, if tlist has any */ @@ -3169,6 +3300,7 @@ set_returning_clause_references(PlannerInfo *root, NULL, resultRelation, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST(topplan)); pfree(itlist); |