PostgreSQL Source Code  git master
joininfo.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * joininfo.c
4  * joininfo list manipulation routines
5  *
6  * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  *
10  * IDENTIFICATION
11  * src/backend/optimizer/util/joininfo.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 #include "postgres.h"
16 
17 #include "optimizer/joininfo.h"
18 #include "optimizer/pathnode.h"
19 #include "optimizer/paths.h"
20 
21 
22 /*
23  * have_relevant_joinclause
24  * Detect whether there is a joinclause that involves
25  * the two given relations.
26  *
27  * Note: the joinclause does not have to be evaluable with only these two
28  * relations. This is intentional. For example consider
29  * SELECT * FROM a, b, c WHERE a.x = (b.y + c.z)
30  * If a is much larger than the other tables, it may be worthwhile to
31  * cross-join b and c and then use an inner indexscan on a.x. Therefore
32  * we should consider this joinclause as reason to join b to c, even though
33  * it can't be applied at that join step.
34  */
35 bool
37  RelOptInfo *rel1, RelOptInfo *rel2)
38 {
39  bool result = false;
40  List *joininfo;
41  Relids other_relids;
42  ListCell *l;
43 
44  /*
45  * We could scan either relation's joininfo list; may as well use the
46  * shorter one.
47  */
48  if (list_length(rel1->joininfo) <= list_length(rel2->joininfo))
49  {
50  joininfo = rel1->joininfo;
51  other_relids = rel2->relids;
52  }
53  else
54  {
55  joininfo = rel2->joininfo;
56  other_relids = rel1->relids;
57  }
58 
59  foreach(l, joininfo)
60  {
61  RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
62 
63  if (bms_overlap(other_relids, rinfo->required_relids))
64  {
65  result = true;
66  break;
67  }
68  }
69 
70  /*
71  * We also need to check the EquivalenceClass data structure, which might
72  * contain relationships not emitted into the joininfo lists.
73  */
74  if (!result && rel1->has_eclass_joins && rel2->has_eclass_joins)
75  result = have_relevant_eclass_joinclause(root, rel1, rel2);
76 
77  return result;
78 }
79 
80 
81 /*
82  * add_join_clause_to_rels
83  * Add 'restrictinfo' to the joininfo list of each relation it requires.
84  *
85  * Note that the same copy of the restrictinfo node is linked to by all the
86  * lists it is in. This allows us to exploit caching of information about
87  * the restriction clause (but we must be careful that the information does
88  * not depend on context).
89  *
90  * 'restrictinfo' describes the join clause
91  * 'join_relids' is the set of relations participating in the join clause
92  * (some of these could be outer joins)
93  */
94 void
96  RestrictInfo *restrictinfo,
97  Relids join_relids)
98 {
99  int cur_relid;
100 
101  cur_relid = -1;
102  while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0)
103  {
104  RelOptInfo *rel = find_base_rel_ignore_join(root, cur_relid);
105 
106  /* We only need to add the clause to baserels */
107  if (rel == NULL)
108  continue;
109  rel->joininfo = lappend(rel->joininfo, restrictinfo);
110  }
111 }
112 
113 /*
114  * remove_join_clause_from_rels
115  * Delete 'restrictinfo' from all the joininfo lists it is in
116  *
117  * This reverses the effect of add_join_clause_to_rels. It's used when we
118  * discover that a relation need not be joined at all.
119  *
120  * 'restrictinfo' describes the join clause
121  * 'join_relids' is the set of relations participating in the join clause
122  * (some of these could be outer joins)
123  */
124 void
126  RestrictInfo *restrictinfo,
127  Relids join_relids)
128 {
129  int cur_relid;
130 
131  cur_relid = -1;
132  while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0)
133  {
134  RelOptInfo *rel = find_base_rel_ignore_join(root, cur_relid);
135 
136  /* We would only have added the clause to baserels */
137  if (rel == NULL)
138  continue;
139 
140  /*
141  * Remove the restrictinfo from the list. Pointer comparison is
142  * sufficient.
143  */
144  Assert(list_member_ptr(rel->joininfo, restrictinfo));
145  rel->joininfo = list_delete_ptr(rel->joininfo, restrictinfo);
146  }
147 }
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1106
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:527
bool have_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: equivclass.c:3016
void remove_join_clause_from_rels(PlannerInfo *root, RestrictInfo *restrictinfo, Relids join_relids)
Definition: joininfo.c:125
void add_join_clause_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo, Relids join_relids)
Definition: joininfo.c:95
bool have_relevant_joinclause(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joininfo.c:36
Assert(fmt[strlen(fmt) - 1] !='\n')
List * list_delete_ptr(List *list, void *datum)
Definition: list.c:871
List * lappend(List *list, void *datum)
Definition: list.c:338
bool list_member_ptr(const List *list, const void *datum)
Definition: list.c:681
#define lfirst(lc)
Definition: pg_list.h:172
static int list_length(const List *l)
Definition: pg_list.h:152
RelOptInfo * find_base_rel_ignore_join(PlannerInfo *root, int relid)
Definition: relnode.c:433
Definition: pg_list.h:54
List * joininfo
Definition: pathnodes.h:970
Relids relids
Definition: pathnodes.h:856
bool has_eclass_joins
Definition: pathnodes.h:972
Relids required_relids
Definition: pathnodes.h:2560