PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, 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 list of relations participating in the join clause
92  * (there must be more than one)
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(root, cur_relid);
105 
106  rel->joininfo = lappend(rel->joininfo, restrictinfo);
107  }
108 }
109 
110 /*
111  * remove_join_clause_from_rels
112  * Delete 'restrictinfo' from all the joininfo lists it is in
113  *
114  * This reverses the effect of add_join_clause_to_rels. It's used when we
115  * discover that a relation need not be joined at all.
116  *
117  * 'restrictinfo' describes the join clause
118  * 'join_relids' is the list of relations participating in the join clause
119  * (there must be more than one)
120  */
121 void
123  RestrictInfo *restrictinfo,
124  Relids join_relids)
125 {
126  int cur_relid;
127 
128  cur_relid = -1;
129  while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0)
130  {
131  RelOptInfo *rel = find_base_rel(root, cur_relid);
132 
133  /*
134  * Remove the restrictinfo from the list. Pointer comparison is
135  * sufficient.
136  */
137  Assert(list_member_ptr(rel->joininfo, restrictinfo));
138  rel->joininfo = list_delete_ptr(rel->joininfo, restrictinfo);
139  }
140 }
bool has_eclass_joins
Definition: relation.h:637
void remove_join_clause_from_rels(PlannerInfo *root, RestrictInfo *restrictinfo, Relids join_relids)
Definition: joininfo.c:122
Relids required_relids
Definition: relation.h:1819
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:937
List * list_delete_ptr(List *list, void *datum)
Definition: list.c:590
List * joininfo
Definition: relation.h:635
Relids relids
Definition: relation.h:571
List * lappend(List *list, void *datum)
Definition: list.c:128
bool have_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: equivclass.c:2305
void add_join_clause_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo, Relids join_relids)
Definition: joininfo.c:95
bool list_member_ptr(const List *list, const void *datum)
Definition: list.c:465
#define Assert(condition)
Definition: c.h:664
#define lfirst(lc)
Definition: pg_list.h:106
static int list_length(const List *l)
Definition: pg_list.h:89
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
bool have_relevant_joinclause(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joininfo.c:36
RelOptInfo * find_base_rel(PlannerInfo *root, int relid)
Definition: relnode.c:271
Definition: pg_list.h:45