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