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