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