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