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