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