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-2023, 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/restrictinfo.h"
33 #include "optimizer/tlist.h"
34 #include "utils/lsyscache.h"
35 
36 /* local functions */
37 static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
38 static void remove_rel_from_query(PlannerInfo *root, int relid,
39  SpecialJoinInfo *sjinfo);
41  int relid, int ojrelid);
43  int relid, int ojrelid);
44 static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
45 static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel);
46 static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel,
47  List *clause_list);
48 static Oid distinct_col_search(int colno, List *colnos, List *opids);
49 static bool is_innerrel_unique_for(PlannerInfo *root,
50  Relids joinrelids,
51  Relids outerrelids,
52  RelOptInfo *innerrel,
53  JoinType jointype,
54  List *restrictlist);
55 
56 
57 /*
58  * remove_useless_joins
59  * Check for relations that don't actually need to be joined at all,
60  * and remove them from the query.
61  *
62  * We are passed the current joinlist and return the updated list. Other
63  * data structures that have to be updated are accessible via "root".
64  */
65 List *
67 {
68  ListCell *lc;
69 
70  /*
71  * We are only interested in relations that are left-joined to, so we can
72  * scan the join_info_list to find them easily.
73  */
74 restart:
75  foreach(lc, root->join_info_list)
76  {
77  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
78  int innerrelid;
79  int nremoved;
80 
81  /* Skip if not removable */
82  if (!join_is_removable(root, sjinfo))
83  continue;
84 
85  /*
86  * Currently, join_is_removable can only succeed when the sjinfo's
87  * righthand is a single baserel. Remove that rel from the query and
88  * joinlist.
89  */
90  innerrelid = bms_singleton_member(sjinfo->min_righthand);
91 
92  remove_rel_from_query(root, innerrelid, sjinfo);
93 
94  /* We verify that exactly one reference gets removed from joinlist */
95  nremoved = 0;
96  joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
97  if (nremoved != 1)
98  elog(ERROR, "failed to find relation %d in joinlist", innerrelid);
99 
100  /*
101  * We can delete this SpecialJoinInfo from the list too, since it's no
102  * longer of interest. (Since we'll restart the foreach loop
103  * immediately, we don't bother with foreach_delete_current.)
104  */
106 
107  /*
108  * Restart the scan. This is necessary to ensure we find all
109  * removable joins independently of ordering of the join_info_list
110  * (note that removal of attr_needed bits may make a join appear
111  * removable that did not before).
112  */
113  goto restart;
114  }
115 
116  return joinlist;
117 }
118 
119 /*
120  * clause_sides_match_join
121  * Determine whether a join clause is of the right form to use in this join.
122  *
123  * We already know that the clause is a binary opclause referencing only the
124  * rels in the current join. The point here is to check whether it has the
125  * form "outerrel_expr op innerrel_expr" or "innerrel_expr op outerrel_expr",
126  * rather than mixing outer and inner vars on either side. If it matches,
127  * we set the transient flag outer_is_left to identify which side is which.
128  */
129 static inline bool
131  Relids innerrelids)
132 {
133  if (bms_is_subset(rinfo->left_relids, outerrelids) &&
134  bms_is_subset(rinfo->right_relids, innerrelids))
135  {
136  /* lefthand side is outer */
137  rinfo->outer_is_left = true;
138  return true;
139  }
140  else if (bms_is_subset(rinfo->left_relids, innerrelids) &&
141  bms_is_subset(rinfo->right_relids, outerrelids))
142  {
143  /* righthand side is outer */
144  rinfo->outer_is_left = false;
145  return true;
146  }
147  return false; /* no good for these input relations */
148 }
149 
150 /*
151  * join_is_removable
152  * Check whether we need not perform this special join at all, because
153  * it will just duplicate its left input.
154  *
155  * This is true for a left join for which the join condition cannot match
156  * more than one inner-side row. (There are other possibly interesting
157  * cases, but we don't have the infrastructure to prove them.) We also
158  * have to check that the inner side doesn't generate any variables needed
159  * above the join.
160  */
161 static bool
163 {
164  int innerrelid;
165  RelOptInfo *innerrel;
166  Relids inputrelids;
167  Relids joinrelids;
168  List *clause_list = NIL;
169  ListCell *l;
170  int attroff;
171 
172  /*
173  * Must be a left join to a single baserel, else we aren't going to be
174  * able to do anything with it.
175  */
176  if (sjinfo->jointype != JOIN_LEFT)
177  return false;
178 
179  if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
180  return false;
181 
182  /*
183  * Never try to eliminate a left join to the query result rel. Although
184  * the case is syntactically impossible in standard SQL, MERGE will build
185  * a join tree that looks exactly like that.
186  */
187  if (innerrelid == root->parse->resultRelation)
188  return false;
189 
190  innerrel = find_base_rel(root, innerrelid);
191 
192  /*
193  * Before we go to the effort of checking whether any innerrel variables
194  * are needed above the join, make a quick check to eliminate cases in
195  * which we will surely be unable to prove uniqueness of the innerrel.
196  */
197  if (!rel_supports_distinctness(root, innerrel))
198  return false;
199 
200  /* Compute the relid set for the join we are considering */
201  inputrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
202  Assert(sjinfo->ojrelid != 0);
203  joinrelids = bms_copy(inputrelids);
204  joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);
205 
206  /*
207  * We can't remove the join if any inner-rel attributes are used above the
208  * join. Here, "above" the join includes pushed-down conditions, so we
209  * should reject if attr_needed includes the OJ's own relid; therefore,
210  * compare to inputrelids not joinrelids.
211  *
212  * As a micro-optimization, it seems better to start with max_attr and
213  * count down rather than starting with min_attr and counting up, on the
214  * theory that the system attributes are somewhat less likely to be wanted
215  * and should be tested last.
216  */
217  for (attroff = innerrel->max_attr - innerrel->min_attr;
218  attroff >= 0;
219  attroff--)
220  {
221  if (!bms_is_subset(innerrel->attr_needed[attroff], inputrelids))
222  return false;
223  }
224 
225  /*
226  * Similarly check that the inner rel isn't needed by any PlaceHolderVars
227  * that will be used above the join. The PHV case is a little bit more
228  * complicated, because PHVs may have been assigned a ph_eval_at location
229  * that includes the innerrel, yet their contained expression might not
230  * actually reference the innerrel (it could be just a constant, for
231  * instance). If such a PHV is due to be evaluated above the join then it
232  * needn't prevent join removal.
233  */
234  foreach(l, root->placeholder_list)
235  {
236  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
237 
238  if (bms_overlap(phinfo->ph_lateral, innerrel->relids))
239  return false; /* it references innerrel laterally */
240  if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
241  continue; /* it definitely doesn't reference innerrel */
242  if (bms_is_subset(phinfo->ph_needed, inputrelids))
243  continue; /* PHV is not used above the join */
244  if (!bms_is_member(sjinfo->ojrelid, phinfo->ph_eval_at))
245  return false; /* it has to be evaluated below the join */
246 
247  /*
248  * We need to be sure there will still be a place to evaluate the PHV
249  * if we remove the join, ie that ph_eval_at wouldn't become empty.
250  */
251  if (!bms_overlap(sjinfo->min_lefthand, phinfo->ph_eval_at))
252  return false; /* there isn't any other place to eval PHV */
253  /* Check contained expression last, since this is a bit expensive */
254  if (bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
255  innerrel->relids))
256  return false; /* contained expression references innerrel */
257  }
258 
259  /*
260  * Search for mergejoinable clauses that constrain the inner rel against
261  * either the outer rel or a pseudoconstant. If an operator is
262  * mergejoinable then it behaves like equality for some btree opclass, so
263  * it's what we want. The mergejoinability test also eliminates clauses
264  * containing volatile functions, which we couldn't depend on.
265  */
266  foreach(l, innerrel->joininfo)
267  {
268  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
269 
270  /*
271  * If the current join commutes with some other outer join(s) via
272  * outer join identity 3, there will be multiple clones of its join
273  * clauses in the joininfo list. We want to consider only the
274  * has_clone form of such clauses. Processing more than one form
275  * would be wasteful, and also some of the others would confuse the
276  * RINFO_IS_PUSHED_DOWN test below.
277  */
278  if (restrictinfo->is_clone)
279  continue; /* ignore it */
280 
281  /*
282  * If it's not a join clause for this outer join, we can't use it.
283  * Note that if the clause is pushed-down, then it is logically from
284  * above the outer join, even if it references no other rels (it might
285  * be from WHERE, for example).
286  */
287  if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
288  continue; /* ignore; not useful here */
289 
290  /* Ignore if it's not a mergejoinable clause */
291  if (!restrictinfo->can_join ||
292  restrictinfo->mergeopfamilies == NIL)
293  continue; /* not mergejoinable */
294 
295  /*
296  * Check if clause has the form "outer op inner" or "inner op outer",
297  * and if so mark which side is inner.
298  */
299  if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
300  innerrel->relids))
301  continue; /* no good for these input relations */
302 
303  /* OK, add to list */
304  clause_list = lappend(clause_list, restrictinfo);
305  }
306 
307  /*
308  * Now that we have the relevant equality join clauses, try to prove the
309  * innerrel distinct.
310  */
311  if (rel_is_distinct_for(root, innerrel, clause_list))
312  return true;
313 
314  /*
315  * Some day it would be nice to check for other methods of establishing
316  * distinctness.
317  */
318  return false;
319 }
320 
321 
322 /*
323  * Remove the target relid and references to the target join from the
324  * planner's data structures, having determined that there is no need
325  * to include them in the query.
326  *
327  * We are not terribly thorough here. We only bother to update parts of
328  * the planner's data structures that will actually be consulted later.
329  */
330 static void
332 {
333  RelOptInfo *rel = find_base_rel(root, relid);
334  int ojrelid = sjinfo->ojrelid;
335  Relids joinrelids;
336  Relids join_plus_commute;
337  List *joininfos;
338  Index rti;
339  ListCell *l;
340 
341  /* Compute the relid set for the join we are considering */
342  joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
343  Assert(ojrelid != 0);
344  joinrelids = bms_add_member(joinrelids, ojrelid);
345 
346  /*
347  * Remove references to the rel from other baserels' attr_needed arrays.
348  */
349  for (rti = 1; rti < root->simple_rel_array_size; rti++)
350  {
351  RelOptInfo *otherrel = root->simple_rel_array[rti];
352  int attroff;
353 
354  /* there may be empty slots corresponding to non-baserel RTEs */
355  if (otherrel == NULL)
356  continue;
357 
358  Assert(otherrel->relid == rti); /* sanity check on array */
359 
360  /* no point in processing target rel itself */
361  if (otherrel == rel)
362  continue;
363 
364  for (attroff = otherrel->max_attr - otherrel->min_attr;
365  attroff >= 0;
366  attroff--)
367  {
368  otherrel->attr_needed[attroff] =
369  bms_del_member(otherrel->attr_needed[attroff], relid);
370  otherrel->attr_needed[attroff] =
371  bms_del_member(otherrel->attr_needed[attroff], ojrelid);
372  }
373  }
374 
375  /*
376  * Update all_baserels and related relid sets.
377  */
378  root->all_baserels = bms_del_member(root->all_baserels, relid);
379  root->outer_join_rels = bms_del_member(root->outer_join_rels, ojrelid);
380  root->all_query_rels = bms_del_member(root->all_query_rels, relid);
381  root->all_query_rels = bms_del_member(root->all_query_rels, ojrelid);
382 
383  /*
384  * Likewise remove references from SpecialJoinInfo data structures.
385  *
386  * This is relevant in case the outer join we're deleting is nested inside
387  * other outer joins: the upper joins' relid sets have to be adjusted. The
388  * RHS of the target outer join will be made empty here, but that's OK
389  * since caller will delete that SpecialJoinInfo entirely.
390  */
391  foreach(l, root->join_info_list)
392  {
393  SpecialJoinInfo *sjinf = (SpecialJoinInfo *) lfirst(l);
394 
395  sjinf->min_lefthand = bms_del_member(sjinf->min_lefthand, relid);
396  sjinf->min_righthand = bms_del_member(sjinf->min_righthand, relid);
397  sjinf->syn_lefthand = bms_del_member(sjinf->syn_lefthand, relid);
398  sjinf->syn_righthand = bms_del_member(sjinf->syn_righthand, relid);
399  sjinf->min_lefthand = bms_del_member(sjinf->min_lefthand, ojrelid);
400  sjinf->min_righthand = bms_del_member(sjinf->min_righthand, ojrelid);
401  sjinf->syn_lefthand = bms_del_member(sjinf->syn_lefthand, ojrelid);
402  sjinf->syn_righthand = bms_del_member(sjinf->syn_righthand, ojrelid);
403  /* relid cannot appear in these fields, but ojrelid can: */
404  sjinf->commute_above_l = bms_del_member(sjinf->commute_above_l, ojrelid);
405  sjinf->commute_above_r = bms_del_member(sjinf->commute_above_r, ojrelid);
406  sjinf->commute_below_l = bms_del_member(sjinf->commute_below_l, ojrelid);
407  sjinf->commute_below_r = bms_del_member(sjinf->commute_below_r, ojrelid);
408  }
409 
410  /*
411  * Likewise remove references from PlaceHolderVar data structures,
412  * removing any no-longer-needed placeholders entirely.
413  *
414  * Removal is a bit trickier than it might seem: we can remove PHVs that
415  * are used at the target rel and/or in the join qual, but not those that
416  * are used at join partner rels or above the join. It's not that easy to
417  * distinguish PHVs used at partner rels from those used in the join qual,
418  * since they will both have ph_needed sets that are subsets of
419  * joinrelids. However, a PHV used at a partner rel could not have the
420  * target rel in ph_eval_at, so we check that while deciding whether to
421  * remove or just update the PHV. There is no corresponding test in
422  * join_is_removable because it doesn't need to distinguish those cases.
423  */
424  foreach(l, root->placeholder_list)
425  {
426  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
427 
428  Assert(!bms_is_member(relid, phinfo->ph_lateral));
429  if (bms_is_subset(phinfo->ph_needed, joinrelids) &&
430  bms_is_member(relid, phinfo->ph_eval_at) &&
431  !bms_is_member(ojrelid, phinfo->ph_eval_at))
432  {
434  l);
435  root->placeholder_array[phinfo->phid] = NULL;
436  }
437  else
438  {
439  PlaceHolderVar *phv = phinfo->ph_var;
440 
441  phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
442  phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, ojrelid);
443  Assert(!bms_is_empty(phinfo->ph_eval_at)); /* checked previously */
444  phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid);
445  phinfo->ph_needed = bms_del_member(phinfo->ph_needed, ojrelid);
446  /* ph_needed might or might not become empty */
447  phv->phrels = bms_del_member(phv->phrels, relid);
448  phv->phrels = bms_del_member(phv->phrels, ojrelid);
449  Assert(!bms_is_empty(phv->phrels));
450  Assert(phv->phnullingrels == NULL); /* no need to adjust */
451  }
452  }
453 
454  /*
455  * Remove any joinquals referencing the rel from the joininfo lists.
456  *
457  * In some cases, a joinqual has to be put back after deleting its
458  * reference to the target rel. This can occur for pseudoconstant and
459  * outerjoin-delayed quals, which can get marked as requiring the rel in
460  * order to force them to be evaluated at or above the join. We can't
461  * just discard them, though. Only quals that logically belonged to the
462  * outer join being discarded should be removed from the query.
463  *
464  * We might encounter a qual that is a clone of a deletable qual with some
465  * outer-join relids added (see deconstruct_distribute_oj_quals). To
466  * ensure we get rid of such clones as well, add the relids of all OJs
467  * commutable with this one to the set we test against for
468  * pushed-down-ness.
469  */
470  join_plus_commute = bms_union(joinrelids,
471  sjinfo->commute_above_r);
472  join_plus_commute = bms_add_members(join_plus_commute,
473  sjinfo->commute_below_l);
474 
475  /*
476  * We must make a copy of the rel's old joininfo list before starting the
477  * loop, because otherwise remove_join_clause_from_rels would destroy the
478  * list while we're scanning it.
479  */
480  joininfos = list_copy(rel->joininfo);
481  foreach(l, joininfos)
482  {
483  RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
484 
485  remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
486 
487  if (RINFO_IS_PUSHED_DOWN(rinfo, join_plus_commute))
488  {
489  /*
490  * There might be references to relid or ojrelid in the
491  * RestrictInfo's relid sets, as a consequence of PHVs having had
492  * ph_eval_at sets that include those. We already checked above
493  * that any such PHV is safe (and updated its ph_eval_at), so we
494  * can just drop those references.
495  */
496  remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
497 
498  /*
499  * Cross-check that the clause itself does not reference the
500  * target rel or join.
501  */
502 #ifdef USE_ASSERT_CHECKING
503  {
504  Relids clause_varnos = pull_varnos(root,
505  (Node *) rinfo->clause);
506 
507  Assert(!bms_is_member(relid, clause_varnos));
508  Assert(!bms_is_member(ojrelid, clause_varnos));
509  }
510 #endif
511  /* Now throw it back into the joininfo lists */
512  distribute_restrictinfo_to_rels(root, rinfo);
513  }
514  }
515 
516  /*
517  * Likewise remove references from EquivalenceClasses.
518  */
519  foreach(l, root->eq_classes)
520  {
522 
523  if (bms_is_member(relid, ec->ec_relids) ||
524  bms_is_member(ojrelid, ec->ec_relids))
525  remove_rel_from_eclass(ec, relid, ojrelid);
526  }
527 
528  /*
529  * There may be references to the rel in root->fkey_list, but if so,
530  * match_foreign_keys_to_quals() will get rid of them.
531  */
532 
533  /*
534  * Finally, remove the rel from the baserel array to prevent it from being
535  * referenced again. (We can't do this earlier because
536  * remove_join_clause_from_rels will touch it.)
537  */
538  root->simple_rel_array[relid] = NULL;
539 
540  /* And nuke the RelOptInfo, just in case there's another access path */
541  pfree(rel);
542 }
543 
544 /*
545  * Remove any references to relid or ojrelid from the RestrictInfo.
546  *
547  * We only bother to clean out bits in clause_relids and required_relids,
548  * not nullingrel bits in contained Vars and PHVs. (This might have to be
549  * improved sometime.) However, if the RestrictInfo contains an OR clause
550  * we have to also clean up the sub-clauses.
551  */
552 static void
553 remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
554 {
555  /*
556  * The clause_relids probably aren't shared with anything else, but let's
557  * copy them just to be sure.
558  */
559  rinfo->clause_relids = bms_copy(rinfo->clause_relids);
560  rinfo->clause_relids = bms_del_member(rinfo->clause_relids, relid);
561  rinfo->clause_relids = bms_del_member(rinfo->clause_relids, ojrelid);
562  /* Likewise for required_relids */
563  rinfo->required_relids = bms_copy(rinfo->required_relids);
564  rinfo->required_relids = bms_del_member(rinfo->required_relids, relid);
565  rinfo->required_relids = bms_del_member(rinfo->required_relids, ojrelid);
566 
567  /* If it's an OR, recurse to clean up sub-clauses */
568  if (restriction_is_or_clause(rinfo))
569  {
570  ListCell *lc;
571 
572  Assert(is_orclause(rinfo->orclause));
573  foreach(lc, ((BoolExpr *) rinfo->orclause)->args)
574  {
575  Node *orarg = (Node *) lfirst(lc);
576 
577  /* OR arguments should be ANDs or sub-RestrictInfos */
578  if (is_andclause(orarg))
579  {
580  List *andargs = ((BoolExpr *) orarg)->args;
581  ListCell *lc2;
582 
583  foreach(lc2, andargs)
584  {
585  RestrictInfo *rinfo2 = lfirst_node(RestrictInfo, lc2);
586 
587  remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
588  }
589  }
590  else
591  {
592  RestrictInfo *rinfo2 = castNode(RestrictInfo, orarg);
593 
594  remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
595  }
596  }
597  }
598 }
599 
600 /*
601  * Remove any references to relid or ojrelid from the EquivalenceClass.
602  *
603  * Like remove_rel_from_restrictinfo, we don't worry about cleaning out
604  * any nullingrel bits in contained Vars and PHVs. (This might have to be
605  * improved sometime.) We do need to fix the EC and EM relid sets to ensure
606  * that implied join equalities will be generated at the appropriate join
607  * level(s).
608  */
609 static void
610 remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
611 {
612  ListCell *lc;
613 
614  /* Fix up the EC's overall relids */
615  ec->ec_relids = bms_del_member(ec->ec_relids, relid);
616  ec->ec_relids = bms_del_member(ec->ec_relids, ojrelid);
617 
618  /*
619  * Fix up the member expressions. Any non-const member that ends with
620  * empty em_relids must be a Var or PHV of the removed relation. We don't
621  * need it anymore, so we can drop it.
622  */
623  foreach(lc, ec->ec_members)
624  {
625  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
626 
627  if (bms_is_member(relid, cur_em->em_relids) ||
628  bms_is_member(ojrelid, cur_em->em_relids))
629  {
630  Assert(!cur_em->em_is_const);
631  cur_em->em_relids = bms_del_member(cur_em->em_relids, relid);
632  cur_em->em_relids = bms_del_member(cur_em->em_relids, ojrelid);
633  if (bms_is_empty(cur_em->em_relids))
635  }
636  }
637 
638  /* Fix up the source clauses, in case we can re-use them later */
639  foreach(lc, ec->ec_sources)
640  {
641  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
642 
643  remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
644  }
645 
646  /*
647  * Rather than expend code on fixing up any already-derived clauses, just
648  * drop them. (At this point, any such clauses would be base restriction
649  * clauses, which we'd not need anymore anyway.)
650  */
651  ec->ec_derives = NIL;
652 }
653 
654 /*
655  * Remove any occurrences of the target relid from a joinlist structure.
656  *
657  * It's easiest to build a whole new list structure, so we handle it that
658  * way. Efficiency is not a big deal here.
659  *
660  * *nremoved is incremented by the number of occurrences removed (there
661  * should be exactly one, but the caller checks that).
662  */
663 static List *
664 remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
665 {
666  List *result = NIL;
667  ListCell *jl;
668 
669  foreach(jl, joinlist)
670  {
671  Node *jlnode = (Node *) lfirst(jl);
672 
673  if (IsA(jlnode, RangeTblRef))
674  {
675  int varno = ((RangeTblRef *) jlnode)->rtindex;
676 
677  if (varno == relid)
678  (*nremoved)++;
679  else
680  result = lappend(result, jlnode);
681  }
682  else if (IsA(jlnode, List))
683  {
684  /* Recurse to handle subproblem */
685  List *sublist;
686 
687  sublist = remove_rel_from_joinlist((List *) jlnode,
688  relid, nremoved);
689  /* Avoid including empty sub-lists in the result */
690  if (sublist)
691  result = lappend(result, sublist);
692  }
693  else
694  {
695  elog(ERROR, "unrecognized joinlist node type: %d",
696  (int) nodeTag(jlnode));
697  }
698  }
699 
700  return result;
701 }
702 
703 
704 /*
705  * reduce_unique_semijoins
706  * Check for semijoins that can be simplified to plain inner joins
707  * because the inner relation is provably unique for the join clauses.
708  *
709  * Ideally this would happen during reduce_outer_joins, but we don't have
710  * enough information at that point.
711  *
712  * To perform the strength reduction when applicable, we need only delete
713  * the semijoin's SpecialJoinInfo from root->join_info_list. (We don't
714  * bother fixing the join type attributed to it in the query jointree,
715  * since that won't be consulted again.)
716  */
717 void
719 {
720  ListCell *lc;
721 
722  /*
723  * Scan the join_info_list to find semijoins.
724  */
725  foreach(lc, root->join_info_list)
726  {
727  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
728  int innerrelid;
729  RelOptInfo *innerrel;
730  Relids joinrelids;
731  List *restrictlist;
732 
733  /*
734  * Must be a semijoin to a single baserel, else we aren't going to be
735  * able to do anything with it.
736  */
737  if (sjinfo->jointype != JOIN_SEMI)
738  continue;
739 
740  if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
741  continue;
742 
743  innerrel = find_base_rel(root, innerrelid);
744 
745  /*
746  * Before we trouble to run generate_join_implied_equalities, make a
747  * quick check to eliminate cases in which we will surely be unable to
748  * prove uniqueness of the innerrel.
749  */
750  if (!rel_supports_distinctness(root, innerrel))
751  continue;
752 
753  /* Compute the relid set for the join we are considering */
754  joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
755  Assert(sjinfo->ojrelid == 0); /* SEMI joins don't have RT indexes */
756 
757  /*
758  * Since we're only considering a single-rel RHS, any join clauses it
759  * has must be clauses linking it to the semijoin's min_lefthand. We
760  * can also consider EC-derived join clauses.
761  */
762  restrictlist =
764  joinrelids,
765  sjinfo->min_lefthand,
766  innerrel,
767  NULL),
768  innerrel->joininfo);
769 
770  /* Test whether the innerrel is unique for those clauses. */
771  if (!innerrel_is_unique(root,
772  joinrelids, sjinfo->min_lefthand, innerrel,
773  JOIN_SEMI, restrictlist, true))
774  continue;
775 
776  /* OK, remove the SpecialJoinInfo from the list. */
778  }
779 }
780 
781 
782 /*
783  * rel_supports_distinctness
784  * Could the relation possibly be proven distinct on some set of columns?
785  *
786  * This is effectively a pre-checking function for rel_is_distinct_for().
787  * It must return true if rel_is_distinct_for() could possibly return true
788  * with this rel, but it should not expend a lot of cycles. The idea is
789  * that callers can avoid doing possibly-expensive processing to compute
790  * rel_is_distinct_for()'s argument lists if the call could not possibly
791  * succeed.
792  */
793 static bool
795 {
796  /* We only know about baserels ... */
797  if (rel->reloptkind != RELOPT_BASEREL)
798  return false;
799  if (rel->rtekind == RTE_RELATION)
800  {
801  /*
802  * For a plain relation, we only know how to prove uniqueness by
803  * reference to unique indexes. Make sure there's at least one
804  * suitable unique index. It must be immediately enforced, and not a
805  * partial index. (Keep these conditions in sync with
806  * relation_has_unique_index_for!)
807  */
808  ListCell *lc;
809 
810  foreach(lc, rel->indexlist)
811  {
812  IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
813 
814  if (ind->unique && ind->immediate && ind->indpred == NIL)
815  return true;
816  }
817  }
818  else if (rel->rtekind == RTE_SUBQUERY)
819  {
820  Query *subquery = root->simple_rte_array[rel->relid]->subquery;
821 
822  /* Check if the subquery has any qualities that support distinctness */
823  if (query_supports_distinctness(subquery))
824  return true;
825  }
826  /* We have no proof rules for any other rtekinds. */
827  return false;
828 }
829 
830 /*
831  * rel_is_distinct_for
832  * Does the relation return only distinct rows according to clause_list?
833  *
834  * clause_list is a list of join restriction clauses involving this rel and
835  * some other one. Return true if no two rows emitted by this rel could
836  * possibly join to the same row of the other rel.
837  *
838  * The caller must have already determined that each condition is a
839  * mergejoinable equality with an expression in this relation on one side, and
840  * an expression not involving this relation on the other. The transient
841  * outer_is_left flag is used to identify which side references this relation:
842  * left side if outer_is_left is false, right side if it is true.
843  *
844  * Note that the passed-in clause_list may be destructively modified! This
845  * is OK for current uses, because the clause_list is built by the caller for
846  * the sole purpose of passing to this function.
847  */
848 static bool
849 rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list)
850 {
851  /*
852  * We could skip a couple of tests here if we assume all callers checked
853  * rel_supports_distinctness first, but it doesn't seem worth taking any
854  * risk for.
855  */
856  if (rel->reloptkind != RELOPT_BASEREL)
857  return false;
858  if (rel->rtekind == RTE_RELATION)
859  {
860  /*
861  * Examine the indexes to see if we have a matching unique index.
862  * relation_has_unique_index_for automatically adds any usable
863  * restriction clauses for the rel, so we needn't do that here.
864  */
865  if (relation_has_unique_index_for(root, rel, clause_list, NIL, NIL))
866  return true;
867  }
868  else if (rel->rtekind == RTE_SUBQUERY)
869  {
870  Index relid = rel->relid;
871  Query *subquery = root->simple_rte_array[relid]->subquery;
872  List *colnos = NIL;
873  List *opids = NIL;
874  ListCell *l;
875 
876  /*
877  * Build the argument lists for query_is_distinct_for: a list of
878  * output column numbers that the query needs to be distinct over, and
879  * a list of equality operators that the output columns need to be
880  * distinct according to.
881  *
882  * (XXX we are not considering restriction clauses attached to the
883  * subquery; is that worth doing?)
884  */
885  foreach(l, clause_list)
886  {
888  Oid op;
889  Var *var;
890 
891  /*
892  * Get the equality operator we need uniqueness according to.
893  * (This might be a cross-type operator and thus not exactly the
894  * same operator the subquery would consider; that's all right
895  * since query_is_distinct_for can resolve such cases.) The
896  * caller's mergejoinability test should have selected only
897  * OpExprs.
898  */
899  op = castNode(OpExpr, rinfo->clause)->opno;
900 
901  /* caller identified the inner side for us */
902  if (rinfo->outer_is_left)
903  var = (Var *) get_rightop(rinfo->clause);
904  else
905  var = (Var *) get_leftop(rinfo->clause);
906 
907  /*
908  * We may ignore any RelabelType node above the operand. (There
909  * won't be more than one, since eval_const_expressions() has been
910  * applied already.)
911  */
912  if (var && IsA(var, RelabelType))
913  var = (Var *) ((RelabelType *) var)->arg;
914 
915  /*
916  * If inner side isn't a Var referencing a subquery output column,
917  * this clause doesn't help us.
918  */
919  if (!var || !IsA(var, Var) ||
920  var->varno != relid || var->varlevelsup != 0)
921  continue;
922 
923  colnos = lappend_int(colnos, var->varattno);
924  opids = lappend_oid(opids, op);
925  }
926 
927  if (query_is_distinct_for(subquery, colnos, opids))
928  return true;
929  }
930  return false;
931 }
932 
933 
934 /*
935  * query_supports_distinctness - could the query possibly be proven distinct
936  * on some set of output columns?
937  *
938  * This is effectively a pre-checking function for query_is_distinct_for().
939  * It must return true if query_is_distinct_for() could possibly return true
940  * with this query, but it should not expend a lot of cycles. The idea is
941  * that callers can avoid doing possibly-expensive processing to compute
942  * query_is_distinct_for()'s argument lists if the call could not possibly
943  * succeed.
944  */
945 bool
947 {
948  /* SRFs break distinctness except with DISTINCT, see below */
949  if (query->hasTargetSRFs && query->distinctClause == NIL)
950  return false;
951 
952  /* check for features we can prove distinctness with */
953  if (query->distinctClause != NIL ||
954  query->groupClause != NIL ||
955  query->groupingSets != NIL ||
956  query->hasAggs ||
957  query->havingQual ||
958  query->setOperations)
959  return true;
960 
961  return false;
962 }
963 
964 /*
965  * query_is_distinct_for - does query never return duplicates of the
966  * specified columns?
967  *
968  * query is a not-yet-planned subquery (in current usage, it's always from
969  * a subquery RTE, which the planner avoids scribbling on).
970  *
971  * colnos is an integer list of output column numbers (resno's). We are
972  * interested in whether rows consisting of just these columns are certain
973  * to be distinct. "Distinctness" is defined according to whether the
974  * corresponding upper-level equality operators listed in opids would think
975  * the values are distinct. (Note: the opids entries could be cross-type
976  * operators, and thus not exactly the equality operators that the subquery
977  * would use itself. We use equality_ops_are_compatible() to check
978  * compatibility. That looks at btree or hash opfamily membership, and so
979  * should give trustworthy answers for all operators that we might need
980  * to deal with here.)
981  */
982 bool
983 query_is_distinct_for(Query *query, List *colnos, List *opids)
984 {
985  ListCell *l;
986  Oid opid;
987 
988  Assert(list_length(colnos) == list_length(opids));
989 
990  /*
991  * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
992  * columns in the DISTINCT clause appear in colnos and operator semantics
993  * match. This is true even if there are SRFs in the DISTINCT columns or
994  * elsewhere in the tlist.
995  */
996  if (query->distinctClause)
997  {
998  foreach(l, query->distinctClause)
999  {
1000  SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
1002  query->targetList);
1003 
1004  opid = distinct_col_search(tle->resno, colnos, opids);
1005  if (!OidIsValid(opid) ||
1006  !equality_ops_are_compatible(opid, sgc->eqop))
1007  break; /* exit early if no match */
1008  }
1009  if (l == NULL) /* had matches for all? */
1010  return true;
1011  }
1012 
1013  /*
1014  * Otherwise, a set-returning function in the query's targetlist can
1015  * result in returning duplicate rows, despite any grouping that might
1016  * occur before tlist evaluation. (If all tlist SRFs are within GROUP BY
1017  * columns, it would be safe because they'd be expanded before grouping.
1018  * But it doesn't currently seem worth the effort to check for that.)
1019  */
1020  if (query->hasTargetSRFs)
1021  return false;
1022 
1023  /*
1024  * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
1025  * the grouped columns appear in colnos and operator semantics match.
1026  */
1027  if (query->groupClause && !query->groupingSets)
1028  {
1029  foreach(l, query->groupClause)
1030  {
1031  SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
1033  query->targetList);
1034 
1035  opid = distinct_col_search(tle->resno, colnos, opids);
1036  if (!OidIsValid(opid) ||
1037  !equality_ops_are_compatible(opid, sgc->eqop))
1038  break; /* exit early if no match */
1039  }
1040  if (l == NULL) /* had matches for all? */
1041  return true;
1042  }
1043  else if (query->groupingSets)
1044  {
1045  /*
1046  * If we have grouping sets with expressions, we probably don't have
1047  * uniqueness and analysis would be hard. Punt.
1048  */
1049  if (query->groupClause)
1050  return false;
1051 
1052  /*
1053  * If we have no groupClause (therefore no grouping expressions), we
1054  * might have one or many empty grouping sets. If there's just one,
1055  * then we're returning only one row and are certainly unique. But
1056  * otherwise, we know we're certainly not unique.
1057  */
1058  if (list_length(query->groupingSets) == 1 &&
1059  ((GroupingSet *) linitial(query->groupingSets))->kind == GROUPING_SET_EMPTY)
1060  return true;
1061  else
1062  return false;
1063  }
1064  else
1065  {
1066  /*
1067  * If we have no GROUP BY, but do have aggregates or HAVING, then the
1068  * result is at most one row so it's surely unique, for any operators.
1069  */
1070  if (query->hasAggs || query->havingQual)
1071  return true;
1072  }
1073 
1074  /*
1075  * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
1076  * except with ALL.
1077  */
1078  if (query->setOperations)
1079  {
1081 
1082  Assert(topop->op != SETOP_NONE);
1083 
1084  if (!topop->all)
1085  {
1086  ListCell *lg;
1087 
1088  /* We're good if all the nonjunk output columns are in colnos */
1089  lg = list_head(topop->groupClauses);
1090  foreach(l, query->targetList)
1091  {
1092  TargetEntry *tle = (TargetEntry *) lfirst(l);
1093  SortGroupClause *sgc;
1094 
1095  if (tle->resjunk)
1096  continue; /* ignore resjunk columns */
1097 
1098  /* non-resjunk columns should have grouping clauses */
1099  Assert(lg != NULL);
1100  sgc = (SortGroupClause *) lfirst(lg);
1101  lg = lnext(topop->groupClauses, lg);
1102 
1103  opid = distinct_col_search(tle->resno, colnos, opids);
1104  if (!OidIsValid(opid) ||
1105  !equality_ops_are_compatible(opid, sgc->eqop))
1106  break; /* exit early if no match */
1107  }
1108  if (l == NULL) /* had matches for all? */
1109  return true;
1110  }
1111  }
1112 
1113  /*
1114  * XXX Are there any other cases in which we can easily see the result
1115  * must be distinct?
1116  *
1117  * If you do add more smarts to this function, be sure to update
1118  * query_supports_distinctness() to match.
1119  */
1120 
1121  return false;
1122 }
1123 
1124 /*
1125  * distinct_col_search - subroutine for query_is_distinct_for
1126  *
1127  * If colno is in colnos, return the corresponding element of opids,
1128  * else return InvalidOid. (Ordinarily colnos would not contain duplicates,
1129  * but if it does, we arbitrarily select the first match.)
1130  */
1131 static Oid
1132 distinct_col_search(int colno, List *colnos, List *opids)
1133 {
1134  ListCell *lc1,
1135  *lc2;
1136 
1137  forboth(lc1, colnos, lc2, opids)
1138  {
1139  if (colno == lfirst_int(lc1))
1140  return lfirst_oid(lc2);
1141  }
1142  return InvalidOid;
1143 }
1144 
1145 
1146 /*
1147  * innerrel_is_unique
1148  * Check if the innerrel provably contains at most one tuple matching any
1149  * tuple from the outerrel, based on join clauses in the 'restrictlist'.
1150  *
1151  * We need an actual RelOptInfo for the innerrel, but it's sufficient to
1152  * identify the outerrel by its Relids. This asymmetry supports use of this
1153  * function before joinrels have been built. (The caller is expected to
1154  * also supply the joinrelids, just to save recalculating that.)
1155  *
1156  * The proof must be made based only on clauses that will be "joinquals"
1157  * rather than "otherquals" at execution. For an inner join there's no
1158  * difference; but if the join is outer, we must ignore pushed-down quals,
1159  * as those will become "otherquals". Note that this means the answer might
1160  * vary depending on whether IS_OUTER_JOIN(jointype); since we cache the
1161  * answer without regard to that, callers must take care not to call this
1162  * with jointypes that would be classified differently by IS_OUTER_JOIN().
1163  *
1164  * The actual proof is undertaken by is_innerrel_unique_for(); this function
1165  * is a frontend that is mainly concerned with caching the answers.
1166  * In particular, the force_cache argument allows overriding the internal
1167  * heuristic about whether to cache negative answers; it should be "true"
1168  * if making an inquiry that is not part of the normal bottom-up join search
1169  * sequence.
1170  */
1171 bool
1173  Relids joinrelids,
1174  Relids outerrelids,
1175  RelOptInfo *innerrel,
1176  JoinType jointype,
1177  List *restrictlist,
1178  bool force_cache)
1179 {
1180  MemoryContext old_context;
1181  ListCell *lc;
1182 
1183  /* Certainly can't prove uniqueness when there are no joinclauses */
1184  if (restrictlist == NIL)
1185  return false;
1186 
1187  /*
1188  * Make a quick check to eliminate cases in which we will surely be unable
1189  * to prove uniqueness of the innerrel.
1190  */
1191  if (!rel_supports_distinctness(root, innerrel))
1192  return false;
1193 
1194  /*
1195  * Query the cache to see if we've managed to prove that innerrel is
1196  * unique for any subset of this outerrel. We don't need an exact match,
1197  * as extra outerrels can't make the innerrel any less unique (or more
1198  * formally, the restrictlist for a join to a superset outerrel must be a
1199  * superset of the conditions we successfully used before).
1200  */
1201  foreach(lc, innerrel->unique_for_rels)
1202  {
1203  Relids unique_for_rels = (Relids) lfirst(lc);
1204 
1205  if (bms_is_subset(unique_for_rels, outerrelids))
1206  return true; /* Success! */
1207  }
1208 
1209  /*
1210  * Conversely, we may have already determined that this outerrel, or some
1211  * superset thereof, cannot prove this innerrel to be unique.
1212  */
1213  foreach(lc, innerrel->non_unique_for_rels)
1214  {
1215  Relids unique_for_rels = (Relids) lfirst(lc);
1216 
1217  if (bms_is_subset(outerrelids, unique_for_rels))
1218  return false;
1219  }
1220 
1221  /* No cached information, so try to make the proof. */
1222  if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
1223  jointype, restrictlist))
1224  {
1225  /*
1226  * Cache the positive result for future probes, being sure to keep it
1227  * in the planner_cxt even if we are working in GEQO.
1228  *
1229  * Note: one might consider trying to isolate the minimal subset of
1230  * the outerrels that proved the innerrel unique. But it's not worth
1231  * the trouble, because the planner builds up joinrels incrementally
1232  * and so we'll see the minimally sufficient outerrels before any
1233  * supersets of them anyway.
1234  */
1235  old_context = MemoryContextSwitchTo(root->planner_cxt);
1236  innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
1237  bms_copy(outerrelids));
1238  MemoryContextSwitchTo(old_context);
1239 
1240  return true; /* Success! */
1241  }
1242  else
1243  {
1244  /*
1245  * None of the join conditions for outerrel proved innerrel unique, so
1246  * we can safely reject this outerrel or any subset of it in future
1247  * checks.
1248  *
1249  * However, in normal planning mode, caching this knowledge is totally
1250  * pointless; it won't be queried again, because we build up joinrels
1251  * from smaller to larger. It is useful in GEQO mode, where the
1252  * knowledge can be carried across successive planning attempts; and
1253  * it's likely to be useful when using join-search plugins, too. Hence
1254  * cache when join_search_private is non-NULL. (Yeah, that's a hack,
1255  * but it seems reasonable.)
1256  *
1257  * Also, allow callers to override that heuristic and force caching;
1258  * that's useful for reduce_unique_semijoins, which calls here before
1259  * the normal join search starts.
1260  */
1261  if (force_cache || root->join_search_private)
1262  {
1263  old_context = MemoryContextSwitchTo(root->planner_cxt);
1264  innerrel->non_unique_for_rels =
1265  lappend(innerrel->non_unique_for_rels,
1266  bms_copy(outerrelids));
1267  MemoryContextSwitchTo(old_context);
1268  }
1269 
1270  return false;
1271  }
1272 }
1273 
1274 /*
1275  * is_innerrel_unique_for
1276  * Check if the innerrel provably contains at most one tuple matching any
1277  * tuple from the outerrel, based on join clauses in the 'restrictlist'.
1278  */
1279 static bool
1281  Relids joinrelids,
1282  Relids outerrelids,
1283  RelOptInfo *innerrel,
1284  JoinType jointype,
1285  List *restrictlist)
1286 {
1287  List *clause_list = NIL;
1288  ListCell *lc;
1289 
1290  /*
1291  * Search for mergejoinable clauses that constrain the inner rel against
1292  * the outer rel. If an operator is mergejoinable then it behaves like
1293  * equality for some btree opclass, so it's what we want. The
1294  * mergejoinability test also eliminates clauses containing volatile
1295  * functions, which we couldn't depend on.
1296  */
1297  foreach(lc, restrictlist)
1298  {
1299  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
1300 
1301  /*
1302  * As noted above, if it's a pushed-down clause and we're at an outer
1303  * join, we can't use it.
1304  */
1305  if (IS_OUTER_JOIN(jointype) &&
1306  RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
1307  continue;
1308 
1309  /* Ignore if it's not a mergejoinable clause */
1310  if (!restrictinfo->can_join ||
1311  restrictinfo->mergeopfamilies == NIL)
1312  continue; /* not mergejoinable */
1313 
1314  /*
1315  * Check if clause has the form "outer op inner" or "inner op outer",
1316  * and if so mark which side is inner.
1317  */
1318  if (!clause_sides_match_join(restrictinfo, outerrelids,
1319  innerrel->relids))
1320  continue; /* no good for these input relations */
1321 
1322  /* OK, add to list */
1323  clause_list = lappend(clause_list, restrictinfo);
1324  }
1325 
1326  /* Let rel_is_distinct_for() do the hard work */
1327  return rel_is_distinct_for(root, innerrel, clause_list);
1328 }
List * remove_useless_joins(PlannerInfo *root, List *joinlist)
Definition: analyzejoins.c:66
static void remove_rel_from_query(PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
Definition: analyzejoins.c:331
static bool clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
Definition: analyzejoins.c:130
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
static List * remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
Definition: analyzejoins.c:664
bool query_is_distinct_for(Query *query, List *colnos, List *opids)
Definition: analyzejoins.c:983
static Oid distinct_col_search(int colno, List *colnos, List *opids)
bool query_supports_distinctness(Query *query)
Definition: analyzejoins.c:946
static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list)
Definition: analyzejoins.c:849
static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
Definition: analyzejoins.c:162
void reduce_unique_semijoins(PlannerInfo *root)
Definition: analyzejoins.c:718
static bool is_innerrel_unique_for(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist)
static void remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
Definition: analyzejoins.c:553
static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
Definition: analyzejoins.c:794
static void remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
Definition: analyzejoins.c:610
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:363
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:612
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:460
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:753
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:211
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:835
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:793
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:527
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:80
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:652
#define bms_is_empty(a)
Definition: bitmapset.h:105
unsigned int Index
Definition: c.h:603
#define OidIsValid(objectId)
Definition: c.h:764
#define ERROR
Definition: elog.h:39
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
Definition: equivclass.c:1381
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:2631
void remove_join_clause_from_rels(PlannerInfo *root, RestrictInfo *restrictinfo, Relids join_relids)
Definition: joininfo.c:125
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
void pfree(void *pointer)
Definition: mcxt.c:1456
static bool is_andclause(const void *clause)
Definition: nodeFuncs.h:105
static bool is_orclause(const void *clause)
Definition: nodeFuncs.h:114
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:179
#define nodeTag(nodeptr)
Definition: nodes.h:133
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:348
#define castNode(_type_, nodeptr)
Definition: nodes.h:197
JoinType
Definition: nodes.h:299
@ JOIN_SEMI
Definition: nodes.h:318
@ JOIN_LEFT
Definition: nodes.h:305
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:138
@ GROUPING_SET_EMPTY
Definition: parsenodes.h:1452
@ SETOP_NONE
Definition: parsenodes.h:1972
@ RTE_SUBQUERY
Definition: parsenodes.h:1014
@ RTE_RELATION
Definition: parsenodes.h:1013
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2683
Bitmapset * Relids
Definition: pathnodes.h:30
@ RELOPT_BASEREL
Definition: pathnodes.h:812
#define lfirst(lc)
Definition: pg_list.h:172
#define lfirst_node(type, lc)
Definition: pg_list.h:176
static int list_length(const List *l)
Definition: pg_list.h:152
#define NIL
Definition: pg_list.h:68
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:467
#define lfirst_int(lc)
Definition: pg_list.h:173
static ListCell * list_head(const List *l)
Definition: pg_list.h:128
#define linitial(l)
Definition: pg_list.h:178
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:343
#define lfirst_oid(lc)
Definition: pg_list.h:174
#define foreach_delete_current(lst, cell)
Definition: pg_list.h:390
#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:405
bool restriction_is_or_clause(RestrictInfo *restrictinfo)
Definition: restrictinfo.c:416
Definition: pg_list.h:54
Definition: nodes.h:129
Relids ph_lateral
Definition: pathnodes.h:3050
Relids ph_needed
Definition: pathnodes.h:3053
Relids ph_eval_at
Definition: pathnodes.h:3047
PlaceHolderVar * ph_var
Definition: pathnodes.h:3044
Relids phnullingrels
Definition: pathnodes.h:2753
int simple_rel_array_size
Definition: pathnodes.h:229
Relids all_query_rels
Definition: pathnodes.h:266
Relids outer_join_rels
Definition: pathnodes.h:258
List * placeholder_list
Definition: pathnodes.h:371
List * eq_classes
Definition: pathnodes.h:311
Query * parse
Definition: pathnodes.h:199
List * join_info_list
Definition: pathnodes.h:337
Relids all_baserels
Definition: pathnodes.h:252
Node * setOperations
Definition: parsenodes.h:216
List * groupClause
Definition: parsenodes.h:197
Node * havingQual
Definition: parsenodes.h:202
List * targetList
Definition: parsenodes.h:188
List * groupingSets
Definition: parsenodes.h:200
List * distinctClause
Definition: parsenodes.h:206
List * joininfo
Definition: pathnodes.h:970
Relids relids
Definition: pathnodes.h:856
Index relid
Definition: pathnodes.h:903
List * unique_for_rels
Definition: pathnodes.h:956
RelOptKind reloptkind
Definition: pathnodes.h:850
List * indexlist
Definition: pathnodes.h:923
List * non_unique_for_rels
Definition: pathnodes.h:958
AttrNumber max_attr
Definition: pathnodes.h:911
AttrNumber min_attr
Definition: pathnodes.h:909
RTEKind rtekind
Definition: pathnodes.h:907
Relids required_relids
Definition: pathnodes.h:2560
Expr * clause
Definition: pathnodes.h:2529
SetOperation op
Definition: parsenodes.h:2050
Relids commute_above_r
Definition: pathnodes.h:2860
Relids syn_lefthand
Definition: pathnodes.h:2855
Relids min_righthand
Definition: pathnodes.h:2854
Relids commute_above_l
Definition: pathnodes.h:2859
JoinType jointype
Definition: pathnodes.h:2857
Relids commute_below_l
Definition: pathnodes.h:2861
Relids min_lefthand
Definition: pathnodes.h:2853
Relids syn_righthand
Definition: pathnodes.h:2856
Relids commute_below_r
Definition: pathnodes.h:2862
AttrNumber resno
Definition: primnodes.h:1897
Definition: primnodes.h:226
AttrNumber varattno
Definition: primnodes.h:238
int varno
Definition: primnodes.h:233
Index varlevelsup
Definition: primnodes.h:258
TargetEntry * get_sortgroupclause_tle(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:367
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:108