1 /*-------------------------------------------------------------------------
4 * Target list, qualification, joininfo initialization routines
6 * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/optimizer/plan/initsplan.c
13 *-------------------------------------------------------------------------
17 #include "catalog/pg_operator.h"
18 #include "catalog/pg_type.h"
19 #include "nodes/nodeFuncs.h"
20 #include "optimizer/clauses.h"
21 #include "optimizer/cost.h"
22 #include "optimizer/joininfo.h"
23 #include "optimizer/pathnode.h"
24 #include "optimizer/paths.h"
25 #include "optimizer/placeholder.h"
26 #include "optimizer/planmain.h"
27 #include "optimizer/prep.h"
28 #include "optimizer/restrictinfo.h"
29 #include "optimizer/var.h"
30 #include "parser/parse_expr.h"
31 #include "parser/parse_oper.h"
32 #include "utils/builtins.h"
33 #include "utils/lsyscache.h"
34 #include "utils/syscache.h"
37 /* These parameters are set by GUC */
38 int from_collapse_limit;
39 int join_collapse_limit;
42 static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
43 bool below_outer_join,
44 Relids *qualscope, Relids *inner_join_rels);
45 static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root,
46 Relids left_rels, Relids right_rels,
47 Relids inner_join_rels,
48 JoinType jointype, List *clause);
49 static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
51 bool below_outer_join,
55 Relids outerjoin_nonnullable);
56 static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p,
57 Relids *nullable_relids_p, bool is_pushed_down);
58 static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause);
59 static void check_mergejoinable(RestrictInfo *restrictinfo);
60 static void check_hashjoinable(RestrictInfo *restrictinfo);
63 /*****************************************************************************
67 *****************************************************************************/
70 * add_base_rels_to_query
72 * Scan the query's jointree and create baserel RelOptInfos for all
73 * the base relations (ie, table, subquery, and function RTEs)
74 * appearing in the jointree.
76 * The initial invocation must pass root->parse->jointree as the value of
77 * jtnode. Internally, the function recurses through the jointree.
79 * At the end of this process, there should be one baserel RelOptInfo for
80 * every non-join RTE that is used in the query. Therefore, this routine
81 * is the only place that should call build_simple_rel with reloptkind
82 * RELOPT_BASEREL. (Note: build_simple_rel recurses internally to build
83 * "other rel" RelOptInfos for the members of any appendrels we find here.)
86 add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
90 if (IsA(jtnode, RangeTblRef))
92 int varno = ((RangeTblRef *) jtnode)->rtindex;
94 (void) build_simple_rel(root, varno, RELOPT_BASEREL);
96 else if (IsA(jtnode, FromExpr))
98 FromExpr *f = (FromExpr *) jtnode;
101 foreach(l, f->fromlist)
102 add_base_rels_to_query(root, lfirst(l));
104 else if (IsA(jtnode, JoinExpr))
106 JoinExpr *j = (JoinExpr *) jtnode;
108 add_base_rels_to_query(root, j->larg);
109 add_base_rels_to_query(root, j->rarg);
112 elog(ERROR, "unrecognized node type: %d",
113 (int) nodeTag(jtnode));
117 /*****************************************************************************
121 *****************************************************************************/
124 * build_base_rel_tlists
125 * Add targetlist entries for each var needed in the query's final tlist
126 * to the appropriate base relations.
128 * We mark such vars as needed by "relation 0" to ensure that they will
129 * propagate up through all join plan steps.
132 build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
134 List *tlist_vars = pull_var_clause((Node *) final_tlist,
135 PVC_INCLUDE_PLACEHOLDERS);
137 if (tlist_vars != NIL)
139 add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0));
140 list_free(tlist_vars);
145 * add_vars_to_targetlist
146 * For each variable appearing in the list, add it to the owning
147 * relation's targetlist if not already present, and mark the variable
148 * as being needed for the indicated join (or for final output if
149 * where_needed includes "relation 0").
151 * The list may also contain PlaceHolderVars. These don't necessarily
152 * have a single owning relation; we keep their attr_needed info in
153 * root->placeholder_list instead.
156 add_vars_to_targetlist(PlannerInfo *root, List *vars, Relids where_needed)
160 Assert(!bms_is_empty(where_needed));
164 Node *node = (Node *) lfirst(temp);
168 Var *var = (Var *) node;
169 RelOptInfo *rel = find_base_rel(root, var->varno);
170 int attno = var->varattno;
172 Assert(attno >= rel->min_attr && attno <= rel->max_attr);
173 attno -= rel->min_attr;
174 if (rel->attr_needed[attno] == NULL)
176 /* Variable not yet requested, so add to reltargetlist */
177 /* XXX is copyObject necessary here? */
178 rel->reltargetlist = lappend(rel->reltargetlist,
181 rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno],
184 else if (IsA(node, PlaceHolderVar))
186 PlaceHolderVar *phv = (PlaceHolderVar *) node;
187 PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
189 phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
192 * Update ph_may_need too. This is currently only necessary
193 * when being called from build_base_rel_tlists, but we may as
196 phinfo->ph_may_need = bms_add_members(phinfo->ph_may_need,
200 elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
205 /*****************************************************************************
207 * JOIN TREE PROCESSING
209 *****************************************************************************/
212 * deconstruct_jointree
213 * Recursively scan the query's join tree for WHERE and JOIN/ON qual
214 * clauses, and add these to the appropriate restrictinfo and joininfo
215 * lists belonging to base RelOptInfos. Also, add SpecialJoinInfo nodes
216 * to root->join_info_list for any outer joins appearing in the query tree.
217 * Return a "joinlist" data structure showing the join order decisions
218 * that need to be made by make_one_rel().
220 * The "joinlist" result is a list of items that are either RangeTblRef
221 * jointree nodes or sub-joinlists. All the items at the same level of
222 * joinlist must be joined in an order to be determined by make_one_rel()
223 * (note that legal orders may be constrained by SpecialJoinInfo nodes).
224 * A sub-joinlist represents a subproblem to be planned separately. Currently
225 * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
226 * subproblems is stopped by join_collapse_limit or from_collapse_limit.
228 * NOTE: when dealing with inner joins, it is appropriate to let a qual clause
229 * be evaluated at the lowest level where all the variables it mentions are
230 * available. However, we cannot push a qual down into the nullable side(s)
231 * of an outer join since the qual might eliminate matching rows and cause a
232 * NULL row to be incorrectly emitted by the join. Therefore, we artificially
233 * OR the minimum-relids of such an outer join into the required_relids of
234 * clauses appearing above it. This forces those clauses to be delayed until
235 * application of the outer join (or maybe even higher in the join tree).
238 deconstruct_jointree(PlannerInfo *root)
241 Relids inner_join_rels;
243 /* Start recursion at top of jointree */
244 Assert(root->parse->jointree != NULL &&
245 IsA(root->parse->jointree, FromExpr));
247 return deconstruct_recurse(root, (Node *) root->parse->jointree, false,
248 &qualscope, &inner_join_rels);
252 * deconstruct_recurse
253 * One recursion level of deconstruct_jointree processing.
256 * jtnode is the jointree node to examine
257 * below_outer_join is TRUE if this node is within the nullable side of a
258 * higher-level outer join
260 * *qualscope gets the set of base Relids syntactically included in this
261 * jointree node (do not modify or free this, as it may also be pointed
262 * to by RestrictInfo and SpecialJoinInfo nodes)
263 * *inner_join_rels gets the set of base Relids syntactically included in
264 * inner joins appearing at or below this jointree node (do not modify
265 * or free this, either)
266 * Return value is the appropriate joinlist for this jointree node
268 * In addition, entries will be added to root->join_info_list for outer joins.
271 deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
272 Relids *qualscope, Relids *inner_join_rels)
279 *inner_join_rels = NULL;
282 if (IsA(jtnode, RangeTblRef))
284 int varno = ((RangeTblRef *) jtnode)->rtindex;
286 /* No quals to deal with, just return correct result */
287 *qualscope = bms_make_singleton(varno);
288 /* A single baserel does not create an inner join */
289 *inner_join_rels = NULL;
290 joinlist = list_make1(jtnode);
292 else if (IsA(jtnode, FromExpr))
294 FromExpr *f = (FromExpr *) jtnode;
299 * First, recurse to handle child joins. We collapse subproblems into
300 * a single joinlist whenever the resulting joinlist wouldn't exceed
301 * from_collapse_limit members. Also, always collapse one-element
302 * subproblems, since that won't lengthen the joinlist anyway.
305 *inner_join_rels = NULL;
307 remaining = list_length(f->fromlist);
308 foreach(l, f->fromlist)
310 Relids sub_qualscope;
314 sub_joinlist = deconstruct_recurse(root, lfirst(l),
318 *qualscope = bms_add_members(*qualscope, sub_qualscope);
319 sub_members = list_length(sub_joinlist);
321 if (sub_members <= 1 ||
322 list_length(joinlist) + sub_members + remaining <= from_collapse_limit)
323 joinlist = list_concat(joinlist, sub_joinlist);
325 joinlist = lappend(joinlist, sub_joinlist);
329 * A FROM with more than one list element is an inner join subsuming
330 * all below it, so we should report inner_join_rels = qualscope. If
331 * there was exactly one element, we should (and already did) report
332 * whatever its inner_join_rels were. If there were no elements (is
333 * that possible?) the initialization before the loop fixed it.
335 if (list_length(f->fromlist) > 1)
336 *inner_join_rels = *qualscope;
339 * Now process the top-level quals.
341 foreach(l, (List *) f->quals)
343 Node *qual = (Node *) lfirst(l);
345 distribute_qual_to_rels(root, qual,
346 false, below_outer_join, JOIN_INNER,
347 *qualscope, NULL, NULL);
350 else if (IsA(jtnode, JoinExpr))
352 JoinExpr *j = (JoinExpr *) jtnode;
361 SpecialJoinInfo *sjinfo;
365 * Order of operations here is subtle and critical. First we recurse
366 * to handle sub-JOINs. Their join quals will be placed without
367 * regard for whether this level is an outer join, which is correct.
368 * Then we place our own join quals, which are restricted by lower
369 * outer joins in any case, and are forced to this level if this is an
370 * outer join and they mention the outer side. Finally, if this is an
371 * outer join, we create a join_info_list entry for the join. This
372 * will prevent quals above us in the join tree that use those rels
373 * from being pushed down below this level. (It's okay for upper
374 * quals to be pushed down to the outer side, however.)
379 leftjoinlist = deconstruct_recurse(root, j->larg,
381 &leftids, &left_inners);
382 rightjoinlist = deconstruct_recurse(root, j->rarg,
384 &rightids, &right_inners);
385 *qualscope = bms_union(leftids, rightids);
386 *inner_join_rels = *qualscope;
387 /* Inner join adds no restrictions for quals */
388 nonnullable_rels = NULL;
392 leftjoinlist = deconstruct_recurse(root, j->larg,
394 &leftids, &left_inners);
395 rightjoinlist = deconstruct_recurse(root, j->rarg,
397 &rightids, &right_inners);
398 *qualscope = bms_union(leftids, rightids);
399 *inner_join_rels = bms_union(left_inners, right_inners);
400 nonnullable_rels = leftids;
403 leftjoinlist = deconstruct_recurse(root, j->larg,
405 &leftids, &left_inners);
406 rightjoinlist = deconstruct_recurse(root, j->rarg,
408 &rightids, &right_inners);
409 *qualscope = bms_union(leftids, rightids);
410 *inner_join_rels = bms_union(left_inners, right_inners);
411 /* Semi join adds no restrictions for quals */
412 nonnullable_rels = NULL;
415 leftjoinlist = deconstruct_recurse(root, j->larg,
417 &leftids, &left_inners);
418 rightjoinlist = deconstruct_recurse(root, j->rarg,
420 &rightids, &right_inners);
421 *qualscope = bms_union(leftids, rightids);
422 *inner_join_rels = bms_union(left_inners, right_inners);
423 /* each side is both outer and inner */
424 nonnullable_rels = *qualscope;
427 /* JOIN_RIGHT was eliminated during reduce_outer_joins() */
428 elog(ERROR, "unrecognized join type: %d",
430 nonnullable_rels = NULL; /* keep compiler quiet */
431 leftjoinlist = rightjoinlist = NIL;
436 * For an OJ, form the SpecialJoinInfo now, because we need the OJ's
437 * semantic scope (ojscope) to pass to distribute_qual_to_rels. But
438 * we mustn't add it to join_info_list just yet, because we don't want
439 * distribute_qual_to_rels to think it is an outer join below us.
441 * Semijoins are a bit of a hybrid: we build a SpecialJoinInfo, but we
442 * want ojscope = NULL for distribute_qual_to_rels.
444 if (j->jointype != JOIN_INNER)
446 sjinfo = make_outerjoininfo(root,
451 if (j->jointype == JOIN_SEMI)
454 ojscope = bms_union(sjinfo->min_lefthand,
455 sjinfo->min_righthand);
463 /* Process the qual clauses */
464 foreach(l, (List *) j->quals)
466 Node *qual = (Node *) lfirst(l);
468 distribute_qual_to_rels(root, qual,
469 false, below_outer_join, j->jointype,
471 ojscope, nonnullable_rels);
474 /* Now we can add the SpecialJoinInfo to join_info_list */
477 root->join_info_list = lappend(root->join_info_list, sjinfo);
478 /* Each time we do that, recheck placeholder eval levels */
479 update_placeholder_eval_levels(root, sjinfo);
483 * Finally, compute the output joinlist. We fold subproblems together
484 * except at a FULL JOIN or where join_collapse_limit would be
487 if (j->jointype == JOIN_FULL)
489 /* force the join order exactly at this node */
490 joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
492 else if (list_length(leftjoinlist) + list_length(rightjoinlist) <=
495 /* OK to combine subproblems */
496 joinlist = list_concat(leftjoinlist, rightjoinlist);
500 /* can't combine, but needn't force join order above here */
504 /* avoid creating useless 1-element sublists */
505 if (list_length(leftjoinlist) == 1)
506 leftpart = (Node *) linitial(leftjoinlist);
508 leftpart = (Node *) leftjoinlist;
509 if (list_length(rightjoinlist) == 1)
510 rightpart = (Node *) linitial(rightjoinlist);
512 rightpart = (Node *) rightjoinlist;
513 joinlist = list_make2(leftpart, rightpart);
518 elog(ERROR, "unrecognized node type: %d",
519 (int) nodeTag(jtnode));
520 joinlist = NIL; /* keep compiler quiet */
527 * Build a SpecialJoinInfo for the current outer join
530 * left_rels: the base Relids syntactically on outer side of join
531 * right_rels: the base Relids syntactically on inner side of join
532 * inner_join_rels: base Relids participating in inner joins below this one
533 * jointype: what it says (must always be LEFT, FULL, SEMI, or ANTI)
534 * clause: the outer join's join condition (in implicit-AND format)
536 * The node should eventually be appended to root->join_info_list, but we
537 * do not do that here.
539 * Note: we assume that this function is invoked bottom-up, so that
540 * root->join_info_list already contains entries for all outer joins that are
541 * syntactically below this one.
543 static SpecialJoinInfo *
544 make_outerjoininfo(PlannerInfo *root,
545 Relids left_rels, Relids right_rels,
546 Relids inner_join_rels,
547 JoinType jointype, List *clause)
549 SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo);
550 Relids clause_relids;
551 Relids strict_relids;
553 Relids min_righthand;
557 * We should not see RIGHT JOIN here because left/right were switched
560 Assert(jointype != JOIN_INNER);
561 Assert(jointype != JOIN_RIGHT);
564 * Presently the executor cannot support FOR UPDATE/SHARE marking of rels
565 * appearing on the nullable side of an outer join. (It's somewhat unclear
566 * what that would mean, anyway: what should we mark when a result row is
567 * generated from no element of the nullable relation?) So, complain if
568 * any nullable rel is FOR UPDATE/SHARE.
570 * You might be wondering why this test isn't made far upstream in the
571 * parser. It's because the parser hasn't got enough info --- consider
572 * FOR UPDATE applied to a view. Only after rewriting and flattening do
573 * we know whether the view contains an outer join.
575 * We use the original RowMarkClause list here; the PlanRowMark list would
578 foreach(l, root->parse->rowMarks)
580 RowMarkClause *rc = (RowMarkClause *) lfirst(l);
582 if (bms_is_member(rc->rti, right_rels) ||
583 (jointype == JOIN_FULL && bms_is_member(rc->rti, left_rels)))
585 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
586 errmsg("SELECT FOR UPDATE/SHARE cannot be applied to the nullable side of an outer join")));
589 sjinfo->syn_lefthand = left_rels;
590 sjinfo->syn_righthand = right_rels;
591 sjinfo->jointype = jointype;
592 /* this always starts out false */
593 sjinfo->delay_upper_joins = false;
594 sjinfo->join_quals = clause;
596 /* If it's a full join, no need to be very smart */
597 if (jointype == JOIN_FULL)
599 sjinfo->min_lefthand = bms_copy(left_rels);
600 sjinfo->min_righthand = bms_copy(right_rels);
601 sjinfo->lhs_strict = false; /* don't care about this */
606 * Retrieve all relids mentioned within the join clause.
608 clause_relids = pull_varnos((Node *) clause);
611 * For which relids is the clause strict, ie, it cannot succeed if the
612 * rel's columns are all NULL?
614 strict_relids = find_nonnullable_rels((Node *) clause);
616 /* Remember whether the clause is strict for any LHS relations */
617 sjinfo->lhs_strict = bms_overlap(strict_relids, left_rels);
620 * Required LHS always includes the LHS rels mentioned in the clause. We
621 * may have to add more rels based on lower outer joins; see below.
623 min_lefthand = bms_intersect(clause_relids, left_rels);
626 * Similarly for required RHS. But here, we must also include any lower
627 * inner joins, to ensure we don't try to commute with any of them.
629 min_righthand = bms_int_members(bms_union(clause_relids, inner_join_rels),
632 foreach(l, root->join_info_list)
634 SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
636 /* ignore full joins --- other mechanisms preserve their ordering */
637 if (otherinfo->jointype == JOIN_FULL)
641 * For a lower OJ in our LHS, if our join condition uses the lower
642 * join's RHS and is not strict for that rel, we must preserve the
643 * ordering of the two OJs, so add lower OJ's full syntactic relset to
644 * min_lefthand. (We must use its full syntactic relset, not just its
645 * min_lefthand + min_righthand. This is because there might be other
646 * OJs below this one that this one can commute with, but we cannot
647 * commute with them if we don't with this one.) Also, if the current
648 * join is a semijoin or antijoin, we must preserve ordering
649 * regardless of strictness.
651 * Note: I believe we have to insist on being strict for at least one
652 * rel in the lower OJ's min_righthand, not its whole syn_righthand.
654 if (bms_overlap(left_rels, otherinfo->syn_righthand))
656 if (bms_overlap(clause_relids, otherinfo->syn_righthand) &&
657 (jointype == JOIN_SEMI || jointype == JOIN_ANTI ||
658 !bms_overlap(strict_relids, otherinfo->min_righthand)))
660 min_lefthand = bms_add_members(min_lefthand,
661 otherinfo->syn_lefthand);
662 min_lefthand = bms_add_members(min_lefthand,
663 otherinfo->syn_righthand);
668 * For a lower OJ in our RHS, if our join condition does not use the
669 * lower join's RHS and the lower OJ's join condition is strict, we
670 * can interchange the ordering of the two OJs; otherwise we must add
671 * lower OJ's full syntactic relset to min_righthand. Here, we must
672 * preserve ordering anyway if either the current join is a semijoin,
673 * or the lower OJ is either a semijoin or an antijoin.
675 * Here, we have to consider that "our join condition" includes any
676 * clauses that syntactically appeared above the lower OJ and below
677 * ours; those are equivalent to degenerate clauses in our OJ and must
678 * be treated as such. Such clauses obviously can't reference our
679 * LHS, and they must be non-strict for the lower OJ's RHS (else
680 * reduce_outer_joins would have reduced the lower OJ to a plain
681 * join). Hence the other ways in which we handle clauses within our
682 * join condition are not affected by them. The net effect is
683 * therefore sufficiently represented by the delay_upper_joins flag
684 * saved for us by check_outerjoin_delay.
686 if (bms_overlap(right_rels, otherinfo->syn_righthand))
688 if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
689 jointype == JOIN_SEMI ||
690 otherinfo->jointype == JOIN_SEMI ||
691 otherinfo->jointype == JOIN_ANTI ||
692 !otherinfo->lhs_strict || otherinfo->delay_upper_joins)
694 min_righthand = bms_add_members(min_righthand,
695 otherinfo->syn_lefthand);
696 min_righthand = bms_add_members(min_righthand,
697 otherinfo->syn_righthand);
703 * Examine PlaceHolderVars. If a PHV is supposed to be evaluated within
704 * this join's nullable side, and it may get used above this join, then
705 * ensure that min_righthand contains the full eval_at set of the PHV.
706 * This ensures that the PHV actually can be evaluated within the RHS.
707 * Note that this works only because we should already have determined
708 * the final eval_at level for any PHV syntactically within this join.
710 foreach(l, root->placeholder_list)
712 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
713 Relids ph_syn_level = phinfo->ph_var->phrels;
715 /* Ignore placeholder if it didn't syntactically come from RHS */
716 if (!bms_is_subset(ph_syn_level, right_rels))
719 /* We can also ignore it if it's certainly not used above this join */
720 /* XXX this test is probably overly conservative */
721 if (bms_is_subset(phinfo->ph_may_need, min_righthand))
724 /* Else, prevent join from being formed before we eval the PHV */
725 min_righthand = bms_add_members(min_righthand, phinfo->ph_eval_at);
729 * If we found nothing to put in min_lefthand, punt and make it the full
730 * LHS, to avoid having an empty min_lefthand which will confuse later
731 * processing. (We don't try to be smart about such cases, just correct.)
732 * Likewise for min_righthand.
734 if (bms_is_empty(min_lefthand))
735 min_lefthand = bms_copy(left_rels);
736 if (bms_is_empty(min_righthand))
737 min_righthand = bms_copy(right_rels);
739 /* Now they'd better be nonempty */
740 Assert(!bms_is_empty(min_lefthand));
741 Assert(!bms_is_empty(min_righthand));
742 /* Shouldn't overlap either */
743 Assert(!bms_overlap(min_lefthand, min_righthand));
745 sjinfo->min_lefthand = min_lefthand;
746 sjinfo->min_righthand = min_righthand;
752 /*****************************************************************************
756 *****************************************************************************/
759 * distribute_qual_to_rels
760 * Add clause information to either the baserestrictinfo or joininfo list
761 * (depending on whether the clause is a join) of each base relation
762 * mentioned in the clause. A RestrictInfo node is created and added to
763 * the appropriate list for each rel. Alternatively, if the clause uses a
764 * mergejoinable operator and is not delayed by outer-join rules, enter
765 * the left- and right-side expressions into the query's list of
766 * EquivalenceClasses.
768 * 'clause': the qual clause to be distributed
769 * 'is_deduced': TRUE if the qual came from implied-equality deduction
770 * 'below_outer_join': TRUE if the qual is from a JOIN/ON that is below the
771 * nullable side of a higher-level outer join
772 * 'jointype': type of join the qual is from (JOIN_INNER for a WHERE clause)
773 * 'qualscope': set of baserels the qual's syntactic scope covers
774 * 'ojscope': NULL if not an outer-join qual, else the minimum set of baserels
775 * needed to form this join
776 * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of
777 * baserels appearing on the outer (nonnullable) side of the join
778 * (for FULL JOIN this includes both sides of the join, and must in fact
781 * 'qualscope' identifies what level of JOIN the qual came from syntactically.
782 * 'ojscope' is needed if we decide to force the qual up to the outer-join
783 * level, which will be ojscope not necessarily qualscope.
785 * At the time this is called, root->join_info_list must contain entries for
786 * all and only those special joins that are syntactically below this qual.
789 distribute_qual_to_rels(PlannerInfo *root, Node *clause,
791 bool below_outer_join,
795 Relids outerjoin_nonnullable)
799 bool outerjoin_delayed;
800 bool pseudoconstant = false;
801 bool maybe_equivalence;
802 bool maybe_outer_join;
803 Relids nullable_relids;
804 RestrictInfo *restrictinfo;
807 * Retrieve all relids mentioned within the clause.
809 relids = pull_varnos(clause);
812 * Cross-check: clause should contain no relids not within its scope.
813 * Otherwise the parser messed up.
815 if (!bms_is_subset(relids, qualscope))
816 elog(ERROR, "JOIN qualification cannot refer to other relations");
817 if (ojscope && !bms_is_subset(relids, ojscope))
818 elog(ERROR, "JOIN qualification cannot refer to other relations");
821 * If the clause is variable-free, our normal heuristic for pushing it
822 * down to just the mentioned rels doesn't work, because there are none.
824 * If the clause is an outer-join clause, we must force it to the OJ's
825 * semantic level to preserve semantics.
827 * Otherwise, when the clause contains volatile functions, we force it to
828 * be evaluated at its original syntactic level. This preserves the
829 * expected semantics.
831 * When the clause contains no volatile functions either, it is actually a
832 * pseudoconstant clause that will not change value during any one
833 * execution of the plan, and hence can be used as a one-time qual in a
834 * gating Result plan node. We put such a clause into the regular
835 * RestrictInfo lists for the moment, but eventually createplan.c will
836 * pull it out and make a gating Result node immediately above whatever
837 * plan node the pseudoconstant clause is assigned to. It's usually best
838 * to put a gating node as high in the plan tree as possible. If we are
839 * not below an outer join, we can actually push the pseudoconstant qual
840 * all the way to the top of the tree. If we are below an outer join, we
841 * leave the qual at its original syntactic level (we could push it up to
842 * just below the outer join, but that seems more complex than it's
845 if (bms_is_empty(relids))
849 /* clause is attached to outer join, eval it there */
850 relids = bms_copy(ojscope);
851 /* mustn't use as gating qual, so don't mark pseudoconstant */
855 /* eval at original syntactic level */
856 relids = bms_copy(qualscope);
857 if (!contain_volatile_functions(clause))
859 /* mark as gating qual */
860 pseudoconstant = true;
861 /* tell createplan.c to check for gating quals */
862 root->hasPseudoConstantQuals = true;
863 /* if not below outer join, push it to top of tree */
864 if (!below_outer_join)
867 get_relids_in_jointree((Node *) root->parse->jointree,
869 qualscope = bms_copy(relids);
876 * Check to see if clause application must be delayed by outer-join
879 * A word about is_pushed_down: we mark the qual as "pushed down" if
880 * it is (potentially) applicable at a level different from its original
881 * syntactic level. This flag is used to distinguish OUTER JOIN ON quals
882 * from other quals pushed down to the same joinrel. The rules are:
883 * WHERE quals and INNER JOIN quals: is_pushed_down = true.
884 * Non-degenerate OUTER JOIN quals: is_pushed_down = false.
885 * Degenerate OUTER JOIN quals: is_pushed_down = true.
886 * A "degenerate" OUTER JOIN qual is one that doesn't mention the
887 * non-nullable side, and hence can be pushed down into the nullable side
888 * without changing the join result. It is correct to treat it as a
889 * regular filter condition at the level where it is evaluated.
891 * Note: it is not immediately obvious that a simple boolean is enough
892 * for this: if for some reason we were to attach a degenerate qual to
893 * its original join level, it would need to be treated as an outer join
894 * qual there. However, this cannot happen, because all the rels the
895 * clause mentions must be in the outer join's min_righthand, therefore
896 * the join it needs must be formed before the outer join; and we always
897 * attach quals to the lowest level where they can be evaluated. But
898 * if we were ever to re-introduce a mechanism for delaying evaluation
899 * of "expensive" quals, this area would need work.
905 * If the qual came from implied-equality deduction, it should not be
906 * outerjoin-delayed, else deducer blew it. But we can't check this
907 * because the join_info_list may now contain OJs above where the qual
911 is_pushed_down = true;
912 outerjoin_delayed = false;
913 nullable_relids = NULL;
914 /* Don't feed it back for more deductions */
915 maybe_equivalence = false;
916 maybe_outer_join = false;
918 else if (bms_overlap(relids, outerjoin_nonnullable))
921 * The qual is attached to an outer join and mentions (some of the)
922 * rels on the nonnullable side, so it's not degenerate.
924 * We can't use such a clause to deduce equivalence (the left and
925 * right sides might be unequal above the join because one of them has
926 * gone to NULL) ... but we might be able to use it for more limited
927 * deductions, if it is mergejoinable. So consider adding it to the
928 * lists of set-aside outer-join clauses.
930 is_pushed_down = false;
931 maybe_equivalence = false;
932 maybe_outer_join = true;
934 /* Check to see if must be delayed by lower outer join */
935 outerjoin_delayed = check_outerjoin_delay(root,
941 * Now force the qual to be evaluated exactly at the level of joining
942 * corresponding to the outer join. We cannot let it get pushed down
943 * into the nonnullable side, since then we'd produce no output rows,
944 * rather than the intended single null-extended row, for any
945 * nonnullable-side rows failing the qual.
947 * (Do this step after calling check_outerjoin_delay, because that
952 Assert(!pseudoconstant);
957 * Normal qual clause or degenerate outer-join clause. Either way, we
958 * can mark it as pushed-down.
960 is_pushed_down = true;
962 /* Check to see if must be delayed by lower outer join */
963 outerjoin_delayed = check_outerjoin_delay(root,
968 if (outerjoin_delayed)
970 /* Should still be a subset of current scope ... */
971 Assert(bms_is_subset(relids, qualscope));
974 * Because application of the qual will be delayed by outer join,
975 * we mustn't assume its vars are equal everywhere.
977 maybe_equivalence = false;
980 * It's possible that this is an IS NULL clause that's redundant
981 * with a lower antijoin; if so we can just discard it. We need
982 * not test in any of the other cases, because this will only be
983 * possible for pushed-down, delayed clauses.
985 if (check_redundant_nullability_qual(root, clause))
991 * Qual is not delayed by any lower outer-join restriction, so we
992 * can consider feeding it to the equivalence machinery. However,
993 * if it's itself within an outer-join clause, treat it as though
994 * it appeared below that outer join (note that we can only get
995 * here when the clause references only nullable-side rels).
997 maybe_equivalence = true;
998 if (outerjoin_nonnullable != NULL)
999 below_outer_join = true;
1003 * Since it doesn't mention the LHS, it's certainly not useful as a
1004 * set-aside OJ clause, even if it's in an OJ.
1006 maybe_outer_join = false;
1010 * Build the RestrictInfo node itself.
1012 restrictinfo = make_restrictinfo((Expr *) clause,
1020 * If it's a join clause (either naturally, or because delayed by
1021 * outer-join rules), add vars used in the clause to targetlists of their
1022 * relations, so that they will be emitted by the plan nodes that scan
1023 * those relations (else they won't be available at the join node!).
1025 * Note: if the clause gets absorbed into an EquivalenceClass then this
1026 * may be unnecessary, but for now we have to do it to cover the case
1027 * where the EC becomes ec_broken and we end up reinserting the original
1028 * clauses into the plan.
1030 if (bms_membership(relids) == BMS_MULTIPLE)
1032 List *vars = pull_var_clause(clause, PVC_INCLUDE_PLACEHOLDERS);
1034 add_vars_to_targetlist(root, vars, relids);
1039 * We check "mergejoinability" of every clause, not only join clauses,
1040 * because we want to know about equivalences between vars of the same
1041 * relation, or between vars and consts.
1043 check_mergejoinable(restrictinfo);
1046 * If it is a true equivalence clause, send it to the EquivalenceClass
1047 * machinery. We do *not* attach it directly to any restriction or join
1048 * lists. The EC code will propagate it to the appropriate places later.
1050 * If the clause has a mergejoinable operator and is not
1051 * outerjoin-delayed, yet isn't an equivalence because it is an outer-join
1052 * clause, the EC code may yet be able to do something with it. We add it
1053 * to appropriate lists for further consideration later. Specifically:
1055 * If it is a left or right outer-join qualification that relates the two
1056 * sides of the outer join (no funny business like leftvar1 = leftvar2 +
1057 * rightvar), we add it to root->left_join_clauses or
1058 * root->right_join_clauses according to which side the nonnullable
1059 * variable appears on.
1061 * If it is a full outer-join qualification, we add it to
1062 * root->full_join_clauses. (Ideally we'd discard cases that aren't
1063 * leftvar = rightvar, as we do for left/right joins, but this routine
1064 * doesn't have the info needed to do that; and the current usage of the
1065 * full_join_clauses list doesn't require that, so it's not currently
1066 * worth complicating this routine's API to make it possible.)
1068 * If none of the above hold, pass it off to
1069 * distribute_restrictinfo_to_rels().
1071 * In all cases, it's important to initialize the left_ec and right_ec
1072 * fields of a mergejoinable clause, so that all possibly mergejoinable
1073 * expressions have representations in EquivalenceClasses. If
1074 * process_equivalence is successful, it will take care of that;
1075 * otherwise, we have to call initialize_mergeclause_eclasses to do it.
1077 if (restrictinfo->mergeopfamilies)
1079 if (maybe_equivalence)
1081 if (process_equivalence(root, restrictinfo, below_outer_join))
1083 /* EC rejected it, so set left_ec/right_ec the hard way ... */
1084 initialize_mergeclause_eclasses(root, restrictinfo);
1085 /* ... and fall through to distribute_restrictinfo_to_rels */
1087 else if (maybe_outer_join && restrictinfo->can_join)
1089 /* we need to set up left_ec/right_ec the hard way */
1090 initialize_mergeclause_eclasses(root, restrictinfo);
1091 /* now see if it should go to any outer-join lists */
1092 if (bms_is_subset(restrictinfo->left_relids,
1093 outerjoin_nonnullable) &&
1094 !bms_overlap(restrictinfo->right_relids,
1095 outerjoin_nonnullable))
1097 /* we have outervar = innervar */
1098 root->left_join_clauses = lappend(root->left_join_clauses,
1102 if (bms_is_subset(restrictinfo->right_relids,
1103 outerjoin_nonnullable) &&
1104 !bms_overlap(restrictinfo->left_relids,
1105 outerjoin_nonnullable))
1107 /* we have innervar = outervar */
1108 root->right_join_clauses = lappend(root->right_join_clauses,
1112 if (jointype == JOIN_FULL)
1114 /* FULL JOIN (above tests cannot match in this case) */
1115 root->full_join_clauses = lappend(root->full_join_clauses,
1119 /* nope, so fall through to distribute_restrictinfo_to_rels */
1123 /* we still need to set up left_ec/right_ec */
1124 initialize_mergeclause_eclasses(root, restrictinfo);
1128 /* No EC special case applies, so push it into the clause lists */
1129 distribute_restrictinfo_to_rels(root, restrictinfo);
1133 * check_outerjoin_delay
1134 * Detect whether a qual referencing the given relids must be delayed
1135 * in application due to the presence of a lower outer join, and/or
1136 * may force extra delay of higher-level outer joins.
1138 * If the qual must be delayed, add relids to *relids_p to reflect the lowest
1139 * safe level for evaluating the qual, and return TRUE. Any extra delay for
1140 * higher-level joins is reflected by setting delay_upper_joins to TRUE in
1141 * SpecialJoinInfo structs. We also compute nullable_relids, the set of
1142 * referenced relids that are nullable by lower outer joins (note that this
1143 * can be nonempty even for a non-delayed qual).
1145 * For an is_pushed_down qual, we can evaluate the qual as soon as (1) we have
1146 * all the rels it mentions, and (2) we are at or above any outer joins that
1147 * can null any of these rels and are below the syntactic location of the
1148 * given qual. We must enforce (2) because pushing down such a clause below
1149 * the OJ might cause the OJ to emit null-extended rows that should not have
1150 * been formed, or that should have been rejected by the clause. (This is
1151 * only an issue for non-strict quals, since if we can prove a qual mentioning
1152 * only nullable rels is strict, we'd have reduced the outer join to an inner
1153 * join in reduce_outer_joins().)
1155 * To enforce (2), scan the join_info_list and merge the required-relid sets of
1156 * any such OJs into the clause's own reference list. At the time we are
1157 * called, the join_info_list contains only outer joins below this qual. We
1158 * have to repeat the scan until no new relids get added; this ensures that
1159 * the qual is suitably delayed regardless of the order in which OJs get
1160 * executed. As an example, if we have one OJ with LHS=A, RHS=B, and one with
1161 * LHS=B, RHS=C, it is implied that these can be done in either order; if the
1162 * B/C join is done first then the join to A can null C, so a qual actually
1163 * mentioning only C cannot be applied below the join to A.
1165 * For a non-pushed-down qual, this isn't going to determine where we place the
1166 * qual, but we need to determine outerjoin_delayed and nullable_relids anyway
1167 * for use later in the planning process.
1169 * Lastly, a pushed-down qual that references the nullable side of any current
1170 * join_info_list member and has to be evaluated above that OJ (because its
1171 * required relids overlap the LHS too) causes that OJ's delay_upper_joins
1172 * flag to be set TRUE. This will prevent any higher-level OJs from
1173 * being interchanged with that OJ, which would result in not having any
1174 * correct place to evaluate the qual. (The case we care about here is a
1175 * sub-select WHERE clause within the RHS of some outer join. The WHERE
1176 * clause must effectively be treated as a degenerate clause of that outer
1177 * join's condition. Rather than trying to match such clauses with joins
1178 * directly, we set delay_upper_joins here, and when the upper outer join
1179 * is processed by make_outerjoininfo, it will refrain from allowing the
1180 * two OJs to commute.)
1183 check_outerjoin_delay(PlannerInfo *root,
1184 Relids *relids_p, /* in/out parameter */
1185 Relids *nullable_relids_p, /* output parameter */
1186 bool is_pushed_down)
1189 Relids nullable_relids;
1190 bool outerjoin_delayed;
1193 /* fast path if no special joins */
1194 if (root->join_info_list == NIL)
1196 *nullable_relids_p = NULL;
1200 /* must copy relids because we need the original value at the end */
1201 relids = bms_copy(*relids_p);
1202 nullable_relids = NULL;
1203 outerjoin_delayed = false;
1209 foreach(l, root->join_info_list)
1211 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1213 /* do we reference any nullable rels of this OJ? */
1214 if (bms_overlap(relids, sjinfo->min_righthand) ||
1215 (sjinfo->jointype == JOIN_FULL &&
1216 bms_overlap(relids, sjinfo->min_lefthand)))
1218 /* yes; have we included all its rels in relids? */
1219 if (!bms_is_subset(sjinfo->min_lefthand, relids) ||
1220 !bms_is_subset(sjinfo->min_righthand, relids))
1222 /* no, so add them in */
1223 relids = bms_add_members(relids, sjinfo->min_lefthand);
1224 relids = bms_add_members(relids, sjinfo->min_righthand);
1225 outerjoin_delayed = true;
1226 /* we'll need another iteration */
1229 /* track all the nullable rels of relevant OJs */
1230 nullable_relids = bms_add_members(nullable_relids,
1231 sjinfo->min_righthand);
1232 if (sjinfo->jointype == JOIN_FULL)
1233 nullable_relids = bms_add_members(nullable_relids,
1234 sjinfo->min_lefthand);
1235 /* set delay_upper_joins if needed */
1236 if (is_pushed_down && sjinfo->jointype != JOIN_FULL &&
1237 bms_overlap(relids, sjinfo->min_lefthand))
1238 sjinfo->delay_upper_joins = true;
1241 } while (found_some);
1243 /* identify just the actually-referenced nullable rels */
1244 nullable_relids = bms_int_members(nullable_relids, *relids_p);
1246 /* replace *relids_p, and return nullable_relids */
1247 bms_free(*relids_p);
1249 *nullable_relids_p = nullable_relids;
1250 return outerjoin_delayed;
1254 * check_redundant_nullability_qual
1255 * Check to see if the qual is an IS NULL qual that is redundant with
1256 * a lower JOIN_ANTI join.
1258 * We want to suppress redundant IS NULL quals, not so much to save cycles
1259 * as to avoid generating bogus selectivity estimates for them. So if
1260 * redundancy is detected here, distribute_qual_to_rels() just throws away
1264 check_redundant_nullability_qual(PlannerInfo *root, Node *clause)
1266 Var *forced_null_var;
1267 Index forced_null_rel;
1270 /* Check for IS NULL, and identify the Var forced to NULL */
1271 forced_null_var = find_forced_null_var(clause);
1272 if (forced_null_var == NULL)
1274 forced_null_rel = forced_null_var->varno;
1277 * If the Var comes from the nullable side of a lower antijoin, the IS
1278 * NULL condition is necessarily true.
1280 foreach(lc, root->join_info_list)
1282 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
1284 if (sjinfo->jointype == JOIN_ANTI &&
1285 bms_is_member(forced_null_rel, sjinfo->syn_righthand))
1293 * distribute_restrictinfo_to_rels
1294 * Push a completed RestrictInfo into the proper restriction or join
1297 * This is the last step of distribute_qual_to_rels() for ordinary qual
1298 * clauses. Clauses that are interesting for equivalence-class processing
1299 * are diverted to the EC machinery, but may ultimately get fed back here.
1302 distribute_restrictinfo_to_rels(PlannerInfo *root,
1303 RestrictInfo *restrictinfo)
1305 Relids relids = restrictinfo->required_relids;
1308 switch (bms_membership(relids))
1313 * There is only one relation participating in the clause, so it
1314 * is a restriction clause for that relation.
1316 rel = find_base_rel(root, bms_singleton_member(relids));
1318 /* Add clause to rel's restriction list */
1319 rel->baserestrictinfo = lappend(rel->baserestrictinfo,
1325 * The clause is a join clause, since there is more than one rel
1330 * Check for hashjoinable operators. (We don't bother setting the
1331 * hashjoin info except in true join clauses.)
1333 check_hashjoinable(restrictinfo);
1336 * Add clause to the join lists of all the relevant relations.
1338 add_join_clause_to_rels(root, restrictinfo, relids);
1343 * clause references no rels, and therefore we have no place to
1344 * attach it. Shouldn't get here if callers are working properly.
1346 elog(ERROR, "cannot cope with variable-free clause");
1352 * process_implied_equality
1353 * Create a restrictinfo item that says "item1 op item2", and push it
1354 * into the appropriate lists. (In practice opno is always a btree
1355 * equality operator.)
1357 * "qualscope" is the nominal syntactic level to impute to the restrictinfo.
1358 * This must contain at least all the rels used in the expressions, but it
1359 * is used only to set the qual application level when both exprs are
1360 * variable-free. Otherwise the qual is applied at the lowest join level
1361 * that provides all its variables.
1363 * "both_const" indicates whether both items are known pseudo-constant;
1364 * in this case it is worth applying eval_const_expressions() in case we
1365 * can produce constant TRUE or constant FALSE. (Otherwise it's not,
1366 * because the expressions went through eval_const_expressions already.)
1368 * This is currently used only when an EquivalenceClass is found to
1369 * contain pseudoconstants. See path/pathkeys.c for more details.
1372 process_implied_equality(PlannerInfo *root,
1378 bool below_outer_join,
1384 * Build the new clause. Copy to ensure it shares no substructure with
1385 * original (this is necessary in case there are subselects in there...)
1387 clause = make_opclause(opno,
1388 BOOLOID, /* opresulttype */
1389 false, /* opretset */
1390 (Expr *) copyObject(item1),
1391 (Expr *) copyObject(item2),
1395 /* If both constant, try to reduce to a boolean constant. */
1398 clause = (Expr *) eval_const_expressions(root, (Node *) clause);
1400 /* If we produced const TRUE, just drop the clause */
1401 if (clause && IsA(clause, Const))
1403 Const *cclause = (Const *) clause;
1405 Assert(cclause->consttype == BOOLOID);
1406 if (!cclause->constisnull && DatumGetBool(cclause->constvalue))
1411 /* Make a copy of qualscope to avoid problems if source EC changes */
1412 qualscope = bms_copy(qualscope);
1415 * Push the new clause into all the appropriate restrictinfo lists.
1417 distribute_qual_to_rels(root, (Node *) clause,
1418 true, below_outer_join, JOIN_INNER,
1419 qualscope, NULL, NULL);
1423 * build_implied_join_equality --- build a RestrictInfo for a derived equality
1425 * This overlaps the functionality of process_implied_equality(), but we
1426 * must return the RestrictInfo, not push it into the joininfo tree.
1428 * Note: we do not do initialize_mergeclause_eclasses() here. It is
1429 * caller's responsibility that left_ec/right_ec be set as necessary.
1432 build_implied_join_equality(Oid opno,
1438 RestrictInfo *restrictinfo;
1442 * Build the new clause. Copy to ensure it shares no substructure with
1443 * original (this is necessary in case there are subselects in there...)
1445 clause = make_opclause(opno,
1446 BOOLOID, /* opresulttype */
1447 false, /* opretset */
1448 (Expr *) copyObject(item1),
1449 (Expr *) copyObject(item2),
1453 /* Make a copy of qualscope to avoid problems if source EC changes */
1454 qualscope = bms_copy(qualscope);
1457 * Build the RestrictInfo node itself.
1459 restrictinfo = make_restrictinfo(clause,
1460 true, /* is_pushed_down */
1461 false, /* outerjoin_delayed */
1462 false, /* pseudoconstant */
1463 qualscope, /* required_relids */
1464 NULL); /* nullable_relids */
1466 /* Set mergejoinability/hashjoinability flags */
1467 check_mergejoinable(restrictinfo);
1468 check_hashjoinable(restrictinfo);
1470 return restrictinfo;
1474 /*****************************************************************************
1476 * CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
1478 *****************************************************************************/
1481 * check_mergejoinable
1482 * If the restrictinfo's clause is mergejoinable, set the mergejoin
1483 * info fields in the restrictinfo.
1485 * Currently, we support mergejoin for binary opclauses where
1486 * the operator is a mergejoinable operator. The arguments can be
1487 * anything --- as long as there are no volatile functions in them.
1490 check_mergejoinable(RestrictInfo *restrictinfo)
1492 Expr *clause = restrictinfo->clause;
1496 if (restrictinfo->pseudoconstant)
1498 if (!is_opclause(clause))
1500 if (list_length(((OpExpr *) clause)->args) != 2)
1503 opno = ((OpExpr *) clause)->opno;
1504 leftarg = linitial(((OpExpr *) clause)->args);
1506 if (op_mergejoinable(opno, exprType(leftarg)) &&
1507 !contain_volatile_functions((Node *) clause))
1508 restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
1511 * Note: op_mergejoinable is just a hint; if we fail to find the operator
1512 * in any btree opfamilies, mergeopfamilies remains NIL and so the clause
1513 * is not treated as mergejoinable.
1518 * check_hashjoinable
1519 * If the restrictinfo's clause is hashjoinable, set the hashjoin
1520 * info fields in the restrictinfo.
1522 * Currently, we support hashjoin for binary opclauses where
1523 * the operator is a hashjoinable operator. The arguments can be
1524 * anything --- as long as there are no volatile functions in them.
1527 check_hashjoinable(RestrictInfo *restrictinfo)
1529 Expr *clause = restrictinfo->clause;
1533 if (restrictinfo->pseudoconstant)
1535 if (!is_opclause(clause))
1537 if (list_length(((OpExpr *) clause)->args) != 2)
1540 opno = ((OpExpr *) clause)->opno;
1541 leftarg = linitial(((OpExpr *) clause)->args);
1543 if (op_hashjoinable(opno, exprType(leftarg)) &&
1544 !contain_volatile_functions((Node *) clause))
1545 restrictinfo->hashjoinoperator = opno;