| blob | a8237af806744b91d7c0ba3c591c59485fba6d6e |
1 /*-------------------------------------------------------------------------
2 *
3 * prepjointree.c
4 * Planner preprocessing for subqueries and join tree manipulation.
5 *
6 * NOTE: the intended sequence for invoking these operations is
7 * pull_up_sublinks
8 * inline_set_returning_functions
9 * pull_up_subqueries
10 * do expression preprocessing (including flattening JOIN alias vars)
11 * reduce_outer_joins
12 *
13 *
14 * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
15 * Portions Copyright (c) 1994, Regents of the University of California
16 *
17 *
18 * IDENTIFICATION
19 * $PostgreSQL$
20 *
21 *-------------------------------------------------------------------------
22 */
38 {
73 Relids nonnullable_rels,
79 Relids subrelids);
83 /*
84 * pull_up_sublinks
85 * Attempt to pull up ANY and EXISTS SubLinks to be treated as
86 * semijoins or anti-semijoins.
87 *
88 * A clause "foo op ANY (sub-SELECT)" can be processed by pulling the
89 * sub-SELECT up to become a rangetable entry and treating the implied
90 * comparisons as quals of a semijoin. However, this optimization *only*
91 * works at the top level of WHERE or a JOIN/ON clause, because we cannot
92 * distinguish whether the ANY ought to return FALSE or NULL in cases
93 * involving NULL inputs. Also, in an outer join's ON clause we can only
94 * do this if the sublink is degenerate (ie, references only the nullable
95 * side of the join). In that case it is legal to push the semijoin
96 * down into the nullable side of the join. If the sublink references any
97 * nonnullable-side variables then it would have to be evaluated as part
98 * of the outer join, which makes things way too complicated.
99 *
100 * Under similar conditions, EXISTS and NOT EXISTS clauses can be handled
101 * by pulling up the sub-SELECT and creating a semijoin or anti-semijoin.
102 *
103 * This routine searches for such clauses and does the necessary parsetree
104 * transformations if any are found.
105 *
106 * This routine has to run before preprocess_expression(), so the quals
107 * clauses are not yet reduced to implicit-AND format. That means we need
108 * to recursively search through explicit AND clauses, which are
109 * probably only binary ANDs. We stop as soon as we hit a non-AND item.
110 */
111 void
113 {
115 Relids relids;
117 /* Begin recursion through the jointree */
122 /*
123 * root->parse->jointree must always be a FromExpr, so insert a dummy one
124 * if we got a bare RangeTblRef or JoinExpr out of the recursion.
125 */
128 else
130 }
132 /*
133 * Recurse through jointree nodes for pull_up_sublinks()
134 *
135 * In addition to returning the possibly-modified jointree node, we return
136 * a relids set of the contained rels into *relids.
137 */
141 {
143 {
145 }
147 {
151 /* jtnode is returned unmodified */
152 }
154 {
162 /* First, recurse to process children and collect their relids */
164 {
166 Relids childrelids;
173 }
174 /* Build the replacement FromExpr; no quals yet */
176 /* Set up a link representing the rebuilt jointree */
178 /* Now process qual --- all children are available for use */
182 /*
183 * Note that the result will be either newf, or a stack of JoinExprs
184 * with newf at the base. We rely on subsequent optimization steps to
185 * flatten this and rearrange the joins as needed.
186 *
187 * Although we could include the pulled-up subqueries in the returned
188 * relids, there's no need since upper quals couldn't refer to their
189 * outputs anyway.
190 */
193 }
195 {
197 Relids leftrelids;
198 Relids rightrelids;
201 /*
202 * Make a modifiable copy of join node, but don't bother copying its
203 * subnodes (yet).
204 */
209 /* Recurse to process children and collect their relids */
215 /*
216 * Now process qual, showing appropriate child relids as available,
217 * and attach any pulled-up jointree items at the right place. In the
218 * inner-join case we put new JoinExprs above the existing one (much
219 * as for a FromExpr-style join). In outer-join cases the new
220 * JoinExprs must go into the nullable side of the outer join. The
221 * point of the available_rels machinations is to ensure that we only
222 * pull up quals for which that's okay.
223 *
224 * XXX for the moment, we refrain from pulling up IN/EXISTS clauses
225 * appearing in LEFT or RIGHT join conditions. Although it is
226 * semantically valid to do so under the above conditions, we end up
227 * with a query in which the semijoin or antijoin must be evaluated
228 * below the outer join, which could perform far worse than leaving it
229 * as a sublink that is executed only for row pairs that meet the
230 * other join conditions. Fixing this seems to require considerable
231 * restructuring of the executor, but maybe someday it can happen.
232 *
233 * We don't expect to see any pre-existing JOIN_SEMI or JOIN_ANTI
234 * nodes here.
235 */
237 {
241 rightrelids),
247 rightrelids,
249 #endif
252 /* can't do anything with full-join quals */
257 leftrelids,
259 #endif
265 }
267 /*
268 * Although we could include the pulled-up subqueries in the returned
269 * relids, there's no need since upper quals couldn't refer to their
270 * outputs anyway. But we *do* need to include the join's own rtindex
271 * because we haven't yet collapsed join alias variables, so upper
272 * levels would mistakenly think they couldn't use references to this
273 * join.
274 */
279 }
280 else
284 }
286 /*
287 * Recurse through top-level qual nodes for pull_up_sublinks()
288 *
289 * jtlink points to the link in the jointree where any new JoinExprs should be
290 * inserted. If we find multiple pull-up-able SubLinks, they'll get stacked
291 * there in the order we encounter them. We rely on subsequent optimization
292 * to rearrange the stack if appropriate.
293 */
297 {
301 {
305 /* Is it a convertible ANY or EXISTS clause? */
307 {
309 available_rels);
311 {
312 /* Yes, insert the new join node into the join tree */
315 /* and return NULL representing constant TRUE */
317 }
318 }
320 {
322 available_rels);
324 {
325 /* Yes, insert the new join node into the join tree */
328 /* and return NULL representing constant TRUE */
330 }
331 }
332 /* Else return it unmodified */
334 }
336 {
337 /* If the immediate argument of NOT is EXISTS, try to convert */
342 {
344 {
346 available_rels);
348 {
349 /* Yes, insert the new join node into the join tree */
352 /* and return NULL representing constant TRUE */
354 }
355 }
356 }
357 /* Else return it unmodified */
359 }
361 {
362 /* Recurse into AND clause */
367 {
372 oldclause,
373 available_rels,
374 jtlink);
377 }
378 /* We might have got back fewer clauses than we started with */
383 else
385 }
386 /* Stop if not an AND */
388 }
390 /*
391 * inline_set_returning_functions
392 * Attempt to "inline" set-returning functions in the FROM clause.
393 *
394 * If an RTE_FUNCTION rtable entry invokes a set-returning function that
395 * contains just a simple SELECT, we can convert the rtable entry to an
396 * RTE_SUBQUERY entry exposing the SELECT directly. This is especially
397 * useful if the subquery can then be "pulled up" for further optimization,
398 * but we do it even if not, to reduce executor overhead.
399 *
400 * This has to be done before we have started to do any optimization of
401 * subqueries, else any such steps wouldn't get applied to subqueries
402 * obtained via inlining. However, we do it after pull_up_sublinks
403 * so that we can inline any functions used in SubLink subselects.
404 *
405 * Like most of the planner, this feels free to scribble on its input data
406 * structure.
407 */
408 void
410 {
414 {
418 {
421 /* Check safety of expansion, and expand if possible */
424 {
425 /* Successful expansion, replace the rtable entry */
431 }
432 }
433 }
434 }
436 /*
437 * pull_up_subqueries
438 * Look for subqueries in the rangetable that can be pulled up into
439 * the parent query. If the subquery has no special features like
440 * grouping/aggregation then we can merge it into the parent's jointree.
441 * Also, subqueries that are simple UNION ALL structures can be
442 * converted into "append relations".
443 *
444 * If this jointree node is within the nullable side of an outer join, then
445 * lowest_outer_join references the lowest such JoinExpr node; otherwise it
446 * is NULL. This forces use of the PlaceHolderVar mechanism for references
447 * to non-nullable targetlist items, but only for references above that join.
448 *
449 * If we are looking at a member subquery of an append relation,
450 * containing_appendrel describes that relation; else it is NULL.
451 * This forces use of the PlaceHolderVar mechanism for all non-Var targetlist
452 * items, and puts some additional restrictions on what can be pulled up.
453 *
454 * A tricky aspect of this code is that if we pull up a subquery we have
455 * to replace Vars that reference the subquery's outputs throughout the
456 * parent query, including quals attached to jointree nodes above the one
457 * we are currently processing! We handle this by being careful not to
458 * change the jointree structure while recursing: no nodes other than
459 * subquery RangeTblRef entries will be replaced. Also, we can't turn
460 * ResolveNew loose on the whole jointree, because it'll return a mutated
461 * copy of the tree; we have to invoke it just on the quals, instead.
462 * This behavior is what makes it reasonable to pass lowest_outer_join as a
463 * pointer rather than some more-indirect way of identifying the lowest OJ.
464 * Likewise, we don't replace append_rel_list members but only their
465 * substructure, so the containing_appendrel reference is safe to use.
466 */
467 Node *
471 {
475 {
479 /*
480 * Is this a subquery RTE, and if so, is the subquery simple enough to
481 * pull up?
482 *
483 * If we are looking at an append-relation member, we can't pull it up
484 * unless is_safe_append_member says so.
485 */
491 lowest_outer_join,
492 containing_appendrel);
494 /*
495 * Alternatively, is it a simple UNION ALL subquery? If so, flatten
496 * into an "append relation".
497 *
498 * It's safe to do this regardless of whether this query is itself an
499 * appendrel member. (If you're thinking we should try to flatten the
500 * two levels of appendrel together, you're right; but we handle that
501 * in set_append_rel_pathlist, not here.)
502 */
507 /* Otherwise, do nothing at this node. */
508 }
510 {
518 }
520 {
524 /* Recurse, being careful to tell myself when inside outer join */
526 {
557 }
558 }
559 else
563 }
565 /*
566 * pull_up_simple_subquery
567 * Attempt to pull up a single simple subquery.
568 *
569 * jtnode is a RangeTblRef that has been tentatively identified as a simple
570 * subquery by pull_up_subqueries. We return the replacement jointree node,
571 * or jtnode itself if we determine that the subquery can't be pulled up after
572 * all.
573 *
574 * rte is the RangeTblEntry referenced by jtnode. Remaining parameters are
575 * as for pull_up_subqueries.
576 */
581 {
591 /*
592 * Need a modifiable copy of the subquery to hack on. Even if we didn't
593 * sometimes choose not to pull up below, we must do this to avoid
594 * problems if the same subquery is referenced from multiple jointree
595 * items (which can't happen normally, but might after rule rewriting).
596 */
599 /*
600 * Create a PlannerInfo data structure for this subquery.
601 *
602 * NOTE: the next few steps should match the first processing in
603 * subquery_planner(). Can we refactor to avoid code duplication, or
604 * would that just make things uglier?
605 */
620 /* No CTEs to worry about */
623 /*
624 * Pull up any SubLinks within the subquery's quals, so that we don't
625 * leave unoptimized SubLinks behind.
626 */
630 /*
631 * Similarly, inline any set-returning functions in its rangetable.
632 */
635 /*
636 * Recursively pull up the subquery's subqueries, so that
637 * pull_up_subqueries' processing is complete for its jointree and
638 * rangetable.
639 *
640 * Note: we should pass NULL for containing-join info even if we are
641 * within an outer join in the upper query; the lower query starts with a
642 * clean slate for outer-join semantics. Likewise, we say we aren't
643 * handling an appendrel member.
644 */
648 /*
649 * Now we must recheck whether the subquery is still simple enough to pull
650 * up. If not, abandon processing it.
651 *
652 * We don't really need to recheck all the conditions involved, but it's
653 * easier just to keep this "if" looking the same as the one in
654 * pull_up_subqueries.
655 */
658 {
659 /* good to go */
660 }
661 else
662 {
663 /*
664 * Give up, return unmodified RangeTblRef.
665 *
666 * Note: The work we just did will be redone when the subquery gets
667 * planned on its own. Perhaps we could avoid that by storing the
668 * modified subquery back into the rangetable, but I'm not gonna risk
669 * it now.
670 */
672 }
674 /*
675 * Adjust level-0 varnos in subquery so that we can append its rangetable
676 * to upper query's. We have to fix the subquery's append_rel_list as
677 * well.
678 */
683 /*
684 * Upper-level vars in subquery are now one level closer to their parent
685 * than before.
686 */
690 /*
691 * The subquery's targetlist items are now in the appropriate form to
692 * insert into the top query, but if we are under an outer join then
693 * non-nullable items may have to be turned into PlaceHolderVars. If we
694 * are dealing with an appendrel member then anything that's not a simple
695 * Var has to be turned into a PlaceHolderVar.
696 */
700 subtlist,
701 varno,
703 else
706 /*
707 * Replace all of the top query's references to the subquery's outputs
708 * with copies of the adjusted subtlist items, being careful not to
709 * replace any of the jointree structure. (This'd be a lot cleaner if we
710 * could use query_tree_mutator.) We have to use PHVs in the targetList,
711 * returningList, and havingQual, since those are certainly above any
712 * outer join. resolvenew_in_jointree tracks its location in the jointree
713 * and uses PHVs or not appropriately.
714 */
725 lowest_outer_join);
732 /*
733 * Replace references in the translated_vars lists of appendrels. When
734 * pulling up an appendrel member, we do not need PHVs in the list of the
735 * parent appendrel --- there isn't any outer join between. Elsewhere, use
736 * PHVs for safety. (This analysis could be made tighter but it seems
737 * unlikely to be worth much trouble.)
738 */
740 {
749 }
751 /*
752 * Replace references in the joinaliasvars lists of join RTEs.
753 *
754 * You might think that we could avoid using PHVs for alias vars of joins
755 * below lowest_outer_join, but that doesn't work because the alias vars
756 * could be referenced above that join; we need the PHVs to be present in
757 * such references after the alias vars get flattened. (It might be worth
758 * trying to be smarter here, someday.)
759 */
761 {
769 }
771 /*
772 * Now append the adjusted rtable entries to upper query. (We hold off
773 * until after fixing the upper rtable entries; no point in running that
774 * code on the subquery ones too.)
775 */
778 /*
779 * Pull up any FOR UPDATE/SHARE markers, too. (OffsetVarNodes already
780 * adjusted the marker rtindexes, so just concat the lists.)
781 */
784 /*
785 * We also have to fix the relid sets of any PlaceHolderVar nodes in the
786 * parent query. (This could perhaps be done by ResolveNew, but it would
787 * clutter that routine's API unreasonably.) Note in particular that any
788 * PlaceHolderVar nodes just created by insert_targetlist_placeholders()
789 * will be adjusted, so having created them with the subquery's varno is
790 * correct.
791 *
792 * Likewise, relids appearing in AppendRelInfo nodes have to be fixed. We
793 * already checked that this won't require introducing multiple subrelids
794 * into the single-slot AppendRelInfo structs.
795 */
798 {
799 Relids subrelids;
804 }
806 /*
807 * And now add subquery's AppendRelInfos to our list.
808 */
812 /*
813 * We don't have to do the equivalent bookkeeping for outer-join info,
814 * because that hasn't been set up yet. placeholder_list likewise.
815 */
821 /*
822 * Miscellaneous housekeeping.
823 */
826 /*
827 * subquery won't be pulled up if it hasAggs or hasWindowFuncs, so no work
828 * needed on those flags
829 */
831 /*
832 * Return the adjusted subquery jointree to replace the RangeTblRef entry
833 * in parent's jointree.
834 */
836 }
838 /*
839 * pull_up_simple_union_all
840 * Pull up a single simple UNION ALL subquery.
841 *
842 * jtnode is a RangeTblRef that has been identified as a simple UNION ALL
843 * subquery by pull_up_subqueries. We pull up the leaf subqueries and
844 * build an "append relation" for the union set. The result value is just
845 * jtnode, since we don't actually need to change the query jointree.
846 */
849 {
855 /*
856 * Append the subquery rtable entries to upper query.
857 */
860 /*
861 * Append child RTEs to parent rtable.
862 *
863 * Upper-level vars in subquery are now one level closer to their parent
864 * than before. We don't have to worry about offsetting varnos, though,
865 * because any such vars must refer to stuff above the level of the query
866 * we are pulling into.
867 */
872 /*
873 * Recursively scan the subquery's setOperations tree and add
874 * AppendRelInfo nodes for leaf subqueries to the parent's
875 * append_rel_list.
876 */
879 rtoffset);
881 /*
882 * Mark the parent as an append relation.
883 */
887 }
889 /*
890 * pull_up_union_leaf_queries -- recursive guts of pull_up_simple_union_all
891 *
892 * Note that setOpQuery is the Query containing the setOp node, whose rtable
893 * is where to look up the RTE if setOp is a RangeTblRef. This is *not* the
894 * same as root->parse, which is the top-level Query we are pulling up into.
895 *
896 * parentRTindex is the appendrel parent's index in root->parse->rtable.
897 *
898 * The child RTEs have already been copied to the parent. childRToffset
899 * tells us where in the parent's range table they were copied.
900 */
901 static void
904 {
906 {
911 /*
912 * Calculate the index in the parent's range table
913 */
916 /*
917 * Build a suitable AppendRelInfo, and attach to parent's list.
918 */
929 /*
930 * Recursively apply pull_up_subqueries to the new child RTE. (We
931 * must build the AppendRelInfo first, because this will modify it.)
932 * Note that we can pass NULL for containing-join info even if we're
933 * actually under an outer join, because the child's expressions
934 * aren't going to propagate up above the join.
935 */
939 }
941 {
944 /* Recurse to reach leaf queries */
946 childRToffset);
948 childRToffset);
949 }
950 else
951 {
954 }
955 }
957 /*
958 * make_setop_translation_list
959 * Build the list of translations from parent Vars to child Vars for
960 * a UNION ALL member. (At this point it's just a simple list of
961 * referencing Vars, but if we succeed in pulling up the member
962 * subquery, the Vars will get replaced by pulled-up expressions.)
963 */
964 static void
967 {
972 {
983 }
986 }
988 /*
989 * is_simple_subquery
990 * Check a subquery in the range table to see if it's simple enough
991 * to pull up into the parent query.
992 */
993 static bool
995 {
996 /*
997 * Let's just make sure it's a valid subselect ...
998 */
1005 /*
1006 * Can't currently pull up a query with setops (unless it's simple UNION
1007 * ALL, which is handled by a different code path). Maybe after querytree
1008 * redesign...
1009 */
1013 /*
1014 * Can't pull up a subquery involving grouping, aggregation, sorting,
1015 * limiting, or WITH. (XXX WITH could possibly be allowed later)
1016 */
1028 /*
1029 * Don't pull up a subquery that has any set-returning functions in its
1030 * targetlist. Otherwise we might well wind up inserting set-returning
1031 * functions into places where they mustn't go, such as quals of higher
1032 * queries.
1033 */
1037 /*
1038 * Don't pull up a subquery that has any volatile functions in its
1039 * targetlist. Otherwise we might introduce multiple evaluations of these
1040 * functions, if they get copied to multiple places in the upper query,
1041 * leading to surprising results. (Note: the PlaceHolderVar mechanism
1042 * doesn't quite guarantee single evaluation; else we could pull up anyway
1043 * and just wrap such items in PlaceHolderVars ...)
1044 */
1048 /*
1049 * Hack: don't try to pull up a subquery with an empty jointree.
1050 * query_planner() will correctly generate a Result plan for a jointree
1051 * that's totally empty, but I don't think the right things happen if an
1052 * empty FromExpr appears lower down in a jointree. It would pose a
1053 * problem for the PlaceHolderVar mechanism too, since we'd have no way to
1054 * identify where to evaluate a PHV coming out of the subquery. Not worth
1055 * working hard on this, just to collapse SubqueryScan/Result into Result;
1056 * especially since the SubqueryScan can often be optimized away by
1057 * setrefs.c anyway.
1058 */
1063 }
1065 /*
1066 * is_simple_union_all
1067 * Check a subquery to see if it's a simple UNION ALL.
1068 *
1069 * We require all the setops to be UNION ALL (no mixing) and there can't be
1070 * any datatype coercions involved, ie, all the leaf queries must emit the
1071 * same datatypes.
1072 */
1073 static bool
1075 {
1078 /* Let's just make sure it's a valid subselect ... */
1085 /* Is it a set-operation query at all? */
1091 /* Can't handle ORDER BY, LIMIT/OFFSET, locking, or WITH */
1099 /* Recursively check the tree of set operations */
1102 }
1104 static bool
1106 {
1108 {
1115 /* Leaf nodes are OK if they match the toplevel column types */
1116 /* We don't have to compare typmods here */
1118 }
1120 {
1123 /* Must be UNION ALL */
1127 /* Recurse to check inputs */
1130 }
1131 else
1132 {
1136 }
1137 }
1139 /*
1140 * insert_targetlist_placeholders
1141 * Insert PlaceHolderVar nodes into any non-junk targetlist items that are
1142 * not simple variables or strict functions of simple variables (and hence
1143 * might not correctly go to NULL when examined above the point of an outer
1144 * join).
1145 *
1146 * varno is the upper-query relid of the subquery; this is used as the
1147 * syntactic location of the PlaceHolderVars.
1148 * If wrap_non_vars is true then *only* simple Var references escape being
1149 * wrapped with PlaceHolderVars.
1150 */
1154 {
1159 {
1163 /* resjunk columns need not be changed */
1165 {
1168 }
1170 /*
1171 * Simple Vars always escape being wrapped. This is common enough to
1172 * deserve a fast path even if we aren't doing wrap_non_vars.
1173 */
1176 {
1179 }
1182 {
1183 /*
1184 * If it contains a Var of current level, and does not contain any
1185 * non-strict constructs, then it's certainly nullable and we
1186 * don't need to insert a PlaceHolderVar. (Note: in future maybe
1187 * we should insert PlaceHolderVars anyway, when a tlist item is
1188 * expensive to evaluate?
1189 */
1192 {
1195 }
1196 }
1198 /* Else wrap it in a PlaceHolderVar */
1206 }
1208 }
1210 /*
1211 * is_safe_append_member
1212 * Check a subquery that is a leaf of a UNION ALL appendrel to see if it's
1213 * safe to pull up.
1214 */
1215 static bool
1217 {
1220 /*
1221 * It's only safe to pull up the child if its jointree contains exactly
1222 * one RTE, else the AppendRelInfo data structure breaks. The one base RTE
1223 * could be buried in several levels of FromExpr, however.
1224 *
1225 * Also, the child can't have any WHERE quals because there's no place to
1226 * put them in an appendrel. (This is a bit annoying...) If we didn't
1227 * need to check this, we'd just test whether get_relids_in_jointree()
1228 * yields a singleton set, to be more consistent with the coding of
1229 * fix_append_rel_relids().
1230 */
1233 {
1239 }
1244 }
1246 /*
1247 * Helper routine for pull_up_subqueries: do ResolveNew on every expression
1248 * in the jointree, without changing the jointree structure itself. Ugly,
1249 * but there's no other way...
1250 *
1251 * If we are above lowest_outer_join then use subtlist_with_phvs; at or
1252 * below it, use subtlist. (When no outer joins are in the picture,
1253 * these will be the same list.)
1254 */
1255 static void
1259 {
1263 {
1264 /* nothing to do here */
1265 }
1267 {
1274 lowest_outer_join);
1278 }
1280 {
1284 {
1285 /* no more PHVs in or below this join */
1288 }
1291 lowest_outer_join);
1294 lowest_outer_join);
1299 /*
1300 * We don't bother to update the colvars list, since it won't be used
1301 * again ...
1302 */
1303 }
1304 else
1307 }
1309 /*
1310 * reduce_outer_joins
1311 * Attempt to reduce outer joins to plain inner joins.
1312 *
1313 * The idea here is that given a query like
1314 * SELECT ... FROM a LEFT JOIN b ON (...) WHERE b.y = 42;
1315 * we can reduce the LEFT JOIN to a plain JOIN if the "=" operator in WHERE
1316 * is strict. The strict operator will always return NULL, causing the outer
1317 * WHERE to fail, on any row where the LEFT JOIN filled in NULLs for b's
1318 * columns. Therefore, there's no need for the join to produce null-extended
1319 * rows in the first place --- which makes it a plain join not an outer join.
1320 * (This scenario may not be very likely in a query written out by hand, but
1321 * it's reasonably likely when pushing quals down into complex views.)
1322 *
1323 * More generally, an outer join can be reduced in strength if there is a
1324 * strict qual above it in the qual tree that constrains a Var from the
1325 * nullable side of the join to be non-null. (For FULL joins this applies
1326 * to each side separately.)
1327 *
1328 * Another transformation we apply here is to recognize cases like
1329 * SELECT ... FROM a LEFT JOIN b ON (a.x = b.y) WHERE b.y IS NULL;
1330 * If the join clause is strict for b.y, then only null-extended rows could
1331 * pass the upper WHERE, and we can conclude that what the query is really
1332 * specifying is an anti-semijoin. We change the join type from JOIN_LEFT
1333 * to JOIN_ANTI. The IS NULL clause then becomes redundant, and must be
1334 * removed to prevent bogus selectivity calculations, but we leave it to
1335 * distribute_qual_to_rels to get rid of such clauses.
1336 *
1337 * Also, we get rid of JOIN_RIGHT cases by flipping them around to become
1338 * JOIN_LEFT. This saves some code here and in some later planner routines,
1339 * but the main reason to do it is to not need to invent a JOIN_REVERSE_ANTI
1340 * join type.
1341 *
1342 * To ease recognition of strict qual clauses, we require this routine to be
1343 * run after expression preprocessing (i.e., qual canonicalization and JOIN
1344 * alias-var expansion).
1345 */
1346 void
1348 {
1351 /*
1352 * To avoid doing strictness checks on more quals than necessary, we want
1353 * to stop descending the jointree as soon as there are no outer joins
1354 * below our current point. This consideration forces a two-pass process.
1355 * The first pass gathers information about which base rels appear below
1356 * each side of each join clause, and about whether there are outer
1357 * join(s) below each side of each join clause. The second pass examines
1358 * qual clauses and changes join types as it descends the tree.
1359 */
1362 /* planner.c shouldn't have called me if no outer joins */
1368 }
1370 /*
1371 * reduce_outer_joins_pass1 - phase 1 data collection
1372 *
1373 * Returns a state node describing the given jointree node.
1374 */
1377 {
1389 {
1393 }
1395 {
1400 {
1408 }
1409 }
1411 {
1415 /* join's own RT index is not wanted in result->relids */
1430 }
1431 else
1435 }
1437 /*
1438 * reduce_outer_joins_pass2 - phase 2 processing
1439 *
1440 * jtnode: current jointree node
1441 * state: state data collected by phase 1 for this node
1442 * root: toplevel planner state
1443 * nonnullable_rels: set of base relids forced non-null by upper quals
1444 * nonnullable_vars: list of Vars forced non-null by upper quals
1445 * forced_null_vars: list of Vars forced null by upper quals
1446 */
1447 static void
1451 Relids nonnullable_rels,
1454 {
1455 /*
1456 * pass 2 should never descend as far as an empty subnode or base rel,
1457 * because it's only called on subtrees marked as contains_outer.
1458 */
1464 {
1468 Relids pass_nonnullable_rels;
1472 /* Scan quals to see if we can add any constraints */
1475 nonnullable_rels);
1476 /* NB: we rely on list_concat to not damage its second argument */
1479 nonnullable_vars);
1482 forced_null_vars);
1483 /* And recurse --- but only into interesting subtrees */
1486 {
1491 pass_nonnullable_rels,
1492 pass_nonnullable_vars,
1493 pass_forced_null_vars);
1494 }
1496 /* can't so easily clean up var lists, unfortunately */
1497 }
1499 {
1508 /* Can we simplify this join? */
1510 {
1523 {
1526 else
1528 }
1529 else
1530 {
1533 }
1538 /*
1539 * These could only have been introduced by pull_up_sublinks,
1540 * so there's no way that upper quals could refer to their
1541 * righthand sides, and no point in checking.
1542 */
1548 }
1550 /*
1551 * Convert JOIN_RIGHT to JOIN_LEFT. Note that in the case where we
1552 * reduced JOIN_FULL to JOIN_RIGHT, this will mean the JoinExpr no
1553 * longer matches the internal ordering of any CoalesceExpr's built to
1554 * represent merged join variables. We don't care about that at
1555 * present, but be wary of it ...
1556 */
1558 {
1567 }
1569 /*
1570 * See if we can reduce JOIN_LEFT to JOIN_ANTI. This is the case if
1571 * the join's own quals are strict for any var that was forced null by
1572 * higher qual levels. NOTE: there are other ways that we could
1573 * detect an anti-join, in particular if we were to check whether Vars
1574 * coming from the RHS must be non-null because of table constraints.
1575 * That seems complicated and expensive though (in particular, one
1576 * would have to be wary of lower outer joins). For the moment this
1577 * seems sufficient.
1578 */
1580 {
1586 /*
1587 * It's not sufficient to check whether local_nonnullable_vars and
1588 * forced_null_vars overlap: we need to know if the overlap
1589 * includes any RHS variables.
1590 */
1592 forced_null_vars);
1597 }
1599 /* Apply the jointype change, if any, to both jointree node and RTE */
1601 {
1607 }
1610 /* Only recurse if there's more to do below here */
1612 {
1613 Relids local_nonnullable_rels;
1615 Relids pass_nonnullable_rels;
1619 /*
1620 * If this join is (now) inner, we can add any constraints its
1621 * quals provide to those we got from above. But if it is outer,
1622 * we can pass down the local constraints only into the nullable
1623 * side, because an outer join never eliminates any rows from its
1624 * non-nullable side. Also, there is no point in passing upper
1625 * constraints into the nullable side, since if there were any
1626 * we'd have been able to reduce the join. (In the case of upper
1627 * forced-null constraints, we *must not* pass them into the
1628 * nullable side --- they either applied here, or not.) The upshot
1629 * is that we pass either the local or the upper constraints,
1630 * never both, to the children of an outer join.
1631 *
1632 * At a FULL join we just punt and pass nothing down --- is it
1633 * possible to be smarter?
1634 */
1636 {
1642 {
1643 /* OK to merge upper and local constraints */
1645 nonnullable_rels);
1647 nonnullable_vars);
1649 forced_null_vars);
1650 }
1651 }
1652 else
1653 {
1654 /* no use in calculating these */
1657 }
1660 {
1662 {
1663 /* pass union of local and upper constraints */
1667 }
1669 {
1670 /* can't pass local constraints to non-nullable side */
1674 }
1675 else
1676 {
1677 /* no constraints pass through JOIN_FULL */
1681 }
1683 pass_nonnullable_rels,
1684 pass_nonnullable_vars,
1685 pass_forced_null_vars);
1686 }
1689 {
1691 {
1692 /* pass appropriate constraints, per comment above */
1696 }
1697 else
1698 {
1699 /* no constraints pass through JOIN_FULL */
1703 }
1705 pass_nonnullable_rels,
1706 pass_nonnullable_vars,
1707 pass_forced_null_vars);
1708 }
1710 }
1711 }
1712 else
1715 }
1717 /*
1718 * substitute_multiple_relids - adjust node relid sets after pulling up
1719 * a subquery
1720 *
1721 * Find any PlaceHolderVar nodes in the given tree that reference the
1722 * pulled-up relid, and change them to reference the replacement relid(s).
1723 * We do not need to recurse into subqueries, since no subquery of the current
1724 * top query could (yet) contain such a reference.
1725 *
1726 * NOTE: although this has the form of a walker, we cheat and modify the
1727 * nodes in-place. This should be OK since the tree was copied by ResolveNew
1728 * earlier. Avoid scribbling on the original values of the bitmapsets, though,
1729 * because expression_tree_mutator doesn't copy those.
1730 */
1733 {
1735 Relids subrelids;
1738 static bool
1741 {
1745 {
1749 {
1754 }
1755 /* fall through to examine children */
1756 }
1757 /* Shouldn't need to handle planner auxiliary nodes here */
1764 }
1766 static void
1768 {
1769 substitute_multiple_relids_context context;
1774 /*
1775 * Must be prepared to start with a Query or a bare expression tree.
1776 */
1778 substitute_multiple_relids_walker,
1781 }
1783 /*
1784 * fix_append_rel_relids: update RT-index fields of AppendRelInfo nodes
1785 *
1786 * When we pull up a subquery, any AppendRelInfo references to the subquery's
1787 * RT index have to be replaced by the substituted relid (and there had better
1788 * be only one). We also need to apply substitute_multiple_relids to their
1789 * translated_vars lists, since those might contain PlaceHolderVars.
1790 *
1791 * We assume we may modify the AppendRelInfo nodes in-place.
1792 */
1793 static void
1795 {
1799 /*
1800 * We only want to extract the member relid once, but we mustn't fail
1801 * immediately if there are multiple members; it could be that none of the
1802 * AppendRelInfo nodes refer to it. So compute it on first use. Note that
1803 * bms_singleton_member will complain if set is not singleton.
1804 */
1806 {
1809 /* The parent_relid shouldn't ever be a pullup target */
1813 {
1817 }
1819 /* Also finish fixups for its translated vars */
1822 }
1823 }
1825 /*
1826 * get_relids_in_jointree: get set of RT indexes present in a jointree
1827 *
1828 * If include_joins is true, join RT indexes are included; if false,
1829 * only base rels are included.
1830 */
1831 Relids
1833 {
1839 {
1843 }
1845 {
1850 {
1853 include_joins));
1854 }
1855 }
1857 {
1865 }
1866 else
1870 }
1872 /*
1873 * get_relids_for_join: get set of base RT indexes making up a join
1874 */
1875 Relids
1877 {
1881 joinrelid);
1885 }
1887 /*
1888 * find_jointree_node_for_rel: locate jointree node for a base or join RT index
1889 *
1890 * Returns NULL if not found
1891 */
1894 {
1898 {
1903 }
1905 {
1910 {
1914 }
1915 }
1917 {
1928 }
1929 else
1933 }