1 /*-------------------------------------------------------------------------
2 *
3 * joininfo.c
4 * joininfo list manipulation routines
5 *
6 * Portions Copyright (c) 1996-2016, 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
have_relevant_joinclause(PlannerInfo * root,RelOptInfo * rel1,RelOptInfo * rel2)36 have_relevant_joinclause(PlannerInfo *root,
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
add_join_clause_to_rels(PlannerInfo * root,RestrictInfo * restrictinfo,Relids join_relids)95 add_join_clause_to_rels(PlannerInfo *root,
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
remove_join_clause_from_rels(PlannerInfo * root,RestrictInfo * restrictinfo,Relids join_relids)122 remove_join_clause_from_rels(PlannerInfo *root,
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 }
141