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