Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * joinpath.c
4 : * Routines to find all possible paths for processing a set of joins
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/joinpath.c
12 : *
13 : *-------------------------------------------------------------------------
14 : */
15 : #include "postgres.h"
16 :
17 : #include <math.h>
18 :
19 : #include "executor/executor.h"
20 : #include "foreign/fdwapi.h"
21 : #include "optimizer/cost.h"
22 : #include "optimizer/pathnode.h"
23 : #include "optimizer/paths.h"
24 : #include "optimizer/planmain.h"
25 :
26 : /* Hook for plugins to get control in add_paths_to_joinrel() */
27 : set_join_pathlist_hook_type set_join_pathlist_hook = NULL;
28 :
29 : #define PATH_PARAM_BY_REL(path, rel) \
30 : ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids))
31 :
32 : static void try_partial_mergejoin_path(PlannerInfo *root,
33 : RelOptInfo *joinrel,
34 : Path *outer_path,
35 : Path *inner_path,
36 : List *pathkeys,
37 : List *mergeclauses,
38 : List *outersortkeys,
39 : List *innersortkeys,
40 : JoinType jointype,
41 : JoinPathExtraData *extra);
42 : static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
43 : RelOptInfo *outerrel, RelOptInfo *innerrel,
44 : JoinType jointype, JoinPathExtraData *extra);
45 : static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel,
46 : RelOptInfo *outerrel, RelOptInfo *innerrel,
47 : JoinType jointype, JoinPathExtraData *extra);
48 : static void consider_parallel_nestloop(PlannerInfo *root,
49 : RelOptInfo *joinrel,
50 : RelOptInfo *outerrel,
51 : RelOptInfo *innerrel,
52 : JoinType jointype,
53 : JoinPathExtraData *extra);
54 : static void consider_parallel_mergejoin(PlannerInfo *root,
55 : RelOptInfo *joinrel,
56 : RelOptInfo *outerrel,
57 : RelOptInfo *innerrel,
58 : JoinType jointype,
59 : JoinPathExtraData *extra,
60 : Path *inner_cheapest_total);
61 : static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
62 : RelOptInfo *outerrel, RelOptInfo *innerrel,
63 : JoinType jointype, JoinPathExtraData *extra);
64 : static List *select_mergejoin_clauses(PlannerInfo *root,
65 : RelOptInfo *joinrel,
66 : RelOptInfo *outerrel,
67 : RelOptInfo *innerrel,
68 : List *restrictlist,
69 : JoinType jointype,
70 : bool *mergejoin_allowed);
71 : static void generate_mergejoin_paths(PlannerInfo *root,
72 : RelOptInfo *joinrel,
73 : RelOptInfo *innerrel,
74 : Path *outerpath,
75 : JoinType jointype,
76 : JoinPathExtraData *extra,
77 : bool useallclauses,
78 : Path *inner_cheapest_total,
79 : List *merge_pathkeys,
80 : bool is_partial);
81 :
82 :
83 : /*
84 : * add_paths_to_joinrel
85 : * Given a join relation and two component rels from which it can be made,
86 : * consider all possible paths that use the two component rels as outer
87 : * and inner rel respectively. Add these paths to the join rel's pathlist
88 : * if they survive comparison with other paths (and remove any existing
89 : * paths that are dominated by these paths).
90 : *
91 : * Modifies the pathlist field of the joinrel node to contain the best
92 : * paths found so far.
93 : *
94 : * jointype is not necessarily the same as sjinfo->jointype; it might be
95 : * "flipped around" if we are considering joining the rels in the opposite
96 : * direction from what's indicated in sjinfo.
97 : *
98 : * Also, this routine and others in this module accept the special JoinTypes
99 : * JOIN_UNIQUE_OUTER and JOIN_UNIQUE_INNER to indicate that we should
100 : * unique-ify the outer or inner relation and then apply a regular inner
101 : * join. These values are not allowed to propagate outside this module,
102 : * however. Path cost estimation code may need to recognize that it's
103 : * dealing with such a case --- the combination of nominal jointype INNER
104 : * with sjinfo->jointype == JOIN_SEMI indicates that.
105 : */
106 : void
107 15042 : add_paths_to_joinrel(PlannerInfo *root,
108 : RelOptInfo *joinrel,
109 : RelOptInfo *outerrel,
110 : RelOptInfo *innerrel,
111 : JoinType jointype,
112 : SpecialJoinInfo *sjinfo,
113 : List *restrictlist)
114 : {
115 : JoinPathExtraData extra;
116 15042 : bool mergejoin_allowed = true;
117 : ListCell *lc;
118 :
119 15042 : extra.restrictlist = restrictlist;
120 15042 : extra.mergeclause_list = NIL;
121 15042 : extra.sjinfo = sjinfo;
122 15042 : extra.param_source_rels = NULL;
123 :
124 : /*
125 : * See if the inner relation is provably unique for this outer rel.
126 : *
127 : * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
128 : * matter since the executor can make the equivalent optimization anyway;
129 : * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
130 : * must be considering a semijoin whose inner side is not provably unique
131 : * (else reduce_unique_semijoins would've simplified it), so there's no
132 : * point in calling innerrel_is_unique. However, if the LHS covers all of
133 : * the semijoin's min_lefthand, then it's appropriate to set inner_unique
134 : * because the path produced by create_unique_path will be unique relative
135 : * to the LHS. (If we have an LHS that's only part of the min_lefthand,
136 : * that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
137 : * letting that value escape this module.
138 : */
139 15042 : switch (jointype)
140 : {
141 : case JOIN_SEMI:
142 : case JOIN_ANTI:
143 570 : extra.inner_unique = false; /* well, unproven */
144 570 : break;
145 : case JOIN_UNIQUE_INNER:
146 315 : extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
147 315 : outerrel->relids);
148 315 : break;
149 : case JOIN_UNIQUE_OUTER:
150 315 : extra.inner_unique = innerrel_is_unique(root,
151 : outerrel->relids,
152 : innerrel,
153 : JOIN_INNER,
154 : restrictlist,
155 : false);
156 315 : break;
157 : default:
158 13842 : extra.inner_unique = innerrel_is_unique(root,
159 : outerrel->relids,
160 : innerrel,
161 : jointype,
162 : restrictlist,
163 : false);
164 13842 : break;
165 : }
166 :
167 : /*
168 : * Find potential mergejoin clauses. We can skip this if we are not
169 : * interested in doing a mergejoin. However, mergejoin may be our only
170 : * way of implementing a full outer join, so override enable_mergejoin if
171 : * it's a full join.
172 : */
173 15042 : if (enable_mergejoin || jointype == JOIN_FULL)
174 14994 : extra.mergeclause_list = select_mergejoin_clauses(root,
175 : joinrel,
176 : outerrel,
177 : innerrel,
178 : restrictlist,
179 : jointype,
180 : &mergejoin_allowed);
181 :
182 : /*
183 : * If it's SEMI, ANTI, or inner_unique join, compute correction factors
184 : * for cost estimation. These will be the same for all paths.
185 : */
186 15042 : if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique)
187 4609 : compute_semi_anti_join_factors(root, outerrel, innerrel,
188 : jointype, sjinfo, restrictlist,
189 : &extra.semifactors);
190 :
191 : /*
192 : * Decide whether it's sensible to generate parameterized paths for this
193 : * joinrel, and if so, which relations such paths should require. There
194 : * is usually no need to create a parameterized result path unless there
195 : * is a join order restriction that prevents joining one of our input rels
196 : * directly to the parameter source rel instead of joining to the other
197 : * input rel. (But see allow_star_schema_join().) This restriction
198 : * reduces the number of parameterized paths we have to deal with at
199 : * higher join levels, without compromising the quality of the resulting
200 : * plan. We express the restriction as a Relids set that must overlap the
201 : * parameterization of any proposed join path.
202 : */
203 29067 : foreach(lc, root->join_info_list)
204 : {
205 14025 : SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
206 :
207 : /*
208 : * SJ is relevant to this join if we have some part of its RHS
209 : * (possibly not all of it), and haven't yet joined to its LHS. (This
210 : * test is pretty simplistic, but should be sufficient considering the
211 : * join has already been proven legal.) If the SJ is relevant, it
212 : * presents constraints for joining to anything not in its RHS.
213 : */
214 21454 : if (bms_overlap(joinrel->relids, sjinfo2->min_righthand) &&
215 7429 : !bms_overlap(joinrel->relids, sjinfo2->min_lefthand))
216 968 : extra.param_source_rels = bms_join(extra.param_source_rels,
217 968 : bms_difference(root->all_baserels,
218 968 : sjinfo2->min_righthand));
219 :
220 : /* full joins constrain both sides symmetrically */
221 14107 : if (sjinfo2->jointype == JOIN_FULL &&
222 160 : bms_overlap(joinrel->relids, sjinfo2->min_lefthand) &&
223 78 : !bms_overlap(joinrel->relids, sjinfo2->min_righthand))
224 4 : extra.param_source_rels = bms_join(extra.param_source_rels,
225 4 : bms_difference(root->all_baserels,
226 4 : sjinfo2->min_lefthand));
227 : }
228 :
229 : /*
230 : * However, when a LATERAL subquery is involved, there will simply not be
231 : * any paths for the joinrel that aren't parameterized by whatever the
232 : * subquery is parameterized by, unless its parameterization is resolved
233 : * within the joinrel. So we might as well allow additional dependencies
234 : * on whatever residual lateral dependencies the joinrel will have.
235 : */
236 15042 : extra.param_source_rels = bms_add_members(extra.param_source_rels,
237 15042 : joinrel->lateral_relids);
238 :
239 : /*
240 : * 1. Consider mergejoin paths where both relations must be explicitly
241 : * sorted. Skip this if we can't mergejoin.
242 : */
243 15042 : if (mergejoin_allowed)
244 14729 : sort_inner_and_outer(root, joinrel, outerrel, innerrel,
245 : jointype, &extra);
246 :
247 : /*
248 : * 2. Consider paths where the outer relation need not be explicitly
249 : * sorted. This includes both nestloops and mergejoins where the outer
250 : * path is already ordered. Again, skip this if we can't mergejoin.
251 : * (That's okay because we know that nestloop can't handle right/full
252 : * joins at all, so it wouldn't work in the prohibited cases either.)
253 : */
254 15042 : if (mergejoin_allowed)
255 14729 : match_unsorted_outer(root, joinrel, outerrel, innerrel,
256 : jointype, &extra);
257 :
258 : #ifdef NOT_USED
259 :
260 : /*
261 : * 3. Consider paths where the inner relation need not be explicitly
262 : * sorted. This includes mergejoins only (nestloops were already built in
263 : * match_unsorted_outer).
264 : *
265 : * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
266 : * significant difference between the inner and outer side of a mergejoin,
267 : * so match_unsorted_inner creates no paths that aren't equivalent to
268 : * those made by match_unsorted_outer when add_paths_to_joinrel() is
269 : * invoked with the two rels given in the other order.
270 : */
271 : if (mergejoin_allowed)
272 : match_unsorted_inner(root, joinrel, outerrel, innerrel,
273 : jointype, &extra);
274 : #endif
275 :
276 : /*
277 : * 4. Consider paths where both outer and inner relations must be hashed
278 : * before being joined. As above, disregard enable_hashjoin for full
279 : * joins, because there may be no other alternative.
280 : */
281 15042 : if (enable_hashjoin || jointype == JOIN_FULL)
282 14964 : hash_inner_and_outer(root, joinrel, outerrel, innerrel,
283 : jointype, &extra);
284 :
285 : /*
286 : * 5. If inner and outer relations are foreign tables (or joins) belonging
287 : * to the same server and assigned to the same user to check access
288 : * permissions as, give the FDW a chance to push down joins.
289 : */
290 15042 : if (joinrel->fdwroutine &&
291 0 : joinrel->fdwroutine->GetForeignJoinPaths)
292 0 : joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
293 : outerrel, innerrel,
294 : jointype, &extra);
295 :
296 : /*
297 : * 6. Finally, give extensions a chance to manipulate the path list.
298 : */
299 15042 : if (set_join_pathlist_hook)
300 0 : set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
301 : jointype, &extra);
302 15042 : }
303 :
304 : /*
305 : * We override the param_source_rels heuristic to accept nestloop paths in
306 : * which the outer rel satisfies some but not all of the inner path's
307 : * parameterization. This is necessary to get good plans for star-schema
308 : * scenarios, in which a parameterized path for a large table may require
309 : * parameters from multiple small tables that will not get joined directly to
310 : * each other. We can handle that by stacking nestloops that have the small
311 : * tables on the outside; but this breaks the rule the param_source_rels
312 : * heuristic is based on, namely that parameters should not be passed down
313 : * across joins unless there's a join-order-constraint-based reason to do so.
314 : * So we ignore the param_source_rels restriction when this case applies.
315 : *
316 : * allow_star_schema_join() returns TRUE if the param_source_rels restriction
317 : * should be overridden, ie, it's okay to perform this join.
318 : */
319 : static inline bool
320 3753 : allow_star_schema_join(PlannerInfo *root,
321 : Relids outerrelids,
322 : Relids inner_paramrels)
323 : {
324 : /*
325 : * It's a star-schema case if the outer rel provides some but not all of
326 : * the inner rel's parameterization.
327 : */
328 4149 : return (bms_overlap(inner_paramrels, outerrelids) &&
329 396 : bms_nonempty_difference(inner_paramrels, outerrelids));
330 : }
331 :
332 : /*
333 : * try_nestloop_path
334 : * Consider a nestloop join path; if it appears useful, push it into
335 : * the joinrel's pathlist via add_path().
336 : */
337 : static void
338 53567 : try_nestloop_path(PlannerInfo *root,
339 : RelOptInfo *joinrel,
340 : Path *outer_path,
341 : Path *inner_path,
342 : List *pathkeys,
343 : JoinType jointype,
344 : JoinPathExtraData *extra)
345 : {
346 : Relids required_outer;
347 : JoinCostWorkspace workspace;
348 53567 : RelOptInfo *innerrel = inner_path->parent;
349 53567 : RelOptInfo *outerrel = outer_path->parent;
350 53567 : Relids innerrelids = innerrel->relids;
351 53567 : Relids outerrelids = outerrel->relids;
352 53567 : Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
353 53567 : Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
354 :
355 : /*
356 : * Check to see if proposed path is still parameterized, and reject if the
357 : * parameterization wouldn't be sensible --- unless allow_star_schema_join
358 : * says to allow it anyway. Also, we must reject if have_dangerous_phv
359 : * doesn't like the look of it, which could only happen if the nestloop is
360 : * still parameterized.
361 : */
362 53567 : required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels,
363 : innerrelids, inner_paramrels);
364 58067 : if (required_outer &&
365 8253 : ((!bms_overlap(required_outer, extra->param_source_rels) &&
366 4548 : !allow_star_schema_join(root, outerrelids, inner_paramrels)) ||
367 795 : have_dangerous_phv(root, outerrelids, inner_paramrels)))
368 : {
369 : /* Waste no memory when we reject a path here */
370 3717 : bms_free(required_outer);
371 57284 : return;
372 : }
373 :
374 : /*
375 : * Do a precheck to quickly eliminate obviously-inferior paths. We
376 : * calculate a cheap lower bound on the path's cost and then use
377 : * add_path_precheck() to see if the path is clearly going to be dominated
378 : * by some existing path for the joinrel. If not, do the full pushup with
379 : * creating a fully valid path structure and submitting it to add_path().
380 : * The latter two steps are expensive enough to make this two-phase
381 : * methodology worthwhile.
382 : */
383 49850 : initial_cost_nestloop(root, &workspace, jointype,
384 : outer_path, inner_path, extra);
385 :
386 49850 : if (add_path_precheck(joinrel,
387 : workspace.startup_cost, workspace.total_cost,
388 : pathkeys, required_outer))
389 : {
390 25819 : add_path(joinrel, (Path *)
391 25819 : create_nestloop_path(root,
392 : joinrel,
393 : jointype,
394 : &workspace,
395 : extra,
396 : outer_path,
397 : inner_path,
398 : extra->restrictlist,
399 : pathkeys,
400 : required_outer));
401 : }
402 : else
403 : {
404 : /* Waste no memory when we reject a path here */
405 24031 : bms_free(required_outer);
406 : }
407 : }
408 :
409 : /*
410 : * try_partial_nestloop_path
411 : * Consider a partial nestloop join path; if it appears useful, push it into
412 : * the joinrel's partial_pathlist via add_partial_path().
413 : */
414 : static void
415 51 : try_partial_nestloop_path(PlannerInfo *root,
416 : RelOptInfo *joinrel,
417 : Path *outer_path,
418 : Path *inner_path,
419 : List *pathkeys,
420 : JoinType jointype,
421 : JoinPathExtraData *extra)
422 : {
423 : JoinCostWorkspace workspace;
424 :
425 : /*
426 : * If the inner path is parameterized, the parameterization must be fully
427 : * satisfied by the proposed outer path. Parameterized partial paths are
428 : * not supported. The caller should already have verified that no
429 : * extra_lateral_rels are required here.
430 : */
431 51 : Assert(bms_is_empty(joinrel->lateral_relids));
432 51 : if (inner_path->param_info != NULL)
433 : {
434 22 : Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
435 :
436 22 : if (!bms_is_subset(inner_paramrels, outer_path->parent->relids))
437 29 : return;
438 : }
439 :
440 : /*
441 : * Before creating a path, get a quick lower bound on what it is likely to
442 : * cost. Bail out right away if it looks terrible.
443 : */
444 51 : initial_cost_nestloop(root, &workspace, jointype,
445 : outer_path, inner_path, extra);
446 51 : if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
447 29 : return;
448 :
449 : /* Might be good enough to be worth trying, so let's try it. */
450 22 : add_partial_path(joinrel, (Path *)
451 22 : create_nestloop_path(root,
452 : joinrel,
453 : jointype,
454 : &workspace,
455 : extra,
456 : outer_path,
457 : inner_path,
458 : extra->restrictlist,
459 : pathkeys,
460 : NULL));
461 : }
462 :
463 : /*
464 : * try_mergejoin_path
465 : * Consider a merge join path; if it appears useful, push it into
466 : * the joinrel's pathlist via add_path().
467 : */
468 : static void
469 20359 : try_mergejoin_path(PlannerInfo *root,
470 : RelOptInfo *joinrel,
471 : Path *outer_path,
472 : Path *inner_path,
473 : List *pathkeys,
474 : List *mergeclauses,
475 : List *outersortkeys,
476 : List *innersortkeys,
477 : JoinType jointype,
478 : JoinPathExtraData *extra,
479 : bool is_partial)
480 : {
481 : Relids required_outer;
482 : JoinCostWorkspace workspace;
483 :
484 20359 : if (is_partial)
485 : {
486 2 : try_partial_mergejoin_path(root,
487 : joinrel,
488 : outer_path,
489 : inner_path,
490 : pathkeys,
491 : mergeclauses,
492 : outersortkeys,
493 : innersortkeys,
494 : jointype,
495 : extra);
496 2 : return;
497 : }
498 :
499 : /*
500 : * Check to see if proposed path is still parameterized, and reject if the
501 : * parameterization wouldn't be sensible.
502 : */
503 20357 : required_outer = calc_non_nestloop_required_outer(outer_path,
504 : inner_path);
505 20619 : if (required_outer &&
506 262 : !bms_overlap(required_outer, extra->param_source_rels))
507 : {
508 : /* Waste no memory when we reject a path here */
509 215 : bms_free(required_outer);
510 215 : return;
511 : }
512 :
513 : /*
514 : * If the given paths are already well enough ordered, we can skip doing
515 : * an explicit sort.
516 : */
517 31326 : if (outersortkeys &&
518 11184 : pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
519 293 : outersortkeys = NIL;
520 37354 : if (innersortkeys &&
521 17212 : pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
522 429 : innersortkeys = NIL;
523 :
524 : /*
525 : * See comments in try_nestloop_path().
526 : */
527 20142 : initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
528 : outer_path, inner_path,
529 : outersortkeys, innersortkeys,
530 : extra);
531 :
532 20142 : if (add_path_precheck(joinrel,
533 : workspace.startup_cost, workspace.total_cost,
534 : pathkeys, required_outer))
535 : {
536 6489 : add_path(joinrel, (Path *)
537 6489 : create_mergejoin_path(root,
538 : joinrel,
539 : jointype,
540 : &workspace,
541 : extra,
542 : outer_path,
543 : inner_path,
544 : extra->restrictlist,
545 : pathkeys,
546 : required_outer,
547 : mergeclauses,
548 : outersortkeys,
549 : innersortkeys));
550 : }
551 : else
552 : {
553 : /* Waste no memory when we reject a path here */
554 13653 : bms_free(required_outer);
555 : }
556 : }
557 :
558 : /*
559 : * try_partial_mergejoin_path
560 : * Consider a partial merge join path; if it appears useful, push it into
561 : * the joinrel's pathlist via add_partial_path().
562 : */
563 : static void
564 25 : try_partial_mergejoin_path(PlannerInfo *root,
565 : RelOptInfo *joinrel,
566 : Path *outer_path,
567 : Path *inner_path,
568 : List *pathkeys,
569 : List *mergeclauses,
570 : List *outersortkeys,
571 : List *innersortkeys,
572 : JoinType jointype,
573 : JoinPathExtraData *extra)
574 : {
575 : JoinCostWorkspace workspace;
576 :
577 : /*
578 : * See comments in try_partial_hashjoin_path().
579 : */
580 25 : Assert(bms_is_empty(joinrel->lateral_relids));
581 25 : if (inner_path->param_info != NULL)
582 : {
583 0 : Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
584 :
585 0 : if (!bms_is_empty(inner_paramrels))
586 4 : return;
587 : }
588 :
589 : /*
590 : * If the given paths are already well enough ordered, we can skip doing
591 : * an explicit sort.
592 : */
593 48 : if (outersortkeys &&
594 23 : pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
595 2 : outersortkeys = NIL;
596 50 : if (innersortkeys &&
597 25 : pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
598 6 : innersortkeys = NIL;
599 :
600 : /*
601 : * See comments in try_partial_nestloop_path().
602 : */
603 25 : initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
604 : outer_path, inner_path,
605 : outersortkeys, innersortkeys,
606 : extra);
607 :
608 25 : if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
609 4 : return;
610 :
611 : /* Might be good enough to be worth trying, so let's try it. */
612 21 : add_partial_path(joinrel, (Path *)
613 21 : create_mergejoin_path(root,
614 : joinrel,
615 : jointype,
616 : &workspace,
617 : extra,
618 : outer_path,
619 : inner_path,
620 : extra->restrictlist,
621 : pathkeys,
622 : NULL,
623 : mergeclauses,
624 : outersortkeys,
625 : innersortkeys));
626 : }
627 :
628 : /*
629 : * try_hashjoin_path
630 : * Consider a hash join path; if it appears useful, push it into
631 : * the joinrel's pathlist via add_path().
632 : */
633 : static void
634 13802 : try_hashjoin_path(PlannerInfo *root,
635 : RelOptInfo *joinrel,
636 : Path *outer_path,
637 : Path *inner_path,
638 : List *hashclauses,
639 : JoinType jointype,
640 : JoinPathExtraData *extra)
641 : {
642 : Relids required_outer;
643 : JoinCostWorkspace workspace;
644 :
645 : /*
646 : * Check to see if proposed path is still parameterized, and reject if the
647 : * parameterization wouldn't be sensible.
648 : */
649 13802 : required_outer = calc_non_nestloop_required_outer(outer_path,
650 : inner_path);
651 15506 : if (required_outer &&
652 1704 : !bms_overlap(required_outer, extra->param_source_rels))
653 : {
654 : /* Waste no memory when we reject a path here */
655 1441 : bms_free(required_outer);
656 15243 : return;
657 : }
658 :
659 : /*
660 : * See comments in try_nestloop_path(). Also note that hashjoin paths
661 : * never have any output pathkeys, per comments in create_hashjoin_path.
662 : */
663 12361 : initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
664 : outer_path, inner_path, extra);
665 :
666 12361 : if (add_path_precheck(joinrel,
667 : workspace.startup_cost, workspace.total_cost,
668 : NIL, required_outer))
669 : {
670 7050 : add_path(joinrel, (Path *)
671 7050 : create_hashjoin_path(root,
672 : joinrel,
673 : jointype,
674 : &workspace,
675 : extra,
676 : outer_path,
677 : inner_path,
678 : extra->restrictlist,
679 : required_outer,
680 : hashclauses));
681 : }
682 : else
683 : {
684 : /* Waste no memory when we reject a path here */
685 5311 : bms_free(required_outer);
686 : }
687 : }
688 :
689 : /*
690 : * try_partial_hashjoin_path
691 : * Consider a partial hashjoin join path; if it appears useful, push it into
692 : * the joinrel's partial_pathlist via add_partial_path().
693 : */
694 : static void
695 19 : try_partial_hashjoin_path(PlannerInfo *root,
696 : RelOptInfo *joinrel,
697 : Path *outer_path,
698 : Path *inner_path,
699 : List *hashclauses,
700 : JoinType jointype,
701 : JoinPathExtraData *extra)
702 : {
703 : JoinCostWorkspace workspace;
704 :
705 : /*
706 : * If the inner path is parameterized, the parameterization must be fully
707 : * satisfied by the proposed outer path. Parameterized partial paths are
708 : * not supported. The caller should already have verified that no
709 : * extra_lateral_rels are required here.
710 : */
711 19 : Assert(bms_is_empty(joinrel->lateral_relids));
712 19 : if (inner_path->param_info != NULL)
713 : {
714 0 : Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
715 :
716 0 : if (!bms_is_empty(inner_paramrels))
717 2 : return;
718 : }
719 :
720 : /*
721 : * Before creating a path, get a quick lower bound on what it is likely to
722 : * cost. Bail out right away if it looks terrible.
723 : */
724 19 : initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
725 : outer_path, inner_path, extra);
726 19 : if (!add_partial_path_precheck(joinrel, workspace.total_cost, NIL))
727 2 : return;
728 :
729 : /* Might be good enough to be worth trying, so let's try it. */
730 17 : add_partial_path(joinrel, (Path *)
731 17 : create_hashjoin_path(root,
732 : joinrel,
733 : jointype,
734 : &workspace,
735 : extra,
736 : outer_path,
737 : inner_path,
738 : extra->restrictlist,
739 : NULL,
740 : hashclauses));
741 : }
742 :
743 : /*
744 : * clause_sides_match_join
745 : * Determine whether a join clause is of the right form to use in this join.
746 : *
747 : * We already know that the clause is a binary opclause referencing only the
748 : * rels in the current join. The point here is to check whether it has the
749 : * form "outerrel_expr op innerrel_expr" or "innerrel_expr op outerrel_expr",
750 : * rather than mixing outer and inner vars on either side. If it matches,
751 : * we set the transient flag outer_is_left to identify which side is which.
752 : */
753 : static inline bool
754 23699 : clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel,
755 : RelOptInfo *innerrel)
756 : {
757 35259 : if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
758 11560 : bms_is_subset(rinfo->right_relids, innerrel->relids))
759 : {
760 : /* lefthand side is outer */
761 11552 : rinfo->outer_is_left = true;
762 11552 : return true;
763 : }
764 24098 : else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
765 11951 : bms_is_subset(rinfo->right_relids, outerrel->relids))
766 : {
767 : /* righthand side is outer */
768 11943 : rinfo->outer_is_left = false;
769 11943 : return true;
770 : }
771 204 : return false; /* no good for these input relations */
772 : }
773 :
774 : /*
775 : * sort_inner_and_outer
776 : * Create mergejoin join paths by explicitly sorting both the outer and
777 : * inner join relations on each available merge ordering.
778 : *
779 : * 'joinrel' is the join relation
780 : * 'outerrel' is the outer join relation
781 : * 'innerrel' is the inner join relation
782 : * 'jointype' is the type of join to do
783 : * 'extra' contains additional input values
784 : */
785 : static void
786 14729 : sort_inner_and_outer(PlannerInfo *root,
787 : RelOptInfo *joinrel,
788 : RelOptInfo *outerrel,
789 : RelOptInfo *innerrel,
790 : JoinType jointype,
791 : JoinPathExtraData *extra)
792 : {
793 14729 : JoinType save_jointype = jointype;
794 : Path *outer_path;
795 : Path *inner_path;
796 14729 : Path *cheapest_partial_outer = NULL;
797 14729 : Path *cheapest_safe_inner = NULL;
798 : List *all_pathkeys;
799 : ListCell *l;
800 :
801 : /*
802 : * We only consider the cheapest-total-cost input paths, since we are
803 : * assuming here that a sort is required. We will consider
804 : * cheapest-startup-cost input paths later, and only if they don't need a
805 : * sort.
806 : *
807 : * This function intentionally does not consider parameterized input
808 : * paths, except when the cheapest-total is parameterized. If we did so,
809 : * we'd have a combinatorial explosion of mergejoin paths of dubious
810 : * value. This interacts with decisions elsewhere that also discriminate
811 : * against mergejoins with parameterized inputs; see comments in
812 : * src/backend/optimizer/README.
813 : */
814 14729 : outer_path = outerrel->cheapest_total_path;
815 14729 : inner_path = innerrel->cheapest_total_path;
816 :
817 : /*
818 : * If either cheapest-total path is parameterized by the other rel, we
819 : * can't use a mergejoin. (There's no use looking for alternative input
820 : * paths, since these should already be the least-parameterized available
821 : * paths.)
822 : */
823 29225 : if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
824 14762 : PATH_PARAM_BY_REL(inner_path, outerrel))
825 15197 : return;
826 :
827 : /*
828 : * If unique-ification is requested, do it and then handle as a plain
829 : * inner join.
830 : */
831 14261 : if (jointype == JOIN_UNIQUE_OUTER)
832 : {
833 315 : outer_path = (Path *) create_unique_path(root, outerrel,
834 : outer_path, extra->sjinfo);
835 315 : Assert(outer_path);
836 315 : jointype = JOIN_INNER;
837 : }
838 13946 : else if (jointype == JOIN_UNIQUE_INNER)
839 : {
840 315 : inner_path = (Path *) create_unique_path(root, innerrel,
841 : inner_path, extra->sjinfo);
842 315 : Assert(inner_path);
843 315 : jointype = JOIN_INNER;
844 : }
845 :
846 : /*
847 : * If the joinrel is parallel-safe, we may be able to consider a partial
848 : * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
849 : * outer path will be partial, and therefore we won't be able to properly
850 : * guarantee uniqueness. Similarly, we can't handle JOIN_FULL and
851 : * JOIN_RIGHT, because they can produce false null extended rows. Also,
852 : * the resulting path must not be parameterized.
853 : */
854 14261 : if (joinrel->consider_parallel &&
855 8688 : save_jointype != JOIN_UNIQUE_OUTER &&
856 8642 : save_jointype != JOIN_FULL &&
857 7887 : save_jointype != JOIN_RIGHT &&
858 7922 : outerrel->partial_pathlist != NIL &&
859 35 : bms_is_empty(joinrel->lateral_relids))
860 : {
861 35 : cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
862 :
863 35 : if (inner_path->parallel_safe)
864 29 : cheapest_safe_inner = inner_path;
865 6 : else if (save_jointype != JOIN_UNIQUE_INNER)
866 6 : cheapest_safe_inner =
867 6 : get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
868 : }
869 :
870 : /*
871 : * Each possible ordering of the available mergejoin clauses will generate
872 : * a differently-sorted result path at essentially the same cost. We have
873 : * no basis for choosing one over another at this level of joining, but
874 : * some sort orders may be more useful than others for higher-level
875 : * mergejoins, so it's worth considering multiple orderings.
876 : *
877 : * Actually, it's not quite true that every mergeclause ordering will
878 : * generate a different path order, because some of the clauses may be
879 : * partially redundant (refer to the same EquivalenceClasses). Therefore,
880 : * what we do is convert the mergeclause list to a list of canonical
881 : * pathkeys, and then consider different orderings of the pathkeys.
882 : *
883 : * Generating a path for *every* permutation of the pathkeys doesn't seem
884 : * like a winning strategy; the cost in planning time is too high. For
885 : * now, we generate one path for each pathkey, listing that pathkey first
886 : * and the rest in random order. This should allow at least a one-clause
887 : * mergejoin without re-sorting against any other possible mergejoin
888 : * partner path. But if we've not guessed the right ordering of secondary
889 : * keys, we may end up evaluating clauses as qpquals when they could have
890 : * been done as mergeclauses. (In practice, it's rare that there's more
891 : * than two or three mergeclauses, so expending a huge amount of thought
892 : * on that is probably not worth it.)
893 : *
894 : * The pathkey order returned by select_outer_pathkeys_for_merge() has
895 : * some heuristics behind it (see that function), so be sure to try it
896 : * exactly as-is as well as making variants.
897 : */
898 14261 : all_pathkeys = select_outer_pathkeys_for_merge(root,
899 : extra->mergeclause_list,
900 : joinrel);
901 :
902 25445 : foreach(l, all_pathkeys)
903 : {
904 11184 : List *front_pathkey = (List *) lfirst(l);
905 : List *cur_mergeclauses;
906 : List *outerkeys;
907 : List *innerkeys;
908 : List *merge_pathkeys;
909 :
910 : /* Make a pathkey list with this guy first */
911 11184 : if (l != list_head(all_pathkeys))
912 654 : outerkeys = lcons(front_pathkey,
913 : list_delete_ptr(list_copy(all_pathkeys),
914 : front_pathkey));
915 : else
916 10530 : outerkeys = all_pathkeys; /* no work at first one... */
917 :
918 : /* Sort the mergeclauses into the corresponding ordering */
919 11184 : cur_mergeclauses = find_mergeclauses_for_pathkeys(root,
920 : outerkeys,
921 : true,
922 : extra->mergeclause_list);
923 :
924 : /* Should have used them all... */
925 11184 : Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
926 :
927 : /* Build sort pathkeys for the inner side */
928 11184 : innerkeys = make_inner_pathkeys_for_merge(root,
929 : cur_mergeclauses,
930 : outerkeys);
931 :
932 : /* Build pathkeys representing output sort order */
933 11184 : merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
934 : outerkeys);
935 :
936 : /*
937 : * And now we can make the path.
938 : *
939 : * Note: it's possible that the cheapest paths will already be sorted
940 : * properly. try_mergejoin_path will detect that case and suppress an
941 : * explicit sort step, so we needn't do so here.
942 : */
943 11184 : try_mergejoin_path(root,
944 : joinrel,
945 : outer_path,
946 : inner_path,
947 : merge_pathkeys,
948 : cur_mergeclauses,
949 : outerkeys,
950 : innerkeys,
951 : jointype,
952 : extra,
953 : false);
954 :
955 : /*
956 : * If we have partial outer and parallel safe inner path then try
957 : * partial mergejoin path.
958 : */
959 11184 : if (cheapest_partial_outer && cheapest_safe_inner)
960 23 : try_partial_mergejoin_path(root,
961 : joinrel,
962 : cheapest_partial_outer,
963 : cheapest_safe_inner,
964 : merge_pathkeys,
965 : cur_mergeclauses,
966 : outerkeys,
967 : innerkeys,
968 : jointype,
969 : extra);
970 : }
971 : }
972 :
973 : /*
974 : * generate_mergejoin_paths
975 : * Creates possible mergejoin paths for input outerpath.
976 : *
977 : * We generate mergejoins if mergejoin clauses are available. We have
978 : * two ways to generate the inner path for a mergejoin: sort the cheapest
979 : * inner path, or use an inner path that is already suitably ordered for the
980 : * merge. If we have several mergeclauses, it could be that there is no inner
981 : * path (or only a very expensive one) for the full list of mergeclauses, but
982 : * better paths exist if we truncate the mergeclause list (thereby discarding
983 : * some sort key requirements). So, we consider truncations of the
984 : * mergeclause list as well as the full list. (Ideally we'd consider all
985 : * subsets of the mergeclause list, but that seems way too expensive.)
986 : */
987 : static void
988 22947 : generate_mergejoin_paths(PlannerInfo *root,
989 : RelOptInfo *joinrel,
990 : RelOptInfo *innerrel,
991 : Path *outerpath,
992 : JoinType jointype,
993 : JoinPathExtraData *extra,
994 : bool useallclauses,
995 : Path *inner_cheapest_total,
996 : List *merge_pathkeys,
997 : bool is_partial)
998 : {
999 : List *mergeclauses;
1000 : List *innersortkeys;
1001 : List *trialsortkeys;
1002 : Path *cheapest_startup_inner;
1003 : Path *cheapest_total_inner;
1004 22947 : JoinType save_jointype = jointype;
1005 : int num_sortkeys;
1006 : int sortkeycnt;
1007 :
1008 22947 : if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)
1009 340 : jointype = JOIN_INNER;
1010 :
1011 : /* Look for useful mergeclauses (if any) */
1012 22947 : mergeclauses = find_mergeclauses_for_pathkeys(root,
1013 : outerpath->pathkeys,
1014 : true,
1015 : extra->mergeclause_list);
1016 :
1017 : /*
1018 : * Done with this outer path if no chance for a mergejoin.
1019 : *
1020 : * Special corner case: for "x FULL JOIN y ON true", there will be no join
1021 : * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1022 : * but since mergejoin is our only join type that supports FULL JOIN
1023 : * without any join clauses, it's necessary to generate a clauseless
1024 : * mergejoin path instead.
1025 : */
1026 22947 : if (mergeclauses == NIL)
1027 : {
1028 16777 : if (jointype == JOIN_FULL)
1029 : /* okay to try for mergejoin */ ;
1030 : else
1031 16721 : return;
1032 : }
1033 7051 : if (useallclauses &&
1034 825 : list_length(mergeclauses) != list_length(extra->mergeclause_list))
1035 58 : return;
1036 :
1037 : /* Compute the required ordering of the inner path */
1038 6168 : innersortkeys = make_inner_pathkeys_for_merge(root,
1039 : mergeclauses,
1040 : outerpath->pathkeys);
1041 :
1042 : /*
1043 : * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1044 : * a sort will be needed, only cheapest total cost matters. (But
1045 : * try_mergejoin_path will do the right thing if inner_cheapest_total is
1046 : * already correctly sorted.)
1047 : */
1048 6168 : try_mergejoin_path(root,
1049 : joinrel,
1050 : outerpath,
1051 : inner_cheapest_total,
1052 : merge_pathkeys,
1053 : mergeclauses,
1054 : NIL,
1055 : innersortkeys,
1056 : jointype,
1057 : extra,
1058 : is_partial);
1059 :
1060 : /* Can't do anything else if inner path needs to be unique'd */
1061 6168 : if (save_jointype == JOIN_UNIQUE_INNER)
1062 18 : return;
1063 :
1064 : /*
1065 : * Look for presorted inner paths that satisfy the innersortkey list ---
1066 : * or any truncation thereof, if we are allowed to build a mergejoin using
1067 : * a subset of the merge clauses. Here, we consider both cheap startup
1068 : * cost and cheap total cost.
1069 : *
1070 : * Currently we do not consider parameterized inner paths here. This
1071 : * interacts with decisions elsewhere that also discriminate against
1072 : * mergejoins with parameterized inputs; see comments in
1073 : * src/backend/optimizer/README.
1074 : *
1075 : * As we shorten the sortkey list, we should consider only paths that are
1076 : * strictly cheaper than (in particular, not the same as) any path found
1077 : * in an earlier iteration. Otherwise we'd be intentionally using fewer
1078 : * merge keys than a given path allows (treating the rest as plain
1079 : * joinquals), which is unlikely to be a good idea. Also, eliminating
1080 : * paths here on the basis of compare_path_costs is a lot cheaper than
1081 : * building the mergejoin path only to throw it away.
1082 : *
1083 : * If inner_cheapest_total is well enough sorted to have not required a
1084 : * sort in the path made above, we shouldn't make a duplicate path with
1085 : * it, either. We handle that case with the same logic that handles the
1086 : * previous consideration, by initializing the variables that track
1087 : * cheapest-so-far properly. Note that we do NOT reject
1088 : * inner_cheapest_total if we find it matches some shorter set of
1089 : * pathkeys. That case corresponds to using fewer mergekeys to avoid
1090 : * sorting inner_cheapest_total, whereas we did sort it above, so the
1091 : * plans being considered are different.
1092 : */
1093 6150 : if (pathkeys_contained_in(innersortkeys,
1094 : inner_cheapest_total->pathkeys))
1095 : {
1096 : /* inner_cheapest_total didn't require a sort */
1097 92 : cheapest_startup_inner = inner_cheapest_total;
1098 92 : cheapest_total_inner = inner_cheapest_total;
1099 : }
1100 : else
1101 : {
1102 : /* it did require a sort, at least for the full set of keys */
1103 6058 : cheapest_startup_inner = NULL;
1104 6058 : cheapest_total_inner = NULL;
1105 : }
1106 6150 : num_sortkeys = list_length(innersortkeys);
1107 6150 : if (num_sortkeys > 1 && !useallclauses)
1108 151 : trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */
1109 : else
1110 5999 : trialsortkeys = innersortkeys; /* won't really truncate */
1111 :
1112 11686 : for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1113 : {
1114 : Path *innerpath;
1115 6297 : List *newclauses = NIL;
1116 :
1117 : /*
1118 : * Look for an inner path ordered well enough for the first
1119 : * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1120 : * destructively, which is why we made a copy...
1121 : */
1122 6297 : trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
1123 6297 : innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1124 : trialsortkeys,
1125 : NULL,
1126 : TOTAL_COST,
1127 : is_partial);
1128 6297 : if (innerpath != NULL &&
1129 172 : (cheapest_total_inner == NULL ||
1130 172 : compare_path_costs(innerpath, cheapest_total_inner,
1131 : TOTAL_COST) < 0))
1132 : {
1133 : /* Found a cheap (or even-cheaper) sorted path */
1134 : /* Select the right mergeclauses, if we didn't already */
1135 3005 : if (sortkeycnt < num_sortkeys)
1136 : {
1137 24 : newclauses =
1138 : find_mergeclauses_for_pathkeys(root,
1139 : trialsortkeys,
1140 : false,
1141 : mergeclauses);
1142 24 : Assert(newclauses != NIL);
1143 : }
1144 : else
1145 2981 : newclauses = mergeclauses;
1146 3005 : try_mergejoin_path(root,
1147 : joinrel,
1148 : outerpath,
1149 : innerpath,
1150 : merge_pathkeys,
1151 : newclauses,
1152 : NIL,
1153 : NIL,
1154 : jointype,
1155 : extra,
1156 : is_partial);
1157 3005 : cheapest_total_inner = innerpath;
1158 : }
1159 : /* Same on the basis of cheapest startup cost ... */
1160 6297 : innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1161 : trialsortkeys,
1162 : NULL,
1163 : STARTUP_COST,
1164 : is_partial);
1165 6297 : if (innerpath != NULL &&
1166 172 : (cheapest_startup_inner == NULL ||
1167 172 : compare_path_costs(innerpath, cheapest_startup_inner,
1168 : STARTUP_COST) < 0))
1169 : {
1170 : /* Found a cheap (or even-cheaper) sorted path */
1171 2998 : if (innerpath != cheapest_total_inner)
1172 : {
1173 : /*
1174 : * Avoid rebuilding clause list if we already made one; saves
1175 : * memory in big join trees...
1176 : */
1177 2 : if (newclauses == NIL)
1178 : {
1179 0 : if (sortkeycnt < num_sortkeys)
1180 : {
1181 0 : newclauses =
1182 : find_mergeclauses_for_pathkeys(root,
1183 : trialsortkeys,
1184 : false,
1185 : mergeclauses);
1186 0 : Assert(newclauses != NIL);
1187 : }
1188 : else
1189 0 : newclauses = mergeclauses;
1190 : }
1191 2 : try_mergejoin_path(root,
1192 : joinrel,
1193 : outerpath,
1194 : innerpath,
1195 : merge_pathkeys,
1196 : newclauses,
1197 : NIL,
1198 : NIL,
1199 : jointype,
1200 : extra,
1201 : is_partial);
1202 : }
1203 2998 : cheapest_startup_inner = innerpath;
1204 : }
1205 :
1206 : /*
1207 : * Don't consider truncated sortkeys if we need all clauses.
1208 : */
1209 6297 : if (useallclauses)
1210 761 : break;
1211 : }
1212 : }
1213 :
1214 : /*
1215 : * match_unsorted_outer
1216 : * Creates possible join paths for processing a single join relation
1217 : * 'joinrel' by employing either iterative substitution or
1218 : * mergejoining on each of its possible outer paths (considering
1219 : * only outer paths that are already ordered well enough for merging).
1220 : *
1221 : * We always generate a nestloop path for each available outer path.
1222 : * In fact we may generate as many as five: one on the cheapest-total-cost
1223 : * inner path, one on the same with materialization, one on the
1224 : * cheapest-startup-cost inner path (if different), one on the
1225 : * cheapest-total inner-indexscan path (if any), and one on the
1226 : * cheapest-startup inner-indexscan path (if different).
1227 : *
1228 : * We also consider mergejoins if mergejoin clauses are available. See
1229 : * detailed comments in generate_mergejoin_paths.
1230 : *
1231 : * 'joinrel' is the join relation
1232 : * 'outerrel' is the outer join relation
1233 : * 'innerrel' is the inner join relation
1234 : * 'jointype' is the type of join to do
1235 : * 'extra' contains additional input values
1236 : */
1237 : static void
1238 14729 : match_unsorted_outer(PlannerInfo *root,
1239 : RelOptInfo *joinrel,
1240 : RelOptInfo *outerrel,
1241 : RelOptInfo *innerrel,
1242 : JoinType jointype,
1243 : JoinPathExtraData *extra)
1244 : {
1245 14729 : JoinType save_jointype = jointype;
1246 : bool nestjoinOK;
1247 : bool useallclauses;
1248 14729 : Path *inner_cheapest_total = innerrel->cheapest_total_path;
1249 14729 : Path *matpath = NULL;
1250 : ListCell *lc1;
1251 :
1252 : /*
1253 : * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1254 : * are doing a right or full mergejoin, we must use *all* the mergeclauses
1255 : * as join clauses, else we will not have a valid plan. (Although these
1256 : * two flags are currently inverses, keep them separate for clarity and
1257 : * possible future changes.)
1258 : */
1259 14729 : switch (jointype)
1260 : {
1261 : case JOIN_INNER:
1262 : case JOIN_LEFT:
1263 : case JOIN_SEMI:
1264 : case JOIN_ANTI:
1265 13054 : nestjoinOK = true;
1266 13054 : useallclauses = false;
1267 13054 : break;
1268 : case JOIN_RIGHT:
1269 : case JOIN_FULL:
1270 1045 : nestjoinOK = false;
1271 1045 : useallclauses = true;
1272 1045 : break;
1273 : case JOIN_UNIQUE_OUTER:
1274 : case JOIN_UNIQUE_INNER:
1275 630 : jointype = JOIN_INNER;
1276 630 : nestjoinOK = true;
1277 630 : useallclauses = false;
1278 630 : break;
1279 : default:
1280 0 : elog(ERROR, "unrecognized join type: %d",
1281 : (int) jointype);
1282 : nestjoinOK = false; /* keep compiler quiet */
1283 : useallclauses = false;
1284 : break;
1285 : }
1286 :
1287 : /*
1288 : * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1289 : * we will consider it below as a member of cheapest_parameterized_paths,
1290 : * but the other possibilities considered in this routine aren't usable.
1291 : */
1292 14729 : if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1293 235 : inner_cheapest_total = NULL;
1294 :
1295 : /*
1296 : * If we need to unique-ify the inner path, we will consider only the
1297 : * cheapest-total inner.
1298 : */
1299 14729 : if (save_jointype == JOIN_UNIQUE_INNER)
1300 : {
1301 : /* No way to do this with an inner path parameterized by outer rel */
1302 315 : if (inner_cheapest_total == NULL)
1303 0 : return;
1304 315 : inner_cheapest_total = (Path *)
1305 315 : create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1306 315 : Assert(inner_cheapest_total);
1307 : }
1308 14414 : else if (nestjoinOK)
1309 : {
1310 : /*
1311 : * Consider materializing the cheapest inner path, unless
1312 : * enable_material is off or the path in question materializes its
1313 : * output anyway.
1314 : */
1315 26489 : if (enable_material && inner_cheapest_total != NULL &&
1316 13120 : !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1317 12691 : matpath = (Path *)
1318 : create_material_path(innerrel, inner_cheapest_total);
1319 : }
1320 :
1321 43051 : foreach(lc1, outerrel->pathlist)
1322 : {
1323 28322 : Path *outerpath = (Path *) lfirst(lc1);
1324 : List *merge_pathkeys;
1325 :
1326 : /*
1327 : * We cannot use an outer path that is parameterized by the inner rel.
1328 : */
1329 28322 : if (PATH_PARAM_BY_REL(outerpath, innerrel))
1330 4831 : continue;
1331 :
1332 : /*
1333 : * If we need to unique-ify the outer path, it's pointless to consider
1334 : * any but the cheapest outer. (XXX we don't consider parameterized
1335 : * outers, nor inners, for unique-ified cases. Should we?)
1336 : */
1337 23491 : if (save_jointype == JOIN_UNIQUE_OUTER)
1338 : {
1339 323 : if (outerpath != outerrel->cheapest_total_path)
1340 8 : continue;
1341 315 : outerpath = (Path *) create_unique_path(root, outerrel,
1342 : outerpath, extra->sjinfo);
1343 315 : Assert(outerpath);
1344 : }
1345 :
1346 : /*
1347 : * The result will have this sort order (even if it is implemented as
1348 : * a nestloop, and even if some of the mergeclauses are implemented by
1349 : * qpquals rather than as true mergeclauses):
1350 : */
1351 23483 : merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1352 : outerpath->pathkeys);
1353 :
1354 23483 : if (save_jointype == JOIN_UNIQUE_INNER)
1355 : {
1356 : /*
1357 : * Consider nestloop join, but only with the unique-ified cheapest
1358 : * inner path
1359 : */
1360 337 : try_nestloop_path(root,
1361 : joinrel,
1362 : outerpath,
1363 : inner_cheapest_total,
1364 : merge_pathkeys,
1365 : jointype,
1366 : extra);
1367 : }
1368 23146 : else if (nestjoinOK)
1369 : {
1370 : /*
1371 : * Consider nestloop joins using this outer path and various
1372 : * available paths for the inner relation. We consider the
1373 : * cheapest-total paths for each available parameterization of the
1374 : * inner relation, including the unparameterized case.
1375 : */
1376 : ListCell *lc2;
1377 :
1378 53957 : foreach(lc2, innerrel->cheapest_parameterized_paths)
1379 : {
1380 32609 : Path *innerpath = (Path *) lfirst(lc2);
1381 :
1382 32609 : try_nestloop_path(root,
1383 : joinrel,
1384 : outerpath,
1385 : innerpath,
1386 : merge_pathkeys,
1387 : jointype,
1388 : extra);
1389 : }
1390 :
1391 : /* Also consider materialized form of the cheapest inner path */
1392 21348 : if (matpath != NULL)
1393 20621 : try_nestloop_path(root,
1394 : joinrel,
1395 : outerpath,
1396 : matpath,
1397 : merge_pathkeys,
1398 : jointype,
1399 : extra);
1400 : }
1401 :
1402 : /* Can't do anything else if outer path needs to be unique'd */
1403 23483 : if (save_jointype == JOIN_UNIQUE_OUTER)
1404 315 : continue;
1405 :
1406 : /* Can't do anything else if inner rel is parameterized by outer */
1407 23168 : if (inner_cheapest_total == NULL)
1408 256 : continue;
1409 :
1410 : /* Generate merge join paths */
1411 22912 : generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
1412 : save_jointype, extra, useallclauses,
1413 : inner_cheapest_total, merge_pathkeys,
1414 : false);
1415 : }
1416 :
1417 : /*
1418 : * Consider partial nestloop and mergejoin plan if outerrel has any
1419 : * partial path and the joinrel is parallel-safe. However, we can't
1420 : * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
1421 : * therefore we won't be able to properly guarantee uniqueness. Nor can
1422 : * we handle extra_lateral_rels, since partial paths must not be
1423 : * parameterized. Similarly, we can't handle JOIN_FULL and JOIN_RIGHT,
1424 : * because they can produce false null extended rows.
1425 : */
1426 14729 : if (joinrel->consider_parallel &&
1427 8973 : save_jointype != JOIN_UNIQUE_OUTER &&
1428 8927 : save_jointype != JOIN_FULL &&
1429 8161 : save_jointype != JOIN_RIGHT &&
1430 8196 : outerrel->partial_pathlist != NIL &&
1431 35 : bms_is_empty(joinrel->lateral_relids))
1432 : {
1433 35 : if (nestjoinOK)
1434 35 : consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
1435 : save_jointype, extra);
1436 :
1437 : /*
1438 : * If inner_cheapest_total is NULL or non parallel-safe then find the
1439 : * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
1440 : * can't use any alternative inner path.
1441 : */
1442 70 : if (inner_cheapest_total == NULL ||
1443 35 : !inner_cheapest_total->parallel_safe)
1444 : {
1445 6 : if (save_jointype == JOIN_UNIQUE_INNER)
1446 0 : return;
1447 :
1448 6 : inner_cheapest_total = get_cheapest_parallel_safe_total_inner(
1449 : innerrel->pathlist);
1450 : }
1451 :
1452 35 : if (inner_cheapest_total)
1453 35 : consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
1454 : save_jointype, extra,
1455 : inner_cheapest_total);
1456 : }
1457 : }
1458 :
1459 : /*
1460 : * consider_parallel_mergejoin
1461 : * Try to build partial paths for a joinrel by joining a partial path
1462 : * for the outer relation to a complete path for the inner relation.
1463 : *
1464 : * 'joinrel' is the join relation
1465 : * 'outerrel' is the outer join relation
1466 : * 'innerrel' is the inner join relation
1467 : * 'jointype' is the type of join to do
1468 : * 'extra' contains additional input values
1469 : * 'inner_cheapest_total' cheapest total path for innerrel
1470 : */
1471 : static void
1472 35 : consider_parallel_mergejoin(PlannerInfo *root,
1473 : RelOptInfo *joinrel,
1474 : RelOptInfo *outerrel,
1475 : RelOptInfo *innerrel,
1476 : JoinType jointype,
1477 : JoinPathExtraData *extra,
1478 : Path *inner_cheapest_total)
1479 : {
1480 : ListCell *lc1;
1481 :
1482 : /* generate merge join path for each partial outer path */
1483 70 : foreach(lc1, outerrel->partial_pathlist)
1484 : {
1485 35 : Path *outerpath = (Path *) lfirst(lc1);
1486 : List *merge_pathkeys;
1487 :
1488 : /*
1489 : * Figure out what useful ordering any paths we create will have.
1490 : */
1491 35 : merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1492 : outerpath->pathkeys);
1493 :
1494 35 : generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
1495 : extra, false, inner_cheapest_total,
1496 : merge_pathkeys, true);
1497 : }
1498 35 : }
1499 :
1500 : /*
1501 : * consider_parallel_nestloop
1502 : * Try to build partial paths for a joinrel by joining a partial path for the
1503 : * outer relation to a complete path for the inner relation.
1504 : *
1505 : * 'joinrel' is the join relation
1506 : * 'outerrel' is the outer join relation
1507 : * 'innerrel' is the inner join relation
1508 : * 'jointype' is the type of join to do
1509 : * 'extra' contains additional input values
1510 : */
1511 : static void
1512 35 : consider_parallel_nestloop(PlannerInfo *root,
1513 : RelOptInfo *joinrel,
1514 : RelOptInfo *outerrel,
1515 : RelOptInfo *innerrel,
1516 : JoinType jointype,
1517 : JoinPathExtraData *extra)
1518 : {
1519 35 : JoinType save_jointype = jointype;
1520 : ListCell *lc1;
1521 :
1522 35 : if (jointype == JOIN_UNIQUE_INNER)
1523 3 : jointype = JOIN_INNER;
1524 :
1525 70 : foreach(lc1, outerrel->partial_pathlist)
1526 : {
1527 35 : Path *outerpath = (Path *) lfirst(lc1);
1528 : List *pathkeys;
1529 : ListCell *lc2;
1530 :
1531 : /* Figure out what useful ordering any paths we create will have. */
1532 35 : pathkeys = build_join_pathkeys(root, joinrel, jointype,
1533 : outerpath->pathkeys);
1534 :
1535 : /*
1536 : * Try the cheapest parameterized paths; only those which will produce
1537 : * an unparameterized path when joined to this outerrel will survive
1538 : * try_partial_nestloop_path. The cheapest unparameterized path is
1539 : * also in this list.
1540 : */
1541 93 : foreach(lc2, innerrel->cheapest_parameterized_paths)
1542 : {
1543 58 : Path *innerpath = (Path *) lfirst(lc2);
1544 :
1545 : /* Can't join to an inner path that is not parallel-safe */
1546 58 : if (!innerpath->parallel_safe)
1547 6 : continue;
1548 :
1549 : /*
1550 : * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
1551 : * cheapest_total_path, and we have to unique-ify it. (We might
1552 : * be able to relax this to allow other safe, unparameterized
1553 : * inner paths, but right now create_unique_path is not on board
1554 : * with that.)
1555 : */
1556 52 : if (save_jointype == JOIN_UNIQUE_INNER)
1557 : {
1558 4 : if (innerpath != innerrel->cheapest_total_path)
1559 1 : continue;
1560 3 : innerpath = (Path *) create_unique_path(root, innerrel,
1561 : innerpath,
1562 : extra->sjinfo);
1563 3 : Assert(innerpath);
1564 : }
1565 :
1566 51 : try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
1567 : pathkeys, jointype, extra);
1568 : }
1569 : }
1570 35 : }
1571 :
1572 : /*
1573 : * hash_inner_and_outer
1574 : * Create hashjoin join paths by explicitly hashing both the outer and
1575 : * inner keys of each available hash clause.
1576 : *
1577 : * 'joinrel' is the join relation
1578 : * 'outerrel' is the outer join relation
1579 : * 'innerrel' is the inner join relation
1580 : * 'jointype' is the type of join to do
1581 : * 'extra' contains additional input values
1582 : */
1583 : static void
1584 14964 : hash_inner_and_outer(PlannerInfo *root,
1585 : RelOptInfo *joinrel,
1586 : RelOptInfo *outerrel,
1587 : RelOptInfo *innerrel,
1588 : JoinType jointype,
1589 : JoinPathExtraData *extra)
1590 : {
1591 14964 : JoinType save_jointype = jointype;
1592 14964 : bool isouterjoin = IS_OUTER_JOIN(jointype);
1593 : List *hashclauses;
1594 : ListCell *l;
1595 :
1596 : /*
1597 : * We need to build only one hashclauses list for any given pair of outer
1598 : * and inner relations; all of the hashable clauses will be used as keys.
1599 : *
1600 : * Scan the join's restrictinfo list to find hashjoinable clauses that are
1601 : * usable with this pair of sub-relations.
1602 : */
1603 14964 : hashclauses = NIL;
1604 28552 : foreach(l, extra->restrictlist)
1605 : {
1606 13588 : RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1607 :
1608 : /*
1609 : * If processing an outer join, only use its own join clauses for
1610 : * hashing. For inner joins we need not be so picky.
1611 : */
1612 13588 : if (isouterjoin && restrictinfo->is_pushed_down)
1613 80 : continue;
1614 :
1615 25641 : if (!restrictinfo->can_join ||
1616 12133 : restrictinfo->hashjoinoperator == InvalidOid)
1617 1698 : continue; /* not hashjoinable */
1618 :
1619 : /*
1620 : * Check if clause has the form "outer op inner" or "inner op outer".
1621 : */
1622 11810 : if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
1623 98 : continue; /* no good for these input relations */
1624 :
1625 11712 : hashclauses = lappend(hashclauses, restrictinfo);
1626 : }
1627 :
1628 : /* If we found any usable hashclauses, make paths */
1629 14964 : if (hashclauses)
1630 : {
1631 : /*
1632 : * We consider both the cheapest-total-cost and cheapest-startup-cost
1633 : * outer paths. There's no need to consider any but the
1634 : * cheapest-total-cost inner path, however.
1635 : */
1636 10856 : Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
1637 10856 : Path *cheapest_total_outer = outerrel->cheapest_total_path;
1638 10856 : Path *cheapest_total_inner = innerrel->cheapest_total_path;
1639 :
1640 : /*
1641 : * If either cheapest-total path is parameterized by the other rel, we
1642 : * can't use a hashjoin. (There's no use looking for alternative
1643 : * input paths, since these should already be the least-parameterized
1644 : * available paths.)
1645 : */
1646 21676 : if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
1647 10870 : PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
1648 15036 : return;
1649 :
1650 : /* Unique-ify if need be; we ignore parameterized possibilities */
1651 10784 : if (jointype == JOIN_UNIQUE_OUTER)
1652 : {
1653 46 : cheapest_total_outer = (Path *)
1654 46 : create_unique_path(root, outerrel,
1655 : cheapest_total_outer, extra->sjinfo);
1656 46 : Assert(cheapest_total_outer);
1657 46 : jointype = JOIN_INNER;
1658 46 : try_hashjoin_path(root,
1659 : joinrel,
1660 : cheapest_total_outer,
1661 : cheapest_total_inner,
1662 : hashclauses,
1663 : jointype,
1664 : extra);
1665 : /* no possibility of cheap startup here */
1666 : }
1667 10738 : else if (jointype == JOIN_UNIQUE_INNER)
1668 : {
1669 46 : cheapest_total_inner = (Path *)
1670 46 : create_unique_path(root, innerrel,
1671 : cheapest_total_inner, extra->sjinfo);
1672 46 : Assert(cheapest_total_inner);
1673 46 : jointype = JOIN_INNER;
1674 46 : try_hashjoin_path(root,
1675 : joinrel,
1676 : cheapest_total_outer,
1677 : cheapest_total_inner,
1678 : hashclauses,
1679 : jointype,
1680 : extra);
1681 46 : if (cheapest_startup_outer != NULL &&
1682 : cheapest_startup_outer != cheapest_total_outer)
1683 1 : try_hashjoin_path(root,
1684 : joinrel,
1685 : cheapest_startup_outer,
1686 : cheapest_total_inner,
1687 : hashclauses,
1688 : jointype,
1689 : extra);
1690 : }
1691 : else
1692 : {
1693 : /*
1694 : * For other jointypes, we consider the cheapest startup outer
1695 : * together with the cheapest total inner, and then consider
1696 : * pairings of cheapest-total paths including parameterized ones.
1697 : * There is no use in generating parameterized paths on the basis
1698 : * of possibly cheap startup cost, so this is sufficient.
1699 : */
1700 : ListCell *lc1;
1701 : ListCell *lc2;
1702 :
1703 10692 : if (cheapest_startup_outer != NULL)
1704 10682 : try_hashjoin_path(root,
1705 : joinrel,
1706 : cheapest_startup_outer,
1707 : cheapest_total_inner,
1708 : hashclauses,
1709 : jointype,
1710 : extra);
1711 :
1712 26839 : foreach(lc1, outerrel->cheapest_parameterized_paths)
1713 : {
1714 16147 : Path *outerpath = (Path *) lfirst(lc1);
1715 :
1716 : /*
1717 : * We cannot use an outer path that is parameterized by the
1718 : * inner rel.
1719 : */
1720 16147 : if (PATH_PARAM_BY_REL(outerpath, innerrel))
1721 4661 : continue;
1722 :
1723 29194 : foreach(lc2, innerrel->cheapest_parameterized_paths)
1724 : {
1725 17708 : Path *innerpath = (Path *) lfirst(lc2);
1726 :
1727 : /*
1728 : * We cannot use an inner path that is parameterized by
1729 : * the outer rel, either.
1730 : */
1731 17708 : if (PATH_PARAM_BY_REL(innerpath, outerrel))
1732 5338 : continue;
1733 :
1734 12370 : if (outerpath == cheapest_startup_outer &&
1735 : innerpath == cheapest_total_inner)
1736 9343 : continue; /* already tried it */
1737 :
1738 3027 : try_hashjoin_path(root,
1739 : joinrel,
1740 : outerpath,
1741 : innerpath,
1742 : hashclauses,
1743 : jointype,
1744 : extra);
1745 : }
1746 : }
1747 : }
1748 :
1749 : /*
1750 : * If the joinrel is parallel-safe, we may be able to consider a
1751 : * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER,
1752 : * because the outer path will be partial, and therefore we won't be
1753 : * able to properly guarantee uniqueness. Similarly, we can't handle
1754 : * JOIN_FULL and JOIN_RIGHT, because they can produce false null
1755 : * extended rows. Also, the resulting path must not be parameterized.
1756 : */
1757 10784 : if (joinrel->consider_parallel &&
1758 6809 : save_jointype != JOIN_UNIQUE_OUTER &&
1759 6769 : save_jointype != JOIN_FULL &&
1760 5837 : save_jointype != JOIN_RIGHT &&
1761 5856 : outerrel->partial_pathlist != NIL &&
1762 19 : bms_is_empty(joinrel->lateral_relids))
1763 : {
1764 : Path *cheapest_partial_outer;
1765 19 : Path *cheapest_safe_inner = NULL;
1766 :
1767 19 : cheapest_partial_outer =
1768 19 : (Path *) linitial(outerrel->partial_pathlist);
1769 :
1770 : /*
1771 : * Normally, given that the joinrel is parallel-safe, the cheapest
1772 : * total inner path will also be parallel-safe, but if not, we'll
1773 : * have to search for the cheapest safe, unparameterized inner
1774 : * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
1775 : * inner path.
1776 : */
1777 19 : if (cheapest_total_inner->parallel_safe)
1778 19 : cheapest_safe_inner = cheapest_total_inner;
1779 0 : else if (save_jointype != JOIN_UNIQUE_INNER)
1780 0 : cheapest_safe_inner =
1781 0 : get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
1782 :
1783 19 : if (cheapest_safe_inner != NULL)
1784 19 : try_partial_hashjoin_path(root, joinrel,
1785 : cheapest_partial_outer,
1786 : cheapest_safe_inner,
1787 : hashclauses, jointype, extra);
1788 : }
1789 : }
1790 : }
1791 :
1792 : /*
1793 : * select_mergejoin_clauses
1794 : * Select mergejoin clauses that are usable for a particular join.
1795 : * Returns a list of RestrictInfo nodes for those clauses.
1796 : *
1797 : * *mergejoin_allowed is normally set to TRUE, but it is set to FALSE if
1798 : * this is a right/full join and there are nonmergejoinable join clauses.
1799 : * The executor's mergejoin machinery cannot handle such cases, so we have
1800 : * to avoid generating a mergejoin plan. (Note that this flag does NOT
1801 : * consider whether there are actually any mergejoinable clauses. This is
1802 : * correct because in some cases we need to build a clauseless mergejoin.
1803 : * Simply returning NIL is therefore not enough to distinguish safe from
1804 : * unsafe cases.)
1805 : *
1806 : * We also mark each selected RestrictInfo to show which side is currently
1807 : * being considered as outer. These are transient markings that are only
1808 : * good for the duration of the current add_paths_to_joinrel() call!
1809 : *
1810 : * We examine each restrictinfo clause known for the join to see
1811 : * if it is mergejoinable and involves vars from the two sub-relations
1812 : * currently of interest.
1813 : */
1814 : static List *
1815 14994 : select_mergejoin_clauses(PlannerInfo *root,
1816 : RelOptInfo *joinrel,
1817 : RelOptInfo *outerrel,
1818 : RelOptInfo *innerrel,
1819 : List *restrictlist,
1820 : JoinType jointype,
1821 : bool *mergejoin_allowed)
1822 : {
1823 14994 : List *result_list = NIL;
1824 14994 : bool isouterjoin = IS_OUTER_JOIN(jointype);
1825 14994 : bool have_nonmergeable_joinclause = false;
1826 : ListCell *l;
1827 :
1828 28624 : foreach(l, restrictlist)
1829 : {
1830 13630 : RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1831 :
1832 : /*
1833 : * If processing an outer join, only use its own join clauses in the
1834 : * merge. For inner joins we can use pushed-down clauses too. (Note:
1835 : * we don't set have_nonmergeable_joinclause here because pushed-down
1836 : * clauses will become otherquals not joinquals.)
1837 : */
1838 13630 : if (isouterjoin && restrictinfo->is_pushed_down)
1839 84 : continue;
1840 :
1841 : /* Check that clause is a mergeable operator clause */
1842 25717 : if (!restrictinfo->can_join ||
1843 12171 : restrictinfo->mergeopfamilies == NIL)
1844 : {
1845 : /*
1846 : * The executor can handle extra joinquals that are constants, but
1847 : * not anything else, when doing right/full merge join. (The
1848 : * reason to support constants is so we can do FULL JOIN ON
1849 : * FALSE.)
1850 : */
1851 1657 : if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
1852 1655 : have_nonmergeable_joinclause = true;
1853 1657 : continue; /* not mergejoinable */
1854 : }
1855 :
1856 : /*
1857 : * Check if clause has the form "outer op inner" or "inner op outer".
1858 : */
1859 11889 : if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
1860 : {
1861 106 : have_nonmergeable_joinclause = true;
1862 106 : continue; /* no good for these input relations */
1863 : }
1864 :
1865 : /*
1866 : * Insist that each side have a non-redundant eclass. This
1867 : * restriction is needed because various bits of the planner expect
1868 : * that each clause in a merge be associable with some pathkey in a
1869 : * canonical pathkey list, but redundant eclasses can't appear in
1870 : * canonical sort orderings. (XXX it might be worth relaxing this,
1871 : * but not enough time to address it for 8.3.)
1872 : *
1873 : * Note: it would be bad if this condition failed for an otherwise
1874 : * mergejoinable FULL JOIN clause, since that would result in
1875 : * undesirable planner failure. I believe that is not possible
1876 : * however; a variable involved in a full join could only appear in
1877 : * below_outer_join eclasses, which aren't considered redundant.
1878 : *
1879 : * This case *can* happen for left/right join clauses: the outer-side
1880 : * variable could be equated to a constant. Because we will propagate
1881 : * that constant across the join clause, the loss of ability to do a
1882 : * mergejoin is not really all that big a deal, and so it's not clear
1883 : * that improving this is important.
1884 : */
1885 11783 : update_mergeclause_eclasses(root, restrictinfo);
1886 :
1887 23536 : if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
1888 11995 : EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
1889 : {
1890 250 : have_nonmergeable_joinclause = true;
1891 250 : continue; /* can't handle redundant eclasses */
1892 : }
1893 :
1894 11533 : result_list = lappend(result_list, restrictinfo);
1895 : }
1896 :
1897 : /*
1898 : * Report whether mergejoin is allowed (see comment at top of function).
1899 : */
1900 14994 : switch (jointype)
1901 : {
1902 : case JOIN_RIGHT:
1903 : case JOIN_FULL:
1904 1358 : *mergejoin_allowed = !have_nonmergeable_joinclause;
1905 1358 : break;
1906 : default:
1907 13636 : *mergejoin_allowed = true;
1908 13636 : break;
1909 : }
1910 :
1911 14994 : return result_list;
1912 : }
|
