PostgreSQL Source Code  git master
analyzejoins.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * analyzejoins.c
4  * Routines for simplifying joins after initial query analysis
5  *
6  * While we do a great deal of join simplification in prep/prepjointree.c,
7  * certain optimizations cannot be performed at that stage for lack of
8  * detailed information about the query. The routines here are invoked
9  * after initsplan.c has done its work, and can do additional join removal
10  * and simplification steps based on the information extracted. The penalty
11  * is that we have to work harder to clean up after ourselves when we modify
12  * the query, since the derived data structures have to be updated too.
13  *
14  * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
15  * Portions Copyright (c) 1994, Regents of the University of California
16  *
17  *
18  * IDENTIFICATION
19  * src/backend/optimizer/plan/analyzejoins.c
20  *
21  *-------------------------------------------------------------------------
22  */
23 #include "postgres.h"
24 
25 #include "nodes/nodeFuncs.h"
26 #include "optimizer/clauses.h"
27 #include "optimizer/joininfo.h"
28 #include "optimizer/optimizer.h"
29 #include "optimizer/pathnode.h"
30 #include "optimizer/paths.h"
31 #include "optimizer/planmain.h"
32 #include "optimizer/tlist.h"
33 #include "utils/lsyscache.h"
34 
35 /* local functions */
36 static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
37 static void remove_rel_from_query(PlannerInfo *root, int relid,
38  Relids joinrelids);
39 static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
40 static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel);
41 static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel,
42  List *clause_list);
43 static Oid distinct_col_search(int colno, List *colnos, List *opids);
44 static bool is_innerrel_unique_for(PlannerInfo *root,
45  Relids joinrelids,
46  Relids outerrelids,
47  RelOptInfo *innerrel,
48  JoinType jointype,
49  List *restrictlist);
50 
51 
52 /*
53  * remove_useless_joins
54  * Check for relations that don't actually need to be joined at all,
55  * and remove them from the query.
56  *
57  * We are passed the current joinlist and return the updated list. Other
58  * data structures that have to be updated are accessible via "root".
59  */
60 List *
62 {
63  ListCell *lc;
64 
65  /*
66  * We are only interested in relations that are left-joined to, so we can
67  * scan the join_info_list to find them easily.
68  */
69 restart:
70  foreach(lc, root->join_info_list)
71  {
72  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
73  int innerrelid;
74  int nremoved;
75 
76  /* Skip if not removable */
77  if (!join_is_removable(root, sjinfo))
78  continue;
79 
80  /*
81  * Currently, join_is_removable can only succeed when the sjinfo's
82  * righthand is a single baserel. Remove that rel from the query and
83  * joinlist.
84  */
85  innerrelid = bms_singleton_member(sjinfo->min_righthand);
86 
87  remove_rel_from_query(root, innerrelid,
88  bms_union(sjinfo->min_lefthand,
89  sjinfo->min_righthand));
90 
91  /* We verify that exactly one reference gets removed from joinlist */
92  nremoved = 0;
93  joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
94  if (nremoved != 1)
95  elog(ERROR, "failed to find relation %d in joinlist", innerrelid);
96 
97  /*
98  * We can delete this SpecialJoinInfo from the list too, since it's no
99  * longer of interest. (Since we'll restart the foreach loop
100  * immediately, we don't bother with foreach_delete_current.)
101  */
103 
104  /*
105  * Restart the scan. This is necessary to ensure we find all
106  * removable joins independently of ordering of the join_info_list
107  * (note that removal of attr_needed bits may make a join appear
108  * removable that did not before).
109  */
110  goto restart;
111  }
112 
113  return joinlist;
114 }
115 
116 /*
117  * clause_sides_match_join
118  * Determine whether a join clause is of the right form to use in this join.
119  *
120  * We already know that the clause is a binary opclause referencing only the
121  * rels in the current join. The point here is to check whether it has the
122  * form "outerrel_expr op innerrel_expr" or "innerrel_expr op outerrel_expr",
123  * rather than mixing outer and inner vars on either side. If it matches,
124  * we set the transient flag outer_is_left to identify which side is which.
125  */
126 static inline bool
128  Relids innerrelids)
129 {
130  if (bms_is_subset(rinfo->left_relids, outerrelids) &&
131  bms_is_subset(rinfo->right_relids, innerrelids))
132  {
133  /* lefthand side is outer */
134  rinfo->outer_is_left = true;
135  return true;
136  }
137  else if (bms_is_subset(rinfo->left_relids, innerrelids) &&
138  bms_is_subset(rinfo->right_relids, outerrelids))
139  {
140  /* righthand side is outer */
141  rinfo->outer_is_left = false;
142  return true;
143  }
144  return false; /* no good for these input relations */
145 }
146 
147 /*
148  * join_is_removable
149  * Check whether we need not perform this special join at all, because
150  * it will just duplicate its left input.
151  *
152  * This is true for a left join for which the join condition cannot match
153  * more than one inner-side row. (There are other possibly interesting
154  * cases, but we don't have the infrastructure to prove them.) We also
155  * have to check that the inner side doesn't generate any variables needed
156  * above the join.
157  */
158 static bool
160 {
161  int innerrelid;
162  RelOptInfo *innerrel;
163  Relids joinrelids;
164  List *clause_list = NIL;
165  ListCell *l;
166  int attroff;
167 
168  /*
169  * Must be a non-delaying left join to a single baserel, else we aren't
170  * going to be able to do anything with it.
171  */
172  if (sjinfo->jointype != JOIN_LEFT ||
173  sjinfo->delay_upper_joins)
174  return false;
175 
176  if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
177  return false;
178 
179  innerrel = find_base_rel(root, innerrelid);
180 
181  /*
182  * Before we go to the effort of checking whether any innerrel variables
183  * are needed above the join, make a quick check to eliminate cases in
184  * which we will surely be unable to prove uniqueness of the innerrel.
185  */
186  if (!rel_supports_distinctness(root, innerrel))
187  return false;
188 
189  /* Compute the relid set for the join we are considering */
190  joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
191 
192  /*
193  * We can't remove the join if any inner-rel attributes are used above the
194  * join.
195  *
196  * Note that this test only detects use of inner-rel attributes in higher
197  * join conditions and the target list. There might be such attributes in
198  * pushed-down conditions at this join, too. We check that case below.
199  *
200  * As a micro-optimization, it seems better to start with max_attr and
201  * count down rather than starting with min_attr and counting up, on the
202  * theory that the system attributes are somewhat less likely to be wanted
203  * and should be tested last.
204  */
205  for (attroff = innerrel->max_attr - innerrel->min_attr;
206  attroff >= 0;
207  attroff--)
208  {
209  if (!bms_is_subset(innerrel->attr_needed[attroff], joinrelids))
210  return false;
211  }
212 
213  /*
214  * Similarly check that the inner rel isn't needed by any PlaceHolderVars
215  * that will be used above the join. We only need to fail if such a PHV
216  * actually references some inner-rel attributes; but the correct check
217  * for that is relatively expensive, so we first check against ph_eval_at,
218  * which must mention the inner rel if the PHV uses any inner-rel attrs as
219  * non-lateral references. Note that if the PHV's syntactic scope is just
220  * the inner rel, we can't drop the rel even if the PHV is variable-free.
221  */
222  foreach(l, root->placeholder_list)
223  {
224  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
225 
226  if (bms_overlap(phinfo->ph_lateral, innerrel->relids))
227  return false; /* it references innerrel laterally */
228  if (bms_is_subset(phinfo->ph_needed, joinrelids))
229  continue; /* PHV is not used above the join */
230  if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
231  continue; /* it definitely doesn't reference innerrel */
232  if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids))
233  return false; /* there isn't any other place to eval PHV */
234  if (bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
235  innerrel->relids))
236  return false; /* it does reference innerrel */
237  }
238 
239  /*
240  * Search for mergejoinable clauses that constrain the inner rel against
241  * either the outer rel or a pseudoconstant. If an operator is
242  * mergejoinable then it behaves like equality for some btree opclass, so
243  * it's what we want. The mergejoinability test also eliminates clauses
244  * containing volatile functions, which we couldn't depend on.
245  */
246  foreach(l, innerrel->joininfo)
247  {
248  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
249 
250  /*
251  * If it's not a join clause for this outer join, we can't use it.
252  * Note that if the clause is pushed-down, then it is logically from
253  * above the outer join, even if it references no other rels (it might
254  * be from WHERE, for example).
255  */
256  if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
257  {
258  /*
259  * If such a clause actually references the inner rel then join
260  * removal has to be disallowed. We have to check this despite
261  * the previous attr_needed checks because of the possibility of
262  * pushed-down clauses referencing the rel.
263  */
264  if (bms_is_member(innerrelid, restrictinfo->clause_relids))
265  return false;
266  continue; /* else, ignore; not useful here */
267  }
268 
269  /* Ignore if it's not a mergejoinable clause */
270  if (!restrictinfo->can_join ||
271  restrictinfo->mergeopfamilies == NIL)
272  continue; /* not mergejoinable */
273 
274  /*
275  * Check if clause has the form "outer op inner" or "inner op outer",
276  * and if so mark which side is inner.
277  */
278  if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
279  innerrel->relids))
280  continue; /* no good for these input relations */
281 
282  /* OK, add to list */
283  clause_list = lappend(clause_list, restrictinfo);
284  }
285 
286  /*
287  * Now that we have the relevant equality join clauses, try to prove the
288  * innerrel distinct.
289  */
290  if (rel_is_distinct_for(root, innerrel, clause_list))
291  return true;
292 
293  /*
294  * Some day it would be nice to check for other methods of establishing
295  * distinctness.
296  */
297  return false;
298 }
299 
300 
301 /*
302  * Remove the target relid from the planner's data structures, having
303  * determined that there is no need to include it in the query.
304  *
305  * We are not terribly thorough here. We must make sure that the rel is
306  * no longer treated as a baserel, and that attributes of other baserels
307  * are no longer marked as being needed at joins involving this rel.
308  * Also, join quals involving the rel have to be removed from the joininfo
309  * lists, but only if they belong to the outer join identified by joinrelids.
310  */
311 static void
312 remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids)
313 {
314  RelOptInfo *rel = find_base_rel(root, relid);
315  List *joininfos;
316  Index rti;
317  ListCell *l;
318 
319  /*
320  * Mark the rel as "dead" to show it is no longer part of the join tree.
321  * (Removing it from the baserel array altogether seems too risky.)
322  */
323  rel->reloptkind = RELOPT_DEADREL;
324 
325  /*
326  * Remove references to the rel from other baserels' attr_needed arrays.
327  */
328  for (rti = 1; rti < root->simple_rel_array_size; rti++)
329  {
330  RelOptInfo *otherrel = root->simple_rel_array[rti];
331  int attroff;
332 
333  /* there may be empty slots corresponding to non-baserel RTEs */
334  if (otherrel == NULL)
335  continue;
336 
337  Assert(otherrel->relid == rti); /* sanity check on array */
338 
339  /* no point in processing target rel itself */
340  if (otherrel == rel)
341  continue;
342 
343  for (attroff = otherrel->max_attr - otherrel->min_attr;
344  attroff >= 0;
345  attroff--)
346  {
347  otherrel->attr_needed[attroff] =
348  bms_del_member(otherrel->attr_needed[attroff], relid);
349  }
350  }
351 
352  /*
353  * Likewise remove references from SpecialJoinInfo data structures.
354  *
355  * This is relevant in case the outer join we're deleting is nested inside
356  * other outer joins: the upper joins' relid sets have to be adjusted. The
357  * RHS of the target outer join will be made empty here, but that's OK
358  * since caller will delete that SpecialJoinInfo entirely.
359  */
360  foreach(l, root->join_info_list)
361  {
362  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
363 
364  sjinfo->min_lefthand = bms_del_member(sjinfo->min_lefthand, relid);
365  sjinfo->min_righthand = bms_del_member(sjinfo->min_righthand, relid);
366  sjinfo->syn_lefthand = bms_del_member(sjinfo->syn_lefthand, relid);
367  sjinfo->syn_righthand = bms_del_member(sjinfo->syn_righthand, relid);
368  }
369 
370  /*
371  * Likewise remove references from PlaceHolderVar data structures,
372  * removing any no-longer-needed placeholders entirely.
373  *
374  * Removal is a bit trickier than it might seem: we can remove PHVs that
375  * are used at the target rel and/or in the join qual, but not those that
376  * are used at join partner rels or above the join. It's not that easy to
377  * distinguish PHVs used at partner rels from those used in the join qual,
378  * since they will both have ph_needed sets that are subsets of
379  * joinrelids. However, a PHV used at a partner rel could not have the
380  * target rel in ph_eval_at, so we check that while deciding whether to
381  * remove or just update the PHV. There is no corresponding test in
382  * join_is_removable because it doesn't need to distinguish those cases.
383  */
384  foreach(l, root->placeholder_list)
385  {
386  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
387 
388  Assert(!bms_is_member(relid, phinfo->ph_lateral));
389  if (bms_is_subset(phinfo->ph_needed, joinrelids) &&
390  bms_is_member(relid, phinfo->ph_eval_at))
391  {
393  l);
394  root->placeholder_array[phinfo->phid] = NULL;
395  }
396  else
397  {
398  phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
399  Assert(!bms_is_empty(phinfo->ph_eval_at));
400  phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid);
401  }
402  }
403 
404  /*
405  * Remove any joinquals referencing the rel from the joininfo lists.
406  *
407  * In some cases, a joinqual has to be put back after deleting its
408  * reference to the target rel. This can occur for pseudoconstant and
409  * outerjoin-delayed quals, which can get marked as requiring the rel in
410  * order to force them to be evaluated at or above the join. We can't
411  * just discard them, though. Only quals that logically belonged to the
412  * outer join being discarded should be removed from the query.
413  *
414  * We must make a copy of the rel's old joininfo list before starting the
415  * loop, because otherwise remove_join_clause_from_rels would destroy the
416  * list while we're scanning it.
417  */
418  joininfos = list_copy(rel->joininfo);
419  foreach(l, joininfos)
420  {
421  RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
422 
423  remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
424 
425  if (RINFO_IS_PUSHED_DOWN(rinfo, joinrelids))
426  {
427  /* Recheck that qual doesn't actually reference the target rel */
428  Assert(!bms_is_member(relid, rinfo->clause_relids));
429 
430  /*
431  * The required_relids probably aren't shared with anything else,
432  * but let's copy them just to be sure.
433  */
434  rinfo->required_relids = bms_copy(rinfo->required_relids);
436  relid);
437  distribute_restrictinfo_to_rels(root, rinfo);
438  }
439  }
440 
441  /*
442  * There may be references to the rel in root->fkey_list, but if so,
443  * match_foreign_keys_to_quals() will get rid of them.
444  */
445 }
446 
447 /*
448  * Remove any occurrences of the target relid from a joinlist structure.
449  *
450  * It's easiest to build a whole new list structure, so we handle it that
451  * way. Efficiency is not a big deal here.
452  *
453  * *nremoved is incremented by the number of occurrences removed (there
454  * should be exactly one, but the caller checks that).
455  */
456 static List *
457 remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
458 {
459  List *result = NIL;
460  ListCell *jl;
461 
462  foreach(jl, joinlist)
463  {
464  Node *jlnode = (Node *) lfirst(jl);
465 
466  if (IsA(jlnode, RangeTblRef))
467  {
468  int varno = ((RangeTblRef *) jlnode)->rtindex;
469 
470  if (varno == relid)
471  (*nremoved)++;
472  else
473  result = lappend(result, jlnode);
474  }
475  else if (IsA(jlnode, List))
476  {
477  /* Recurse to handle subproblem */
478  List *sublist;
479 
480  sublist = remove_rel_from_joinlist((List *) jlnode,
481  relid, nremoved);
482  /* Avoid including empty sub-lists in the result */
483  if (sublist)
484  result = lappend(result, sublist);
485  }
486  else
487  {
488  elog(ERROR, "unrecognized joinlist node type: %d",
489  (int) nodeTag(jlnode));
490  }
491  }
492 
493  return result;
494 }
495 
496 
497 /*
498  * reduce_unique_semijoins
499  * Check for semijoins that can be simplified to plain inner joins
500  * because the inner relation is provably unique for the join clauses.
501  *
502  * Ideally this would happen during reduce_outer_joins, but we don't have
503  * enough information at that point.
504  *
505  * To perform the strength reduction when applicable, we need only delete
506  * the semijoin's SpecialJoinInfo from root->join_info_list. (We don't
507  * bother fixing the join type attributed to it in the query jointree,
508  * since that won't be consulted again.)
509  */
510 void
512 {
513  ListCell *lc;
514 
515  /*
516  * Scan the join_info_list to find semijoins.
517  */
518  foreach(lc, root->join_info_list)
519  {
520  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
521  int innerrelid;
522  RelOptInfo *innerrel;
523  Relids joinrelids;
524  List *restrictlist;
525 
526  /*
527  * Must be a non-delaying semijoin to a single baserel, else we aren't
528  * going to be able to do anything with it. (It's probably not
529  * possible for delay_upper_joins to be set on a semijoin, but we
530  * might as well check.)
531  */
532  if (sjinfo->jointype != JOIN_SEMI ||
533  sjinfo->delay_upper_joins)
534  continue;
535 
536  if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
537  continue;
538 
539  innerrel = find_base_rel(root, innerrelid);
540 
541  /*
542  * Before we trouble to run generate_join_implied_equalities, make a
543  * quick check to eliminate cases in which we will surely be unable to
544  * prove uniqueness of the innerrel.
545  */
546  if (!rel_supports_distinctness(root, innerrel))
547  continue;
548 
549  /* Compute the relid set for the join we are considering */
550  joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
551 
552  /*
553  * Since we're only considering a single-rel RHS, any join clauses it
554  * has must be clauses linking it to the semijoin's min_lefthand. We
555  * can also consider EC-derived join clauses.
556  */
557  restrictlist =
559  joinrelids,
560  sjinfo->min_lefthand,
561  innerrel),
562  innerrel->joininfo);
563 
564  /* Test whether the innerrel is unique for those clauses. */
565  if (!innerrel_is_unique(root,
566  joinrelids, sjinfo->min_lefthand, innerrel,
567  JOIN_SEMI, restrictlist, true))
568  continue;
569 
570  /* OK, remove the SpecialJoinInfo from the list. */
572  }
573 }
574 
575 
576 /*
577  * rel_supports_distinctness
578  * Could the relation possibly be proven distinct on some set of columns?
579  *
580  * This is effectively a pre-checking function for rel_is_distinct_for().
581  * It must return true if rel_is_distinct_for() could possibly return true
582  * with this rel, but it should not expend a lot of cycles. The idea is
583  * that callers can avoid doing possibly-expensive processing to compute
584  * rel_is_distinct_for()'s argument lists if the call could not possibly
585  * succeed.
586  */
587 static bool
589 {
590  /* We only know about baserels ... */
591  if (rel->reloptkind != RELOPT_BASEREL)
592  return false;
593  if (rel->rtekind == RTE_RELATION)
594  {
595  /*
596  * For a plain relation, we only know how to prove uniqueness by
597  * reference to unique indexes. Make sure there's at least one
598  * suitable unique index. It must be immediately enforced, and if
599  * it's a partial index, it must match the query. (Keep these
600  * conditions in sync with relation_has_unique_index_for!)
601  */
602  ListCell *lc;
603 
604  foreach(lc, rel->indexlist)
605  {
606  IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
607 
608  if (ind->unique && ind->immediate &&
609  (ind->indpred == NIL || ind->predOK))
610  return true;
611  }
612  }
613  else if (rel->rtekind == RTE_SUBQUERY)
614  {
615  Query *subquery = root->simple_rte_array[rel->relid]->subquery;
616 
617  /* Check if the subquery has any qualities that support distinctness */
618  if (query_supports_distinctness(subquery))
619  return true;
620  }
621  /* We have no proof rules for any other rtekinds. */
622  return false;
623 }
624 
625 /*
626  * rel_is_distinct_for
627  * Does the relation return only distinct rows according to clause_list?
628  *
629  * clause_list is a list of join restriction clauses involving this rel and
630  * some other one. Return true if no two rows emitted by this rel could
631  * possibly join to the same row of the other rel.
632  *
633  * The caller must have already determined that each condition is a
634  * mergejoinable equality with an expression in this relation on one side, and
635  * an expression not involving this relation on the other. The transient
636  * outer_is_left flag is used to identify which side references this relation:
637  * left side if outer_is_left is false, right side if it is true.
638  *
639  * Note that the passed-in clause_list may be destructively modified! This
640  * is OK for current uses, because the clause_list is built by the caller for
641  * the sole purpose of passing to this function.
642  */
643 static bool
644 rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list)
645 {
646  /*
647  * We could skip a couple of tests here if we assume all callers checked
648  * rel_supports_distinctness first, but it doesn't seem worth taking any
649  * risk for.
650  */
651  if (rel->reloptkind != RELOPT_BASEREL)
652  return false;
653  if (rel->rtekind == RTE_RELATION)
654  {
655  /*
656  * Examine the indexes to see if we have a matching unique index.
657  * relation_has_unique_index_for automatically adds any usable
658  * restriction clauses for the rel, so we needn't do that here.
659  */
660  if (relation_has_unique_index_for(root, rel, clause_list, NIL, NIL))
661  return true;
662  }
663  else if (rel->rtekind == RTE_SUBQUERY)
664  {
665  Index relid = rel->relid;
666  Query *subquery = root->simple_rte_array[relid]->subquery;
667  List *colnos = NIL;
668  List *opids = NIL;
669  ListCell *l;
670 
671  /*
672  * Build the argument lists for query_is_distinct_for: a list of
673  * output column numbers that the query needs to be distinct over, and
674  * a list of equality operators that the output columns need to be
675  * distinct according to.
676  *
677  * (XXX we are not considering restriction clauses attached to the
678  * subquery; is that worth doing?)
679  */
680  foreach(l, clause_list)
681  {
683  Oid op;
684  Var *var;
685 
686  /*
687  * Get the equality operator we need uniqueness according to.
688  * (This might be a cross-type operator and thus not exactly the
689  * same operator the subquery would consider; that's all right
690  * since query_is_distinct_for can resolve such cases.) The
691  * caller's mergejoinability test should have selected only
692  * OpExprs.
693  */
694  op = castNode(OpExpr, rinfo->clause)->opno;
695 
696  /* caller identified the inner side for us */
697  if (rinfo->outer_is_left)
698  var = (Var *) get_rightop(rinfo->clause);
699  else
700  var = (Var *) get_leftop(rinfo->clause);
701 
702  /*
703  * We may ignore any RelabelType node above the operand. (There
704  * won't be more than one, since eval_const_expressions() has been
705  * applied already.)
706  */
707  if (var && IsA(var, RelabelType))
708  var = (Var *) ((RelabelType *) var)->arg;
709 
710  /*
711  * If inner side isn't a Var referencing a subquery output column,
712  * this clause doesn't help us.
713  */
714  if (!var || !IsA(var, Var) ||
715  var->varno != relid || var->varlevelsup != 0)
716  continue;
717 
718  colnos = lappend_int(colnos, var->varattno);
719  opids = lappend_oid(opids, op);
720  }
721 
722  if (query_is_distinct_for(subquery, colnos, opids))
723  return true;
724  }
725  return false;
726 }
727 
728 
729 /*
730  * query_supports_distinctness - could the query possibly be proven distinct
731  * on some set of output columns?
732  *
733  * This is effectively a pre-checking function for query_is_distinct_for().
734  * It must return true if query_is_distinct_for() could possibly return true
735  * with this query, but it should not expend a lot of cycles. The idea is
736  * that callers can avoid doing possibly-expensive processing to compute
737  * query_is_distinct_for()'s argument lists if the call could not possibly
738  * succeed.
739  */
740 bool
742 {
743  /* SRFs break distinctness except with DISTINCT, see below */
744  if (query->hasTargetSRFs && query->distinctClause == NIL)
745  return false;
746 
747  /* check for features we can prove distinctness with */
748  if (query->distinctClause != NIL ||
749  query->groupClause != NIL ||
750  query->groupingSets != NIL ||
751  query->hasAggs ||
752  query->havingQual ||
753  query->setOperations)
754  return true;
755 
756  return false;
757 }
758 
759 /*
760  * query_is_distinct_for - does query never return duplicates of the
761  * specified columns?
762  *
763  * query is a not-yet-planned subquery (in current usage, it's always from
764  * a subquery RTE, which the planner avoids scribbling on).
765  *
766  * colnos is an integer list of output column numbers (resno's). We are
767  * interested in whether rows consisting of just these columns are certain
768  * to be distinct. "Distinctness" is defined according to whether the
769  * corresponding upper-level equality operators listed in opids would think
770  * the values are distinct. (Note: the opids entries could be cross-type
771  * operators, and thus not exactly the equality operators that the subquery
772  * would use itself. We use equality_ops_are_compatible() to check
773  * compatibility. That looks at btree or hash opfamily membership, and so
774  * should give trustworthy answers for all operators that we might need
775  * to deal with here.)
776  */
777 bool
778 query_is_distinct_for(Query *query, List *colnos, List *opids)
779 {
780  ListCell *l;
781  Oid opid;
782 
783  Assert(list_length(colnos) == list_length(opids));
784 
785  /*
786  * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
787  * columns in the DISTINCT clause appear in colnos and operator semantics
788  * match. This is true even if there are SRFs in the DISTINCT columns or
789  * elsewhere in the tlist.
790  */
791  if (query->distinctClause)
792  {
793  foreach(l, query->distinctClause)
794  {
795  SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
797  query->targetList);
798 
799  opid = distinct_col_search(tle->resno, colnos, opids);
800  if (!OidIsValid(opid) ||
801  !equality_ops_are_compatible(opid, sgc->eqop))
802  break; /* exit early if no match */
803  }
804  if (l == NULL) /* had matches for all? */
805  return true;
806  }
807 
808  /*
809  * Otherwise, a set-returning function in the query's targetlist can
810  * result in returning duplicate rows, despite any grouping that might
811  * occur before tlist evaluation. (If all tlist SRFs are within GROUP BY
812  * columns, it would be safe because they'd be expanded before grouping.
813  * But it doesn't currently seem worth the effort to check for that.)
814  */
815  if (query->hasTargetSRFs)
816  return false;
817 
818  /*
819  * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
820  * the grouped columns appear in colnos and operator semantics match.
821  */
822  if (query->groupClause && !query->groupingSets)
823  {
824  foreach(l, query->groupClause)
825  {
826  SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
828  query->targetList);
829 
830  opid = distinct_col_search(tle->resno, colnos, opids);
831  if (!OidIsValid(opid) ||
832  !equality_ops_are_compatible(opid, sgc->eqop))
833  break; /* exit early if no match */
834  }
835  if (l == NULL) /* had matches for all? */
836  return true;
837  }
838  else if (query->groupingSets)
839  {
840  /*
841  * If we have grouping sets with expressions, we probably don't have
842  * uniqueness and analysis would be hard. Punt.
843  */
844  if (query->groupClause)
845  return false;
846 
847  /*
848  * If we have no groupClause (therefore no grouping expressions), we
849  * might have one or many empty grouping sets. If there's just one,
850  * then we're returning only one row and are certainly unique. But
851  * otherwise, we know we're certainly not unique.
852  */
853  if (list_length(query->groupingSets) == 1 &&
854  ((GroupingSet *) linitial(query->groupingSets))->kind == GROUPING_SET_EMPTY)
855  return true;
856  else
857  return false;
858  }
859  else
860  {
861  /*
862  * If we have no GROUP BY, but do have aggregates or HAVING, then the
863  * result is at most one row so it's surely unique, for any operators.
864  */
865  if (query->hasAggs || query->havingQual)
866  return true;
867  }
868 
869  /*
870  * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
871  * except with ALL.
872  */
873  if (query->setOperations)
874  {
876 
877  Assert(topop->op != SETOP_NONE);
878 
879  if (!topop->all)
880  {
881  ListCell *lg;
882 
883  /* We're good if all the nonjunk output columns are in colnos */
884  lg = list_head(topop->groupClauses);
885  foreach(l, query->targetList)
886  {
887  TargetEntry *tle = (TargetEntry *) lfirst(l);
888  SortGroupClause *sgc;
889 
890  if (tle->resjunk)
891  continue; /* ignore resjunk columns */
892 
893  /* non-resjunk columns should have grouping clauses */
894  Assert(lg != NULL);
895  sgc = (SortGroupClause *) lfirst(lg);
896  lg = lnext(topop->groupClauses, lg);
897 
898  opid = distinct_col_search(tle->resno, colnos, opids);
899  if (!OidIsValid(opid) ||
900  !equality_ops_are_compatible(opid, sgc->eqop))
901  break; /* exit early if no match */
902  }
903  if (l == NULL) /* had matches for all? */
904  return true;
905  }
906  }
907 
908  /*
909  * XXX Are there any other cases in which we can easily see the result
910  * must be distinct?
911  *
912  * If you do add more smarts to this function, be sure to update
913  * query_supports_distinctness() to match.
914  */
915 
916  return false;
917 }
918 
919 /*
920  * distinct_col_search - subroutine for query_is_distinct_for
921  *
922  * If colno is in colnos, return the corresponding element of opids,
923  * else return InvalidOid. (Ordinarily colnos would not contain duplicates,
924  * but if it does, we arbitrarily select the first match.)
925  */
926 static Oid
927 distinct_col_search(int colno, List *colnos, List *opids)
928 {
929  ListCell *lc1,
930  *lc2;
931 
932  forboth(lc1, colnos, lc2, opids)
933  {
934  if (colno == lfirst_int(lc1))
935  return lfirst_oid(lc2);
936  }
937  return InvalidOid;
938 }
939 
940 
941 /*
942  * innerrel_is_unique
943  * Check if the innerrel provably contains at most one tuple matching any
944  * tuple from the outerrel, based on join clauses in the 'restrictlist'.
945  *
946  * We need an actual RelOptInfo for the innerrel, but it's sufficient to
947  * identify the outerrel by its Relids. This asymmetry supports use of this
948  * function before joinrels have been built. (The caller is expected to
949  * also supply the joinrelids, just to save recalculating that.)
950  *
951  * The proof must be made based only on clauses that will be "joinquals"
952  * rather than "otherquals" at execution. For an inner join there's no
953  * difference; but if the join is outer, we must ignore pushed-down quals,
954  * as those will become "otherquals". Note that this means the answer might
955  * vary depending on whether IS_OUTER_JOIN(jointype); since we cache the
956  * answer without regard to that, callers must take care not to call this
957  * with jointypes that would be classified differently by IS_OUTER_JOIN().
958  *
959  * The actual proof is undertaken by is_innerrel_unique_for(); this function
960  * is a frontend that is mainly concerned with caching the answers.
961  * In particular, the force_cache argument allows overriding the internal
962  * heuristic about whether to cache negative answers; it should be "true"
963  * if making an inquiry that is not part of the normal bottom-up join search
964  * sequence.
965  */
966 bool
968  Relids joinrelids,
969  Relids outerrelids,
970  RelOptInfo *innerrel,
971  JoinType jointype,
972  List *restrictlist,
973  bool force_cache)
974 {
975  MemoryContext old_context;
976  ListCell *lc;
977 
978  /* Certainly can't prove uniqueness when there are no joinclauses */
979  if (restrictlist == NIL)
980  return false;
981 
982  /*
983  * Make a quick check to eliminate cases in which we will surely be unable
984  * to prove uniqueness of the innerrel.
985  */
986  if (!rel_supports_distinctness(root, innerrel))
987  return false;
988 
989  /*
990  * Query the cache to see if we've managed to prove that innerrel is
991  * unique for any subset of this outerrel. We don't need an exact match,
992  * as extra outerrels can't make the innerrel any less unique (or more
993  * formally, the restrictlist for a join to a superset outerrel must be a
994  * superset of the conditions we successfully used before).
995  */
996  foreach(lc, innerrel->unique_for_rels)
997  {
998  Relids unique_for_rels = (Relids) lfirst(lc);
999 
1000  if (bms_is_subset(unique_for_rels, outerrelids))
1001  return true; /* Success! */
1002  }
1003 
1004  /*
1005  * Conversely, we may have already determined that this outerrel, or some
1006  * superset thereof, cannot prove this innerrel to be unique.
1007  */
1008  foreach(lc, innerrel->non_unique_for_rels)
1009  {
1010  Relids unique_for_rels = (Relids) lfirst(lc);
1011 
1012  if (bms_is_subset(outerrelids, unique_for_rels))
1013  return false;
1014  }
1015 
1016  /* No cached information, so try to make the proof. */
1017  if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
1018  jointype, restrictlist))
1019  {
1020  /*
1021  * Cache the positive result for future probes, being sure to keep it
1022  * in the planner_cxt even if we are working in GEQO.
1023  *
1024  * Note: one might consider trying to isolate the minimal subset of
1025  * the outerrels that proved the innerrel unique. But it's not worth
1026  * the trouble, because the planner builds up joinrels incrementally
1027  * and so we'll see the minimally sufficient outerrels before any
1028  * supersets of them anyway.
1029  */
1030  old_context = MemoryContextSwitchTo(root->planner_cxt);
1031  innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
1032  bms_copy(outerrelids));
1033  MemoryContextSwitchTo(old_context);
1034 
1035  return true; /* Success! */
1036  }
1037  else
1038  {
1039  /*
1040  * None of the join conditions for outerrel proved innerrel unique, so
1041  * we can safely reject this outerrel or any subset of it in future
1042  * checks.
1043  *
1044  * However, in normal planning mode, caching this knowledge is totally
1045  * pointless; it won't be queried again, because we build up joinrels
1046  * from smaller to larger. It is useful in GEQO mode, where the
1047  * knowledge can be carried across successive planning attempts; and
1048  * it's likely to be useful when using join-search plugins, too. Hence
1049  * cache when join_search_private is non-NULL. (Yeah, that's a hack,
1050  * but it seems reasonable.)
1051  *
1052  * Also, allow callers to override that heuristic and force caching;
1053  * that's useful for reduce_unique_semijoins, which calls here before
1054  * the normal join search starts.
1055  */
1056  if (force_cache || root->join_search_private)
1057  {
1058  old_context = MemoryContextSwitchTo(root->planner_cxt);
1059  innerrel->non_unique_for_rels =
1060  lappend(innerrel->non_unique_for_rels,
1061  bms_copy(outerrelids));
1062  MemoryContextSwitchTo(old_context);
1063  }
1064 
1065  return false;
1066  }
1067 }
1068 
1069 /*
1070  * is_innerrel_unique_for
1071  * Check if the innerrel provably contains at most one tuple matching any
1072  * tuple from the outerrel, based on join clauses in the 'restrictlist'.
1073  */
1074 static bool
1076  Relids joinrelids,
1077  Relids outerrelids,
1078  RelOptInfo *innerrel,
1079  JoinType jointype,
1080  List *restrictlist)
1081 {
1082  List *clause_list = NIL;
1083  ListCell *lc;
1084 
1085  /*
1086  * Search for mergejoinable clauses that constrain the inner rel against
1087  * the outer rel. If an operator is mergejoinable then it behaves like
1088  * equality for some btree opclass, so it's what we want. The
1089  * mergejoinability test also eliminates clauses containing volatile
1090  * functions, which we couldn't depend on.
1091  */
1092  foreach(lc, restrictlist)
1093  {
1094  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
1095 
1096  /*
1097  * As noted above, if it's a pushed-down clause and we're at an outer
1098  * join, we can't use it.
1099  */
1100  if (IS_OUTER_JOIN(jointype) &&
1101  RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
1102  continue;
1103 
1104  /* Ignore if it's not a mergejoinable clause */
1105  if (!restrictinfo->can_join ||
1106  restrictinfo->mergeopfamilies == NIL)
1107  continue; /* not mergejoinable */
1108 
1109  /*
1110  * Check if clause has the form "outer op inner" or "inner op outer",
1111  * and if so mark which side is inner.
1112  */
1113  if (!clause_sides_match_join(restrictinfo, outerrelids,
1114  innerrel->relids))
1115  continue; /* no good for these input relations */
1116 
1117  /* OK, add to list */
1118  clause_list = lappend(clause_list, restrictinfo);
1119  }
1120 
1121  /* Let rel_is_distinct_for() do the hard work */
1122  return rel_is_distinct_for(root, innerrel, clause_list);
1123 }
List * remove_useless_joins(PlannerInfo *root, List *joinlist)
Definition: analyzejoins.c:61
static bool clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
Definition: analyzejoins.c:127
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition: analyzejoins.c:967
static void remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids)
Definition: analyzejoins.c:312
static List * remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
Definition: analyzejoins.c:457
bool query_is_distinct_for(Query *query, List *colnos, List *opids)
Definition: analyzejoins.c:778
static Oid distinct_col_search(int colno, List *colnos, List *opids)
Definition: analyzejoins.c:927
bool query_supports_distinctness(Query *query)
Definition: analyzejoins.c:741
static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list)
Definition: analyzejoins.c:644
static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
Definition: analyzejoins.c:159
void reduce_unique_semijoins(PlannerInfo *root)
Definition: analyzejoins.c:511
static bool is_innerrel_unique_for(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist)
static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
Definition: analyzejoins.c:588
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:316
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:580
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:428
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:226
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:776
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:704
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:495
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:74
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:618
unsigned int Index
Definition: c.h:550
#define OidIsValid(objectId)
Definition: c.h:711
#define ERROR
Definition: elog.h:35
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1394
bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist)
Definition: indxpath.c:3494
void distribute_restrictinfo_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: initsplan.c:2181
void remove_join_clause_from_rels(PlannerInfo *root, RestrictInfo *restrictinfo, Relids join_relids)
Definition: joininfo.c:122
Assert(fmt[strlen(fmt) - 1] !='\n')
List * lappend(List *list, void *datum)
Definition: list.c:338
List * lappend_int(List *list, int datum)
Definition: list.c:356
List * lappend_oid(List *list, Oid datum)
Definition: list.c:374
List * list_copy(const List *oldlist)
Definition: list.c:1572
List * list_delete_cell(List *list, ListCell *cell)
Definition: list.c:840
List * list_concat(List *list1, const List *list2)
Definition: list.c:560
bool equality_ops_are_compatible(Oid opno1, Oid opno2)
Definition: lsyscache.c:697
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:93
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:81
#define IsA(nodeptr, _type_)
Definition: nodes.h:168
#define nodeTag(nodeptr)
Definition: nodes.h:122
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:336
#define castNode(_type_, nodeptr)
Definition: nodes.h:186
JoinType
Definition: nodes.h:288
@ JOIN_SEMI
Definition: nodes.h:307
@ JOIN_LEFT
Definition: nodes.h:294
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:135
@ GROUPING_SET_EMPTY
Definition: parsenodes.h:1379
@ SETOP_NONE
Definition: parsenodes.h:1718
@ RTE_SUBQUERY
Definition: parsenodes.h:1012
@ RTE_RELATION
Definition: parsenodes.h:1011
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2566
Bitmapset * Relids
Definition: pathnodes.h:30
@ RELOPT_BASEREL
Definition: pathnodes.h:776
@ RELOPT_DEADREL
Definition: pathnodes.h:782
#define lfirst(lc)
Definition: pg_list.h:170
#define lfirst_node(type, lc)
Definition: pg_list.h:174
static int list_length(const List *l)
Definition: pg_list.h:150
#define NIL
Definition: pg_list.h:66
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:465
#define lfirst_int(lc)
Definition: pg_list.h:171
static ListCell * list_head(const List *l)
Definition: pg_list.h:126
#define linitial(l)
Definition: pg_list.h:176
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:341
#define lfirst_oid(lc)
Definition: pg_list.h:172
#define foreach_delete_current(lst, cell)
Definition: pg_list.h:388
#define InvalidOid
Definition: postgres_ext.h:36
unsigned int Oid
Definition: postgres_ext.h:31
RelOptInfo * find_base_rel(PlannerInfo *root, int relid)
Definition: relnode.c:360
Definition: pg_list.h:52
Definition: nodes.h:118
Relids ph_lateral
Definition: pathnodes.h:2876
Relids ph_needed
Definition: pathnodes.h:2879
Relids ph_eval_at
Definition: pathnodes.h:2873
PlaceHolderVar * ph_var
Definition: pathnodes.h:2870
int simple_rel_array_size
Definition: pathnodes.h:229
List * placeholder_list
Definition: pathnodes.h:361
List * join_info_list
Definition: pathnodes.h:330
Node * setOperations
Definition: parsenodes.h:189
bool hasTargetSRFs
Definition: parsenodes.h:143
List * groupClause
Definition: parsenodes.h:170
Node * havingQual
Definition: parsenodes.h:175
bool hasAggs
Definition: parsenodes.h:141
List * targetList
Definition: parsenodes.h:162
List * groupingSets
Definition: parsenodes.h:173
List * distinctClause
Definition: parsenodes.h:179
List * joininfo
Definition: pathnodes.h:936
Relids relids
Definition: pathnodes.h:821
Index relid
Definition: pathnodes.h:868
List * unique_for_rels
Definition: pathnodes.h:922
RelOptKind reloptkind
Definition: pathnodes.h:815
List * indexlist
Definition: pathnodes.h:886
List * non_unique_for_rels
Definition: pathnodes.h:924
AttrNumber max_attr
Definition: pathnodes.h:876
AttrNumber min_attr
Definition: pathnodes.h:874
RTEKind rtekind
Definition: pathnodes.h:872
Relids required_relids
Definition: pathnodes.h:2459
Expr * clause
Definition: pathnodes.h:2432
SetOperation op
Definition: parsenodes.h:1796
Relids syn_lefthand
Definition: pathnodes.h:2702
Relids min_righthand
Definition: pathnodes.h:2701
JoinType jointype
Definition: pathnodes.h:2704
Relids min_lefthand
Definition: pathnodes.h:2700
Relids syn_righthand
Definition: pathnodes.h:2703
bool delay_upper_joins
Definition: pathnodes.h:2706
AttrNumber resno
Definition: primnodes.h:1556
bool resjunk
Definition: primnodes.h:1562
Definition: primnodes.h:205
AttrNumber varattno
Definition: primnodes.h:217
int varno
Definition: primnodes.h:212
Index varlevelsup
Definition: primnodes.h:230
TargetEntry * get_sortgroupclause_tle(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:367
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:100