1 /*-------------------------------------------------------------------------
2 *
3 * initsplan.c
4 * Target list, qualification, joininfo initialization routines
5 *
6 * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/optimizer/plan/initsplan.c
12 *
13 *-------------------------------------------------------------------------
14 */
15 #include "postgres.h"
16
17 #include "catalog/pg_type.h"
18 #include "nodes/nodeFuncs.h"
19 #include "optimizer/clauses.h"
20 #include "optimizer/cost.h"
21 #include "optimizer/joininfo.h"
22 #include "optimizer/pathnode.h"
23 #include "optimizer/paths.h"
24 #include "optimizer/placeholder.h"
25 #include "optimizer/planmain.h"
26 #include "optimizer/planner.h"
27 #include "optimizer/prep.h"
28 #include "optimizer/restrictinfo.h"
29 #include "optimizer/var.h"
30 #include "parser/analyze.h"
31 #include "rewrite/rewriteManip.h"
32 #include "utils/lsyscache.h"
33
34
35 /* These parameters are set by GUC */
36 int from_collapse_limit;
37 int join_collapse_limit;
38
39
40 /* Elements of the postponed_qual_list used during deconstruct_recurse */
41 typedef struct PostponedQual
42 {
43 Node *qual; /* a qual clause waiting to be processed */
44 Relids relids; /* the set of baserels it references */
45 } PostponedQual;
46
47
48 static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel,
49 Index rtindex);
50 static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
51 bool below_outer_join,
52 Relids *qualscope, Relids *inner_join_rels,
53 List **postponed_qual_list);
54 static void process_security_barrier_quals(PlannerInfo *root,
55 int rti, Relids qualscope,
56 bool below_outer_join);
57 static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root,
58 Relids left_rels, Relids right_rels,
59 Relids inner_join_rels,
60 JoinType jointype, List *clause);
61 static void compute_semijoin_info(SpecialJoinInfo *sjinfo, List *clause);
62 static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
63 bool is_deduced,
64 bool below_outer_join,
65 JoinType jointype,
66 Index security_level,
67 Relids qualscope,
68 Relids ojscope,
69 Relids outerjoin_nonnullable,
70 Relids deduced_nullable_relids,
71 List **postponed_qual_list);
72 static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p,
73 Relids *nullable_relids_p, bool is_pushed_down);
74 static bool check_equivalence_delay(PlannerInfo *root,
75 RestrictInfo *restrictinfo);
76 static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause);
77 static void check_mergejoinable(RestrictInfo *restrictinfo);
78 static void check_hashjoinable(RestrictInfo *restrictinfo);
79
80
81 /*****************************************************************************
82 *
83 * JOIN TREES
84 *
85 *****************************************************************************/
86
87 /*
88 * add_base_rels_to_query
89 *
90 * Scan the query's jointree and create baserel RelOptInfos for all
91 * the base relations (ie, table, subquery, and function RTEs)
92 * appearing in the jointree.
93 *
94 * The initial invocation must pass root->parse->jointree as the value of
95 * jtnode. Internally, the function recurses through the jointree.
96 *
97 * At the end of this process, there should be one baserel RelOptInfo for
98 * every non-join RTE that is used in the query. Therefore, this routine
99 * is the only place that should call build_simple_rel with reloptkind
100 * RELOPT_BASEREL. (Note: build_simple_rel recurses internally to build
101 * "other rel" RelOptInfos for the members of any appendrels we find here.)
102 */
103 void
add_base_rels_to_query(PlannerInfo * root,Node * jtnode)104 add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
105 {
106 if (jtnode == NULL)
107 return;
108 if (IsA(jtnode, RangeTblRef))
109 {
110 int varno = ((RangeTblRef *) jtnode)->rtindex;
111
112 (void) build_simple_rel(root, varno, NULL);
113 }
114 else if (IsA(jtnode, FromExpr))
115 {
116 FromExpr *f = (FromExpr *) jtnode;
117 ListCell *l;
118
119 foreach(l, f->fromlist)
120 add_base_rels_to_query(root, lfirst(l));
121 }
122 else if (IsA(jtnode, JoinExpr))
123 {
124 JoinExpr *j = (JoinExpr *) jtnode;
125
126 add_base_rels_to_query(root, j->larg);
127 add_base_rels_to_query(root, j->rarg);
128 }
129 else
130 elog(ERROR, "unrecognized node type: %d",
131 (int) nodeTag(jtnode));
132 }
133
134
135 /*****************************************************************************
136 *
137 * TARGET LISTS
138 *
139 *****************************************************************************/
140
141 /*
142 * build_base_rel_tlists
143 * Add targetlist entries for each var needed in the query's final tlist
144 * (and HAVING clause, if any) to the appropriate base relations.
145 *
146 * We mark such vars as needed by "relation 0" to ensure that they will
147 * propagate up through all join plan steps.
148 */
149 void
build_base_rel_tlists(PlannerInfo * root,List * final_tlist)150 build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
151 {
152 List *tlist_vars = pull_var_clause((Node *) final_tlist,
153 PVC_RECURSE_AGGREGATES |
154 PVC_RECURSE_WINDOWFUNCS |
155 PVC_INCLUDE_PLACEHOLDERS);
156
157 if (tlist_vars != NIL)
158 {
159 add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0), true);
160 list_free(tlist_vars);
161 }
162
163 /*
164 * If there's a HAVING clause, we'll need the Vars it uses, too. Note
165 * that HAVING can contain Aggrefs but not WindowFuncs.
166 */
167 if (root->parse->havingQual)
168 {
169 List *having_vars = pull_var_clause(root->parse->havingQual,
170 PVC_RECURSE_AGGREGATES |
171 PVC_INCLUDE_PLACEHOLDERS);
172
173 if (having_vars != NIL)
174 {
175 add_vars_to_targetlist(root, having_vars,
176 bms_make_singleton(0), true);
177 list_free(having_vars);
178 }
179 }
180 }
181
182 /*
183 * add_vars_to_targetlist
184 * For each variable appearing in the list, add it to the owning
185 * relation's targetlist if not already present, and mark the variable
186 * as being needed for the indicated join (or for final output if
187 * where_needed includes "relation 0").
188 *
189 * The list may also contain PlaceHolderVars. These don't necessarily
190 * have a single owning relation; we keep their attr_needed info in
191 * root->placeholder_list instead. If create_new_ph is true, it's OK
192 * to create new PlaceHolderInfos; otherwise, the PlaceHolderInfos must
193 * already exist, and we should only update their ph_needed. (This should
194 * be true before deconstruct_jointree begins, and false after that.)
195 */
196 void
add_vars_to_targetlist(PlannerInfo * root,List * vars,Relids where_needed,bool create_new_ph)197 add_vars_to_targetlist(PlannerInfo *root, List *vars,
198 Relids where_needed, bool create_new_ph)
199 {
200 ListCell *temp;
201
202 Assert(!bms_is_empty(where_needed));
203
204 foreach(temp, vars)
205 {
206 Node *node = (Node *) lfirst(temp);
207
208 if (IsA(node, Var))
209 {
210 Var *var = (Var *) node;
211 RelOptInfo *rel = find_base_rel(root, var->varno);
212 int attno = var->varattno;
213
214 if (bms_is_subset(where_needed, rel->relids))
215 continue;
216 Assert(attno >= rel->min_attr && attno <= rel->max_attr);
217 attno -= rel->min_attr;
218 if (rel->attr_needed[attno] == NULL)
219 {
220 /* Variable not yet requested, so add to rel's targetlist */
221 /* XXX is copyObject necessary here? */
222 rel->reltarget->exprs = lappend(rel->reltarget->exprs,
223 copyObject(var));
224 /* reltarget cost and width will be computed later */
225 }
226 rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno],
227 where_needed);
228 }
229 else if (IsA(node, PlaceHolderVar))
230 {
231 PlaceHolderVar *phv = (PlaceHolderVar *) node;
232 PlaceHolderInfo *phinfo = find_placeholder_info(root, phv,
233 create_new_ph);
234
235 phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
236 where_needed);
237 }
238 else
239 elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
240 }
241 }
242
243
244 /*****************************************************************************
245 *
246 * LATERAL REFERENCES
247 *
248 *****************************************************************************/
249
250 /*
251 * find_lateral_references
252 * For each LATERAL subquery, extract all its references to Vars and
253 * PlaceHolderVars of the current query level, and make sure those values
254 * will be available for evaluation of the subquery.
255 *
256 * While later planning steps ensure that the Var/PHV source rels are on the
257 * outside of nestloops relative to the LATERAL subquery, we also need to
258 * ensure that the Vars/PHVs propagate up to the nestloop join level; this
259 * means setting suitable where_needed values for them.
260 *
261 * Note that this only deals with lateral references in unflattened LATERAL
262 * subqueries. When we flatten a LATERAL subquery, its lateral references
263 * become plain Vars in the parent query, but they may have to be wrapped in
264 * PlaceHolderVars if they need to be forced NULL by outer joins that don't
265 * also null the LATERAL subquery. That's all handled elsewhere.
266 *
267 * This has to run before deconstruct_jointree, since it might result in
268 * creation of PlaceHolderInfos.
269 */
270 void
find_lateral_references(PlannerInfo * root)271 find_lateral_references(PlannerInfo *root)
272 {
273 Index rti;
274
275 /* We need do nothing if the query contains no LATERAL RTEs */
276 if (!root->hasLateralRTEs)
277 return;
278
279 /*
280 * Examine all baserels (the rel array has been set up by now).
281 */
282 for (rti = 1; rti < root->simple_rel_array_size; rti++)
283 {
284 RelOptInfo *brel = root->simple_rel_array[rti];
285
286 /* there may be empty slots corresponding to non-baserel RTEs */
287 if (brel == NULL)
288 continue;
289
290 Assert(brel->relid == rti); /* sanity check on array */
291
292 /*
293 * This bit is less obvious than it might look. We ignore appendrel
294 * otherrels and consider only their parent baserels. In a case where
295 * a LATERAL-containing UNION ALL subquery was pulled up, it is the
296 * otherrel that is actually going to be in the plan. However, we
297 * want to mark all its lateral references as needed by the parent,
298 * because it is the parent's relid that will be used for join
299 * planning purposes. And the parent's RTE will contain all the
300 * lateral references we need to know, since the pulled-up member is
301 * nothing but a copy of parts of the original RTE's subquery. We
302 * could visit the parent's children instead and transform their
303 * references back to the parent's relid, but it would be much more
304 * complicated for no real gain. (Important here is that the child
305 * members have not yet received any processing beyond being pulled
306 * up.) Similarly, in appendrels created by inheritance expansion,
307 * it's sufficient to look at the parent relation.
308 */
309
310 /* ignore RTEs that are "other rels" */
311 if (brel->reloptkind != RELOPT_BASEREL)
312 continue;
313
314 extract_lateral_references(root, brel, rti);
315 }
316 }
317
318 static void
extract_lateral_references(PlannerInfo * root,RelOptInfo * brel,Index rtindex)319 extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex)
320 {
321 RangeTblEntry *rte = root->simple_rte_array[rtindex];
322 List *vars;
323 List *newvars;
324 Relids where_needed;
325 ListCell *lc;
326
327 /* No cross-references are possible if it's not LATERAL */
328 if (!rte->lateral)
329 return;
330
331 /* Fetch the appropriate variables */
332 if (rte->rtekind == RTE_RELATION)
333 vars = pull_vars_of_level((Node *) rte->tablesample, 0);
334 else if (rte->rtekind == RTE_SUBQUERY)
335 vars = pull_vars_of_level((Node *) rte->subquery, 1);
336 else if (rte->rtekind == RTE_FUNCTION)
337 vars = pull_vars_of_level((Node *) rte->functions, 0);
338 else if (rte->rtekind == RTE_TABLEFUNC)
339 vars = pull_vars_of_level((Node *) rte->tablefunc, 0);
340 else if (rte->rtekind == RTE_VALUES)
341 vars = pull_vars_of_level((Node *) rte->values_lists, 0);
342 else
343 {
344 Assert(false);
345 return; /* keep compiler quiet */
346 }
347
348 if (vars == NIL)
349 return; /* nothing to do */
350
351 /* Copy each Var (or PlaceHolderVar) and adjust it to match our level */
352 newvars = NIL;
353 foreach(lc, vars)
354 {
355 Node *node = (Node *) lfirst(lc);
356
357 node = copyObject(node);
358 if (IsA(node, Var))
359 {
360 Var *var = (Var *) node;
361
362 /* Adjustment is easy since it's just one node */
363 var->varlevelsup = 0;
364 }
365 else if (IsA(node, PlaceHolderVar))
366 {
367 PlaceHolderVar *phv = (PlaceHolderVar *) node;
368 int levelsup = phv->phlevelsup;
369
370 /* Have to work harder to adjust the contained expression too */
371 if (levelsup != 0)
372 IncrementVarSublevelsUp(node, -levelsup, 0);
373
374 /*
375 * If we pulled the PHV out of a subquery RTE, its expression
376 * needs to be preprocessed. subquery_planner() already did this
377 * for level-zero PHVs in function and values RTEs, though.
378 */
379 if (levelsup > 0)
380 phv->phexpr = preprocess_phv_expression(root, phv->phexpr);
381 }
382 else
383 Assert(false);
384 newvars = lappend(newvars, node);
385 }
386
387 list_free(vars);
388
389 /*
390 * We mark the Vars as being "needed" at the LATERAL RTE. This is a bit
391 * of a cheat: a more formal approach would be to mark each one as needed
392 * at the join of the LATERAL RTE with its source RTE. But it will work,
393 * and it's much less tedious than computing a separate where_needed for
394 * each Var.
395 */
396 where_needed = bms_make_singleton(rtindex);
397
398 /*
399 * Push Vars into their source relations' targetlists, and PHVs into
400 * root->placeholder_list.
401 */
402 add_vars_to_targetlist(root, newvars, where_needed, true);
403
404 /* Remember the lateral references for create_lateral_join_info */
405 brel->lateral_vars = newvars;
406 }
407
408 /*
409 * create_lateral_join_info
410 * Fill in the per-base-relation direct_lateral_relids, lateral_relids
411 * and lateral_referencers sets.
412 *
413 * This has to run after deconstruct_jointree, because we need to know the
414 * final ph_eval_at values for PlaceHolderVars.
415 */
416 void
create_lateral_join_info(PlannerInfo * root)417 create_lateral_join_info(PlannerInfo *root)
418 {
419 bool found_laterals = false;
420 Relids prev_parents PG_USED_FOR_ASSERTS_ONLY = NULL;
421 Index rti;
422 ListCell *lc;
423
424 /* We need do nothing if the query contains no LATERAL RTEs */
425 if (!root->hasLateralRTEs)
426 return;
427
428 /*
429 * Examine all baserels (the rel array has been set up by now).
430 */
431 for (rti = 1; rti < root->simple_rel_array_size; rti++)
432 {
433 RelOptInfo *brel = root->simple_rel_array[rti];
434 Relids lateral_relids;
435
436 /* there may be empty slots corresponding to non-baserel RTEs */
437 if (brel == NULL)
438 continue;
439
440 Assert(brel->relid == rti); /* sanity check on array */
441
442 /* ignore RTEs that are "other rels" */
443 if (brel->reloptkind != RELOPT_BASEREL)
444 continue;
445
446 lateral_relids = NULL;
447
448 /* consider each laterally-referenced Var or PHV */
449 foreach(lc, brel->lateral_vars)
450 {
451 Node *node = (Node *) lfirst(lc);
452
453 if (IsA(node, Var))
454 {
455 Var *var = (Var *) node;
456
457 found_laterals = true;
458 lateral_relids = bms_add_member(lateral_relids,
459 var->varno);
460 }
461 else if (IsA(node, PlaceHolderVar))
462 {
463 PlaceHolderVar *phv = (PlaceHolderVar *) node;
464 PlaceHolderInfo *phinfo = find_placeholder_info(root, phv,
465 false);
466
467 found_laterals = true;
468 lateral_relids = bms_add_members(lateral_relids,
469 phinfo->ph_eval_at);
470 }
471 else
472 Assert(false);
473 }
474
475 /* We now have all the simple lateral refs from this rel */
476 brel->direct_lateral_relids = lateral_relids;
477 brel->lateral_relids = bms_copy(lateral_relids);
478 }
479
480 /*
481 * Now check for lateral references within PlaceHolderVars, and mark their
482 * eval_at rels as having lateral references to the source rels.
483 *
484 * For a PHV that is due to be evaluated at a baserel, mark its source(s)
485 * as direct lateral dependencies of the baserel (adding onto the ones
486 * recorded above). If it's due to be evaluated at a join, mark its
487 * source(s) as indirect lateral dependencies of each baserel in the join,
488 * ie put them into lateral_relids but not direct_lateral_relids. This is
489 * appropriate because we can't put any such baserel on the outside of a
490 * join to one of the PHV's lateral dependencies, but on the other hand we
491 * also can't yet join it directly to the dependency.
492 */
493 foreach(lc, root->placeholder_list)
494 {
495 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
496 Relids eval_at = phinfo->ph_eval_at;
497 int varno;
498
499 if (phinfo->ph_lateral == NULL)
500 continue; /* PHV is uninteresting if no lateral refs */
501
502 found_laterals = true;
503
504 if (bms_get_singleton_member(eval_at, &varno))
505 {
506 /* Evaluation site is a baserel */
507 RelOptInfo *brel = find_base_rel(root, varno);
508
509 brel->direct_lateral_relids =
510 bms_add_members(brel->direct_lateral_relids,
511 phinfo->ph_lateral);
512 brel->lateral_relids =
513 bms_add_members(brel->lateral_relids,
514 phinfo->ph_lateral);
515 }
516 else
517 {
518 /* Evaluation site is a join */
519 varno = -1;
520 while ((varno = bms_next_member(eval_at, varno)) >= 0)
521 {
522 RelOptInfo *brel = find_base_rel(root, varno);
523
524 brel->lateral_relids = bms_add_members(brel->lateral_relids,
525 phinfo->ph_lateral);
526 }
527 }
528 }
529
530 /*
531 * If we found no actual lateral references, we're done; but reset the
532 * hasLateralRTEs flag to avoid useless work later.
533 */
534 if (!found_laterals)
535 {
536 root->hasLateralRTEs = false;
537 return;
538 }
539
540 /*
541 * Calculate the transitive closure of the lateral_relids sets, so that
542 * they describe both direct and indirect lateral references. If relation
543 * X references Y laterally, and Y references Z laterally, then we will
544 * have to scan X on the inside of a nestloop with Z, so for all intents
545 * and purposes X is laterally dependent on Z too.
546 *
547 * This code is essentially Warshall's algorithm for transitive closure.
548 * The outer loop considers each baserel, and propagates its lateral
549 * dependencies to those baserels that have a lateral dependency on it.
550 */
551 for (rti = 1; rti < root->simple_rel_array_size; rti++)
552 {
553 RelOptInfo *brel = root->simple_rel_array[rti];
554 Relids outer_lateral_relids;
555 Index rti2;
556
557 if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
558 continue;
559
560 /* need not consider baserel further if it has no lateral refs */
561 outer_lateral_relids = brel->lateral_relids;
562 if (outer_lateral_relids == NULL)
563 continue;
564
565 /* else scan all baserels */
566 for (rti2 = 1; rti2 < root->simple_rel_array_size; rti2++)
567 {
568 RelOptInfo *brel2 = root->simple_rel_array[rti2];
569
570 if (brel2 == NULL || brel2->reloptkind != RELOPT_BASEREL)
571 continue;
572
573 /* if brel2 has lateral ref to brel, propagate brel's refs */
574 if (bms_is_member(rti, brel2->lateral_relids))
575 brel2->lateral_relids = bms_add_members(brel2->lateral_relids,
576 outer_lateral_relids);
577 }
578 }
579
580 /*
581 * Now that we've identified all lateral references, mark each baserel
582 * with the set of relids of rels that reference it laterally (possibly
583 * indirectly) --- that is, the inverse mapping of lateral_relids.
584 */
585 for (rti = 1; rti < root->simple_rel_array_size; rti++)
586 {
587 RelOptInfo *brel = root->simple_rel_array[rti];
588 Relids lateral_relids;
589 int rti2;
590
591 if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
592 continue;
593
594 /* Nothing to do at rels with no lateral refs */
595 lateral_relids = brel->lateral_relids;
596 if (lateral_relids == NULL)
597 continue;
598
599 /*
600 * We should not have broken the invariant that lateral_relids is
601 * exactly NULL if empty.
602 */
603 Assert(!bms_is_empty(lateral_relids));
604
605 /* Also, no rel should have a lateral dependency on itself */
606 Assert(!bms_is_member(rti, lateral_relids));
607
608 /* Mark this rel's referencees */
609 rti2 = -1;
610 while ((rti2 = bms_next_member(lateral_relids, rti2)) >= 0)
611 {
612 RelOptInfo *brel2 = root->simple_rel_array[rti2];
613
614 Assert(brel2 != NULL && brel2->reloptkind == RELOPT_BASEREL);
615 brel2->lateral_referencers =
616 bms_add_member(brel2->lateral_referencers, rti);
617 }
618 }
619
620 /*
621 * Lastly, propagate lateral_relids and lateral_referencers from appendrel
622 * parent rels to their child rels. We intentionally give each child rel
623 * the same minimum parameterization, even though it's quite possible that
624 * some don't reference all the lateral rels. This is because any append
625 * path for the parent will have to have the same parameterization for
626 * every child anyway, and there's no value in forcing extra
627 * reparameterize_path() calls. Similarly, a lateral reference to the
628 * parent prevents use of otherwise-movable join rels for each child.
629 *
630 * It's possible for child rels to have their own children, in which case
631 * the topmost parent's lateral info must be propagated all the way down.
632 * This code handles that case correctly so long as append_rel_list has
633 * entries for child relationships before grandchild relationships, which
634 * is an okay assumption right now, but we'll need to be careful to
635 * preserve it. The assertions below check for incorrect ordering.
636 */
637 foreach(lc, root->append_rel_list)
638 {
639 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
640 RelOptInfo *parentrel = root->simple_rel_array[appinfo->parent_relid];
641 RelOptInfo *childrel = root->simple_rel_array[appinfo->child_relid];
642
643 /*
644 * If we're processing a subquery of a query with inherited target rel
645 * (cf. inheritance_planner), append_rel_list may contain entries for
646 * tables that are not part of the current subquery and hence have no
647 * RelOptInfo. Ignore them. We can ignore dead rels, too.
648 */
649 if (parentrel == NULL || !IS_SIMPLE_REL(parentrel))
650 continue;
651
652 /* Verify that children are processed before grandchildren */
653 #ifdef USE_ASSERT_CHECKING
654 prev_parents = bms_add_member(prev_parents, appinfo->parent_relid);
655 Assert(!bms_is_member(appinfo->child_relid, prev_parents));
656 #endif
657
658 /* OK, propagate info down */
659 Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
660 Assert(childrel->direct_lateral_relids == NULL);
661 childrel->direct_lateral_relids = parentrel->direct_lateral_relids;
662 Assert(childrel->lateral_relids == NULL);
663 childrel->lateral_relids = parentrel->lateral_relids;
664 Assert(childrel->lateral_referencers == NULL);
665 childrel->lateral_referencers = parentrel->lateral_referencers;
666 }
667 }
668
669
670 /*****************************************************************************
671 *
672 * JOIN TREE PROCESSING
673 *
674 *****************************************************************************/
675
676 /*
677 * deconstruct_jointree
678 * Recursively scan the query's join tree for WHERE and JOIN/ON qual
679 * clauses, and add these to the appropriate restrictinfo and joininfo
680 * lists belonging to base RelOptInfos. Also, add SpecialJoinInfo nodes
681 * to root->join_info_list for any outer joins appearing in the query tree.
682 * Return a "joinlist" data structure showing the join order decisions
683 * that need to be made by make_one_rel().
684 *
685 * The "joinlist" result is a list of items that are either RangeTblRef
686 * jointree nodes or sub-joinlists. All the items at the same level of
687 * joinlist must be joined in an order to be determined by make_one_rel()
688 * (note that legal orders may be constrained by SpecialJoinInfo nodes).
689 * A sub-joinlist represents a subproblem to be planned separately. Currently
690 * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
691 * subproblems is stopped by join_collapse_limit or from_collapse_limit.
692 *
693 * NOTE: when dealing with inner joins, it is appropriate to let a qual clause
694 * be evaluated at the lowest level where all the variables it mentions are
695 * available. However, we cannot push a qual down into the nullable side(s)
696 * of an outer join since the qual might eliminate matching rows and cause a
697 * NULL row to be incorrectly emitted by the join. Therefore, we artificially
698 * OR the minimum-relids of such an outer join into the required_relids of
699 * clauses appearing above it. This forces those clauses to be delayed until
700 * application of the outer join (or maybe even higher in the join tree).
701 */
702 List *
deconstruct_jointree(PlannerInfo * root)703 deconstruct_jointree(PlannerInfo *root)
704 {
705 List *result;
706 Relids qualscope;
707 Relids inner_join_rels;
708 List *postponed_qual_list = NIL;
709
710 /* Start recursion at top of jointree */
711 Assert(root->parse->jointree != NULL &&
712 IsA(root->parse->jointree, FromExpr));
713
714 /* this is filled as we scan the jointree */
715 root->nullable_baserels = NULL;
716
717 result = deconstruct_recurse(root, (Node *) root->parse->jointree, false,
718 &qualscope, &inner_join_rels,
719 &postponed_qual_list);
720
721 /* Shouldn't be any leftover quals */
722 Assert(postponed_qual_list == NIL);
723
724 return result;
725 }
726
727 /*
728 * deconstruct_recurse
729 * One recursion level of deconstruct_jointree processing.
730 *
731 * Inputs:
732 * jtnode is the jointree node to examine
733 * below_outer_join is TRUE if this node is within the nullable side of a
734 * higher-level outer join
735 * Outputs:
736 * *qualscope gets the set of base Relids syntactically included in this
737 * jointree node (do not modify or free this, as it may also be pointed
738 * to by RestrictInfo and SpecialJoinInfo nodes)
739 * *inner_join_rels gets the set of base Relids syntactically included in
740 * inner joins appearing at or below this jointree node (do not modify
741 * or free this, either)
742 * *postponed_qual_list is a list of PostponedQual structs, which we can
743 * add quals to if they turn out to belong to a higher join level
744 * Return value is the appropriate joinlist for this jointree node
745 *
746 * In addition, entries will be added to root->join_info_list for outer joins.
747 */
748 static List *
deconstruct_recurse(PlannerInfo * root,Node * jtnode,bool below_outer_join,Relids * qualscope,Relids * inner_join_rels,List ** postponed_qual_list)749 deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
750 Relids *qualscope, Relids *inner_join_rels,
751 List **postponed_qual_list)
752 {
753 List *joinlist;
754
755 if (jtnode == NULL)
756 {
757 *qualscope = NULL;
758 *inner_join_rels = NULL;
759 return NIL;
760 }
761 if (IsA(jtnode, RangeTblRef))
762 {
763 int varno = ((RangeTblRef *) jtnode)->rtindex;
764
765 /* qualscope is just the one RTE */
766 *qualscope = bms_make_singleton(varno);
767 /* Deal with any securityQuals attached to the RTE */
768 if (root->qual_security_level > 0)
769 process_security_barrier_quals(root,
770 varno,
771 *qualscope,
772 below_outer_join);
773 /* A single baserel does not create an inner join */
774 *inner_join_rels = NULL;
775 joinlist = list_make1(jtnode);
776 }
777 else if (IsA(jtnode, FromExpr))
778 {
779 FromExpr *f = (FromExpr *) jtnode;
780 List *child_postponed_quals = NIL;
781 int remaining;
782 ListCell *l;
783
784 /*
785 * First, recurse to handle child joins. We collapse subproblems into
786 * a single joinlist whenever the resulting joinlist wouldn't exceed
787 * from_collapse_limit members. Also, always collapse one-element
788 * subproblems, since that won't lengthen the joinlist anyway.
789 */
790 *qualscope = NULL;
791 *inner_join_rels = NULL;
792 joinlist = NIL;
793 remaining = list_length(f->fromlist);
794 foreach(l, f->fromlist)
795 {
796 Relids sub_qualscope;
797 List *sub_joinlist;
798 int sub_members;
799
800 sub_joinlist = deconstruct_recurse(root, lfirst(l),
801 below_outer_join,
802 &sub_qualscope,
803 inner_join_rels,
804 &child_postponed_quals);
805 *qualscope = bms_add_members(*qualscope, sub_qualscope);
806 sub_members = list_length(sub_joinlist);
807 remaining--;
808 if (sub_members <= 1 ||
809 list_length(joinlist) + sub_members + remaining <= from_collapse_limit)
810 joinlist = list_concat(joinlist, sub_joinlist);
811 else
812 joinlist = lappend(joinlist, sub_joinlist);
813 }
814
815 /*
816 * A FROM with more than one list element is an inner join subsuming
817 * all below it, so we should report inner_join_rels = qualscope. If
818 * there was exactly one element, we should (and already did) report
819 * whatever its inner_join_rels were. If there were no elements (is
820 * that possible?) the initialization before the loop fixed it.
821 */
822 if (list_length(f->fromlist) > 1)
823 *inner_join_rels = *qualscope;
824
825 /*
826 * Try to process any quals postponed by children. If they need
827 * further postponement, add them to my output postponed_qual_list.
828 */
829 foreach(l, child_postponed_quals)
830 {
831 PostponedQual *pq = (PostponedQual *) lfirst(l);
832
833 if (bms_is_subset(pq->relids, *qualscope))
834 distribute_qual_to_rels(root, pq->qual,
835 false, below_outer_join, JOIN_INNER,
836 root->qual_security_level,
837 *qualscope, NULL, NULL, NULL,
838 NULL);
839 else
840 *postponed_qual_list = lappend(*postponed_qual_list, pq);
841 }
842
843 /*
844 * Now process the top-level quals.
845 */
846 foreach(l, (List *) f->quals)
847 {
848 Node *qual = (Node *) lfirst(l);
849
850 distribute_qual_to_rels(root, qual,
851 false, below_outer_join, JOIN_INNER,
852 root->qual_security_level,
853 *qualscope, NULL, NULL, NULL,
854 postponed_qual_list);
855 }
856 }
857 else if (IsA(jtnode, JoinExpr))
858 {
859 JoinExpr *j = (JoinExpr *) jtnode;
860 List *child_postponed_quals = NIL;
861 Relids leftids,
862 rightids,
863 left_inners,
864 right_inners,
865 nonnullable_rels,
866 nullable_rels,
867 ojscope;
868 List *leftjoinlist,
869 *rightjoinlist;
870 List *my_quals;
871 SpecialJoinInfo *sjinfo;
872 ListCell *l;
873
874 /*
875 * Order of operations here is subtle and critical. First we recurse
876 * to handle sub-JOINs. Their join quals will be placed without
877 * regard for whether this level is an outer join, which is correct.
878 * Then we place our own join quals, which are restricted by lower
879 * outer joins in any case, and are forced to this level if this is an
880 * outer join and they mention the outer side. Finally, if this is an
881 * outer join, we create a join_info_list entry for the join. This
882 * will prevent quals above us in the join tree that use those rels
883 * from being pushed down below this level. (It's okay for upper
884 * quals to be pushed down to the outer side, however.)
885 */
886 switch (j->jointype)
887 {
888 case JOIN_INNER:
889 leftjoinlist = deconstruct_recurse(root, j->larg,
890 below_outer_join,
891 &leftids, &left_inners,
892 &child_postponed_quals);
893 rightjoinlist = deconstruct_recurse(root, j->rarg,
894 below_outer_join,
895 &rightids, &right_inners,
896 &child_postponed_quals);
897 *qualscope = bms_union(leftids, rightids);
898 *inner_join_rels = *qualscope;
899 /* Inner join adds no restrictions for quals */
900 nonnullable_rels = NULL;
901 /* and it doesn't force anything to null, either */
902 nullable_rels = NULL;
903 break;
904 case JOIN_LEFT:
905 case JOIN_ANTI:
906 leftjoinlist = deconstruct_recurse(root, j->larg,
907 below_outer_join,
908 &leftids, &left_inners,
909 &child_postponed_quals);
910 rightjoinlist = deconstruct_recurse(root, j->rarg,
911 true,
912 &rightids, &right_inners,
913 &child_postponed_quals);
914 *qualscope = bms_union(leftids, rightids);
915 *inner_join_rels = bms_union(left_inners, right_inners);
916 nonnullable_rels = leftids;
917 nullable_rels = rightids;
918 break;
919 case JOIN_SEMI:
920 leftjoinlist = deconstruct_recurse(root, j->larg,
921 below_outer_join,
922 &leftids, &left_inners,
923 &child_postponed_quals);
924 rightjoinlist = deconstruct_recurse(root, j->rarg,
925 below_outer_join,
926 &rightids, &right_inners,
927 &child_postponed_quals);
928 *qualscope = bms_union(leftids, rightids);
929 *inner_join_rels = bms_union(left_inners, right_inners);
930 /* Semi join adds no restrictions for quals */
931 nonnullable_rels = NULL;
932
933 /*
934 * Theoretically, a semijoin would null the RHS; but since the
935 * RHS can't be accessed above the join, this is immaterial
936 * and we needn't account for it.
937 */
938 nullable_rels = NULL;
939 break;
940 case JOIN_FULL:
941 leftjoinlist = deconstruct_recurse(root, j->larg,
942 true,
943 &leftids, &left_inners,
944 &child_postponed_quals);
945 rightjoinlist = deconstruct_recurse(root, j->rarg,
946 true,
947 &rightids, &right_inners,
948 &child_postponed_quals);
949 *qualscope = bms_union(leftids, rightids);
950 *inner_join_rels = bms_union(left_inners, right_inners);
951 /* each side is both outer and inner */
952 nonnullable_rels = *qualscope;
953 nullable_rels = *qualscope;
954 break;
955 default:
956 /* JOIN_RIGHT was eliminated during reduce_outer_joins() */
957 elog(ERROR, "unrecognized join type: %d",
958 (int) j->jointype);
959 nonnullable_rels = NULL; /* keep compiler quiet */
960 nullable_rels = NULL;
961 leftjoinlist = rightjoinlist = NIL;
962 break;
963 }
964
965 /* Report all rels that will be nulled anywhere in the jointree */
966 root->nullable_baserels = bms_add_members(root->nullable_baserels,
967 nullable_rels);
968
969 /*
970 * Try to process any quals postponed by children. If they need
971 * further postponement, add them to my output postponed_qual_list.
972 * Quals that can be processed now must be included in my_quals, so
973 * that they'll be handled properly in make_outerjoininfo.
974 */
975 my_quals = NIL;
976 foreach(l, child_postponed_quals)
977 {
978 PostponedQual *pq = (PostponedQual *) lfirst(l);
979
980 if (bms_is_subset(pq->relids, *qualscope))
981 my_quals = lappend(my_quals, pq->qual);
982 else
983 {
984 /*
985 * We should not be postponing any quals past an outer join.
986 * If this Assert fires, pull_up_subqueries() messed up.
987 */
988 Assert(j->jointype == JOIN_INNER);
989 *postponed_qual_list = lappend(*postponed_qual_list, pq);
990 }
991 }
992 /* list_concat is nondestructive of its second argument */
993 my_quals = list_concat(my_quals, (List *) j->quals);
994
995 /*
996 * For an OJ, form the SpecialJoinInfo now, because we need the OJ's
997 * semantic scope (ojscope) to pass to distribute_qual_to_rels. But
998 * we mustn't add it to join_info_list just yet, because we don't want
999 * distribute_qual_to_rels to think it is an outer join below us.
1000 *
1001 * Semijoins are a bit of a hybrid: we build a SpecialJoinInfo, but we
1002 * want ojscope = NULL for distribute_qual_to_rels.
1003 */
1004 if (j->jointype != JOIN_INNER)
1005 {
1006 sjinfo = make_outerjoininfo(root,
1007 leftids, rightids,
1008 *inner_join_rels,
1009 j->jointype,
1010 my_quals);
1011 if (j->jointype == JOIN_SEMI)
1012 ojscope = NULL;
1013 else
1014 ojscope = bms_union(sjinfo->min_lefthand,
1015 sjinfo->min_righthand);
1016 }
1017 else
1018 {
1019 sjinfo = NULL;
1020 ojscope = NULL;
1021 }
1022
1023 /* Process the JOIN's qual clauses */
1024 foreach(l, my_quals)
1025 {
1026 Node *qual = (Node *) lfirst(l);
1027
1028 distribute_qual_to_rels(root, qual,
1029 false, below_outer_join, j->jointype,
1030 root->qual_security_level,
1031 *qualscope,
1032 ojscope, nonnullable_rels, NULL,
1033 postponed_qual_list);
1034 }
1035
1036 /* Now we can add the SpecialJoinInfo to join_info_list */
1037 if (sjinfo)
1038 {
1039 root->join_info_list = lappend(root->join_info_list, sjinfo);
1040 /* Each time we do that, recheck placeholder eval levels */
1041 update_placeholder_eval_levels(root, sjinfo);
1042 }
1043
1044 /*
1045 * Finally, compute the output joinlist. We fold subproblems together
1046 * except at a FULL JOIN or where join_collapse_limit would be
1047 * exceeded.
1048 */
1049 if (j->jointype == JOIN_FULL)
1050 {
1051 /* force the join order exactly at this node */
1052 joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
1053 }
1054 else if (list_length(leftjoinlist) + list_length(rightjoinlist) <=
1055 join_collapse_limit)
1056 {
1057 /* OK to combine subproblems */
1058 joinlist = list_concat(leftjoinlist, rightjoinlist);
1059 }
1060 else
1061 {
1062 /* can't combine, but needn't force join order above here */
1063 Node *leftpart,
1064 *rightpart;
1065
1066 /* avoid creating useless 1-element sublists */
1067 if (list_length(leftjoinlist) == 1)
1068 leftpart = (Node *) linitial(leftjoinlist);
1069 else
1070 leftpart = (Node *) leftjoinlist;
1071 if (list_length(rightjoinlist) == 1)
1072 rightpart = (Node *) linitial(rightjoinlist);
1073 else
1074 rightpart = (Node *) rightjoinlist;
1075 joinlist = list_make2(leftpart, rightpart);
1076 }
1077 }
1078 else
1079 {
1080 elog(ERROR, "unrecognized node type: %d",
1081 (int) nodeTag(jtnode));
1082 joinlist = NIL; /* keep compiler quiet */
1083 }
1084 return joinlist;
1085 }
1086
1087 /*
1088 * process_security_barrier_quals
1089 * Transfer security-barrier quals into relation's baserestrictinfo list.
1090 *
1091 * The rewriter put any relevant security-barrier conditions into the RTE's
1092 * securityQuals field, but it's now time to copy them into the rel's
1093 * baserestrictinfo.
1094 *
1095 * In inheritance cases, we only consider quals attached to the parent rel
1096 * here; they will be valid for all children too, so it's okay to consider
1097 * them for purposes like equivalence class creation. Quals attached to
1098 * individual child rels will be dealt with during path creation.
1099 */
1100 static void
process_security_barrier_quals(PlannerInfo * root,int rti,Relids qualscope,bool below_outer_join)1101 process_security_barrier_quals(PlannerInfo *root,
1102 int rti, Relids qualscope,
1103 bool below_outer_join)
1104 {
1105 RangeTblEntry *rte = root->simple_rte_array[rti];
1106 Index security_level = 0;
1107 ListCell *lc;
1108
1109 /*
1110 * Each element of the securityQuals list has been preprocessed into an
1111 * implicitly-ANDed list of clauses. All the clauses in a given sublist
1112 * should get the same security level, but successive sublists get higher
1113 * levels.
1114 */
1115 foreach(lc, rte->securityQuals)
1116 {
1117 List *qualset = (List *) lfirst(lc);
1118 ListCell *lc2;
1119
1120 foreach(lc2, qualset)
1121 {
1122 Node *qual = (Node *) lfirst(lc2);
1123
1124 /*
1125 * We cheat to the extent of passing ojscope = qualscope rather
1126 * than its more logical value of NULL. The only effect this has
1127 * is to force a Var-free qual to be evaluated at the rel rather
1128 * than being pushed up to top of tree, which we don't want.
1129 */
1130 distribute_qual_to_rels(root, qual,
1131 false,
1132 below_outer_join,
1133 JOIN_INNER,
1134 security_level,
1135 qualscope,
1136 qualscope,
1137 NULL,
1138 NULL,
1139 NULL);
1140 }
1141 security_level++;
1142 }
1143
1144 /* Assert that qual_security_level is higher than anything we just used */
1145 Assert(security_level <= root->qual_security_level);
1146 }
1147
1148 /*
1149 * make_outerjoininfo
1150 * Build a SpecialJoinInfo for the current outer join
1151 *
1152 * Inputs:
1153 * left_rels: the base Relids syntactically on outer side of join
1154 * right_rels: the base Relids syntactically on inner side of join
1155 * inner_join_rels: base Relids participating in inner joins below this one
1156 * jointype: what it says (must always be LEFT, FULL, SEMI, or ANTI)
1157 * clause: the outer join's join condition (in implicit-AND format)
1158 *
1159 * The node should eventually be appended to root->join_info_list, but we
1160 * do not do that here.
1161 *
1162 * Note: we assume that this function is invoked bottom-up, so that
1163 * root->join_info_list already contains entries for all outer joins that are
1164 * syntactically below this one.
1165 */
1166 static SpecialJoinInfo *
make_outerjoininfo(PlannerInfo * root,Relids left_rels,Relids right_rels,Relids inner_join_rels,JoinType jointype,List * clause)1167 make_outerjoininfo(PlannerInfo *root,
1168 Relids left_rels, Relids right_rels,
1169 Relids inner_join_rels,
1170 JoinType jointype, List *clause)
1171 {
1172 SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo);
1173 Relids clause_relids;
1174 Relids strict_relids;
1175 Relids min_lefthand;
1176 Relids min_righthand;
1177 ListCell *l;
1178
1179 /*
1180 * We should not see RIGHT JOIN here because left/right were switched
1181 * earlier
1182 */
1183 Assert(jointype != JOIN_INNER);
1184 Assert(jointype != JOIN_RIGHT);
1185
1186 /*
1187 * Presently the executor cannot support FOR [KEY] UPDATE/SHARE marking of
1188 * rels appearing on the nullable side of an outer join. (It's somewhat
1189 * unclear what that would mean, anyway: what should we mark when a result
1190 * row is generated from no element of the nullable relation?) So,
1191 * complain if any nullable rel is FOR [KEY] UPDATE/SHARE.
1192 *
1193 * You might be wondering why this test isn't made far upstream in the
1194 * parser. It's because the parser hasn't got enough info --- consider
1195 * FOR UPDATE applied to a view. Only after rewriting and flattening do
1196 * we know whether the view contains an outer join.
1197 *
1198 * We use the original RowMarkClause list here; the PlanRowMark list would
1199 * list everything.
1200 */
1201 foreach(l, root->parse->rowMarks)
1202 {
1203 RowMarkClause *rc = (RowMarkClause *) lfirst(l);
1204
1205 if (bms_is_member(rc->rti, right_rels) ||
1206 (jointype == JOIN_FULL && bms_is_member(rc->rti, left_rels)))
1207 ereport(ERROR,
1208 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1209 /*------
1210 translator: %s is a SQL row locking clause such as FOR UPDATE */
1211 errmsg("%s cannot be applied to the nullable side of an outer join",
1212 LCS_asString(rc->strength))));
1213 }
1214
1215 sjinfo->syn_lefthand = left_rels;
1216 sjinfo->syn_righthand = right_rels;
1217 sjinfo->jointype = jointype;
1218 /* this always starts out false */
1219 sjinfo->delay_upper_joins = false;
1220
1221 compute_semijoin_info(sjinfo, clause);
1222
1223 /* If it's a full join, no need to be very smart */
1224 if (jointype == JOIN_FULL)
1225 {
1226 sjinfo->min_lefthand = bms_copy(left_rels);
1227 sjinfo->min_righthand = bms_copy(right_rels);
1228 sjinfo->lhs_strict = false; /* don't care about this */
1229 return sjinfo;
1230 }
1231
1232 /*
1233 * Retrieve all relids mentioned within the join clause.
1234 */
1235 clause_relids = pull_varnos((Node *) clause);
1236
1237 /*
1238 * For which relids is the clause strict, ie, it cannot succeed if the
1239 * rel's columns are all NULL?
1240 */
1241 strict_relids = find_nonnullable_rels((Node *) clause);
1242
1243 /* Remember whether the clause is strict for any LHS relations */
1244 sjinfo->lhs_strict = bms_overlap(strict_relids, left_rels);
1245
1246 /*
1247 * Required LHS always includes the LHS rels mentioned in the clause. We
1248 * may have to add more rels based on lower outer joins; see below.
1249 */
1250 min_lefthand = bms_intersect(clause_relids, left_rels);
1251
1252 /*
1253 * Similarly for required RHS. But here, we must also include any lower
1254 * inner joins, to ensure we don't try to commute with any of them.
1255 */
1256 min_righthand = bms_int_members(bms_union(clause_relids, inner_join_rels),
1257 right_rels);
1258
1259 /*
1260 * Now check previous outer joins for ordering restrictions.
1261 */
1262 foreach(l, root->join_info_list)
1263 {
1264 SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
1265
1266 /*
1267 * A full join is an optimization barrier: we can't associate into or
1268 * out of it. Hence, if it overlaps either LHS or RHS of the current
1269 * rel, expand that side's min relset to cover the whole full join.
1270 */
1271 if (otherinfo->jointype == JOIN_FULL)
1272 {
1273 if (bms_overlap(left_rels, otherinfo->syn_lefthand) ||
1274 bms_overlap(left_rels, otherinfo->syn_righthand))
1275 {
1276 min_lefthand = bms_add_members(min_lefthand,
1277 otherinfo->syn_lefthand);
1278 min_lefthand = bms_add_members(min_lefthand,
1279 otherinfo->syn_righthand);
1280 }
1281 if (bms_overlap(right_rels, otherinfo->syn_lefthand) ||
1282 bms_overlap(right_rels, otherinfo->syn_righthand))
1283 {
1284 min_righthand = bms_add_members(min_righthand,
1285 otherinfo->syn_lefthand);
1286 min_righthand = bms_add_members(min_righthand,
1287 otherinfo->syn_righthand);
1288 }
1289 /* Needn't do anything else with the full join */
1290 continue;
1291 }
1292
1293 /*
1294 * For a lower OJ in our LHS, if our join condition uses the lower
1295 * join's RHS and is not strict for that rel, we must preserve the
1296 * ordering of the two OJs, so add lower OJ's full syntactic relset to
1297 * min_lefthand. (We must use its full syntactic relset, not just its
1298 * min_lefthand + min_righthand. This is because there might be other
1299 * OJs below this one that this one can commute with, but we cannot
1300 * commute with them if we don't with this one.) Also, if the current
1301 * join is a semijoin or antijoin, we must preserve ordering
1302 * regardless of strictness.
1303 *
1304 * Note: I believe we have to insist on being strict for at least one
1305 * rel in the lower OJ's min_righthand, not its whole syn_righthand.
1306 */
1307 if (bms_overlap(left_rels, otherinfo->syn_righthand))
1308 {
1309 if (bms_overlap(clause_relids, otherinfo->syn_righthand) &&
1310 (jointype == JOIN_SEMI || jointype == JOIN_ANTI ||
1311 !bms_overlap(strict_relids, otherinfo->min_righthand)))
1312 {
1313 min_lefthand = bms_add_members(min_lefthand,
1314 otherinfo->syn_lefthand);
1315 min_lefthand = bms_add_members(min_lefthand,
1316 otherinfo->syn_righthand);
1317 }
1318 }
1319
1320 /*
1321 * For a lower OJ in our RHS, if our join condition does not use the
1322 * lower join's RHS and the lower OJ's join condition is strict, we
1323 * can interchange the ordering of the two OJs; otherwise we must add
1324 * the lower OJ's full syntactic relset to min_righthand.
1325 *
1326 * Also, if our join condition does not use the lower join's LHS
1327 * either, force the ordering to be preserved. Otherwise we can end
1328 * up with SpecialJoinInfos with identical min_righthands, which can
1329 * confuse join_is_legal (see discussion in backend/optimizer/README).
1330 *
1331 * Also, we must preserve ordering anyway if either the current join
1332 * or the lower OJ is either a semijoin or an antijoin.
1333 *
1334 * Here, we have to consider that "our join condition" includes any
1335 * clauses that syntactically appeared above the lower OJ and below
1336 * ours; those are equivalent to degenerate clauses in our OJ and must
1337 * be treated as such. Such clauses obviously can't reference our
1338 * LHS, and they must be non-strict for the lower OJ's RHS (else
1339 * reduce_outer_joins would have reduced the lower OJ to a plain
1340 * join). Hence the other ways in which we handle clauses within our
1341 * join condition are not affected by them. The net effect is
1342 * therefore sufficiently represented by the delay_upper_joins flag
1343 * saved for us by check_outerjoin_delay.
1344 */
1345 if (bms_overlap(right_rels, otherinfo->syn_righthand))
1346 {
1347 if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
1348 !bms_overlap(clause_relids, otherinfo->min_lefthand) ||
1349 jointype == JOIN_SEMI ||
1350 jointype == JOIN_ANTI ||
1351 otherinfo->jointype == JOIN_SEMI ||
1352 otherinfo->jointype == JOIN_ANTI ||
1353 !otherinfo->lhs_strict || otherinfo->delay_upper_joins)
1354 {
1355 min_righthand = bms_add_members(min_righthand,
1356 otherinfo->syn_lefthand);
1357 min_righthand = bms_add_members(min_righthand,
1358 otherinfo->syn_righthand);
1359 }
1360 }
1361 }
1362
1363 /*
1364 * Examine PlaceHolderVars. If a PHV is supposed to be evaluated within
1365 * this join's nullable side, then ensure that min_righthand contains the
1366 * full eval_at set of the PHV. This ensures that the PHV actually can be
1367 * evaluated within the RHS. Note that this works only because we should
1368 * already have determined the final eval_at level for any PHV
1369 * syntactically within this join.
1370 */
1371 foreach(l, root->placeholder_list)
1372 {
1373 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
1374 Relids ph_syn_level = phinfo->ph_var->phrels;
1375
1376 /* Ignore placeholder if it didn't syntactically come from RHS */
1377 if (!bms_is_subset(ph_syn_level, right_rels))
1378 continue;
1379
1380 /* Else, prevent join from being formed before we eval the PHV */
1381 min_righthand = bms_add_members(min_righthand, phinfo->ph_eval_at);
1382 }
1383
1384 /*
1385 * If we found nothing to put in min_lefthand, punt and make it the full
1386 * LHS, to avoid having an empty min_lefthand which will confuse later
1387 * processing. (We don't try to be smart about such cases, just correct.)
1388 * Likewise for min_righthand.
1389 */
1390 if (bms_is_empty(min_lefthand))
1391 min_lefthand = bms_copy(left_rels);
1392 if (bms_is_empty(min_righthand))
1393 min_righthand = bms_copy(right_rels);
1394
1395 /* Now they'd better be nonempty */
1396 Assert(!bms_is_empty(min_lefthand));
1397 Assert(!bms_is_empty(min_righthand));
1398 /* Shouldn't overlap either */
1399 Assert(!bms_overlap(min_lefthand, min_righthand));
1400
1401 sjinfo->min_lefthand = min_lefthand;
1402 sjinfo->min_righthand = min_righthand;
1403
1404 return sjinfo;
1405 }
1406
1407 /*
1408 * compute_semijoin_info
1409 * Fill semijoin-related fields of a new SpecialJoinInfo
1410 *
1411 * Note: this relies on only the jointype and syn_righthand fields of the
1412 * SpecialJoinInfo; the rest may not be set yet.
1413 */
1414 static void
compute_semijoin_info(SpecialJoinInfo * sjinfo,List * clause)1415 compute_semijoin_info(SpecialJoinInfo *sjinfo, List *clause)
1416 {
1417 List *semi_operators;
1418 List *semi_rhs_exprs;
1419 bool all_btree;
1420 bool all_hash;
1421 ListCell *lc;
1422
1423 /* Initialize semijoin-related fields in case we can't unique-ify */
1424 sjinfo->semi_can_btree = false;
1425 sjinfo->semi_can_hash = false;
1426 sjinfo->semi_operators = NIL;
1427 sjinfo->semi_rhs_exprs = NIL;
1428
1429 /* Nothing more to do if it's not a semijoin */
1430 if (sjinfo->jointype != JOIN_SEMI)
1431 return;
1432
1433 /*
1434 * Look to see whether the semijoin's join quals consist of AND'ed
1435 * equality operators, with (only) RHS variables on only one side of each
1436 * one. If so, we can figure out how to enforce uniqueness for the RHS.
1437 *
1438 * Note that the input clause list is the list of quals that are
1439 * *syntactically* associated with the semijoin, which in practice means
1440 * the synthesized comparison list for an IN or the WHERE of an EXISTS.
1441 * Particularly in the latter case, it might contain clauses that aren't
1442 * *semantically* associated with the join, but refer to just one side or
1443 * the other. We can ignore such clauses here, as they will just drop
1444 * down to be processed within one side or the other. (It is okay to
1445 * consider only the syntactically-associated clauses here because for a
1446 * semijoin, no higher-level quals could refer to the RHS, and so there
1447 * can be no other quals that are semantically associated with this join.
1448 * We do things this way because it is useful to have the set of potential
1449 * unique-ification expressions before we can extract the list of quals
1450 * that are actually semantically associated with the particular join.)
1451 *
1452 * Note that the semi_operators list consists of the joinqual operators
1453 * themselves (but commuted if needed to put the RHS value on the right).
1454 * These could be cross-type operators, in which case the operator
1455 * actually needed for uniqueness is a related single-type operator. We
1456 * assume here that that operator will be available from the btree or hash
1457 * opclass when the time comes ... if not, create_unique_plan() will fail.
1458 */
1459 semi_operators = NIL;
1460 semi_rhs_exprs = NIL;
1461 all_btree = true;
1462 all_hash = enable_hashagg; /* don't consider hash if not enabled */
1463 foreach(lc, clause)
1464 {
1465 OpExpr *op = (OpExpr *) lfirst(lc);
1466 Oid opno;
1467 Node *left_expr;
1468 Node *right_expr;
1469 Relids left_varnos;
1470 Relids right_varnos;
1471 Relids all_varnos;
1472 Oid opinputtype;
1473
1474 /* Is it a binary opclause? */
1475 if (!IsA(op, OpExpr) ||
1476 list_length(op->args) != 2)
1477 {
1478 /* No, but does it reference both sides? */
1479 all_varnos = pull_varnos((Node *) op);
1480 if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
1481 bms_is_subset(all_varnos, sjinfo->syn_righthand))
1482 {
1483 /*
1484 * Clause refers to only one rel, so ignore it --- unless it
1485 * contains volatile functions, in which case we'd better
1486 * punt.
1487 */
1488 if (contain_volatile_functions((Node *) op))
1489 return;
1490 continue;
1491 }
1492 /* Non-operator clause referencing both sides, must punt */
1493 return;
1494 }
1495
1496 /* Extract data from binary opclause */
1497 opno = op->opno;
1498 left_expr = linitial(op->args);
1499 right_expr = lsecond(op->args);
1500 left_varnos = pull_varnos(left_expr);
1501 right_varnos = pull_varnos(right_expr);
1502 all_varnos = bms_union(left_varnos, right_varnos);
1503 opinputtype = exprType(left_expr);
1504
1505 /* Does it reference both sides? */
1506 if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
1507 bms_is_subset(all_varnos, sjinfo->syn_righthand))
1508 {
1509 /*
1510 * Clause refers to only one rel, so ignore it --- unless it
1511 * contains volatile functions, in which case we'd better punt.
1512 */
1513 if (contain_volatile_functions((Node *) op))
1514 return;
1515 continue;
1516 }
1517
1518 /* check rel membership of arguments */
1519 if (!bms_is_empty(right_varnos) &&
1520 bms_is_subset(right_varnos, sjinfo->syn_righthand) &&
1521 !bms_overlap(left_varnos, sjinfo->syn_righthand))
1522 {
1523 /* typical case, right_expr is RHS variable */
1524 }
1525 else if (!bms_is_empty(left_varnos) &&
1526 bms_is_subset(left_varnos, sjinfo->syn_righthand) &&
1527 !bms_overlap(right_varnos, sjinfo->syn_righthand))
1528 {
1529 /* flipped case, left_expr is RHS variable */
1530 opno = get_commutator(opno);
1531 if (!OidIsValid(opno))
1532 return;
1533 right_expr = left_expr;
1534 }
1535 else
1536 {
1537 /* mixed membership of args, punt */
1538 return;
1539 }
1540
1541 /* all operators must be btree equality or hash equality */
1542 if (all_btree)
1543 {
1544 /* oprcanmerge is considered a hint... */
1545 if (!op_mergejoinable(opno, opinputtype) ||
1546 get_mergejoin_opfamilies(opno) == NIL)
1547 all_btree = false;
1548 }
1549 if (all_hash)
1550 {
1551 /* ... but oprcanhash had better be correct */
1552 if (!op_hashjoinable(opno, opinputtype))
1553 all_hash = false;
1554 }
1555 if (!(all_btree || all_hash))
1556 return;
1557
1558 /* so far so good, keep building lists */
1559 semi_operators = lappend_oid(semi_operators, opno);
1560 semi_rhs_exprs = lappend(semi_rhs_exprs, copyObject(right_expr));
1561 }
1562
1563 /* Punt if we didn't find at least one column to unique-ify */
1564 if (semi_rhs_exprs == NIL)
1565 return;
1566
1567 /*
1568 * The expressions we'd need to unique-ify mustn't be volatile.
1569 */
1570 if (contain_volatile_functions((Node *) semi_rhs_exprs))
1571 return;
1572
1573 /*
1574 * If we get here, we can unique-ify the semijoin's RHS using at least one
1575 * of sorting and hashing. Save the information about how to do that.
1576 */
1577 sjinfo->semi_can_btree = all_btree;
1578 sjinfo->semi_can_hash = all_hash;
1579 sjinfo->semi_operators = semi_operators;
1580 sjinfo->semi_rhs_exprs = semi_rhs_exprs;
1581 }
1582
1583
1584 /*****************************************************************************
1585 *
1586 * QUALIFICATIONS
1587 *
1588 *****************************************************************************/
1589
1590 /*
1591 * distribute_qual_to_rels
1592 * Add clause information to either the baserestrictinfo or joininfo list
1593 * (depending on whether the clause is a join) of each base relation
1594 * mentioned in the clause. A RestrictInfo node is created and added to
1595 * the appropriate list for each rel. Alternatively, if the clause uses a
1596 * mergejoinable operator and is not delayed by outer-join rules, enter
1597 * the left- and right-side expressions into the query's list of
1598 * EquivalenceClasses. Alternatively, if the clause needs to be treated
1599 * as belonging to a higher join level, just add it to postponed_qual_list.
1600 *
1601 * 'clause': the qual clause to be distributed
1602 * 'is_deduced': TRUE if the qual came from implied-equality deduction
1603 * 'below_outer_join': TRUE if the qual is from a JOIN/ON that is below the
1604 * nullable side of a higher-level outer join
1605 * 'jointype': type of join the qual is from (JOIN_INNER for a WHERE clause)
1606 * 'security_level': security_level to assign to the qual
1607 * 'qualscope': set of baserels the qual's syntactic scope covers
1608 * 'ojscope': NULL if not an outer-join qual, else the minimum set of baserels
1609 * needed to form this join
1610 * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of
1611 * baserels appearing on the outer (nonnullable) side of the join
1612 * (for FULL JOIN this includes both sides of the join, and must in fact
1613 * equal qualscope)
1614 * 'deduced_nullable_relids': if is_deduced is TRUE, the nullable relids to
1615 * impute to the clause; otherwise NULL
1616 * 'postponed_qual_list': list of PostponedQual structs, which we can add
1617 * this qual to if it turns out to belong to a higher join level.
1618 * Can be NULL if caller knows postponement is impossible.
1619 *
1620 * 'qualscope' identifies what level of JOIN the qual came from syntactically.
1621 * 'ojscope' is needed if we decide to force the qual up to the outer-join
1622 * level, which will be ojscope not necessarily qualscope.
1623 *
1624 * In normal use (when is_deduced is FALSE), at the time this is called,
1625 * root->join_info_list must contain entries for all and only those special
1626 * joins that are syntactically below this qual. But when is_deduced is TRUE,
1627 * we are adding new deduced clauses after completion of deconstruct_jointree,
1628 * so it cannot be assumed that root->join_info_list has anything to do with
1629 * qual placement.
1630 */
1631 static void
distribute_qual_to_rels(PlannerInfo * root,Node * clause,bool is_deduced,bool below_outer_join,JoinType jointype,Index security_level,Relids qualscope,Relids ojscope,Relids outerjoin_nonnullable,Relids deduced_nullable_relids,List ** postponed_qual_list)1632 distribute_qual_to_rels(PlannerInfo *root, Node *clause,
1633 bool is_deduced,
1634 bool below_outer_join,
1635 JoinType jointype,
1636 Index security_level,
1637 Relids qualscope,
1638 Relids ojscope,
1639 Relids outerjoin_nonnullable,
1640 Relids deduced_nullable_relids,
1641 List **postponed_qual_list)
1642 {
1643 Relids relids;
1644 bool is_pushed_down;
1645 bool outerjoin_delayed;
1646 bool pseudoconstant = false;
1647 bool maybe_equivalence;
1648 bool maybe_outer_join;
1649 Relids nullable_relids;
1650 RestrictInfo *restrictinfo;
1651
1652 /*
1653 * Retrieve all relids mentioned within the clause.
1654 */
1655 relids = pull_varnos(clause);
1656
1657 /*
1658 * In ordinary SQL, a WHERE or JOIN/ON clause can't reference any rels
1659 * that aren't within its syntactic scope; however, if we pulled up a
1660 * LATERAL subquery then we might find such references in quals that have
1661 * been pulled up. We need to treat such quals as belonging to the join
1662 * level that includes every rel they reference. Although we could make
1663 * pull_up_subqueries() place such quals correctly to begin with, it's
1664 * easier to handle it here. When we find a clause that contains Vars
1665 * outside its syntactic scope, we add it to the postponed-quals list, and
1666 * process it once we've recursed back up to the appropriate join level.
1667 */
1668 if (!bms_is_subset(relids, qualscope))
1669 {
1670 PostponedQual *pq = (PostponedQual *) palloc(sizeof(PostponedQual));
1671
1672 Assert(root->hasLateralRTEs); /* shouldn't happen otherwise */
1673 Assert(jointype == JOIN_INNER); /* mustn't postpone past outer join */
1674 Assert(!is_deduced); /* shouldn't be deduced, either */
1675 pq->qual = clause;
1676 pq->relids = relids;
1677 *postponed_qual_list = lappend(*postponed_qual_list, pq);
1678 return;
1679 }
1680
1681 /*
1682 * If it's an outer-join clause, also check that relids is a subset of
1683 * ojscope. (This should not fail if the syntactic scope check passed.)
1684 */
1685 if (ojscope && !bms_is_subset(relids, ojscope))
1686 elog(ERROR, "JOIN qualification cannot refer to other relations");
1687
1688 /*
1689 * If the clause is variable-free, our normal heuristic for pushing it
1690 * down to just the mentioned rels doesn't work, because there are none.
1691 *
1692 * If the clause is an outer-join clause, we must force it to the OJ's
1693 * semantic level to preserve semantics.
1694 *
1695 * Otherwise, when the clause contains volatile functions, we force it to
1696 * be evaluated at its original syntactic level. This preserves the
1697 * expected semantics.
1698 *
1699 * When the clause contains no volatile functions either, it is actually a
1700 * pseudoconstant clause that will not change value during any one
1701 * execution of the plan, and hence can be used as a one-time qual in a
1702 * gating Result plan node. We put such a clause into the regular
1703 * RestrictInfo lists for the moment, but eventually createplan.c will
1704 * pull it out and make a gating Result node immediately above whatever
1705 * plan node the pseudoconstant clause is assigned to. It's usually best
1706 * to put a gating node as high in the plan tree as possible. If we are
1707 * not below an outer join, we can actually push the pseudoconstant qual
1708 * all the way to the top of the tree. If we are below an outer join, we
1709 * leave the qual at its original syntactic level (we could push it up to
1710 * just below the outer join, but that seems more complex than it's
1711 * worth).
1712 */
1713 if (bms_is_empty(relids))
1714 {
1715 if (ojscope)
1716 {
1717 /* clause is attached to outer join, eval it there */
1718 relids = bms_copy(ojscope);
1719 /* mustn't use as gating qual, so don't mark pseudoconstant */
1720 }
1721 else
1722 {
1723 /* eval at original syntactic level */
1724 relids = bms_copy(qualscope);
1725 if (!contain_volatile_functions(clause))
1726 {
1727 /* mark as gating qual */
1728 pseudoconstant = true;
1729 /* tell createplan.c to check for gating quals */
1730 root->hasPseudoConstantQuals = true;
1731 /* if not below outer join, push it to top of tree */
1732 if (!below_outer_join)
1733 {
1734 relids =
1735 get_relids_in_jointree((Node *) root->parse->jointree,
1736 false);
1737 qualscope = bms_copy(relids);
1738 }
1739 }
1740 }
1741 }
1742
1743 /*----------
1744 * Check to see if clause application must be delayed by outer-join
1745 * considerations.
1746 *
1747 * A word about is_pushed_down: we mark the qual as "pushed down" if
1748 * it is (potentially) applicable at a level different from its original
1749 * syntactic level. This flag is used to distinguish OUTER JOIN ON quals
1750 * from other quals pushed down to the same joinrel. The rules are:
1751 * WHERE quals and INNER JOIN quals: is_pushed_down = true.
1752 * Non-degenerate OUTER JOIN quals: is_pushed_down = false.
1753 * Degenerate OUTER JOIN quals: is_pushed_down = true.
1754 * A "degenerate" OUTER JOIN qual is one that doesn't mention the
1755 * non-nullable side, and hence can be pushed down into the nullable side
1756 * without changing the join result. It is correct to treat it as a
1757 * regular filter condition at the level where it is evaluated.
1758 *
1759 * Note: it is not immediately obvious that a simple boolean is enough
1760 * for this: if for some reason we were to attach a degenerate qual to
1761 * its original join level, it would need to be treated as an outer join
1762 * qual there. However, this cannot happen, because all the rels the
1763 * clause mentions must be in the outer join's min_righthand, therefore
1764 * the join it needs must be formed before the outer join; and we always
1765 * attach quals to the lowest level where they can be evaluated. But
1766 * if we were ever to re-introduce a mechanism for delaying evaluation
1767 * of "expensive" quals, this area would need work.
1768 *
1769 * Note: generally, use of is_pushed_down has to go through the macro
1770 * RINFO_IS_PUSHED_DOWN, because that flag alone is not always sufficient
1771 * to tell whether a clause must be treated as pushed-down in context.
1772 * This seems like another reason why it should perhaps be rethought.
1773 *----------
1774 */
1775 if (is_deduced)
1776 {
1777 /*
1778 * If the qual came from implied-equality deduction, it should not be
1779 * outerjoin-delayed, else deducer blew it. But we can't check this
1780 * because the join_info_list may now contain OJs above where the qual
1781 * belongs. For the same reason, we must rely on caller to supply the
1782 * correct nullable_relids set.
1783 */
1784 Assert(!ojscope);
1785 is_pushed_down = true;
1786 outerjoin_delayed = false;
1787 nullable_relids = deduced_nullable_relids;
1788 /* Don't feed it back for more deductions */
1789 maybe_equivalence = false;
1790 maybe_outer_join = false;
1791 }
1792 else if (bms_overlap(relids, outerjoin_nonnullable))
1793 {
1794 /*
1795 * The qual is attached to an outer join and mentions (some of the)
1796 * rels on the nonnullable side, so it's not degenerate.
1797 *
1798 * We can't use such a clause to deduce equivalence (the left and
1799 * right sides might be unequal above the join because one of them has
1800 * gone to NULL) ... but we might be able to use it for more limited
1801 * deductions, if it is mergejoinable. So consider adding it to the
1802 * lists of set-aside outer-join clauses.
1803 */
1804 is_pushed_down = false;
1805 maybe_equivalence = false;
1806 maybe_outer_join = true;
1807
1808 /* Check to see if must be delayed by lower outer join */
1809 outerjoin_delayed = check_outerjoin_delay(root,
1810 &relids,
1811 &nullable_relids,
1812 false);
1813
1814 /*
1815 * Now force the qual to be evaluated exactly at the level of joining
1816 * corresponding to the outer join. We cannot let it get pushed down
1817 * into the nonnullable side, since then we'd produce no output rows,
1818 * rather than the intended single null-extended row, for any
1819 * nonnullable-side rows failing the qual.
1820 *
1821 * (Do this step after calling check_outerjoin_delay, because that
1822 * trashes relids.)
1823 */
1824 Assert(ojscope);
1825 relids = ojscope;
1826 Assert(!pseudoconstant);
1827 }
1828 else
1829 {
1830 /*
1831 * Normal qual clause or degenerate outer-join clause. Either way, we
1832 * can mark it as pushed-down.
1833 */
1834 is_pushed_down = true;
1835
1836 /* Check to see if must be delayed by lower outer join */
1837 outerjoin_delayed = check_outerjoin_delay(root,
1838 &relids,
1839 &nullable_relids,
1840 true);
1841
1842 if (outerjoin_delayed)
1843 {
1844 /* Should still be a subset of current scope ... */
1845 Assert(root->hasLateralRTEs || bms_is_subset(relids, qualscope));
1846 Assert(ojscope == NULL || bms_is_subset(relids, ojscope));
1847
1848 /*
1849 * Because application of the qual will be delayed by outer join,
1850 * we mustn't assume its vars are equal everywhere.
1851 */
1852 maybe_equivalence = false;
1853
1854 /*
1855 * It's possible that this is an IS NULL clause that's redundant
1856 * with a lower antijoin; if so we can just discard it. We need
1857 * not test in any of the other cases, because this will only be
1858 * possible for pushed-down, delayed clauses.
1859 */
1860 if (check_redundant_nullability_qual(root, clause))
1861 return;
1862 }
1863 else
1864 {
1865 /*
1866 * Qual is not delayed by any lower outer-join restriction, so we
1867 * can consider feeding it to the equivalence machinery. However,
1868 * if it's itself within an outer-join clause, treat it as though
1869 * it appeared below that outer join (note that we can only get
1870 * here when the clause references only nullable-side rels).
1871 */
1872 maybe_equivalence = true;
1873 if (outerjoin_nonnullable != NULL)
1874 below_outer_join = true;
1875 }
1876
1877 /*
1878 * Since it doesn't mention the LHS, it's certainly not useful as a
1879 * set-aside OJ clause, even if it's in an OJ.
1880 */
1881 maybe_outer_join = false;
1882 }
1883
1884 /*
1885 * Build the RestrictInfo node itself.
1886 */
1887 restrictinfo = make_restrictinfo((Expr *) clause,
1888 is_pushed_down,
1889 outerjoin_delayed,
1890 pseudoconstant,
1891 security_level,
1892 relids,
1893 outerjoin_nonnullable,
1894 nullable_relids);
1895
1896 /*
1897 * If it's a join clause (either naturally, or because delayed by
1898 * outer-join rules), add vars used in the clause to targetlists of their
1899 * relations, so that they will be emitted by the plan nodes that scan
1900 * those relations (else they won't be available at the join node!).
1901 *
1902 * Note: if the clause gets absorbed into an EquivalenceClass then this
1903 * may be unnecessary, but for now we have to do it to cover the case
1904 * where the EC becomes ec_broken and we end up reinserting the original
1905 * clauses into the plan.
1906 */
1907 if (bms_membership(relids) == BMS_MULTIPLE)
1908 {
1909 List *vars = pull_var_clause(clause,
1910 PVC_RECURSE_AGGREGATES |
1911 PVC_RECURSE_WINDOWFUNCS |
1912 PVC_INCLUDE_PLACEHOLDERS);
1913
1914 add_vars_to_targetlist(root, vars, relids, false);
1915 list_free(vars);
1916 }
1917
1918 /*
1919 * We check "mergejoinability" of every clause, not only join clauses,
1920 * because we want to know about equivalences between vars of the same
1921 * relation, or between vars and consts.
1922 */
1923 check_mergejoinable(restrictinfo);
1924
1925 /*
1926 * If it is a true equivalence clause, send it to the EquivalenceClass
1927 * machinery. We do *not* attach it directly to any restriction or join
1928 * lists. The EC code will propagate it to the appropriate places later.
1929 *
1930 * If the clause has a mergejoinable operator and is not
1931 * outerjoin-delayed, yet isn't an equivalence because it is an outer-join
1932 * clause, the EC code may yet be able to do something with it. We add it
1933 * to appropriate lists for further consideration later. Specifically:
1934 *
1935 * If it is a left or right outer-join qualification that relates the two
1936 * sides of the outer join (no funny business like leftvar1 = leftvar2 +
1937 * rightvar), we add it to root->left_join_clauses or
1938 * root->right_join_clauses according to which side the nonnullable
1939 * variable appears on.
1940 *
1941 * If it is a full outer-join qualification, we add it to
1942 * root->full_join_clauses. (Ideally we'd discard cases that aren't
1943 * leftvar = rightvar, as we do for left/right joins, but this routine
1944 * doesn't have the info needed to do that; and the current usage of the
1945 * full_join_clauses list doesn't require that, so it's not currently
1946 * worth complicating this routine's API to make it possible.)
1947 *
1948 * If none of the above hold, pass it off to
1949 * distribute_restrictinfo_to_rels().
1950 *
1951 * In all cases, it's important to initialize the left_ec and right_ec
1952 * fields of a mergejoinable clause, so that all possibly mergejoinable
1953 * expressions have representations in EquivalenceClasses. If
1954 * process_equivalence is successful, it will take care of that;
1955 * otherwise, we have to call initialize_mergeclause_eclasses to do it.
1956 */
1957 if (restrictinfo->mergeopfamilies)
1958 {
1959 if (maybe_equivalence)
1960 {
1961 if (check_equivalence_delay(root, restrictinfo) &&
1962 process_equivalence(root, restrictinfo, below_outer_join))
1963 return;
1964 /* EC rejected it, so set left_ec/right_ec the hard way ... */
1965 initialize_mergeclause_eclasses(root, restrictinfo);
1966 /* ... and fall through to distribute_restrictinfo_to_rels */
1967 }
1968 else if (maybe_outer_join && restrictinfo->can_join)
1969 {
1970 /* we need to set up left_ec/right_ec the hard way */
1971 initialize_mergeclause_eclasses(root, restrictinfo);
1972 /* now see if it should go to any outer-join lists */
1973 if (bms_is_subset(restrictinfo->left_relids,
1974 outerjoin_nonnullable) &&
1975 !bms_overlap(restrictinfo->right_relids,
1976 outerjoin_nonnullable))
1977 {
1978 /* we have outervar = innervar */
1979 root->left_join_clauses = lappend(root->left_join_clauses,
1980 restrictinfo);
1981 return;
1982 }
1983 if (bms_is_subset(restrictinfo->right_relids,
1984 outerjoin_nonnullable) &&
1985 !bms_overlap(restrictinfo->left_relids,
1986 outerjoin_nonnullable))
1987 {
1988 /* we have innervar = outervar */
1989 root->right_join_clauses = lappend(root->right_join_clauses,
1990 restrictinfo);
1991 return;
1992 }
1993 if (jointype == JOIN_FULL)
1994 {
1995 /* FULL JOIN (above tests cannot match in this case) */
1996 root->full_join_clauses = lappend(root->full_join_clauses,
1997 restrictinfo);
1998 return;
1999 }
2000 /* nope, so fall through to distribute_restrictinfo_to_rels */
2001 }
2002 else
2003 {
2004 /* we still need to set up left_ec/right_ec */
2005 initialize_mergeclause_eclasses(root, restrictinfo);
2006 }
2007 }
2008
2009 /* No EC special case applies, so push it into the clause lists */
2010 distribute_restrictinfo_to_rels(root, restrictinfo);
2011 }
2012
2013 /*
2014 * check_outerjoin_delay
2015 * Detect whether a qual referencing the given relids must be delayed
2016 * in application due to the presence of a lower outer join, and/or
2017 * may force extra delay of higher-level outer joins.
2018 *
2019 * If the qual must be delayed, add relids to *relids_p to reflect the lowest
2020 * safe level for evaluating the qual, and return TRUE. Any extra delay for
2021 * higher-level joins is reflected by setting delay_upper_joins to TRUE in
2022 * SpecialJoinInfo structs. We also compute nullable_relids, the set of
2023 * referenced relids that are nullable by lower outer joins (note that this
2024 * can be nonempty even for a non-delayed qual).
2025 *
2026 * For an is_pushed_down qual, we can evaluate the qual as soon as (1) we have
2027 * all the rels it mentions, and (2) we are at or above any outer joins that
2028 * can null any of these rels and are below the syntactic location of the
2029 * given qual. We must enforce (2) because pushing down such a clause below
2030 * the OJ might cause the OJ to emit null-extended rows that should not have
2031 * been formed, or that should have been rejected by the clause. (This is
2032 * only an issue for non-strict quals, since if we can prove a qual mentioning
2033 * only nullable rels is strict, we'd have reduced the outer join to an inner
2034 * join in reduce_outer_joins().)
2035 *
2036 * To enforce (2), scan the join_info_list and merge the required-relid sets of
2037 * any such OJs into the clause's own reference list. At the time we are
2038 * called, the join_info_list contains only outer joins below this qual. We
2039 * have to repeat the scan until no new relids get added; this ensures that
2040 * the qual is suitably delayed regardless of the order in which OJs get
2041 * executed. As an example, if we have one OJ with LHS=A, RHS=B, and one with
2042 * LHS=B, RHS=C, it is implied that these can be done in either order; if the
2043 * B/C join is done first then the join to A can null C, so a qual actually
2044 * mentioning only C cannot be applied below the join to A.
2045 *
2046 * For a non-pushed-down qual, this isn't going to determine where we place the
2047 * qual, but we need to determine outerjoin_delayed and nullable_relids anyway
2048 * for use later in the planning process.
2049 *
2050 * Lastly, a pushed-down qual that references the nullable side of any current
2051 * join_info_list member and has to be evaluated above that OJ (because its
2052 * required relids overlap the LHS too) causes that OJ's delay_upper_joins
2053 * flag to be set TRUE. This will prevent any higher-level OJs from
2054 * being interchanged with that OJ, which would result in not having any
2055 * correct place to evaluate the qual. (The case we care about here is a
2056 * sub-select WHERE clause within the RHS of some outer join. The WHERE
2057 * clause must effectively be treated as a degenerate clause of that outer
2058 * join's condition. Rather than trying to match such clauses with joins
2059 * directly, we set delay_upper_joins here, and when the upper outer join
2060 * is processed by make_outerjoininfo, it will refrain from allowing the
2061 * two OJs to commute.)
2062 */
2063 static bool
check_outerjoin_delay(PlannerInfo * root,Relids * relids_p,Relids * nullable_relids_p,bool is_pushed_down)2064 check_outerjoin_delay(PlannerInfo *root,
2065 Relids *relids_p, /* in/out parameter */
2066 Relids *nullable_relids_p, /* output parameter */
2067 bool is_pushed_down)
2068 {
2069 Relids relids;
2070 Relids nullable_relids;
2071 bool outerjoin_delayed;
2072 bool found_some;
2073
2074 /* fast path if no special joins */
2075 if (root->join_info_list == NIL)
2076 {
2077 *nullable_relids_p = NULL;
2078 return false;
2079 }
2080
2081 /* must copy relids because we need the original value at the end */
2082 relids = bms_copy(*relids_p);
2083 nullable_relids = NULL;
2084 outerjoin_delayed = false;
2085 do
2086 {
2087 ListCell *l;
2088
2089 found_some = false;
2090 foreach(l, root->join_info_list)
2091 {
2092 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
2093
2094 /* do we reference any nullable rels of this OJ? */
2095 if (bms_overlap(relids, sjinfo->min_righthand) ||
2096 (sjinfo->jointype == JOIN_FULL &&
2097 bms_overlap(relids, sjinfo->min_lefthand)))
2098 {
2099 /* yes; have we included all its rels in relids? */
2100 if (!bms_is_subset(sjinfo->min_lefthand, relids) ||
2101 !bms_is_subset(sjinfo->min_righthand, relids))
2102 {
2103 /* no, so add them in */
2104 relids = bms_add_members(relids, sjinfo->min_lefthand);
2105 relids = bms_add_members(relids, sjinfo->min_righthand);
2106 outerjoin_delayed = true;
2107 /* we'll need another iteration */
2108 found_some = true;
2109 }
2110 /* track all the nullable rels of relevant OJs */
2111 nullable_relids = bms_add_members(nullable_relids,
2112 sjinfo->min_righthand);
2113 if (sjinfo->jointype == JOIN_FULL)
2114 nullable_relids = bms_add_members(nullable_relids,
2115 sjinfo->min_lefthand);
2116 /* set delay_upper_joins if needed */
2117 if (is_pushed_down && sjinfo->jointype != JOIN_FULL &&
2118 bms_overlap(relids, sjinfo->min_lefthand))
2119 sjinfo->delay_upper_joins = true;
2120 }
2121 }
2122 } while (found_some);
2123
2124 /* identify just the actually-referenced nullable rels */
2125 nullable_relids = bms_int_members(nullable_relids, *relids_p);
2126
2127 /* replace *relids_p, and return nullable_relids */
2128 bms_free(*relids_p);
2129 *relids_p = relids;
2130 *nullable_relids_p = nullable_relids;
2131 return outerjoin_delayed;
2132 }
2133
2134 /*
2135 * check_equivalence_delay
2136 * Detect whether a potential equivalence clause is rendered unsafe
2137 * by outer-join-delay considerations. Return TRUE if it's safe.
2138 *
2139 * The initial tests in distribute_qual_to_rels will consider a mergejoinable
2140 * clause to be a potential equivalence clause if it is not outerjoin_delayed.
2141 * But since the point of equivalence processing is that we will recombine the
2142 * two sides of the clause with others, we have to check that each side
2143 * satisfies the not-outerjoin_delayed condition on its own; otherwise it might
2144 * not be safe to evaluate everywhere we could place a derived equivalence
2145 * condition.
2146 */
2147 static bool
check_equivalence_delay(PlannerInfo * root,RestrictInfo * restrictinfo)2148 check_equivalence_delay(PlannerInfo *root,
2149 RestrictInfo *restrictinfo)
2150 {
2151 Relids relids;
2152 Relids nullable_relids;
2153
2154 /* fast path if no special joins */
2155 if (root->join_info_list == NIL)
2156 return true;
2157
2158 /* must copy restrictinfo's relids to avoid changing it */
2159 relids = bms_copy(restrictinfo->left_relids);
2160 /* check left side does not need delay */
2161 if (check_outerjoin_delay(root, &relids, &nullable_relids, true))
2162 return false;
2163
2164 /* and similarly for the right side */
2165 relids = bms_copy(restrictinfo->right_relids);
2166 if (check_outerjoin_delay(root, &relids, &nullable_relids, true))
2167 return false;
2168
2169 return true;
2170 }
2171
2172 /*
2173 * check_redundant_nullability_qual
2174 * Check to see if the qual is an IS NULL qual that is redundant with
2175 * a lower JOIN_ANTI join.
2176 *
2177 * We want to suppress redundant IS NULL quals, not so much to save cycles
2178 * as to avoid generating bogus selectivity estimates for them. So if
2179 * redundancy is detected here, distribute_qual_to_rels() just throws away
2180 * the qual.
2181 */
2182 static bool
check_redundant_nullability_qual(PlannerInfo * root,Node * clause)2183 check_redundant_nullability_qual(PlannerInfo *root, Node *clause)
2184 {
2185 Var *forced_null_var;
2186 Index forced_null_rel;
2187 ListCell *lc;
2188
2189 /* Check for IS NULL, and identify the Var forced to NULL */
2190 forced_null_var = find_forced_null_var(clause);
2191 if (forced_null_var == NULL)
2192 return false;
2193 forced_null_rel = forced_null_var->varno;
2194
2195 /*
2196 * If the Var comes from the nullable side of a lower antijoin, the IS
2197 * NULL condition is necessarily true.
2198 */
2199 foreach(lc, root->join_info_list)
2200 {
2201 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
2202
2203 if (sjinfo->jointype == JOIN_ANTI &&
2204 bms_is_member(forced_null_rel, sjinfo->syn_righthand))
2205 return true;
2206 }
2207
2208 return false;
2209 }
2210
2211 /*
2212 * distribute_restrictinfo_to_rels
2213 * Push a completed RestrictInfo into the proper restriction or join
2214 * clause list(s).
2215 *
2216 * This is the last step of distribute_qual_to_rels() for ordinary qual
2217 * clauses. Clauses that are interesting for equivalence-class processing
2218 * are diverted to the EC machinery, but may ultimately get fed back here.
2219 */
2220 void
distribute_restrictinfo_to_rels(PlannerInfo * root,RestrictInfo * restrictinfo)2221 distribute_restrictinfo_to_rels(PlannerInfo *root,
2222 RestrictInfo *restrictinfo)
2223 {
2224 Relids relids = restrictinfo->required_relids;
2225 RelOptInfo *rel;
2226
2227 switch (bms_membership(relids))
2228 {
2229 case BMS_SINGLETON:
2230
2231 /*
2232 * There is only one relation participating in the clause, so it
2233 * is a restriction clause for that relation.
2234 */
2235 rel = find_base_rel(root, bms_singleton_member(relids));
2236
2237 /* Add clause to rel's restriction list */
2238 rel->baserestrictinfo = lappend(rel->baserestrictinfo,
2239 restrictinfo);
2240 /* Update security level info */
2241 rel->baserestrict_min_security = Min(rel->baserestrict_min_security,
2242 restrictinfo->security_level);
2243 break;
2244 case BMS_MULTIPLE:
2245
2246 /*
2247 * The clause is a join clause, since there is more than one rel
2248 * in its relid set.
2249 */
2250
2251 /*
2252 * Check for hashjoinable operators. (We don't bother setting the
2253 * hashjoin info except in true join clauses.)
2254 */
2255 check_hashjoinable(restrictinfo);
2256
2257 /*
2258 * Add clause to the join lists of all the relevant relations.
2259 */
2260 add_join_clause_to_rels(root, restrictinfo, relids);
2261 break;
2262 default:
2263
2264 /*
2265 * clause references no rels, and therefore we have no place to
2266 * attach it. Shouldn't get here if callers are working properly.
2267 */
2268 elog(ERROR, "cannot cope with variable-free clause");
2269 break;
2270 }
2271 }
2272
2273 /*
2274 * process_implied_equality
2275 * Create a restrictinfo item that says "item1 op item2", and push it
2276 * into the appropriate lists. (In practice opno is always a btree
2277 * equality operator.)
2278 *
2279 * "qualscope" is the nominal syntactic level to impute to the restrictinfo.
2280 * This must contain at least all the rels used in the expressions, but it
2281 * is used only to set the qual application level when both exprs are
2282 * variable-free. Otherwise the qual is applied at the lowest join level
2283 * that provides all its variables.
2284 *
2285 * "nullable_relids" is the set of relids used in the expressions that are
2286 * potentially nullable below the expressions. (This has to be supplied by
2287 * caller because this function is used after deconstruct_jointree, so we
2288 * don't have knowledge of where the clause items came from.)
2289 *
2290 * "security_level" is the security level to assign to the new restrictinfo.
2291 *
2292 * "both_const" indicates whether both items are known pseudo-constant;
2293 * in this case it is worth applying eval_const_expressions() in case we
2294 * can produce constant TRUE or constant FALSE. (Otherwise it's not,
2295 * because the expressions went through eval_const_expressions already.)
2296 *
2297 * Note: this function will copy item1 and item2, but it is caller's
2298 * responsibility to make sure that the Relids parameters are fresh copies
2299 * not shared with other uses.
2300 *
2301 * This is currently used only when an EquivalenceClass is found to
2302 * contain pseudoconstants. See path/pathkeys.c for more details.
2303 */
2304 void
process_implied_equality(PlannerInfo * root,Oid opno,Oid collation,Expr * item1,Expr * item2,Relids qualscope,Relids nullable_relids,Index security_level,bool below_outer_join,bool both_const)2305 process_implied_equality(PlannerInfo *root,
2306 Oid opno,
2307 Oid collation,
2308 Expr *item1,
2309 Expr *item2,
2310 Relids qualscope,
2311 Relids nullable_relids,
2312 Index security_level,
2313 bool below_outer_join,
2314 bool both_const)
2315 {
2316 Expr *clause;
2317
2318 /*
2319 * Build the new clause. Copy to ensure it shares no substructure with
2320 * original (this is necessary in case there are subselects in there...)
2321 */
2322 clause = make_opclause(opno,
2323 BOOLOID, /* opresulttype */
2324 false, /* opretset */
2325 copyObject(item1),
2326 copyObject(item2),
2327 InvalidOid,
2328 collation);
2329
2330 /* If both constant, try to reduce to a boolean constant. */
2331 if (both_const)
2332 {
2333 clause = (Expr *) eval_const_expressions(root, (Node *) clause);
2334
2335 /* If we produced const TRUE, just drop the clause */
2336 if (clause && IsA(clause, Const))
2337 {
2338 Const *cclause = (Const *) clause;
2339
2340 Assert(cclause->consttype == BOOLOID);
2341 if (!cclause->constisnull && DatumGetBool(cclause->constvalue))
2342 return;
2343 }
2344 }
2345
2346 /*
2347 * Push the new clause into all the appropriate restrictinfo lists.
2348 */
2349 distribute_qual_to_rels(root, (Node *) clause,
2350 true, below_outer_join, JOIN_INNER,
2351 security_level,
2352 qualscope, NULL, NULL, nullable_relids,
2353 NULL);
2354 }
2355
2356 /*
2357 * build_implied_join_equality --- build a RestrictInfo for a derived equality
2358 *
2359 * This overlaps the functionality of process_implied_equality(), but we
2360 * must return the RestrictInfo, not push it into the joininfo tree.
2361 *
2362 * Note: this function will copy item1 and item2, but it is caller's
2363 * responsibility to make sure that the Relids parameters are fresh copies
2364 * not shared with other uses.
2365 *
2366 * Note: we do not do initialize_mergeclause_eclasses() here. It is
2367 * caller's responsibility that left_ec/right_ec be set as necessary.
2368 */
2369 RestrictInfo *
build_implied_join_equality(Oid opno,Oid collation,Expr * item1,Expr * item2,Relids qualscope,Relids nullable_relids,Index security_level)2370 build_implied_join_equality(Oid opno,
2371 Oid collation,
2372 Expr *item1,
2373 Expr *item2,
2374 Relids qualscope,
2375 Relids nullable_relids,
2376 Index security_level)
2377 {
2378 RestrictInfo *restrictinfo;
2379 Expr *clause;
2380
2381 /*
2382 * Build the new clause. Copy to ensure it shares no substructure with
2383 * original (this is necessary in case there are subselects in there...)
2384 */
2385 clause = make_opclause(opno,
2386 BOOLOID, /* opresulttype */
2387 false, /* opretset */
2388 copyObject(item1),
2389 copyObject(item2),
2390 InvalidOid,
2391 collation);
2392
2393 /*
2394 * Build the RestrictInfo node itself.
2395 */
2396 restrictinfo = make_restrictinfo(clause,
2397 true, /* is_pushed_down */
2398 false, /* outerjoin_delayed */
2399 false, /* pseudoconstant */
2400 security_level, /* security_level */
2401 qualscope, /* required_relids */
2402 NULL, /* outer_relids */
2403 nullable_relids); /* nullable_relids */
2404
2405 /* Set mergejoinability/hashjoinability flags */
2406 check_mergejoinable(restrictinfo);
2407 check_hashjoinable(restrictinfo);
2408
2409 return restrictinfo;
2410 }
2411
2412
2413 /*
2414 * match_foreign_keys_to_quals
2415 * Match foreign-key constraints to equivalence classes and join quals
2416 *
2417 * The idea here is to see which query join conditions match equality
2418 * constraints of a foreign-key relationship. For such join conditions,
2419 * we can use the FK semantics to make selectivity estimates that are more
2420 * reliable than estimating from statistics, especially for multiple-column
2421 * FKs, where the normal assumption of independent conditions tends to fail.
2422 *
2423 * In this function we annotate the ForeignKeyOptInfos in root->fkey_list
2424 * with info about which eclasses and join qual clauses they match, and
2425 * discard any ForeignKeyOptInfos that are irrelevant for the query.
2426 */
2427 void
match_foreign_keys_to_quals(PlannerInfo * root)2428 match_foreign_keys_to_quals(PlannerInfo *root)
2429 {
2430 List *newlist = NIL;
2431 ListCell *lc;
2432
2433 foreach(lc, root->fkey_list)
2434 {
2435 ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
2436 RelOptInfo *con_rel;
2437 RelOptInfo *ref_rel;
2438 int colno;
2439
2440 /*
2441 * Either relid might identify a rel that is in the query's rtable but
2442 * isn't referenced by the jointree so won't have a RelOptInfo. Hence
2443 * don't use find_base_rel() here. We can ignore such FKs.
2444 */
2445 if (fkinfo->con_relid >= root->simple_rel_array_size ||
2446 fkinfo->ref_relid >= root->simple_rel_array_size)
2447 continue; /* just paranoia */
2448 con_rel = root->simple_rel_array[fkinfo->con_relid];
2449 if (con_rel == NULL)
2450 continue;
2451 ref_rel = root->simple_rel_array[fkinfo->ref_relid];
2452 if (ref_rel == NULL)
2453 continue;
2454
2455 /*
2456 * Ignore FK unless both rels are baserels. This gets rid of FKs that
2457 * link to inheritance child rels (otherrels) and those that link to
2458 * rels removed by join removal (dead rels).
2459 */
2460 if (con_rel->reloptkind != RELOPT_BASEREL ||
2461 ref_rel->reloptkind != RELOPT_BASEREL)
2462 continue;
2463
2464 /*
2465 * Scan the columns and try to match them to eclasses and quals.
2466 *
2467 * Note: for simple inner joins, any match should be in an eclass.
2468 * "Loose" quals that syntactically match an FK equality must have
2469 * been rejected for EC status because they are outer-join quals or
2470 * similar. We can still consider them to match the FK if they are
2471 * not outerjoin_delayed.
2472 */
2473 for (colno = 0; colno < fkinfo->nkeys; colno++)
2474 {
2475 AttrNumber con_attno,
2476 ref_attno;
2477 Oid fpeqop;
2478 ListCell *lc2;
2479
2480 fkinfo->eclass[colno] = match_eclasses_to_foreign_key_col(root,
2481 fkinfo,
2482 colno);
2483 /* Don't bother looking for loose quals if we got an EC match */
2484 if (fkinfo->eclass[colno] != NULL)
2485 {
2486 fkinfo->nmatched_ec++;
2487 continue;
2488 }
2489
2490 /*
2491 * Scan joininfo list for relevant clauses. Either rel's joininfo
2492 * list would do equally well; we use con_rel's.
2493 */
2494 con_attno = fkinfo->conkey[colno];
2495 ref_attno = fkinfo->confkey[colno];
2496 fpeqop = InvalidOid; /* we'll look this up only if needed */
2497
2498 foreach(lc2, con_rel->joininfo)
2499 {
2500 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc2);
2501 OpExpr *clause = (OpExpr *) rinfo->clause;
2502 Var *leftvar;
2503 Var *rightvar;
2504
2505 /* Ignore outerjoin-delayed clauses */
2506 if (rinfo->outerjoin_delayed)
2507 continue;
2508
2509 /* Only binary OpExprs are useful for consideration */
2510 if (!IsA(clause, OpExpr) ||
2511 list_length(clause->args) != 2)
2512 continue;
2513 leftvar = (Var *) get_leftop((Expr *) clause);
2514 rightvar = (Var *) get_rightop((Expr *) clause);
2515
2516 /* Operands must be Vars, possibly with RelabelType */
2517 while (leftvar && IsA(leftvar, RelabelType))
2518 leftvar = (Var *) ((RelabelType *) leftvar)->arg;
2519 if (!(leftvar && IsA(leftvar, Var)))
2520 continue;
2521 while (rightvar && IsA(rightvar, RelabelType))
2522 rightvar = (Var *) ((RelabelType *) rightvar)->arg;
2523 if (!(rightvar && IsA(rightvar, Var)))
2524 continue;
2525
2526 /* Now try to match the vars to the current foreign key cols */
2527 if (fkinfo->ref_relid == leftvar->varno &&
2528 ref_attno == leftvar->varattno &&
2529 fkinfo->con_relid == rightvar->varno &&
2530 con_attno == rightvar->varattno)
2531 {
2532 /* Vars match, but is it the right operator? */
2533 if (clause->opno == fkinfo->conpfeqop[colno])
2534 {
2535 fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
2536 rinfo);
2537 fkinfo->nmatched_ri++;
2538 }
2539 }
2540 else if (fkinfo->ref_relid == rightvar->varno &&
2541 ref_attno == rightvar->varattno &&
2542 fkinfo->con_relid == leftvar->varno &&
2543 con_attno == leftvar->varattno)
2544 {
2545 /*
2546 * Reverse match, must check commutator operator. Look it
2547 * up if we didn't already. (In the worst case we might
2548 * do multiple lookups here, but that would require an FK
2549 * equality operator without commutator, which is
2550 * unlikely.)
2551 */
2552 if (!OidIsValid(fpeqop))
2553 fpeqop = get_commutator(fkinfo->conpfeqop[colno]);
2554 if (clause->opno == fpeqop)
2555 {
2556 fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
2557 rinfo);
2558 fkinfo->nmatched_ri++;
2559 }
2560 }
2561 }
2562 /* If we found any matching loose quals, count col as matched */
2563 if (fkinfo->rinfos[colno])
2564 fkinfo->nmatched_rcols++;
2565 }
2566
2567 /*
2568 * Currently, we drop multicolumn FKs that aren't fully matched to the
2569 * query. Later we might figure out how to derive some sort of
2570 * estimate from them, in which case this test should be weakened to
2571 * "if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) > 0)".
2572 */
2573 if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) == fkinfo->nkeys)
2574 newlist = lappend(newlist, fkinfo);
2575 }
2576 /* Replace fkey_list, thereby discarding any useless entries */
2577 root->fkey_list = newlist;
2578 }
2579
2580
2581 /*****************************************************************************
2582 *
2583 * CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
2584 *
2585 *****************************************************************************/
2586
2587 /*
2588 * check_mergejoinable
2589 * If the restrictinfo's clause is mergejoinable, set the mergejoin
2590 * info fields in the restrictinfo.
2591 *
2592 * Currently, we support mergejoin for binary opclauses where
2593 * the operator is a mergejoinable operator. The arguments can be
2594 * anything --- as long as there are no volatile functions in them.
2595 */
2596 static void
check_mergejoinable(RestrictInfo * restrictinfo)2597 check_mergejoinable(RestrictInfo *restrictinfo)
2598 {
2599 Expr *clause = restrictinfo->clause;
2600 Oid opno;
2601 Node *leftarg;
2602
2603 if (restrictinfo->pseudoconstant)
2604 return;
2605 if (!is_opclause(clause))
2606 return;
2607 if (list_length(((OpExpr *) clause)->args) != 2)
2608 return;
2609
2610 opno = ((OpExpr *) clause)->opno;
2611 leftarg = linitial(((OpExpr *) clause)->args);
2612
2613 if (op_mergejoinable(opno, exprType(leftarg)) &&
2614 !contain_volatile_functions((Node *) clause))
2615 restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
2616
2617 /*
2618 * Note: op_mergejoinable is just a hint; if we fail to find the operator
2619 * in any btree opfamilies, mergeopfamilies remains NIL and so the clause
2620 * is not treated as mergejoinable.
2621 */
2622 }
2623
2624 /*
2625 * check_hashjoinable
2626 * If the restrictinfo's clause is hashjoinable, set the hashjoin
2627 * info fields in the restrictinfo.
2628 *
2629 * Currently, we support hashjoin for binary opclauses where
2630 * the operator is a hashjoinable operator. The arguments can be
2631 * anything --- as long as there are no volatile functions in them.
2632 */
2633 static void
check_hashjoinable(RestrictInfo * restrictinfo)2634 check_hashjoinable(RestrictInfo *restrictinfo)
2635 {
2636 Expr *clause = restrictinfo->clause;
2637 Oid opno;
2638 Node *leftarg;
2639
2640 if (restrictinfo->pseudoconstant)
2641 return;
2642 if (!is_opclause(clause))
2643 return;
2644 if (list_length(((OpExpr *) clause)->args) != 2)
2645 return;
2646
2647 opno = ((OpExpr *) clause)->opno;
2648 leftarg = linitial(((OpExpr *) clause)->args);
2649
2650 if (op_hashjoinable(opno, exprType(leftarg)) &&
2651 !contain_volatile_functions((Node *) clause))
2652 restrictinfo->hashjoinoperator = opno;
2653 }
2654