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