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 "catalog/pg_class.h"
26 #include "nodes/nodeFuncs.h"
27 #include "optimizer/clauses.h"
28 #include "optimizer/joininfo.h"
29 #include "optimizer/optimizer.h"
30 #include "optimizer/pathnode.h"
31 #include "optimizer/paths.h"
32 #include "optimizer/planmain.h"
33 #include "optimizer/restrictinfo.h"
34 #include "optimizer/tlist.h"
35 #include "utils/lsyscache.h"
36 
37 /*
38  * The context for replace_varno_walker() containing source and target relids.
39  */
40 typedef struct
41 {
42  int from;
43  int to;
45 
46 /*
47  * The struct containing self-join candidate. Used to find duplicate reloids.
48  */
49 typedef struct
50 {
51  int relid;
54 
56 
57 /* local functions */
58 static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
59 
60 static void remove_leftjoinrel_from_query(PlannerInfo *root, int relid,
61  SpecialJoinInfo *sjinfo);
63  int relid, int ojrelid);
65  int relid, int ojrelid);
66 static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
67 static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel);
68 static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel,
69  List *clause_list, List **extra_clauses);
70 static Oid distinct_col_search(int colno, List *colnos, List *opids);
71 static bool is_innerrel_unique_for(PlannerInfo *root,
72  Relids joinrelids,
73  Relids outerrelids,
74  RelOptInfo *innerrel,
75  JoinType jointype,
76  List *restrictlist,
77  List **extra_clauses);
78 static Bitmapset *replace_relid(Relids relids, int oldId, int newId);
79 static void replace_varno(Node *node, int from, int to);
80 static bool replace_varno_walker(Node *node, ReplaceVarnoContext *ctx);
81 static int self_join_candidates_cmp(const void *a, const void *b);
82 
83 
84 
85 /*
86  * remove_useless_joins
87  * Check for relations that don't actually need to be joined at all,
88  * and remove them from the query.
89  *
90  * We are passed the current joinlist and return the updated list. Other
91  * data structures that have to be updated are accessible via "root".
92  */
93 List *
95 {
96  ListCell *lc;
97 
98  /*
99  * We are only interested in relations that are left-joined to, so we can
100  * scan the join_info_list to find them easily.
101  */
102 restart:
103  foreach(lc, root->join_info_list)
104  {
105  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
106  int innerrelid;
107  int nremoved;
108 
109  /* Skip if not removable */
110  if (!join_is_removable(root, sjinfo))
111  continue;
112 
113  /*
114  * Currently, join_is_removable can only succeed when the sjinfo's
115  * righthand is a single baserel. Remove that rel from the query and
116  * joinlist.
117  */
118  innerrelid = bms_singleton_member(sjinfo->min_righthand);
119 
120  remove_leftjoinrel_from_query(root, innerrelid, sjinfo);
121 
122  /* We verify that exactly one reference gets removed from joinlist */
123  nremoved = 0;
124  joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
125  if (nremoved != 1)
126  elog(ERROR, "failed to find relation %d in joinlist", innerrelid);
127 
128  /*
129  * We can delete this SpecialJoinInfo from the list too, since it's no
130  * longer of interest. (Since we'll restart the foreach loop
131  * immediately, we don't bother with foreach_delete_current.)
132  */
134 
135  /*
136  * Restart the scan. This is necessary to ensure we find all
137  * removable joins independently of ordering of the join_info_list
138  * (note that removal of attr_needed bits may make a join appear
139  * removable that did not before).
140  */
141  goto restart;
142  }
143 
144  return joinlist;
145 }
146 
147 /*
148  * clause_sides_match_join
149  * Determine whether a join clause is of the right form to use in this join.
150  *
151  * We already know that the clause is a binary opclause referencing only the
152  * rels in the current join. The point here is to check whether it has the
153  * form "outerrel_expr op innerrel_expr" or "innerrel_expr op outerrel_expr",
154  * rather than mixing outer and inner vars on either side. If it matches,
155  * we set the transient flag outer_is_left to identify which side is which.
156  */
157 static inline bool
159  Relids innerrelids)
160 {
161  if (bms_is_subset(rinfo->left_relids, outerrelids) &&
162  bms_is_subset(rinfo->right_relids, innerrelids))
163  {
164  /* lefthand side is outer */
165  rinfo->outer_is_left = true;
166  return true;
167  }
168  else if (bms_is_subset(rinfo->left_relids, innerrelids) &&
169  bms_is_subset(rinfo->right_relids, outerrelids))
170  {
171  /* righthand side is outer */
172  rinfo->outer_is_left = false;
173  return true;
174  }
175  return false; /* no good for these input relations */
176 }
177 
178 /*
179  * join_is_removable
180  * Check whether we need not perform this special join at all, because
181  * it will just duplicate its left input.
182  *
183  * This is true for a left join for which the join condition cannot match
184  * more than one inner-side row. (There are other possibly interesting
185  * cases, but we don't have the infrastructure to prove them.) We also
186  * have to check that the inner side doesn't generate any variables needed
187  * above the join.
188  */
189 static bool
191 {
192  int innerrelid;
193  RelOptInfo *innerrel;
194  Relids inputrelids;
195  Relids joinrelids;
196  List *clause_list = NIL;
197  ListCell *l;
198  int attroff;
199 
200  /*
201  * Must be a left join to a single baserel, else we aren't going to be
202  * able to do anything with it.
203  */
204  if (sjinfo->jointype != JOIN_LEFT)
205  return false;
206 
207  if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
208  return false;
209 
210  /*
211  * Never try to eliminate a left join to the query result rel. Although
212  * the case is syntactically impossible in standard SQL, MERGE will build
213  * a join tree that looks exactly like that.
214  */
215  if (innerrelid == root->parse->resultRelation)
216  return false;
217 
218  innerrel = find_base_rel(root, innerrelid);
219 
220  /*
221  * Before we go to the effort of checking whether any innerrel variables
222  * are needed above the join, make a quick check to eliminate cases in
223  * which we will surely be unable to prove uniqueness of the innerrel.
224  */
225  if (!rel_supports_distinctness(root, innerrel))
226  return false;
227 
228  /* Compute the relid set for the join we are considering */
229  inputrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
230  Assert(sjinfo->ojrelid != 0);
231  joinrelids = bms_copy(inputrelids);
232  joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);
233 
234  /*
235  * We can't remove the join if any inner-rel attributes are used above the
236  * join. Here, "above" the join includes pushed-down conditions, so we
237  * should reject if attr_needed includes the OJ's own relid; therefore,
238  * compare to inputrelids not joinrelids.
239  *
240  * As a micro-optimization, it seems better to start with max_attr and
241  * count down rather than starting with min_attr and counting up, on the
242  * theory that the system attributes are somewhat less likely to be wanted
243  * and should be tested last.
244  */
245  for (attroff = innerrel->max_attr - innerrel->min_attr;
246  attroff >= 0;
247  attroff--)
248  {
249  if (!bms_is_subset(innerrel->attr_needed[attroff], inputrelids))
250  return false;
251  }
252 
253  /*
254  * Similarly check that the inner rel isn't needed by any PlaceHolderVars
255  * that will be used above the join. The PHV case is a little bit more
256  * complicated, because PHVs may have been assigned a ph_eval_at location
257  * that includes the innerrel, yet their contained expression might not
258  * actually reference the innerrel (it could be just a constant, for
259  * instance). If such a PHV is due to be evaluated above the join then it
260  * needn't prevent join removal.
261  */
262  foreach(l, root->placeholder_list)
263  {
264  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
265 
266  if (bms_overlap(phinfo->ph_lateral, innerrel->relids))
267  return false; /* it references innerrel laterally */
268  if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
269  continue; /* it definitely doesn't reference innerrel */
270  if (bms_is_subset(phinfo->ph_needed, inputrelids))
271  continue; /* PHV is not used above the join */
272  if (!bms_is_member(sjinfo->ojrelid, phinfo->ph_eval_at))
273  return false; /* it has to be evaluated below the join */
274 
275  /*
276  * We need to be sure there will still be a place to evaluate the PHV
277  * if we remove the join, ie that ph_eval_at wouldn't become empty.
278  */
279  if (!bms_overlap(sjinfo->min_lefthand, phinfo->ph_eval_at))
280  return false; /* there isn't any other place to eval PHV */
281  /* Check contained expression last, since this is a bit expensive */
282  if (bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
283  innerrel->relids))
284  return false; /* contained expression references innerrel */
285  }
286 
287  /*
288  * Search for mergejoinable clauses that constrain the inner rel against
289  * either the outer rel or a pseudoconstant. If an operator is
290  * mergejoinable then it behaves like equality for some btree opclass, so
291  * it's what we want. The mergejoinability test also eliminates clauses
292  * containing volatile functions, which we couldn't depend on.
293  */
294  foreach(l, innerrel->joininfo)
295  {
296  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
297 
298  /*
299  * If the current join commutes with some other outer join(s) via
300  * outer join identity 3, there will be multiple clones of its join
301  * clauses in the joininfo list. We want to consider only the
302  * has_clone form of such clauses. Processing more than one form
303  * would be wasteful, and also some of the others would confuse the
304  * RINFO_IS_PUSHED_DOWN test below.
305  */
306  if (restrictinfo->is_clone)
307  continue; /* ignore it */
308 
309  /*
310  * If it's not a join clause for this outer join, we can't use it.
311  * Note that if the clause is pushed-down, then it is logically from
312  * above the outer join, even if it references no other rels (it might
313  * be from WHERE, for example).
314  */
315  if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
316  continue; /* ignore; not useful here */
317 
318  /* Ignore if it's not a mergejoinable clause */
319  if (!restrictinfo->can_join ||
320  restrictinfo->mergeopfamilies == NIL)
321  continue; /* not mergejoinable */
322 
323  /*
324  * Check if clause has the form "outer op inner" or "inner op outer",
325  * and if so mark which side is inner.
326  */
327  if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
328  innerrel->relids))
329  continue; /* no good for these input relations */
330 
331  /* OK, add to list */
332  clause_list = lappend(clause_list, restrictinfo);
333  }
334 
335  /*
336  * Now that we have the relevant equality join clauses, try to prove the
337  * innerrel distinct.
338  */
339  if (rel_is_distinct_for(root, innerrel, clause_list, NULL))
340  return true;
341 
342  /*
343  * Some day it would be nice to check for other methods of establishing
344  * distinctness.
345  */
346  return false;
347 }
348 
349 
350 /*
351  * Remove the target rel->relid and references to the target join from the
352  * planner's data structures, having determined that there is no need
353  * to include them in the query. Optionally replace them with subst if subst
354  * is non-negative.
355  *
356  * This function updates only parts needed for both left-join removal and
357  * self-join removal.
358  */
359 static void
361  int subst, SpecialJoinInfo *sjinfo,
362  Relids joinrelids)
363 {
364  int relid = rel->relid;
365  int ojrelid = (sjinfo != NULL) ? sjinfo->ojrelid : -1;
366  Index rti;
367  ListCell *l;
368 
369  /*
370  * Remove references to the rel from other baserels' attr_needed arrays.
371  */
372  for (rti = 1; rti < root->simple_rel_array_size; rti++)
373  {
374  RelOptInfo *otherrel = root->simple_rel_array[rti];
375  int attroff;
376 
377  /* there may be empty slots corresponding to non-baserel RTEs */
378  if (otherrel == NULL)
379  continue;
380 
381  Assert(otherrel->relid == rti); /* sanity check on array */
382 
383  /* no point in processing target rel itself */
384  if (otherrel == rel)
385  continue;
386 
387  for (attroff = otherrel->max_attr - otherrel->min_attr;
388  attroff >= 0;
389  attroff--)
390  {
391  otherrel->attr_needed[attroff] =
392  replace_relid(otherrel->attr_needed[attroff], relid, subst);
393  otherrel->attr_needed[attroff] =
394  replace_relid(otherrel->attr_needed[attroff], ojrelid, subst);
395  }
396 
397  /* Update lateral references. */
398  if (root->hasLateralRTEs)
399  {
400  RangeTblEntry *rte = root->simple_rte_array[rti];
401  ReplaceVarnoContext ctx = {.from = relid,.to = subst};
402 
403  if (rte->lateral)
404  {
405  replace_varno((Node *) otherrel->lateral_vars, relid, subst);
406 
407  /*
408  * Although we pass root->parse through cleanup procedure,
409  * but parse->rtable and rte contains refs to different copies
410  * of the subquery.
411  */
412  if (otherrel->rtekind == RTE_SUBQUERY)
415 #ifdef USE_ASSERT_CHECKING
416  /* Just check possibly hidden non-replaced relids */
417  Assert(!bms_is_member(relid, pull_varnos(root, (Node *) rte->tablesample)));
418  Assert(!bms_is_member(relid, pull_varnos(root, (Node *) rte->functions)));
419  Assert(!bms_is_member(relid, pull_varnos(root, (Node *) rte->tablefunc)));
420  Assert(!bms_is_member(relid, pull_varnos(root, (Node *) rte->values_lists)));
421 #endif
422  }
423  }
424 
425 
426  }
427 
428  /*
429  * Update all_baserels and related relid sets.
430  */
431  root->all_baserels = replace_relid(root->all_baserels, relid, subst);
432  root->outer_join_rels = replace_relid(root->outer_join_rels, ojrelid, subst);
433  root->all_query_rels = replace_relid(root->all_query_rels, relid, subst);
434  root->all_query_rels = replace_relid(root->all_query_rels, ojrelid, subst);
435 
436  /*
437  * Likewise remove references from SpecialJoinInfo data structures.
438  *
439  * This is relevant in case the outer join we're deleting is nested inside
440  * other outer joins: the upper joins' relid sets have to be adjusted. The
441  * RHS of the target outer join will be made empty here, but that's OK
442  * since caller will delete that SpecialJoinInfo entirely.
443  */
444  foreach(l, root->join_info_list)
445  {
446  SpecialJoinInfo *sjinf = (SpecialJoinInfo *) lfirst(l);
447 
448  sjinf->min_lefthand = replace_relid(sjinf->min_lefthand, relid, subst);
449  sjinf->min_righthand = replace_relid(sjinf->min_righthand, relid, subst);
450  sjinf->syn_lefthand = replace_relid(sjinf->syn_lefthand, relid, subst);
451  sjinf->syn_righthand = replace_relid(sjinf->syn_righthand, relid, subst);
452  sjinf->min_lefthand = replace_relid(sjinf->min_lefthand, ojrelid, subst);
453  sjinf->min_righthand = replace_relid(sjinf->min_righthand, ojrelid, subst);
454  sjinf->syn_lefthand = replace_relid(sjinf->syn_lefthand, ojrelid, subst);
455  sjinf->syn_righthand = replace_relid(sjinf->syn_righthand, ojrelid, subst);
456  /* relid cannot appear in these fields, but ojrelid can: */
457  sjinf->commute_above_l = replace_relid(sjinf->commute_above_l, ojrelid, subst);
458  sjinf->commute_above_r = replace_relid(sjinf->commute_above_r, ojrelid, subst);
459  sjinf->commute_below_l = replace_relid(sjinf->commute_below_l, ojrelid, subst);
460  sjinf->commute_below_r = replace_relid(sjinf->commute_below_r, ojrelid, subst);
461 
462  replace_varno((Node *) sjinf->semi_rhs_exprs, relid, subst);
463  }
464 
465  /*
466  * Likewise remove references from PlaceHolderVar data structures,
467  * removing any no-longer-needed placeholders entirely.
468  *
469  * Removal is a bit trickier than it might seem: we can remove PHVs that
470  * are used at the target rel and/or in the join qual, but not those that
471  * are used at join partner rels or above the join. It's not that easy to
472  * distinguish PHVs used at partner rels from those used in the join qual,
473  * since they will both have ph_needed sets that are subsets of
474  * joinrelids. However, a PHV used at a partner rel could not have the
475  * target rel in ph_eval_at, so we check that while deciding whether to
476  * remove or just update the PHV. There is no corresponding test in
477  * join_is_removable because it doesn't need to distinguish those cases.
478  */
479  foreach(l, root->placeholder_list)
480  {
481  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
482 
483  Assert(sjinfo == NULL || !bms_is_member(relid, phinfo->ph_lateral));
484  if (bms_is_subset(phinfo->ph_needed, joinrelids) &&
485  bms_is_member(relid, phinfo->ph_eval_at) &&
486  (sjinfo == NULL || !bms_is_member(ojrelid, phinfo->ph_eval_at)))
487  {
489  l);
490  root->placeholder_array[phinfo->phid] = NULL;
491  }
492  else
493  {
494  PlaceHolderVar *phv = phinfo->ph_var;
495 
496  phinfo->ph_eval_at = replace_relid(phinfo->ph_eval_at, relid, subst);
497  phinfo->ph_eval_at = replace_relid(phinfo->ph_eval_at, ojrelid, subst);
498  Assert(!bms_is_empty(phinfo->ph_eval_at)); /* checked previously */
499  phinfo->ph_needed = replace_relid(phinfo->ph_needed, relid, subst);
500  phinfo->ph_needed = replace_relid(phinfo->ph_needed, ojrelid, subst);
501  /* ph_needed might or might not become empty */
502  phinfo->ph_lateral = replace_relid(phinfo->ph_lateral, relid, subst);
503  /* ph_lateral might or might not be empty */
504  phv->phrels = replace_relid(phv->phrels, relid, subst);
505  phv->phrels = replace_relid(phv->phrels, ojrelid, subst);
506  Assert(!bms_is_empty(phv->phrels));
507  replace_varno((Node *) phv->phexpr, relid, subst);
508  Assert(phv->phnullingrels == NULL); /* no need to adjust */
509  }
510  }
511 }
512 
513 /*
514  * Remove the target relid and references to the target join from the
515  * planner's data structures, having determined that there is no need
516  * to include them in the query.
517  *
518  * We are not terribly thorough here. We only bother to update parts of
519  * the planner's data structures that will actually be consulted later.
520  */
521 static void
523  SpecialJoinInfo *sjinfo)
524 {
525  List *joininfos;
526  int ojrelid = sjinfo->ojrelid;
527  RelOptInfo *rel = find_base_rel(root, relid);
528  Relids join_plus_commute;
529  Relids joinrelids;
530  ListCell *l;
531 
532  /* Compute the relid set for the join we are considering */
533  joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
534  Assert(ojrelid != 0);
535  joinrelids = bms_add_member(joinrelids, ojrelid);
536 
537  remove_rel_from_query(root, rel, -1, sjinfo, joinrelids);
538 
539  /*
540  * Remove any joinquals referencing the rel from the joininfo lists.
541  *
542  * In some cases, a joinqual has to be put back after deleting its
543  * reference to the target rel. This can occur for pseudoconstant and
544  * outerjoin-delayed quals, which can get marked as requiring the rel in
545  * order to force them to be evaluated at or above the join. We can't
546  * just discard them, though. Only quals that logically belonged to the
547  * outer join being discarded should be removed from the query.
548  *
549  * We might encounter a qual that is a clone of a deletable qual with some
550  * outer-join relids added (see deconstruct_distribute_oj_quals). To
551  * ensure we get rid of such clones as well, add the relids of all OJs
552  * commutable with this one to the set we test against for
553  * pushed-down-ness.
554  */
555  join_plus_commute = bms_union(joinrelids,
556  sjinfo->commute_above_r);
557  join_plus_commute = bms_add_members(join_plus_commute,
558  sjinfo->commute_below_l);
559 
560  /*
561  * We must make a copy of the rel's old joininfo list before starting the
562  * loop, because otherwise remove_join_clause_from_rels would destroy the
563  * list while we're scanning it.
564  */
565  joininfos = list_copy(rel->joininfo);
566  foreach(l, joininfos)
567  {
568  RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
569 
570  remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
571 
572  if (RINFO_IS_PUSHED_DOWN(rinfo, join_plus_commute))
573  {
574  /*
575  * There might be references to relid or ojrelid in the
576  * RestrictInfo's relid sets, as a consequence of PHVs having had
577  * ph_eval_at sets that include those. We already checked above
578  * that any such PHV is safe (and updated its ph_eval_at), so we
579  * can just drop those references.
580  */
581  remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
582 
583  /*
584  * Cross-check that the clause itself does not reference the
585  * target rel or join.
586  */
587 #ifdef USE_ASSERT_CHECKING
588  {
589  Relids clause_varnos = pull_varnos(root,
590  (Node *) rinfo->clause);
591 
592  Assert(!bms_is_member(relid, clause_varnos));
593  Assert(!bms_is_member(ojrelid, clause_varnos));
594  }
595 #endif
596  /* Now throw it back into the joininfo lists */
597  distribute_restrictinfo_to_rels(root, rinfo);
598  }
599  }
600 
601  /*
602  * Likewise remove references from EquivalenceClasses.
603  */
604  foreach(l, root->eq_classes)
605  {
607 
608  if (bms_is_member(relid, ec->ec_relids) ||
609  bms_is_member(ojrelid, ec->ec_relids))
610  remove_rel_from_eclass(ec, relid, ojrelid);
611  }
612 
613  /*
614  * There may be references to the rel in root->fkey_list, but if so,
615  * match_foreign_keys_to_quals() will get rid of them.
616  */
617 
618  /*
619  * Finally, remove the rel from the baserel array to prevent it from being
620  * referenced again. (We can't do this earlier because
621  * remove_join_clause_from_rels will touch it.)
622  */
623  root->simple_rel_array[relid] = NULL;
624 
625  /* And nuke the RelOptInfo, just in case there's another access path */
626  pfree(rel);
627 }
628 
629 /*
630  * Remove any references to relid or ojrelid from the RestrictInfo.
631  *
632  * We only bother to clean out bits in clause_relids and required_relids,
633  * not nullingrel bits in contained Vars and PHVs. (This might have to be
634  * improved sometime.) However, if the RestrictInfo contains an OR clause
635  * we have to also clean up the sub-clauses.
636  */
637 static void
638 remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
639 {
640  /*
641  * The clause_relids probably aren't shared with anything else, but let's
642  * copy them just to be sure.
643  */
644  rinfo->clause_relids = bms_copy(rinfo->clause_relids);
645  rinfo->clause_relids = bms_del_member(rinfo->clause_relids, relid);
646  rinfo->clause_relids = bms_del_member(rinfo->clause_relids, ojrelid);
647  /* Likewise for required_relids */
648  rinfo->required_relids = bms_copy(rinfo->required_relids);
649  rinfo->required_relids = bms_del_member(rinfo->required_relids, relid);
650  rinfo->required_relids = bms_del_member(rinfo->required_relids, ojrelid);
651 
652  /* If it's an OR, recurse to clean up sub-clauses */
653  if (restriction_is_or_clause(rinfo))
654  {
655  ListCell *lc;
656 
657  Assert(is_orclause(rinfo->orclause));
658  foreach(lc, ((BoolExpr *) rinfo->orclause)->args)
659  {
660  Node *orarg = (Node *) lfirst(lc);
661 
662  /* OR arguments should be ANDs or sub-RestrictInfos */
663  if (is_andclause(orarg))
664  {
665  List *andargs = ((BoolExpr *) orarg)->args;
666  ListCell *lc2;
667 
668  foreach(lc2, andargs)
669  {
670  RestrictInfo *rinfo2 = lfirst_node(RestrictInfo, lc2);
671 
672  remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
673  }
674  }
675  else
676  {
677  RestrictInfo *rinfo2 = castNode(RestrictInfo, orarg);
678 
679  remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
680  }
681  }
682  }
683 }
684 
685 /*
686  * Remove any references to relid or ojrelid from the EquivalenceClass.
687  *
688  * Like remove_rel_from_restrictinfo, we don't worry about cleaning out
689  * any nullingrel bits in contained Vars and PHVs. (This might have to be
690  * improved sometime.) We do need to fix the EC and EM relid sets to ensure
691  * that implied join equalities will be generated at the appropriate join
692  * level(s).
693  */
694 static void
695 remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
696 {
697  ListCell *lc;
698 
699  /* Fix up the EC's overall relids */
700  ec->ec_relids = bms_del_member(ec->ec_relids, relid);
701  ec->ec_relids = bms_del_member(ec->ec_relids, ojrelid);
702 
703  /*
704  * Fix up the member expressions. Any non-const member that ends with
705  * empty em_relids must be a Var or PHV of the removed relation. We don't
706  * need it anymore, so we can drop it.
707  */
708  foreach(lc, ec->ec_members)
709  {
710  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
711 
712  if (bms_is_member(relid, cur_em->em_relids) ||
713  bms_is_member(ojrelid, cur_em->em_relids))
714  {
715  Assert(!cur_em->em_is_const);
716  cur_em->em_relids = bms_del_member(cur_em->em_relids, relid);
717  cur_em->em_relids = bms_del_member(cur_em->em_relids, ojrelid);
718  if (bms_is_empty(cur_em->em_relids))
720  }
721  }
722 
723  /* Fix up the source clauses, in case we can re-use them later */
724  foreach(lc, ec->ec_sources)
725  {
726  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
727 
728  remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
729  }
730 
731  /*
732  * Rather than expend code on fixing up any already-derived clauses, just
733  * drop them. (At this point, any such clauses would be base restriction
734  * clauses, which we'd not need anymore anyway.)
735  */
736  ec->ec_derives = NIL;
737 }
738 
739 /*
740  * Remove any occurrences of the target relid from a joinlist structure.
741  *
742  * It's easiest to build a whole new list structure, so we handle it that
743  * way. Efficiency is not a big deal here.
744  *
745  * *nremoved is incremented by the number of occurrences removed (there
746  * should be exactly one, but the caller checks that).
747  */
748 static List *
749 remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
750 {
751  List *result = NIL;
752  ListCell *jl;
753 
754  foreach(jl, joinlist)
755  {
756  Node *jlnode = (Node *) lfirst(jl);
757 
758  if (IsA(jlnode, RangeTblRef))
759  {
760  int varno = ((RangeTblRef *) jlnode)->rtindex;
761 
762  if (varno == relid)
763  (*nremoved)++;
764  else
765  result = lappend(result, jlnode);
766  }
767  else if (IsA(jlnode, List))
768  {
769  /* Recurse to handle subproblem */
770  List *sublist;
771 
772  sublist = remove_rel_from_joinlist((List *) jlnode,
773  relid, nremoved);
774  /* Avoid including empty sub-lists in the result */
775  if (sublist)
776  result = lappend(result, sublist);
777  }
778  else
779  {
780  elog(ERROR, "unrecognized joinlist node type: %d",
781  (int) nodeTag(jlnode));
782  }
783  }
784 
785  return result;
786 }
787 
788 
789 /*
790  * reduce_unique_semijoins
791  * Check for semijoins that can be simplified to plain inner joins
792  * because the inner relation is provably unique for the join clauses.
793  *
794  * Ideally this would happen during reduce_outer_joins, but we don't have
795  * enough information at that point.
796  *
797  * To perform the strength reduction when applicable, we need only delete
798  * the semijoin's SpecialJoinInfo from root->join_info_list. (We don't
799  * bother fixing the join type attributed to it in the query jointree,
800  * since that won't be consulted again.)
801  */
802 void
804 {
805  ListCell *lc;
806 
807  /*
808  * Scan the join_info_list to find semijoins.
809  */
810  foreach(lc, root->join_info_list)
811  {
812  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
813  int innerrelid;
814  RelOptInfo *innerrel;
815  Relids joinrelids;
816  List *restrictlist;
817 
818  /*
819  * Must be a semijoin to a single baserel, else we aren't going to be
820  * able to do anything with it.
821  */
822  if (sjinfo->jointype != JOIN_SEMI)
823  continue;
824 
825  if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
826  continue;
827 
828  innerrel = find_base_rel(root, innerrelid);
829 
830  /*
831  * Before we trouble to run generate_join_implied_equalities, make a
832  * quick check to eliminate cases in which we will surely be unable to
833  * prove uniqueness of the innerrel.
834  */
835  if (!rel_supports_distinctness(root, innerrel))
836  continue;
837 
838  /* Compute the relid set for the join we are considering */
839  joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
840  Assert(sjinfo->ojrelid == 0); /* SEMI joins don't have RT indexes */
841 
842  /*
843  * Since we're only considering a single-rel RHS, any join clauses it
844  * has must be clauses linking it to the semijoin's min_lefthand. We
845  * can also consider EC-derived join clauses.
846  */
847  restrictlist =
849  joinrelids,
850  sjinfo->min_lefthand,
851  innerrel,
852  NULL),
853  innerrel->joininfo);
854 
855  /* Test whether the innerrel is unique for those clauses. */
856  if (!innerrel_is_unique(root,
857  joinrelids, sjinfo->min_lefthand, innerrel,
858  JOIN_SEMI, restrictlist, true))
859  continue;
860 
861  /* OK, remove the SpecialJoinInfo from the list. */
863  }
864 }
865 
866 
867 /*
868  * rel_supports_distinctness
869  * Could the relation possibly be proven distinct on some set of columns?
870  *
871  * This is effectively a pre-checking function for rel_is_distinct_for().
872  * It must return true if rel_is_distinct_for() could possibly return true
873  * with this rel, but it should not expend a lot of cycles. The idea is
874  * that callers can avoid doing possibly-expensive processing to compute
875  * rel_is_distinct_for()'s argument lists if the call could not possibly
876  * succeed.
877  */
878 static bool
880 {
881  /* We only know about baserels ... */
882  if (rel->reloptkind != RELOPT_BASEREL)
883  return false;
884  if (rel->rtekind == RTE_RELATION)
885  {
886  /*
887  * For a plain relation, we only know how to prove uniqueness by
888  * reference to unique indexes. Make sure there's at least one
889  * suitable unique index. It must be immediately enforced, and not a
890  * partial index. (Keep these conditions in sync with
891  * relation_has_unique_index_for!)
892  */
893  ListCell *lc;
894 
895  foreach(lc, rel->indexlist)
896  {
897  IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
898 
899  if (ind->unique && ind->immediate && ind->indpred == NIL)
900  return true;
901  }
902  }
903  else if (rel->rtekind == RTE_SUBQUERY)
904  {
905  Query *subquery = root->simple_rte_array[rel->relid]->subquery;
906 
907  /* Check if the subquery has any qualities that support distinctness */
908  if (query_supports_distinctness(subquery))
909  return true;
910  }
911  /* We have no proof rules for any other rtekinds. */
912  return false;
913 }
914 
915 /*
916  * rel_is_distinct_for
917  * Does the relation return only distinct rows according to clause_list?
918  *
919  * clause_list is a list of join restriction clauses involving this rel and
920  * some other one. Return true if no two rows emitted by this rel could
921  * possibly join to the same row of the other rel.
922  *
923  * The caller must have already determined that each condition is a
924  * mergejoinable equality with an expression in this relation on one side, and
925  * an expression not involving this relation on the other. The transient
926  * outer_is_left flag is used to identify which side references this relation:
927  * left side if outer_is_left is false, right side if it is true.
928  *
929  * Note that the passed-in clause_list may be destructively modified! This
930  * is OK for current uses, because the clause_list is built by the caller for
931  * the sole purpose of passing to this function.
932  *
933  * outer_exprs contains the right sides of baserestrictinfo clauses looking
934  * like x = const if distinctness is derived from such clauses, not joininfo
935  * clause. Pass NULL to the outer_exprs, if its value is not needed.
936  */
937 static bool
938 rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list,
939  List **extra_clauses)
940 {
941  /*
942  * We could skip a couple of tests here if we assume all callers checked
943  * rel_supports_distinctness first, but it doesn't seem worth taking any
944  * risk for.
945  */
946  if (rel->reloptkind != RELOPT_BASEREL)
947  return false;
948  if (rel->rtekind == RTE_RELATION)
949  {
950  /*
951  * Examine the indexes to see if we have a matching unique index.
952  * relation_has_unique_index_ext automatically adds any usable
953  * restriction clauses for the rel, so we needn't do that here.
954  */
955  if (relation_has_unique_index_ext(root, rel, clause_list, NIL, NIL,
956  extra_clauses))
957  return true;
958  }
959  else if (rel->rtekind == RTE_SUBQUERY)
960  {
961  Index relid = rel->relid;
962  Query *subquery = root->simple_rte_array[relid]->subquery;
963  List *colnos = NIL;
964  List *opids = NIL;
965  ListCell *l;
966 
967  /*
968  * Build the argument lists for query_is_distinct_for: a list of
969  * output column numbers that the query needs to be distinct over, and
970  * a list of equality operators that the output columns need to be
971  * distinct according to.
972  *
973  * (XXX we are not considering restriction clauses attached to the
974  * subquery; is that worth doing?)
975  */
976  foreach(l, clause_list)
977  {
979  Oid op;
980  Var *var;
981 
982  /*
983  * Get the equality operator we need uniqueness according to.
984  * (This might be a cross-type operator and thus not exactly the
985  * same operator the subquery would consider; that's all right
986  * since query_is_distinct_for can resolve such cases.) The
987  * caller's mergejoinability test should have selected only
988  * OpExprs.
989  */
990  op = castNode(OpExpr, rinfo->clause)->opno;
991 
992  /* caller identified the inner side for us */
993  if (rinfo->outer_is_left)
994  var = (Var *) get_rightop(rinfo->clause);
995  else
996  var = (Var *) get_leftop(rinfo->clause);
997 
998  /*
999  * We may ignore any RelabelType node above the operand. (There
1000  * won't be more than one, since eval_const_expressions() has been
1001  * applied already.)
1002  */
1003  if (var && IsA(var, RelabelType))
1004  var = (Var *) ((RelabelType *) var)->arg;
1005 
1006  /*
1007  * If inner side isn't a Var referencing a subquery output column,
1008  * this clause doesn't help us.
1009  */
1010  if (!var || !IsA(var, Var) ||
1011  var->varno != relid || var->varlevelsup != 0)
1012  continue;
1013 
1014  colnos = lappend_int(colnos, var->varattno);
1015  opids = lappend_oid(opids, op);
1016  }
1017 
1018  if (query_is_distinct_for(subquery, colnos, opids))
1019  return true;
1020  }
1021  return false;
1022 }
1023 
1024 
1025 /*
1026  * query_supports_distinctness - could the query possibly be proven distinct
1027  * on some set of output columns?
1028  *
1029  * This is effectively a pre-checking function for query_is_distinct_for().
1030  * It must return true if query_is_distinct_for() could possibly return true
1031  * with this query, but it should not expend a lot of cycles. The idea is
1032  * that callers can avoid doing possibly-expensive processing to compute
1033  * query_is_distinct_for()'s argument lists if the call could not possibly
1034  * succeed.
1035  */
1036 bool
1038 {
1039  /* SRFs break distinctness except with DISTINCT, see below */
1040  if (query->hasTargetSRFs && query->distinctClause == NIL)
1041  return false;
1042 
1043  /* check for features we can prove distinctness with */
1044  if (query->distinctClause != NIL ||
1045  query->groupClause != NIL ||
1046  query->groupingSets != NIL ||
1047  query->hasAggs ||
1048  query->havingQual ||
1049  query->setOperations)
1050  return true;
1051 
1052  return false;
1053 }
1054 
1055 /*
1056  * query_is_distinct_for - does query never return duplicates of the
1057  * specified columns?
1058  *
1059  * query is a not-yet-planned subquery (in current usage, it's always from
1060  * a subquery RTE, which the planner avoids scribbling on).
1061  *
1062  * colnos is an integer list of output column numbers (resno's). We are
1063  * interested in whether rows consisting of just these columns are certain
1064  * to be distinct. "Distinctness" is defined according to whether the
1065  * corresponding upper-level equality operators listed in opids would think
1066  * the values are distinct. (Note: the opids entries could be cross-type
1067  * operators, and thus not exactly the equality operators that the subquery
1068  * would use itself. We use equality_ops_are_compatible() to check
1069  * compatibility. That looks at btree or hash opfamily membership, and so
1070  * should give trustworthy answers for all operators that we might need
1071  * to deal with here.)
1072  */
1073 bool
1074 query_is_distinct_for(Query *query, List *colnos, List *opids)
1075 {
1076  ListCell *l;
1077  Oid opid;
1078 
1079  Assert(list_length(colnos) == list_length(opids));
1080 
1081  /*
1082  * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
1083  * columns in the DISTINCT clause appear in colnos and operator semantics
1084  * match. This is true even if there are SRFs in the DISTINCT columns or
1085  * elsewhere in the tlist.
1086  */
1087  if (query->distinctClause)
1088  {
1089  foreach(l, query->distinctClause)
1090  {
1091  SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
1093  query->targetList);
1094 
1095  opid = distinct_col_search(tle->resno, colnos, opids);
1096  if (!OidIsValid(opid) ||
1097  !equality_ops_are_compatible(opid, sgc->eqop))
1098  break; /* exit early if no match */
1099  }
1100  if (l == NULL) /* had matches for all? */
1101  return true;
1102  }
1103 
1104  /*
1105  * Otherwise, a set-returning function in the query's targetlist can
1106  * result in returning duplicate rows, despite any grouping that might
1107  * occur before tlist evaluation. (If all tlist SRFs are within GROUP BY
1108  * columns, it would be safe because they'd be expanded before grouping.
1109  * But it doesn't currently seem worth the effort to check for that.)
1110  */
1111  if (query->hasTargetSRFs)
1112  return false;
1113 
1114  /*
1115  * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
1116  * the grouped columns appear in colnos and operator semantics match.
1117  */
1118  if (query->groupClause && !query->groupingSets)
1119  {
1120  foreach(l, query->groupClause)
1121  {
1122  SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
1124  query->targetList);
1125 
1126  opid = distinct_col_search(tle->resno, colnos, opids);
1127  if (!OidIsValid(opid) ||
1128  !equality_ops_are_compatible(opid, sgc->eqop))
1129  break; /* exit early if no match */
1130  }
1131  if (l == NULL) /* had matches for all? */
1132  return true;
1133  }
1134  else if (query->groupingSets)
1135  {
1136  /*
1137  * If we have grouping sets with expressions, we probably don't have
1138  * uniqueness and analysis would be hard. Punt.
1139  */
1140  if (query->groupClause)
1141  return false;
1142 
1143  /*
1144  * If we have no groupClause (therefore no grouping expressions), we
1145  * might have one or many empty grouping sets. If there's just one,
1146  * then we're returning only one row and are certainly unique. But
1147  * otherwise, we know we're certainly not unique.
1148  */
1149  if (list_length(query->groupingSets) == 1 &&
1150  ((GroupingSet *) linitial(query->groupingSets))->kind == GROUPING_SET_EMPTY)
1151  return true;
1152  else
1153  return false;
1154  }
1155  else
1156  {
1157  /*
1158  * If we have no GROUP BY, but do have aggregates or HAVING, then the
1159  * result is at most one row so it's surely unique, for any operators.
1160  */
1161  if (query->hasAggs || query->havingQual)
1162  return true;
1163  }
1164 
1165  /*
1166  * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
1167  * except with ALL.
1168  */
1169  if (query->setOperations)
1170  {
1172 
1173  Assert(topop->op != SETOP_NONE);
1174 
1175  if (!topop->all)
1176  {
1177  ListCell *lg;
1178 
1179  /* We're good if all the nonjunk output columns are in colnos */
1180  lg = list_head(topop->groupClauses);
1181  foreach(l, query->targetList)
1182  {
1183  TargetEntry *tle = (TargetEntry *) lfirst(l);
1184  SortGroupClause *sgc;
1185 
1186  if (tle->resjunk)
1187  continue; /* ignore resjunk columns */
1188 
1189  /* non-resjunk columns should have grouping clauses */
1190  Assert(lg != NULL);
1191  sgc = (SortGroupClause *) lfirst(lg);
1192  lg = lnext(topop->groupClauses, lg);
1193 
1194  opid = distinct_col_search(tle->resno, colnos, opids);
1195  if (!OidIsValid(opid) ||
1196  !equality_ops_are_compatible(opid, sgc->eqop))
1197  break; /* exit early if no match */
1198  }
1199  if (l == NULL) /* had matches for all? */
1200  return true;
1201  }
1202  }
1203 
1204  /*
1205  * XXX Are there any other cases in which we can easily see the result
1206  * must be distinct?
1207  *
1208  * If you do add more smarts to this function, be sure to update
1209  * query_supports_distinctness() to match.
1210  */
1211 
1212  return false;
1213 }
1214 
1215 /*
1216  * distinct_col_search - subroutine for query_is_distinct_for
1217  *
1218  * If colno is in colnos, return the corresponding element of opids,
1219  * else return InvalidOid. (Ordinarily colnos would not contain duplicates,
1220  * but if it does, we arbitrarily select the first match.)
1221  */
1222 static Oid
1223 distinct_col_search(int colno, List *colnos, List *opids)
1224 {
1225  ListCell *lc1,
1226  *lc2;
1227 
1228  forboth(lc1, colnos, lc2, opids)
1229  {
1230  if (colno == lfirst_int(lc1))
1231  return lfirst_oid(lc2);
1232  }
1233  return InvalidOid;
1234 }
1235 
1236 
1237 /*
1238  * innerrel_is_unique
1239  * Check if the innerrel provably contains at most one tuple matching any
1240  * tuple from the outerrel, based on join clauses in the 'restrictlist'.
1241  *
1242  * We need an actual RelOptInfo for the innerrel, but it's sufficient to
1243  * identify the outerrel by its Relids. This asymmetry supports use of this
1244  * function before joinrels have been built. (The caller is expected to
1245  * also supply the joinrelids, just to save recalculating that.)
1246  *
1247  * The proof must be made based only on clauses that will be "joinquals"
1248  * rather than "otherquals" at execution. For an inner join there's no
1249  * difference; but if the join is outer, we must ignore pushed-down quals,
1250  * as those will become "otherquals". Note that this means the answer might
1251  * vary depending on whether IS_OUTER_JOIN(jointype); since we cache the
1252  * answer without regard to that, callers must take care not to call this
1253  * with jointypes that would be classified differently by IS_OUTER_JOIN().
1254  *
1255  * The actual proof is undertaken by is_innerrel_unique_for(); this function
1256  * is a frontend that is mainly concerned with caching the answers.
1257  * In particular, the force_cache argument allows overriding the internal
1258  * heuristic about whether to cache negative answers; it should be "true"
1259  * if making an inquiry that is not part of the normal bottom-up join search
1260  * sequence.
1261  */
1262 bool
1264  Relids joinrelids,
1265  Relids outerrelids,
1266  RelOptInfo *innerrel,
1267  JoinType jointype,
1268  List *restrictlist,
1269  bool force_cache)
1270 {
1271  return innerrel_is_unique_ext(root, joinrelids, outerrelids, innerrel,
1272  jointype, restrictlist, force_cache, NULL);
1273 }
1274 
1275 /*
1276  * innerrel_is_unique_ext
1277  * Do the same as innerrel_is_unique(), but also set to '*extra_clauses'
1278  * additional clauses from a baserestrictinfo list that were used to prove
1279  * uniqueness. A non NULL 'extra_clauses' indicates that we're checking
1280  * for self-join and correspondingly dealing with filtered clauses.
1281  */
1282 bool
1284  Relids joinrelids,
1285  Relids outerrelids,
1286  RelOptInfo *innerrel,
1287  JoinType jointype,
1288  List *restrictlist,
1289  bool force_cache,
1290  List **extra_clauses)
1291 {
1292  MemoryContext old_context;
1293  ListCell *lc;
1294  UniqueRelInfo *uniqueRelInfo;
1295  List *outer_exprs = NIL;
1296  bool self_join = (extra_clauses != NULL);
1297 
1298  /* Certainly can't prove uniqueness when there are no joinclauses */
1299  if (restrictlist == NIL)
1300  return false;
1301 
1302  /*
1303  * Make a quick check to eliminate cases in which we will surely be unable
1304  * to prove uniqueness of the innerrel.
1305  */
1306  if (!rel_supports_distinctness(root, innerrel))
1307  return false;
1308 
1309  /*
1310  * Query the cache to see if we've managed to prove that innerrel is
1311  * unique for any subset of this outerrel. For non self-join search, we
1312  * don't need an exact match, as extra outerrels can't make the innerrel
1313  * any less unique (or more formally, the restrictlist for a join to a
1314  * superset outerrel must be a superset of the conditions we successfully
1315  * used before). For self-join search, we require an exact match of
1316  * outerrels, because we need extra clauses to be valid for our case.
1317  * Also, for self-join checking we've filtered the clauses list. Thus,
1318  * for a self-join search, we can match only the result cached for another
1319  * self-join check.
1320  */
1321  foreach(lc, innerrel->unique_for_rels)
1322  {
1323  uniqueRelInfo = (UniqueRelInfo *) lfirst(lc);
1324 
1325  if ((!self_join && bms_is_subset(uniqueRelInfo->outerrelids, outerrelids)) ||
1326  (self_join && bms_equal(uniqueRelInfo->outerrelids, outerrelids) &&
1327  uniqueRelInfo->self_join))
1328  {
1329  if (extra_clauses)
1330  *extra_clauses = uniqueRelInfo->extra_clauses;
1331  return true; /* Success! */
1332  }
1333  }
1334 
1335  /*
1336  * Conversely, we may have already determined that this outerrel, or some
1337  * superset thereof, cannot prove this innerrel to be unique.
1338  */
1339  foreach(lc, innerrel->non_unique_for_rels)
1340  {
1341  Relids unique_for_rels = (Relids) lfirst(lc);
1342 
1343  if (bms_is_subset(outerrelids, unique_for_rels))
1344  return false;
1345  }
1346 
1347  /* No cached information, so try to make the proof. */
1348  if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
1349  jointype, restrictlist,
1350  self_join ? &outer_exprs : NULL))
1351  {
1352  /*
1353  * Cache the positive result for future probes, being sure to keep it
1354  * in the planner_cxt even if we are working in GEQO.
1355  *
1356  * Note: one might consider trying to isolate the minimal subset of
1357  * the outerrels that proved the innerrel unique. But it's not worth
1358  * the trouble, because the planner builds up joinrels incrementally
1359  * and so we'll see the minimally sufficient outerrels before any
1360  * supersets of them anyway.
1361  */
1362  old_context = MemoryContextSwitchTo(root->planner_cxt);
1363  uniqueRelInfo = makeNode(UniqueRelInfo);
1364  uniqueRelInfo->outerrelids = bms_copy(outerrelids);
1365  uniqueRelInfo->self_join = self_join;
1366  uniqueRelInfo->extra_clauses = outer_exprs;
1367  innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
1368  uniqueRelInfo);
1369  MemoryContextSwitchTo(old_context);
1370 
1371  if (extra_clauses)
1372  *extra_clauses = outer_exprs;
1373  return true; /* Success! */
1374  }
1375  else
1376  {
1377  /*
1378  * None of the join conditions for outerrel proved innerrel unique, so
1379  * we can safely reject this outerrel or any subset of it in future
1380  * checks.
1381  *
1382  * However, in normal planning mode, caching this knowledge is totally
1383  * pointless; it won't be queried again, because we build up joinrels
1384  * from smaller to larger. It is useful in GEQO mode, where the
1385  * knowledge can be carried across successive planning attempts; and
1386  * it's likely to be useful when using join-search plugins, too. Hence
1387  * cache when join_search_private is non-NULL. (Yeah, that's a hack,
1388  * but it seems reasonable.)
1389  *
1390  * Also, allow callers to override that heuristic and force caching;
1391  * that's useful for reduce_unique_semijoins, which calls here before
1392  * the normal join search starts.
1393  */
1394  if (force_cache || root->join_search_private)
1395  {
1396  old_context = MemoryContextSwitchTo(root->planner_cxt);
1397  innerrel->non_unique_for_rels =
1398  lappend(innerrel->non_unique_for_rels,
1399  bms_copy(outerrelids));
1400  MemoryContextSwitchTo(old_context);
1401  }
1402 
1403  return false;
1404  }
1405 }
1406 
1407 /*
1408  * is_innerrel_unique_for
1409  * Check if the innerrel provably contains at most one tuple matching any
1410  * tuple from the outerrel, based on join clauses in the 'restrictlist'.
1411  */
1412 static bool
1414  Relids joinrelids,
1415  Relids outerrelids,
1416  RelOptInfo *innerrel,
1417  JoinType jointype,
1418  List *restrictlist,
1419  List **extra_clauses)
1420 {
1421  List *clause_list = NIL;
1422  ListCell *lc;
1423 
1424  /*
1425  * Search for mergejoinable clauses that constrain the inner rel against
1426  * the outer rel. If an operator is mergejoinable then it behaves like
1427  * equality for some btree opclass, so it's what we want. The
1428  * mergejoinability test also eliminates clauses containing volatile
1429  * functions, which we couldn't depend on.
1430  */
1431  foreach(lc, restrictlist)
1432  {
1433  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
1434 
1435  /*
1436  * As noted above, if it's a pushed-down clause and we're at an outer
1437  * join, we can't use it.
1438  */
1439  if (IS_OUTER_JOIN(jointype) &&
1440  RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
1441  continue;
1442 
1443  /* Ignore if it's not a mergejoinable clause */
1444  if (!restrictinfo->can_join ||
1445  restrictinfo->mergeopfamilies == NIL)
1446  continue; /* not mergejoinable */
1447 
1448  /*
1449  * Check if the clause has the form "outer op inner" or "inner op
1450  * outer", and if so mark which side is inner.
1451  */
1452  if (!clause_sides_match_join(restrictinfo, outerrelids,
1453  innerrel->relids))
1454  continue; /* no good for these input relations */
1455 
1456  /* OK, add to the list */
1457  clause_list = lappend(clause_list, restrictinfo);
1458  }
1459 
1460  /* Let rel_is_distinct_for() do the hard work */
1461  return rel_is_distinct_for(root, innerrel, clause_list, extra_clauses);
1462 }
1463 
1464 /*
1465  * Replace each occurrence of removing relid with the keeping one
1466  */
1467 static void
1468 replace_varno(Node *node, int from, int to)
1469 {
1470  ReplaceVarnoContext ctx;
1471 
1472  if (to <= 0)
1473  return;
1474 
1475  ctx.from = from;
1476  ctx.to = to;
1477  replace_varno_walker(node, &ctx);
1478 }
1479 
1480 /*
1481  * Walker function for replace_varno()
1482  */
1483 static bool
1485 {
1486  if (node == NULL)
1487  return false;
1488 
1489  if (IsA(node, Var))
1490  {
1491  Var *var = (Var *) node;
1492 
1493  if (var->varno == ctx->from)
1494  {
1495  var->varno = ctx->to;
1496  var->varnosyn = ctx->to;
1497  }
1498  return false;
1499  }
1500  else if (IsA(node, PlaceHolderVar))
1501  {
1502  PlaceHolderVar *phv = (PlaceHolderVar *) node;
1503 
1504  phv->phrels = replace_relid(phv->phrels, ctx->from, ctx->to);
1505  phv->phnullingrels = replace_relid(phv->phnullingrels, ctx->from, ctx->to);
1506 
1507  /* fall through to recurse into the placeholder's expression */
1508  }
1509  else if (IsA(node, RestrictInfo))
1510  {
1511  RestrictInfo *rinfo = (RestrictInfo *) node;
1512  int relid = -1;
1513  bool is_req_equal =
1514  (rinfo->required_relids == rinfo->clause_relids);
1515 
1516  if (bms_is_member(ctx->from, rinfo->clause_relids))
1517  {
1518  replace_varno((Node *) rinfo->clause, ctx->from, ctx->to);
1519  replace_varno((Node *) rinfo->orclause, ctx->from, ctx->to);
1520  rinfo->clause_relids = replace_relid(rinfo->clause_relids, ctx->from, ctx->to);
1521  rinfo->left_relids = replace_relid(rinfo->left_relids, ctx->from, ctx->to);
1522  rinfo->right_relids = replace_relid(rinfo->right_relids, ctx->from, ctx->to);
1523  }
1524 
1525  if (is_req_equal)
1526  rinfo->required_relids = rinfo->clause_relids;
1527  else
1528  rinfo->required_relids = replace_relid(rinfo->required_relids, ctx->from, ctx->to);
1529 
1530  rinfo->outer_relids = replace_relid(rinfo->outer_relids, ctx->from, ctx->to);
1531  rinfo->incompatible_relids = replace_relid(rinfo->incompatible_relids, ctx->from, ctx->to);
1532 
1533  if (rinfo->mergeopfamilies &&
1534  bms_get_singleton_member(rinfo->clause_relids, &relid) &&
1535  relid == ctx->to && IsA(rinfo->clause, OpExpr))
1536  {
1537  Expr *leftOp;
1538  Expr *rightOp;
1539 
1540  leftOp = (Expr *) get_leftop(rinfo->clause);
1541  rightOp = (Expr *) get_rightop(rinfo->clause);
1542 
1543  if (leftOp != NULL && equal(leftOp, rightOp))
1544  {
1545  NullTest *ntest = makeNode(NullTest);
1546 
1547  ntest->arg = leftOp;
1548  ntest->nulltesttype = IS_NOT_NULL;
1549  ntest->argisrow = false;
1550  ntest->location = -1;
1551  rinfo->clause = (Expr *) ntest;
1552  rinfo->mergeopfamilies = NIL;
1553  }
1554  Assert(rinfo->orclause == NULL);
1555  }
1556 
1557  return false;
1558  }
1559  return expression_tree_walker(node, replace_varno_walker, (void *) ctx);
1560 }
1561 
1562 /*
1563  * Substitute newId by oldId in relids.
1564  *
1565  * We must make a copy of the original Bitmapset before making any
1566  * modifications, because the same pointer to it might be shared among
1567  * different places.
1568  */
1569 static Bitmapset *
1570 replace_relid(Relids relids, int oldId, int newId)
1571 {
1572  if (oldId < 0)
1573  return relids;
1574 
1575  /* Delete relid without substitution. */
1576  if (newId < 0)
1577  return bms_del_member(bms_copy(relids), oldId);
1578 
1579  /* Substitute newId for oldId. */
1580  if (bms_is_member(oldId, relids))
1581  return bms_add_member(bms_del_member(bms_copy(relids), oldId), newId);
1582 
1583  return relids;
1584 }
1585 
1586 /*
1587  * Update EC members to point to the remaining relation instead of the removed
1588  * one, removing duplicates.
1589  *
1590  * Restriction clauses for base relations are already distributed to
1591  * the respective baserestrictinfo lists (see
1592  * generate_implied_equalities_for_column). The above code has already processed
1593  * this list, and updated these clauses to reference the remaining
1594  * relation, so we can skip them here based on their relids.
1595  *
1596  * Likewise, we have already processed the join clauses that join the
1597  * removed relation to the remaining one.
1598  *
1599  * Finally, there are join clauses that join the removed relation to
1600  * some third relation. We can't just delete the source clauses and
1601  * regenerate them from the EC because the corresponding equality
1602  * operators might be missing (see the handling of ec_broken).
1603  * Therefore, we will update the references in the source clauses.
1604  *
1605  * Derived clauses can be generated again, so it is simpler to just
1606  * delete them.
1607  */
1608 static void
1609 update_eclasses(EquivalenceClass *ec, int from, int to)
1610 {
1611  List *new_members = NIL;
1612  List *new_sources = NIL;
1613  ListCell *lc;
1614  ListCell *lc1;
1615 
1616  foreach(lc, ec->ec_members)
1617  {
1619  bool is_redundant = false;
1620 
1621  if (!bms_is_member(from, em->em_relids))
1622  {
1623  new_members = lappend(new_members, em);
1624  continue;
1625  }
1626 
1627  em->em_relids = replace_relid(em->em_relids, from, to);
1628  em->em_jdomain->jd_relids = replace_relid(em->em_jdomain->jd_relids, from, to);
1629 
1630  /* We only process inner joins */
1631  replace_varno((Node *) em->em_expr, from, to);
1632 
1633  foreach(lc1, new_members)
1634  {
1636 
1637  if (!equal(em->em_relids, other->em_relids))
1638  continue;
1639 
1640  if (equal(em->em_expr, other->em_expr))
1641  {
1642  is_redundant = true;
1643  break;
1644  }
1645  }
1646 
1647  if (!is_redundant)
1648  new_members = lappend(new_members, em);
1649  }
1650 
1651  list_free(ec->ec_members);
1652  ec->ec_members = new_members;
1653 
1654  list_free(ec->ec_derives);
1655  ec->ec_derives = NULL;
1656 
1657  /* Update EC source expressions */
1658  foreach(lc, ec->ec_sources)
1659  {
1660  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1661  bool is_redundant = false;
1662 
1663  if (!bms_is_member(from, rinfo->required_relids))
1664  {
1665  new_sources = lappend(new_sources, rinfo);
1666  continue;
1667  }
1668 
1669  replace_varno((Node *) rinfo, from, to);
1670 
1671  /*
1672  * After switching the clause to the remaining relation, check it for
1673  * redundancy with existing ones. We don't have to check for
1674  * redundancy with derived clauses, because we've just deleted them.
1675  */
1676  foreach(lc1, new_sources)
1677  {
1678  RestrictInfo *other = lfirst_node(RestrictInfo, lc1);
1679 
1680  if (!equal(rinfo->clause_relids, other->clause_relids))
1681  continue;
1682 
1683  if (equal(rinfo->clause, other->clause))
1684  {
1685  is_redundant = true;
1686  break;
1687  }
1688  }
1689 
1690  if (!is_redundant)
1691  new_sources = lappend(new_sources, rinfo);
1692  }
1693 
1694  list_free(ec->ec_sources);
1695  ec->ec_sources = new_sources;
1696  ec->ec_relids = replace_relid(ec->ec_relids, from, to);
1697 }
1698 
1699 /*
1700  * "Logically" compares two RestrictInfo's ignoring the 'rinfo_serial' field,
1701  * which makes almost every RestrictInfo unique. This type of comparison is
1702  * useful when removing duplicates while moving RestrictInfo's from removed
1703  * relation to remaining relation during self-join elimination.
1704  *
1705  * XXX: In the future, we might remove the 'rinfo_serial' field completely and
1706  * get rid of this function.
1707  */
1708 static bool
1710 {
1711  int saved_rinfo_serial = a->rinfo_serial;
1712  bool result;
1713 
1714  a->rinfo_serial = b->rinfo_serial;
1715  result = equal(a, b);
1716  a->rinfo_serial = saved_rinfo_serial;
1717 
1718  return result;
1719 }
1720 
1721 /*
1722  * Remove a relation after we have proven that it participates only in an
1723  * unneeded unique self join.
1724  *
1725  * Replace any links in planner info structures.
1726  *
1727  * Transfer join and restriction clauses from the removed relation to the
1728  * remaining one. We change the Vars of the clause to point to the
1729  * remaining relation instead of the removed one. The clauses that require
1730  * a subset of joinrelids become restriction clauses of the remaining
1731  * relation, and others remain join clauses. We append them to
1732  * baserestrictinfo and joininfo respectively, trying not to introduce
1733  * duplicates.
1734  *
1735  * We also have to process the 'joinclauses' list here, because it
1736  * contains EC-derived join clauses which must become filter clauses. It
1737  * is not enough to just correct the ECs because the EC-derived
1738  * restrictions are generated before join removal (see
1739  * generate_base_implied_equalities).
1740  */
1741 static void
1743  RelOptInfo *toKeep, RelOptInfo *toRemove,
1744  List *restrictlist)
1745 {
1746  List *joininfos;
1747  ListCell *lc;
1748  int i;
1749  List *jinfo_candidates = NIL;
1750  List *binfo_candidates = NIL;
1751  ReplaceVarnoContext ctx = {.from = toRemove->relid,.to = toKeep->relid};
1752 
1753  Assert(toKeep->relid != -1);
1754 
1755  /*
1756  * Replace the index of the removing table with the keeping one. The
1757  * technique of removing/distributing restrictinfo is used here to attach
1758  * just appeared (for keeping relation) join clauses and avoid adding
1759  * duplicates of those that already exist in the joininfo list.
1760  */
1761  joininfos = list_copy(toRemove->joininfo);
1762  foreach(lc, joininfos)
1763  {
1764  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1765 
1766  remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
1767  replace_varno((Node *) rinfo, toRemove->relid, toKeep->relid);
1768 
1770  jinfo_candidates = lappend(jinfo_candidates, rinfo);
1771  else
1772  binfo_candidates = lappend(binfo_candidates, rinfo);
1773  }
1774 
1775  /*
1776  * Concatenate restrictlist to the list of base restrictions of the
1777  * removing table just to simplify the replacement procedure: all of them
1778  * weren't connected to any keeping relations and need to be added to some
1779  * rels.
1780  */
1781  toRemove->baserestrictinfo = list_concat(toRemove->baserestrictinfo,
1782  restrictlist);
1783  foreach(lc, toRemove->baserestrictinfo)
1784  {
1785  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1786 
1787  replace_varno((Node *) rinfo, toRemove->relid, toKeep->relid);
1788 
1790  jinfo_candidates = lappend(jinfo_candidates, rinfo);
1791  else
1792  binfo_candidates = lappend(binfo_candidates, rinfo);
1793  }
1794 
1795  /*
1796  * Now, add all non-redundant clauses to the keeping relation.
1797  * Contradictory operation. On the one side, we reduce the length of
1798  * restrict lists that can impact planning or executing time.
1799  * Additionally, we improve the accuracy of cardinality estimation. On the
1800  * other side, it is one more place that can make planning time much
1801  * longer in specific cases. It would have been better to avoid calling
1802  * the equal() function here, but it's the only way to detect duplicated
1803  * inequality expressions.
1804  */
1805  foreach(lc, binfo_candidates)
1806  {
1807  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1808  ListCell *olc = NULL;
1809  bool is_redundant = false;
1810 
1811  Assert(!bms_is_member(toRemove->relid, rinfo->required_relids));
1812 
1813  foreach(olc, toKeep->baserestrictinfo)
1814  {
1815  RestrictInfo *src = lfirst_node(RestrictInfo, olc);
1816 
1817  if (!bms_equal(src->clause_relids, rinfo->clause_relids))
1818  /* Const and non-const expressions can't be equal */
1819  continue;
1820 
1821  if (src == rinfo ||
1822  (rinfo->parent_ec != NULL
1823  && src->parent_ec == rinfo->parent_ec)
1824  || restrict_infos_logically_equal(rinfo, src))
1825  {
1826  is_redundant = true;
1827  break;
1828  }
1829  }
1830  if (!is_redundant)
1831  distribute_restrictinfo_to_rels(root, rinfo);
1832  }
1833  foreach(lc, jinfo_candidates)
1834  {
1835  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1836  ListCell *olc = NULL;
1837  bool is_redundant = false;
1838 
1839  Assert(!bms_is_member(toRemove->relid, rinfo->required_relids));
1840 
1841  foreach(olc, toKeep->joininfo)
1842  {
1843  RestrictInfo *src = lfirst_node(RestrictInfo, olc);
1844 
1845  if (!bms_equal(src->clause_relids, rinfo->clause_relids))
1846  /* Can't compare trivially different clauses */
1847  continue;
1848 
1849  if (src == rinfo ||
1850  (rinfo->parent_ec != NULL
1851  && src->parent_ec == rinfo->parent_ec)
1852  || restrict_infos_logically_equal(rinfo, src))
1853  {
1854  is_redundant = true;
1855  break;
1856  }
1857  }
1858  if (!is_redundant)
1859  distribute_restrictinfo_to_rels(root, rinfo);
1860  }
1861  list_free(binfo_candidates);
1862  list_free(jinfo_candidates);
1863 
1864  /*
1865  * Arrange equivalence classes, mentioned removing a table, with the
1866  * keeping one: varno of removing table should be replaced in members and
1867  * sources lists. Also, remove duplicated elements if this replacement
1868  * procedure created them.
1869  */
1870  i = -1;
1871  while ((i = bms_next_member(toRemove->eclass_indexes, i)) >= 0)
1872  {
1874 
1875  update_eclasses(ec, toRemove->relid, toKeep->relid);
1876  toKeep->eclass_indexes = bms_add_member(toKeep->eclass_indexes, i);
1877  }
1878 
1879  /*
1880  * Transfer the targetlist and attr_needed flags.
1881  */
1882 
1883  foreach(lc, toRemove->reltarget->exprs)
1884  {
1885  Node *node = lfirst(lc);
1886 
1887  replace_varno(node, toRemove->relid, toKeep->relid);
1888  if (!list_member(toKeep->reltarget->exprs, node))
1889  toKeep->reltarget->exprs = lappend(toKeep->reltarget->exprs, node);
1890  }
1891 
1892  for (i = toKeep->min_attr; i <= toKeep->max_attr; i++)
1893  {
1894  int attno = i - toKeep->min_attr;
1895 
1896  toRemove->attr_needed[attno] = replace_relid(toRemove->attr_needed[attno],
1897  toRemove->relid, toKeep->relid);
1898  toKeep->attr_needed[attno] = bms_add_members(toKeep->attr_needed[attno],
1899  toRemove->attr_needed[attno]);
1900  }
1901 
1902  /*
1903  * If the removed relation has a row mark, transfer it to the remaining
1904  * one.
1905  *
1906  * If both rels have row marks, just keep the one corresponding to the
1907  * remaining relation, because we verified earlier that they have the same
1908  * strength.
1909  */
1910  if (rmark)
1911  {
1912  if (kmark)
1913  {
1914  Assert(kmark->markType == rmark->markType);
1915 
1916  root->rowMarks = list_delete_ptr(root->rowMarks, rmark);
1917  }
1918  else
1919  {
1920  /* Shouldn't have inheritance children here. */
1921  Assert(rmark->rti == rmark->prti);
1922 
1923  rmark->rti = rmark->prti = toKeep->relid;
1924  }
1925  }
1926 
1927  /* Replace varno in all the query structures */
1930 
1931  /* See remove_self_joins_one_group() */
1932  Assert(root->parse->resultRelation != toRemove->relid);
1933  Assert(root->parse->resultRelation != toKeep->relid);
1934 
1935  /* Replace links in the planner info */
1936  remove_rel_from_query(root, toRemove, toKeep->relid, NULL, NULL);
1937 
1938  /* At last, replace varno in root targetlist and HAVING clause */
1940  toRemove->relid, toKeep->relid);
1942  toRemove->relid, toKeep->relid);
1943  replace_relid(root->all_result_relids, toRemove->relid, toKeep->relid);
1944  replace_relid(root->leaf_result_relids, toRemove->relid, toKeep->relid);
1945 
1946 
1947  /*
1948  * There may be references to the rel in root->fkey_list, but if so,
1949  * match_foreign_keys_to_quals() will get rid of them.
1950  */
1951 
1952  /*
1953  * Finally, remove the rel from the baserel array to prevent it from being
1954  * referenced again. (We can't do this earlier because
1955  * remove_join_clause_from_rels will touch it.)
1956  */
1957  root->simple_rel_array[toRemove->relid] = NULL;
1958 
1959  /* And nuke the RelOptInfo, just in case there's another access path */
1960  pfree(toRemove);
1961 }
1962 
1963 /*
1964  * split_selfjoin_quals
1965  * Processes 'joinquals' by building two lists: one containing the quals
1966  * where the columns/exprs are on either side of the join match, and
1967  * another one containing the remaining quals.
1968  *
1969  * 'joinquals' must only contain quals for a RTE_RELATION being joined to
1970  * itself.
1971  */
1972 static void
1973 split_selfjoin_quals(PlannerInfo *root, List *joinquals, List **selfjoinquals,
1974  List **otherjoinquals, int from, int to)
1975 {
1976  ListCell *lc;
1977  List *sjoinquals = NIL;
1978  List *ojoinquals = NIL;
1979 
1980  foreach(lc, joinquals)
1981  {
1982  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1983  OpExpr *expr;
1984  Node *leftexpr;
1985  Node *rightexpr;
1986 
1987  /* In general, clause looks like F(arg1) = G(arg2) */
1988  if (!rinfo->mergeopfamilies ||
1989  bms_num_members(rinfo->clause_relids) != 2 ||
1990  bms_membership(rinfo->left_relids) != BMS_SINGLETON ||
1991  bms_membership(rinfo->right_relids) != BMS_SINGLETON)
1992  {
1993  ojoinquals = lappend(ojoinquals, rinfo);
1994  continue;
1995  }
1996 
1997  expr = (OpExpr *) rinfo->clause;
1998 
1999  if (!IsA(expr, OpExpr) || list_length(expr->args) != 2)
2000  {
2001  ojoinquals = lappend(ojoinquals, rinfo);
2002  continue;
2003  }
2004 
2005  leftexpr = get_leftop(rinfo->clause);
2006  rightexpr = copyObject(get_rightop(rinfo->clause));
2007 
2008  if (leftexpr && IsA(leftexpr, RelabelType))
2009  leftexpr = (Node *) ((RelabelType *) leftexpr)->arg;
2010  if (rightexpr && IsA(rightexpr, RelabelType))
2011  rightexpr = (Node *) ((RelabelType *) rightexpr)->arg;
2012 
2013  /*
2014  * Quite an expensive operation, narrowing the use case. For example,
2015  * when we have cast of the same var to different (but compatible)
2016  * types.
2017  */
2018  replace_varno(rightexpr, bms_singleton_member(rinfo->right_relids),
2019  bms_singleton_member(rinfo->left_relids));
2020 
2021  if (equal(leftexpr, rightexpr))
2022  sjoinquals = lappend(sjoinquals, rinfo);
2023  else
2024  ojoinquals = lappend(ojoinquals, rinfo);
2025  }
2026 
2027  *selfjoinquals = sjoinquals;
2028  *otherjoinquals = ojoinquals;
2029 }
2030 
2031 /*
2032  * Check for a case when uniqueness is at least partly derived from a
2033  * baserestrictinfo clause. In this case, we have a chance to return only
2034  * one row (if such clauses on both sides of SJ are equal) or nothing (if they
2035  * are different).
2036  */
2037 static bool
2039  Index relid)
2040 {
2041  ListCell *lc;
2042 
2043  foreach(lc, uclauses)
2044  {
2045  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
2046  Expr *clause;
2047  Node *iclause;
2048  Node *c1;
2049  bool matched = false;
2050  ListCell *olc;
2051 
2052  Assert(outer->relid > 0 && relid > 0);
2053 
2054  /* Only filters like f(R.x1,...,R.xN) == expr we should consider. */
2055  Assert(bms_is_empty(rinfo->left_relids) ^
2056  bms_is_empty(rinfo->right_relids));
2057 
2058  clause = (Expr *) copyObject(rinfo->clause);
2059  replace_varno((Node *) clause, relid, outer->relid);
2060 
2061  iclause = bms_is_empty(rinfo->left_relids) ? get_rightop(clause) :
2062  get_leftop(clause);
2063  c1 = bms_is_empty(rinfo->left_relids) ? get_leftop(clause) :
2064  get_rightop(clause);
2065 
2066  /*
2067  * Compare these left and right sides with the corresponding sides of
2068  * the outer's filters. If no one is detected - return immediately.
2069  */
2070  foreach(olc, outer->baserestrictinfo)
2071  {
2072  RestrictInfo *orinfo = lfirst_node(RestrictInfo, olc);
2073  Node *oclause;
2074  Node *c2;
2075 
2076  if (orinfo->mergeopfamilies == NIL)
2077  /* Don't consider clauses which aren't similar to 'F(X)=G(Y)' */
2078  continue;
2079 
2080  Assert(is_opclause(orinfo->clause));
2081 
2082  oclause = bms_is_empty(orinfo->left_relids) ?
2083  get_rightop(orinfo->clause) : get_leftop(orinfo->clause);
2084  c2 = (bms_is_empty(orinfo->left_relids) ?
2085  get_leftop(orinfo->clause) : get_rightop(orinfo->clause));
2086 
2087  if (equal(iclause, oclause) && equal(c1, c2))
2088  {
2089  matched = true;
2090  break;
2091  }
2092  }
2093 
2094  if (!matched)
2095  return false;
2096  }
2097 
2098  return true;
2099 }
2100 
2101 /*
2102  * Find and remove unique self joins in a group of base relations that have
2103  * the same Oid.
2104  *
2105  * Returns a set of relids that were removed.
2106  */
2107 static Relids
2109 {
2110  Relids result = NULL;
2111  int k; /* Index of kept relation */
2112  int r = -1; /* Index of removed relation */
2113 
2114  while ((r = bms_next_member(relids, r)) > 0)
2115  {
2116  RelOptInfo *inner = root->simple_rel_array[r];
2117 
2118  /*
2119  * We don't accept result relation as either source or target relation
2120  * of SJE, because result relation has different behavior in
2121  * EvalPlanQual() and RETURNING clause.
2122  */
2123  if (root->parse->resultRelation == r)
2124  continue;
2125 
2126  k = r;
2127 
2128  while ((k = bms_next_member(relids, k)) > 0)
2129  {
2130  Relids joinrelids = NULL;
2131  RelOptInfo *outer = root->simple_rel_array[k];
2132  List *restrictlist;
2133  List *selfjoinquals;
2134  List *otherjoinquals;
2135  ListCell *lc;
2136  bool jinfo_check = true;
2137  PlanRowMark *omark = NULL;
2138  PlanRowMark *imark = NULL;
2139  List *uclauses = NIL;
2140 
2141  if (root->parse->resultRelation == k)
2142  continue;
2143 
2144  /* A sanity check: the relations have the same Oid. */
2145  Assert(root->simple_rte_array[k]->relid ==
2146  root->simple_rte_array[r]->relid);
2147 
2148  /*
2149  * It is impossible to eliminate join of two relations if they
2150  * belong to different rules of order. Otherwise planner can't be
2151  * able to find any variants of correct query plan.
2152  */
2153  foreach(lc, root->join_info_list)
2154  {
2155  SpecialJoinInfo *info = (SpecialJoinInfo *) lfirst(lc);
2156 
2157  if ((bms_is_member(k, info->syn_lefthand) ^
2158  bms_is_member(r, info->syn_lefthand)) ||
2159  (bms_is_member(k, info->syn_righthand) ^
2160  bms_is_member(r, info->syn_righthand)))
2161  {
2162  jinfo_check = false;
2163  break;
2164  }
2165  }
2166  if (!jinfo_check)
2167  continue;
2168 
2169  /*
2170  * Check Row Marks equivalence. We can't remove the join if the
2171  * relations have row marks of different strength (e.g. one is
2172  * locked FOR UPDATE and another just has ROW_MARK_REFERENCE for
2173  * EvalPlanQual rechecking).
2174  */
2175  foreach(lc, root->rowMarks)
2176  {
2177  PlanRowMark *rowMark = (PlanRowMark *) lfirst(lc);
2178 
2179  if (rowMark->rti == k)
2180  {
2181  Assert(imark == NULL);
2182  imark = rowMark;
2183  }
2184  else if (rowMark->rti == r)
2185  {
2186  Assert(omark == NULL);
2187  omark = rowMark;
2188  }
2189 
2190  if (omark && imark)
2191  break;
2192  }
2193  if (omark && imark && omark->markType != imark->markType)
2194  continue;
2195 
2196  /*
2197  * We only deal with base rels here, so their relids bitset
2198  * contains only one member -- their relid.
2199  */
2200  joinrelids = bms_add_member(joinrelids, r);
2201  joinrelids = bms_add_member(joinrelids, k);
2202 
2203  /*
2204  * PHVs should not impose any constraints on removing self joins.
2205  */
2206 
2207  /*
2208  * At this stage, joininfo lists of inner and outer can contain
2209  * only clauses, required for a superior outer join that can't
2210  * influence this optimization. So, we can avoid to call the
2211  * build_joinrel_restrictlist() routine.
2212  */
2213  restrictlist = generate_join_implied_equalities(root, joinrelids,
2214  inner->relids,
2215  outer, NULL);
2216 
2217  /*
2218  * Process restrictlist to separate the self join quals out of the
2219  * other quals. e.g x = x goes to selfjoinquals and a = b to
2220  * otherjoinquals.
2221  */
2222  split_selfjoin_quals(root, restrictlist, &selfjoinquals,
2223  &otherjoinquals, inner->relid, outer->relid);
2224 
2225  /*
2226  * To enable SJE for the only degenerate case without any self
2227  * join clauses at all, add baserestrictinfo to this list. The
2228  * degenerate case works only if both sides have the same clause.
2229  * So doesn't matter which side to add.
2230  */
2231  selfjoinquals = list_concat(selfjoinquals, outer->baserestrictinfo);
2232 
2233  /*
2234  * Determine if the inner table can duplicate outer rows. We must
2235  * bypass the unique rel cache here since we're possibly using a
2236  * subset of join quals. We can use 'force_cache' == true when all
2237  * join quals are self-join quals. Otherwise, we could end up
2238  * putting false negatives in the cache.
2239  */
2240  if (!innerrel_is_unique_ext(root, joinrelids, inner->relids,
2241  outer, JOIN_INNER, selfjoinquals,
2242  list_length(otherjoinquals) == 0,
2243  &uclauses))
2244  continue;
2245 
2246  /*
2247  * We have proven that for both relations, the same unique index
2248  * guarantees that there is at most one row where columns equal
2249  * given values. These values must be the same for both relations,
2250  * or else we won't match the same row on each side of the join.
2251  */
2252  if (!match_unique_clauses(root, inner, uclauses, outer->relid))
2253  continue;
2254 
2255  /*
2256  * We can remove either relation, so remove the inner one in order
2257  * to simplify this loop.
2258  */
2259  remove_self_join_rel(root, omark, imark, outer, inner, restrictlist);
2260 
2261  result = bms_add_member(result, r);
2262 
2263  /* We have removed the outer relation, try the next one. */
2264  break;
2265  }
2266  }
2267 
2268  return result;
2269 }
2270 
2271 /*
2272  * Gather indexes of base relations from the joinlist and try to eliminate self
2273  * joins.
2274  */
2275 static Relids
2277 {
2278  ListCell *jl;
2279  Relids relids = NULL;
2280  SelfJoinCandidate *candidates = NULL;
2281  int i;
2282  int j;
2283  int numRels;
2284 
2285  /* Collect indexes of base relations of the join tree */
2286  foreach(jl, joinlist)
2287  {
2288  Node *jlnode = (Node *) lfirst(jl);
2289 
2290  if (IsA(jlnode, RangeTblRef))
2291  {
2292  RangeTblRef *ref = (RangeTblRef *) jlnode;
2293  RangeTblEntry *rte = root->simple_rte_array[ref->rtindex];
2294 
2295  /*
2296  * We only care about base relations from which we select
2297  * something.
2298  */
2299  if (rte->rtekind == RTE_RELATION &&
2300  rte->relkind == RELKIND_RELATION &&
2301  root->simple_rel_array[ref->rtindex] != NULL)
2302  {
2303  Assert(!bms_is_member(ref->rtindex, relids));
2304  relids = bms_add_member(relids, ref->rtindex);
2305  }
2306  }
2307  else if (IsA(jlnode, List))
2308  /* Recursively go inside the sub-joinlist */
2309  toRemove = remove_self_joins_recurse(root, (List *) jlnode,
2310  toRemove);
2311  else
2312  elog(ERROR, "unrecognized joinlist node type: %d",
2313  (int) nodeTag(jlnode));
2314  }
2315 
2316  numRels = bms_num_members(relids);
2317 
2318  /* Need at least two relations for the join */
2319  if (numRels < 2)
2320  return toRemove;
2321 
2322  /*
2323  * In order to find relations with the same oid we first build an array of
2324  * candidates and then sort it by oid.
2325  */
2326  candidates = (SelfJoinCandidate *) palloc(sizeof(SelfJoinCandidate) *
2327  numRels);
2328  i = -1;
2329  j = 0;
2330  while ((i = bms_next_member(relids, i)) >= 0)
2331  {
2332  candidates[j].relid = i;
2333  candidates[j].reloid = root->simple_rte_array[i]->relid;
2334  j++;
2335  }
2336 
2337  qsort(candidates, numRels, sizeof(SelfJoinCandidate),
2339 
2340  /*
2341  * Iteratively form a group of relation indexes with the same oid and
2342  * launch the routine that detects self-joins in this group and removes
2343  * excessive range table entries.
2344  *
2345  * At the end of the iteration, exclude the group from the overall relids
2346  * list. So each next iteration of the cycle will involve less and less
2347  * value of relids.
2348  */
2349  i = 0;
2350  for (j = 1; j < numRels + 1; j++)
2351  {
2352  if (j == numRels || candidates[j].reloid != candidates[i].reloid)
2353  {
2354  if (j - i >= 2)
2355  {
2356  /* Create a group of relation indexes with the same oid */
2357  Relids group = NULL;
2358  Relids removed;
2359 
2360  while (i < j)
2361  {
2362  group = bms_add_member(group, candidates[i].relid);
2363  i++;
2364  }
2365 
2366  relids = bms_del_members(relids, group);
2367 
2368  /*
2369  * Try to remove self-joins from a group of identical entries.
2370  * Make the next attempt iteratively - if something is deleted
2371  * from a group, changes in clauses and equivalence classes
2372  * can give us a chance to find more candidates.
2373  */
2374  do
2375  {
2376  Assert(!bms_overlap(group, toRemove));
2377  removed = remove_self_joins_one_group(root, group);
2378  toRemove = bms_add_members(toRemove, removed);
2379  group = bms_del_members(group, removed);
2380  } while (!bms_is_empty(removed) &&
2381  bms_membership(group) == BMS_MULTIPLE);
2382  bms_free(removed);
2383  bms_free(group);
2384  }
2385  else
2386  {
2387  /* Single relation, just remove it from the set */
2388  relids = bms_del_member(relids, candidates[i].relid);
2389  i = j;
2390  }
2391  }
2392  }
2393 
2394  Assert(bms_is_empty(relids));
2395 
2396  return toRemove;
2397 }
2398 
2399 /*
2400  * Compare self-join candidates by their oids.
2401  */
2402 static int
2403 self_join_candidates_cmp(const void *a, const void *b)
2404 {
2405  const SelfJoinCandidate *ca = (const SelfJoinCandidate *) a;
2406  const SelfJoinCandidate *cb = (const SelfJoinCandidate *) b;
2407 
2408  if (ca->reloid != cb->reloid)
2409  return (ca->reloid < cb->reloid ? -1 : 1);
2410  else
2411  return 0;
2412 }
2413 
2414 /*
2415  * Find and remove useless self joins.
2416  *
2417  * Search for joins where a relation is joined to itself. If the join clause
2418  * for each tuple from one side of the join is proven to match the same
2419  * physical row (or nothing) on the other side, that self-join can be
2420  * eliminated from the query. Suitable join clauses are assumed to be in the
2421  * form of X = X, and can be replaced with NOT NULL clauses.
2422  *
2423  * For the sake of simplicity, we don't apply this optimization to special
2424  * joins. Here is a list of what we could do in some particular cases:
2425  * 'a a1 semi join a a2': is reduced to inner by reduce_unique_semijoins,
2426  * and then removed normally.
2427  * 'a a1 anti join a a2': could simplify to a scan with 'outer quals AND
2428  * (IS NULL on join columns OR NOT inner quals)'.
2429  * 'a a1 left join a a2': could simplify to a scan like inner but without
2430  * NOT NULL conditions on join columns.
2431  * 'a a1 left join (a a2 join b)': can't simplify this, because join to b
2432  * can both remove rows and introduce duplicates.
2433  *
2434  * To search for removable joins, we order all the relations on their Oid,
2435  * go over each set with the same Oid, and consider each pair of relations
2436  * in this set.
2437  *
2438  * To remove the join, we mark one of the participating relations as dead
2439  * and rewrite all references to it to point to the remaining relation.
2440  * This includes modifying RestrictInfos, EquivalenceClasses, and
2441  * EquivalenceMembers. We also have to modify the row marks. The join clauses
2442  * of the removed relation become either restriction or join clauses, based on
2443  * whether they reference any relations not participating in the removed join.
2444  *
2445  * 'targetlist' is the top-level targetlist of the query. If it has any
2446  * references to the removed relations, we update them to point to the
2447  * remaining ones.
2448  */
2449 List *
2451 {
2452  Relids toRemove = NULL;
2453  int relid = -1;
2454 
2455  if (!enable_self_join_removal || joinlist == NIL ||
2456  (list_length(joinlist) == 1 && !IsA(linitial(joinlist), List)))
2457  return joinlist;
2458 
2459  /*
2460  * Merge pairs of relations participated in self-join. Remove unnecessary
2461  * range table entries.
2462  */
2463  toRemove = remove_self_joins_recurse(root, joinlist, toRemove);
2464 
2465  if (unlikely(toRemove != NULL))
2466  {
2467  int nremoved = 0;
2468 
2469  /* At the end, remove orphaned relation links */
2470  while ((relid = bms_next_member(toRemove, relid)) >= 0)
2471  joinlist = remove_rel_from_joinlist(joinlist, relid, &nremoved);
2472  }
2473 
2474  return joinlist;
2475 }
List * remove_useless_joins(PlannerInfo *root, List *joinlist)
Definition: analyzejoins.c:94
static int self_join_candidates_cmp(const void *a, const void *b)
static bool match_unique_clauses(PlannerInfo *root, RelOptInfo *outer, List *uclauses, Index relid)
static void split_selfjoin_quals(PlannerInfo *root, List *joinquals, List **selfjoinquals, List **otherjoinquals, int from, int to)
bool enable_self_join_removal
Definition: analyzejoins.c:55
static bool clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
Definition: analyzejoins.c:158
static void remove_rel_from_query(PlannerInfo *root, RelOptInfo *rel, int subst, SpecialJoinInfo *sjinfo, Relids joinrelids)
Definition: analyzejoins.c:360
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:749
static bool replace_varno_walker(Node *node, ReplaceVarnoContext *ctx)
static void remove_leftjoinrel_from_query(PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
Definition: analyzejoins.c:522
static Bitmapset * replace_relid(Relids relids, int oldId, int newId)
bool query_is_distinct_for(Query *query, List *colnos, List *opids)
static Relids remove_self_joins_one_group(PlannerInfo *root, Relids relids)
static Oid distinct_col_search(int colno, List *colnos, List *opids)
static bool is_innerrel_unique_for(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, List **extra_clauses)
static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list, List **extra_clauses)
Definition: analyzejoins.c:938
bool innerrel_is_unique_ext(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache, List **extra_clauses)
bool query_supports_distinctness(Query *query)
List * remove_useless_self_joins(PlannerInfo *root, List *joinlist)
static void update_eclasses(EquivalenceClass *ec, int from, int to)
static bool restrict_infos_logically_equal(RestrictInfo *a, RestrictInfo *b)
static Relids remove_self_joins_recurse(PlannerInfo *root, List *joinlist, Relids toRemove)
static void replace_varno(Node *node, int from, int to)
static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
Definition: analyzejoins.c:190
void reduce_unique_semijoins(PlannerInfo *root)
Definition: analyzejoins.c:803
static void remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
Definition: analyzejoins.c:638
static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
Definition: analyzejoins.c:879
static void remove_self_join_rel(PlannerInfo *root, PlanRowMark *kmark, PlanRowMark *rmark, RelOptInfo *toKeep, RelOptInfo *toRemove, List *restrictlist)
static void remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
Definition: analyzejoins.c:695
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:155
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1319
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:425
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:685
void bms_free(Bitmapset *a)
Definition: bitmapset.c:252
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:764
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:523
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:828
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:264
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:930
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1174
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:881
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:794
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:595
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:135
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:728
#define bms_is_empty(a)
Definition: bitmapset.h:105
@ BMS_SINGLETON
Definition: bitmapset.h:72
@ BMS_MULTIPLE
Definition: bitmapset.h:73
#define unlikely(x)
Definition: c.h:300
unsigned int Index
Definition: c.h:603
#define OidIsValid(objectId)
Definition: c.h:764
#define ERROR
Definition: elog.h:39
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:223
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
Definition: equivclass.c:1392
bool relation_has_unique_index_ext(PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist, List **extra_clauses)
Definition: indxpath.c:3509
void distribute_restrictinfo_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: initsplan.c:2818
int b
Definition: isn.c:70
int a
Definition: isn.c:69
int j
Definition: isn.c:74
int i
Definition: isn.c:73
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
void remove_join_clause_from_rels(PlannerInfo *root, RestrictInfo *restrictinfo, Relids join_relids)
Definition: joininfo.c:153
Assert(fmt[strlen(fmt) - 1] !='\n')
List * list_delete_ptr(List *list, void *datum)
Definition: list.c:872
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
void list_free(List *list)
Definition: list.c:1546
List * list_concat(List *list1, const List *list2)
Definition: list.c:561
bool list_member(const List *list, const void *datum)
Definition: list.c:661
bool equality_ops_are_compatible(Oid opno1, Oid opno2)
Definition: lsyscache.c:697
void pfree(void *pointer)
Definition: mcxt.c:1431
void * palloc(Size size)
Definition: mcxt.c:1201
static bool is_andclause(const void *clause)
Definition: nodeFuncs.h:105
static bool is_orclause(const void *clause)
Definition: nodeFuncs.h:114
#define query_tree_walker(q, w, c, f)
Definition: nodeFuncs.h:156
static bool is_opclause(const void *clause)
Definition: nodeFuncs.h:74
#define QTW_EXAMINE_SORTGROUP
Definition: nodeFuncs.h:30
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:93
#define expression_tree_walker(n, w, c)
Definition: nodeFuncs.h:151
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:81
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
#define copyObject(obj)
Definition: nodes.h:223
#define nodeTag(nodeptr)
Definition: nodes.h:133
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:327
#define makeNode(_type_)
Definition: nodes.h:155
#define castNode(_type_, nodeptr)
Definition: nodes.h:176
JoinType
Definition: nodes.h:278
@ JOIN_SEMI
Definition: nodes.h:297
@ JOIN_INNER
Definition: nodes.h:283
@ JOIN_LEFT
Definition: nodes.h:284
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
@ GROUPING_SET_EMPTY
Definition: parsenodes.h:1445
@ SETOP_NONE
Definition: parsenodes.h:1948
@ RTE_SUBQUERY
Definition: parsenodes.h:1007
@ RTE_RELATION
Definition: parsenodes.h:1006
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2698
Bitmapset * Relids
Definition: pathnodes.h:30
@ RELOPT_BASEREL
Definition: pathnodes.h:812
void * arg
#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 void * list_nth(const List *list, int n)
Definition: pg_list.h:299
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:343
#define lfirst_oid(lc)
Definition: pg_list.h:174
#define qsort(a, b, c, d)
Definition: port.h:449
#define InvalidOid
Definition: postgres_ext.h:36
unsigned int Oid
Definition: postgres_ext.h:31
@ IS_NOT_NULL
Definition: primnodes.h:1694
RelOptInfo * find_base_rel(PlannerInfo *root, int relid)
Definition: relnode.c:407
bool restriction_is_or_clause(RestrictInfo *restrictinfo)
Definition: restrictinfo.c:416
JoinDomain * em_jdomain
Definition: pathnodes.h:1426
Relids jd_relids
Definition: pathnodes.h:1308
Definition: pg_list.h:54
Definition: nodes.h:129
NullTestType nulltesttype
Definition: primnodes.h:1701
int location
Definition: primnodes.h:1704
Expr * arg
Definition: primnodes.h:1700
List * args
Definition: primnodes.h:771
List * exprs
Definition: pathnodes.h:1513
Relids ph_lateral
Definition: pathnodes.h:3065
Relids ph_needed
Definition: pathnodes.h:3068
Relids ph_eval_at
Definition: pathnodes.h:3062
PlaceHolderVar * ph_var
Definition: pathnodes.h:3059
Relids phnullingrels
Definition: pathnodes.h:2768
Index prti
Definition: plannodes.h:1381
RowMarkType markType
Definition: plannodes.h:1383
List * processed_tlist
Definition: pathnodes.h:453
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
bool hasLateralRTEs
Definition: pathnodes.h:491
List * placeholder_list
Definition: pathnodes.h:371
List * eq_classes
Definition: pathnodes.h:311
List * processed_groupClause
Definition: pathnodes.h:430
Query * parse
Definition: pathnodes.h:199
List * rowMarks
Definition: pathnodes.h:368
List * join_info_list
Definition: pathnodes.h:337
Relids all_baserels
Definition: pathnodes.h:252
Relids all_result_relids
Definition: pathnodes.h:351
Relids leaf_result_relids
Definition: pathnodes.h:353
Node * setOperations
Definition: parsenodes.h:209
List * groupClause
Definition: parsenodes.h:190
Node * havingQual
Definition: parsenodes.h:195
List * targetList
Definition: parsenodes.h:181
List * groupingSets
Definition: parsenodes.h:193
List * distinctClause
Definition: parsenodes.h:199
TableFunc * tablefunc
Definition: parsenodes.h:1146
struct TableSampleClause * tablesample
Definition: parsenodes.h:1067
Query * subquery
Definition: parsenodes.h:1073
List * values_lists
Definition: parsenodes.h:1151
List * functions
Definition: parsenodes.h:1140
RTEKind rtekind
Definition: parsenodes.h:1025
List * baserestrictinfo
Definition: pathnodes.h:966
List * joininfo
Definition: pathnodes.h:972
Relids relids
Definition: pathnodes.h:856
struct PathTarget * reltarget
Definition: pathnodes.h:878
Index relid
Definition: pathnodes.h:903
List * lateral_vars
Definition: pathnodes.h:921
List * unique_for_rels
Definition: pathnodes.h:958
RelOptKind reloptkind
Definition: pathnodes.h:850
List * indexlist
Definition: pathnodes.h:925
List * non_unique_for_rels
Definition: pathnodes.h:960
Bitmapset * eclass_indexes
Definition: pathnodes.h:933
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:2572
Relids outer_relids
Definition: pathnodes.h:2578
Relids incompatible_relids
Definition: pathnodes.h:2575
Expr * clause
Definition: pathnodes.h:2541
SetOperation op
Definition: parsenodes.h:2026
Relids commute_above_r
Definition: pathnodes.h:2875
Relids syn_lefthand
Definition: pathnodes.h:2870
Relids min_righthand
Definition: pathnodes.h:2869
List * semi_rhs_exprs
Definition: pathnodes.h:2883
Relids commute_above_l
Definition: pathnodes.h:2874
JoinType jointype
Definition: pathnodes.h:2872
Relids commute_below_l
Definition: pathnodes.h:2876
Relids min_lefthand
Definition: pathnodes.h:2868
Relids syn_righthand
Definition: pathnodes.h:2871
Relids commute_below_r
Definition: pathnodes.h:2877
AttrNumber resno
Definition: primnodes.h:1924
Relids outerrelids
Definition: pathnodes.h:3423
List * extra_clauses
Definition: pathnodes.h:3437
Definition: primnodes.h:234
AttrNumber varattno
Definition: primnodes.h:246
int varno
Definition: primnodes.h:241
Index varlevelsup
Definition: primnodes.h:266
TargetEntry * get_sortgroupclause_tle(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:367
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:108