Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * joinrels.c
4 : * Routines to determine which relations should be joined
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/path/joinrels.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 : #include "utils/memutils.h"
21 :
22 :
23 : static void make_rels_by_clause_joins(PlannerInfo *root,
24 : RelOptInfo *old_rel,
25 : ListCell *other_rels);
26 : static void make_rels_by_clauseless_joins(PlannerInfo *root,
27 : RelOptInfo *old_rel,
28 : ListCell *other_rels);
29 : static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel);
30 : static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel);
31 : static bool is_dummy_rel(RelOptInfo *rel);
32 : static void mark_dummy_rel(RelOptInfo *rel);
33 : static bool restriction_is_constant_false(List *restrictlist,
34 : bool only_pushed_down);
35 : static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
36 : RelOptInfo *rel2, RelOptInfo *joinrel,
37 : SpecialJoinInfo *sjinfo, List *restrictlist);
38 :
39 :
40 : /*
41 : * join_search_one_level
42 : * Consider ways to produce join relations containing exactly 'level'
43 : * jointree items. (This is one step of the dynamic-programming method
44 : * embodied in standard_join_search.) Join rel nodes for each feasible
45 : * combination of lower-level rels are created and returned in a list.
46 : * Implementation paths are created for each such joinrel, too.
47 : *
48 : * level: level of rels we want to make this time
49 : * root->join_rel_level[j], 1 <= j < level, is a list of rels containing j items
50 : *
51 : * The result is returned in root->join_rel_level[level].
52 : */
53 : void
54 3718 : join_search_one_level(PlannerInfo *root, int level)
55 : {
56 3718 : List **joinrels = root->join_rel_level;
57 : ListCell *r;
58 : int k;
59 :
60 3718 : Assert(joinrels[level] == NIL);
61 :
62 : /* Set join_cur_level so that new joinrels are added to proper list */
63 3718 : root->join_cur_level = level;
64 :
65 : /*
66 : * First, consider left-sided and right-sided plans, in which rels of
67 : * exactly level-1 member relations are joined against initial relations.
68 : * We prefer to join using join clauses, but if we find a rel of level-1
69 : * members that has no join clauses, we will generate Cartesian-product
70 : * joins against all initial rels not already contained in it.
71 : */
72 12271 : foreach(r, joinrels[level - 1])
73 : {
74 8553 : RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
75 :
76 9518 : if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
77 965 : has_join_restriction(root, old_rel))
78 7829 : {
79 : /*
80 : * There are join clauses or join order restrictions relevant to
81 : * this rel, so consider joins between this rel and (only) those
82 : * initial rels it is linked to by a clause or restriction.
83 : *
84 : * At level 2 this condition is symmetric, so there is no need to
85 : * look at initial rels before this one in the list; we already
86 : * considered such joins when we were at the earlier rel. (The
87 : * mirror-image joins are handled automatically by make_join_rel.)
88 : * In later passes (level > 2), we join rels of the previous level
89 : * to each initial rel they don't already include but have a join
90 : * clause or restriction with.
91 : */
92 : ListCell *other_rels;
93 :
94 7829 : if (level == 2) /* consider remaining initial rels */
95 6119 : other_rels = lnext(r);
96 : else /* consider all initial rels */
97 1710 : other_rels = list_head(joinrels[1]);
98 :
99 7829 : make_rels_by_clause_joins(root,
100 : old_rel,
101 : other_rels);
102 : }
103 : else
104 : {
105 : /*
106 : * Oops, we have a relation that is not joined to any other
107 : * relation, either directly or by join-order restrictions.
108 : * Cartesian product time.
109 : *
110 : * We consider a cartesian product with each not-already-included
111 : * initial rel, whether it has other join clauses or not. At
112 : * level 2, if there are two or more clauseless initial rels, we
113 : * will redundantly consider joining them in both directions; but
114 : * such cases aren't common enough to justify adding complexity to
115 : * avoid the duplicated effort.
116 : */
117 724 : make_rels_by_clauseless_joins(root,
118 : old_rel,
119 724 : list_head(joinrels[1]));
120 : }
121 : }
122 :
123 : /*
124 : * Now, consider "bushy plans" in which relations of k initial rels are
125 : * joined to relations of level-k initial rels, for 2 <= k <= level-2.
126 : *
127 : * We only consider bushy-plan joins for pairs of rels where there is a
128 : * suitable join clause (or join order restriction), in order to avoid
129 : * unreasonable growth of planning time.
130 : */
131 4058 : for (k = 2;; k++)
132 : {
133 4058 : int other_level = level - k;
134 :
135 : /*
136 : * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
137 : * need to go as far as the halfway point.
138 : */
139 4058 : if (k > other_level)
140 3718 : break;
141 :
142 1661 : foreach(r, joinrels[k])
143 : {
144 1321 : RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
145 : ListCell *other_rels;
146 : ListCell *r2;
147 :
148 : /*
149 : * We can ignore relations without join clauses here, unless they
150 : * participate in join-order restrictions --- then we might have
151 : * to force a bushy join plan.
152 : */
153 1340 : if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
154 19 : !has_join_restriction(root, old_rel))
155 11 : continue;
156 :
157 1310 : if (k == other_level)
158 741 : other_rels = lnext(r); /* only consider remaining rels */
159 : else
160 569 : other_rels = list_head(joinrels[other_level]);
161 :
162 5162 : for_each_cell(r2, other_rels)
163 : {
164 3852 : RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
165 :
166 3852 : if (!bms_overlap(old_rel->relids, new_rel->relids))
167 : {
168 : /*
169 : * OK, we can build a rel of the right level from this
170 : * pair of rels. Do so if there is at least one relevant
171 : * join clause or join order restriction.
172 : */
173 930 : if (have_relevant_joinclause(root, old_rel, new_rel) ||
174 145 : have_join_order_restriction(root, old_rel, new_rel))
175 : {
176 644 : (void) make_join_rel(root, old_rel, new_rel);
177 : }
178 : }
179 : }
180 : }
181 340 : }
182 :
183 : /*----------
184 : * Last-ditch effort: if we failed to find any usable joins so far, force
185 : * a set of cartesian-product joins to be generated. This handles the
186 : * special case where all the available rels have join clauses but we
187 : * cannot use any of those clauses yet. This can only happen when we are
188 : * considering a join sub-problem (a sub-joinlist) and all the rels in the
189 : * sub-problem have only join clauses with rels outside the sub-problem.
190 : * An example is
191 : *
192 : * SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
193 : * WHERE a.w = c.x and b.y = d.z;
194 : *
195 : * If the "a INNER JOIN b" sub-problem does not get flattened into the
196 : * upper level, we must be willing to make a cartesian join of a and b;
197 : * but the code above will not have done so, because it thought that both
198 : * a and b have joinclauses. We consider only left-sided and right-sided
199 : * cartesian joins in this case (no bushy).
200 : *----------
201 : */
202 3718 : if (joinrels[level] == NIL)
203 : {
204 : /*
205 : * This loop is just like the first one, except we always call
206 : * make_rels_by_clauseless_joins().
207 : */
208 9 : foreach(r, joinrels[level - 1])
209 : {
210 6 : RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
211 :
212 6 : make_rels_by_clauseless_joins(root,
213 : old_rel,
214 6 : list_head(joinrels[1]));
215 : }
216 :
217 : /*----------
218 : * When special joins are involved, there may be no legal way
219 : * to make an N-way join for some values of N. For example consider
220 : *
221 : * SELECT ... FROM t1 WHERE
222 : * x IN (SELECT ... FROM t2,t3 WHERE ...) AND
223 : * y IN (SELECT ... FROM t4,t5 WHERE ...)
224 : *
225 : * We will flatten this query to a 5-way join problem, but there are
226 : * no 4-way joins that join_is_legal() will consider legal. We have
227 : * to accept failure at level 4 and go on to discover a workable
228 : * bushy plan at level 5.
229 : *
230 : * However, if there are no special joins and no lateral references
231 : * then join_is_legal() should never fail, and so the following sanity
232 : * check is useful.
233 : *----------
234 : */
235 4 : if (joinrels[level] == NIL &&
236 1 : root->join_info_list == NIL &&
237 0 : !root->hasLateralRTEs)
238 0 : elog(ERROR, "failed to build any %d-way joins", level);
239 : }
240 3718 : }
241 :
242 : /*
243 : * make_rels_by_clause_joins
244 : * Build joins between the given relation 'old_rel' and other relations
245 : * that participate in join clauses that 'old_rel' also participates in
246 : * (or participate in join-order restrictions with it).
247 : * The join rels are returned in root->join_rel_level[join_cur_level].
248 : *
249 : * Note: at levels above 2 we will generate the same joined relation in
250 : * multiple ways --- for example (a join b) join c is the same RelOptInfo as
251 : * (b join c) join a, though the second case will add a different set of Paths
252 : * to it. This is the reason for using the join_rel_level mechanism, which
253 : * automatically ensures that each new joinrel is only added to the list once.
254 : *
255 : * 'old_rel' is the relation entry for the relation to be joined
256 : * 'other_rels': the first cell in a linked list containing the other
257 : * rels to be considered for joining
258 : *
259 : * Currently, this is only used with initial rels in other_rels, but it
260 : * will work for joining to joinrels too.
261 : */
262 : static void
263 7829 : make_rels_by_clause_joins(PlannerInfo *root,
264 : RelOptInfo *old_rel,
265 : ListCell *other_rels)
266 : {
267 : ListCell *l;
268 :
269 20570 : for_each_cell(l, other_rels)
270 : {
271 12741 : RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
272 :
273 20728 : if (!bms_overlap(old_rel->relids, other_rel->relids) &&
274 9843 : (have_relevant_joinclause(root, old_rel, other_rel) ||
275 1856 : have_join_order_restriction(root, old_rel, other_rel)))
276 : {
277 6345 : (void) make_join_rel(root, old_rel, other_rel);
278 : }
279 : }
280 7829 : }
281 :
282 : /*
283 : * make_rels_by_clauseless_joins
284 : * Given a relation 'old_rel' and a list of other relations
285 : * 'other_rels', create a join relation between 'old_rel' and each
286 : * member of 'other_rels' that isn't already included in 'old_rel'.
287 : * The join rels are returned in root->join_rel_level[join_cur_level].
288 : *
289 : * 'old_rel' is the relation entry for the relation to be joined
290 : * 'other_rels': the first cell of a linked list containing the
291 : * other rels to be considered for joining
292 : *
293 : * Currently, this is only used with initial rels in other_rels, but it would
294 : * work for joining to joinrels too.
295 : */
296 : static void
297 730 : make_rels_by_clauseless_joins(PlannerInfo *root,
298 : RelOptInfo *old_rel,
299 : ListCell *other_rels)
300 : {
301 : ListCell *l;
302 :
303 2290 : for_each_cell(l, other_rels)
304 : {
305 1560 : RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
306 :
307 1560 : if (!bms_overlap(other_rel->relids, old_rel->relids))
308 : {
309 768 : (void) make_join_rel(root, old_rel, other_rel);
310 : }
311 : }
312 730 : }
313 :
314 :
315 : /*
316 : * join_is_legal
317 : * Determine whether a proposed join is legal given the query's
318 : * join order constraints; and if it is, determine the join type.
319 : *
320 : * Caller must supply not only the two rels, but the union of their relids.
321 : * (We could simplify the API by computing joinrelids locally, but this
322 : * would be redundant work in the normal path through make_join_rel.)
323 : *
324 : * On success, *sjinfo_p is set to NULL if this is to be a plain inner join,
325 : * else it's set to point to the associated SpecialJoinInfo node. Also,
326 : * *reversed_p is set TRUE if the given relations need to be swapped to
327 : * match the SpecialJoinInfo node.
328 : */
329 : static bool
330 8583 : join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
331 : Relids joinrelids,
332 : SpecialJoinInfo **sjinfo_p, bool *reversed_p)
333 : {
334 : SpecialJoinInfo *match_sjinfo;
335 : bool reversed;
336 : bool unique_ified;
337 : bool must_be_leftjoin;
338 : ListCell *l;
339 :
340 : /*
341 : * Ensure output params are set on failure return. This is just to
342 : * suppress uninitialized-variable warnings from overly anal compilers.
343 : */
344 8583 : *sjinfo_p = NULL;
345 8583 : *reversed_p = false;
346 :
347 : /*
348 : * If we have any special joins, the proposed join might be illegal; and
349 : * in any case we have to determine its join type. Scan the join info
350 : * list for matches and conflicts.
351 : */
352 8583 : match_sjinfo = NULL;
353 8583 : reversed = false;
354 8583 : unique_ified = false;
355 8583 : must_be_leftjoin = false;
356 :
357 16164 : foreach(l, root->join_info_list)
358 : {
359 8547 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
360 :
361 : /*
362 : * This special join is not relevant unless its RHS overlaps the
363 : * proposed join. (Check this first as a fast path for dismissing
364 : * most irrelevant SJs quickly.)
365 : */
366 8547 : if (!bms_overlap(sjinfo->min_righthand, joinrelids))
367 3485 : continue;
368 :
369 : /*
370 : * Also, not relevant if proposed join is fully contained within RHS
371 : * (ie, we're still building up the RHS).
372 : */
373 5062 : if (bms_is_subset(joinrelids, sjinfo->min_righthand))
374 437 : continue;
375 :
376 : /*
377 : * Also, not relevant if SJ is already done within either input.
378 : */
379 8136 : if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
380 3511 : bms_is_subset(sjinfo->min_righthand, rel1->relids))
381 1216 : continue;
382 4081 : if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
383 672 : bms_is_subset(sjinfo->min_righthand, rel2->relids))
384 246 : continue;
385 :
386 : /*
387 : * If it's a semijoin and we already joined the RHS to any other rels
388 : * within either input, then we must have unique-ified the RHS at that
389 : * point (see below). Therefore the semijoin is no longer relevant in
390 : * this join path.
391 : */
392 3163 : if (sjinfo->jointype == JOIN_SEMI)
393 : {
394 876 : if (bms_is_subset(sjinfo->syn_righthand, rel1->relids) &&
395 154 : !bms_equal(sjinfo->syn_righthand, rel1->relids))
396 3 : continue;
397 994 : if (bms_is_subset(sjinfo->syn_righthand, rel2->relids) &&
398 275 : !bms_equal(sjinfo->syn_righthand, rel2->relids))
399 1 : continue;
400 : }
401 :
402 : /*
403 : * If one input contains min_lefthand and the other contains
404 : * min_righthand, then we can perform the SJ at this join.
405 : *
406 : * Reject if we get matches to more than one SJ; that implies we're
407 : * considering something that's not really valid.
408 : */
409 5453 : if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
410 2294 : bms_is_subset(sjinfo->min_righthand, rel2->relids))
411 : {
412 1593 : if (match_sjinfo)
413 0 : return false; /* invalid join path */
414 1593 : match_sjinfo = sjinfo;
415 1593 : reversed = false;
416 : }
417 1991 : else if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
418 425 : bms_is_subset(sjinfo->min_righthand, rel1->relids))
419 : {
420 315 : if (match_sjinfo)
421 0 : return false; /* invalid join path */
422 315 : match_sjinfo = sjinfo;
423 315 : reversed = true;
424 : }
425 1648 : else if (sjinfo->jointype == JOIN_SEMI &&
426 450 : bms_equal(sjinfo->syn_righthand, rel2->relids) &&
427 53 : create_unique_path(root, rel2, rel2->cheapest_total_path,
428 : sjinfo) != NULL)
429 : {
430 : /*----------
431 : * For a semijoin, we can join the RHS to anything else by
432 : * unique-ifying the RHS (if the RHS can be unique-ified).
433 : * We will only get here if we have the full RHS but less
434 : * than min_lefthand on the LHS.
435 : *
436 : * The reason to consider such a join path is exemplified by
437 : * SELECT ... FROM a,b WHERE (a.x,b.y) IN (SELECT c1,c2 FROM c)
438 : * If we insist on doing this as a semijoin we will first have
439 : * to form the cartesian product of A*B. But if we unique-ify
440 : * C then the semijoin becomes a plain innerjoin and we can join
441 : * in any order, eg C to A and then to B. When C is much smaller
442 : * than A and B this can be a huge win. So we allow C to be
443 : * joined to just A or just B here, and then make_join_rel has
444 : * to handle the case properly.
445 : *
446 : * Note that actually we'll allow unique-ified C to be joined to
447 : * some other relation D here, too. That is legal, if usually not
448 : * very sane, and this routine is only concerned with legality not
449 : * with whether the join is good strategy.
450 : *----------
451 : */
452 52 : if (match_sjinfo)
453 20 : return false; /* invalid join path */
454 32 : match_sjinfo = sjinfo;
455 32 : reversed = false;
456 32 : unique_ified = true;
457 : }
458 1544 : else if (sjinfo->jointype == JOIN_SEMI &&
459 396 : bms_equal(sjinfo->syn_righthand, rel1->relids) &&
460 51 : create_unique_path(root, rel1, rel1->cheapest_total_path,
461 : sjinfo) != NULL)
462 : {
463 : /* Reversed semijoin case */
464 51 : if (match_sjinfo)
465 11 : return false; /* invalid join path */
466 40 : match_sjinfo = sjinfo;
467 40 : reversed = true;
468 40 : unique_ified = true;
469 : }
470 : else
471 : {
472 : /*
473 : * Otherwise, the proposed join overlaps the RHS but isn't a valid
474 : * implementation of this SJ. But don't panic quite yet: the RHS
475 : * violation might have occurred previously, in one or both input
476 : * relations, in which case we must have previously decided that
477 : * it was OK to commute some other SJ with this one. If we need
478 : * to perform this join to finish building up the RHS, rejecting
479 : * it could lead to not finding any plan at all. (This can occur
480 : * because of the heuristics elsewhere in this file that postpone
481 : * clauseless joins: we might not consider doing a clauseless join
482 : * within the RHS until after we've performed other, validly
483 : * commutable SJs with one or both sides of the clauseless join.)
484 : * This consideration boils down to the rule that if both inputs
485 : * overlap the RHS, we can allow the join --- they are either
486 : * fully within the RHS, or represent previously-allowed joins to
487 : * rels outside it.
488 : */
489 1437 : if (bms_overlap(rel1->relids, sjinfo->min_righthand) &&
490 289 : bms_overlap(rel2->relids, sjinfo->min_righthand))
491 20 : continue; /* assume valid previous violation of RHS */
492 :
493 : /*
494 : * The proposed join could still be legal, but only if we're
495 : * allowed to associate it into the RHS of this SJ. That means
496 : * this SJ must be a LEFT join (not SEMI or ANTI, and certainly
497 : * not FULL) and the proposed join must not overlap the LHS.
498 : */
499 1941 : if (sjinfo->jointype != JOIN_LEFT ||
500 813 : bms_overlap(joinrelids, sjinfo->min_lefthand))
501 935 : return false; /* invalid join path */
502 :
503 : /*
504 : * To be valid, the proposed join must be a LEFT join; otherwise
505 : * it can't associate into this SJ's RHS. But we may not yet have
506 : * found the SpecialJoinInfo matching the proposed join, so we
507 : * can't test that yet. Remember the requirement for later.
508 : */
509 193 : must_be_leftjoin = true;
510 : }
511 : }
512 :
513 : /*
514 : * Fail if violated any SJ's RHS and didn't match to a LEFT SJ: the
515 : * proposed join can't associate into an SJ's RHS.
516 : *
517 : * Also, fail if the proposed join's predicate isn't strict; we're
518 : * essentially checking to see if we can apply outer-join identity 3, and
519 : * that's a requirement. (This check may be redundant with checks in
520 : * make_outerjoininfo, but I'm not quite sure, and it's cheap to test.)
521 : */
522 7617 : if (must_be_leftjoin &&
523 33 : (match_sjinfo == NULL ||
524 66 : match_sjinfo->jointype != JOIN_LEFT ||
525 33 : !match_sjinfo->lhs_strict))
526 44 : return false; /* invalid join path */
527 :
528 : /*
529 : * We also have to check for constraints imposed by LATERAL references.
530 : */
531 7573 : if (root->hasLateralRTEs)
532 : {
533 : bool lateral_fwd;
534 : bool lateral_rev;
535 : Relids join_lateral_rels;
536 :
537 : /*
538 : * The proposed rels could each contain lateral references to the
539 : * other, in which case the join is impossible. If there are lateral
540 : * references in just one direction, then the join has to be done with
541 : * a nestloop with the lateral referencer on the inside. If the join
542 : * matches an SJ that cannot be implemented by such a nestloop, the
543 : * join is impossible.
544 : *
545 : * Also, if the lateral reference is only indirect, we should reject
546 : * the join; whatever rel(s) the reference chain goes through must be
547 : * joined to first.
548 : *
549 : * Another case that might keep us from building a valid plan is the
550 : * implementation restriction described by have_dangerous_phv().
551 : */
552 579 : lateral_fwd = bms_overlap(rel1->relids, rel2->lateral_relids);
553 579 : lateral_rev = bms_overlap(rel2->relids, rel1->lateral_relids);
554 579 : if (lateral_fwd && lateral_rev)
555 1 : return false; /* have lateral refs in both directions */
556 578 : if (lateral_fwd)
557 : {
558 : /* has to be implemented as nestloop with rel1 on left */
559 208 : if (match_sjinfo &&
560 13 : (reversed ||
561 11 : unique_ified ||
562 11 : match_sjinfo->jointype == JOIN_FULL))
563 2 : return false; /* not implementable as nestloop */
564 : /* check there is a direct reference from rel2 to rel1 */
565 206 : if (!bms_overlap(rel1->relids, rel2->direct_lateral_relids))
566 3 : return false; /* only indirect refs, so reject */
567 : /* check we won't have a dangerous PHV */
568 203 : if (have_dangerous_phv(root, rel1->relids, rel2->lateral_relids))
569 12 : return false; /* might be unable to handle required PHV */
570 : }
571 370 : else if (lateral_rev)
572 : {
573 : /* has to be implemented as nestloop with rel2 on left */
574 64 : if (match_sjinfo &&
575 2 : (!reversed ||
576 2 : unique_ified ||
577 2 : match_sjinfo->jointype == JOIN_FULL))
578 0 : return false; /* not implementable as nestloop */
579 : /* check there is a direct reference from rel1 to rel2 */
580 64 : if (!bms_overlap(rel2->relids, rel1->direct_lateral_relids))
581 0 : return false; /* only indirect refs, so reject */
582 : /* check we won't have a dangerous PHV */
583 64 : if (have_dangerous_phv(root, rel2->relids, rel1->lateral_relids))
584 14 : return false; /* might be unable to handle required PHV */
585 : }
586 :
587 : /*
588 : * LATERAL references could also cause problems later on if we accept
589 : * this join: if the join's minimum parameterization includes any rels
590 : * that would have to be on the inside of an outer join with this join
591 : * rel, then it's never going to be possible to build the complete
592 : * query using this join. We should reject this join not only because
593 : * it'll save work, but because if we don't, the clauseless-join
594 : * heuristics might think that legality of this join means that some
595 : * other join rel need not be formed, and that could lead to failure
596 : * to find any plan at all. We have to consider not only rels that
597 : * are directly on the inner side of an OJ with the joinrel, but also
598 : * ones that are indirectly so, so search to find all such rels.
599 : */
600 547 : join_lateral_rels = min_join_parameterization(root, joinrelids,
601 : rel1, rel2);
602 547 : if (join_lateral_rels)
603 : {
604 93 : Relids join_plus_rhs = bms_copy(joinrelids);
605 : bool more;
606 :
607 : do
608 : {
609 125 : more = false;
610 241 : foreach(l, root->join_info_list)
611 : {
612 116 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
613 :
614 224 : if (bms_overlap(sjinfo->min_lefthand, join_plus_rhs) &&
615 108 : !bms_is_subset(sjinfo->min_righthand, join_plus_rhs))
616 : {
617 47 : join_plus_rhs = bms_add_members(join_plus_rhs,
618 47 : sjinfo->min_righthand);
619 47 : more = true;
620 : }
621 : /* full joins constrain both sides symmetrically */
622 116 : if (sjinfo->jointype == JOIN_FULL &&
623 0 : bms_overlap(sjinfo->min_righthand, join_plus_rhs) &&
624 0 : !bms_is_subset(sjinfo->min_lefthand, join_plus_rhs))
625 : {
626 0 : join_plus_rhs = bms_add_members(join_plus_rhs,
627 0 : sjinfo->min_lefthand);
628 0 : more = true;
629 : }
630 : }
631 125 : } while (more);
632 93 : if (bms_overlap(join_plus_rhs, join_lateral_rels))
633 32 : return false; /* will not be able to join to some RHS rel */
634 : }
635 : }
636 :
637 : /* Otherwise, it's a valid join */
638 7509 : *sjinfo_p = match_sjinfo;
639 7509 : *reversed_p = reversed;
640 7509 : return true;
641 : }
642 :
643 :
644 : /*
645 : * make_join_rel
646 : * Find or create a join RelOptInfo that represents the join of
647 : * the two given rels, and add to it path information for paths
648 : * created with the two rels as outer and inner rel.
649 : * (The join rel may already contain paths generated from other
650 : * pairs of rels that add up to the same set of base rels.)
651 : *
652 : * NB: will return NULL if attempted join is not valid. This can happen
653 : * when working with outer joins, or with IN or EXISTS clauses that have been
654 : * turned into joins.
655 : */
656 : RelOptInfo *
657 8565 : make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
658 : {
659 : Relids joinrelids;
660 : SpecialJoinInfo *sjinfo;
661 : bool reversed;
662 : SpecialJoinInfo sjinfo_data;
663 : RelOptInfo *joinrel;
664 : List *restrictlist;
665 :
666 : /* We should never try to join two overlapping sets of rels. */
667 8565 : Assert(!bms_overlap(rel1->relids, rel2->relids));
668 :
669 : /* Construct Relids set that identifies the joinrel. */
670 8565 : joinrelids = bms_union(rel1->relids, rel2->relids);
671 :
672 : /* Check validity and determine join type. */
673 8565 : if (!join_is_legal(root, rel1, rel2, joinrelids,
674 : &sjinfo, &reversed))
675 : {
676 : /* invalid join path */
677 1064 : bms_free(joinrelids);
678 1064 : return NULL;
679 : }
680 :
681 : /* Swap rels if needed to match the join info. */
682 7501 : if (reversed)
683 : {
684 315 : RelOptInfo *trel = rel1;
685 :
686 315 : rel1 = rel2;
687 315 : rel2 = trel;
688 : }
689 :
690 : /*
691 : * If it's a plain inner join, then we won't have found anything in
692 : * join_info_list. Make up a SpecialJoinInfo so that selectivity
693 : * estimation functions will know what's being joined.
694 : */
695 7501 : if (sjinfo == NULL)
696 : {
697 5595 : sjinfo = &sjinfo_data;
698 5595 : sjinfo->type = T_SpecialJoinInfo;
699 5595 : sjinfo->min_lefthand = rel1->relids;
700 5595 : sjinfo->min_righthand = rel2->relids;
701 5595 : sjinfo->syn_lefthand = rel1->relids;
702 5595 : sjinfo->syn_righthand = rel2->relids;
703 5595 : sjinfo->jointype = JOIN_INNER;
704 : /* we don't bother trying to make the remaining fields valid */
705 5595 : sjinfo->lhs_strict = false;
706 5595 : sjinfo->delay_upper_joins = false;
707 5595 : sjinfo->semi_can_btree = false;
708 5595 : sjinfo->semi_can_hash = false;
709 5595 : sjinfo->semi_operators = NIL;
710 5595 : sjinfo->semi_rhs_exprs = NIL;
711 : }
712 :
713 : /*
714 : * Find or build the join RelOptInfo, and compute the restrictlist that
715 : * goes with this particular joining.
716 : */
717 7501 : joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
718 : &restrictlist);
719 :
720 : /*
721 : * If we've already proven this join is empty, we needn't consider any
722 : * more paths for it.
723 : */
724 7501 : if (is_dummy_rel(joinrel))
725 : {
726 0 : bms_free(joinrelids);
727 0 : return joinrel;
728 : }
729 :
730 : /* Add paths to the join relation. */
731 7501 : populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
732 : restrictlist);
733 :
734 7501 : bms_free(joinrelids);
735 :
736 7501 : return joinrel;
737 : }
738 :
739 : /*
740 : * populate_joinrel_with_paths
741 : * Add paths to the given joinrel for given pair of joining relations. The
742 : * SpecialJoinInfo provides details about the join and the restrictlist
743 : * contains the join clauses and the other clauses applicable for given pair
744 : * of the joining relations.
745 : */
746 : static void
747 7501 : populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
748 : RelOptInfo *rel2, RelOptInfo *joinrel,
749 : SpecialJoinInfo *sjinfo, List *restrictlist)
750 : {
751 : /*
752 : * Consider paths using each rel as both outer and inner. Depending on
753 : * the join type, a provably empty outer or inner rel might mean the join
754 : * is provably empty too; in which case throw away any previously computed
755 : * paths and mark the join as dummy. (We do it this way since it's
756 : * conceivable that dummy-ness of a multi-element join might only be
757 : * noticeable for certain construction paths.)
758 : *
759 : * Also, a provably constant-false join restriction typically means that
760 : * we can skip evaluating one or both sides of the join. We do this by
761 : * marking the appropriate rel as dummy. For outer joins, a
762 : * constant-false restriction that is pushed down still means the whole
763 : * join is dummy, while a non-pushed-down one means that no inner rows
764 : * will join so we can treat the inner rel as dummy.
765 : *
766 : * We need only consider the jointypes that appear in join_info_list, plus
767 : * JOIN_INNER.
768 : */
769 7501 : switch (sjinfo->jointype)
770 : {
771 : case JOIN_INNER:
772 11189 : if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
773 5594 : restriction_is_constant_false(restrictlist, false))
774 : {
775 3 : mark_dummy_rel(joinrel);
776 3 : break;
777 : }
778 5592 : add_paths_to_joinrel(root, joinrel, rel1, rel2,
779 : JOIN_INNER, sjinfo,
780 : restrictlist);
781 5592 : add_paths_to_joinrel(root, joinrel, rel2, rel1,
782 : JOIN_INNER, sjinfo,
783 : restrictlist);
784 5592 : break;
785 : case JOIN_LEFT:
786 2602 : if (is_dummy_rel(rel1) ||
787 1300 : restriction_is_constant_false(restrictlist, true))
788 : {
789 2 : mark_dummy_rel(joinrel);
790 2 : break;
791 : }
792 1300 : if (restriction_is_constant_false(restrictlist, false) &&
793 0 : bms_is_subset(rel2->relids, sjinfo->syn_righthand))
794 0 : mark_dummy_rel(rel2);
795 1300 : add_paths_to_joinrel(root, joinrel, rel1, rel2,
796 : JOIN_LEFT, sjinfo,
797 : restrictlist);
798 1300 : add_paths_to_joinrel(root, joinrel, rel2, rel1,
799 : JOIN_RIGHT, sjinfo,
800 : restrictlist);
801 1300 : break;
802 : case JOIN_FULL:
803 58 : if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) ||
804 29 : restriction_is_constant_false(restrictlist, true))
805 : {
806 0 : mark_dummy_rel(joinrel);
807 0 : break;
808 : }
809 29 : add_paths_to_joinrel(root, joinrel, rel1, rel2,
810 : JOIN_FULL, sjinfo,
811 : restrictlist);
812 29 : add_paths_to_joinrel(root, joinrel, rel2, rel1,
813 : JOIN_FULL, sjinfo,
814 : restrictlist);
815 :
816 : /*
817 : * If there are join quals that aren't mergeable or hashable, we
818 : * may not be able to build any valid plan. Complain here so that
819 : * we can give a somewhat-useful error message. (Since we have no
820 : * flexibility of planning for a full join, there's no chance of
821 : * succeeding later with another pair of input rels.)
822 : */
823 29 : if (joinrel->pathlist == NIL)
824 0 : ereport(ERROR,
825 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
826 : errmsg("FULL JOIN is only supported with merge-joinable or hash-joinable join conditions")));
827 29 : break;
828 : case JOIN_SEMI:
829 :
830 : /*
831 : * We might have a normal semijoin, or a case where we don't have
832 : * enough rels to do the semijoin but can unique-ify the RHS and
833 : * then do an innerjoin (see comments in join_is_legal). In the
834 : * latter case we can't apply JOIN_SEMI joining.
835 : */
836 645 : if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
837 321 : bms_is_subset(sjinfo->min_righthand, rel2->relids))
838 : {
839 641 : if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
840 320 : restriction_is_constant_false(restrictlist, false))
841 : {
842 2 : mark_dummy_rel(joinrel);
843 2 : break;
844 : }
845 319 : add_paths_to_joinrel(root, joinrel, rel1, rel2,
846 : JOIN_SEMI, sjinfo,
847 : restrictlist);
848 : }
849 :
850 : /*
851 : * If we know how to unique-ify the RHS and one input rel is
852 : * exactly the RHS (not a superset) we can consider unique-ifying
853 : * it and then doing a regular join. (The create_unique_path
854 : * check here is probably redundant with what join_is_legal did,
855 : * but if so the check is cheap because it's cached. So test
856 : * anyway to be sure.)
857 : */
858 644 : if (bms_equal(sjinfo->syn_righthand, rel2->relids) &&
859 322 : create_unique_path(root, rel2, rel2->cheapest_total_path,
860 : sjinfo) != NULL)
861 : {
862 630 : if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
863 315 : restriction_is_constant_false(restrictlist, false))
864 : {
865 0 : mark_dummy_rel(joinrel);
866 0 : break;
867 : }
868 315 : add_paths_to_joinrel(root, joinrel, rel1, rel2,
869 : JOIN_UNIQUE_INNER, sjinfo,
870 : restrictlist);
871 315 : add_paths_to_joinrel(root, joinrel, rel2, rel1,
872 : JOIN_UNIQUE_OUTER, sjinfo,
873 : restrictlist);
874 : }
875 322 : break;
876 : case JOIN_ANTI:
877 502 : if (is_dummy_rel(rel1) ||
878 251 : restriction_is_constant_false(restrictlist, true))
879 : {
880 0 : mark_dummy_rel(joinrel);
881 0 : break;
882 : }
883 251 : if (restriction_is_constant_false(restrictlist, false) &&
884 0 : bms_is_subset(rel2->relids, sjinfo->syn_righthand))
885 0 : mark_dummy_rel(rel2);
886 251 : add_paths_to_joinrel(root, joinrel, rel1, rel2,
887 : JOIN_ANTI, sjinfo,
888 : restrictlist);
889 251 : break;
890 : default:
891 : /* other values not expected here */
892 0 : elog(ERROR, "unrecognized join type: %d", (int) sjinfo->jointype);
893 : break;
894 : }
895 7501 : }
896 :
897 :
898 : /*
899 : * have_join_order_restriction
900 : * Detect whether the two relations should be joined to satisfy
901 : * a join-order restriction arising from special or lateral joins.
902 : *
903 : * In practice this is always used with have_relevant_joinclause(), and so
904 : * could be merged with that function, but it seems clearer to separate the
905 : * two concerns. We need this test because there are degenerate cases where
906 : * a clauseless join must be performed to satisfy join-order restrictions.
907 : * Also, if one rel has a lateral reference to the other, or both are needed
908 : * to compute some PHV, we should consider joining them even if the join would
909 : * be clauseless.
910 : *
911 : * Note: this is only a problem if one side of a degenerate outer join
912 : * contains multiple rels, or a clauseless join is required within an
913 : * IN/EXISTS RHS; else we will find a join path via the "last ditch" case in
914 : * join_search_one_level(). We could dispense with this test if we were
915 : * willing to try bushy plans in the "last ditch" case, but that seems much
916 : * less efficient.
917 : */
918 : bool
919 2309 : have_join_order_restriction(PlannerInfo *root,
920 : RelOptInfo *rel1, RelOptInfo *rel2)
921 : {
922 2309 : bool result = false;
923 : ListCell *l;
924 :
925 : /*
926 : * If either side has a direct lateral reference to the other, attempt the
927 : * join regardless of outer-join considerations.
928 : */
929 4449 : if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) ||
930 2140 : bms_overlap(rel2->relids, rel1->direct_lateral_relids))
931 197 : return true;
932 :
933 : /*
934 : * Likewise, if both rels are needed to compute some PlaceHolderVar,
935 : * attempt the join regardless of outer-join considerations. (This is not
936 : * very desirable, because a PHV with a large eval_at set will cause a lot
937 : * of probably-useless joins to be considered, but failing to do this can
938 : * cause us to fail to construct a plan at all.)
939 : */
940 2215 : foreach(l, root->placeholder_list)
941 : {
942 105 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
943 :
944 130 : if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) &&
945 25 : bms_is_subset(rel2->relids, phinfo->ph_eval_at))
946 2 : return true;
947 : }
948 :
949 : /*
950 : * It's possible that the rels correspond to the left and right sides of a
951 : * degenerate outer join, that is, one with no joinclause mentioning the
952 : * non-nullable side; in which case we should force the join to occur.
953 : *
954 : * Also, the two rels could represent a clauseless join that has to be
955 : * completed to build up the LHS or RHS of an outer join.
956 : */
957 6212 : foreach(l, root->join_info_list)
958 : {
959 4129 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
960 :
961 : /* ignore full joins --- other mechanisms handle them */
962 4129 : if (sjinfo->jointype == JOIN_FULL)
963 0 : continue;
964 :
965 : /* Can we perform the SJ with these rels? */
966 5194 : if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
967 1065 : bms_is_subset(sjinfo->min_righthand, rel2->relids))
968 : {
969 14 : result = true;
970 14 : break;
971 : }
972 4423 : if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
973 308 : bms_is_subset(sjinfo->min_righthand, rel1->relids))
974 : {
975 3 : result = true;
976 3 : break;
977 : }
978 :
979 : /*
980 : * Might we need to join these rels to complete the RHS? We have to
981 : * use "overlap" tests since either rel might include a lower SJ that
982 : * has been proven to commute with this one.
983 : */
984 4902 : if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
985 790 : bms_overlap(sjinfo->min_righthand, rel2->relids))
986 : {
987 7 : result = true;
988 7 : break;
989 : }
990 :
991 : /* Likewise for the LHS. */
992 5541 : if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
993 1436 : bms_overlap(sjinfo->min_lefthand, rel2->relids))
994 : {
995 3 : result = true;
996 3 : break;
997 : }
998 : }
999 :
1000 : /*
1001 : * We do not force the join to occur if either input rel can legally be
1002 : * joined to anything else using joinclauses. This essentially means that
1003 : * clauseless bushy joins are put off as long as possible. The reason is
1004 : * that when there is a join order restriction high up in the join tree
1005 : * (that is, with many rels inside the LHS or RHS), we would otherwise
1006 : * expend lots of effort considering very stupid join combinations within
1007 : * its LHS or RHS.
1008 : */
1009 2110 : if (result)
1010 : {
1011 50 : if (has_legal_joinclause(root, rel1) ||
1012 23 : has_legal_joinclause(root, rel2))
1013 8 : result = false;
1014 : }
1015 :
1016 2110 : return result;
1017 : }
1018 :
1019 :
1020 : /*
1021 : * has_join_restriction
1022 : * Detect whether the specified relation has join-order restrictions,
1023 : * due to being inside an outer join or an IN (sub-SELECT),
1024 : * or participating in any LATERAL references or multi-rel PHVs.
1025 : *
1026 : * Essentially, this tests whether have_join_order_restriction() could
1027 : * succeed with this rel and some other one. It's OK if we sometimes
1028 : * say "true" incorrectly. (Therefore, we don't bother with the relatively
1029 : * expensive has_legal_joinclause test.)
1030 : */
1031 : static bool
1032 984 : has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
1033 : {
1034 : ListCell *l;
1035 :
1036 984 : if (rel->lateral_relids != NULL || rel->lateral_referencers != NULL)
1037 217 : return true;
1038 :
1039 788 : foreach(l, root->placeholder_list)
1040 : {
1041 21 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
1042 :
1043 22 : if (bms_is_subset(rel->relids, phinfo->ph_eval_at) &&
1044 1 : !bms_equal(rel->relids, phinfo->ph_eval_at))
1045 0 : return true;
1046 : }
1047 :
1048 790 : foreach(l, root->join_info_list)
1049 : {
1050 55 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1051 :
1052 : /* ignore full joins --- other mechanisms preserve their ordering */
1053 55 : if (sjinfo->jointype == JOIN_FULL)
1054 2 : continue;
1055 :
1056 : /* ignore if SJ is already contained in rel */
1057 78 : if (bms_is_subset(sjinfo->min_lefthand, rel->relids) &&
1058 25 : bms_is_subset(sjinfo->min_righthand, rel->relids))
1059 16 : continue;
1060 :
1061 : /* restricted if it overlaps LHS or RHS, but doesn't contain SJ */
1062 63 : if (bms_overlap(sjinfo->min_lefthand, rel->relids) ||
1063 26 : bms_overlap(sjinfo->min_righthand, rel->relids))
1064 32 : return true;
1065 : }
1066 :
1067 735 : return false;
1068 : }
1069 :
1070 :
1071 : /*
1072 : * has_legal_joinclause
1073 : * Detect whether the specified relation can legally be joined
1074 : * to any other rels using join clauses.
1075 : *
1076 : * We consider only joins to single other relations in the current
1077 : * initial_rels list. This is sufficient to get a "true" result in most real
1078 : * queries, and an occasional erroneous "false" will only cost a bit more
1079 : * planning time. The reason for this limitation is that considering joins to
1080 : * other joins would require proving that the other join rel can legally be
1081 : * formed, which seems like too much trouble for something that's only a
1082 : * heuristic to save planning time. (Note: we must look at initial_rels
1083 : * and not all of the query, since when we are planning a sub-joinlist we
1084 : * may be forced to make clauseless joins within initial_rels even though
1085 : * there are join clauses linking to other parts of the query.)
1086 : */
1087 : static bool
1088 50 : has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
1089 : {
1090 : ListCell *lc;
1091 :
1092 221 : foreach(lc, root->initial_rels)
1093 : {
1094 179 : RelOptInfo *rel2 = (RelOptInfo *) lfirst(lc);
1095 :
1096 : /* ignore rels that are already in "rel" */
1097 179 : if (bms_overlap(rel->relids, rel2->relids))
1098 60 : continue;
1099 :
1100 119 : if (have_relevant_joinclause(root, rel, rel2))
1101 : {
1102 : Relids joinrelids;
1103 : SpecialJoinInfo *sjinfo;
1104 : bool reversed;
1105 :
1106 : /* join_is_legal needs relids of the union */
1107 18 : joinrelids = bms_union(rel->relids, rel2->relids);
1108 :
1109 18 : if (join_is_legal(root, rel, rel2, joinrelids,
1110 : &sjinfo, &reversed))
1111 : {
1112 : /* Yes, this will work */
1113 8 : bms_free(joinrelids);
1114 8 : return true;
1115 : }
1116 :
1117 10 : bms_free(joinrelids);
1118 : }
1119 : }
1120 :
1121 42 : return false;
1122 : }
1123 :
1124 :
1125 : /*
1126 : * There's a pitfall for creating parameterized nestloops: suppose the inner
1127 : * rel (call it A) has a parameter that is a PlaceHolderVar, and that PHV's
1128 : * minimum eval_at set includes the outer rel (B) and some third rel (C).
1129 : * We might think we could create a B/A nestloop join that's parameterized by
1130 : * C. But we would end up with a plan in which the PHV's expression has to be
1131 : * evaluated as a nestloop parameter at the B/A join; and the executor is only
1132 : * set up to handle simple Vars as NestLoopParams. Rather than add complexity
1133 : * and overhead to the executor for such corner cases, it seems better to
1134 : * forbid the join. (Note that we can still make use of A's parameterized
1135 : * path with pre-joined B+C as the outer rel. have_join_order_restriction()
1136 : * ensures that we will consider making such a join even if there are not
1137 : * other reasons to do so.)
1138 : *
1139 : * So we check whether any PHVs used in the query could pose such a hazard.
1140 : * We don't have any simple way of checking whether a risky PHV would actually
1141 : * be used in the inner plan, and the case is so unusual that it doesn't seem
1142 : * worth working very hard on it.
1143 : *
1144 : * This needs to be checked in two places. If the inner rel's minimum
1145 : * parameterization would trigger the restriction, then join_is_legal() should
1146 : * reject the join altogether, because there will be no workable paths for it.
1147 : * But joinpath.c has to check again for every proposed nestloop path, because
1148 : * the inner path might have more than the minimum parameterization, causing
1149 : * some PHV to be dangerous for it that otherwise wouldn't be.
1150 : */
1151 : bool
1152 1062 : have_dangerous_phv(PlannerInfo *root,
1153 : Relids outer_relids, Relids inner_params)
1154 : {
1155 : ListCell *lc;
1156 :
1157 1294 : foreach(lc, root->placeholder_list)
1158 : {
1159 270 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1160 :
1161 270 : if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1162 172 : continue; /* ignore, could not be a nestloop param */
1163 98 : if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1164 22 : continue; /* ignore, not relevant to this join */
1165 76 : if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
1166 38 : continue; /* safe, it can be eval'd within outerrel */
1167 : /* Otherwise, it's potentially unsafe, so reject the join */
1168 38 : return true;
1169 : }
1170 :
1171 : /* OK to perform the join */
1172 1024 : return false;
1173 : }
1174 :
1175 :
1176 : /*
1177 : * is_dummy_rel --- has relation been proven empty?
1178 : */
1179 : static bool
1180 21550 : is_dummy_rel(RelOptInfo *rel)
1181 : {
1182 21550 : return IS_DUMMY_REL(rel);
1183 : }
1184 :
1185 : /*
1186 : * Mark a relation as proven empty.
1187 : *
1188 : * During GEQO planning, this can get invoked more than once on the same
1189 : * baserel struct, so it's worth checking to see if the rel is already marked
1190 : * dummy.
1191 : *
1192 : * Also, when called during GEQO join planning, we are in a short-lived
1193 : * memory context. We must make sure that the dummy path attached to a
1194 : * baserel survives the GEQO cycle, else the baserel is trashed for future
1195 : * GEQO cycles. On the other hand, when we are marking a joinrel during GEQO,
1196 : * we don't want the dummy path to clutter the main planning context. Upshot
1197 : * is that the best solution is to explicitly make the dummy path in the same
1198 : * context the given RelOptInfo is in.
1199 : */
1200 : static void
1201 7 : mark_dummy_rel(RelOptInfo *rel)
1202 : {
1203 : MemoryContext oldcontext;
1204 :
1205 : /* Already marked? */
1206 7 : if (is_dummy_rel(rel))
1207 7 : return;
1208 :
1209 : /* No, so choose correct context to make the dummy path in */
1210 7 : oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1211 :
1212 : /* Set dummy size estimate */
1213 7 : rel->rows = 0;
1214 :
1215 : /* Evict any previously chosen paths */
1216 7 : rel->pathlist = NIL;
1217 7 : rel->partial_pathlist = NIL;
1218 :
1219 : /* Set up the dummy path */
1220 7 : add_path(rel, (Path *) create_append_path(rel, NIL, NULL, 0, NIL));
1221 :
1222 : /* Set or update cheapest_total_path and related fields */
1223 7 : set_cheapest(rel);
1224 :
1225 7 : MemoryContextSwitchTo(oldcontext);
1226 : }
1227 :
1228 :
1229 : /*
1230 : * restriction_is_constant_false --- is a restrictlist just FALSE?
1231 : *
1232 : * In cases where a qual is provably constant FALSE, eval_const_expressions
1233 : * will generally have thrown away anything that's ANDed with it. In outer
1234 : * join situations this will leave us computing cartesian products only to
1235 : * decide there's no match for an outer row, which is pretty stupid. So,
1236 : * we need to detect the case.
1237 : *
1238 : * If only_pushed_down is TRUE, then consider only pushed-down quals.
1239 : */
1240 : static bool
1241 9360 : restriction_is_constant_false(List *restrictlist, bool only_pushed_down)
1242 : {
1243 : ListCell *lc;
1244 :
1245 : /*
1246 : * Despite the above comment, the restriction list we see here might
1247 : * possibly have other members besides the FALSE constant, since other
1248 : * quals could get "pushed down" to the outer join level. So we check
1249 : * each member of the list.
1250 : */
1251 18338 : foreach(lc, restrictlist)
1252 : {
1253 8981 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1254 :
1255 8981 : if (only_pushed_down && !rinfo->is_pushed_down)
1256 1975 : continue;
1257 :
1258 7006 : if (rinfo->clause && IsA(rinfo->clause, Const))
1259 : {
1260 3 : Const *con = (Const *) rinfo->clause;
1261 :
1262 : /* constant NULL is as good as constant FALSE for our purposes */
1263 3 : if (con->constisnull)
1264 0 : return true;
1265 3 : if (!DatumGetBool(con->constvalue))
1266 3 : return true;
1267 : }
1268 : }
1269 9357 : return false;
1270 : }
|
