1 /*-------------------------------------------------------------------------
4 * Routines copied from PostgreSQL core distribution.
6 * src/backend/optimizer/path/joinrels.c
9 * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
10 * Portions Copyright (c) 1994, Regents of the University of California
12 *-------------------------------------------------------------------------
17 * Find or create a join RelOptInfo that represents the join of
18 * the two given rels, and add to it path information for paths
19 * created with the two rels as outer and inner rel.
20 * (The join rel may already contain paths generated from other
21 * pairs of rels that add up to the same set of base rels.)
23 * NB: will return NULL if attempted join is not valid. This can happen
24 * when working with outer joins, or with IN or EXISTS clauses that have been
28 make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
31 SpecialJoinInfo *sjinfo;
33 SpecialJoinInfo sjinfo_data;
37 /* We should never try to join two overlapping sets of rels. */
38 Assert(!bms_overlap(rel1->relids, rel2->relids));
40 /* Construct Relids set that identifies the joinrel. */
41 joinrelids = bms_union(rel1->relids, rel2->relids);
43 /* Check validity and determine join type. */
44 if (!join_is_legal(root, rel1, rel2, joinrelids,
47 /* invalid join path */
52 /* Swap rels if needed to match the join info. */
55 RelOptInfo *trel = rel1;
62 * If it's a plain inner join, then we won't have found anything in
63 * join_info_list. Make up a SpecialJoinInfo so that selectivity
64 * estimation functions will know what's being joined.
68 sjinfo = &sjinfo_data;
69 sjinfo->type = T_SpecialJoinInfo;
70 sjinfo->min_lefthand = rel1->relids;
71 sjinfo->min_righthand = rel2->relids;
72 sjinfo->syn_lefthand = rel1->relids;
73 sjinfo->syn_righthand = rel2->relids;
74 sjinfo->jointype = JOIN_INNER;
75 /* we don't bother trying to make the remaining fields valid */
76 sjinfo->lhs_strict = false;
77 sjinfo->delay_upper_joins = false;
78 sjinfo->join_quals = NIL;
82 * Find or build the join RelOptInfo, and compute the restrictlist that
83 * goes with this particular joining.
85 joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
89 * If we've already proven this join is empty, we needn't consider any
92 if (is_dummy_rel(joinrel))
99 * Consider paths using each rel as both outer and inner. Depending on
100 * the join type, a provably empty outer or inner rel might mean the join
101 * is provably empty too; in which case throw away any previously computed
102 * paths and mark the join as dummy. (We do it this way since it's
103 * conceivable that dummy-ness of a multi-element join might only be
104 * noticeable for certain construction paths.)
106 * Also, a provably constant-false join restriction typically means that
107 * we can skip evaluating one or both sides of the join. We do this by
108 * marking the appropriate rel as dummy. For outer joins, a
109 * constant-false restriction that is pushed down still means the whole
110 * join is dummy, while a non-pushed-down one means that no inner rows
111 * will join so we can treat the inner rel as dummy.
113 * We need only consider the jointypes that appear in join_info_list, plus
116 switch (sjinfo->jointype)
119 if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
120 restriction_is_constant_false(restrictlist, false))
122 mark_dummy_rel(joinrel);
125 add_paths_to_joinrel(root, joinrel, rel1, rel2,
128 add_paths_to_joinrel(root, joinrel, rel2, rel1,
133 if (is_dummy_rel(rel1) ||
134 restriction_is_constant_false(restrictlist, true))
136 mark_dummy_rel(joinrel);
139 if (restriction_is_constant_false(restrictlist, false) &&
140 bms_is_subset(rel2->relids, sjinfo->syn_righthand))
141 mark_dummy_rel(rel2);
142 add_paths_to_joinrel(root, joinrel, rel1, rel2,
145 add_paths_to_joinrel(root, joinrel, rel2, rel1,
150 if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) ||
151 restriction_is_constant_false(restrictlist, true))
153 mark_dummy_rel(joinrel);
156 add_paths_to_joinrel(root, joinrel, rel1, rel2,
159 add_paths_to_joinrel(root, joinrel, rel2, rel1,
164 * If there are join quals that aren't mergeable or hashable, we
165 * may not be able to build any valid plan. Complain here so that
166 * we can give a somewhat-useful error message. (Since we have no
167 * flexibility of planning for a full join, there's no chance of
168 * succeeding later with another pair of input rels.)
170 if (joinrel->pathlist == NIL)
172 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
173 errmsg("FULL JOIN is only supported with merge-joinable or hash-joinable join conditions")));
178 * We might have a normal semijoin, or a case where we don't have
179 * enough rels to do the semijoin but can unique-ify the RHS and
180 * then do an innerjoin (see comments in join_is_legal). In the
181 * latter case we can't apply JOIN_SEMI joining.
183 if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
184 bms_is_subset(sjinfo->min_righthand, rel2->relids))
186 if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
187 restriction_is_constant_false(restrictlist, false))
189 mark_dummy_rel(joinrel);
192 add_paths_to_joinrel(root, joinrel, rel1, rel2,
198 * If we know how to unique-ify the RHS and one input rel is
199 * exactly the RHS (not a superset) we can consider unique-ifying
200 * it and then doing a regular join. (The create_unique_path
201 * check here is probably redundant with what join_is_legal did,
202 * but if so the check is cheap because it's cached. So test
203 * anyway to be sure.)
205 if (bms_equal(sjinfo->syn_righthand, rel2->relids) &&
206 create_unique_path(root, rel2, rel2->cheapest_total_path,
209 if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
210 restriction_is_constant_false(restrictlist, false))
212 mark_dummy_rel(joinrel);
215 add_paths_to_joinrel(root, joinrel, rel1, rel2,
216 JOIN_UNIQUE_INNER, sjinfo,
218 add_paths_to_joinrel(root, joinrel, rel2, rel1,
219 JOIN_UNIQUE_OUTER, sjinfo,
224 if (is_dummy_rel(rel1) ||
225 restriction_is_constant_false(restrictlist, true))
227 mark_dummy_rel(joinrel);
230 if (restriction_is_constant_false(restrictlist, false) &&
231 bms_is_subset(rel2->relids, sjinfo->syn_righthand))
232 mark_dummy_rel(rel2);
233 add_paths_to_joinrel(root, joinrel, rel1, rel2,
238 /* other values not expected here */
239 elog(ERROR, "unrecognized join type: %d", (int) sjinfo->jointype);
243 bms_free(joinrelids);