Debian Codegraph @

src/backend/optimizer/path/joinpath.c

raw
1 /*-------------------------------------------------------------------------
2 *
3 * joinpath.c
4 * Routines to find all possible paths for processing a set of joins
5 *
6 * Portions Copyright (c) 1996-2025, 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 "nodes/nodeFuncs.h"
22 #include "optimizer/cost.h"
23 #include "optimizer/optimizer.h"
24 #include "optimizer/pathnode.h"
25 #include "optimizer/paths.h"
26 #include "optimizer/placeholder.h"
27 #include "optimizer/planmain.h"
28 #include "optimizer/restrictinfo.h"
29 #include "utils/lsyscache.h"
30 #include "utils/typcache.h"
31
32 /* Hook for plugins to get control in add_paths_to_joinrel() */
33 set_join_pathlist_hook_type set_join_pathlist_hook = NULL;
34
35 /*
36 * Paths parameterized by a parent rel can be considered to be parameterized
37 * by any of its children, when we are performing partitionwise joins. These
38 * macros simplify checking for such cases. Beware multiple eval of args.
39 */
40 #define PATH_PARAM_BY_PARENT(path, rel) \
41 ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), \
42 (rel)->top_parent_relids))
43 #define PATH_PARAM_BY_REL_SELF(path, rel) \
44 ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids))
45
46 #define PATH_PARAM_BY_REL(path, rel) \
47 (PATH_PARAM_BY_REL_SELF(path, rel) || PATH_PARAM_BY_PARENT(path, rel))
48
49 static void try_partial_mergejoin_path(PlannerInfo *root,
50 RelOptInfo *joinrel,
51 Path *outer_path,
52 Path *inner_path,
53 List *pathkeys,
54 List *mergeclauses,
55 List *outersortkeys,
56 List *innersortkeys,
57 JoinType jointype,
58 JoinPathExtraData *extra);
59 static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
60 RelOptInfo *outerrel, RelOptInfo *innerrel,
61 JoinType jointype, JoinPathExtraData *extra);
62 static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel,
63 RelOptInfo *outerrel, RelOptInfo *innerrel,
64 JoinType jointype, JoinPathExtraData *extra);
65 static void consider_parallel_nestloop(PlannerInfo *root,
66 RelOptInfo *joinrel,
67 RelOptInfo *outerrel,
68 RelOptInfo *innerrel,
69 JoinType jointype,
70 JoinPathExtraData *extra);
71 static void consider_parallel_mergejoin(PlannerInfo *root,
72 RelOptInfo *joinrel,
73 RelOptInfo *outerrel,
74 RelOptInfo *innerrel,
75 JoinType jointype,
76 JoinPathExtraData *extra,
77 Path *inner_cheapest_total);
78 static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
79 RelOptInfo *outerrel, RelOptInfo *innerrel,
80 JoinType jointype, JoinPathExtraData *extra);
81 static List *select_mergejoin_clauses(PlannerInfo *root,
82 RelOptInfo *joinrel,
83 RelOptInfo *outerrel,
84 RelOptInfo *innerrel,
85 List *restrictlist,
86 JoinType jointype,
87 bool *mergejoin_allowed);
88 static void generate_mergejoin_paths(PlannerInfo *root,
89 RelOptInfo *joinrel,
90 RelOptInfo *innerrel,
91 Path *outerpath,
92 JoinType jointype,
93 JoinPathExtraData *extra,
94 bool useallclauses,
95 Path *inner_cheapest_total,
96 List *merge_pathkeys,
97 bool is_partial);
98
99
100 /*
101 * add_paths_to_joinrel
102 * Given a join relation and two component rels from which it can be made,
103 * consider all possible paths that use the two component rels as outer
104 * and inner rel respectively. Add these paths to the join rel's pathlist
105 * if they survive comparison with other paths (and remove any existing
106 * paths that are dominated by these paths).
107 *
108 * Modifies the pathlist field of the joinrel node to contain the best
109 * paths found so far.
110 *
111 * jointype is not necessarily the same as sjinfo->jointype; it might be
112 * "flipped around" if we are considering joining the rels in the opposite
113 * direction from what's indicated in sjinfo.
114 *
115 * Also, this routine and others in this module accept the special JoinTypes
116 * JOIN_UNIQUE_OUTER and JOIN_UNIQUE_INNER to indicate that we should
117 * unique-ify the outer or inner relation and then apply a regular inner
118 * join. These values are not allowed to propagate outside this module,
119 * however. Path cost estimation code may need to recognize that it's
120 * dealing with such a case --- the combination of nominal jointype INNER
121 * with sjinfo->jointype == JOIN_SEMI indicates that.
122 */
123 void
124 add_paths_to_joinrel(PlannerInfo *root,
125 RelOptInfo *joinrel,
126 RelOptInfo *outerrel,
127 RelOptInfo *innerrel,
128 JoinType jointype,
129 SpecialJoinInfo *sjinfo,
130 List *restrictlist)
131 {
132 JoinPathExtraData extra;
133 bool mergejoin_allowed = true;
134 ListCell *lc;
135 Relids joinrelids;
136
137 /*
138 * PlannerInfo doesn't contain the SpecialJoinInfos created for joins
139 * between child relations, even if there is a SpecialJoinInfo node for
140 * the join between the topmost parents. So, while calculating Relids set
141 * representing the restriction, consider relids of topmost parent of
142 * partitions.
143 */
144 if (joinrel->reloptkind == RELOPT_OTHER_JOINREL)
145 joinrelids = joinrel->top_parent_relids;
146 else
147 joinrelids = joinrel->relids;
148
149 extra.restrictlist = restrictlist;
150 extra.mergeclause_list = NIL;
151 extra.sjinfo = sjinfo;
152 extra.param_source_rels = NULL;
153
154 /*
155 * See if the inner relation is provably unique for this outer rel.
156 *
157 * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
158 * matter since the executor can make the equivalent optimization anyway;
159 * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
160 * must be considering a semijoin whose inner side is not provably unique
161 * (else reduce_unique_semijoins would've simplified it), so there's no
162 * point in calling innerrel_is_unique. However, if the LHS covers all of
163 * the semijoin's min_lefthand, then it's appropriate to set inner_unique
164 * because the path produced by create_unique_path will be unique relative
165 * to the LHS. (If we have an LHS that's only part of the min_lefthand,
166 * that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
167 * letting that value escape this module.
168 */
169 switch (jointype)
170 {
171 case JOIN_SEMI:
172 case JOIN_ANTI:
173
174 /*
175 * XXX it may be worth proving this to allow a Memoize to be
176 * considered for Nested Loop Semi/Anti Joins.
177 */
178 extra.inner_unique = false; /* well, unproven */
179 break;
180 case JOIN_UNIQUE_INNER:
181 extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
182 outerrel->relids);
183 break;
184 case JOIN_UNIQUE_OUTER:
185 extra.inner_unique = innerrel_is_unique(root,
186 joinrel->relids,
187 outerrel->relids,
188 innerrel,
189 JOIN_INNER,
190 restrictlist,
191 false);
192 break;
193 default:
194 extra.inner_unique = innerrel_is_unique(root,
195 joinrel->relids,
196 outerrel->relids,
197 innerrel,
198 jointype,
199 restrictlist,
200 false);
201 break;
202 }
203
204 /*
205 * Find potential mergejoin clauses. We can skip this if we are not
206 * interested in doing a mergejoin. However, mergejoin may be our only
207 * way of implementing a full outer join, so override enable_mergejoin if
208 * it's a full join.
209 */
210 if (enable_mergejoin || jointype == JOIN_FULL)
211 extra.mergeclause_list = select_mergejoin_clauses(root,
212 joinrel,
213 outerrel,
214 innerrel,
215 restrictlist,
216 jointype,
217 &mergejoin_allowed);
218
219 /*
220 * If it's SEMI, ANTI, or inner_unique join, compute correction factors
221 * for cost estimation. These will be the same for all paths.
222 */
223 if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique)
224 compute_semi_anti_join_factors(root, joinrel, outerrel, innerrel,
225 jointype, sjinfo, restrictlist,
226 &extra.semifactors);
227
228 /*
229 * Decide whether it's sensible to generate parameterized paths for this
230 * joinrel, and if so, which relations such paths should require. There
231 * is usually no need to create a parameterized result path unless there
232 * is a join order restriction that prevents joining one of our input rels
233 * directly to the parameter source rel instead of joining to the other
234 * input rel. (But see allow_star_schema_join().) This restriction
235 * reduces the number of parameterized paths we have to deal with at
236 * higher join levels, without compromising the quality of the resulting
237 * plan. We express the restriction as a Relids set that must overlap the
238 * parameterization of any proposed join path. Note: param_source_rels
239 * should contain only baserels, not OJ relids, so starting from
240 * all_baserels not all_query_rels is correct.
241 */
242 foreach(lc, root->join_info_list)
243 {
244 SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
245
246 /*
247 * SJ is relevant to this join if we have some part of its RHS
248 * (possibly not all of it), and haven't yet joined to its LHS. (This
249 * test is pretty simplistic, but should be sufficient considering the
250 * join has already been proven legal.) If the SJ is relevant, it
251 * presents constraints for joining to anything not in its RHS.
252 */
253 if (bms_overlap(joinrelids, sjinfo2->min_righthand) &&
254 !bms_overlap(joinrelids, sjinfo2->min_lefthand))
255 extra.param_source_rels = bms_join(extra.param_source_rels,
256 bms_difference(root->all_baserels,
257 sjinfo2->min_righthand));
258
259 /* full joins constrain both sides symmetrically */
260 if (sjinfo2->jointype == JOIN_FULL &&
261 bms_overlap(joinrelids, sjinfo2->min_lefthand) &&
262 !bms_overlap(joinrelids, sjinfo2->min_righthand))
263 extra.param_source_rels = bms_join(extra.param_source_rels,
264 bms_difference(root->all_baserels,
265 sjinfo2->min_lefthand));
266 }
267
268 /*
269 * However, when a LATERAL subquery is involved, there will simply not be
270 * any paths for the joinrel that aren't parameterized by whatever the
271 * subquery is parameterized by, unless its parameterization is resolved
272 * within the joinrel. So we might as well allow additional dependencies
273 * on whatever residual lateral dependencies the joinrel will have.
274 */
275 extra.param_source_rels = bms_add_members(extra.param_source_rels,
276 joinrel->lateral_relids);
277
278 /*
279 * 1. Consider mergejoin paths where both relations must be explicitly
280 * sorted. Skip this if we can't mergejoin.
281 */
282 if (mergejoin_allowed)
283 sort_inner_and_outer(root, joinrel, outerrel, innerrel,
284 jointype, &extra);
285
286 /*
287 * 2. Consider paths where the outer relation need not be explicitly
288 * sorted. This includes both nestloops and mergejoins where the outer
289 * path is already ordered. Again, skip this if we can't mergejoin.
290 * (That's okay because we know that nestloop can't handle
291 * right/right-anti/right-semi/full joins at all, so it wouldn't work in
292 * the prohibited cases either.)
293 */
294 if (mergejoin_allowed)
295 match_unsorted_outer(root, joinrel, outerrel, innerrel,
296 jointype, &extra);
297
298 #ifdef NOT_USED
299
300 /*
301 * 3. Consider paths where the inner relation need not be explicitly
302 * sorted. This includes mergejoins only (nestloops were already built in
303 * match_unsorted_outer).
304 *
305 * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
306 * significant difference between the inner and outer side of a mergejoin,
307 * so match_unsorted_inner creates no paths that aren't equivalent to
308 * those made by match_unsorted_outer when add_paths_to_joinrel() is
309 * invoked with the two rels given in the other order.
310 */
311 if (mergejoin_allowed)
312 match_unsorted_inner(root, joinrel, outerrel, innerrel,
313 jointype, &extra);
314 #endif
315
316 /*
317 * 4. Consider paths where both outer and inner relations must be hashed
318 * before being joined. As above, disregard enable_hashjoin for full
319 * joins, because there may be no other alternative.
320 */
321 if (enable_hashjoin || jointype == JOIN_FULL)
322 hash_inner_and_outer(root, joinrel, outerrel, innerrel,
323 jointype, &extra);
324
325 /*
326 * 5. If inner and outer relations are foreign tables (or joins) belonging
327 * to the same server and assigned to the same user to check access
328 * permissions as, give the FDW a chance to push down joins.
329 */
330 if (joinrel->fdwroutine &&
331 joinrel->fdwroutine->GetForeignJoinPaths)
332 joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
333 outerrel, innerrel,
334 jointype, &extra);
335
336 /*
337 * 6. Finally, give extensions a chance to manipulate the path list. They
338 * could add new paths (such as CustomPaths) by calling add_path(), or
339 * add_partial_path() if parallel aware. They could also delete or modify
340 * paths added by the core code.
341 */
342 if (set_join_pathlist_hook)
343 set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
344 jointype, &extra);
345 }
346
347 /*
348 * We override the param_source_rels heuristic to accept nestloop paths in
349 * which the outer rel satisfies some but not all of the inner path's
350 * parameterization. This is necessary to get good plans for star-schema
351 * scenarios, in which a parameterized path for a large table may require
352 * parameters from multiple small tables that will not get joined directly to
353 * each other. We can handle that by stacking nestloops that have the small
354 * tables on the outside; but this breaks the rule the param_source_rels
355 * heuristic is based on, namely that parameters should not be passed down
356 * across joins unless there's a join-order-constraint-based reason to do so.
357 * So we ignore the param_source_rels restriction when this case applies.
358 *
359 * allow_star_schema_join() returns true if the param_source_rels restriction
360 * should be overridden, ie, it's okay to perform this join.
361 */
362 static inline bool
363 allow_star_schema_join(PlannerInfo *root,
364 Relids outerrelids,
365 Relids inner_paramrels)
366 {
367 /*
368 * It's a star-schema case if the outer rel provides some but not all of
369 * the inner rel's parameterization.
370 */
371 return (bms_overlap(inner_paramrels, outerrelids) &&
372 bms_nonempty_difference(inner_paramrels, outerrelids));
373 }
374
375 /*
376 * If the parameterization is only partly satisfied by the outer rel,
377 * the unsatisfied part can't include any outer-join relids that could
378 * null rels of the satisfied part. That would imply that we're trying
379 * to use a clause involving a Var with nonempty varnullingrels at
380 * a join level where that value isn't yet computable.
381 *
382 * In practice, this test never finds a problem because earlier join order
383 * restrictions prevent us from attempting a join that would cause a problem.
384 * (That's unsurprising, because the code worked before we ever added
385 * outer-join relids to expression relids.) It still seems worth checking
386 * as a backstop, but we only do so in assert-enabled builds.
387 */
388 #ifdef USE_ASSERT_CHECKING
389 static inline bool
390 have_unsafe_outer_join_ref(PlannerInfo *root,
391 Relids outerrelids,
392 Relids inner_paramrels)
393 {
394 bool result = false;
395 Relids unsatisfied = bms_difference(inner_paramrels, outerrelids);
396 Relids satisfied = bms_intersect(inner_paramrels, outerrelids);
397
398 if (bms_overlap(unsatisfied, root->outer_join_rels))
399 {
400 ListCell *lc;
401
402 foreach(lc, root->join_info_list)
403 {
404 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
405
406 if (!bms_is_member(sjinfo->ojrelid, unsatisfied))
407 continue; /* not relevant */
408 if (bms_overlap(satisfied, sjinfo->min_righthand) ||
409 (sjinfo->jointype == JOIN_FULL &&
410 bms_overlap(satisfied, sjinfo->min_lefthand)))
411 {
412 result = true; /* doesn't work */
413 break;
414 }
415 }
416 }
417
418 /* Waste no memory when we reject a path here */
419 bms_free(unsatisfied);
420 bms_free(satisfied);
421
422 return result;
423 }
424 #endif /* USE_ASSERT_CHECKING */
425
426 /*
427 * paraminfo_get_equal_hashops
428 * Determine if the clauses in param_info and innerrel's lateral vars
429 * can be hashed.
430 * Returns true if hashing is possible, otherwise false.
431 *
432 * Additionally, on success we collect the outer expressions and the
433 * appropriate equality operators for each hashable parameter to innerrel.
434 * These are returned in parallel lists in *param_exprs and *operators.
435 * We also set *binary_mode to indicate whether strict binary matching is
436 * required.
437 */
438 static bool
439 paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info,
440 RelOptInfo *outerrel, RelOptInfo *innerrel,
441 List *ph_lateral_vars, List **param_exprs,
442 List **operators, bool *binary_mode)
443
444 {
445 List *lateral_vars;
446 ListCell *lc;
447
448 *param_exprs = NIL;
449 *operators = NIL;
450 *binary_mode = false;
451
452 /* Add join clauses from param_info to the hash key */
453 if (param_info != NULL)
454 {
455 List *clauses = param_info->ppi_clauses;
456
457 foreach(lc, clauses)
458 {
459 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
460 OpExpr *opexpr;
461 Node *expr;
462 Oid hasheqoperator;
463
464 opexpr = (OpExpr *) rinfo->clause;
465
466 /*
467 * Bail if the rinfo is not compatible. We need a join OpExpr
468 * with 2 args.
469 */
470 if (!IsA(opexpr, OpExpr) || list_length(opexpr->args) != 2 ||
471 !clause_sides_match_join(rinfo, outerrel->relids,
472 innerrel->relids))
473 {
474 list_free(*operators);
475 list_free(*param_exprs);
476 return false;
477 }
478
479 if (rinfo->outer_is_left)
480 {
481 expr = (Node *) linitial(opexpr->args);
482 hasheqoperator = rinfo->left_hasheqoperator;
483 }
484 else
485 {
486 expr = (Node *) lsecond(opexpr->args);
487 hasheqoperator = rinfo->right_hasheqoperator;
488 }
489
490 /* can't do memoize if we can't hash the outer type */
491 if (!OidIsValid(hasheqoperator))
492 {
493 list_free(*operators);
494 list_free(*param_exprs);
495 return false;
496 }
497
498 /*
499 * 'expr' may already exist as a parameter from a previous item in
500 * ppi_clauses. No need to include it again, however we'd better
501 * ensure we do switch into binary mode if required. See below.
502 */
503 if (!list_member(*param_exprs, expr))
504 {
505 *operators = lappend_oid(*operators, hasheqoperator);
506 *param_exprs = lappend(*param_exprs, expr);
507 }
508
509 /*
510 * When the join operator is not hashable then it's possible that
511 * the operator will be able to distinguish something that the
512 * hash equality operator could not. For example with floating
513 * point types -0.0 and +0.0 are classed as equal by the hash
514 * function and equality function, but some other operator may be
515 * able to tell those values apart. This means that we must put
516 * memoize into binary comparison mode so that it does bit-by-bit
517 * comparisons rather than a "logical" comparison as it would
518 * using the hash equality operator.
519 */
520 if (!OidIsValid(rinfo->hashjoinoperator))
521 *binary_mode = true;
522 }
523 }
524
525 /* Now add any lateral vars to the cache key too */
526 lateral_vars = list_concat(ph_lateral_vars, innerrel->lateral_vars);
527 foreach(lc, lateral_vars)
528 {
529 Node *expr = (Node *) lfirst(lc);
530 TypeCacheEntry *typentry;
531
532 /* Reject if there are any volatile functions in lateral vars */
533 if (contain_volatile_functions(expr))
534 {
535 list_free(*operators);
536 list_free(*param_exprs);
537 return false;
538 }
539
540 typentry = lookup_type_cache(exprType(expr),
541 TYPECACHE_HASH_PROC | TYPECACHE_EQ_OPR);
542
543 /* can't use memoize without a valid hash proc and equals operator */
544 if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr))
545 {
546 list_free(*operators);
547 list_free(*param_exprs);
548 return false;
549 }
550
551 /*
552 * 'expr' may already exist as a parameter from the ppi_clauses. No
553 * need to include it again, however we'd better ensure we do switch
554 * into binary mode.
555 */
556 if (!list_member(*param_exprs, expr))
557 {
558 *operators = lappend_oid(*operators, typentry->eq_opr);
559 *param_exprs = lappend(*param_exprs, expr);
560 }
561
562 /*
563 * We must go into binary mode as we don't have too much of an idea of
564 * how these lateral Vars are being used. See comment above when we
565 * set *binary_mode for the non-lateral Var case. This could be
566 * relaxed a bit if we had the RestrictInfos and knew the operators
567 * being used, however for cases like Vars that are arguments to
568 * functions we must operate in binary mode as we don't have
569 * visibility into what the function is doing with the Vars.
570 */
571 *binary_mode = true;
572 }
573
574 /* We're okay to use memoize */
575 return true;
576 }
577
578 /*
579 * extract_lateral_vars_from_PHVs
580 * Extract lateral references within PlaceHolderVars that are due to be
581 * evaluated at 'innerrelids'.
582 */
583 static List *
584 extract_lateral_vars_from_PHVs(PlannerInfo *root, Relids innerrelids)
585 {
586 List *ph_lateral_vars = NIL;
587 ListCell *lc;
588
589 /* Nothing would be found if the query contains no LATERAL RTEs */
590 if (!root->hasLateralRTEs)
591 return NIL;
592
593 /*
594 * No need to consider PHVs that are due to be evaluated at joinrels,
595 * since we do not add Memoize nodes on top of joinrel paths.
596 */
597 if (bms_membership(innerrelids) == BMS_MULTIPLE)
598 return NIL;
599
600 foreach(lc, root->placeholder_list)
601 {
602 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
603 List *vars;
604 ListCell *cell;
605
606 /* PHV is uninteresting if no lateral refs */
607 if (phinfo->ph_lateral == NULL)
608 continue;
609
610 /* PHV is uninteresting if not due to be evaluated at innerrelids */
611 if (!bms_equal(phinfo->ph_eval_at, innerrelids))
612 continue;
613
614 /*
615 * If the PHV does not reference any rels in innerrelids, use its
616 * contained expression as a cache key rather than extracting the
617 * Vars/PHVs from it and using those. This can be beneficial in cases
618 * where the expression results in fewer distinct values to cache
619 * tuples for.
620 */
621 if (!bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
622 innerrelids))
623 {
624 ph_lateral_vars = lappend(ph_lateral_vars, phinfo->ph_var->phexpr);
625 continue;
626 }
627
628 /* Fetch Vars and PHVs of lateral references within PlaceHolderVars */
629 vars = pull_vars_of_level((Node *) phinfo->ph_var->phexpr, 0);
630 foreach(cell, vars)
631 {
632 Node *node = (Node *) lfirst(cell);
633
634 if (IsA(node, Var))
635 {
636 Var *var = (Var *) node;
637
638 Assert(var->varlevelsup == 0);
639
640 if (bms_is_member(var->varno, phinfo->ph_lateral))
641 ph_lateral_vars = lappend(ph_lateral_vars, node);
642 }
643 else if (IsA(node, PlaceHolderVar))
644 {
645 PlaceHolderVar *phv = (PlaceHolderVar *) node;
646
647 Assert(phv->phlevelsup == 0);
648
649 if (bms_is_subset(find_placeholder_info(root, phv)->ph_eval_at,
650 phinfo->ph_lateral))
651 ph_lateral_vars = lappend(ph_lateral_vars, node);
652 }
653 else
654 Assert(false);
655 }
656
657 list_free(vars);
658 }
659
660 return ph_lateral_vars;
661 }
662
663 /*
664 * get_memoize_path
665 * If possible, make and return a Memoize path atop of 'inner_path'.
666 * Otherwise return NULL.
667 *
668 * Note that currently we do not add Memoize nodes on top of join relation
669 * paths. This is because the ParamPathInfos for join relation paths do not
670 * maintain ppi_clauses, as the set of relevant clauses varies depending on how
671 * the join is formed. In addition, joinrels do not maintain lateral_vars. So
672 * we do not have a way to extract cache keys from joinrels.
673 */
674 static Path *
675 get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
676 RelOptInfo *outerrel, Path *inner_path,
677 Path *outer_path, JoinType jointype,
678 JoinPathExtraData *extra)
679 {
680 List *param_exprs;
681 List *hash_operators;
682 ListCell *lc;
683 bool binary_mode;
684 List *ph_lateral_vars;
685
686 /* Obviously not if it's disabled */
687 if (!enable_memoize)
688 return NULL;
689
690 /*
691 * We can safely not bother with all this unless we expect to perform more
692 * than one inner scan. The first scan is always going to be a cache
693 * miss. This would likely fail later anyway based on costs, so this is
694 * really just to save some wasted effort.
695 */
696 if (outer_path->parent->rows < 2)
697 return NULL;
698
699 /*
700 * Extract lateral Vars/PHVs within PlaceHolderVars that are due to be
701 * evaluated at innerrel. These lateral Vars/PHVs could be used as
702 * memoize cache keys.
703 */
704 ph_lateral_vars = extract_lateral_vars_from_PHVs(root, innerrel->relids);
705
706 /*
707 * We can only have a memoize node when there's some kind of cache key,
708 * either parameterized path clauses or lateral Vars. No cache key sounds
709 * more like something a Materialize node might be more useful for.
710 */
711 if ((inner_path->param_info == NULL ||
712 inner_path->param_info->ppi_clauses == NIL) &&
713 innerrel->lateral_vars == NIL &&
714 ph_lateral_vars == NIL)
715 return NULL;
716
717 /*
718 * Currently we don't do this for SEMI and ANTI joins unless they're
719 * marked as inner_unique. This is because nested loop SEMI/ANTI joins
720 * don't scan the inner node to completion, which will mean memoize cannot
721 * mark the cache entry as complete.
722 *
723 * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
724 * = true. Should we? See add_paths_to_joinrel()
725 */
726 if (!extra->inner_unique && (jointype == JOIN_SEMI ||
727 jointype == JOIN_ANTI))
728 return NULL;
729
730 /*
731 * Memoize normally marks cache entries as complete when it runs out of
732 * tuples to read from its subplan. However, with unique joins, Nested
733 * Loop will skip to the next outer tuple after finding the first matching
734 * inner tuple. This means that we may not read the inner side of the
735 * join to completion which leaves no opportunity to mark the cache entry
736 * as complete. To work around that, when the join is unique we
737 * automatically mark cache entries as complete after fetching the first
738 * tuple. This works when the entire join condition is parameterized.
739 * Otherwise, when the parameterization is only a subset of the join
740 * condition, we can't be sure which part of it causes the join to be
741 * unique. This means there are no guarantees that only 1 tuple will be
742 * read. We cannot mark the cache entry as complete after reading the
743 * first tuple without that guarantee. This means the scope of Memoize
744 * node's usefulness is limited to only outer rows that have no join
745 * partner as this is the only case where Nested Loop would exhaust the
746 * inner scan of a unique join. Since the scope is limited to that, we
747 * just don't bother making a memoize path in this case.
748 *
749 * Lateral vars needn't be considered here as they're not considered when
750 * determining if the join is unique.
751 */
752 if (extra->inner_unique)
753 {
754 Bitmapset *ppi_serials;
755
756 if (inner_path->param_info == NULL)
757 return NULL;
758
759 ppi_serials = inner_path->param_info->ppi_serials;
760
761 foreach_node(RestrictInfo, rinfo, extra->restrictlist)
762 {
763 if (!bms_is_member(rinfo->rinfo_serial, ppi_serials))
764 return NULL;
765 }
766 }
767
768 /*
769 * We can't use a memoize node if there are volatile functions in the
770 * inner rel's target list or restrict list. A cache hit could reduce the
771 * number of calls to these functions.
772 */
773 if (contain_volatile_functions((Node *) innerrel->reltarget))
774 return NULL;
775
776 foreach(lc, innerrel->baserestrictinfo)
777 {
778 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
779
780 if (contain_volatile_functions((Node *) rinfo))
781 return NULL;
782 }
783
784 /*
785 * Also check the parameterized path restrictinfos for volatile functions.
786 * Indexed functions must be immutable so shouldn't have any volatile
787 * functions, however, with a lateral join the inner scan may not be an
788 * index scan.
789 */
790 if (inner_path->param_info != NULL)
791 {
792 foreach(lc, inner_path->param_info->ppi_clauses)
793 {
794 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
795
796 if (contain_volatile_functions((Node *) rinfo))
797 return NULL;
798 }
799 }
800
801 /* Check if we have hash ops for each parameter to the path */
802 if (paraminfo_get_equal_hashops(root,
803 inner_path->param_info,
804 outerrel->top_parent ?
805 outerrel->top_parent : outerrel,
806 innerrel,
807 ph_lateral_vars,
808 &param_exprs,
809 &hash_operators,
810 &binary_mode))
811 {
812 return (Path *) create_memoize_path(root,
813 innerrel,
814 inner_path,
815 param_exprs,
816 hash_operators,
817 extra->inner_unique,
818 binary_mode,
819 outer_path->rows);
820 }
821
822 return NULL;
823 }
824
825 /*
826 * try_nestloop_path
827 * Consider a nestloop join path; if it appears useful, push it into
828 * the joinrel's pathlist via add_path().
829 */
830 static void
831 try_nestloop_path(PlannerInfo *root,
832 RelOptInfo *joinrel,
833 Path *outer_path,
834 Path *inner_path,
835 List *pathkeys,
836 JoinType jointype,
837 JoinPathExtraData *extra)
838 {
839 Relids required_outer;
840 JoinCostWorkspace workspace;
841 RelOptInfo *innerrel = inner_path->parent;
842 RelOptInfo *outerrel = outer_path->parent;
843 Relids innerrelids;
844 Relids outerrelids;
845 Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
846 Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
847
848 /*
849 * If we are forming an outer join at this join, it's nonsensical to use
850 * an input path that uses the outer join as part of its parameterization.
851 * (This can happen despite our join order restrictions, since those apply
852 * to what is in an input relation not what its parameters are.)
853 */
854 if (extra->sjinfo->ojrelid != 0 &&
855 (bms_is_member(extra->sjinfo->ojrelid, inner_paramrels) ||
856 bms_is_member(extra->sjinfo->ojrelid, outer_paramrels)))
857 return;
858
859 /*
860 * Any parameterization of the input paths refers to topmost parents of
861 * the relevant relations, because reparameterize_path_by_child() hasn't
862 * been called yet. So we must consider topmost parents of the relations
863 * being joined, too, while determining parameterization of the result and
864 * checking for disallowed parameterization cases.
865 */
866 if (innerrel->top_parent_relids)
867 innerrelids = innerrel->top_parent_relids;
868 else
869 innerrelids = innerrel->relids;
870
871 if (outerrel->top_parent_relids)
872 outerrelids = outerrel->top_parent_relids;
873 else
874 outerrelids = outerrel->relids;
875
876 /*
877 * Check to see if proposed path is still parameterized, and reject if the
878 * parameterization wouldn't be sensible --- unless allow_star_schema_join
879 * says to allow it anyway.
880 */
881 required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels,
882 innerrelids, inner_paramrels);
883 if (required_outer &&
884 !bms_overlap(required_outer, extra->param_source_rels) &&
885 !allow_star_schema_join(root, outerrelids, inner_paramrels))
886 {
887 /* Waste no memory when we reject a path here */
888 bms_free(required_outer);
889 return;
890 }
891
892 /* If we got past that, we shouldn't have any unsafe outer-join refs */
893 Assert(!have_unsafe_outer_join_ref(root, outerrelids, inner_paramrels));
894
895 /*
896 * If the inner path is parameterized, it is parameterized by the topmost
897 * parent of the outer rel, not the outer rel itself. We will need to
898 * translate the parameterization, if this path is chosen, during
899 * create_plan(). Here we just check whether we will be able to perform
900 * the translation, and if not avoid creating a nestloop path.
901 */
902 if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent) &&
903 !path_is_reparameterizable_by_child(inner_path, outer_path->parent))
904 {
905 bms_free(required_outer);
906 return;
907 }
908
909 /*
910 * Do a precheck to quickly eliminate obviously-inferior paths. We
911 * calculate a cheap lower bound on the path's cost and then use
912 * add_path_precheck() to see if the path is clearly going to be dominated
913 * by some existing path for the joinrel. If not, do the full pushup with
914 * creating a fully valid path structure and submitting it to add_path().
915 * The latter two steps are expensive enough to make this two-phase
916 * methodology worthwhile.
917 */
918 initial_cost_nestloop(root, &workspace, jointype,
919 outer_path, inner_path, extra);
920
921 if (add_path_precheck(joinrel, workspace.disabled_nodes,
922 workspace.startup_cost, workspace.total_cost,
923 pathkeys, required_outer))
924 {
925 add_path(joinrel, (Path *)
926 create_nestloop_path(root,
927 joinrel,
928 jointype,
929 &workspace,
930 extra,
931 outer_path,
932 inner_path,
933 extra->restrictlist,
934 pathkeys,
935 required_outer));
936 }
937 else
938 {
939 /* Waste no memory when we reject a path here */
940 bms_free(required_outer);
941 }
942 }
943
944 /*
945 * try_partial_nestloop_path
946 * Consider a partial nestloop join path; if it appears useful, push it into
947 * the joinrel's partial_pathlist via add_partial_path().
948 */
949 static void
950 try_partial_nestloop_path(PlannerInfo *root,
951 RelOptInfo *joinrel,
952 Path *outer_path,
953 Path *inner_path,
954 List *pathkeys,
955 JoinType jointype,
956 JoinPathExtraData *extra)
957 {
958 JoinCostWorkspace workspace;
959
960 /*
961 * If the inner path is parameterized, the parameterization must be fully
962 * satisfied by the proposed outer path. Parameterized partial paths are
963 * not supported. The caller should already have verified that no lateral
964 * rels are required here.
965 */
966 Assert(bms_is_empty(joinrel->lateral_relids));
967 Assert(bms_is_empty(PATH_REQ_OUTER(outer_path)));
968 if (inner_path->param_info != NULL)
969 {
970 Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
971 RelOptInfo *outerrel = outer_path->parent;
972 Relids outerrelids;
973
974 /*
975 * The inner and outer paths are parameterized, if at all, by the top
976 * level parents, not the child relations, so we must use those relids
977 * for our parameterization tests.
978 */
979 if (outerrel->top_parent_relids)
980 outerrelids = outerrel->top_parent_relids;
981 else
982 outerrelids = outerrel->relids;
983
984 if (!bms_is_subset(inner_paramrels, outerrelids))
985 return;
986 }
987
988 /*
989 * If the inner path is parameterized, it is parameterized by the topmost
990 * parent of the outer rel, not the outer rel itself. We will need to
991 * translate the parameterization, if this path is chosen, during
992 * create_plan(). Here we just check whether we will be able to perform
993 * the translation, and if not avoid creating a nestloop path.
994 */
995 if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent) &&
996 !path_is_reparameterizable_by_child(inner_path, outer_path->parent))
997 return;
998
999 /*
1000 * Before creating a path, get a quick lower bound on what it is likely to
1001 * cost. Bail out right away if it looks terrible.
1002 */
1003 initial_cost_nestloop(root, &workspace, jointype,
1004 outer_path, inner_path, extra);
1005 if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,
1006 workspace.total_cost, pathkeys))
1007 return;
1008
1009 /* Might be good enough to be worth trying, so let's try it. */
1010 add_partial_path(joinrel, (Path *)
1011 create_nestloop_path(root,
1012 joinrel,
1013 jointype,
1014 &workspace,
1015 extra,
1016 outer_path,
1017 inner_path,
1018 extra->restrictlist,
1019 pathkeys,
1020 NULL));
1021 }
1022
1023 /*
1024 * try_mergejoin_path
1025 * Consider a merge join path; if it appears useful, push it into
1026 * the joinrel's pathlist via add_path().
1027 */
1028 static void
1029 try_mergejoin_path(PlannerInfo *root,
1030 RelOptInfo *joinrel,
1031 Path *outer_path,
1032 Path *inner_path,
1033 List *pathkeys,
1034 List *mergeclauses,
1035 List *outersortkeys,
1036 List *innersortkeys,
1037 JoinType jointype,
1038 JoinPathExtraData *extra,
1039 bool is_partial)
1040 {
1041 Relids required_outer;
1042 int outer_presorted_keys = 0;
1043 JoinCostWorkspace workspace;
1044
1045 if (is_partial)
1046 {
1047 try_partial_mergejoin_path(root,
1048 joinrel,
1049 outer_path,
1050 inner_path,
1051 pathkeys,
1052 mergeclauses,
1053 outersortkeys,
1054 innersortkeys,
1055 jointype,
1056 extra);
1057 return;
1058 }
1059
1060 /*
1061 * If we are forming an outer join at this join, it's nonsensical to use
1062 * an input path that uses the outer join as part of its parameterization.
1063 * (This can happen despite our join order restrictions, since those apply
1064 * to what is in an input relation not what its parameters are.)
1065 */
1066 if (extra->sjinfo->ojrelid != 0 &&
1067 (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) ||
1068 bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path))))
1069 return;
1070
1071 /*
1072 * Check to see if proposed path is still parameterized, and reject if the
1073 * parameterization wouldn't be sensible.
1074 */
1075 required_outer = calc_non_nestloop_required_outer(outer_path,
1076 inner_path);
1077 if (required_outer &&
1078 !bms_overlap(required_outer, extra->param_source_rels))
1079 {
1080 /* Waste no memory when we reject a path here */
1081 bms_free(required_outer);
1082 return;
1083 }
1084
1085 /*
1086 * If the given paths are already well enough ordered, we can skip doing
1087 * an explicit sort.
1088 *
1089 * We need to determine the number of presorted keys of the outer path to
1090 * decide whether explicit incremental sort can be applied when
1091 * outersortkeys is not NIL. We do not need to do the same for the inner
1092 * path though, as incremental sort currently does not support
1093 * mark/restore.
1094 */
1095 if (outersortkeys &&
1096 pathkeys_count_contained_in(outersortkeys, outer_path->pathkeys,
1097 &outer_presorted_keys))
1098 outersortkeys = NIL;
1099 if (innersortkeys &&
1100 pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
1101 innersortkeys = NIL;
1102
1103 /*
1104 * See comments in try_nestloop_path().
1105 */
1106 initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
1107 outer_path, inner_path,
1108 outersortkeys, innersortkeys,
1109 outer_presorted_keys,
1110 extra);
1111
1112 if (add_path_precheck(joinrel, workspace.disabled_nodes,
1113 workspace.startup_cost, workspace.total_cost,
1114 pathkeys, required_outer))
1115 {
1116 add_path(joinrel, (Path *)
1117 create_mergejoin_path(root,
1118 joinrel,
1119 jointype,
1120 &workspace,
1121 extra,
1122 outer_path,
1123 inner_path,
1124 extra->restrictlist,
1125 pathkeys,
1126 required_outer,
1127 mergeclauses,
1128 outersortkeys,
1129 innersortkeys,
1130 outer_presorted_keys));
1131 }
1132 else
1133 {
1134 /* Waste no memory when we reject a path here */
1135 bms_free(required_outer);
1136 }
1137 }
1138
1139 /*
1140 * try_partial_mergejoin_path
1141 * Consider a partial merge join path; if it appears useful, push it into
1142 * the joinrel's pathlist via add_partial_path().
1143 */
1144 static void
1145 try_partial_mergejoin_path(PlannerInfo *root,
1146 RelOptInfo *joinrel,
1147 Path *outer_path,
1148 Path *inner_path,
1149 List *pathkeys,
1150 List *mergeclauses,
1151 List *outersortkeys,
1152 List *innersortkeys,
1153 JoinType jointype,
1154 JoinPathExtraData *extra)
1155 {
1156 int outer_presorted_keys = 0;
1157 JoinCostWorkspace workspace;
1158
1159 /*
1160 * See comments in try_partial_hashjoin_path().
1161 */
1162 Assert(bms_is_empty(joinrel->lateral_relids));
1163 Assert(bms_is_empty(PATH_REQ_OUTER(outer_path)));
1164 if (!bms_is_empty(PATH_REQ_OUTER(inner_path)))
1165 return;
1166
1167 /*
1168 * If the given paths are already well enough ordered, we can skip doing
1169 * an explicit sort.
1170 *
1171 * We need to determine the number of presorted keys of the outer path to
1172 * decide whether explicit incremental sort can be applied when
1173 * outersortkeys is not NIL. We do not need to do the same for the inner
1174 * path though, as incremental sort currently does not support
1175 * mark/restore.
1176 */
1177 if (outersortkeys &&
1178 pathkeys_count_contained_in(outersortkeys, outer_path->pathkeys,
1179 &outer_presorted_keys))
1180 outersortkeys = NIL;
1181 if (innersortkeys &&
1182 pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
1183 innersortkeys = NIL;
1184
1185 /*
1186 * See comments in try_partial_nestloop_path().
1187 */
1188 initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
1189 outer_path, inner_path,
1190 outersortkeys, innersortkeys,
1191 outer_presorted_keys,
1192 extra);
1193
1194 if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,
1195 workspace.total_cost, pathkeys))
1196 return;
1197
1198 /* Might be good enough to be worth trying, so let's try it. */
1199 add_partial_path(joinrel, (Path *)
1200 create_mergejoin_path(root,
1201 joinrel,
1202 jointype,
1203 &workspace,
1204 extra,
1205 outer_path,
1206 inner_path,
1207 extra->restrictlist,
1208 pathkeys,
1209 NULL,
1210 mergeclauses,
1211 outersortkeys,
1212 innersortkeys,
1213 outer_presorted_keys));
1214 }
1215
1216 /*
1217 * try_hashjoin_path
1218 * Consider a hash join path; if it appears useful, push it into
1219 * the joinrel's pathlist via add_path().
1220 */
1221 static void
1222 try_hashjoin_path(PlannerInfo *root,
1223 RelOptInfo *joinrel,
1224 Path *outer_path,
1225 Path *inner_path,
1226 List *hashclauses,
1227 JoinType jointype,
1228 JoinPathExtraData *extra)
1229 {
1230 Relids required_outer;
1231 JoinCostWorkspace workspace;
1232
1233 /*
1234 * If we are forming an outer join at this join, it's nonsensical to use
1235 * an input path that uses the outer join as part of its parameterization.
1236 * (This can happen despite our join order restrictions, since those apply
1237 * to what is in an input relation not what its parameters are.)
1238 */
1239 if (extra->sjinfo->ojrelid != 0 &&
1240 (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) ||
1241 bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path))))
1242 return;
1243
1244 /*
1245 * Check to see if proposed path is still parameterized, and reject if the
1246 * parameterization wouldn't be sensible.
1247 */
1248 required_outer = calc_non_nestloop_required_outer(outer_path,
1249 inner_path);
1250 if (required_outer &&
1251 !bms_overlap(required_outer, extra->param_source_rels))
1252 {
1253 /* Waste no memory when we reject a path here */
1254 bms_free(required_outer);
1255 return;
1256 }
1257
1258 /*
1259 * See comments in try_nestloop_path(). Also note that hashjoin paths
1260 * never have any output pathkeys, per comments in create_hashjoin_path.
1261 */
1262 initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1263 outer_path, inner_path, extra, false);
1264
1265 if (add_path_precheck(joinrel, workspace.disabled_nodes,
1266 workspace.startup_cost, workspace.total_cost,
1267 NIL, required_outer))
1268 {
1269 add_path(joinrel, (Path *)
1270 create_hashjoin_path(root,
1271 joinrel,
1272 jointype,
1273 &workspace,
1274 extra,
1275 outer_path,
1276 inner_path,
1277 false, /* parallel_hash */
1278 extra->restrictlist,
1279 required_outer,
1280 hashclauses));
1281 }
1282 else
1283 {
1284 /* Waste no memory when we reject a path here */
1285 bms_free(required_outer);
1286 }
1287 }
1288
1289 /*
1290 * try_partial_hashjoin_path
1291 * Consider a partial hashjoin join path; if it appears useful, push it into
1292 * the joinrel's partial_pathlist via add_partial_path().
1293 * The outer side is partial. If parallel_hash is true, then the inner path
1294 * must be partial and will be run in parallel to create one or more shared
1295 * hash tables; otherwise the inner path must be complete and a copy of it
1296 * is run in every process to create separate identical private hash tables.
1297 */
1298 static void
1299 try_partial_hashjoin_path(PlannerInfo *root,
1300 RelOptInfo *joinrel,
1301 Path *outer_path,
1302 Path *inner_path,
1303 List *hashclauses,
1304 JoinType jointype,
1305 JoinPathExtraData *extra,
1306 bool parallel_hash)
1307 {
1308 JoinCostWorkspace workspace;
1309
1310 /*
1311 * If the inner path is parameterized, we can't use a partial hashjoin.
1312 * Parameterized partial paths are not supported. The caller should
1313 * already have verified that no lateral rels are required here.
1314 */
1315 Assert(bms_is_empty(joinrel->lateral_relids));
1316 Assert(bms_is_empty(PATH_REQ_OUTER(outer_path)));
1317 if (!bms_is_empty(PATH_REQ_OUTER(inner_path)))
1318 return;
1319
1320 /*
1321 * Before creating a path, get a quick lower bound on what it is likely to
1322 * cost. Bail out right away if it looks terrible.
1323 */
1324 initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1325 outer_path, inner_path, extra, parallel_hash);
1326 if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,
1327 workspace.total_cost, NIL))
1328 return;
1329
1330 /* Might be good enough to be worth trying, so let's try it. */
1331 add_partial_path(joinrel, (Path *)
1332 create_hashjoin_path(root,
1333 joinrel,
1334 jointype,
1335 &workspace,
1336 extra,
1337 outer_path,
1338 inner_path,
1339 parallel_hash,
1340 extra->restrictlist,
1341 NULL,
1342 hashclauses));
1343 }
1344
1345 /*
1346 * sort_inner_and_outer
1347 * Create mergejoin join paths by explicitly sorting both the outer and
1348 * inner join relations on each available merge ordering.
1349 *
1350 * 'joinrel' is the join relation
1351 * 'outerrel' is the outer join relation
1352 * 'innerrel' is the inner join relation
1353 * 'jointype' is the type of join to do
1354 * 'extra' contains additional input values
1355 */
1356 static void
1357 sort_inner_and_outer(PlannerInfo *root,
1358 RelOptInfo *joinrel,
1359 RelOptInfo *outerrel,
1360 RelOptInfo *innerrel,
1361 JoinType jointype,
1362 JoinPathExtraData *extra)
1363 {
1364 JoinType save_jointype = jointype;
1365 Path *outer_path;
1366 Path *inner_path;
1367 Path *cheapest_partial_outer = NULL;
1368 Path *cheapest_safe_inner = NULL;
1369 List *all_pathkeys;
1370 ListCell *l;
1371
1372 /* Nothing to do if there are no available mergejoin clauses */
1373 if (extra->mergeclause_list == NIL)
1374 return;
1375
1376 /*
1377 * We only consider the cheapest-total-cost input paths, since we are
1378 * assuming here that a sort is required. We will consider
1379 * cheapest-startup-cost input paths later, and only if they don't need a
1380 * sort.
1381 *
1382 * This function intentionally does not consider parameterized input
1383 * paths, except when the cheapest-total is parameterized. If we did so,
1384 * we'd have a combinatorial explosion of mergejoin paths of dubious
1385 * value. This interacts with decisions elsewhere that also discriminate
1386 * against mergejoins with parameterized inputs; see comments in
1387 * src/backend/optimizer/README.
1388 */
1389 outer_path = outerrel->cheapest_total_path;
1390 inner_path = innerrel->cheapest_total_path;
1391
1392 /*
1393 * If either cheapest-total path is parameterized by the other rel, we
1394 * can't use a mergejoin. (There's no use looking for alternative input
1395 * paths, since these should already be the least-parameterized available
1396 * paths.)
1397 */
1398 if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
1399 PATH_PARAM_BY_REL(inner_path, outerrel))
1400 return;
1401
1402 /*
1403 * If unique-ification is requested, do it and then handle as a plain
1404 * inner join.
1405 */
1406 if (jointype == JOIN_UNIQUE_OUTER)
1407 {
1408 outer_path = (Path *) create_unique_path(root, outerrel,
1409 outer_path, extra->sjinfo);
1410 Assert(outer_path);
1411 jointype = JOIN_INNER;
1412 }
1413 else if (jointype == JOIN_UNIQUE_INNER)
1414 {
1415 inner_path = (Path *) create_unique_path(root, innerrel,
1416 inner_path, extra->sjinfo);
1417 Assert(inner_path);
1418 jointype = JOIN_INNER;
1419 }
1420
1421 /*
1422 * If the joinrel is parallel-safe, we may be able to consider a partial
1423 * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
1424 * outer path will be partial, and therefore we won't be able to properly
1425 * guarantee uniqueness. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT
1426 * and JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1427 * Also, the resulting path must not be parameterized.
1428 */
1429 if (joinrel->consider_parallel &&
1430 save_jointype != JOIN_UNIQUE_OUTER &&
1431 save_jointype != JOIN_FULL &&
1432 save_jointype != JOIN_RIGHT &&
1433 save_jointype != JOIN_RIGHT_ANTI &&
1434 outerrel->partial_pathlist != NIL &&
1435 bms_is_empty(joinrel->lateral_relids))
1436 {
1437 cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
1438
1439 if (inner_path->parallel_safe)
1440 cheapest_safe_inner = inner_path;
1441 else if (save_jointype != JOIN_UNIQUE_INNER)
1442 cheapest_safe_inner =
1443 get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
1444 }
1445
1446 /*
1447 * Each possible ordering of the available mergejoin clauses will generate
1448 * a differently-sorted result path at essentially the same cost. We have
1449 * no basis for choosing one over another at this level of joining, but
1450 * some sort orders may be more useful than others for higher-level
1451 * mergejoins, so it's worth considering multiple orderings.
1452 *
1453 * Actually, it's not quite true that every mergeclause ordering will
1454 * generate a different path order, because some of the clauses may be
1455 * partially redundant (refer to the same EquivalenceClasses). Therefore,
1456 * what we do is convert the mergeclause list to a list of canonical
1457 * pathkeys, and then consider different orderings of the pathkeys.
1458 *
1459 * Generating a path for *every* permutation of the pathkeys doesn't seem
1460 * like a winning strategy; the cost in planning time is too high. For
1461 * now, we generate one path for each pathkey, listing that pathkey first
1462 * and the rest in random order. This should allow at least a one-clause
1463 * mergejoin without re-sorting against any other possible mergejoin
1464 * partner path. But if we've not guessed the right ordering of secondary
1465 * keys, we may end up evaluating clauses as qpquals when they could have
1466 * been done as mergeclauses. (In practice, it's rare that there's more
1467 * than two or three mergeclauses, so expending a huge amount of thought
1468 * on that is probably not worth it.)
1469 *
1470 * The pathkey order returned by select_outer_pathkeys_for_merge() has
1471 * some heuristics behind it (see that function), so be sure to try it
1472 * exactly as-is as well as making variants.
1473 */
1474 all_pathkeys = select_outer_pathkeys_for_merge(root,
1475 extra->mergeclause_list,
1476 joinrel);
1477
1478 foreach(l, all_pathkeys)
1479 {
1480 PathKey *front_pathkey = (PathKey *) lfirst(l);
1481 List *cur_mergeclauses;
1482 List *outerkeys;
1483 List *innerkeys;
1484 List *merge_pathkeys;
1485
1486 /* Make a pathkey list with this guy first */
1487 if (l != list_head(all_pathkeys))
1488 outerkeys = lcons(front_pathkey,
1489 list_delete_nth_cell(list_copy(all_pathkeys),
1490 foreach_current_index(l)));
1491 else
1492 outerkeys = all_pathkeys; /* no work at first one... */
1493
1494 /* Sort the mergeclauses into the corresponding ordering */
1495 cur_mergeclauses =
1496 find_mergeclauses_for_outer_pathkeys(root,
1497 outerkeys,
1498 extra->mergeclause_list);
1499
1500 /* Should have used them all... */
1501 Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
1502
1503 /* Build sort pathkeys for the inner side */
1504 innerkeys = make_inner_pathkeys_for_merge(root,
1505 cur_mergeclauses,
1506 outerkeys);
1507
1508 /* Build pathkeys representing output sort order */
1509 merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1510 outerkeys);
1511
1512 /*
1513 * And now we can make the path.
1514 *
1515 * Note: it's possible that the cheapest paths will already be sorted
1516 * properly. try_mergejoin_path will detect that case and suppress an
1517 * explicit sort step, so we needn't do so here.
1518 */
1519 try_mergejoin_path(root,
1520 joinrel,
1521 outer_path,
1522 inner_path,
1523 merge_pathkeys,
1524 cur_mergeclauses,
1525 outerkeys,
1526 innerkeys,
1527 jointype,
1528 extra,
1529 false);
1530
1531 /*
1532 * If we have partial outer and parallel safe inner path then try
1533 * partial mergejoin path.
1534 */
1535 if (cheapest_partial_outer && cheapest_safe_inner)
1536 try_partial_mergejoin_path(root,
1537 joinrel,
1538 cheapest_partial_outer,
1539 cheapest_safe_inner,
1540 merge_pathkeys,
1541 cur_mergeclauses,
1542 outerkeys,
1543 innerkeys,
1544 jointype,
1545 extra);
1546 }
1547 }
1548
1549 /*
1550 * generate_mergejoin_paths
1551 * Creates possible mergejoin paths for input outerpath.
1552 *
1553 * We generate mergejoins if mergejoin clauses are available. We have
1554 * two ways to generate the inner path for a mergejoin: sort the cheapest
1555 * inner path, or use an inner path that is already suitably ordered for the
1556 * merge. If we have several mergeclauses, it could be that there is no inner
1557 * path (or only a very expensive one) for the full list of mergeclauses, but
1558 * better paths exist if we truncate the mergeclause list (thereby discarding
1559 * some sort key requirements). So, we consider truncations of the
1560 * mergeclause list as well as the full list. (Ideally we'd consider all
1561 * subsets of the mergeclause list, but that seems way too expensive.)
1562 */
1563 static void
1564 generate_mergejoin_paths(PlannerInfo *root,
1565 RelOptInfo *joinrel,
1566 RelOptInfo *innerrel,
1567 Path *outerpath,
1568 JoinType jointype,
1569 JoinPathExtraData *extra,
1570 bool useallclauses,
1571 Path *inner_cheapest_total,
1572 List *merge_pathkeys,
1573 bool is_partial)
1574 {
1575 List *mergeclauses;
1576 List *innersortkeys;
1577 List *trialsortkeys;
1578 Path *cheapest_startup_inner;
1579 Path *cheapest_total_inner;
1580 JoinType save_jointype = jointype;
1581 int num_sortkeys;
1582 int sortkeycnt;
1583
1584 if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)
1585 jointype = JOIN_INNER;
1586
1587 /* Look for useful mergeclauses (if any) */
1588 mergeclauses =
1589 find_mergeclauses_for_outer_pathkeys(root,
1590 outerpath->pathkeys,
1591 extra->mergeclause_list);
1592
1593 /*
1594 * Done with this outer path if no chance for a mergejoin.
1595 *
1596 * Special corner case: for "x FULL JOIN y ON true", there will be no join
1597 * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1598 * but since mergejoin is our only join type that supports FULL JOIN
1599 * without any join clauses, it's necessary to generate a clauseless
1600 * mergejoin path instead.
1601 */
1602 if (mergeclauses == NIL)
1603 {
1604 if (jointype == JOIN_FULL)
1605 /* okay to try for mergejoin */ ;
1606 else
1607 return;
1608 }
1609 if (useallclauses &&
1610 list_length(mergeclauses) != list_length(extra->mergeclause_list))
1611 return;
1612
1613 /* Compute the required ordering of the inner path */
1614 innersortkeys = make_inner_pathkeys_for_merge(root,
1615 mergeclauses,
1616 outerpath->pathkeys);
1617
1618 /*
1619 * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1620 * a sort will be needed, only cheapest total cost matters. (But
1621 * try_mergejoin_path will do the right thing if inner_cheapest_total is
1622 * already correctly sorted.)
1623 */
1624 try_mergejoin_path(root,
1625 joinrel,
1626 outerpath,
1627 inner_cheapest_total,
1628 merge_pathkeys,
1629 mergeclauses,
1630 NIL,
1631 innersortkeys,
1632 jointype,
1633 extra,
1634 is_partial);
1635
1636 /* Can't do anything else if inner path needs to be unique'd */
1637 if (save_jointype == JOIN_UNIQUE_INNER)
1638 return;
1639
1640 /*
1641 * Look for presorted inner paths that satisfy the innersortkey list ---
1642 * or any truncation thereof, if we are allowed to build a mergejoin using
1643 * a subset of the merge clauses. Here, we consider both cheap startup
1644 * cost and cheap total cost.
1645 *
1646 * Currently we do not consider parameterized inner paths here. This
1647 * interacts with decisions elsewhere that also discriminate against
1648 * mergejoins with parameterized inputs; see comments in
1649 * src/backend/optimizer/README.
1650 *
1651 * As we shorten the sortkey list, we should consider only paths that are
1652 * strictly cheaper than (in particular, not the same as) any path found
1653 * in an earlier iteration. Otherwise we'd be intentionally using fewer
1654 * merge keys than a given path allows (treating the rest as plain
1655 * joinquals), which is unlikely to be a good idea. Also, eliminating
1656 * paths here on the basis of compare_path_costs is a lot cheaper than
1657 * building the mergejoin path only to throw it away.
1658 *
1659 * If inner_cheapest_total is well enough sorted to have not required a
1660 * sort in the path made above, we shouldn't make a duplicate path with
1661 * it, either. We handle that case with the same logic that handles the
1662 * previous consideration, by initializing the variables that track
1663 * cheapest-so-far properly. Note that we do NOT reject
1664 * inner_cheapest_total if we find it matches some shorter set of
1665 * pathkeys. That case corresponds to using fewer mergekeys to avoid
1666 * sorting inner_cheapest_total, whereas we did sort it above, so the
1667 * plans being considered are different.
1668 */
1669 if (pathkeys_contained_in(innersortkeys,
1670 inner_cheapest_total->pathkeys))
1671 {
1672 /* inner_cheapest_total didn't require a sort */
1673 cheapest_startup_inner = inner_cheapest_total;
1674 cheapest_total_inner = inner_cheapest_total;
1675 }
1676 else
1677 {
1678 /* it did require a sort, at least for the full set of keys */
1679 cheapest_startup_inner = NULL;
1680 cheapest_total_inner = NULL;
1681 }
1682 num_sortkeys = list_length(innersortkeys);
1683 if (num_sortkeys > 1 && !useallclauses)
1684 trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */
1685 else
1686 trialsortkeys = innersortkeys; /* won't really truncate */
1687
1688 for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1689 {
1690 Path *innerpath;
1691 List *newclauses = NIL;
1692
1693 /*
1694 * Look for an inner path ordered well enough for the first
1695 * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1696 * destructively, which is why we made a copy...
1697 */
1698 trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
1699 innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1700 trialsortkeys,
1701 NULL,
1702 TOTAL_COST,
1703 is_partial);
1704 if (innerpath != NULL &&
1705 (cheapest_total_inner == NULL ||
1706 compare_path_costs(innerpath, cheapest_total_inner,
1707 TOTAL_COST) < 0))
1708 {
1709 /* Found a cheap (or even-cheaper) sorted path */
1710 /* Select the right mergeclauses, if we didn't already */
1711 if (sortkeycnt < num_sortkeys)
1712 {
1713 newclauses =
1714 trim_mergeclauses_for_inner_pathkeys(root,
1715 mergeclauses,
1716 trialsortkeys);
1717 Assert(newclauses != NIL);
1718 }
1719 else
1720 newclauses = mergeclauses;
1721 try_mergejoin_path(root,
1722 joinrel,
1723 outerpath,
1724 innerpath,
1725 merge_pathkeys,
1726 newclauses,
1727 NIL,
1728 NIL,
1729 jointype,
1730 extra,
1731 is_partial);
1732 cheapest_total_inner = innerpath;
1733 }
1734 /* Same on the basis of cheapest startup cost ... */
1735 innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1736 trialsortkeys,
1737 NULL,
1738 STARTUP_COST,
1739 is_partial);
1740 if (innerpath != NULL &&
1741 (cheapest_startup_inner == NULL ||
1742 compare_path_costs(innerpath, cheapest_startup_inner,
1743 STARTUP_COST) < 0))
1744 {
1745 /* Found a cheap (or even-cheaper) sorted path */
1746 if (innerpath != cheapest_total_inner)
1747 {
1748 /*
1749 * Avoid rebuilding clause list if we already made one; saves
1750 * memory in big join trees...
1751 */
1752 if (newclauses == NIL)
1753 {
1754 if (sortkeycnt < num_sortkeys)
1755 {
1756 newclauses =
1757 trim_mergeclauses_for_inner_pathkeys(root,
1758 mergeclauses,
1759 trialsortkeys);
1760 Assert(newclauses != NIL);
1761 }
1762 else
1763 newclauses = mergeclauses;
1764 }
1765 try_mergejoin_path(root,
1766 joinrel,
1767 outerpath,
1768 innerpath,
1769 merge_pathkeys,
1770 newclauses,
1771 NIL,
1772 NIL,
1773 jointype,
1774 extra,
1775 is_partial);
1776 }
1777 cheapest_startup_inner = innerpath;
1778 }
1779
1780 /*
1781 * Don't consider truncated sortkeys if we need all clauses.
1782 */
1783 if (useallclauses)
1784 break;
1785 }
1786 }
1787
1788 /*
1789 * match_unsorted_outer
1790 * Creates possible join paths for processing a single join relation
1791 * 'joinrel' by employing either iterative substitution or
1792 * mergejoining on each of its possible outer paths (considering
1793 * only outer paths that are already ordered well enough for merging).
1794 *
1795 * We always generate a nestloop path for each available outer path.
1796 * In fact we may generate as many as five: one on the cheapest-total-cost
1797 * inner path, one on the same with materialization, one on the
1798 * cheapest-startup-cost inner path (if different), one on the
1799 * cheapest-total inner-indexscan path (if any), and one on the
1800 * cheapest-startup inner-indexscan path (if different).
1801 *
1802 * We also consider mergejoins if mergejoin clauses are available. See
1803 * detailed comments in generate_mergejoin_paths.
1804 *
1805 * 'joinrel' is the join relation
1806 * 'outerrel' is the outer join relation
1807 * 'innerrel' is the inner join relation
1808 * 'jointype' is the type of join to do
1809 * 'extra' contains additional input values
1810 */
1811 static void
1812 match_unsorted_outer(PlannerInfo *root,
1813 RelOptInfo *joinrel,
1814 RelOptInfo *outerrel,
1815 RelOptInfo *innerrel,
1816 JoinType jointype,
1817 JoinPathExtraData *extra)
1818 {
1819 JoinType save_jointype = jointype;
1820 bool nestjoinOK;
1821 bool useallclauses;
1822 Path *inner_cheapest_total = innerrel->cheapest_total_path;
1823 Path *matpath = NULL;
1824 ListCell *lc1;
1825
1826 /*
1827 * For now we do not support RIGHT_SEMI join in mergejoin or nestloop
1828 * join.
1829 */
1830 if (jointype == JOIN_RIGHT_SEMI)
1831 return;
1832
1833 /*
1834 * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1835 * are doing a right, right-anti or full mergejoin, we must use *all* the
1836 * mergeclauses as join clauses, else we will not have a valid plan.
1837 * (Although these two flags are currently inverses, keep them separate
1838 * for clarity and possible future changes.)
1839 */
1840 switch (jointype)
1841 {
1842 case JOIN_INNER:
1843 case JOIN_LEFT:
1844 case JOIN_SEMI:
1845 case JOIN_ANTI:
1846 nestjoinOK = true;
1847 useallclauses = false;
1848 break;
1849 case JOIN_RIGHT:
1850 case JOIN_RIGHT_ANTI:
1851 case JOIN_FULL:
1852 nestjoinOK = false;
1853 useallclauses = true;
1854 break;
1855 case JOIN_UNIQUE_OUTER:
1856 case JOIN_UNIQUE_INNER:
1857 jointype = JOIN_INNER;
1858 nestjoinOK = true;
1859 useallclauses = false;
1860 break;
1861 default:
1862 elog(ERROR, "unrecognized join type: %d",
1863 (int) jointype);
1864 nestjoinOK = false; /* keep compiler quiet */
1865 useallclauses = false;
1866 break;
1867 }
1868
1869 /*
1870 * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1871 * we will consider it below as a member of cheapest_parameterized_paths,
1872 * but the other possibilities considered in this routine aren't usable.
1873 */
1874 if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1875 inner_cheapest_total = NULL;
1876
1877 /*
1878 * If we need to unique-ify the inner path, we will consider only the
1879 * cheapest-total inner.
1880 */
1881 if (save_jointype == JOIN_UNIQUE_INNER)
1882 {
1883 /* No way to do this with an inner path parameterized by outer rel */
1884 if (inner_cheapest_total == NULL)
1885 return;
1886 inner_cheapest_total = (Path *)
1887 create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1888 Assert(inner_cheapest_total);
1889 }
1890 else if (nestjoinOK)
1891 {
1892 /*
1893 * Consider materializing the cheapest inner path, unless
1894 * enable_material is off or the path in question materializes its
1895 * output anyway.
1896 */
1897 if (enable_material && inner_cheapest_total != NULL &&
1898 !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1899 matpath = (Path *)
1900 create_material_path(innerrel, inner_cheapest_total);
1901 }
1902
1903 foreach(lc1, outerrel->pathlist)
1904 {
1905 Path *outerpath = (Path *) lfirst(lc1);
1906 List *merge_pathkeys;
1907
1908 /*
1909 * We cannot use an outer path that is parameterized by the inner rel.
1910 */
1911 if (PATH_PARAM_BY_REL(outerpath, innerrel))
1912 continue;
1913
1914 /*
1915 * If we need to unique-ify the outer path, it's pointless to consider
1916 * any but the cheapest outer. (XXX we don't consider parameterized
1917 * outers, nor inners, for unique-ified cases. Should we?)
1918 */
1919 if (save_jointype == JOIN_UNIQUE_OUTER)
1920 {
1921 if (outerpath != outerrel->cheapest_total_path)
1922 continue;
1923 outerpath = (Path *) create_unique_path(root, outerrel,
1924 outerpath, extra->sjinfo);
1925 Assert(outerpath);
1926 }
1927
1928 /*
1929 * The result will have this sort order (even if it is implemented as
1930 * a nestloop, and even if some of the mergeclauses are implemented by
1931 * qpquals rather than as true mergeclauses):
1932 */
1933 merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1934 outerpath->pathkeys);
1935
1936 if (save_jointype == JOIN_UNIQUE_INNER)
1937 {
1938 /*
1939 * Consider nestloop join, but only with the unique-ified cheapest
1940 * inner path
1941 */
1942 try_nestloop_path(root,
1943 joinrel,
1944 outerpath,
1945 inner_cheapest_total,
1946 merge_pathkeys,
1947 jointype,
1948 extra);
1949 }
1950 else if (nestjoinOK)
1951 {
1952 /*
1953 * Consider nestloop joins using this outer path and various
1954 * available paths for the inner relation. We consider the
1955 * cheapest-total paths for each available parameterization of the
1956 * inner relation, including the unparameterized case.
1957 */
1958 ListCell *lc2;
1959
1960 foreach(lc2, innerrel->cheapest_parameterized_paths)
1961 {
1962 Path *innerpath = (Path *) lfirst(lc2);
1963 Path *mpath;
1964
1965 try_nestloop_path(root,
1966 joinrel,
1967 outerpath,
1968 innerpath,
1969 merge_pathkeys,
1970 jointype,
1971 extra);
1972
1973 /*
1974 * Try generating a memoize path and see if that makes the
1975 * nested loop any cheaper.
1976 */
1977 mpath = get_memoize_path(root, innerrel, outerrel,
1978 innerpath, outerpath, jointype,
1979 extra);
1980 if (mpath != NULL)
1981 try_nestloop_path(root,
1982 joinrel,
1983 outerpath,
1984 mpath,
1985 merge_pathkeys,
1986 jointype,
1987 extra);
1988 }
1989
1990 /* Also consider materialized form of the cheapest inner path */
1991 if (matpath != NULL)
1992 try_nestloop_path(root,
1993 joinrel,
1994 outerpath,
1995 matpath,
1996 merge_pathkeys,
1997 jointype,
1998 extra);
1999 }
2000
2001 /* Can't do anything else if outer path needs to be unique'd */
2002 if (save_jointype == JOIN_UNIQUE_OUTER)
2003 continue;
2004
2005 /* Can't do anything else if inner rel is parameterized by outer */
2006 if (inner_cheapest_total == NULL)
2007 continue;
2008
2009 /* Generate merge join paths */
2010 generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
2011 save_jointype, extra, useallclauses,
2012 inner_cheapest_total, merge_pathkeys,
2013 false);
2014 }
2015
2016 /*
2017 * Consider partial nestloop and mergejoin plan if outerrel has any
2018 * partial path and the joinrel is parallel-safe. However, we can't
2019 * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
2020 * therefore we won't be able to properly guarantee uniqueness. Nor can
2021 * we handle joins needing lateral rels, since partial paths must not be
2022 * parameterized. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT and
2023 * JOIN_RIGHT_ANTI, because they can produce false null extended rows.
2024 */
2025 if (joinrel->consider_parallel &&
2026 save_jointype != JOIN_UNIQUE_OUTER &&
2027 save_jointype != JOIN_FULL &&
2028 save_jointype != JOIN_RIGHT &&
2029 save_jointype != JOIN_RIGHT_ANTI &&
2030 outerrel->partial_pathlist != NIL &&
2031 bms_is_empty(joinrel->lateral_relids))
2032 {
2033 if (nestjoinOK)
2034 consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
2035 save_jointype, extra);
2036
2037 /*
2038 * If inner_cheapest_total is NULL or non parallel-safe then find the
2039 * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
2040 * can't use any alternative inner path.
2041 */
2042 if (inner_cheapest_total == NULL ||
2043 !inner_cheapest_total->parallel_safe)
2044 {
2045 if (save_jointype == JOIN_UNIQUE_INNER)
2046 return;
2047
2048 inner_cheapest_total = get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
2049 }
2050
2051 if (inner_cheapest_total)
2052 consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
2053 save_jointype, extra,
2054 inner_cheapest_total);
2055 }
2056 }
2057
2058 /*
2059 * consider_parallel_mergejoin
2060 * Try to build partial paths for a joinrel by joining a partial path
2061 * for the outer relation to a complete path for the inner relation.
2062 *
2063 * 'joinrel' is the join relation
2064 * 'outerrel' is the outer join relation
2065 * 'innerrel' is the inner join relation
2066 * 'jointype' is the type of join to do
2067 * 'extra' contains additional input values
2068 * 'inner_cheapest_total' cheapest total path for innerrel
2069 */
2070 static void
2071 consider_parallel_mergejoin(PlannerInfo *root,
2072 RelOptInfo *joinrel,
2073 RelOptInfo *outerrel,
2074 RelOptInfo *innerrel,
2075 JoinType jointype,
2076 JoinPathExtraData *extra,
2077 Path *inner_cheapest_total)
2078 {
2079 ListCell *lc1;
2080
2081 /* generate merge join path for each partial outer path */
2082 foreach(lc1, outerrel->partial_pathlist)
2083 {
2084 Path *outerpath = (Path *) lfirst(lc1);
2085 List *merge_pathkeys;
2086
2087 /*
2088 * Figure out what useful ordering any paths we create will have.
2089 */
2090 merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
2091 outerpath->pathkeys);
2092
2093 generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
2094 extra, false, inner_cheapest_total,
2095 merge_pathkeys, true);
2096 }
2097 }
2098
2099 /*
2100 * consider_parallel_nestloop
2101 * Try to build partial paths for a joinrel by joining a partial path for the
2102 * outer relation to a complete path for the inner relation.
2103 *
2104 * 'joinrel' is the join relation
2105 * 'outerrel' is the outer join relation
2106 * 'innerrel' is the inner join relation
2107 * 'jointype' is the type of join to do
2108 * 'extra' contains additional input values
2109 */
2110 static void
2111 consider_parallel_nestloop(PlannerInfo *root,
2112 RelOptInfo *joinrel,
2113 RelOptInfo *outerrel,
2114 RelOptInfo *innerrel,
2115 JoinType jointype,
2116 JoinPathExtraData *extra)
2117 {
2118 JoinType save_jointype = jointype;
2119 Path *inner_cheapest_total = innerrel->cheapest_total_path;
2120 Path *matpath = NULL;
2121 ListCell *lc1;
2122
2123 if (jointype == JOIN_UNIQUE_INNER)
2124 jointype = JOIN_INNER;
2125
2126 /*
2127 * Consider materializing the cheapest inner path, unless: 1) we're doing
2128 * JOIN_UNIQUE_INNER, because in this case we have to unique-ify the
2129 * cheapest inner path, 2) enable_material is off, 3) the cheapest inner
2130 * path is not parallel-safe, 4) the cheapest inner path is parameterized
2131 * by the outer rel, or 5) the cheapest inner path materializes its output
2132 * anyway.
2133 */
2134 if (save_jointype != JOIN_UNIQUE_INNER &&
2135 enable_material && inner_cheapest_total->parallel_safe &&
2136 !PATH_PARAM_BY_REL(inner_cheapest_total, outerrel) &&
2137 !ExecMaterializesOutput(inner_cheapest_total->pathtype))
2138 {
2139 matpath = (Path *)
2140 create_material_path(innerrel, inner_cheapest_total);
2141 Assert(matpath->parallel_safe);
2142 }
2143
2144 foreach(lc1, outerrel->partial_pathlist)
2145 {
2146 Path *outerpath = (Path *) lfirst(lc1);
2147 List *pathkeys;
2148 ListCell *lc2;
2149
2150 /* Figure out what useful ordering any paths we create will have. */
2151 pathkeys = build_join_pathkeys(root, joinrel, jointype,
2152 outerpath->pathkeys);
2153
2154 /*
2155 * Try the cheapest parameterized paths; only those which will produce
2156 * an unparameterized path when joined to this outerrel will survive
2157 * try_partial_nestloop_path. The cheapest unparameterized path is
2158 * also in this list.
2159 */
2160 foreach(lc2, innerrel->cheapest_parameterized_paths)
2161 {
2162 Path *innerpath = (Path *) lfirst(lc2);
2163 Path *mpath;
2164
2165 /* Can't join to an inner path that is not parallel-safe */
2166 if (!innerpath->parallel_safe)
2167 continue;
2168
2169 /*
2170 * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
2171 * cheapest_total_path, and we have to unique-ify it. (We might
2172 * be able to relax this to allow other safe, unparameterized
2173 * inner paths, but right now create_unique_path is not on board
2174 * with that.)
2175 */
2176 if (save_jointype == JOIN_UNIQUE_INNER)
2177 {
2178 if (innerpath != innerrel->cheapest_total_path)
2179 continue;
2180 innerpath = (Path *) create_unique_path(root, innerrel,
2181 innerpath,
2182 extra->sjinfo);
2183 Assert(innerpath);
2184 }
2185
2186 try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
2187 pathkeys, jointype, extra);
2188
2189 /*
2190 * Try generating a memoize path and see if that makes the nested
2191 * loop any cheaper.
2192 */
2193 mpath = get_memoize_path(root, innerrel, outerrel,
2194 innerpath, outerpath, jointype,
2195 extra);
2196 if (mpath != NULL)
2197 try_partial_nestloop_path(root, joinrel, outerpath, mpath,
2198 pathkeys, jointype, extra);
2199 }
2200
2201 /* Also consider materialized form of the cheapest inner path */
2202 if (matpath != NULL)
2203 try_partial_nestloop_path(root, joinrel, outerpath, matpath,
2204 pathkeys, jointype, extra);
2205 }
2206 }
2207
2208 /*
2209 * hash_inner_and_outer
2210 * Create hashjoin join paths by explicitly hashing both the outer and
2211 * inner keys of each available hash clause.
2212 *
2213 * 'joinrel' is the join relation
2214 * 'outerrel' is the outer join relation
2215 * 'innerrel' is the inner join relation
2216 * 'jointype' is the type of join to do
2217 * 'extra' contains additional input values
2218 */
2219 static void
2220 hash_inner_and_outer(PlannerInfo *root,
2221 RelOptInfo *joinrel,
2222 RelOptInfo *outerrel,
2223 RelOptInfo *innerrel,
2224 JoinType jointype,
2225 JoinPathExtraData *extra)
2226 {
2227 JoinType save_jointype = jointype;
2228 bool isouterjoin = IS_OUTER_JOIN(jointype);
2229 List *hashclauses;
2230 ListCell *l;
2231
2232 /*
2233 * We need to build only one hashclauses list for any given pair of outer
2234 * and inner relations; all of the hashable clauses will be used as keys.
2235 *
2236 * Scan the join's restrictinfo list to find hashjoinable clauses that are
2237 * usable with this pair of sub-relations.
2238 */
2239 hashclauses = NIL;
2240 foreach(l, extra->restrictlist)
2241 {
2242 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2243
2244 /*
2245 * If processing an outer join, only use its own join clauses for
2246 * hashing. For inner joins we need not be so picky.
2247 */
2248 if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2249 continue;
2250
2251 if (!restrictinfo->can_join ||
2252 restrictinfo->hashjoinoperator == InvalidOid)
2253 continue; /* not hashjoinable */
2254
2255 /*
2256 * Check if clause has the form "outer op inner" or "inner op outer".
2257 */
2258 if (!clause_sides_match_join(restrictinfo, outerrel->relids,
2259 innerrel->relids))
2260 continue; /* no good for these input relations */
2261
2262 /*
2263 * If clause has the form "inner op outer", check if its operator has
2264 * valid commutator. This is necessary because hashclauses in this
2265 * form will get commuted in createplan.c to put the outer var on the
2266 * left (see get_switched_clauses). This probably shouldn't ever
2267 * fail, since hashable operators ought to have commutators, but be
2268 * paranoid.
2269 *
2270 * The clause being hashjoinable indicates that it's an OpExpr.
2271 */
2272 if (!restrictinfo->outer_is_left &&
2273 !OidIsValid(get_commutator(castNode(OpExpr, restrictinfo->clause)->opno)))
2274 continue;
2275
2276 hashclauses = lappend(hashclauses, restrictinfo);
2277 }
2278
2279 /* If we found any usable hashclauses, make paths */
2280 if (hashclauses)
2281 {
2282 /*
2283 * We consider both the cheapest-total-cost and cheapest-startup-cost
2284 * outer paths. There's no need to consider any but the
2285 * cheapest-total-cost inner path, however.
2286 */
2287 Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
2288 Path *cheapest_total_outer = outerrel->cheapest_total_path;
2289 Path *cheapest_total_inner = innerrel->cheapest_total_path;
2290
2291 /*
2292 * If either cheapest-total path is parameterized by the other rel, we
2293 * can't use a hashjoin. (There's no use looking for alternative
2294 * input paths, since these should already be the least-parameterized
2295 * available paths.)
2296 */
2297 if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
2298 PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
2299 return;
2300
2301 /* Unique-ify if need be; we ignore parameterized possibilities */
2302 if (jointype == JOIN_UNIQUE_OUTER)
2303 {
2304 cheapest_total_outer = (Path *)
2305 create_unique_path(root, outerrel,
2306 cheapest_total_outer, extra->sjinfo);
2307 Assert(cheapest_total_outer);
2308 jointype = JOIN_INNER;
2309 try_hashjoin_path(root,
2310 joinrel,
2311 cheapest_total_outer,
2312 cheapest_total_inner,
2313 hashclauses,
2314 jointype,
2315 extra);
2316 /* no possibility of cheap startup here */
2317 }
2318 else if (jointype == JOIN_UNIQUE_INNER)
2319 {
2320 cheapest_total_inner = (Path *)
2321 create_unique_path(root, innerrel,
2322 cheapest_total_inner, extra->sjinfo);
2323 Assert(cheapest_total_inner);
2324 jointype = JOIN_INNER;
2325 try_hashjoin_path(root,
2326 joinrel,
2327 cheapest_total_outer,
2328 cheapest_total_inner,
2329 hashclauses,
2330 jointype,
2331 extra);
2332 if (cheapest_startup_outer != NULL &&
2333 cheapest_startup_outer != cheapest_total_outer)
2334 try_hashjoin_path(root,
2335 joinrel,
2336 cheapest_startup_outer,
2337 cheapest_total_inner,
2338 hashclauses,
2339 jointype,
2340 extra);
2341 }
2342 else
2343 {
2344 /*
2345 * For other jointypes, we consider the cheapest startup outer
2346 * together with the cheapest total inner, and then consider
2347 * pairings of cheapest-total paths including parameterized ones.
2348 * There is no use in generating parameterized paths on the basis
2349 * of possibly cheap startup cost, so this is sufficient.
2350 */
2351 ListCell *lc1;
2352 ListCell *lc2;
2353
2354 if (cheapest_startup_outer != NULL)
2355 try_hashjoin_path(root,
2356 joinrel,
2357 cheapest_startup_outer,
2358 cheapest_total_inner,
2359 hashclauses,
2360 jointype,
2361 extra);
2362
2363 foreach(lc1, outerrel->cheapest_parameterized_paths)
2364 {
2365 Path *outerpath = (Path *) lfirst(lc1);
2366
2367 /*
2368 * We cannot use an outer path that is parameterized by the
2369 * inner rel.
2370 */
2371 if (PATH_PARAM_BY_REL(outerpath, innerrel))
2372 continue;
2373
2374 foreach(lc2, innerrel->cheapest_parameterized_paths)
2375 {
2376 Path *innerpath = (Path *) lfirst(lc2);
2377
2378 /*
2379 * We cannot use an inner path that is parameterized by
2380 * the outer rel, either.
2381 */
2382 if (PATH_PARAM_BY_REL(innerpath, outerrel))
2383 continue;
2384
2385 if (outerpath == cheapest_startup_outer &&
2386 innerpath == cheapest_total_inner)
2387 continue; /* already tried it */
2388
2389 try_hashjoin_path(root,
2390 joinrel,
2391 outerpath,
2392 innerpath,
2393 hashclauses,
2394 jointype,
2395 extra);
2396 }
2397 }
2398 }
2399
2400 /*
2401 * If the joinrel is parallel-safe, we may be able to consider a
2402 * partial hash join.
2403 *
2404 * However, we can't handle JOIN_UNIQUE_OUTER, because the outer path
2405 * will be partial, and therefore we won't be able to properly
2406 * guarantee uniqueness.
2407 *
2408 * Similarly, we can't handle JOIN_RIGHT_SEMI, because the hash table
2409 * is either a shared hash table or a private hash table per backend.
2410 * In the shared case, there is no concurrency protection for the
2411 * match flags, so multiple workers could inspect and set the flags
2412 * concurrently, potentially producing incorrect results. In the
2413 * private case, each worker has its own copy of the hash table, so no
2414 * single process has all the match flags.
2415 *
2416 * Also, the resulting path must not be parameterized.
2417 */
2418 if (joinrel->consider_parallel &&
2419 save_jointype != JOIN_UNIQUE_OUTER &&
2420 save_jointype != JOIN_RIGHT_SEMI &&
2421 outerrel->partial_pathlist != NIL &&
2422 bms_is_empty(joinrel->lateral_relids))
2423 {
2424 Path *cheapest_partial_outer;
2425 Path *cheapest_partial_inner = NULL;
2426 Path *cheapest_safe_inner = NULL;
2427
2428 cheapest_partial_outer =
2429 (Path *) linitial(outerrel->partial_pathlist);
2430
2431 /*
2432 * Can we use a partial inner plan too, so that we can build a
2433 * shared hash table in parallel? We can't handle
2434 * JOIN_UNIQUE_INNER because we can't guarantee uniqueness.
2435 */
2436 if (innerrel->partial_pathlist != NIL &&
2437 save_jointype != JOIN_UNIQUE_INNER &&
2438 enable_parallel_hash)
2439 {
2440 cheapest_partial_inner =
2441 (Path *) linitial(innerrel->partial_pathlist);
2442 try_partial_hashjoin_path(root, joinrel,
2443 cheapest_partial_outer,
2444 cheapest_partial_inner,
2445 hashclauses, jointype, extra,
2446 true /* parallel_hash */ );
2447 }
2448
2449 /*
2450 * Normally, given that the joinrel is parallel-safe, the cheapest
2451 * total inner path will also be parallel-safe, but if not, we'll
2452 * have to search for the cheapest safe, unparameterized inner
2453 * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
2454 * inner path. If full, right, or right-anti join, we can't use
2455 * parallelism (building the hash table in each backend) because
2456 * no one process has all the match bits.
2457 */
2458 if (save_jointype == JOIN_FULL ||
2459 save_jointype == JOIN_RIGHT ||
2460 save_jointype == JOIN_RIGHT_ANTI)
2461 cheapest_safe_inner = NULL;
2462 else if (cheapest_total_inner->parallel_safe)
2463 cheapest_safe_inner = cheapest_total_inner;
2464 else if (save_jointype != JOIN_UNIQUE_INNER)
2465 cheapest_safe_inner =
2466 get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
2467
2468 if (cheapest_safe_inner != NULL)
2469 try_partial_hashjoin_path(root, joinrel,
2470 cheapest_partial_outer,
2471 cheapest_safe_inner,
2472 hashclauses, jointype, extra,
2473 false /* parallel_hash */ );
2474 }
2475 }
2476 }
2477
2478 /*
2479 * select_mergejoin_clauses
2480 * Select mergejoin clauses that are usable for a particular join.
2481 * Returns a list of RestrictInfo nodes for those clauses.
2482 *
2483 * *mergejoin_allowed is normally set to true, but it is set to false if
2484 * this is a right-semi join, or this is a right/right-anti/full join and
2485 * there are nonmergejoinable join clauses. The executor's mergejoin
2486 * machinery cannot handle such cases, so we have to avoid generating a
2487 * mergejoin plan. (Note that this flag does NOT consider whether there are
2488 * actually any mergejoinable clauses. This is correct because in some
2489 * cases we need to build a clauseless mergejoin. Simply returning NIL is
2490 * therefore not enough to distinguish safe from unsafe cases.)
2491 *
2492 * We also mark each selected RestrictInfo to show which side is currently
2493 * being considered as outer. These are transient markings that are only
2494 * good for the duration of the current add_paths_to_joinrel() call!
2495 *
2496 * We examine each restrictinfo clause known for the join to see
2497 * if it is mergejoinable and involves vars from the two sub-relations
2498 * currently of interest.
2499 */
2500 static List *
2501 select_mergejoin_clauses(PlannerInfo *root,
2502 RelOptInfo *joinrel,
2503 RelOptInfo *outerrel,
2504 RelOptInfo *innerrel,
2505 List *restrictlist,
2506 JoinType jointype,
2507 bool *mergejoin_allowed)
2508 {
2509 List *result_list = NIL;
2510 bool isouterjoin = IS_OUTER_JOIN(jointype);
2511 bool have_nonmergeable_joinclause = false;
2512 ListCell *l;
2513
2514 /*
2515 * For now we do not support RIGHT_SEMI join in mergejoin: the benefit of
2516 * swapping inputs tends to be small here.
2517 */
2518 if (jointype == JOIN_RIGHT_SEMI)
2519 {
2520 *mergejoin_allowed = false;
2521 return NIL;
2522 }
2523
2524 foreach(l, restrictlist)
2525 {
2526 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2527
2528 /*
2529 * If processing an outer join, only use its own join clauses in the
2530 * merge. For inner joins we can use pushed-down clauses too. (Note:
2531 * we don't set have_nonmergeable_joinclause here because pushed-down
2532 * clauses will become otherquals not joinquals.)
2533 */
2534 if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2535 continue;
2536
2537 /* Check that clause is a mergeable operator clause */
2538 if (!restrictinfo->can_join ||
2539 restrictinfo->mergeopfamilies == NIL)
2540 {
2541 /*
2542 * The executor can handle extra joinquals that are constants, but
2543 * not anything else, when doing right/right-anti/full merge join.
2544 * (The reason to support constants is so we can do FULL JOIN ON
2545 * FALSE.)
2546 */
2547 if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
2548 have_nonmergeable_joinclause = true;
2549 continue; /* not mergejoinable */
2550 }
2551
2552 /*
2553 * Check if clause has the form "outer op inner" or "inner op outer".
2554 */
2555 if (!clause_sides_match_join(restrictinfo, outerrel->relids,
2556 innerrel->relids))
2557 {
2558 have_nonmergeable_joinclause = true;
2559 continue; /* no good for these input relations */
2560 }
2561
2562 /*
2563 * If clause has the form "inner op outer", check if its operator has
2564 * valid commutator. This is necessary because mergejoin clauses in
2565 * this form will get commuted in createplan.c to put the outer var on
2566 * the left (see get_switched_clauses). This probably shouldn't ever
2567 * fail, since mergejoinable operators ought to have commutators, but
2568 * be paranoid.
2569 *
2570 * The clause being mergejoinable indicates that it's an OpExpr.
2571 */
2572 if (!restrictinfo->outer_is_left &&
2573 !OidIsValid(get_commutator(castNode(OpExpr, restrictinfo->clause)->opno)))
2574 {
2575 have_nonmergeable_joinclause = true;
2576 continue;
2577 }
2578
2579 /*
2580 * Insist that each side have a non-redundant eclass. This
2581 * restriction is needed because various bits of the planner expect
2582 * that each clause in a merge be associable with some pathkey in a
2583 * canonical pathkey list, but redundant eclasses can't appear in
2584 * canonical sort orderings. (XXX it might be worth relaxing this,
2585 * but not enough time to address it for 8.3.)
2586 */
2587 update_mergeclause_eclasses(root, restrictinfo);
2588
2589 if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
2590 EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
2591 {
2592 have_nonmergeable_joinclause = true;
2593 continue; /* can't handle redundant eclasses */
2594 }
2595
2596 result_list = lappend(result_list, restrictinfo);
2597 }
2598
2599 /*
2600 * Report whether mergejoin is allowed (see comment at top of function).
2601 */
2602 switch (jointype)
2603 {
2604 case JOIN_RIGHT:
2605 case JOIN_RIGHT_ANTI:
2606 case JOIN_FULL:
2607 *mergejoin_allowed = !have_nonmergeable_joinclause;
2608 break;
2609 default:
2610 *mergejoin_allowed = true;
2611 break;
2612 }
2613
2614 return result_list;
2615 }