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