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