1 /*-------------------------------------------------------------------------
4 * Planner preprocessing for subqueries and join tree manipulation.
6 * NOTE: the intended sequence for invoking these operations is
8 * inline_set_returning_functions
10 * flatten_simple_union_all
11 * do expression preprocessing (including flattening JOIN alias vars)
15 * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
16 * Portions Copyright (c) 1994, Regents of the University of California
20 * src/backend/optimizer/prep/prepjointree.c
22 *-------------------------------------------------------------------------
26 #include "catalog/pg_type.h"
27 #include "nodes/makefuncs.h"
28 #include "nodes/nodeFuncs.h"
29 #include "optimizer/clauses.h"
30 #include "optimizer/placeholder.h"
31 #include "optimizer/prep.h"
32 #include "optimizer/subselect.h"
33 #include "optimizer/tlist.h"
34 #include "parser/parse_relation.h"
35 #include "parser/parsetree.h"
36 #include "rewrite/rewriteManip.h"
39 typedef struct pullup_replace_vars_context
42 List *targetlist; /* tlist of subquery being pulled up */
43 RangeTblEntry *target_rte; /* RTE of subquery */
44 bool *outer_hasSubLinks; /* -> outer query's hasSubLinks */
45 int varno; /* varno of subquery */
46 bool need_phvs; /* do we need PlaceHolderVars? */
47 bool wrap_non_vars; /* do we need 'em on *all* non-Vars? */
48 Node **rv_cache; /* cache for results with PHVs */
49 } pullup_replace_vars_context;
51 typedef struct reduce_outer_joins_state
53 Relids relids; /* base relids within this subtree */
54 bool contains_outer; /* does subtree contain outer join(s)? */
55 List *sub_states; /* List of states for subtree components */
56 } reduce_outer_joins_state;
58 static Node *pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode,
60 static Node *pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
61 Relids available_rels, Node **jtlink);
62 static Node *pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,
64 JoinExpr *lowest_outer_join,
65 AppendRelInfo *containing_appendrel);
66 static Node *pull_up_simple_union_all(PlannerInfo *root, Node *jtnode,
68 static void pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root,
69 int parentRTindex, Query *setOpQuery,
71 static void make_setop_translation_list(Query *query, Index newvarno,
72 List **translated_vars);
73 static bool is_simple_subquery(Query *subquery);
74 static bool is_simple_union_all(Query *subquery);
75 static bool is_simple_union_all_recurse(Node *setOp, Query *setOpQuery,
77 static bool is_safe_append_member(Query *subquery);
78 static void replace_vars_in_jointree(Node *jtnode,
79 pullup_replace_vars_context *context,
80 JoinExpr *lowest_outer_join);
81 static Node *pullup_replace_vars(Node *expr,
82 pullup_replace_vars_context *context);
83 static Node *pullup_replace_vars_callback(Var *var,
84 replace_rte_variables_context *context);
85 static reduce_outer_joins_state *reduce_outer_joins_pass1(Node *jtnode);
86 static void reduce_outer_joins_pass2(Node *jtnode,
87 reduce_outer_joins_state *state,
89 Relids nonnullable_rels,
90 List *nonnullable_vars,
91 List *forced_null_vars);
92 static void substitute_multiple_relids(Node *node,
93 int varno, Relids subrelids);
94 static void fix_append_rel_relids(List *append_rel_list, int varno,
96 static Node *find_jointree_node_for_rel(Node *jtnode, int relid);
101 * Attempt to pull up ANY and EXISTS SubLinks to be treated as
102 * semijoins or anti-semijoins.
104 * A clause "foo op ANY (sub-SELECT)" can be processed by pulling the
105 * sub-SELECT up to become a rangetable entry and treating the implied
106 * comparisons as quals of a semijoin. However, this optimization *only*
107 * works at the top level of WHERE or a JOIN/ON clause, because we cannot
108 * distinguish whether the ANY ought to return FALSE or NULL in cases
109 * involving NULL inputs. Also, in an outer join's ON clause we can only
110 * do this if the sublink is degenerate (ie, references only the nullable
111 * side of the join). In that case it is legal to push the semijoin
112 * down into the nullable side of the join. If the sublink references any
113 * nonnullable-side variables then it would have to be evaluated as part
114 * of the outer join, which makes things way too complicated.
116 * Under similar conditions, EXISTS and NOT EXISTS clauses can be handled
117 * by pulling up the sub-SELECT and creating a semijoin or anti-semijoin.
119 * This routine searches for such clauses and does the necessary parsetree
120 * transformations if any are found.
122 * This routine has to run before preprocess_expression(), so the quals
123 * clauses are not yet reduced to implicit-AND format. That means we need
124 * to recursively search through explicit AND clauses, which are
125 * probably only binary ANDs. We stop as soon as we hit a non-AND item.
128 pull_up_sublinks(PlannerInfo *root)
133 /* Begin recursion through the jointree */
134 jtnode = pull_up_sublinks_jointree_recurse(root,
135 (Node *) root->parse->jointree,
139 * root->parse->jointree must always be a FromExpr, so insert a dummy one
140 * if we got a bare RangeTblRef or JoinExpr out of the recursion.
142 if (IsA(jtnode, FromExpr))
143 root->parse->jointree = (FromExpr *) jtnode;
145 root->parse->jointree = makeFromExpr(list_make1(jtnode), NULL);
149 * Recurse through jointree nodes for pull_up_sublinks()
151 * In addition to returning the possibly-modified jointree node, we return
152 * a relids set of the contained rels into *relids.
155 pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode,
162 else if (IsA(jtnode, RangeTblRef))
164 int varno = ((RangeTblRef *) jtnode)->rtindex;
166 *relids = bms_make_singleton(varno);
167 /* jtnode is returned unmodified */
169 else if (IsA(jtnode, FromExpr))
171 FromExpr *f = (FromExpr *) jtnode;
172 List *newfromlist = NIL;
173 Relids frelids = NULL;
178 /* First, recurse to process children and collect their relids */
179 foreach(l, f->fromlist)
184 newchild = pull_up_sublinks_jointree_recurse(root,
187 newfromlist = lappend(newfromlist, newchild);
188 frelids = bms_join(frelids, childrelids);
190 /* Build the replacement FromExpr; no quals yet */
191 newf = makeFromExpr(newfromlist, NULL);
192 /* Set up a link representing the rebuilt jointree */
193 jtlink = (Node *) newf;
194 /* Now process qual --- all children are available for use */
195 newf->quals = pull_up_sublinks_qual_recurse(root, f->quals, frelids,
199 * Note that the result will be either newf, or a stack of JoinExprs
200 * with newf at the base. We rely on subsequent optimization steps to
201 * flatten this and rearrange the joins as needed.
203 * Although we could include the pulled-up subqueries in the returned
204 * relids, there's no need since upper quals couldn't refer to their
210 else if (IsA(jtnode, JoinExpr))
218 * Make a modifiable copy of join node, but don't bother copying its
221 j = (JoinExpr *) palloc(sizeof(JoinExpr));
222 memcpy(j, jtnode, sizeof(JoinExpr));
225 /* Recurse to process children and collect their relids */
226 j->larg = pull_up_sublinks_jointree_recurse(root, j->larg,
228 j->rarg = pull_up_sublinks_jointree_recurse(root, j->rarg,
232 * Now process qual, showing appropriate child relids as available,
233 * and attach any pulled-up jointree items at the right place. In the
234 * inner-join case we put new JoinExprs above the existing one (much
235 * as for a FromExpr-style join). In outer-join cases the new
236 * JoinExprs must go into the nullable side of the outer join. The
237 * point of the available_rels machinations is to ensure that we only
238 * pull up quals for which that's okay.
240 * XXX for the moment, we refrain from pulling up IN/EXISTS clauses
241 * appearing in LEFT or RIGHT join conditions. Although it is
242 * semantically valid to do so under the above conditions, we end up
243 * with a query in which the semijoin or antijoin must be evaluated
244 * below the outer join, which could perform far worse than leaving it
245 * as a sublink that is executed only for row pairs that meet the
246 * other join conditions. Fixing this seems to require considerable
247 * restructuring of the executor, but maybe someday it can happen.
248 * (See also the comparable case in pull_up_sublinks_qual_recurse.)
250 * We don't expect to see any pre-existing JOIN_SEMI or JOIN_ANTI
256 j->quals = pull_up_sublinks_qual_recurse(root, j->quals,
257 bms_union(leftrelids,
262 #ifdef NOT_USED /* see XXX comment above */
263 j->quals = pull_up_sublinks_qual_recurse(root, j->quals,
269 /* can't do anything with full-join quals */
272 #ifdef NOT_USED /* see XXX comment above */
273 j->quals = pull_up_sublinks_qual_recurse(root, j->quals,
279 elog(ERROR, "unrecognized join type: %d",
285 * Although we could include the pulled-up subqueries in the returned
286 * relids, there's no need since upper quals couldn't refer to their
287 * outputs anyway. But we *do* need to include the join's own rtindex
288 * because we haven't yet collapsed join alias variables, so upper
289 * levels would mistakenly think they couldn't use references to this
292 *relids = bms_join(leftrelids, rightrelids);
294 *relids = bms_add_member(*relids, j->rtindex);
298 elog(ERROR, "unrecognized node type: %d",
299 (int) nodeTag(jtnode));
304 * Recurse through top-level qual nodes for pull_up_sublinks()
306 * jtlink points to the link in the jointree where any new JoinExprs should be
307 * inserted. If we find multiple pull-up-able SubLinks, they'll get stacked
308 * there in the order we encounter them. We rely on subsequent optimization
309 * to rearrange the stack if appropriate.
312 pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
313 Relids available_rels, Node **jtlink)
317 if (IsA(node, SubLink))
319 SubLink *sublink = (SubLink *) node;
323 /* Is it a convertible ANY or EXISTS clause? */
324 if (sublink->subLinkType == ANY_SUBLINK)
326 j = convert_ANY_sublink_to_join(root, sublink,
330 /* Yes; recursively process what we pulled up */
331 j->rarg = pull_up_sublinks_jointree_recurse(root,
334 /* Any inserted joins get stacked onto j->rarg */
335 j->quals = pull_up_sublinks_qual_recurse(root,
339 /* Now insert the new join node into the join tree */
341 *jtlink = (Node *) j;
342 /* and return NULL representing constant TRUE */
346 else if (sublink->subLinkType == EXISTS_SUBLINK)
348 j = convert_EXISTS_sublink_to_join(root, sublink, false,
352 /* Yes; recursively process what we pulled up */
353 j->rarg = pull_up_sublinks_jointree_recurse(root,
356 /* Any inserted joins get stacked onto j->rarg */
357 j->quals = pull_up_sublinks_qual_recurse(root,
361 /* Now insert the new join node into the join tree */
363 *jtlink = (Node *) j;
364 /* and return NULL representing constant TRUE */
368 /* Else return it unmodified */
371 if (not_clause(node))
373 /* If the immediate argument of NOT is EXISTS, try to convert */
374 SubLink *sublink = (SubLink *) get_notclausearg((Expr *) node);
377 if (sublink && IsA(sublink, SubLink))
379 if (sublink->subLinkType == EXISTS_SUBLINK)
381 j = convert_EXISTS_sublink_to_join(root, sublink, true,
386 * For the moment, refrain from recursing underneath NOT.
387 * As in pull_up_sublinks_jointree_recurse, recursing here
388 * would result in inserting a join underneath an ANTI
389 * join with which it could not commute, and that could
390 * easily lead to a worse plan than what we've
391 * historically generated.
394 /* Yes; recursively process what we pulled up */
397 j->rarg = pull_up_sublinks_jointree_recurse(root,
400 /* Any inserted joins get stacked onto j->rarg */
401 j->quals = pull_up_sublinks_qual_recurse(root,
406 /* Now insert the new join node into the join tree */
408 *jtlink = (Node *) j;
409 /* and return NULL representing constant TRUE */
414 /* Else return it unmodified */
417 if (and_clause(node))
419 /* Recurse into AND clause */
420 List *newclauses = NIL;
423 foreach(l, ((BoolExpr *) node)->args)
425 Node *oldclause = (Node *) lfirst(l);
428 newclause = pull_up_sublinks_qual_recurse(root,
433 newclauses = lappend(newclauses, newclause);
435 /* We might have got back fewer clauses than we started with */
436 if (newclauses == NIL)
438 else if (list_length(newclauses) == 1)
439 return (Node *) linitial(newclauses);
441 return (Node *) make_andclause(newclauses);
443 /* Stop if not an AND */
448 * inline_set_returning_functions
449 * Attempt to "inline" set-returning functions in the FROM clause.
451 * If an RTE_FUNCTION rtable entry invokes a set-returning function that
452 * contains just a simple SELECT, we can convert the rtable entry to an
453 * RTE_SUBQUERY entry exposing the SELECT directly. This is especially
454 * useful if the subquery can then be "pulled up" for further optimization,
455 * but we do it even if not, to reduce executor overhead.
457 * This has to be done before we have started to do any optimization of
458 * subqueries, else any such steps wouldn't get applied to subqueries
459 * obtained via inlining. However, we do it after pull_up_sublinks
460 * so that we can inline any functions used in SubLink subselects.
462 * Like most of the planner, this feels free to scribble on its input data
466 inline_set_returning_functions(PlannerInfo *root)
470 foreach(rt, root->parse->rtable)
472 RangeTblEntry *rte = (RangeTblEntry *) lfirst(rt);
474 if (rte->rtekind == RTE_FUNCTION)
478 /* Check safety of expansion, and expand if possible */
479 funcquery = inline_set_returning_function(root, rte);
482 /* Successful expansion, replace the rtable entry */
483 rte->rtekind = RTE_SUBQUERY;
484 rte->subquery = funcquery;
485 rte->funcexpr = NULL;
486 rte->funccoltypes = NIL;
487 rte->funccoltypmods = NIL;
488 rte->funccolcollations = NIL;
496 * Look for subqueries in the rangetable that can be pulled up into
497 * the parent query. If the subquery has no special features like
498 * grouping/aggregation then we can merge it into the parent's jointree.
499 * Also, subqueries that are simple UNION ALL structures can be
500 * converted into "append relations".
502 * If this jointree node is within the nullable side of an outer join, then
503 * lowest_outer_join references the lowest such JoinExpr node; otherwise it
504 * is NULL. This forces use of the PlaceHolderVar mechanism for references
505 * to non-nullable targetlist items, but only for references above that join.
507 * If we are looking at a member subquery of an append relation,
508 * containing_appendrel describes that relation; else it is NULL.
509 * This forces use of the PlaceHolderVar mechanism for all non-Var targetlist
510 * items, and puts some additional restrictions on what can be pulled up.
512 * A tricky aspect of this code is that if we pull up a subquery we have
513 * to replace Vars that reference the subquery's outputs throughout the
514 * parent query, including quals attached to jointree nodes above the one
515 * we are currently processing! We handle this by being careful not to
516 * change the jointree structure while recursing: no nodes other than
517 * subquery RangeTblRef entries will be replaced. Also, we can't turn
518 * pullup_replace_vars loose on the whole jointree, because it'll return a
519 * mutated copy of the tree; we have to invoke it just on the quals, instead.
520 * This behavior is what makes it reasonable to pass lowest_outer_join as a
521 * pointer rather than some more-indirect way of identifying the lowest OJ.
522 * Likewise, we don't replace append_rel_list members but only their
523 * substructure, so the containing_appendrel reference is safe to use.
526 pull_up_subqueries(PlannerInfo *root, Node *jtnode,
527 JoinExpr *lowest_outer_join,
528 AppendRelInfo *containing_appendrel)
532 if (IsA(jtnode, RangeTblRef))
534 int varno = ((RangeTblRef *) jtnode)->rtindex;
535 RangeTblEntry *rte = rt_fetch(varno, root->parse->rtable);
538 * Is this a subquery RTE, and if so, is the subquery simple enough to
541 * If we are looking at an append-relation member, we can't pull it up
542 * unless is_safe_append_member says so.
544 if (rte->rtekind == RTE_SUBQUERY &&
545 is_simple_subquery(rte->subquery) &&
546 (containing_appendrel == NULL ||
547 is_safe_append_member(rte->subquery)))
548 return pull_up_simple_subquery(root, jtnode, rte,
550 containing_appendrel);
553 * Alternatively, is it a simple UNION ALL subquery? If so, flatten
554 * into an "append relation".
556 * It's safe to do this regardless of whether this query is itself an
557 * appendrel member. (If you're thinking we should try to flatten the
558 * two levels of appendrel together, you're right; but we handle that
559 * in set_append_rel_pathlist, not here.)
561 if (rte->rtekind == RTE_SUBQUERY &&
562 is_simple_union_all(rte->subquery))
563 return pull_up_simple_union_all(root, jtnode, rte);
565 /* Otherwise, do nothing at this node. */
567 else if (IsA(jtnode, FromExpr))
569 FromExpr *f = (FromExpr *) jtnode;
572 Assert(containing_appendrel == NULL);
573 foreach(l, f->fromlist)
574 lfirst(l) = pull_up_subqueries(root, lfirst(l),
575 lowest_outer_join, NULL);
577 else if (IsA(jtnode, JoinExpr))
579 JoinExpr *j = (JoinExpr *) jtnode;
581 Assert(containing_appendrel == NULL);
582 /* Recurse, being careful to tell myself when inside outer join */
586 j->larg = pull_up_subqueries(root, j->larg,
587 lowest_outer_join, NULL);
588 j->rarg = pull_up_subqueries(root, j->rarg,
589 lowest_outer_join, NULL);
594 j->larg = pull_up_subqueries(root, j->larg,
595 lowest_outer_join, NULL);
596 j->rarg = pull_up_subqueries(root, j->rarg,
600 j->larg = pull_up_subqueries(root, j->larg,
602 j->rarg = pull_up_subqueries(root, j->rarg,
606 j->larg = pull_up_subqueries(root, j->larg,
608 j->rarg = pull_up_subqueries(root, j->rarg,
609 lowest_outer_join, NULL);
612 elog(ERROR, "unrecognized join type: %d",
618 elog(ERROR, "unrecognized node type: %d",
619 (int) nodeTag(jtnode));
624 * pull_up_simple_subquery
625 * Attempt to pull up a single simple subquery.
627 * jtnode is a RangeTblRef that has been tentatively identified as a simple
628 * subquery by pull_up_subqueries. We return the replacement jointree node,
629 * or jtnode itself if we determine that the subquery can't be pulled up after
632 * rte is the RangeTblEntry referenced by jtnode. Remaining parameters are
633 * as for pull_up_subqueries.
636 pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
637 JoinExpr *lowest_outer_join,
638 AppendRelInfo *containing_appendrel)
640 Query *parse = root->parse;
641 int varno = ((RangeTblRef *) jtnode)->rtindex;
643 PlannerInfo *subroot;
645 pullup_replace_vars_context rvcontext;
649 * Need a modifiable copy of the subquery to hack on. Even if we didn't
650 * sometimes choose not to pull up below, we must do this to avoid
651 * problems if the same subquery is referenced from multiple jointree
652 * items (which can't happen normally, but might after rule rewriting).
654 subquery = copyObject(rte->subquery);
657 * Create a PlannerInfo data structure for this subquery.
659 * NOTE: the next few steps should match the first processing in
660 * subquery_planner(). Can we refactor to avoid code duplication, or
661 * would that just make things uglier?
663 subroot = makeNode(PlannerInfo);
664 subroot->parse = subquery;
665 subroot->glob = root->glob;
666 subroot->query_level = root->query_level;
667 subroot->parent_root = root->parent_root;
668 subroot->planner_cxt = CurrentMemoryContext;
669 subroot->init_plans = NIL;
670 subroot->cte_plan_ids = NIL;
671 subroot->eq_classes = NIL;
672 subroot->append_rel_list = NIL;
673 subroot->rowMarks = NIL;
674 subroot->hasRecursion = false;
675 subroot->wt_param_id = -1;
676 subroot->non_recursive_plan = NULL;
678 /* No CTEs to worry about */
679 Assert(subquery->cteList == NIL);
682 * Pull up any SubLinks within the subquery's quals, so that we don't
683 * leave unoptimized SubLinks behind.
685 if (subquery->hasSubLinks)
686 pull_up_sublinks(subroot);
689 * Similarly, inline any set-returning functions in its rangetable.
691 inline_set_returning_functions(subroot);
694 * Recursively pull up the subquery's subqueries, so that
695 * pull_up_subqueries' processing is complete for its jointree and
698 * Note: we should pass NULL for containing-join info even if we are
699 * within an outer join in the upper query; the lower query starts with a
700 * clean slate for outer-join semantics. Likewise, we say we aren't
701 * handling an appendrel member.
703 subquery->jointree = (FromExpr *)
704 pull_up_subqueries(subroot, (Node *) subquery->jointree, NULL, NULL);
707 * Now we must recheck whether the subquery is still simple enough to pull
708 * up. If not, abandon processing it.
710 * We don't really need to recheck all the conditions involved, but it's
711 * easier just to keep this "if" looking the same as the one in
712 * pull_up_subqueries.
714 if (is_simple_subquery(subquery) &&
715 (containing_appendrel == NULL || is_safe_append_member(subquery)))
722 * Give up, return unmodified RangeTblRef.
724 * Note: The work we just did will be redone when the subquery gets
725 * planned on its own. Perhaps we could avoid that by storing the
726 * modified subquery back into the rangetable, but I'm not gonna risk
733 * Adjust level-0 varnos in subquery so that we can append its rangetable
734 * to upper query's. We have to fix the subquery's append_rel_list as
737 rtoffset = list_length(parse->rtable);
738 OffsetVarNodes((Node *) subquery, rtoffset, 0);
739 OffsetVarNodes((Node *) subroot->append_rel_list, rtoffset, 0);
742 * Upper-level vars in subquery are now one level closer to their parent
745 IncrementVarSublevelsUp((Node *) subquery, -1, 1);
746 IncrementVarSublevelsUp((Node *) subroot->append_rel_list, -1, 1);
749 * The subquery's targetlist items are now in the appropriate form to
750 * insert into the top query, but if we are under an outer join then
751 * non-nullable items may have to be turned into PlaceHolderVars. If we
752 * are dealing with an appendrel member then anything that's not a simple
753 * Var has to be turned into a PlaceHolderVar. Set up appropriate context
754 * data for pullup_replace_vars.
756 rvcontext.root = root;
757 rvcontext.targetlist = subquery->targetList;
758 rvcontext.target_rte = rte;
759 rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
760 rvcontext.varno = varno;
761 rvcontext.need_phvs = (lowest_outer_join != NULL ||
762 containing_appendrel != NULL);
763 rvcontext.wrap_non_vars = (containing_appendrel != NULL);
764 /* initialize cache array with indexes 0 .. length(tlist) */
765 rvcontext.rv_cache = palloc0((list_length(subquery->targetList) + 1) *
769 * Replace all of the top query's references to the subquery's outputs
770 * with copies of the adjusted subtlist items, being careful not to
771 * replace any of the jointree structure. (This'd be a lot cleaner if we
772 * could use query_tree_mutator.) We have to use PHVs in the targetList,
773 * returningList, and havingQual, since those are certainly above any
774 * outer join. replace_vars_in_jointree tracks its location in the
775 * jointree and uses PHVs or not appropriately.
777 parse->targetList = (List *)
778 pullup_replace_vars((Node *) parse->targetList, &rvcontext);
779 parse->returningList = (List *)
780 pullup_replace_vars((Node *) parse->returningList, &rvcontext);
781 replace_vars_in_jointree((Node *) parse->jointree, &rvcontext,
783 Assert(parse->setOperations == NULL);
784 parse->havingQual = pullup_replace_vars(parse->havingQual, &rvcontext);
787 * Replace references in the translated_vars lists of appendrels. When
788 * pulling up an appendrel member, we do not need PHVs in the list of the
789 * parent appendrel --- there isn't any outer join between. Elsewhere, use
790 * PHVs for safety. (This analysis could be made tighter but it seems
791 * unlikely to be worth much trouble.)
793 foreach(lc, root->append_rel_list)
795 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
796 bool save_need_phvs = rvcontext.need_phvs;
798 if (appinfo == containing_appendrel)
799 rvcontext.need_phvs = false;
800 appinfo->translated_vars = (List *)
801 pullup_replace_vars((Node *) appinfo->translated_vars, &rvcontext);
802 rvcontext.need_phvs = save_need_phvs;
806 * Replace references in the joinaliasvars lists of join RTEs.
808 * You might think that we could avoid using PHVs for alias vars of joins
809 * below lowest_outer_join, but that doesn't work because the alias vars
810 * could be referenced above that join; we need the PHVs to be present in
811 * such references after the alias vars get flattened. (It might be worth
812 * trying to be smarter here, someday.)
814 foreach(lc, parse->rtable)
816 RangeTblEntry *otherrte = (RangeTblEntry *) lfirst(lc);
818 if (otherrte->rtekind == RTE_JOIN)
819 otherrte->joinaliasvars = (List *)
820 pullup_replace_vars((Node *) otherrte->joinaliasvars,
825 * Now append the adjusted rtable entries to upper query. (We hold off
826 * until after fixing the upper rtable entries; no point in running that
827 * code on the subquery ones too.)
829 parse->rtable = list_concat(parse->rtable, subquery->rtable);
832 * Pull up any FOR UPDATE/SHARE markers, too. (OffsetVarNodes already
833 * adjusted the marker rtindexes, so just concat the lists.)
835 parse->rowMarks = list_concat(parse->rowMarks, subquery->rowMarks);
838 * We also have to fix the relid sets of any PlaceHolderVar nodes in the
839 * parent query. (This could perhaps be done by pullup_replace_vars(),
840 * but it seems cleaner to use two passes.) Note in particular that any
841 * PlaceHolderVar nodes just created by pullup_replace_vars() will be
842 * adjusted, so having created them with the subquery's varno is correct.
844 * Likewise, relids appearing in AppendRelInfo nodes have to be fixed. We
845 * already checked that this won't require introducing multiple subrelids
846 * into the single-slot AppendRelInfo structs.
848 if (parse->hasSubLinks || root->glob->lastPHId != 0 ||
849 root->append_rel_list)
853 subrelids = get_relids_in_jointree((Node *) subquery->jointree, false);
854 substitute_multiple_relids((Node *) parse, varno, subrelids);
855 fix_append_rel_relids(root->append_rel_list, varno, subrelids);
859 * And now add subquery's AppendRelInfos to our list.
861 root->append_rel_list = list_concat(root->append_rel_list,
862 subroot->append_rel_list);
865 * We don't have to do the equivalent bookkeeping for outer-join info,
866 * because that hasn't been set up yet. placeholder_list likewise.
868 Assert(root->join_info_list == NIL);
869 Assert(subroot->join_info_list == NIL);
870 Assert(root->placeholder_list == NIL);
871 Assert(subroot->placeholder_list == NIL);
874 * Miscellaneous housekeeping.
876 * Although replace_rte_variables() faithfully updated parse->hasSubLinks
877 * if it copied any SubLinks out of the subquery's targetlist, we still
878 * could have SubLinks added to the query in the expressions of FUNCTION
879 * and VALUES RTEs copied up from the subquery. So it's necessary to copy
880 * subquery->hasSubLinks anyway. Perhaps this can be improved someday.
882 parse->hasSubLinks |= subquery->hasSubLinks;
885 * subquery won't be pulled up if it hasAggs or hasWindowFuncs, so no work
886 * needed on those flags
890 * Return the adjusted subquery jointree to replace the RangeTblRef entry
891 * in parent's jointree.
893 return (Node *) subquery->jointree;
897 * pull_up_simple_union_all
898 * Pull up a single simple UNION ALL subquery.
900 * jtnode is a RangeTblRef that has been identified as a simple UNION ALL
901 * subquery by pull_up_subqueries. We pull up the leaf subqueries and
902 * build an "append relation" for the union set. The result value is just
903 * jtnode, since we don't actually need to change the query jointree.
906 pull_up_simple_union_all(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte)
908 int varno = ((RangeTblRef *) jtnode)->rtindex;
909 Query *subquery = rte->subquery;
914 * Append child RTEs to parent rtable.
916 * Upper-level vars in subquery are now one level closer to their parent
917 * than before. We don't have to worry about offsetting varnos, though,
918 * because any such vars must refer to stuff above the level of the query
919 * we are pulling into.
921 rtoffset = list_length(root->parse->rtable);
922 rtable = copyObject(subquery->rtable);
923 IncrementVarSublevelsUp_rtable(rtable, -1, 1);
924 root->parse->rtable = list_concat(root->parse->rtable, rtable);
927 * Recursively scan the subquery's setOperations tree and add
928 * AppendRelInfo nodes for leaf subqueries to the parent's
929 * append_rel_list. Also apply pull_up_subqueries to the leaf subqueries.
931 Assert(subquery->setOperations);
932 pull_up_union_leaf_queries(subquery->setOperations, root, varno, subquery,
936 * Mark the parent as an append relation.
944 * pull_up_union_leaf_queries -- recursive guts of pull_up_simple_union_all
946 * Build an AppendRelInfo for each leaf query in the setop tree, and then
947 * apply pull_up_subqueries to the leaf query.
949 * Note that setOpQuery is the Query containing the setOp node, whose tlist
950 * contains references to all the setop output columns. When called from
951 * pull_up_simple_union_all, this is *not* the same as root->parse, which is
952 * the parent Query we are pulling up into.
954 * parentRTindex is the appendrel parent's index in root->parse->rtable.
956 * The child RTEs have already been copied to the parent. childRToffset
957 * tells us where in the parent's range table they were copied. When called
958 * from flatten_simple_union_all, childRToffset is 0 since the child RTEs
959 * were already in root->parse->rtable and no RT index adjustment is needed.
962 pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root, int parentRTindex,
963 Query *setOpQuery, int childRToffset)
965 if (IsA(setOp, RangeTblRef))
967 RangeTblRef *rtr = (RangeTblRef *) setOp;
969 AppendRelInfo *appinfo;
972 * Calculate the index in the parent's range table
974 childRTindex = childRToffset + rtr->rtindex;
977 * Build a suitable AppendRelInfo, and attach to parent's list.
979 appinfo = makeNode(AppendRelInfo);
980 appinfo->parent_relid = parentRTindex;
981 appinfo->child_relid = childRTindex;
982 appinfo->parent_reltype = InvalidOid;
983 appinfo->child_reltype = InvalidOid;
984 make_setop_translation_list(setOpQuery, childRTindex,
985 &appinfo->translated_vars);
986 appinfo->parent_reloid = InvalidOid;
987 root->append_rel_list = lappend(root->append_rel_list, appinfo);
990 * Recursively apply pull_up_subqueries to the new child RTE. (We
991 * must build the AppendRelInfo first, because this will modify it.)
992 * Note that we can pass NULL for containing-join info even if we're
993 * actually under an outer join, because the child's expressions
994 * aren't going to propagate up above the join.
996 rtr = makeNode(RangeTblRef);
997 rtr->rtindex = childRTindex;
998 (void) pull_up_subqueries(root, (Node *) rtr, NULL, appinfo);
1000 else if (IsA(setOp, SetOperationStmt))
1002 SetOperationStmt *op = (SetOperationStmt *) setOp;
1004 /* Recurse to reach leaf queries */
1005 pull_up_union_leaf_queries(op->larg, root, parentRTindex, setOpQuery,
1007 pull_up_union_leaf_queries(op->rarg, root, parentRTindex, setOpQuery,
1012 elog(ERROR, "unrecognized node type: %d",
1013 (int) nodeTag(setOp));
1018 * make_setop_translation_list
1019 * Build the list of translations from parent Vars to child Vars for
1020 * a UNION ALL member. (At this point it's just a simple list of
1021 * referencing Vars, but if we succeed in pulling up the member
1022 * subquery, the Vars will get replaced by pulled-up expressions.)
1025 make_setop_translation_list(Query *query, Index newvarno,
1026 List **translated_vars)
1031 foreach(l, query->targetList)
1033 TargetEntry *tle = (TargetEntry *) lfirst(l);
1038 vars = lappend(vars, makeVarFromTargetEntry(newvarno, tle));
1041 *translated_vars = vars;
1045 * is_simple_subquery
1046 * Check a subquery in the range table to see if it's simple enough
1047 * to pull up into the parent query.
1050 is_simple_subquery(Query *subquery)
1053 * Let's just make sure it's a valid subselect ...
1055 if (!IsA(subquery, Query) ||
1056 subquery->commandType != CMD_SELECT ||
1057 subquery->utilityStmt != NULL ||
1058 subquery->intoClause != NULL)
1059 elog(ERROR, "subquery is bogus");
1062 * Can't currently pull up a query with setops (unless it's simple UNION
1063 * ALL, which is handled by a different code path). Maybe after querytree
1066 if (subquery->setOperations)
1070 * Can't pull up a subquery involving grouping, aggregation, sorting,
1071 * limiting, or WITH. (XXX WITH could possibly be allowed later)
1073 * We also don't pull up a subquery that has explicit FOR UPDATE/SHARE
1074 * clauses, because pullup would cause the locking to occur semantically
1075 * higher than it should. Implicit FOR UPDATE/SHARE is okay because in
1076 * that case the locking was originally declared in the upper query
1079 if (subquery->hasAggs ||
1080 subquery->hasWindowFuncs ||
1081 subquery->groupClause ||
1082 subquery->havingQual ||
1083 subquery->sortClause ||
1084 subquery->distinctClause ||
1085 subquery->limitOffset ||
1086 subquery->limitCount ||
1087 subquery->hasForUpdate ||
1092 * Don't pull up a subquery that has any set-returning functions in its
1093 * targetlist. Otherwise we might well wind up inserting set-returning
1094 * functions into places where they mustn't go, such as quals of higher
1097 if (expression_returns_set((Node *) subquery->targetList))
1101 * Don't pull up a subquery that has any volatile functions in its
1102 * targetlist. Otherwise we might introduce multiple evaluations of these
1103 * functions, if they get copied to multiple places in the upper query,
1104 * leading to surprising results. (Note: the PlaceHolderVar mechanism
1105 * doesn't quite guarantee single evaluation; else we could pull up anyway
1106 * and just wrap such items in PlaceHolderVars ...)
1108 if (contain_volatile_functions((Node *) subquery->targetList))
1112 * Hack: don't try to pull up a subquery with an empty jointree.
1113 * query_planner() will correctly generate a Result plan for a jointree
1114 * that's totally empty, but I don't think the right things happen if an
1115 * empty FromExpr appears lower down in a jointree. It would pose a
1116 * problem for the PlaceHolderVar mechanism too, since we'd have no way to
1117 * identify where to evaluate a PHV coming out of the subquery. Not worth
1118 * working hard on this, just to collapse SubqueryScan/Result into Result;
1119 * especially since the SubqueryScan can often be optimized away by
1122 if (subquery->jointree->fromlist == NIL)
1129 * is_simple_union_all
1130 * Check a subquery to see if it's a simple UNION ALL.
1132 * We require all the setops to be UNION ALL (no mixing) and there can't be
1133 * any datatype coercions involved, ie, all the leaf queries must emit the
1137 is_simple_union_all(Query *subquery)
1139 SetOperationStmt *topop;
1141 /* Let's just make sure it's a valid subselect ... */
1142 if (!IsA(subquery, Query) ||
1143 subquery->commandType != CMD_SELECT ||
1144 subquery->utilityStmt != NULL ||
1145 subquery->intoClause != NULL)
1146 elog(ERROR, "subquery is bogus");
1148 /* Is it a set-operation query at all? */
1149 topop = (SetOperationStmt *) subquery->setOperations;
1152 Assert(IsA(topop, SetOperationStmt));
1154 /* Can't handle ORDER BY, LIMIT/OFFSET, locking, or WITH */
1155 if (subquery->sortClause ||
1156 subquery->limitOffset ||
1157 subquery->limitCount ||
1158 subquery->rowMarks ||
1162 /* Recursively check the tree of set operations */
1163 return is_simple_union_all_recurse((Node *) topop, subquery,
1168 is_simple_union_all_recurse(Node *setOp, Query *setOpQuery, List *colTypes)
1170 if (IsA(setOp, RangeTblRef))
1172 RangeTblRef *rtr = (RangeTblRef *) setOp;
1173 RangeTblEntry *rte = rt_fetch(rtr->rtindex, setOpQuery->rtable);
1174 Query *subquery = rte->subquery;
1176 Assert(subquery != NULL);
1178 /* Leaf nodes are OK if they match the toplevel column types */
1179 /* We don't have to compare typmods or collations here */
1180 return tlist_same_datatypes(subquery->targetList, colTypes, true);
1182 else if (IsA(setOp, SetOperationStmt))
1184 SetOperationStmt *op = (SetOperationStmt *) setOp;
1186 /* Must be UNION ALL */
1187 if (op->op != SETOP_UNION || !op->all)
1190 /* Recurse to check inputs */
1191 return is_simple_union_all_recurse(op->larg, setOpQuery, colTypes) &&
1192 is_simple_union_all_recurse(op->rarg, setOpQuery, colTypes);
1196 elog(ERROR, "unrecognized node type: %d",
1197 (int) nodeTag(setOp));
1198 return false; /* keep compiler quiet */
1203 * is_safe_append_member
1204 * Check a subquery that is a leaf of a UNION ALL appendrel to see if it's
1208 is_safe_append_member(Query *subquery)
1213 * It's only safe to pull up the child if its jointree contains exactly
1214 * one RTE, else the AppendRelInfo data structure breaks. The one base RTE
1215 * could be buried in several levels of FromExpr, however.
1217 * Also, the child can't have any WHERE quals because there's no place to
1218 * put them in an appendrel. (This is a bit annoying...) If we didn't
1219 * need to check this, we'd just test whether get_relids_in_jointree()
1220 * yields a singleton set, to be more consistent with the coding of
1221 * fix_append_rel_relids().
1223 jtnode = subquery->jointree;
1224 while (IsA(jtnode, FromExpr))
1226 if (jtnode->quals != NULL)
1228 if (list_length(jtnode->fromlist) != 1)
1230 jtnode = linitial(jtnode->fromlist);
1232 if (!IsA(jtnode, RangeTblRef))
1239 * Helper routine for pull_up_subqueries: do pullup_replace_vars on every
1240 * expression in the jointree, without changing the jointree structure itself.
1241 * Ugly, but there's no other way...
1243 * If we are at or below lowest_outer_join, we can suppress use of
1244 * PlaceHolderVars wrapped around the replacement expressions.
1247 replace_vars_in_jointree(Node *jtnode,
1248 pullup_replace_vars_context *context,
1249 JoinExpr *lowest_outer_join)
1253 if (IsA(jtnode, RangeTblRef))
1255 /* nothing to do here */
1257 else if (IsA(jtnode, FromExpr))
1259 FromExpr *f = (FromExpr *) jtnode;
1262 foreach(l, f->fromlist)
1263 replace_vars_in_jointree(lfirst(l), context, lowest_outer_join);
1264 f->quals = pullup_replace_vars(f->quals, context);
1266 else if (IsA(jtnode, JoinExpr))
1268 JoinExpr *j = (JoinExpr *) jtnode;
1269 bool save_need_phvs = context->need_phvs;
1271 if (j == lowest_outer_join)
1273 /* no more PHVs in or below this join */
1274 context->need_phvs = false;
1275 lowest_outer_join = NULL;
1277 replace_vars_in_jointree(j->larg, context, lowest_outer_join);
1278 replace_vars_in_jointree(j->rarg, context, lowest_outer_join);
1279 j->quals = pullup_replace_vars(j->quals, context);
1282 * We don't bother to update the colvars list, since it won't be used
1285 context->need_phvs = save_need_phvs;
1288 elog(ERROR, "unrecognized node type: %d",
1289 (int) nodeTag(jtnode));
1293 * Apply pullup variable replacement throughout an expression tree
1295 * Returns a modified copy of the tree, so this can't be used where we
1296 * need to do in-place replacement.
1299 pullup_replace_vars(Node *expr, pullup_replace_vars_context *context)
1301 return replace_rte_variables(expr,
1303 pullup_replace_vars_callback,
1305 context->outer_hasSubLinks);
1309 pullup_replace_vars_callback(Var *var,
1310 replace_rte_variables_context *context)
1312 pullup_replace_vars_context *rcon = (pullup_replace_vars_context *) context->callback_arg;
1313 int varattno = var->varattno;
1317 * If PlaceHolderVars are needed, we cache the modified expressions in
1318 * rcon->rv_cache[]. This is not in hopes of any material speed gain
1319 * within this function, but to avoid generating identical PHVs with
1320 * different IDs. That would result in duplicate evaluations at runtime,
1321 * and possibly prevent optimizations that rely on recognizing different
1322 * references to the same subquery output as being equal(). So it's worth
1323 * a bit of extra effort to avoid it.
1325 if (rcon->need_phvs &&
1326 varattno >= InvalidAttrNumber &&
1327 varattno <= list_length(rcon->targetlist) &&
1328 rcon->rv_cache[varattno] != NULL)
1330 /* Just copy the entry and fall through to adjust its varlevelsup */
1331 newnode = copyObject(rcon->rv_cache[varattno]);
1333 else if (varattno == InvalidAttrNumber)
1335 /* Must expand whole-tuple reference into RowExpr */
1339 bool save_need_phvs = rcon->need_phvs;
1340 int save_sublevelsup = context->sublevels_up;
1343 * If generating an expansion for a var of a named rowtype (ie, this
1344 * is a plain relation RTE), then we must include dummy items for
1345 * dropped columns. If the var is RECORD (ie, this is a JOIN), then
1346 * omit dropped columns. Either way, attach column names to the
1347 * RowExpr for use of ruleutils.c.
1349 * In order to be able to cache the results, we always generate the
1350 * expansion with varlevelsup = 0, and then adjust if needed.
1352 expandRTE(rcon->target_rte,
1353 var->varno, 0 /* not varlevelsup */ , var->location,
1354 (var->vartype != RECORDOID),
1355 &colnames, &fields);
1356 /* Adjust the generated per-field Vars, but don't insert PHVs */
1357 rcon->need_phvs = false;
1358 context->sublevels_up = 0; /* to match the expandRTE output */
1359 fields = (List *) replace_rte_variables_mutator((Node *) fields,
1361 rcon->need_phvs = save_need_phvs;
1362 context->sublevels_up = save_sublevelsup;
1364 rowexpr = makeNode(RowExpr);
1365 rowexpr->args = fields;
1366 rowexpr->row_typeid = var->vartype;
1367 rowexpr->row_format = COERCE_IMPLICIT_CAST;
1368 rowexpr->colnames = colnames;
1369 rowexpr->location = var->location;
1370 newnode = (Node *) rowexpr;
1373 * Insert PlaceHolderVar if needed. Notice that we are wrapping one
1374 * PlaceHolderVar around the whole RowExpr, rather than putting one
1375 * around each element of the row. This is because we need the
1376 * expression to yield NULL, not ROW(NULL,NULL,...) when it is forced
1377 * to null by an outer join.
1379 if (rcon->need_phvs)
1381 /* RowExpr is certainly not strict, so always need PHV */
1383 make_placeholder_expr(rcon->root,
1385 bms_make_singleton(rcon->varno));
1386 /* cache it with the PHV, and with varlevelsup still zero */
1387 rcon->rv_cache[InvalidAttrNumber] = copyObject(newnode);
1392 /* Normal case referencing one targetlist element */
1393 TargetEntry *tle = get_tle_by_resno(rcon->targetlist, varattno);
1395 if (tle == NULL) /* shouldn't happen */
1396 elog(ERROR, "could not find attribute %d in subquery targetlist",
1399 /* Make a copy of the tlist item to return */
1400 newnode = copyObject(tle->expr);
1402 /* Insert PlaceHolderVar if needed */
1403 if (rcon->need_phvs)
1407 if (newnode && IsA(newnode, Var) &&
1408 ((Var *) newnode)->varlevelsup == 0)
1410 /* Simple Vars always escape being wrapped */
1413 else if (newnode && IsA(newnode, PlaceHolderVar) &&
1414 ((PlaceHolderVar *) newnode)->phlevelsup == 0)
1416 /* No need to wrap a PlaceHolderVar with another one, either */
1419 else if (rcon->wrap_non_vars)
1421 /* Wrap all non-Vars in a PlaceHolderVar */
1427 * If it contains a Var of current level, and does not contain
1428 * any non-strict constructs, then it's certainly nullable so
1429 * we don't need to insert a PlaceHolderVar.
1431 * This analysis could be tighter: in particular, a non-strict
1432 * construct hidden within a lower-level PlaceHolderVar is not
1433 * reason to add another PHV. But for now it doesn't seem
1434 * worth the code to be more exact.
1436 * Note: in future maybe we should insert a PlaceHolderVar
1437 * anyway, if the tlist item is expensive to evaluate?
1439 if (contain_vars_of_level((Node *) newnode, 0) &&
1440 !contain_nonstrict_functions((Node *) newnode))
1442 /* No wrap needed */
1447 /* Else wrap it in a PlaceHolderVar */
1454 make_placeholder_expr(rcon->root,
1456 bms_make_singleton(rcon->varno));
1459 * Cache it if possible (ie, if the attno is in range, which it
1460 * probably always should be). We can cache the value even if we
1461 * decided we didn't need a PHV, since this result will be
1462 * suitable for any request that has need_phvs.
1464 if (varattno > InvalidAttrNumber &&
1465 varattno <= list_length(rcon->targetlist))
1466 rcon->rv_cache[varattno] = copyObject(newnode);
1470 /* Must adjust varlevelsup if tlist item is from higher query */
1471 if (var->varlevelsup > 0)
1472 IncrementVarSublevelsUp(newnode, var->varlevelsup, 0);
1479 * flatten_simple_union_all
1480 * Try to optimize top-level UNION ALL structure into an appendrel
1482 * If a query's setOperations tree consists entirely of simple UNION ALL
1483 * operations, flatten it into an append relation, which we can process more
1484 * intelligently than the general setops case. Otherwise, do nothing.
1486 * In most cases, this can succeed only for a top-level query, because for a
1487 * subquery in FROM, the parent query's invocation of pull_up_subqueries would
1488 * already have flattened the UNION via pull_up_simple_union_all. But there
1489 * are a few cases we can support here but not in that code path, for example
1490 * when the subquery also contains ORDER BY.
1493 flatten_simple_union_all(PlannerInfo *root)
1495 Query *parse = root->parse;
1496 SetOperationStmt *topop;
1497 Node *leftmostjtnode;
1499 RangeTblEntry *leftmostRTE;
1501 RangeTblEntry *childRTE;
1504 /* Shouldn't be called unless query has setops */
1505 topop = (SetOperationStmt *) parse->setOperations;
1506 Assert(topop && IsA(topop, SetOperationStmt));
1508 /* Can't optimize away a recursive UNION */
1509 if (root->hasRecursion)
1513 * Recursively check the tree of set operations. If not all UNION ALL
1514 * with identical column types, punt.
1516 if (!is_simple_union_all_recurse((Node *) topop, parse, topop->colTypes))
1520 * Locate the leftmost leaf query in the setops tree. The upper query's
1521 * Vars all refer to this RTE (see transformSetOperationStmt).
1523 leftmostjtnode = topop->larg;
1524 while (leftmostjtnode && IsA(leftmostjtnode, SetOperationStmt))
1525 leftmostjtnode = ((SetOperationStmt *) leftmostjtnode)->larg;
1526 Assert(leftmostjtnode && IsA(leftmostjtnode, RangeTblRef));
1527 leftmostRTI = ((RangeTblRef *) leftmostjtnode)->rtindex;
1528 leftmostRTE = rt_fetch(leftmostRTI, parse->rtable);
1529 Assert(leftmostRTE->rtekind == RTE_SUBQUERY);
1532 * Make a copy of the leftmost RTE and add it to the rtable. This copy
1533 * will represent the leftmost leaf query in its capacity as a member of
1534 * the appendrel. The original will represent the appendrel as a whole.
1535 * (We must do things this way because the upper query's Vars have to be
1536 * seen as referring to the whole appendrel.)
1538 childRTE = copyObject(leftmostRTE);
1539 parse->rtable = lappend(parse->rtable, childRTE);
1540 childRTI = list_length(parse->rtable);
1542 /* Modify the setops tree to reference the child copy */
1543 ((RangeTblRef *) leftmostjtnode)->rtindex = childRTI;
1545 /* Modify the formerly-leftmost RTE to mark it as an appendrel parent */
1546 leftmostRTE->inh = true;
1549 * Form a RangeTblRef for the appendrel, and insert it into FROM. The top
1550 * Query of a setops tree should have had an empty FromClause initially.
1552 rtr = makeNode(RangeTblRef);
1553 rtr->rtindex = leftmostRTI;
1554 Assert(parse->jointree->fromlist == NIL);
1555 parse->jointree->fromlist = list_make1(rtr);
1558 * Now pretend the query has no setops. We must do this before trying to
1559 * do subquery pullup, because of Assert in pull_up_simple_subquery.
1561 parse->setOperations = NULL;
1564 * Build AppendRelInfo information, and apply pull_up_subqueries to the
1565 * leaf queries of the UNION ALL. (We must do that now because they
1566 * weren't previously referenced by the jointree, and so were missed by
1567 * the main invocation of pull_up_subqueries.)
1569 pull_up_union_leaf_queries((Node *) topop, root, leftmostRTI, parse, 0);
1574 * reduce_outer_joins
1575 * Attempt to reduce outer joins to plain inner joins.
1577 * The idea here is that given a query like
1578 * SELECT ... FROM a LEFT JOIN b ON (...) WHERE b.y = 42;
1579 * we can reduce the LEFT JOIN to a plain JOIN if the "=" operator in WHERE
1580 * is strict. The strict operator will always return NULL, causing the outer
1581 * WHERE to fail, on any row where the LEFT JOIN filled in NULLs for b's
1582 * columns. Therefore, there's no need for the join to produce null-extended
1583 * rows in the first place --- which makes it a plain join not an outer join.
1584 * (This scenario may not be very likely in a query written out by hand, but
1585 * it's reasonably likely when pushing quals down into complex views.)
1587 * More generally, an outer join can be reduced in strength if there is a
1588 * strict qual above it in the qual tree that constrains a Var from the
1589 * nullable side of the join to be non-null. (For FULL joins this applies
1590 * to each side separately.)
1592 * Another transformation we apply here is to recognize cases like
1593 * SELECT ... FROM a LEFT JOIN b ON (a.x = b.y) WHERE b.y IS NULL;
1594 * If the join clause is strict for b.y, then only null-extended rows could
1595 * pass the upper WHERE, and we can conclude that what the query is really
1596 * specifying is an anti-semijoin. We change the join type from JOIN_LEFT
1597 * to JOIN_ANTI. The IS NULL clause then becomes redundant, and must be
1598 * removed to prevent bogus selectivity calculations, but we leave it to
1599 * distribute_qual_to_rels to get rid of such clauses.
1601 * Also, we get rid of JOIN_RIGHT cases by flipping them around to become
1602 * JOIN_LEFT. This saves some code here and in some later planner routines,
1603 * but the main reason to do it is to not need to invent a JOIN_REVERSE_ANTI
1606 * To ease recognition of strict qual clauses, we require this routine to be
1607 * run after expression preprocessing (i.e., qual canonicalization and JOIN
1608 * alias-var expansion).
1611 reduce_outer_joins(PlannerInfo *root)
1613 reduce_outer_joins_state *state;
1616 * To avoid doing strictness checks on more quals than necessary, we want
1617 * to stop descending the jointree as soon as there are no outer joins
1618 * below our current point. This consideration forces a two-pass process.
1619 * The first pass gathers information about which base rels appear below
1620 * each side of each join clause, and about whether there are outer
1621 * join(s) below each side of each join clause. The second pass examines
1622 * qual clauses and changes join types as it descends the tree.
1624 state = reduce_outer_joins_pass1((Node *) root->parse->jointree);
1626 /* planner.c shouldn't have called me if no outer joins */
1627 if (state == NULL || !state->contains_outer)
1628 elog(ERROR, "so where are the outer joins?");
1630 reduce_outer_joins_pass2((Node *) root->parse->jointree,
1631 state, root, NULL, NIL, NIL);
1635 * reduce_outer_joins_pass1 - phase 1 data collection
1637 * Returns a state node describing the given jointree node.
1639 static reduce_outer_joins_state *
1640 reduce_outer_joins_pass1(Node *jtnode)
1642 reduce_outer_joins_state *result;
1644 result = (reduce_outer_joins_state *)
1645 palloc(sizeof(reduce_outer_joins_state));
1646 result->relids = NULL;
1647 result->contains_outer = false;
1648 result->sub_states = NIL;
1652 if (IsA(jtnode, RangeTblRef))
1654 int varno = ((RangeTblRef *) jtnode)->rtindex;
1656 result->relids = bms_make_singleton(varno);
1658 else if (IsA(jtnode, FromExpr))
1660 FromExpr *f = (FromExpr *) jtnode;
1663 foreach(l, f->fromlist)
1665 reduce_outer_joins_state *sub_state;
1667 sub_state = reduce_outer_joins_pass1(lfirst(l));
1668 result->relids = bms_add_members(result->relids,
1670 result->contains_outer |= sub_state->contains_outer;
1671 result->sub_states = lappend(result->sub_states, sub_state);
1674 else if (IsA(jtnode, JoinExpr))
1676 JoinExpr *j = (JoinExpr *) jtnode;
1677 reduce_outer_joins_state *sub_state;
1679 /* join's own RT index is not wanted in result->relids */
1680 if (IS_OUTER_JOIN(j->jointype))
1681 result->contains_outer = true;
1683 sub_state = reduce_outer_joins_pass1(j->larg);
1684 result->relids = bms_add_members(result->relids,
1686 result->contains_outer |= sub_state->contains_outer;
1687 result->sub_states = lappend(result->sub_states, sub_state);
1689 sub_state = reduce_outer_joins_pass1(j->rarg);
1690 result->relids = bms_add_members(result->relids,
1692 result->contains_outer |= sub_state->contains_outer;
1693 result->sub_states = lappend(result->sub_states, sub_state);
1696 elog(ERROR, "unrecognized node type: %d",
1697 (int) nodeTag(jtnode));
1702 * reduce_outer_joins_pass2 - phase 2 processing
1704 * jtnode: current jointree node
1705 * state: state data collected by phase 1 for this node
1706 * root: toplevel planner state
1707 * nonnullable_rels: set of base relids forced non-null by upper quals
1708 * nonnullable_vars: list of Vars forced non-null by upper quals
1709 * forced_null_vars: list of Vars forced null by upper quals
1712 reduce_outer_joins_pass2(Node *jtnode,
1713 reduce_outer_joins_state *state,
1715 Relids nonnullable_rels,
1716 List *nonnullable_vars,
1717 List *forced_null_vars)
1720 * pass 2 should never descend as far as an empty subnode or base rel,
1721 * because it's only called on subtrees marked as contains_outer.
1724 elog(ERROR, "reached empty jointree");
1725 if (IsA(jtnode, RangeTblRef))
1726 elog(ERROR, "reached base rel");
1727 else if (IsA(jtnode, FromExpr))
1729 FromExpr *f = (FromExpr *) jtnode;
1732 Relids pass_nonnullable_rels;
1733 List *pass_nonnullable_vars;
1734 List *pass_forced_null_vars;
1736 /* Scan quals to see if we can add any constraints */
1737 pass_nonnullable_rels = find_nonnullable_rels(f->quals);
1738 pass_nonnullable_rels = bms_add_members(pass_nonnullable_rels,
1740 /* NB: we rely on list_concat to not damage its second argument */
1741 pass_nonnullable_vars = find_nonnullable_vars(f->quals);
1742 pass_nonnullable_vars = list_concat(pass_nonnullable_vars,
1744 pass_forced_null_vars = find_forced_null_vars(f->quals);
1745 pass_forced_null_vars = list_concat(pass_forced_null_vars,
1747 /* And recurse --- but only into interesting subtrees */
1748 Assert(list_length(f->fromlist) == list_length(state->sub_states));
1749 forboth(l, f->fromlist, s, state->sub_states)
1751 reduce_outer_joins_state *sub_state = lfirst(s);
1753 if (sub_state->contains_outer)
1754 reduce_outer_joins_pass2(lfirst(l), sub_state, root,
1755 pass_nonnullable_rels,
1756 pass_nonnullable_vars,
1757 pass_forced_null_vars);
1759 bms_free(pass_nonnullable_rels);
1760 /* can't so easily clean up var lists, unfortunately */
1762 else if (IsA(jtnode, JoinExpr))
1764 JoinExpr *j = (JoinExpr *) jtnode;
1765 int rtindex = j->rtindex;
1766 JoinType jointype = j->jointype;
1767 reduce_outer_joins_state *left_state = linitial(state->sub_states);
1768 reduce_outer_joins_state *right_state = lsecond(state->sub_states);
1769 List *local_nonnullable_vars = NIL;
1770 bool computed_local_nonnullable_vars = false;
1772 /* Can we simplify this join? */
1778 if (bms_overlap(nonnullable_rels, right_state->relids))
1779 jointype = JOIN_INNER;
1782 if (bms_overlap(nonnullable_rels, left_state->relids))
1783 jointype = JOIN_INNER;
1786 if (bms_overlap(nonnullable_rels, left_state->relids))
1788 if (bms_overlap(nonnullable_rels, right_state->relids))
1789 jointype = JOIN_INNER;
1791 jointype = JOIN_LEFT;
1795 if (bms_overlap(nonnullable_rels, right_state->relids))
1796 jointype = JOIN_RIGHT;
1803 * These could only have been introduced by pull_up_sublinks,
1804 * so there's no way that upper quals could refer to their
1805 * righthand sides, and no point in checking.
1809 elog(ERROR, "unrecognized join type: %d",
1815 * Convert JOIN_RIGHT to JOIN_LEFT. Note that in the case where we
1816 * reduced JOIN_FULL to JOIN_RIGHT, this will mean the JoinExpr no
1817 * longer matches the internal ordering of any CoalesceExpr's built to
1818 * represent merged join variables. We don't care about that at
1819 * present, but be wary of it ...
1821 if (jointype == JOIN_RIGHT)
1828 jointype = JOIN_LEFT;
1829 right_state = linitial(state->sub_states);
1830 left_state = lsecond(state->sub_states);
1834 * See if we can reduce JOIN_LEFT to JOIN_ANTI. This is the case if
1835 * the join's own quals are strict for any var that was forced null by
1836 * higher qual levels. NOTE: there are other ways that we could
1837 * detect an anti-join, in particular if we were to check whether Vars
1838 * coming from the RHS must be non-null because of table constraints.
1839 * That seems complicated and expensive though (in particular, one
1840 * would have to be wary of lower outer joins). For the moment this
1843 if (jointype == JOIN_LEFT)
1847 local_nonnullable_vars = find_nonnullable_vars(j->quals);
1848 computed_local_nonnullable_vars = true;
1851 * It's not sufficient to check whether local_nonnullable_vars and
1852 * forced_null_vars overlap: we need to know if the overlap
1853 * includes any RHS variables.
1855 overlap = list_intersection(local_nonnullable_vars,
1857 if (overlap != NIL &&
1858 bms_overlap(pull_varnos((Node *) overlap),
1859 right_state->relids))
1860 jointype = JOIN_ANTI;
1863 /* Apply the jointype change, if any, to both jointree node and RTE */
1864 if (rtindex && jointype != j->jointype)
1866 RangeTblEntry *rte = rt_fetch(rtindex, root->parse->rtable);
1868 Assert(rte->rtekind == RTE_JOIN);
1869 Assert(rte->jointype == j->jointype);
1870 rte->jointype = jointype;
1872 j->jointype = jointype;
1874 /* Only recurse if there's more to do below here */
1875 if (left_state->contains_outer || right_state->contains_outer)
1877 Relids local_nonnullable_rels;
1878 List *local_forced_null_vars;
1879 Relids pass_nonnullable_rels;
1880 List *pass_nonnullable_vars;
1881 List *pass_forced_null_vars;
1884 * If this join is (now) inner, we can add any constraints its
1885 * quals provide to those we got from above. But if it is outer,
1886 * we can pass down the local constraints only into the nullable
1887 * side, because an outer join never eliminates any rows from its
1888 * non-nullable side. Also, there is no point in passing upper
1889 * constraints into the nullable side, since if there were any
1890 * we'd have been able to reduce the join. (In the case of upper
1891 * forced-null constraints, we *must not* pass them into the
1892 * nullable side --- they either applied here, or not.) The upshot
1893 * is that we pass either the local or the upper constraints,
1894 * never both, to the children of an outer join.
1896 * Note that a SEMI join works like an inner join here: it's okay
1897 * to pass down both local and upper constraints. (There can't be
1898 * any upper constraints affecting its inner side, but it's not
1899 * worth having a separate code path to avoid passing them.)
1901 * At a FULL join we just punt and pass nothing down --- is it
1902 * possible to be smarter?
1904 if (jointype != JOIN_FULL)
1906 local_nonnullable_rels = find_nonnullable_rels(j->quals);
1907 if (!computed_local_nonnullable_vars)
1908 local_nonnullable_vars = find_nonnullable_vars(j->quals);
1909 local_forced_null_vars = find_forced_null_vars(j->quals);
1910 if (jointype == JOIN_INNER || jointype == JOIN_SEMI)
1912 /* OK to merge upper and local constraints */
1913 local_nonnullable_rels = bms_add_members(local_nonnullable_rels,
1915 local_nonnullable_vars = list_concat(local_nonnullable_vars,
1917 local_forced_null_vars = list_concat(local_forced_null_vars,
1923 /* no use in calculating these */
1924 local_nonnullable_rels = NULL;
1925 local_forced_null_vars = NIL;
1928 if (left_state->contains_outer)
1930 if (jointype == JOIN_INNER || jointype == JOIN_SEMI)
1932 /* pass union of local and upper constraints */
1933 pass_nonnullable_rels = local_nonnullable_rels;
1934 pass_nonnullable_vars = local_nonnullable_vars;
1935 pass_forced_null_vars = local_forced_null_vars;
1937 else if (jointype != JOIN_FULL) /* ie, LEFT or ANTI */
1939 /* can't pass local constraints to non-nullable side */
1940 pass_nonnullable_rels = nonnullable_rels;
1941 pass_nonnullable_vars = nonnullable_vars;
1942 pass_forced_null_vars = forced_null_vars;
1946 /* no constraints pass through JOIN_FULL */
1947 pass_nonnullable_rels = NULL;
1948 pass_nonnullable_vars = NIL;
1949 pass_forced_null_vars = NIL;
1951 reduce_outer_joins_pass2(j->larg, left_state, root,
1952 pass_nonnullable_rels,
1953 pass_nonnullable_vars,
1954 pass_forced_null_vars);
1957 if (right_state->contains_outer)
1959 if (jointype != JOIN_FULL) /* ie, INNER/LEFT/SEMI/ANTI */
1961 /* pass appropriate constraints, per comment above */
1962 pass_nonnullable_rels = local_nonnullable_rels;
1963 pass_nonnullable_vars = local_nonnullable_vars;
1964 pass_forced_null_vars = local_forced_null_vars;
1968 /* no constraints pass through JOIN_FULL */
1969 pass_nonnullable_rels = NULL;
1970 pass_nonnullable_vars = NIL;
1971 pass_forced_null_vars = NIL;
1973 reduce_outer_joins_pass2(j->rarg, right_state, root,
1974 pass_nonnullable_rels,
1975 pass_nonnullable_vars,
1976 pass_forced_null_vars);
1978 bms_free(local_nonnullable_rels);
1982 elog(ERROR, "unrecognized node type: %d",
1983 (int) nodeTag(jtnode));
1987 * substitute_multiple_relids - adjust node relid sets after pulling up
1990 * Find any PlaceHolderVar nodes in the given tree that reference the
1991 * pulled-up relid, and change them to reference the replacement relid(s).
1992 * We do not need to recurse into subqueries, since no subquery of the current
1993 * top query could (yet) contain such a reference.
1995 * NOTE: although this has the form of a walker, we cheat and modify the
1996 * nodes in-place. This should be OK since the tree was copied by
1997 * pullup_replace_vars earlier. Avoid scribbling on the original values of
1998 * the bitmapsets, though, because expression_tree_mutator doesn't copy those.
2005 } substitute_multiple_relids_context;
2008 substitute_multiple_relids_walker(Node *node,
2009 substitute_multiple_relids_context *context)
2013 if (IsA(node, PlaceHolderVar))
2015 PlaceHolderVar *phv = (PlaceHolderVar *) node;
2017 if (bms_is_member(context->varno, phv->phrels))
2019 phv->phrels = bms_union(phv->phrels,
2020 context->subrelids);
2021 phv->phrels = bms_del_member(phv->phrels,
2024 /* fall through to examine children */
2026 /* Shouldn't need to handle planner auxiliary nodes here */
2027 Assert(!IsA(node, SpecialJoinInfo));
2028 Assert(!IsA(node, AppendRelInfo));
2029 Assert(!IsA(node, PlaceHolderInfo));
2030 Assert(!IsA(node, MinMaxAggInfo));
2032 return expression_tree_walker(node, substitute_multiple_relids_walker,
2037 substitute_multiple_relids(Node *node, int varno, Relids subrelids)
2039 substitute_multiple_relids_context context;
2041 context.varno = varno;
2042 context.subrelids = subrelids;
2045 * Must be prepared to start with a Query or a bare expression tree.
2047 query_or_expression_tree_walker(node,
2048 substitute_multiple_relids_walker,
2054 * fix_append_rel_relids: update RT-index fields of AppendRelInfo nodes
2056 * When we pull up a subquery, any AppendRelInfo references to the subquery's
2057 * RT index have to be replaced by the substituted relid (and there had better
2058 * be only one). We also need to apply substitute_multiple_relids to their
2059 * translated_vars lists, since those might contain PlaceHolderVars.
2061 * We assume we may modify the AppendRelInfo nodes in-place.
2064 fix_append_rel_relids(List *append_rel_list, int varno, Relids subrelids)
2070 * We only want to extract the member relid once, but we mustn't fail
2071 * immediately if there are multiple members; it could be that none of the
2072 * AppendRelInfo nodes refer to it. So compute it on first use. Note that
2073 * bms_singleton_member will complain if set is not singleton.
2075 foreach(l, append_rel_list)
2077 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
2079 /* The parent_relid shouldn't ever be a pullup target */
2080 Assert(appinfo->parent_relid != varno);
2082 if (appinfo->child_relid == varno)
2085 subvarno = bms_singleton_member(subrelids);
2086 appinfo->child_relid = subvarno;
2089 /* Also finish fixups for its translated vars */
2090 substitute_multiple_relids((Node *) appinfo->translated_vars,
2096 * get_relids_in_jointree: get set of RT indexes present in a jointree
2098 * If include_joins is true, join RT indexes are included; if false,
2099 * only base rels are included.
2102 get_relids_in_jointree(Node *jtnode, bool include_joins)
2104 Relids result = NULL;
2108 if (IsA(jtnode, RangeTblRef))
2110 int varno = ((RangeTblRef *) jtnode)->rtindex;
2112 result = bms_make_singleton(varno);
2114 else if (IsA(jtnode, FromExpr))
2116 FromExpr *f = (FromExpr *) jtnode;
2119 foreach(l, f->fromlist)
2121 result = bms_join(result,
2122 get_relids_in_jointree(lfirst(l),
2126 else if (IsA(jtnode, JoinExpr))
2128 JoinExpr *j = (JoinExpr *) jtnode;
2130 result = get_relids_in_jointree(j->larg, include_joins);
2131 result = bms_join(result,
2132 get_relids_in_jointree(j->rarg, include_joins));
2133 if (include_joins && j->rtindex)
2134 result = bms_add_member(result, j->rtindex);
2137 elog(ERROR, "unrecognized node type: %d",
2138 (int) nodeTag(jtnode));
2143 * get_relids_for_join: get set of base RT indexes making up a join
2146 get_relids_for_join(PlannerInfo *root, int joinrelid)
2150 jtnode = find_jointree_node_for_rel((Node *) root->parse->jointree,
2153 elog(ERROR, "could not find join node %d", joinrelid);
2154 return get_relids_in_jointree(jtnode, false);
2158 * find_jointree_node_for_rel: locate jointree node for a base or join RT index
2160 * Returns NULL if not found
2163 find_jointree_node_for_rel(Node *jtnode, int relid)
2167 if (IsA(jtnode, RangeTblRef))
2169 int varno = ((RangeTblRef *) jtnode)->rtindex;
2174 else if (IsA(jtnode, FromExpr))
2176 FromExpr *f = (FromExpr *) jtnode;
2179 foreach(l, f->fromlist)
2181 jtnode = find_jointree_node_for_rel(lfirst(l), relid);
2186 else if (IsA(jtnode, JoinExpr))
2188 JoinExpr *j = (JoinExpr *) jtnode;
2190 if (relid == j->rtindex)
2192 jtnode = find_jointree_node_for_rel(j->larg, relid);
2195 jtnode = find_jointree_node_for_rel(j->rarg, relid);
2200 elog(ERROR, "unrecognized node type: %d",
2201 (int) nodeTag(jtnode));