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