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