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