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