Age Owner TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * joinrels.c
4 : * Routines to determine which relations should be joined
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/path/joinrels.c
12 : *
13 : *-------------------------------------------------------------------------
14 : */
15 : #include "postgres.h"
16 :
17 : #include "miscadmin.h"
18 : #include "optimizer/appendinfo.h"
19 : #include "optimizer/joininfo.h"
20 : #include "optimizer/pathnode.h"
21 : #include "optimizer/paths.h"
22 : #include "partitioning/partbounds.h"
23 : #include "utils/memutils.h"
24 :
25 :
26 : static void make_rels_by_clause_joins(PlannerInfo *root,
27 : RelOptInfo *old_rel,
28 : List *other_rels_list,
29 : ListCell *other_rels);
30 : static void make_rels_by_clauseless_joins(PlannerInfo *root,
31 : RelOptInfo *old_rel,
32 : List *other_rels);
33 : static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel);
34 : static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel);
35 : static bool restriction_is_constant_false(List *restrictlist,
36 : RelOptInfo *joinrel,
37 : bool only_pushed_down);
38 : static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
39 : RelOptInfo *rel2, RelOptInfo *joinrel,
40 : SpecialJoinInfo *sjinfo, List *restrictlist);
41 : static void try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1,
42 : RelOptInfo *rel2, RelOptInfo *joinrel,
43 : SpecialJoinInfo *parent_sjinfo,
44 : List *parent_restrictlist);
45 : static SpecialJoinInfo *build_child_join_sjinfo(PlannerInfo *root,
46 : SpecialJoinInfo *parent_sjinfo,
47 : Relids left_relids, Relids right_relids);
48 : static void compute_partition_bounds(PlannerInfo *root, RelOptInfo *rel1,
49 : RelOptInfo *rel2, RelOptInfo *joinrel,
50 : SpecialJoinInfo *parent_sjinfo,
51 : List **parts1, List **parts2);
52 : static void get_matching_part_pairs(PlannerInfo *root, RelOptInfo *joinrel,
53 : RelOptInfo *rel1, RelOptInfo *rel2,
54 : List **parts1, List **parts2);
55 :
56 :
57 : /*
58 : * join_search_one_level
59 : * Consider ways to produce join relations containing exactly 'level'
60 : * jointree items. (This is one step of the dynamic-programming method
61 : * embodied in standard_join_search.) Join rel nodes for each feasible
62 : * combination of lower-level rels are created and returned in a list.
63 : * Implementation paths are created for each such joinrel, too.
64 : *
65 : * level: level of rels we want to make this time
66 : * root->join_rel_level[j], 1 <= j < level, is a list of rels containing j items
67 : *
68 : * The result is returned in root->join_rel_level[level].
69 : */
70 : void
4880 tgl 71 CBC 47977 : join_search_one_level(PlannerInfo *root, int level)
72 : {
73 47977 : List **joinrels = root->join_rel_level;
74 : ListCell *r;
75 : int k;
76 :
77 47977 : Assert(joinrels[level] == NIL);
78 :
79 : /* Set join_cur_level so that new joinrels are added to proper list */
80 47977 : root->join_cur_level = level;
81 :
82 : /*
83 : * First, consider left-sided and right-sided plans, in which rels of
84 : * exactly level-1 member relations are joined against initial relations.
85 : * We prefer to join using join clauses, but if we find a rel of level-1
86 : * members that has no join clauses, we will generate Cartesian-product
87 : * joins against all initial rels not already contained in it.
88 : */
8053 bruce 89 168969 : foreach(r, joinrels[level - 1])
90 : {
8816 91 120992 : RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
92 :
5896 tgl 93 132495 : if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
94 11503 : has_join_restriction(root, old_rel))
8462 95 116796 : {
96 : /*
97 : * There are join clauses or join order restrictions relevant to
98 : * this rel, so consider joins between this rel and (only) those
99 : * initial rels it is linked to by a clause or restriction.
100 : *
101 : * At level 2 this condition is symmetric, so there is no need to
102 : * look at initial rels before this one in the list; we already
103 : * considered such joins when we were at the earlier rel. (The
104 : * mirror-image joins are handled automatically by make_join_rel.)
105 : * In later passes (level > 2), we join rels of the previous level
106 : * to each initial rel they don't already include but have a join
107 : * clause or restriction with.
108 : */
109 : List *other_rels_list;
110 : ListCell *other_rels;
111 :
4006 112 116796 : if (level == 2) /* consider remaining initial rels */
113 : {
1364 114 78516 : other_rels_list = joinrels[level - 1];
115 78516 : other_rels = lnext(other_rels_list, r);
116 : }
117 : else /* consider all initial rels */
118 : {
119 38280 : other_rels_list = joinrels[1];
120 38280 : other_rels = list_head(other_rels_list);
121 : }
122 :
4880 123 116796 : make_rels_by_clause_joins(root,
124 : old_rel,
125 : other_rels_list,
126 : other_rels);
127 : }
128 : else
129 : {
130 : /*
131 : * Oops, we have a relation that is not joined to any other
132 : * relation, either directly or by join-order restrictions.
133 : * Cartesian product time.
134 : *
135 : * We consider a cartesian product with each not-already-included
136 : * initial rel, whether it has other join clauses or not. At
137 : * level 2, if there are two or more clauseless initial rels, we
138 : * will redundantly consider joining them in both directions; but
139 : * such cases aren't common enough to justify adding complexity to
140 : * avoid the duplicated effort.
141 : */
142 4196 : make_rels_by_clauseless_joins(root,
143 : old_rel,
1364 144 4196 : joinrels[1]);
145 : }
146 : }
147 :
148 : /*
149 : * Now, consider "bushy plans" in which relations of k initial rels are
150 : * joined to relations of level-k initial rels, for 2 <= k <= level-2.
151 : *
152 : * We only consider bushy-plan joins for pairs of rels where there is a
153 : * suitable join clause (or join order restriction), in order to avoid
154 : * unreasonable growth of planning time.
155 : */
8053 bruce 156 47977 : for (k = 2;; k++)
8720 157 4846 : {
8244 tgl 158 52823 : int other_level = level - k;
159 :
160 : /*
161 : * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
162 : * need to go as far as the halfway point.
163 : */
164 52823 : if (k > other_level)
8462 165 47977 : break;
166 :
8244 167 24170 : foreach(r, joinrels[k])
168 : {
169 19324 : RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
170 : List *other_rels_list;
171 : ListCell *other_rels;
172 : ListCell *r2;
173 :
174 : /*
175 : * We can ignore relations without join clauses here, unless they
176 : * participate in join-order restrictions --- then we might have
177 : * to force a bushy join plan.
178 : */
5923 179 19324 : if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
5896 180 108 : !has_join_restriction(root, old_rel))
5962 181 72 : continue;
182 :
8244 183 19252 : if (k == other_level)
184 : {
185 : /* only consider remaining rels */
1364 186 13888 : other_rels_list = joinrels[k];
187 13888 : other_rels = lnext(other_rels_list, r);
188 : }
189 : else
190 : {
191 5364 : other_rels_list = joinrels[other_level];
192 5364 : other_rels = list_head(other_rels_list);
193 : }
194 :
195 79562 : for_each_cell(r2, other_rels_list, other_rels)
196 : {
8244 197 60310 : RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
198 :
7365 199 60310 : if (!bms_overlap(old_rel->relids, new_rel->relids))
200 : {
201 : /*
202 : * OK, we can build a rel of the right level from this
203 : * pair of rels. Do so if there is at least one relevant
204 : * join clause or join order restriction.
205 : */
5896 206 8211 : if (have_relevant_joinclause(root, old_rel, new_rel) ||
207 485 : have_join_order_restriction(root, old_rel, new_rel))
208 : {
4880 209 7259 : (void) make_join_rel(root, old_rel, new_rel);
210 : }
211 : }
212 : }
213 : }
214 : }
215 :
216 : /*----------
217 : * Last-ditch effort: if we failed to find any usable joins so far, force
218 : * a set of cartesian-product joins to be generated. This handles the
219 : * special case where all the available rels have join clauses but we
220 : * cannot use any of those clauses yet. This can only happen when we are
221 : * considering a join sub-problem (a sub-joinlist) and all the rels in the
222 : * sub-problem have only join clauses with rels outside the sub-problem.
223 : * An example is
224 : *
225 : * SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
226 : * WHERE a.w = c.x and b.y = d.z;
227 : *
228 : * If the "a INNER JOIN b" sub-problem does not get flattened into the
229 : * upper level, we must be willing to make a cartesian join of a and b;
230 : * but the code above will not have done so, because it thought that both
231 : * a and b have joinclauses. We consider only left-sided and right-sided
232 : * cartesian joins in this case (no bushy).
233 : *----------
234 : */
3889 235 47977 : if (joinrels[level] == NIL)
236 : {
237 : /*
238 : * This loop is just like the first one, except we always call
239 : * make_rels_by_clauseless_joins().
240 : */
241 27 : foreach(r, joinrels[level - 1])
242 : {
243 18 : RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
244 :
245 18 : make_rels_by_clauseless_joins(root,
246 : old_rel,
1364 247 18 : joinrels[1]);
248 : }
249 :
250 : /*----------
251 : * When special joins are involved, there may be no legal way
252 : * to make an N-way join for some values of N. For example consider
253 : *
254 : * SELECT ... FROM t1 WHERE
255 : * x IN (SELECT ... FROM t2,t3 WHERE ...) AND
256 : * y IN (SELECT ... FROM t4,t5 WHERE ...)
257 : *
258 : * We will flatten this query to a 5-way join problem, but there are
259 : * no 4-way joins that join_is_legal() will consider legal. We have
260 : * to accept failure at level 4 and go on to discover a workable
261 : * bushy plan at level 5.
262 : *
263 : * However, if there are no special joins and no lateral references
264 : * then join_is_legal() should never fail, and so the following sanity
265 : * check is useful.
266 : *----------
267 : */
3878 268 9 : if (joinrels[level] == NIL &&
269 3 : root->join_info_list == NIL &&
2676 tgl 270 UBC 0 : !root->hasLateralRTEs)
3889 271 0 : elog(ERROR, "failed to build any %d-way joins", level);
272 : }
9770 scrappy 273 CBC 47977 : }
274 :
275 : /*
276 : * make_rels_by_clause_joins
277 : * Build joins between the given relation 'old_rel' and other relations
278 : * that participate in join clauses that 'old_rel' also participates in
279 : * (or participate in join-order restrictions with it).
280 : * The join rels are returned in root->join_rel_level[join_cur_level].
281 : *
282 : * Note: at levels above 2 we will generate the same joined relation in
283 : * multiple ways --- for example (a join b) join c is the same RelOptInfo as
284 : * (b join c) join a, though the second case will add a different set of Paths
285 : * to it. This is the reason for using the join_rel_level mechanism, which
286 : * automatically ensures that each new joinrel is only added to the list once.
287 : *
288 : * 'old_rel' is the relation entry for the relation to be joined
289 : * 'other_rels_list': a list containing the other
290 : * rels to be considered for joining
291 : * 'other_rels': the first cell to be considered
292 : *
293 : * Currently, this is only used with initial rels in other_rels, but it
294 : * will work for joining to joinrels too.
295 : */
296 : static void
6517 tgl 297 116796 : make_rels_by_clause_joins(PlannerInfo *root,
298 : RelOptInfo *old_rel,
299 : List *other_rels_list,
300 : ListCell *other_rels)
301 : {
302 : ListCell *l;
303 :
1364 304 342798 : for_each_cell(l, other_rels_list, other_rels)
305 : {
6513 306 226002 : RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
307 :
308 355083 : if (!bms_overlap(old_rel->relids, other_rel->relids) &&
5896 309 157165 : (have_relevant_joinclause(root, old_rel, other_rel) ||
310 28084 : have_join_order_restriction(root, old_rel, other_rel)))
311 : {
4880 312 105267 : (void) make_join_rel(root, old_rel, other_rel);
313 : }
314 : }
9770 scrappy 315 116796 : }
316 :
317 : /*
318 : * make_rels_by_clauseless_joins
319 : * Given a relation 'old_rel' and a list of other relations
320 : * 'other_rels', create a join relation between 'old_rel' and each
321 : * member of 'other_rels' that isn't already included in 'old_rel'.
322 : * The join rels are returned in root->join_rel_level[join_cur_level].
323 : *
324 : * 'old_rel' is the relation entry for the relation to be joined
325 : * 'other_rels': a list containing the other rels to be considered for joining
326 : *
327 : * Currently, this is only used with initial rels in other_rels, but it would
328 : * work for joining to joinrels too.
329 : */
330 : static void
6517 tgl 331 4214 : make_rels_by_clauseless_joins(PlannerInfo *root,
332 : RelOptInfo *old_rel,
333 : List *other_rels)
334 : {
335 : ListCell *l;
336 :
1364 337 13260 : foreach(l, other_rels)
338 : {
4880 339 9046 : RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
340 :
7365 341 9046 : if (!bms_overlap(other_rel->relids, old_rel->relids))
342 : {
4880 343 4464 : (void) make_join_rel(root, old_rel, other_rel);
344 : }
345 : }
9770 scrappy 346 4214 : }
347 :
348 :
349 : /*
350 : * join_is_legal
351 : * Determine whether a proposed join is legal given the query's
352 : * join order constraints; and if it is, determine the join type.
353 : *
354 : * Caller must supply not only the two rels, but the union of their relids.
355 : * (We could simplify the API by computing joinrelids locally, but this
356 : * would be redundant work in the normal path through make_join_rel.
357 : * Note that this value does NOT include the RT index of any outer join that
358 : * might need to be performed here, so it's not the canonical identifier
359 : * of the join relation.)
360 : *
361 : * On success, *sjinfo_p is set to NULL if this is to be a plain inner join,
362 : * else it's set to point to the associated SpecialJoinInfo node. Also,
363 : * *reversed_p is set true if the given relations need to be swapped to
364 : * match the SpecialJoinInfo node.
365 : */
366 : static bool
5644 tgl 367 GIC 119438 : join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
368 : Relids joinrelids,
369 : SpecialJoinInfo **sjinfo_p, bool *reversed_p)
9770 scrappy 370 ECB : {
371 : SpecialJoinInfo *match_sjinfo;
372 : bool reversed;
373 : bool unique_ified;
374 : bool must_be_leftjoin;
375 : ListCell *l;
376 :
377 : /*
378 : * Ensure output params are set on failure return. This is just to
379 : * suppress uninitialized-variable warnings from overly anal compilers.
380 : */
5351 tgl 381 GIC 119438 : *sjinfo_p = NULL;
382 119438 : *reversed_p = false;
383 :
7384 tgl 384 ECB : /*
5351 385 : * If we have any special joins, the proposed join might be illegal; and
386 : * in any case we have to determine its join type. Scan the join info
387 : * list for matches and conflicts.
388 : */
5351 tgl 389 GIC 119438 : match_sjinfo = NULL;
390 119438 : reversed = false;
5012 391 119438 : unique_ified = false;
2803 tgl 392 CBC 119438 : must_be_leftjoin = false;
7384 tgl 393 ECB :
5351 tgl 394 CBC 254525 : foreach(l, root->join_info_list)
6319 tgl 395 ECB : {
5351 tgl 396 GIC 139638 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
7384 tgl 397 ECB :
398 : /*
5351 399 : * This special join is not relevant unless its RHS overlaps the
400 : * proposed join. (Check this first as a fast path for dismissing
401 : * most irrelevant SJs quickly.)
402 : */
5351 tgl 403 GIC 139638 : if (!bms_overlap(sjinfo->min_righthand, joinrelids))
6319 404 47432 : continue;
405 :
6319 tgl 406 ECB : /*
407 : * Also, not relevant if proposed join is fully contained within RHS
408 : * (ie, we're still building up the RHS).
409 : */
5351 tgl 410 GIC 92206 : if (bms_is_subset(joinrelids, sjinfo->min_righthand))
6319 411 2648 : continue;
412 :
6319 tgl 413 ECB : /*
5351 414 : * Also, not relevant if SJ is already done within either input.
415 : */
5351 tgl 416 GIC 167824 : if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
417 78266 : bms_is_subset(sjinfo->min_righthand, rel1->relids))
6319 418 37114 : continue;
5351 tgl 419 CBC 60002 : if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
420 7558 : bms_is_subset(sjinfo->min_righthand, rel2->relids))
6319 421 3851 : continue;
7188 bruce 422 ECB :
5008 tgl 423 : /*
4790 bruce 424 : * If it's a semijoin and we already joined the RHS to any other rels
425 : * within either input, then we must have unique-ified the RHS at that
426 : * point (see below). Therefore the semijoin is no longer relevant in
427 : * this join path.
428 : */
5008 tgl 429 GIC 48593 : if (sjinfo->jointype == JOIN_SEMI)
430 : {
431 2720 : if (bms_is_subset(sjinfo->syn_righthand, rel1->relids) &&
5008 tgl 432 CBC 429 : !bms_equal(sjinfo->syn_righthand, rel1->relids))
5008 tgl 433 GIC 57 : continue;
5008 tgl 434 CBC 2663 : if (bms_is_subset(sjinfo->syn_righthand, rel2->relids) &&
435 1391 : !bms_equal(sjinfo->syn_righthand, rel2->relids))
436 3 : continue;
5008 tgl 437 ECB : }
438 :
6319 439 : /*
440 : * If one input contains min_lefthand and the other contains
441 : * min_righthand, then we can perform the SJ at this join.
442 : *
443 : * Reject if we get matches to more than one SJ; that implies we're
444 : * considering something that's not really valid.
445 : */
5351 tgl 446 GIC 89682 : if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
447 41149 : bms_is_subset(sjinfo->min_righthand, rel2->relids))
448 : {
5351 tgl 449 CBC 37697 : if (match_sjinfo)
5624 bruce 450 4551 : return false; /* invalid join path */
5351 tgl 451 GIC 37697 : match_sjinfo = sjinfo;
5351 tgl 452 CBC 37697 : reversed = false;
6319 tgl 453 ECB : }
5351 tgl 454 CBC 14516 : else if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
455 3680 : bms_is_subset(sjinfo->min_righthand, rel1->relids))
456 : {
457 3119 : if (match_sjinfo)
5624 bruce 458 LBC 0 : return false; /* invalid join path */
5351 tgl 459 GIC 3119 : match_sjinfo = sjinfo;
5351 tgl 460 CBC 3119 : reversed = true;
6319 tgl 461 EUB : }
5251 tgl 462 CBC 8905 : else if (sjinfo->jointype == JOIN_SEMI &&
5245 463 1368 : bms_equal(sjinfo->syn_righthand, rel2->relids) &&
5245 tgl 464 GIC 180 : create_unique_path(root, rel2, rel2->cheapest_total_path,
5245 tgl 465 ECB : sjinfo) != NULL)
5251 466 : {
5162 467 : /*----------
468 : * For a semijoin, we can join the RHS to anything else by
469 : * unique-ifying the RHS (if the RHS can be unique-ified).
470 : * We will only get here if we have the full RHS but less
471 : * than min_lefthand on the LHS.
472 : *
473 : * The reason to consider such a join path is exemplified by
474 : * SELECT ... FROM a,b WHERE (a.x,b.y) IN (SELECT c1,c2 FROM c)
475 : * If we insist on doing this as a semijoin we will first have
476 : * to form the cartesian product of A*B. But if we unique-ify
477 : * C then the semijoin becomes a plain innerjoin and we can join
478 : * in any order, eg C to A and then to B. When C is much smaller
479 : * than A and B this can be a huge win. So we allow C to be
480 : * joined to just A or just B here, and then make_join_rel has
481 : * to handle the case properly.
482 : *
483 : * Note that actually we'll allow unique-ified C to be joined to
484 : * some other relation D here, too. That is legal, if usually not
485 : * very sane, and this routine is only concerned with legality not
486 : * with whether the join is good strategy.
487 : *----------
488 : */
5251 tgl 489 GIC 177 : if (match_sjinfo)
490 39 : return false; /* invalid join path */
491 138 : match_sjinfo = sjinfo;
5251 tgl 492 CBC 138 : reversed = false;
5012 493 138 : unique_ified = true;
5251 tgl 494 ECB : }
5251 tgl 495 CBC 8551 : else if (sjinfo->jointype == JOIN_SEMI &&
5245 496 1119 : bms_equal(sjinfo->syn_righthand, rel1->relids) &&
5245 tgl 497 GIC 108 : create_unique_path(root, rel1, rel1->cheapest_total_path,
5245 tgl 498 ECB : sjinfo) != NULL)
5251 499 : {
500 : /* Reversed semijoin case */
5251 tgl 501 GIC 108 : if (match_sjinfo)
502 39 : return false; /* invalid join path */
503 69 : match_sjinfo = sjinfo;
5251 tgl 504 CBC 69 : reversed = true;
5012 505 69 : unique_ified = true;
5251 tgl 506 ECB : }
6319 507 : else
508 : {
509 : /*
510 : * Otherwise, the proposed join overlaps the RHS but isn't a valid
511 : * implementation of this SJ. But don't panic quite yet: the RHS
512 : * violation might have occurred previously, in one or both input
513 : * relations, in which case we must have previously decided that
514 : * it was OK to commute some other SJ with this one. If we need
515 : * to perform this join to finish building up the RHS, rejecting
516 : * it could lead to not finding any plan at all. (This can occur
517 : * because of the heuristics elsewhere in this file that postpone
518 : * clauseless joins: we might not consider doing a clauseless join
519 : * within the RHS until after we've performed other, validly
520 : * commutable SJs with one or both sides of the clauseless join.)
521 : * This consideration boils down to the rule that if both inputs
522 : * overlap the RHS, we can allow the join --- they are either
523 : * fully within the RHS, or represent previously-allowed joins to
524 : * rels outside it.
525 : */
2797 tgl 526 GIC 10412 : if (bms_overlap(rel1->relids, sjinfo->min_righthand) &&
527 2980 : bms_overlap(rel2->relids, sjinfo->min_righthand))
528 81 : continue; /* assume valid previous violation of RHS */
2797 tgl 529 ECB :
530 : /*
531 : * The proposed join could still be legal, but only if we're
532 : * allowed to associate it into the RHS of this SJ. That means
533 : * this SJ must be a LEFT join (not SEMI or ANTI, and certainly
534 : * not FULL) and the proposed join must not overlap the LHS.
535 : */
2803 tgl 536 GIC 13733 : if (sjinfo->jointype != JOIN_LEFT ||
2804 537 6382 : bms_overlap(joinrelids, sjinfo->min_lefthand))
538 4473 : return false; /* invalid join path */
2808 tgl 539 ECB :
2803 540 : /*
541 : * To be valid, the proposed join must be a LEFT join; otherwise
542 : * it can't associate into this SJ's RHS. But we may not yet have
543 : * found the SpecialJoinInfo matching the proposed join, so we
544 : * can't test that yet. Remember the requirement for later.
545 : */
2803 tgl 546 GIC 2878 : must_be_leftjoin = true;
547 : }
548 : }
6319 tgl 549 ECB :
550 : /*
551 : * Fail if violated any SJ's RHS and didn't match to a LEFT SJ: the
552 : * proposed join can't associate into an SJ's RHS.
553 : *
554 : * Also, fail if the proposed join's predicate isn't strict; we're
555 : * essentially checking to see if we can apply outer-join identity 3, and
556 : * that's a requirement. (This check may be redundant with checks in
557 : * make_outerjoininfo, but I'm not quite sure, and it's cheap to test.)
558 : */
2803 tgl 559 GIC 114887 : if (must_be_leftjoin &&
560 1662 : (match_sjinfo == NULL ||
561 1662 : match_sjinfo->jointype != JOIN_LEFT ||
2803 tgl 562 CBC 1662 : !match_sjinfo->lhs_strict))
5644 563 591 : return false; /* invalid join path */
6319 tgl 564 ECB :
3878 565 : /*
566 : * We also have to check for constraints imposed by LATERAL references.
567 : */
2676 tgl 568 GIC 114296 : if (root->hasLateralRTEs)
569 : {
570 : bool lateral_fwd;
2676 tgl 571 ECB : bool lateral_rev;
572 : Relids join_lateral_rels;
573 :
574 : /*
575 : * The proposed rels could each contain lateral references to the
576 : * other, in which case the join is impossible. If there are lateral
577 : * references in just one direction, then the join has to be done with
578 : * a nestloop with the lateral referencer on the inside. If the join
579 : * matches an SJ that cannot be implemented by such a nestloop, the
580 : * join is impossible.
581 : *
582 : * Also, if the lateral reference is only indirect, we should reject
583 : * the join; whatever rel(s) the reference chain goes through must be
584 : * joined to first.
585 : *
586 : * Another case that might keep us from building a valid plan is the
587 : * implementation restriction described by have_dangerous_phv().
588 : */
2676 tgl 589 GIC 6023 : lateral_fwd = bms_overlap(rel1->relids, rel2->lateral_relids);
590 6023 : lateral_rev = bms_overlap(rel2->relids, rel1->lateral_relids);
591 6023 : if (lateral_fwd && lateral_rev)
2676 tgl 592 CBC 9 : return false; /* have lateral refs in both directions */
593 6014 : if (lateral_fwd)
3878 tgl 594 ECB : {
595 : /* has to be implemented as nestloop with rel1 on left */
3878 tgl 596 CBC 3760 : if (match_sjinfo &&
2809 tgl 597 GIC 72 : (reversed ||
598 66 : unique_ified ||
2809 tgl 599 CBC 66 : match_sjinfo->jointype == JOIN_FULL))
3878 600 6 : return false; /* not implementable as nestloop */
2676 tgl 601 ECB : /* check there is a direct reference from rel2 to rel1 */
2676 tgl 602 CBC 3754 : if (!bms_overlap(rel1->relids, rel2->direct_lateral_relids))
603 21 : return false; /* only indirect refs, so reject */
604 : /* check we won't have a dangerous PHV */
605 3733 : if (have_dangerous_phv(root, rel1->relids, rel2->lateral_relids))
606 36 : return false; /* might be unable to handle required PHV */
607 : }
608 2254 : else if (lateral_rev)
3878 tgl 609 ECB : {
610 : /* has to be implemented as nestloop with rel2 on left */
3878 tgl 611 CBC 491 : if (match_sjinfo &&
2809 tgl 612 GIC 36 : (!reversed ||
613 36 : unique_ified ||
2809 tgl 614 CBC 36 : match_sjinfo->jointype == JOIN_FULL))
3878 tgl 615 LBC 0 : return false; /* not implementable as nestloop */
2676 tgl 616 ECB : /* check there is a direct reference from rel1 to rel2 */
2676 tgl 617 CBC 491 : if (!bms_overlap(rel2->relids, rel1->direct_lateral_relids))
2676 tgl 618 UBC 0 : return false; /* only indirect refs, so reject */
619 : /* check we won't have a dangerous PHV */
2676 tgl 620 CBC 491 : if (have_dangerous_phv(root, rel2->relids, rel1->lateral_relids))
2676 tgl 621 GBC 42 : return false; /* might be unable to handle required PHV */
622 : }
3878 tgl 623 ECB :
2676 624 : /*
625 : * LATERAL references could also cause problems later on if we accept
626 : * this join: if the join's minimum parameterization includes any rels
627 : * that would have to be on the inside of an outer join with this join
628 : * rel, then it's never going to be possible to build the complete
629 : * query using this join. We should reject this join not only because
630 : * it'll save work, but because if we don't, the clauseless-join
631 : * heuristics might think that legality of this join means that some
632 : * other join rel need not be formed, and that could lead to failure
633 : * to find any plan at all. We have to consider not only rels that
634 : * are directly on the inner side of an OJ with the joinrel, but also
635 : * ones that are indirectly so, so search to find all such rels.
636 : */
2676 tgl 637 GIC 5909 : join_lateral_rels = min_join_parameterization(root, joinrelids,
638 : rel1, rel2);
639 5909 : if (join_lateral_rels)
2680 tgl 640 ECB : {
2676 tgl 641 GIC 677 : Relids join_plus_rhs = bms_copy(joinrelids);
2676 tgl 642 ECB : bool more;
643 :
644 : do
645 : {
2676 tgl 646 GIC 791 : more = false;
647 1304 : foreach(l, root->join_info_list)
648 : {
2676 tgl 649 CBC 513 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
2676 tgl 650 ECB :
651 : /* ignore full joins --- their ordering is predetermined */
1462 tgl 652 CBC 513 : if (sjinfo->jointype == JOIN_FULL)
1462 tgl 653 GIC 9 : continue;
654 :
2676 tgl 655 CBC 504 : if (bms_overlap(sjinfo->min_lefthand, join_plus_rhs) &&
656 411 : !bms_is_subset(sjinfo->min_righthand, join_plus_rhs))
657 : {
658 159 : join_plus_rhs = bms_add_members(join_plus_rhs,
2118 659 159 : sjinfo->min_righthand);
2676 tgl 660 GIC 159 : more = true;
2676 tgl 661 ECB : }
662 : }
2676 tgl 663 CBC 791 : } while (more);
2676 tgl 664 GIC 677 : if (bms_overlap(join_plus_rhs, join_lateral_rels))
665 114 : return false; /* will not be able to join to some RHS rel */
2680 tgl 666 ECB : }
667 : }
668 :
669 : /* Otherwise, it's a valid join */
5351 tgl 670 GIC 114068 : *sjinfo_p = match_sjinfo;
671 114068 : *reversed_p = reversed;
5644 672 114068 : return true;
5644 tgl 673 ECB : }
674 :
675 :
676 : /*
677 : * make_join_rel
678 : * Find or create a join RelOptInfo that represents the join of
679 : * the two given rels, and add to it path information for paths
680 : * created with the two rels as outer and inner rel.
681 : * (The join rel may already contain paths generated from other
682 : * pairs of rels that add up to the same set of base rels.)
683 : *
684 : * NB: will return NULL if attempted join is not valid. This can happen
685 : * when working with outer joins, or with IN or EXISTS clauses that have been
686 : * turned into joins.
687 : */
688 : RelOptInfo *
5644 tgl 689 GIC 119366 : make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
690 : {
691 : Relids joinrelids;
5351 tgl 692 ECB : SpecialJoinInfo *sjinfo;
693 : bool reversed;
694 : SpecialJoinInfo sjinfo_data;
695 : RelOptInfo *joinrel;
696 : List *restrictlist;
697 :
698 : /* We should never try to join two overlapping sets of rels. */
5644 tgl 699 GIC 119366 : Assert(!bms_overlap(rel1->relids, rel2->relids));
700 :
701 : /* Construct Relids set that identifies the joinrel (without OJ as yet). */
5644 tgl 702 CBC 119366 : joinrelids = bms_union(rel1->relids, rel2->relids);
703 :
704 : /* Check validity and determine join type. */
5351 705 119366 : if (!join_is_legal(root, rel1, rel2, joinrelids,
706 : &sjinfo, &reversed))
707 : {
5644 tgl 708 ECB : /* invalid join path */
5644 tgl 709 GIC 5331 : bms_free(joinrelids);
710 5331 : return NULL;
711 : }
7384 tgl 712 ECB :
713 : /* If we have an outer join, add its RTI to form the canonical relids. */
69 tgl 714 GNC 114035 : if (sjinfo && sjinfo->ojrelid != 0)
715 36232 : joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);
716 :
5351 tgl 717 ECB : /* Swap rels if needed to match the join info. */
5351 tgl 718 GIC 114035 : if (reversed)
719 : {
720 3116 : RelOptInfo *trel = rel1;
5351 tgl 721 ECB :
5351 tgl 722 CBC 3116 : rel1 = rel2;
5351 tgl 723 GIC 3116 : rel2 = trel;
724 : }
5351 tgl 725 ECB :
726 : /*
727 : * If it's a plain inner join, then we won't have found anything in
728 : * join_info_list. Make up a SpecialJoinInfo so that selectivity
729 : * estimation functions will know what's being joined.
730 : */
5351 tgl 731 GIC 114035 : if (sjinfo == NULL)
732 : {
733 73210 : sjinfo = &sjinfo_data;
734 73210 : sjinfo->type = T_SpecialJoinInfo;
735 73210 : sjinfo->min_lefthand = rel1->relids;
736 73210 : sjinfo->min_righthand = rel2->relids;
737 73210 : sjinfo->syn_lefthand = rel1->relids;
5351 tgl 738 CBC 73210 : sjinfo->syn_righthand = rel2->relids;
5351 tgl 739 GIC 73210 : sjinfo->jointype = JOIN_INNER;
69 tgl 740 GNC 73210 : sjinfo->ojrelid = 0;
741 73210 : sjinfo->commute_above_l = NULL;
742 73210 : sjinfo->commute_above_r = NULL;
743 73210 : sjinfo->commute_below = NULL;
5351 tgl 744 ECB : /* we don't bother trying to make the remaining fields valid */
5351 tgl 745 CBC 73210 : sjinfo->lhs_strict = false;
2951 746 73210 : sjinfo->semi_can_btree = false;
747 73210 : sjinfo->semi_can_hash = false;
748 73210 : sjinfo->semi_operators = NIL;
749 73210 : sjinfo->semi_rhs_exprs = NIL;
5351 tgl 750 ECB : }
751 :
9345 bruce 752 : /*
6385 753 : * Find or build the join RelOptInfo, and compute the restrictlist that
754 : * goes with this particular joining.
9345 755 : */
5351 tgl 756 CBC 114035 : joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
7384 tgl 757 ECB : &restrictlist);
9345 bruce 758 :
8462 tgl 759 : /*
760 : * If we've already proven this join is empty, we needn't consider any
761 : * more paths for it.
762 : */
5494 tgl 763 GIC 114035 : if (is_dummy_rel(joinrel))
764 : {
765 204 : bms_free(joinrelids);
5494 tgl 766 CBC 204 : return joinrel;
767 : }
768 :
769 : /* Add paths to the join relation. */
2217 rhaas 770 GIC 113831 : populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
771 : restrictlist);
772 :
2217 rhaas 773 CBC 113831 : bms_free(joinrelids);
774 :
775 113831 : return joinrel;
2217 rhaas 776 ECB : }
777 :
778 : /*
779 : * populate_joinrel_with_paths
780 : * Add paths to the given joinrel for given pair of joining relations. The
781 : * SpecialJoinInfo provides details about the join and the restrictlist
782 : * contains the join clauses and the other clauses applicable for given pair
783 : * of the joining relations.
784 : */
785 : static void
2217 rhaas 786 GIC 116199 : populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
787 : RelOptInfo *rel2, RelOptInfo *joinrel,
788 : SpecialJoinInfo *sjinfo, List *restrictlist)
789 : {
790 : /*
791 : * Consider paths using each rel as both outer and inner. Depending on
792 : * the join type, a provably empty outer or inner rel might mean the join
793 : * is provably empty too; in which case throw away any previously computed
794 : * paths and mark the join as dummy. (We do it this way since it's
795 : * conceivable that dummy-ness of a multi-element join might only be
5050 bruce 796 ECB : * noticeable for certain construction paths.)
797 : *
798 : * Also, a provably constant-false join restriction typically means that
799 : * we can skip evaluating one or both sides of the join. We do this by
800 : * marking the appropriate rel as dummy. For outer joins, a
801 : * constant-false restriction that is pushed down still means the whole
802 : * join is dummy, while a non-pushed-down one means that no inner rows
803 : * will join so we can treat the inner rel as dummy.
804 : *
805 : * We need only consider the jointypes that appear in join_info_list, plus
806 : * JOIN_INNER.
807 : */
5351 tgl 808 GIC 116199 : switch (sjinfo->jointype)
809 : {
8244 810 73931 : case JOIN_INNER:
5348 811 147853 : if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
1815 812 73922 : restriction_is_constant_false(restrictlist, joinrel, false))
813 : {
5348 814 90 : mark_dummy_rel(joinrel);
5494 815 90 : break;
816 : }
5351 817 73841 : add_paths_to_joinrel(root, joinrel, rel1, rel2,
5351 tgl 818 ECB : JOIN_INNER, sjinfo,
819 : restrictlist);
5351 tgl 820 CBC 73841 : add_paths_to_joinrel(root, joinrel, rel2, rel1,
5351 tgl 821 ECB : JOIN_INNER, sjinfo,
8244 822 : restrictlist);
8244 tgl 823 GIC 73841 : break;
8244 tgl 824 CBC 36064 : case JOIN_LEFT:
4590 825 72101 : if (is_dummy_rel(rel1) ||
1815 tgl 826 GIC 36037 : restriction_is_constant_false(restrictlist, joinrel, true))
5494 tgl 827 ECB : {
5348 tgl 828 GIC 40 : mark_dummy_rel(joinrel);
5494 829 40 : break;
5494 tgl 830 ECB : }
1815 tgl 831 GIC 36096 : if (restriction_is_constant_false(restrictlist, joinrel, false) &&
5348 832 72 : bms_is_subset(rel2->relids, sjinfo->syn_righthand))
5348 tgl 833 CBC 60 : mark_dummy_rel(rel2);
5351 834 36024 : add_paths_to_joinrel(root, joinrel, rel1, rel2,
5351 tgl 835 ECB : JOIN_LEFT, sjinfo,
8244 836 : restrictlist);
5351 tgl 837 GIC 36024 : add_paths_to_joinrel(root, joinrel, rel2, rel1,
5351 tgl 838 ECB : JOIN_RIGHT, sjinfo,
8244 839 : restrictlist);
8244 tgl 840 GIC 36024 : break;
8244 tgl 841 CBC 791 : case JOIN_FULL:
4590 842 1582 : if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) ||
1815 843 791 : restriction_is_constant_false(restrictlist, joinrel, true))
5494 tgl 844 ECB : {
5348 tgl 845 UIC 0 : mark_dummy_rel(joinrel);
5494 846 0 : break;
5494 tgl 847 ECB : }
5351 tgl 848 GIC 791 : add_paths_to_joinrel(root, joinrel, rel1, rel2,
849 : JOIN_FULL, sjinfo,
7384 tgl 850 ECB : restrictlist);
5351 tgl 851 CBC 791 : add_paths_to_joinrel(root, joinrel, rel2, rel1,
5351 tgl 852 ECB : JOIN_FULL, sjinfo,
7384 853 : restrictlist);
854 :
4483 tgl 855 EUB : /*
856 : * If there are join quals that aren't mergeable or hashable, we
857 : * may not be able to build any valid plan. Complain here so that
4483 tgl 858 ECB : * we can give a somewhat-useful error message. (Since we have no
859 : * flexibility of planning for a full join, there's no chance of
860 : * succeeding later with another pair of input rels.)
861 : */
4483 tgl 862 GIC 791 : if (joinrel->pathlist == NIL)
4483 tgl 863 UIC 0 : ereport(ERROR,
864 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
865 : errmsg("FULL JOIN is only supported with merge-joinable or hash-joinable join conditions")));
7384 tgl 866 GIC 791 : break;
5351 867 1703 : case JOIN_SEMI:
868 :
869 : /*
870 : * We might have a normal semijoin, or a case where we don't have
871 : * enough rels to do the semijoin but can unique-ify the RHS and
5162 tgl 872 ECB : * then do an innerjoin (see comments in join_is_legal). In the
5162 tgl 873 EUB : * latter case we can't apply JOIN_SEMI joining.
874 : */
5251 tgl 875 GIC 3373 : if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
5251 tgl 876 CBC 1670 : bms_is_subset(sjinfo->min_righthand, rel2->relids))
5494 tgl 877 ECB : {
5251 tgl 878 GIC 3337 : if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
1815 879 1667 : restriction_is_constant_false(restrictlist, joinrel, false))
880 : {
5251 881 6 : mark_dummy_rel(joinrel);
882 6 : break;
883 : }
884 1664 : add_paths_to_joinrel(root, joinrel, rel1, rel2,
5251 tgl 885 ECB : JOIN_SEMI, sjinfo,
886 : restrictlist);
887 : }
5351 888 :
889 : /*
890 : * If we know how to unique-ify the RHS and one input rel is
891 : * exactly the RHS (not a superset) we can consider unique-ifying
5245 892 : * it and then doing a regular join. (The create_unique_path
893 : * check here is probably redundant with what join_is_legal did,
894 : * but if so the check is cheap because it's cached. So test
895 : * anyway to be sure.)
896 : */
5351 tgl 897 GIC 3394 : if (bms_equal(sjinfo->syn_righthand, rel2->relids) &&
898 1697 : create_unique_path(root, rel2, rel2->cheapest_total_path,
899 : sjinfo) != NULL)
900 : {
4590 901 3298 : if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
1815 902 1649 : restriction_is_constant_false(restrictlist, joinrel, false))
903 : {
4590 tgl 904 UIC 0 : mark_dummy_rel(joinrel);
905 0 : break;
906 : }
5351 tgl 907 CBC 1649 : add_paths_to_joinrel(root, joinrel, rel1, rel2,
5351 tgl 908 ECB : JOIN_UNIQUE_INNER, sjinfo,
909 : restrictlist);
5351 tgl 910 GIC 1649 : add_paths_to_joinrel(root, joinrel, rel2, rel1,
5351 tgl 911 ECB : JOIN_UNIQUE_OUTER, sjinfo,
912 : restrictlist);
913 : }
7384 tgl 914 GBC 1697 : break;
5351 915 3710 : case JOIN_ANTI:
4590 tgl 916 GIC 7420 : if (is_dummy_rel(rel1) ||
1815 tgl 917 CBC 3710 : restriction_is_constant_false(restrictlist, joinrel, true))
918 : {
5348 tgl 919 UIC 0 : mark_dummy_rel(joinrel);
5494 tgl 920 LBC 0 : break;
921 : }
1815 tgl 922 GIC 3710 : if (restriction_is_constant_false(restrictlist, joinrel, false) &&
5348 tgl 923 UIC 0 : bms_is_subset(rel2->relids, sjinfo->syn_righthand))
5348 tgl 924 LBC 0 : mark_dummy_rel(rel2);
5351 tgl 925 CBC 3710 : add_paths_to_joinrel(root, joinrel, rel1, rel2,
5351 tgl 926 ECB : JOIN_ANTI, sjinfo,
7384 927 : restrictlist);
4 tgl 928 GNC 3710 : add_paths_to_joinrel(root, joinrel, rel2, rel1,
929 : JOIN_RIGHT_ANTI, sjinfo,
930 : restrictlist);
7384 tgl 931 GIC 3710 : break;
8244 tgl 932 UBC 0 : default:
5351 tgl 933 EUB : /* other values not expected here */
5351 tgl 934 UIC 0 : elog(ERROR, "unrecognized join type: %d", (int) sjinfo->jointype);
8244 tgl 935 ECB : break;
8244 tgl 936 EUB : }
2011 rhaas 937 :
1878 peter_e 938 ECB : /* Apply partitionwise join technique, if possible. */
1878 peter_e 939 GIC 116199 : try_partitionwise_join(root, rel1, rel2, joinrel, sjinfo, restrictlist);
9770 scrappy 940 116199 : }
5896 tgl 941 ECB :
942 :
943 : /*
944 : * have_join_order_restriction
5896 tgl 945 EUB : * Detect whether the two relations should be joined to satisfy
946 : * a join-order restriction arising from special or lateral joins.
947 : *
948 : * In practice this is always used with have_relevant_joinclause(), and so
949 : * could be merged with that function, but it seems clearer to separate the
950 : * two concerns. We need this test because there are degenerate cases where
951 : * a clauseless join must be performed to satisfy join-order restrictions.
2676 tgl 952 ECB : * Also, if one rel has a lateral reference to the other, or both are needed
953 : * to compute some PHV, we should consider joining them even if the join would
954 : * be clauseless.
955 : *
956 : * Note: this is only a problem if one side of a degenerate outer join
957 : * contains multiple rels, or a clauseless join is required within an
958 : * IN/EXISTS RHS; else we will find a join path via the "last ditch" case in
959 : * join_search_one_level(). We could dispense with this test if we were
960 : * willing to try bushy plans in the "last ditch" case, but that seems much
961 : * less efficient.
962 : */
963 : bool
5896 tgl 964 GIC 29709 : have_join_order_restriction(PlannerInfo *root,
965 : RelOptInfo *rel1, RelOptInfo *rel2)
966 : {
5644 967 29709 : bool result = false;
968 : ListCell *l;
969 :
970 : /*
971 : * If either side has a direct lateral reference to the other, attempt the
972 : * join regardless of outer-join considerations.
973 : */
2676 974 55853 : if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) ||
975 26144 : bms_overlap(rel2->relids, rel1->direct_lateral_relids))
976 3909 : return true;
3878 tgl 977 ECB :
978 : /*
979 : * Likewise, if both rels are needed to compute some PlaceHolderVar,
2676 980 : * attempt the join regardless of outer-join considerations. (This is not
981 : * very desirable, because a PHV with a large eval_at set will cause a lot
982 : * of probably-useless joins to be considered, but failing to do this can
983 : * cause us to fail to construct a plan at all.)
984 : */
2676 tgl 985 GIC 26465 : foreach(l, root->placeholder_list)
986 : {
2676 tgl 987 CBC 689 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
2676 tgl 988 ECB :
2676 tgl 989 CBC 830 : if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) &&
2676 tgl 990 GIC 141 : bms_is_subset(rel2->relids, phinfo->ph_eval_at))
991 24 : return true;
992 : }
993 :
994 : /*
995 : * It's possible that the rels correspond to the left and right sides of a
996 : * degenerate outer join, that is, one with no joinclause mentioning the
997 : * non-nullable side; in which case we should force the join to occur.
5896 tgl 998 ECB : *
999 : * Also, the two rels could represent a clauseless join that has to be
1000 : * completed to build up the LHS or RHS of an outer join.
1001 : */
5351 tgl 1002 CBC 73102 : foreach(l, root->join_info_list)
5896 tgl 1003 ECB : {
5351 tgl 1004 CBC 47714 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1005 :
1006 : /* ignore full joins --- other mechanisms handle them */
5351 tgl 1007 GIC 47714 : if (sjinfo->jointype == JOIN_FULL)
5896 1008 6 : continue;
1009 :
1010 : /* Can we perform the SJ with these rels? */
5351 1011 60461 : if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
1012 12753 : bms_is_subset(sjinfo->min_righthand, rel2->relids))
1013 : {
5644 1014 319 : result = true;
5644 tgl 1015 CBC 319 : break;
1016 : }
5351 1017 49087 : if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
5351 tgl 1018 GIC 1698 : bms_is_subset(sjinfo->min_righthand, rel1->relids))
1019 : {
5644 tgl 1020 CBC 21 : result = true;
1021 21 : break;
1022 : }
1023 :
5896 tgl 1024 ECB : /*
5624 bruce 1025 : * Might we need to join these rels to complete the RHS? We have to
1026 : * use "overlap" tests since either rel might include a lower SJ that
1027 : * has been proven to commute with this one.
5896 tgl 1028 : */
5351 tgl 1029 GIC 59235 : if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
5351 tgl 1030 CBC 11867 : bms_overlap(sjinfo->min_righthand, rel2->relids))
5644 tgl 1031 ECB : {
5644 tgl 1032 GIC 39 : result = true;
5644 tgl 1033 CBC 39 : break;
5644 tgl 1034 ECB : }
1035 :
1036 : /* Likewise for the LHS. */
5351 tgl 1037 GIC 61089 : if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
1038 13760 : bms_overlap(sjinfo->min_lefthand, rel2->relids))
1039 : {
5644 1040 9 : result = true;
1041 9 : break;
5644 tgl 1042 ECB : }
5896 1043 : }
1044 :
5644 1045 : /*
5624 bruce 1046 : * We do not force the join to occur if either input rel can legally be
1047 : * joined to anything else using joinclauses. This essentially means that
1048 : * clauseless bushy joins are put off as long as possible. The reason is
1049 : * that when there is a join order restriction high up in the join tree
1050 : * (that is, with many rels inside the LHS or RHS), we would otherwise
1051 : * expend lots of effort considering very stupid join combinations within
1052 : * its LHS or RHS.
5644 tgl 1053 : */
5644 tgl 1054 CBC 25776 : if (result)
1055 : {
5644 tgl 1056 GIC 755 : if (has_legal_joinclause(root, rel1) ||
1057 367 : has_legal_joinclause(root, rel2))
1058 33 : result = false;
1059 : }
1060 :
1061 25776 : return result;
1062 : }
1063 :
1064 :
1065 : /*
1066 : * has_join_restriction
3878 tgl 1067 ECB : * Detect whether the specified relation has join-order restrictions,
1068 : * due to being inside an outer join or an IN (sub-SELECT),
2676 1069 : * or participating in any LATERAL references or multi-rel PHVs.
5896 1070 : *
1071 : * Essentially, this tests whether have_join_order_restriction() could
1072 : * succeed with this rel and some other one. It's OK if we sometimes
1073 : * say "true" incorrectly. (Therefore, we don't bother with the relatively
5644 1074 : * expensive has_legal_joinclause test.)
1075 : */
1076 : static bool
5896 tgl 1077 GIC 11611 : has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
1078 : {
1079 : ListCell *l;
1080 :
2676 1081 11611 : if (rel->lateral_relids != NULL || rel->lateral_referencers != NULL)
1082 6678 : return true;
1083 :
1084 5182 : foreach(l, root->placeholder_list)
1085 : {
1086 267 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
1087 :
1088 267 : if (bms_is_subset(rel->relids, phinfo->ph_eval_at) &&
1089 57 : !bms_equal(rel->relids, phinfo->ph_eval_at))
3878 tgl 1090 CBC 18 : return true;
1091 : }
1092 :
5351 tgl 1093 GIC 5171 : foreach(l, root->join_info_list)
5896 tgl 1094 ECB : {
5351 tgl 1095 CBC 903 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1096 :
5896 tgl 1097 ECB : /* ignore full joins --- other mechanisms preserve their ordering */
5351 tgl 1098 GIC 903 : if (sjinfo->jointype == JOIN_FULL)
5896 tgl 1099 CBC 40 : continue;
1100 :
5351 tgl 1101 ECB : /* ignore if SJ is already contained in rel */
5351 tgl 1102 CBC 1329 : if (bms_is_subset(sjinfo->min_lefthand, rel->relids) &&
1103 466 : bms_is_subset(sjinfo->min_righthand, rel->relids))
5896 tgl 1104 GIC 123 : continue;
1105 :
5351 tgl 1106 ECB : /* restricted if it overlaps LHS or RHS, but doesn't contain SJ */
5351 tgl 1107 GIC 1131 : if (bms_overlap(sjinfo->min_lefthand, rel->relids) ||
5351 tgl 1108 CBC 391 : bms_overlap(sjinfo->min_righthand, rel->relids))
5896 tgl 1109 GIC 647 : return true;
1110 : }
5896 tgl 1111 ECB :
5896 tgl 1112 CBC 4268 : return false;
1113 : }
1114 :
5644 tgl 1115 ECB :
1116 : /*
1117 : * has_legal_joinclause
1118 : * Detect whether the specified relation can legally be joined
1119 : * to any other rels using join clauses.
1120 : *
5567 1121 : * We consider only joins to single other relations in the current
1122 : * initial_rels list. This is sufficient to get a "true" result in most real
1123 : * queries, and an occasional erroneous "false" will only cost a bit more
1124 : * planning time. The reason for this limitation is that considering joins to
1125 : * other joins would require proving that the other join rel can legally be
1126 : * formed, which seems like too much trouble for something that's only a
1127 : * heuristic to save planning time. (Note: we must look at initial_rels
1128 : * and not all of the query, since when we are planning a sub-joinlist we
1129 : * may be forced to make clauseless joins within initial_rels even though
1130 : * there are join clauses linking to other parts of the query.)
1131 : */
1132 : static bool
5644 tgl 1133 GIC 755 : has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
1134 : {
1135 : ListCell *lc;
1136 :
5567 1137 2724 : foreach(lc, root->initial_rels)
1138 : {
1139 2002 : RelOptInfo *rel2 = (RelOptInfo *) lfirst(lc);
1140 :
1141 : /* ignore rels that are already in "rel" */
5644 1142 2002 : if (bms_overlap(rel->relids, rel2->relids))
1143 854 : continue;
1144 :
1145 1148 : if (have_relevant_joinclause(root, rel, rel2))
5644 tgl 1146 ECB : {
1147 : Relids joinrelids;
1148 : SpecialJoinInfo *sjinfo;
1149 : bool reversed;
1150 :
1151 : /* join_is_legal needs relids of the union */
5644 tgl 1152 CBC 72 : joinrelids = bms_union(rel->relids, rel2->relids);
1153 :
5351 tgl 1154 GIC 72 : if (join_is_legal(root, rel, rel2, joinrelids,
5351 tgl 1155 ECB : &sjinfo, &reversed))
5644 1156 : {
1157 : /* Yes, this will work */
5644 tgl 1158 CBC 33 : bms_free(joinrelids);
5644 tgl 1159 GIC 33 : return true;
1160 : }
1161 :
1162 39 : bms_free(joinrelids);
1163 : }
1164 : }
5644 tgl 1165 ECB :
5644 tgl 1166 GIC 722 : return false;
5644 tgl 1167 ECB : }
1168 :
1169 :
1170 : /*
2676 1171 : * There's a pitfall for creating parameterized nestloops: suppose the inner
1172 : * rel (call it A) has a parameter that is a PlaceHolderVar, and that PHV's
1173 : * minimum eval_at set includes the outer rel (B) and some third rel (C).
1174 : * We might think we could create a B/A nestloop join that's parameterized by
1175 : * C. But we would end up with a plan in which the PHV's expression has to be
1176 : * evaluated as a nestloop parameter at the B/A join; and the executor is only
1177 : * set up to handle simple Vars as NestLoopParams. Rather than add complexity
1178 : * and overhead to the executor for such corner cases, it seems better to
1179 : * forbid the join. (Note that we can still make use of A's parameterized
1180 : * path with pre-joined B+C as the outer rel. have_join_order_restriction()
1181 : * ensures that we will consider making such a join even if there are not
1182 : * other reasons to do so.)
1183 : *
1184 : * So we check whether any PHVs used in the query could pose such a hazard.
1185 : * We don't have any simple way of checking whether a risky PHV would actually
1186 : * be used in the inner plan, and the case is so unusual that it doesn't seem
1187 : * worth working very hard on it.
1188 : *
1189 : * This needs to be checked in two places. If the inner rel's minimum
1190 : * parameterization would trigger the restriction, then join_is_legal() should
1191 : * reject the join altogether, because there will be no workable paths for it.
1192 : * But joinpath.c has to check again for every proposed nestloop path, because
1193 : * the inner path might have more than the minimum parameterization, causing
1194 : * some PHV to be dangerous for it that otherwise wouldn't be.
1195 : */
1196 : bool
2676 tgl 1197 GIC 16746 : have_dangerous_phv(PlannerInfo *root,
1198 : Relids outer_relids, Relids inner_params)
1199 : {
1200 : ListCell *lc;
1201 :
1202 18111 : foreach(lc, root->placeholder_list)
1203 : {
1204 1491 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1205 :
1206 1491 : if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1207 1095 : continue; /* ignore, could not be a nestloop param */
1208 396 : if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1209 96 : continue; /* ignore, not relevant to this join */
2676 tgl 1210 CBC 300 : if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
2676 tgl 1211 GIC 174 : continue; /* safe, it can be eval'd within outerrel */
1212 : /* Otherwise, it's potentially unsafe, so reject the join */
1213 126 : return true;
1214 : }
2676 tgl 1215 ECB :
1216 : /* OK to perform the join */
2676 tgl 1217 CBC 16620 : return false;
1218 : }
2676 tgl 1219 ECB :
1220 :
5494 1221 : /*
1222 : * is_dummy_rel --- has relation been proven empty?
1223 : */
1494 1224 : bool
5494 tgl 1225 GIC 954143 : is_dummy_rel(RelOptInfo *rel)
5494 tgl 1226 ECB : {
1227 : Path *path;
1228 :
1229 : /*
1494 1230 : * A rel that is known dummy will have just one path that is a childless
1231 : * Append. (Even if somehow it has more paths, a childless Append will
1232 : * have cost zero and hence should be at the front of the pathlist.)
1233 : */
1494 tgl 1234 GIC 954143 : if (rel->pathlist == NIL)
1235 531809 : return false;
1236 422334 : path = (Path *) linitial(rel->pathlist);
1237 :
1494 tgl 1238 ECB : /*
1239 : * Initially, a dummy path will just be a childless Append. But in later
1240 : * planning stages we might stick a ProjectSetPath and/or ProjectionPath
1241 : * on top, since Append can't project. Rather than make assumptions about
1242 : * which combinations can occur, just descend through whatever we find.
1243 : */
1244 : for (;;)
1245 : {
1494 tgl 1246 GIC 436955 : if (IsA(path, ProjectionPath))
1494 tgl 1247 CBC 12670 : path = ((ProjectionPath *) path)->subpath;
1248 424285 : else if (IsA(path, ProjectSetPath))
1249 1951 : path = ((ProjectSetPath *) path)->subpath;
1250 : else
1494 tgl 1251 GIC 422334 : break;
1252 : }
1253 422334 : if (IS_DUMMY_APPEND(path))
1254 2004 : return true;
1255 420330 : return false;
1256 : }
1257 :
1258 : /*
4379 tgl 1259 ECB : * Mark a relation as proven empty.
1260 : *
1261 : * During GEQO planning, this can get invoked more than once on the same
1262 : * baserel struct, so it's worth checking to see if the rel is already marked
1263 : * dummy.
1264 : *
1265 : * Also, when called during GEQO join planning, we are in a short-lived
3260 bruce 1266 : * memory context. We must make sure that the dummy path attached to a
4379 tgl 1267 : * baserel survives the GEQO cycle, else the baserel is trashed for future
1268 : * GEQO cycles. On the other hand, when we are marking a joinrel during GEQO,
1269 : * we don't want the dummy path to clutter the main planning context. Upshot
1270 : * is that the best solution is to explicitly make the dummy path in the same
1271 : * context the given RelOptInfo is in.
1272 : */
1273 : void
5348 tgl 1274 GIC 235 : mark_dummy_rel(RelOptInfo *rel)
1275 : {
1276 : MemoryContext oldcontext;
1277 :
1278 : /* Already marked? */
4379 1279 235 : if (is_dummy_rel(rel))
1280 6 : return;
1281 :
1282 : /* No, so choose correct context to make the dummy path in */
1283 229 : oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1284 :
1285 : /* Set dummy size estimate */
5494 1286 229 : rel->rows = 0;
5494 tgl 1287 ECB :
1288 : /* Evict any previously chosen paths */
5494 tgl 1289 GIC 229 : rel->pathlist = NIL;
2636 rhaas 1290 229 : rel->partial_pathlist = NIL;
1291 :
5494 tgl 1292 ECB : /* Set up the dummy path */
1487 tgl 1293 CBC 229 : add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL,
1294 : NIL, rel->lateral_relids,
1295 : 0, false, -1));
5494 tgl 1296 ECB :
1297 : /* Set or update cheapest_total_path and related fields */
5348 tgl 1298 GIC 229 : set_cheapest(rel);
4379 tgl 1299 ECB :
4379 tgl 1300 GIC 229 : MemoryContextSwitchTo(oldcontext);
1301 : }
5348 tgl 1302 ECB :
1303 :
1304 : /*
1305 : * restriction_is_constant_false --- is a restrictlist just FALSE?
1306 : *
1307 : * In cases where a qual is provably constant FALSE, eval_const_expressions
1308 : * will generally have thrown away anything that's ANDed with it. In outer
1309 : * join situations this will leave us computing cartesian products only to
1310 : * decide there's no match for an outer row, which is pretty stupid. So,
1311 : * we need to detect the case.
1312 : *
1815 1313 : * If only_pushed_down is true, then consider only quals that are pushed-down
1314 : * from the point of view of the joinrel.
1315 : */
1316 : static bool
1815 tgl 1317 GIC 157510 : restriction_is_constant_false(List *restrictlist,
1318 : RelOptInfo *joinrel,
1319 : bool only_pushed_down)
1320 : {
1321 : ListCell *lc;
1322 :
1323 : /*
1324 : * Despite the above comment, the restriction list we see here might
1325 : * possibly have other members besides the FALSE constant, since other
1326 : * quals could get "pushed down" to the outer join level. So we check
1327 : * each member of the list.
1328 : */
5348 1329 329193 : foreach(lc, restrictlist)
5348 tgl 1330 ECB : {
2190 tgl 1331 GIC 171852 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1332 :
1815 1333 171852 : if (only_pushed_down && !RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
4590 1334 47114 : continue;
1335 :
5348 1336 124738 : if (rinfo->clause && IsA(rinfo->clause, Const))
1337 : {
5050 bruce 1338 3779 : Const *con = (Const *) rinfo->clause;
1339 :
1340 : /* constant NULL is as good as constant FALSE for our purposes */
5348 tgl 1341 3779 : if (con->constisnull)
5348 tgl 1342 CBC 169 : return true;
5348 tgl 1343 GIC 3725 : if (!DatumGetBool(con->constvalue))
5348 tgl 1344 CBC 115 : return true;
1345 : }
5348 tgl 1346 ECB : }
5348 tgl 1347 CBC 157341 : return false;
1348 : }
2011 rhaas 1349 ECB :
1350 : /*
1351 : * Assess whether join between given two partitioned relations can be broken
1352 : * down into joins between matching partitions; a technique called
1353 : * "partitionwise join"
1354 : *
1878 peter_e 1355 : * Partitionwise join is possible when a. Joining relations have same
2011 rhaas 1356 : * partitioning scheme b. There exists an equi-join between the partition keys
1357 : * of the two relations.
1358 : *
1359 : * Partitionwise join is planned as follows (details: optimizer/README.)
1360 : *
1361 : * 1. Create the RelOptInfos for joins between matching partitions i.e
1362 : * child-joins and add paths to them.
1363 : *
1364 : * 2. Construct Append or MergeAppend paths across the set of child joins.
1365 : * This second phase is implemented by generate_partitionwise_join_paths().
1366 : *
1367 : * The RelOptInfo, SpecialJoinInfo and restrictlist for each child join are
1368 : * obtained by translating the respective parent join structures.
1369 : */
1370 : static void
1878 peter_e 1371 GIC 116199 : try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
1372 : RelOptInfo *joinrel, SpecialJoinInfo *parent_sjinfo,
1373 : List *parent_restrictlist)
1374 : {
1539 efujita 1375 116199 : bool rel1_is_simple = IS_SIMPLE_REL(rel1);
1376 116199 : bool rel2_is_simple = IS_SIMPLE_REL(rel2);
1096 1377 116199 : List *parts1 = NIL;
1378 116199 : List *parts2 = NIL;
1379 116199 : ListCell *lcr1 = NULL;
1380 116199 : ListCell *lcr2 = NULL;
1381 : int cnt_parts;
1382 :
1383 : /* Guard against stack overflow due to overly deep partition hierarchy. */
2011 rhaas 1384 CBC 116199 : check_stack_depth();
1385 :
1386 : /* Nothing to do, if the join relation is not partitioned. */
1096 efujita 1387 GIC 116199 : if (joinrel->part_scheme == NULL || joinrel->nparts == 0)
2011 rhaas 1388 CBC 115298 : return;
2011 rhaas 1389 ECB :
1682 efujita 1390 : /* The join relation should have consider_partitionwise_join set. */
1682 efujita 1391 CBC 985 : Assert(joinrel->consider_partitionwise_join);
1682 efujita 1392 ECB :
2011 rhaas 1393 : /*
1394 : * We can not perform partitionwise join if either of the joining
1395 : * relations is not partitioned.
1396 : */
1096 efujita 1397 CBC 985 : if (!IS_PARTITIONED_REL(rel1) || !IS_PARTITIONED_REL(rel2))
1096 efujita 1398 GIC 24 : return;
1399 :
2011 rhaas 1400 CBC 961 : Assert(REL_HAS_ALL_PART_PROPS(rel1) && REL_HAS_ALL_PART_PROPS(rel2));
2011 rhaas 1401 ECB :
1402 : /* The joining relations should have consider_partitionwise_join set. */
1682 efujita 1403 GIC 961 : Assert(rel1->consider_partitionwise_join &&
1682 efujita 1404 ECB : rel2->consider_partitionwise_join);
1405 :
1406 : /*
1407 : * The partition scheme of the join relation should match that of the
1408 : * joining relations.
1409 : */
2011 rhaas 1410 CBC 961 : Assert(joinrel->part_scheme == rel1->part_scheme &&
2011 rhaas 1411 ECB : joinrel->part_scheme == rel2->part_scheme);
1412 :
1096 efujita 1413 CBC 961 : Assert(!(joinrel->partbounds_merged && (joinrel->nparts <= 0)));
1414 :
1096 efujita 1415 GIC 961 : compute_partition_bounds(root, rel1, rel2, joinrel, parent_sjinfo,
1096 efujita 1416 ECB : &parts1, &parts2);
1417 :
1096 efujita 1418 GIC 961 : if (joinrel->partbounds_merged)
1419 : {
1420 384 : lcr1 = list_head(parts1);
1421 384 : lcr2 = list_head(parts2);
1422 : }
2011 rhaas 1423 ECB :
1424 : /*
1425 : * Create child-join relations for this partitioned join, if those don't
1426 : * exist. Add paths to child-joins for a pair of child relations
1427 : * corresponding to the given pair of parent relations.
1428 : */
1096 efujita 1429 GIC 3355 : for (cnt_parts = 0; cnt_parts < joinrel->nparts; cnt_parts++)
1430 : {
1096 efujita 1431 ECB : RelOptInfo *child_rel1;
1432 : RelOptInfo *child_rel2;
1433 : bool rel1_empty;
1434 : bool rel2_empty;
1435 : SpecialJoinInfo *child_sjinfo;
1436 : List *child_restrictlist;
1437 : RelOptInfo *child_joinrel;
1438 : Relids child_joinrelids;
1439 : AppendRelInfo **appinfos;
1440 : int nappinfos;
1441 :
1096 efujita 1442 CBC 2454 : if (joinrel->partbounds_merged)
1443 : {
1096 efujita 1444 GIC 1005 : child_rel1 = lfirst_node(RelOptInfo, lcr1);
1445 1005 : child_rel2 = lfirst_node(RelOptInfo, lcr2);
1446 1005 : lcr1 = lnext(parts1, lcr1);
1447 1005 : lcr2 = lnext(parts2, lcr2);
1448 : }
1449 : else
1450 : {
1451 1449 : child_rel1 = rel1->part_rels[cnt_parts];
1452 1449 : child_rel2 = rel2->part_rels[cnt_parts];
1453 : }
1454 :
1096 efujita 1455 CBC 2454 : rel1_empty = (child_rel1 == NULL || IS_DUMMY_REL(child_rel1));
1096 efujita 1456 GIC 2454 : rel2_empty = (child_rel2 == NULL || IS_DUMMY_REL(child_rel2));
1096 efujita 1457 ECB :
1539 1458 : /*
1471 tgl 1459 : * Check for cases where we can prove that this segment of the join
1460 : * returns no rows, due to one or both inputs being empty (including
1461 : * inputs that have been pruned away entirely). If so just ignore it.
1462 : * These rules are equivalent to populate_joinrel_with_paths's rules
1463 : * for dummy input relations.
1464 : */
1471 tgl 1465 CBC 2454 : switch (parent_sjinfo->jointype)
1466 : {
1471 tgl 1467 GIC 1123 : case JOIN_INNER:
1471 tgl 1468 ECB : case JOIN_SEMI:
1471 tgl 1469 CBC 1123 : if (rel1_empty || rel2_empty)
1471 tgl 1470 GIC 26 : continue; /* ignore this join segment */
1471 1111 : break;
1472 970 : case JOIN_LEFT:
1473 : case JOIN_ANTI:
1474 970 : if (rel1_empty)
1475 14 : continue; /* ignore this join segment */
1476 956 : break;
1477 361 : case JOIN_FULL:
1471 tgl 1478 CBC 361 : if (rel1_empty && rel2_empty)
1471 tgl 1479 UIC 0 : continue; /* ignore this join segment */
1471 tgl 1480 CBC 361 : break;
1471 tgl 1481 UIC 0 : default:
1471 tgl 1482 ECB : /* other values not expected here */
1471 tgl 1483 LBC 0 : elog(ERROR, "unrecognized join type: %d",
1471 tgl 1484 ECB : (int) parent_sjinfo->jointype);
1485 : break;
1486 : }
1487 :
1488 : /*
1489 : * If a child has been pruned entirely then we can't generate paths
1490 : * for it, so we have to reject partitionwise joining unless we were
1491 : * able to eliminate this partition above.
1471 tgl 1492 EUB : */
1471 tgl 1493 CBC 2428 : if (child_rel1 == NULL || child_rel2 == NULL)
1471 tgl 1494 EUB : {
1495 : /*
1496 : * Mark the joinrel as unpartitioned so that later functions treat
1497 : * it correctly.
1498 : */
1471 tgl 1499 GIC 60 : joinrel->nparts = 0;
1500 60 : return;
1501 : }
1502 :
1503 : /*
1504 : * If a leaf relation has consider_partitionwise_join=false, it means
1505 : * that it's a dummy relation for which we skipped setting up tlist
1471 tgl 1506 ECB : * expressions and adding EC members in set_append_rel_size(), so
1507 : * again we have to fail here.
1508 : */
1539 efujita 1509 GIC 2368 : if (rel1_is_simple && !child_rel1->consider_partitionwise_join)
1510 : {
1539 efujita 1511 UIC 0 : Assert(child_rel1->reloptkind == RELOPT_OTHER_MEMBER_REL);
1539 efujita 1512 LBC 0 : Assert(IS_DUMMY_REL(child_rel1));
1471 tgl 1513 0 : joinrel->nparts = 0;
1471 tgl 1514 UIC 0 : return;
1515 : }
1539 efujita 1516 GIC 2368 : if (rel2_is_simple && !child_rel2->consider_partitionwise_join)
1517 : {
1539 efujita 1518 UIC 0 : Assert(child_rel2->reloptkind == RELOPT_OTHER_MEMBER_REL);
1519 0 : Assert(IS_DUMMY_REL(child_rel2));
1471 tgl 1520 0 : joinrel->nparts = 0;
1521 0 : return;
1539 efujita 1522 ECB : }
1523 :
2011 rhaas 1524 EUB : /* We should never try to join two overlapping sets of rels. */
2011 rhaas 1525 GBC 2368 : Assert(!bms_overlap(child_rel1->relids, child_rel2->relids));
1526 :
2011 rhaas 1527 ECB : /*
1528 : * Construct SpecialJoinInfo from parent join relations's
2011 rhaas 1529 EUB : * SpecialJoinInfo.
1530 : */
2011 rhaas 1531 GBC 2368 : child_sjinfo = build_child_join_sjinfo(root, parent_sjinfo,
2011 rhaas 1532 EUB : child_rel1->relids,
1533 : child_rel2->relids);
1534 :
1535 : /* Build correct join relids for child join */
69 tgl 1536 GNC 2368 : child_joinrelids = bms_union(child_rel1->relids, child_rel2->relids);
1537 2368 : if (child_sjinfo->ojrelid != 0)
1538 1116 : child_joinrelids = bms_add_member(child_joinrelids,
1539 1116 : child_sjinfo->ojrelid);
1540 :
1541 : /* Find the AppendRelInfo structures */
1542 2368 : appinfos = find_appinfos_by_relids(root, child_joinrelids, &nappinfos);
1543 :
1544 : /*
2011 rhaas 1545 ECB : * Construct restrictions applicable to the child join from those
1546 : * applicable to the parent join.
1547 : */
1548 : child_restrictlist =
2011 rhaas 1549 GIC 2368 : (List *) adjust_appendrel_attrs(root,
1550 : (Node *) parent_restrictlist,
2011 rhaas 1551 ECB : nappinfos, appinfos);
2011 rhaas 1552 GIC 2368 : pfree(appinfos);
1553 :
1554 2368 : child_joinrel = joinrel->part_rels[cnt_parts];
1555 2368 : if (!child_joinrel)
2011 rhaas 1556 ECB : {
2011 rhaas 1557 CBC 2150 : child_joinrel = build_child_join_rel(root, child_rel1, child_rel2,
2011 rhaas 1558 ECB : joinrel, child_restrictlist,
1559 : child_sjinfo);
2011 rhaas 1560 GIC 2150 : joinrel->part_rels[cnt_parts] = child_joinrel;
614 drowley 1561 CBC 2150 : joinrel->live_parts = bms_add_member(joinrel->live_parts, cnt_parts);
1096 efujita 1562 GIC 2150 : joinrel->all_partrels = bms_add_members(joinrel->all_partrels,
1563 2150 : child_joinrel->relids);
1564 : }
1565 :
2011 rhaas 1566 2368 : Assert(bms_equal(child_joinrel->relids, child_joinrelids));
1567 :
2011 rhaas 1568 CBC 2368 : populate_joinrel_with_paths(root, child_rel1, child_rel2,
1569 : child_joinrel, child_sjinfo,
1570 : child_restrictlist);
2011 rhaas 1571 ECB : }
1572 : }
1573 :
1544 alvherre 1574 : /*
1575 : * Construct the SpecialJoinInfo for a child-join by translating
1576 : * SpecialJoinInfo for the join between parents. left_relids and right_relids
1577 : * are the relids of left and right side of the join respectively.
1578 : */
1579 : static SpecialJoinInfo *
1544 alvherre 1580 CBC 2368 : build_child_join_sjinfo(PlannerInfo *root, SpecialJoinInfo *parent_sjinfo,
1544 alvherre 1581 ECB : Relids left_relids, Relids right_relids)
1582 : {
1544 alvherre 1583 GIC 2368 : SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo);
1584 : AppendRelInfo **left_appinfos;
1544 alvherre 1585 ECB : int left_nappinfos;
1586 : AppendRelInfo **right_appinfos;
1587 : int right_nappinfos;
1588 :
1544 alvherre 1589 GIC 2368 : memcpy(sjinfo, parent_sjinfo, sizeof(SpecialJoinInfo));
1590 2368 : left_appinfos = find_appinfos_by_relids(root, left_relids,
1591 : &left_nappinfos);
1592 2368 : right_appinfos = find_appinfos_by_relids(root, right_relids,
1593 : &right_nappinfos);
1594 :
1595 2368 : sjinfo->min_lefthand = adjust_child_relids(sjinfo->min_lefthand,
1596 : left_nappinfos, left_appinfos);
1597 2368 : sjinfo->min_righthand = adjust_child_relids(sjinfo->min_righthand,
1598 : right_nappinfos,
1544 alvherre 1599 ECB : right_appinfos);
1544 alvherre 1600 GIC 2368 : sjinfo->syn_lefthand = adjust_child_relids(sjinfo->syn_lefthand,
1601 : left_nappinfos, left_appinfos);
1544 alvherre 1602 CBC 2368 : sjinfo->syn_righthand = adjust_child_relids(sjinfo->syn_righthand,
1603 : right_nappinfos,
1604 : right_appinfos);
1605 : /* outer-join relids need no adjustment */
1544 alvherre 1606 GIC 4736 : sjinfo->semi_rhs_exprs = (List *) adjust_appendrel_attrs(root,
1607 2368 : (Node *) sjinfo->semi_rhs_exprs,
1608 : right_nappinfos,
1544 alvherre 1609 ECB : right_appinfos);
1610 :
1544 alvherre 1611 GIC 2368 : pfree(left_appinfos);
1544 alvherre 1612 CBC 2368 : pfree(right_appinfos);
1613 :
1544 alvherre 1614 GIC 2368 : return sjinfo;
1544 alvherre 1615 ECB : }
1616 :
1096 efujita 1617 : /*
1618 : * compute_partition_bounds
1619 : * Compute the partition bounds for a join rel from those for inputs
1620 : */
1621 : static void
1096 efujita 1622 CBC 961 : compute_partition_bounds(PlannerInfo *root, RelOptInfo *rel1,
1623 : RelOptInfo *rel2, RelOptInfo *joinrel,
1624 : SpecialJoinInfo *parent_sjinfo,
1625 : List **parts1, List **parts2)
1096 efujita 1626 ECB : {
1627 : /*
1628 : * If we don't have the partition bounds for the join rel yet, try to
1629 : * compute those along with pairs of partitions to be joined.
1630 : */
1096 efujita 1631 CBC 961 : if (joinrel->nparts == -1)
1096 efujita 1632 ECB : {
1096 efujita 1633 GIC 885 : PartitionScheme part_scheme = joinrel->part_scheme;
1096 efujita 1634 CBC 885 : PartitionBoundInfo boundinfo = NULL;
1096 efujita 1635 GIC 885 : int nparts = 0;
1636 :
1637 885 : Assert(joinrel->boundinfo == NULL);
1638 885 : Assert(joinrel->part_rels == NULL);
1639 :
1640 : /*
1641 : * See if the partition bounds for inputs are exactly the same, in
549 efujita 1642 ECB : * which case we don't need to work hard: the join rel will have the
1643 : * same partition bounds as inputs, and the partitions with the same
1644 : * cardinal positions will form the pairs.
1645 : *
1646 : * Note: even in cases where one or both inputs have merged bounds, it
1647 : * would be possible for both the bounds to be exactly the same, but
1648 : * it seems unlikely to be worth the cycles to check.
1649 : */
1096 efujita 1650 GIC 885 : if (!rel1->partbounds_merged &&
1096 efujita 1651 CBC 855 : !rel2->partbounds_merged &&
1096 efujita 1652 GIC 1581 : rel1->nparts == rel2->nparts &&
1096 efujita 1653 CBC 726 : partition_bounds_equal(part_scheme->partnatts,
1096 efujita 1654 ECB : part_scheme->parttyplen,
1655 : part_scheme->parttypbyval,
1656 : rel1->boundinfo, rel2->boundinfo))
1657 : {
1096 efujita 1658 CBC 462 : boundinfo = rel1->boundinfo;
1096 efujita 1659 GIC 462 : nparts = rel1->nparts;
1660 : }
1661 : else
1662 : {
1663 : /* Try merging the partition bounds for inputs. */
1664 423 : boundinfo = partition_bounds_merge(part_scheme->partnatts,
1665 423 : part_scheme->partsupfunc,
1666 : part_scheme->partcollation,
1667 : rel1, rel2,
1668 : parent_sjinfo->jointype,
1669 : parts1, parts2);
1096 efujita 1670 CBC 423 : if (boundinfo == NULL)
1096 efujita 1671 ECB : {
1096 efujita 1672 CBC 57 : joinrel->nparts = 0;
1673 57 : return;
1674 : }
1096 efujita 1675 GIC 366 : nparts = list_length(*parts1);
1676 366 : joinrel->partbounds_merged = true;
1677 : }
1096 efujita 1678 ECB :
1096 efujita 1679 CBC 828 : Assert(nparts > 0);
1096 efujita 1680 GIC 828 : joinrel->boundinfo = boundinfo;
1681 828 : joinrel->nparts = nparts;
1682 828 : joinrel->part_rels =
1683 828 : (RelOptInfo **) palloc0(sizeof(RelOptInfo *) * nparts);
1096 efujita 1684 ECB : }
1685 : else
1686 : {
1096 efujita 1687 GIC 76 : Assert(joinrel->nparts > 0);
1688 76 : Assert(joinrel->boundinfo);
1689 76 : Assert(joinrel->part_rels);
1096 efujita 1690 ECB :
1691 : /*
1692 : * If the join rel's partbounds_merged flag is true, it means inputs
1693 : * are not guaranteed to have the same partition bounds, therefore we
1694 : * can't assume that the partitions at the same cardinal positions
1060 tgl 1695 : * form the pairs; let get_matching_part_pairs() generate the pairs.
1096 efujita 1696 : * Otherwise, nothing to do since we can assume that.
1697 : */
1096 efujita 1698 GIC 76 : if (joinrel->partbounds_merged)
1096 efujita 1699 ECB : {
1096 efujita 1700 CBC 18 : get_matching_part_pairs(root, joinrel, rel1, rel2,
1096 efujita 1701 ECB : parts1, parts2);
1096 efujita 1702 CBC 18 : Assert(list_length(*parts1) == joinrel->nparts);
1703 18 : Assert(list_length(*parts2) == joinrel->nparts);
1704 : }
1705 : }
1706 : }
1096 efujita 1707 ECB :
1708 : /*
1709 : * get_matching_part_pairs
1710 : * Generate pairs of partitions to be joined from inputs
1711 : */
1712 : static void
1096 efujita 1713 GIC 18 : get_matching_part_pairs(PlannerInfo *root, RelOptInfo *joinrel,
1714 : RelOptInfo *rel1, RelOptInfo *rel2,
1715 : List **parts1, List **parts2)
1716 : {
1717 18 : bool rel1_is_simple = IS_SIMPLE_REL(rel1);
1096 efujita 1718 CBC 18 : bool rel2_is_simple = IS_SIMPLE_REL(rel2);
1719 : int cnt_parts;
1096 efujita 1720 ECB :
1096 efujita 1721 GIC 18 : *parts1 = NIL;
1096 efujita 1722 CBC 18 : *parts2 = NIL;
1096 efujita 1723 ECB :
1096 efujita 1724 GIC 66 : for (cnt_parts = 0; cnt_parts < joinrel->nparts; cnt_parts++)
1725 : {
1726 48 : RelOptInfo *child_joinrel = joinrel->part_rels[cnt_parts];
1727 : RelOptInfo *child_rel1;
1728 : RelOptInfo *child_rel2;
1729 : Relids child_relids1;
1730 : Relids child_relids2;
1731 :
1732 : /*
1096 efujita 1733 ECB : * If this segment of the join is empty, it means that this segment
1734 : * was ignored when previously creating child-join paths for it in
1735 : * try_partitionwise_join() as it would not contribute to the join
1736 : * result, due to one or both inputs being empty; add NULL to each of
1737 : * the given lists so that this segment will be ignored again in that
1738 : * function.
1739 : */
1096 efujita 1740 GIC 48 : if (!child_joinrel)
1096 efujita 1741 ECB : {
1096 efujita 1742 LBC 0 : *parts1 = lappend(*parts1, NULL);
1096 efujita 1743 UIC 0 : *parts2 = lappend(*parts2, NULL);
1096 efujita 1744 LBC 0 : continue;
1745 : }
1096 efujita 1746 ECB :
1747 : /*
1748 : * Get a relids set of partition(s) involved in this join segment that
1749 : * are from the rel1 side.
1750 : */
1096 efujita 1751 GIC 48 : child_relids1 = bms_intersect(child_joinrel->relids,
1752 48 : rel1->all_partrels);
1753 48 : Assert(bms_num_members(child_relids1) == bms_num_members(rel1->relids));
1754 :
1755 : /*
1756 : * Get a child rel for rel1 with the relids. Note that we should have
1757 : * the child rel even if rel1 is a join rel, because in that case the
1758 : * partitions specified in the relids would have matching/overlapping
1759 : * boundaries, so the specified partitions should be considered as
1060 tgl 1760 ECB : * ones to be joined when planning partitionwise joins of rel1,
1761 : * meaning that the child rel would have been built by the time we get
1060 tgl 1762 EUB : * here.
1096 efujita 1763 : */
1096 efujita 1764 GBC 48 : if (rel1_is_simple)
1765 : {
1096 efujita 1766 UIC 0 : int varno = bms_singleton_member(child_relids1);
1767 :
1768 0 : child_rel1 = find_base_rel(root, varno);
1769 : }
1770 : else
1096 efujita 1771 CBC 48 : child_rel1 = find_join_rel(root, child_relids1);
1772 48 : Assert(child_rel1);
1096 efujita 1773 ECB :
1774 : /*
1775 : * Get a relids set of partition(s) involved in this join segment that
1776 : * are from the rel2 side.
1777 : */
1096 efujita 1778 GIC 48 : child_relids2 = bms_intersect(child_joinrel->relids,
1779 48 : rel2->all_partrels);
1780 48 : Assert(bms_num_members(child_relids2) == bms_num_members(rel2->relids));
1781 :
1782 : /*
1783 : * Get a child rel for rel2 with the relids. See above comments.
1096 efujita 1784 ECB : */
1096 efujita 1785 GIC 48 : if (rel2_is_simple)
1096 efujita 1786 EUB : {
1096 efujita 1787 GIC 48 : int varno = bms_singleton_member(child_relids2);
1096 efujita 1788 EUB :
1096 efujita 1789 GIC 48 : child_rel2 = find_base_rel(root, varno);
1790 : }
1096 efujita 1791 ECB : else
1096 efujita 1792 LBC 0 : child_rel2 = find_join_rel(root, child_relids2);
1096 efujita 1793 GIC 48 : Assert(child_rel2);
1794 :
1795 : /*
1796 : * The join of rel1 and rel2 is legal, so is the join of the child
1797 : * rels obtained above; add them to the given lists as a join pair
1096 efujita 1798 ECB : * producing this join segment.
1799 : */
1096 efujita 1800 CBC 48 : *parts1 = lappend(*parts1, child_rel1);
1096 efujita 1801 GIC 48 : *parts2 = lappend(*parts2, child_rel2);
1802 : }
1803 18 : }
|
