/*------------------------------------------------------------------------- * * joinpath.c * Routines to find all possible paths for processing a set of joins * * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION * src/backend/optimizer/path/joinpath.c * *------------------------------------------------------------------------- */ #include "postgres.h" #include #include "executor/executor.h" #include "foreign/fdwapi.h" #include "nodes/nodeFuncs.h" #include "optimizer/cost.h" #include "optimizer/optimizer.h" #include "optimizer/pathnode.h" #include "optimizer/paths.h" #include "optimizer/placeholder.h" #include "optimizer/planmain.h" #include "optimizer/restrictinfo.h" #include "utils/lsyscache.h" #include "utils/typcache.h" /* Hook for plugins to get control in add_paths_to_joinrel() */ set_join_pathlist_hook_type set_join_pathlist_hook = NULL; /* * Paths parameterized by a parent rel can be considered to be parameterized * by any of its children, when we are performing partitionwise joins. These * macros simplify checking for such cases. Beware multiple eval of args. */ #define PATH_PARAM_BY_PARENT(path, rel) \ ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), \ (rel)->top_parent_relids)) #define PATH_PARAM_BY_REL_SELF(path, rel) \ ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids)) #define PATH_PARAM_BY_REL(path, rel) \ (PATH_PARAM_BY_REL_SELF(path, rel) || PATH_PARAM_BY_PARENT(path, rel)) static void try_partial_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys, JoinType jointype, JoinPathExtraData *extra); static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra); static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra); static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra); static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total); static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra); static List *select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed); static void generate_mergejoin_paths(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *innerrel, Path *outerpath, JoinType jointype, JoinPathExtraData *extra, bool useallclauses, Path *inner_cheapest_total, List *merge_pathkeys, bool is_partial); /* * add_paths_to_joinrel * Given a join relation and two component rels from which it can be made, * consider all possible paths that use the two component rels as outer * and inner rel respectively. Add these paths to the join rel's pathlist * if they survive comparison with other paths (and remove any existing * paths that are dominated by these paths). * * Modifies the pathlist field of the joinrel node to contain the best * paths found so far. * * jointype is not necessarily the same as sjinfo->jointype; it might be * "flipped around" if we are considering joining the rels in the opposite * direction from what's indicated in sjinfo. * * Also, this routine and others in this module accept the special JoinTypes * JOIN_UNIQUE_OUTER and JOIN_UNIQUE_INNER to indicate that we should * unique-ify the outer or inner relation and then apply a regular inner * join. These values are not allowed to propagate outside this module, * however. Path cost estimation code may need to recognize that it's * dealing with such a case --- the combination of nominal jointype INNER * with sjinfo->jointype == JOIN_SEMI indicates that. */ void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist) { JoinPathExtraData extra; bool mergejoin_allowed = true; ListCell *lc; Relids joinrelids; /* * PlannerInfo doesn't contain the SpecialJoinInfos created for joins * between child relations, even if there is a SpecialJoinInfo node for * the join between the topmost parents. So, while calculating Relids set * representing the restriction, consider relids of topmost parent of * partitions. */ if (joinrel->reloptkind == RELOPT_OTHER_JOINREL) joinrelids = joinrel->top_parent_relids; else joinrelids = joinrel->relids; extra.restrictlist = restrictlist; extra.mergeclause_list = NIL; extra.sjinfo = sjinfo; extra.param_source_rels = NULL; /* * See if the inner relation is provably unique for this outer rel. * * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't * matter since the executor can make the equivalent optimization anyway; * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we * must be considering a semijoin whose inner side is not provably unique * (else reduce_unique_semijoins would've simplified it), so there's no * point in calling innerrel_is_unique. However, if the LHS covers all of * the semijoin's min_lefthand, then it's appropriate to set inner_unique * because the path produced by create_unique_path will be unique relative * to the LHS. (If we have an LHS that's only part of the min_lefthand, * that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid * letting that value escape this module. */ switch (jointype) { case JOIN_SEMI: case JOIN_ANTI: /* * XXX it may be worth proving this to allow a Memoize to be * considered for Nested Loop Semi/Anti Joins. */ extra.inner_unique = false; /* well, unproven */ break; case JOIN_UNIQUE_INNER: extra.inner_unique = bms_is_subset(sjinfo->min_lefthand, outerrel->relids); break; case JOIN_UNIQUE_OUTER: extra.inner_unique = innerrel_is_unique(root, joinrel->relids, outerrel->relids, innerrel, JOIN_INNER, restrictlist, false); break; default: extra.inner_unique = innerrel_is_unique(root, joinrel->relids, outerrel->relids, innerrel, jointype, restrictlist, false); break; } /* * Find potential mergejoin clauses. We can skip this if we are not * interested in doing a mergejoin. However, mergejoin may be our only * way of implementing a full outer join, so override enable_mergejoin if * it's a full join. */ if (enable_mergejoin || jointype == JOIN_FULL) extra.mergeclause_list = select_mergejoin_clauses(root, joinrel, outerrel, innerrel, restrictlist, jointype, &mergejoin_allowed); /* * If it's SEMI, ANTI, or inner_unique join, compute correction factors * for cost estimation. These will be the same for all paths. */ if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique) compute_semi_anti_join_factors(root, joinrel, outerrel, innerrel, jointype, sjinfo, restrictlist, &extra.semifactors); /* * Decide whether it's sensible to generate parameterized paths for this * joinrel, and if so, which relations such paths should require. There * is usually no need to create a parameterized result path unless there * is a join order restriction that prevents joining one of our input rels * directly to the parameter source rel instead of joining to the other * input rel. (But see allow_star_schema_join().) This restriction * reduces the number of parameterized paths we have to deal with at * higher join levels, without compromising the quality of the resulting * plan. We express the restriction as a Relids set that must overlap the * parameterization of any proposed join path. Note: param_source_rels * should contain only baserels, not OJ relids, so starting from * all_baserels not all_query_rels is correct. */ foreach(lc, root->join_info_list) { SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc); /* * SJ is relevant to this join if we have some part of its RHS * (possibly not all of it), and haven't yet joined to its LHS. (This * test is pretty simplistic, but should be sufficient considering the * join has already been proven legal.) If the SJ is relevant, it * presents constraints for joining to anything not in its RHS. */ if (bms_overlap(joinrelids, sjinfo2->min_righthand) && !bms_overlap(joinrelids, sjinfo2->min_lefthand)) extra.param_source_rels = bms_join(extra.param_source_rels, bms_difference(root->all_baserels, sjinfo2->min_righthand)); /* full joins constrain both sides symmetrically */ if (sjinfo2->jointype == JOIN_FULL && bms_overlap(joinrelids, sjinfo2->min_lefthand) && !bms_overlap(joinrelids, sjinfo2->min_righthand)) extra.param_source_rels = bms_join(extra.param_source_rels, bms_difference(root->all_baserels, sjinfo2->min_lefthand)); } /* * However, when a LATERAL subquery is involved, there will simply not be * any paths for the joinrel that aren't parameterized by whatever the * subquery is parameterized by, unless its parameterization is resolved * within the joinrel. So we might as well allow additional dependencies * on whatever residual lateral dependencies the joinrel will have. */ extra.param_source_rels = bms_add_members(extra.param_source_rels, joinrel->lateral_relids); /* * 1. Consider mergejoin paths where both relations must be explicitly * sorted. Skip this if we can't mergejoin. */ if (mergejoin_allowed) sort_inner_and_outer(root, joinrel, outerrel, innerrel, jointype, &extra); /* * 2. Consider paths where the outer relation need not be explicitly * sorted. This includes both nestloops and mergejoins where the outer * path is already ordered. Again, skip this if we can't mergejoin. * (That's okay because we know that nestloop can't handle * right/right-anti/right-semi/full joins at all, so it wouldn't work in * the prohibited cases either.) */ if (mergejoin_allowed) match_unsorted_outer(root, joinrel, outerrel, innerrel, jointype, &extra); #ifdef NOT_USED /* * 3. Consider paths where the inner relation need not be explicitly * sorted. This includes mergejoins only (nestloops were already built in * match_unsorted_outer). * * Diked out as redundant 2/13/2000 -- tgl. There isn't any really * significant difference between the inner and outer side of a mergejoin, * so match_unsorted_inner creates no paths that aren't equivalent to * those made by match_unsorted_outer when add_paths_to_joinrel() is * invoked with the two rels given in the other order. */ if (mergejoin_allowed) match_unsorted_inner(root, joinrel, outerrel, innerrel, jointype, &extra); #endif /* * 4. Consider paths where both outer and inner relations must be hashed * before being joined. As above, disregard enable_hashjoin for full * joins, because there may be no other alternative. */ if (enable_hashjoin || jointype == JOIN_FULL) hash_inner_and_outer(root, joinrel, outerrel, innerrel, jointype, &extra); /* * 5. If inner and outer relations are foreign tables (or joins) belonging * to the same server and assigned to the same user to check access * permissions as, give the FDW a chance to push down joins. */ if (joinrel->fdwroutine && joinrel->fdwroutine->GetForeignJoinPaths) joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel, outerrel, innerrel, jointype, &extra); /* * 6. Finally, give extensions a chance to manipulate the path list. They * could add new paths (such as CustomPaths) by calling add_path(), or * add_partial_path() if parallel aware. They could also delete or modify * paths added by the core code. */ if (set_join_pathlist_hook) set_join_pathlist_hook(root, joinrel, outerrel, innerrel, jointype, &extra); } /* * We override the param_source_rels heuristic to accept nestloop paths in * which the outer rel satisfies some but not all of the inner path's * parameterization. This is necessary to get good plans for star-schema * scenarios, in which a parameterized path for a large table may require * parameters from multiple small tables that will not get joined directly to * each other. We can handle that by stacking nestloops that have the small * tables on the outside; but this breaks the rule the param_source_rels * heuristic is based on, namely that parameters should not be passed down * across joins unless there's a join-order-constraint-based reason to do so. * So we ignore the param_source_rels restriction when this case applies. * * allow_star_schema_join() returns true if the param_source_rels restriction * should be overridden, ie, it's okay to perform this join. */ static inline bool allow_star_schema_join(PlannerInfo *root, Relids outerrelids, Relids inner_paramrels) { /* * It's a star-schema case if the outer rel provides some but not all of * the inner rel's parameterization. */ return (bms_overlap(inner_paramrels, outerrelids) && bms_nonempty_difference(inner_paramrels, outerrelids)); } /* * If the parameterization is only partly satisfied by the outer rel, * the unsatisfied part can't include any outer-join relids that could * null rels of the satisfied part. That would imply that we're trying * to use a clause involving a Var with nonempty varnullingrels at * a join level where that value isn't yet computable. * * In practice, this test never finds a problem because earlier join order * restrictions prevent us from attempting a join that would cause a problem. * (That's unsurprising, because the code worked before we ever added * outer-join relids to expression relids.) It still seems worth checking * as a backstop, but we only do so in assert-enabled builds. */ #ifdef USE_ASSERT_CHECKING static inline bool have_unsafe_outer_join_ref(PlannerInfo *root, Relids outerrelids, Relids inner_paramrels) { bool result = false; Relids unsatisfied = bms_difference(inner_paramrels, outerrelids); Relids satisfied = bms_intersect(inner_paramrels, outerrelids); if (bms_overlap(unsatisfied, root->outer_join_rels)) { ListCell *lc; foreach(lc, root->join_info_list) { SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc); if (!bms_is_member(sjinfo->ojrelid, unsatisfied)) continue; /* not relevant */ if (bms_overlap(satisfied, sjinfo->min_righthand) || (sjinfo->jointype == JOIN_FULL && bms_overlap(satisfied, sjinfo->min_lefthand))) { result = true; /* doesn't work */ break; } } } /* Waste no memory when we reject a path here */ bms_free(unsatisfied); bms_free(satisfied); return result; } #endif /* USE_ASSERT_CHECKING */ /* * paraminfo_get_equal_hashops * Determine if the clauses in param_info and innerrel's lateral vars * can be hashed. * Returns true if hashing is possible, otherwise false. * * Additionally, on success we collect the outer expressions and the * appropriate equality operators for each hashable parameter to innerrel. * These are returned in parallel lists in *param_exprs and *operators. * We also set *binary_mode to indicate whether strict binary matching is * required. */ static bool paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info, RelOptInfo *outerrel, RelOptInfo *innerrel, List *ph_lateral_vars, List **param_exprs, List **operators, bool *binary_mode) { List *lateral_vars; ListCell *lc; *param_exprs = NIL; *operators = NIL; *binary_mode = false; /* Add join clauses from param_info to the hash key */ if (param_info != NULL) { List *clauses = param_info->ppi_clauses; foreach(lc, clauses) { RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); OpExpr *opexpr; Node *expr; Oid hasheqoperator; opexpr = (OpExpr *) rinfo->clause; /* * Bail if the rinfo is not compatible. We need a join OpExpr * with 2 args. */ if (!IsA(opexpr, OpExpr) || list_length(opexpr->args) != 2 || !clause_sides_match_join(rinfo, outerrel->relids, innerrel->relids)) { list_free(*operators); list_free(*param_exprs); return false; } if (rinfo->outer_is_left) { expr = (Node *) linitial(opexpr->args); hasheqoperator = rinfo->left_hasheqoperator; } else { expr = (Node *) lsecond(opexpr->args); hasheqoperator = rinfo->right_hasheqoperator; } /* can't do memoize if we can't hash the outer type */ if (!OidIsValid(hasheqoperator)) { list_free(*operators); list_free(*param_exprs); return false; } /* * 'expr' may already exist as a parameter from a previous item in * ppi_clauses. No need to include it again, however we'd better * ensure we do switch into binary mode if required. See below. */ if (!list_member(*param_exprs, expr)) { *operators = lappend_oid(*operators, hasheqoperator); *param_exprs = lappend(*param_exprs, expr); } /* * When the join operator is not hashable then it's possible that * the operator will be able to distinguish something that the * hash equality operator could not. For example with floating * point types -0.0 and +0.0 are classed as equal by the hash * function and equality function, but some other operator may be * able to tell those values apart. This means that we must put * memoize into binary comparison mode so that it does bit-by-bit * comparisons rather than a "logical" comparison as it would * using the hash equality operator. */ if (!OidIsValid(rinfo->hashjoinoperator)) *binary_mode = true; } } /* Now add any lateral vars to the cache key too */ lateral_vars = list_concat(ph_lateral_vars, innerrel->lateral_vars); foreach(lc, lateral_vars) { Node *expr = (Node *) lfirst(lc); TypeCacheEntry *typentry; /* Reject if there are any volatile functions in lateral vars */ if (contain_volatile_functions(expr)) { list_free(*operators); list_free(*param_exprs); return false; } typentry = lookup_type_cache(exprType(expr), TYPECACHE_HASH_PROC | TYPECACHE_EQ_OPR); /* can't use memoize without a valid hash proc and equals operator */ if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr)) { list_free(*operators); list_free(*param_exprs); return false; } /* * 'expr' may already exist as a parameter from the ppi_clauses. No * need to include it again, however we'd better ensure we do switch * into binary mode. */ if (!list_member(*param_exprs, expr)) { *operators = lappend_oid(*operators, typentry->eq_opr); *param_exprs = lappend(*param_exprs, expr); } /* * We must go into binary mode as we don't have too much of an idea of * how these lateral Vars are being used. See comment above when we * set *binary_mode for the non-lateral Var case. This could be * relaxed a bit if we had the RestrictInfos and knew the operators * being used, however for cases like Vars that are arguments to * functions we must operate in binary mode as we don't have * visibility into what the function is doing with the Vars. */ *binary_mode = true; } /* We're okay to use memoize */ return true; } /* * extract_lateral_vars_from_PHVs * Extract lateral references within PlaceHolderVars that are due to be * evaluated at 'innerrelids'. */ static List * extract_lateral_vars_from_PHVs(PlannerInfo *root, Relids innerrelids) { List *ph_lateral_vars = NIL; ListCell *lc; /* Nothing would be found if the query contains no LATERAL RTEs */ if (!root->hasLateralRTEs) return NIL; /* * No need to consider PHVs that are due to be evaluated at joinrels, * since we do not add Memoize nodes on top of joinrel paths. */ if (bms_membership(innerrelids) == BMS_MULTIPLE) return NIL; foreach(lc, root->placeholder_list) { PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc); List *vars; ListCell *cell; /* PHV is uninteresting if no lateral refs */ if (phinfo->ph_lateral == NULL) continue; /* PHV is uninteresting if not due to be evaluated at innerrelids */ if (!bms_equal(phinfo->ph_eval_at, innerrelids)) continue; /* * If the PHV does not reference any rels in innerrelids, use its * contained expression as a cache key rather than extracting the * Vars/PHVs from it and using those. This can be beneficial in cases * where the expression results in fewer distinct values to cache * tuples for. */ if (!bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr), innerrelids)) { ph_lateral_vars = lappend(ph_lateral_vars, phinfo->ph_var->phexpr); continue; } /* Fetch Vars and PHVs of lateral references within PlaceHolderVars */ vars = pull_vars_of_level((Node *) phinfo->ph_var->phexpr, 0); foreach(cell, vars) { Node *node = (Node *) lfirst(cell); if (IsA(node, Var)) { Var *var = (Var *) node; Assert(var->varlevelsup == 0); if (bms_is_member(var->varno, phinfo->ph_lateral)) ph_lateral_vars = lappend(ph_lateral_vars, node); } else if (IsA(node, PlaceHolderVar)) { PlaceHolderVar *phv = (PlaceHolderVar *) node; Assert(phv->phlevelsup == 0); if (bms_is_subset(find_placeholder_info(root, phv)->ph_eval_at, phinfo->ph_lateral)) ph_lateral_vars = lappend(ph_lateral_vars, node); } else Assert(false); } list_free(vars); } return ph_lateral_vars; } /* * get_memoize_path * If possible, make and return a Memoize path atop of 'inner_path'. * Otherwise return NULL. * * Note that currently we do not add Memoize nodes on top of join relation * paths. This is because the ParamPathInfos for join relation paths do not * maintain ppi_clauses, as the set of relevant clauses varies depending on how * the join is formed. In addition, joinrels do not maintain lateral_vars. So * we do not have a way to extract cache keys from joinrels. */ static Path * get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra) { List *param_exprs; List *hash_operators; ListCell *lc; bool binary_mode; List *ph_lateral_vars; /* Obviously not if it's disabled */ if (!enable_memoize) return NULL; /* * We can safely not bother with all this unless we expect to perform more * than one inner scan. The first scan is always going to be a cache * miss. This would likely fail later anyway based on costs, so this is * really just to save some wasted effort. */ if (outer_path->parent->rows < 2) return NULL; /* * Extract lateral Vars/PHVs within PlaceHolderVars that are due to be * evaluated at innerrel. These lateral Vars/PHVs could be used as * memoize cache keys. */ ph_lateral_vars = extract_lateral_vars_from_PHVs(root, innerrel->relids); /* * We can only have a memoize node when there's some kind of cache key, * either parameterized path clauses or lateral Vars. No cache key sounds * more like something a Materialize node might be more useful for. */ if ((inner_path->param_info == NULL || inner_path->param_info->ppi_clauses == NIL) && innerrel->lateral_vars == NIL && ph_lateral_vars == NIL) return NULL; /* * Currently we don't do this for SEMI and ANTI joins unless they're * marked as inner_unique. This is because nested loop SEMI/ANTI joins * don't scan the inner node to completion, which will mean memoize cannot * mark the cache entry as complete. * * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique * = true. Should we? See add_paths_to_joinrel() */ if (!extra->inner_unique && (jointype == JOIN_SEMI || jointype == JOIN_ANTI)) return NULL; /* * Memoize normally marks cache entries as complete when it runs out of * tuples to read from its subplan. However, with unique joins, Nested * Loop will skip to the next outer tuple after finding the first matching * inner tuple. This means that we may not read the inner side of the * join to completion which leaves no opportunity to mark the cache entry * as complete. To work around that, when the join is unique we * automatically mark cache entries as complete after fetching the first * tuple. This works when the entire join condition is parameterized. * Otherwise, when the parameterization is only a subset of the join * condition, we can't be sure which part of it causes the join to be * unique. This means there are no guarantees that only 1 tuple will be * read. We cannot mark the cache entry as complete after reading the * first tuple without that guarantee. This means the scope of Memoize * node's usefulness is limited to only outer rows that have no join * partner as this is the only case where Nested Loop would exhaust the * inner scan of a unique join. Since the scope is limited to that, we * just don't bother making a memoize path in this case. * * Lateral vars needn't be considered here as they're not considered when * determining if the join is unique. */ if (extra->inner_unique) { Bitmapset *ppi_serials; if (inner_path->param_info == NULL) return NULL; ppi_serials = inner_path->param_info->ppi_serials; foreach_node(RestrictInfo, rinfo, extra->restrictlist) { if (!bms_is_member(rinfo->rinfo_serial, ppi_serials)) return NULL; } } /* * We can't use a memoize node if there are volatile functions in the * inner rel's target list or restrict list. A cache hit could reduce the * number of calls to these functions. */ if (contain_volatile_functions((Node *) innerrel->reltarget)) return NULL; foreach(lc, innerrel->baserestrictinfo) { RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); if (contain_volatile_functions((Node *) rinfo)) return NULL; } /* * Also check the parameterized path restrictinfos for volatile functions. * Indexed functions must be immutable so shouldn't have any volatile * functions, however, with a lateral join the inner scan may not be an * index scan. */ if (inner_path->param_info != NULL) { foreach(lc, inner_path->param_info->ppi_clauses) { RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); if (contain_volatile_functions((Node *) rinfo)) return NULL; } } /* Check if we have hash ops for each parameter to the path */ if (paraminfo_get_equal_hashops(root, inner_path->param_info, outerrel->top_parent ? outerrel->top_parent : outerrel, innerrel, ph_lateral_vars, ¶m_exprs, &hash_operators, &binary_mode)) { return (Path *) create_memoize_path(root, innerrel, inner_path, param_exprs, hash_operators, extra->inner_unique, binary_mode, outer_path->rows); } return NULL; } /* * try_nestloop_path * Consider a nestloop join path; if it appears useful, push it into * the joinrel's pathlist via add_path(). */ static void try_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra) { Relids required_outer; JoinCostWorkspace workspace; RelOptInfo *innerrel = inner_path->parent; RelOptInfo *outerrel = outer_path->parent; Relids innerrelids; Relids outerrelids; Relids inner_paramrels = PATH_REQ_OUTER(inner_path); Relids outer_paramrels = PATH_REQ_OUTER(outer_path); /* * If we are forming an outer join at this join, it's nonsensical to use * an input path that uses the outer join as part of its parameterization. * (This can happen despite our join order restrictions, since those apply * to what is in an input relation not what its parameters are.) */ if (extra->sjinfo->ojrelid != 0 && (bms_is_member(extra->sjinfo->ojrelid, inner_paramrels) || bms_is_member(extra->sjinfo->ojrelid, outer_paramrels))) return; /* * Any parameterization of the input paths refers to topmost parents of * the relevant relations, because reparameterize_path_by_child() hasn't * been called yet. So we must consider topmost parents of the relations * being joined, too, while determining parameterization of the result and * checking for disallowed parameterization cases. */ if (innerrel->top_parent_relids) innerrelids = innerrel->top_parent_relids; else innerrelids = innerrel->relids; if (outerrel->top_parent_relids) outerrelids = outerrel->top_parent_relids; else outerrelids = outerrel->relids; /* * Check to see if proposed path is still parameterized, and reject if the * parameterization wouldn't be sensible --- unless allow_star_schema_join * says to allow it anyway. */ required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels, innerrelids, inner_paramrels); if (required_outer && !bms_overlap(required_outer, extra->param_source_rels) && !allow_star_schema_join(root, outerrelids, inner_paramrels)) { /* Waste no memory when we reject a path here */ bms_free(required_outer); return; } /* If we got past that, we shouldn't have any unsafe outer-join refs */ Assert(!have_unsafe_outer_join_ref(root, outerrelids, inner_paramrels)); /* * If the inner path is parameterized, it is parameterized by the topmost * parent of the outer rel, not the outer rel itself. We will need to * translate the parameterization, if this path is chosen, during * create_plan(). Here we just check whether we will be able to perform * the translation, and if not avoid creating a nestloop path. */ if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent) && !path_is_reparameterizable_by_child(inner_path, outer_path->parent)) { bms_free(required_outer); return; } /* * Do a precheck to quickly eliminate obviously-inferior paths. We * calculate a cheap lower bound on the path's cost and then use * add_path_precheck() to see if the path is clearly going to be dominated * by some existing path for the joinrel. If not, do the full pushup with * creating a fully valid path structure and submitting it to add_path(). * The latter two steps are expensive enough to make this two-phase * methodology worthwhile. */ initial_cost_nestloop(root, &workspace, jointype, outer_path, inner_path, extra); if (add_path_precheck(joinrel, workspace.disabled_nodes, workspace.startup_cost, workspace.total_cost, pathkeys, required_outer)) { add_path(joinrel, (Path *) create_nestloop_path(root, joinrel, jointype, &workspace, extra, outer_path, inner_path, extra->restrictlist, pathkeys, required_outer)); } else { /* Waste no memory when we reject a path here */ bms_free(required_outer); } } /* * try_partial_nestloop_path * Consider a partial nestloop join path; if it appears useful, push it into * the joinrel's partial_pathlist via add_partial_path(). */ static void try_partial_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra) { JoinCostWorkspace workspace; /* * If the inner path is parameterized, the parameterization must be fully * satisfied by the proposed outer path. Parameterized partial paths are * not supported. The caller should already have verified that no lateral * rels are required here. */ Assert(bms_is_empty(joinrel->lateral_relids)); Assert(bms_is_empty(PATH_REQ_OUTER(outer_path))); if (inner_path->param_info != NULL) { Relids inner_paramrels = inner_path->param_info->ppi_req_outer; RelOptInfo *outerrel = outer_path->parent; Relids outerrelids; /* * The inner and outer paths are parameterized, if at all, by the top * level parents, not the child relations, so we must use those relids * for our parameterization tests. */ if (outerrel->top_parent_relids) outerrelids = outerrel->top_parent_relids; else outerrelids = outerrel->relids; if (!bms_is_subset(inner_paramrels, outerrelids)) return; } /* * If the inner path is parameterized, it is parameterized by the topmost * parent of the outer rel, not the outer rel itself. We will need to * translate the parameterization, if this path is chosen, during * create_plan(). Here we just check whether we will be able to perform * the translation, and if not avoid creating a nestloop path. */ if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent) && !path_is_reparameterizable_by_child(inner_path, outer_path->parent)) return; /* * Before creating a path, get a quick lower bound on what it is likely to * cost. Bail out right away if it looks terrible. */ initial_cost_nestloop(root, &workspace, jointype, outer_path, inner_path, extra); if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes, workspace.total_cost, pathkeys)) return; /* Might be good enough to be worth trying, so let's try it. */ add_partial_path(joinrel, (Path *) create_nestloop_path(root, joinrel, jointype, &workspace, extra, outer_path, inner_path, extra->restrictlist, pathkeys, NULL)); } /* * try_mergejoin_path * Consider a merge join path; if it appears useful, push it into * the joinrel's pathlist via add_path(). */ static void try_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys, JoinType jointype, JoinPathExtraData *extra, bool is_partial) { Relids required_outer; int outer_presorted_keys = 0; JoinCostWorkspace workspace; if (is_partial) { try_partial_mergejoin_path(root, joinrel, outer_path, inner_path, pathkeys, mergeclauses, outersortkeys, innersortkeys, jointype, extra); return; } /* * If we are forming an outer join at this join, it's nonsensical to use * an input path that uses the outer join as part of its parameterization. * (This can happen despite our join order restrictions, since those apply * to what is in an input relation not what its parameters are.) */ if (extra->sjinfo->ojrelid != 0 && (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) || bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path)))) return; /* * Check to see if proposed path is still parameterized, and reject if the * parameterization wouldn't be sensible. */ required_outer = calc_non_nestloop_required_outer(outer_path, inner_path); if (required_outer && !bms_overlap(required_outer, extra->param_source_rels)) { /* Waste no memory when we reject a path here */ bms_free(required_outer); return; } /* * If the given paths are already well enough ordered, we can skip doing * an explicit sort. * * We need to determine the number of presorted keys of the outer path to * decide whether explicit incremental sort can be applied when * outersortkeys is not NIL. We do not need to do the same for the inner * path though, as incremental sort currently does not support * mark/restore. */ if (outersortkeys && pathkeys_count_contained_in(outersortkeys, outer_path->pathkeys, &outer_presorted_keys)) outersortkeys = NIL; if (innersortkeys && pathkeys_contained_in(innersortkeys, inner_path->pathkeys)) innersortkeys = NIL; /* * See comments in try_nestloop_path(). */ initial_cost_mergejoin(root, &workspace, jointype, mergeclauses, outer_path, inner_path, outersortkeys, innersortkeys, outer_presorted_keys, extra); if (add_path_precheck(joinrel, workspace.disabled_nodes, workspace.startup_cost, workspace.total_cost, pathkeys, required_outer)) { add_path(joinrel, (Path *) create_mergejoin_path(root, joinrel, jointype, &workspace, extra, outer_path, inner_path, extra->restrictlist, pathkeys, required_outer, mergeclauses, outersortkeys, innersortkeys, outer_presorted_keys)); } else { /* Waste no memory when we reject a path here */ bms_free(required_outer); } } /* * try_partial_mergejoin_path * Consider a partial merge join path; if it appears useful, push it into * the joinrel's pathlist via add_partial_path(). */ static void try_partial_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys, JoinType jointype, JoinPathExtraData *extra) { int outer_presorted_keys = 0; JoinCostWorkspace workspace; /* * See comments in try_partial_hashjoin_path(). */ Assert(bms_is_empty(joinrel->lateral_relids)); Assert(bms_is_empty(PATH_REQ_OUTER(outer_path))); if (!bms_is_empty(PATH_REQ_OUTER(inner_path))) return; /* * If the given paths are already well enough ordered, we can skip doing * an explicit sort. * * We need to determine the number of presorted keys of the outer path to * decide whether explicit incremental sort can be applied when * outersortkeys is not NIL. We do not need to do the same for the inner * path though, as incremental sort currently does not support * mark/restore. */ if (outersortkeys && pathkeys_count_contained_in(outersortkeys, outer_path->pathkeys, &outer_presorted_keys)) outersortkeys = NIL; if (innersortkeys && pathkeys_contained_in(innersortkeys, inner_path->pathkeys)) innersortkeys = NIL; /* * See comments in try_partial_nestloop_path(). */ initial_cost_mergejoin(root, &workspace, jointype, mergeclauses, outer_path, inner_path, outersortkeys, innersortkeys, outer_presorted_keys, extra); if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes, workspace.total_cost, pathkeys)) return; /* Might be good enough to be worth trying, so let's try it. */ add_partial_path(joinrel, (Path *) create_mergejoin_path(root, joinrel, jointype, &workspace, extra, outer_path, inner_path, extra->restrictlist, pathkeys, NULL, mergeclauses, outersortkeys, innersortkeys, outer_presorted_keys)); } /* * try_hashjoin_path * Consider a hash join path; if it appears useful, push it into * the joinrel's pathlist via add_path(). */ static void try_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra) { Relids required_outer; JoinCostWorkspace workspace; /* * If we are forming an outer join at this join, it's nonsensical to use * an input path that uses the outer join as part of its parameterization. * (This can happen despite our join order restrictions, since those apply * to what is in an input relation not what its parameters are.) */ if (extra->sjinfo->ojrelid != 0 && (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) || bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path)))) return; /* * Check to see if proposed path is still parameterized, and reject if the * parameterization wouldn't be sensible. */ required_outer = calc_non_nestloop_required_outer(outer_path, inner_path); if (required_outer && !bms_overlap(required_outer, extra->param_source_rels)) { /* Waste no memory when we reject a path here */ bms_free(required_outer); return; } /* * See comments in try_nestloop_path(). Also note that hashjoin paths * never have any output pathkeys, per comments in create_hashjoin_path. */ initial_cost_hashjoin(root, &workspace, jointype, hashclauses, outer_path, inner_path, extra, false); if (add_path_precheck(joinrel, workspace.disabled_nodes, workspace.startup_cost, workspace.total_cost, NIL, required_outer)) { add_path(joinrel, (Path *) create_hashjoin_path(root, joinrel, jointype, &workspace, extra, outer_path, inner_path, false, /* parallel_hash */ extra->restrictlist, required_outer, hashclauses)); } else { /* Waste no memory when we reject a path here */ bms_free(required_outer); } } /* * try_partial_hashjoin_path * Consider a partial hashjoin join path; if it appears useful, push it into * the joinrel's partial_pathlist via add_partial_path(). * The outer side is partial. If parallel_hash is true, then the inner path * must be partial and will be run in parallel to create one or more shared * hash tables; otherwise the inner path must be complete and a copy of it * is run in every process to create separate identical private hash tables. */ static void try_partial_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra, bool parallel_hash) { JoinCostWorkspace workspace; /* * If the inner path is parameterized, we can't use a partial hashjoin. * Parameterized partial paths are not supported. The caller should * already have verified that no lateral rels are required here. */ Assert(bms_is_empty(joinrel->lateral_relids)); Assert(bms_is_empty(PATH_REQ_OUTER(outer_path))); if (!bms_is_empty(PATH_REQ_OUTER(inner_path))) return; /* * Before creating a path, get a quick lower bound on what it is likely to * cost. Bail out right away if it looks terrible. */ initial_cost_hashjoin(root, &workspace, jointype, hashclauses, outer_path, inner_path, extra, parallel_hash); if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes, workspace.total_cost, NIL)) return; /* Might be good enough to be worth trying, so let's try it. */ add_partial_path(joinrel, (Path *) create_hashjoin_path(root, joinrel, jointype, &workspace, extra, outer_path, inner_path, parallel_hash, extra->restrictlist, NULL, hashclauses)); } /* * sort_inner_and_outer * Create mergejoin join paths by explicitly sorting both the outer and * inner join relations on each available merge ordering. * * 'joinrel' is the join relation * 'outerrel' is the outer join relation * 'innerrel' is the inner join relation * 'jointype' is the type of join to do * 'extra' contains additional input values */ static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra) { JoinType save_jointype = jointype; Path *outer_path; Path *inner_path; Path *cheapest_partial_outer = NULL; Path *cheapest_safe_inner = NULL; List *all_pathkeys; ListCell *l; /* Nothing to do if there are no available mergejoin clauses */ if (extra->mergeclause_list == NIL) return; /* * We only consider the cheapest-total-cost input paths, since we are * assuming here that a sort is required. We will consider * cheapest-startup-cost input paths later, and only if they don't need a * sort. * * This function intentionally does not consider parameterized input * paths, except when the cheapest-total is parameterized. If we did so, * we'd have a combinatorial explosion of mergejoin paths of dubious * value. This interacts with decisions elsewhere that also discriminate * against mergejoins with parameterized inputs; see comments in * src/backend/optimizer/README. */ outer_path = outerrel->cheapest_total_path; inner_path = innerrel->cheapest_total_path; /* * If either cheapest-total path is parameterized by the other rel, we * can't use a mergejoin. (There's no use looking for alternative input * paths, since these should already be the least-parameterized available * paths.) */ if (PATH_PARAM_BY_REL(outer_path, innerrel) || PATH_PARAM_BY_REL(inner_path, outerrel)) return; /* * If unique-ification is requested, do it and then handle as a plain * inner join. */ if (jointype == JOIN_UNIQUE_OUTER) { outer_path = (Path *) create_unique_path(root, outerrel, outer_path, extra->sjinfo); Assert(outer_path); jointype = JOIN_INNER; } else if (jointype == JOIN_UNIQUE_INNER) { inner_path = (Path *) create_unique_path(root, innerrel, inner_path, extra->sjinfo); Assert(inner_path); jointype = JOIN_INNER; } /* * If the joinrel is parallel-safe, we may be able to consider a partial * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the * outer path will be partial, and therefore we won't be able to properly * guarantee uniqueness. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT * and JOIN_RIGHT_ANTI, because they can produce false null extended rows. * Also, the resulting path must not be parameterized. */ if (joinrel->consider_parallel && save_jointype != JOIN_UNIQUE_OUTER && save_jointype != JOIN_FULL && save_jointype != JOIN_RIGHT && save_jointype != JOIN_RIGHT_ANTI && outerrel->partial_pathlist != NIL && bms_is_empty(joinrel->lateral_relids)) { cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist); if (inner_path->parallel_safe) cheapest_safe_inner = inner_path; else if (save_jointype != JOIN_UNIQUE_INNER) cheapest_safe_inner = get_cheapest_parallel_safe_total_inner(innerrel->pathlist); } /* * Each possible ordering of the available mergejoin clauses will generate * a differently-sorted result path at essentially the same cost. We have * no basis for choosing one over another at this level of joining, but * some sort orders may be more useful than others for higher-level * mergejoins, so it's worth considering multiple orderings. * * Actually, it's not quite true that every mergeclause ordering will * generate a different path order, because some of the clauses may be * partially redundant (refer to the same EquivalenceClasses). Therefore, * what we do is convert the mergeclause list to a list of canonical * pathkeys, and then consider different orderings of the pathkeys. * * Generating a path for *every* permutation of the pathkeys doesn't seem * like a winning strategy; the cost in planning time is too high. For * now, we generate one path for each pathkey, listing that pathkey first * and the rest in random order. This should allow at least a one-clause * mergejoin without re-sorting against any other possible mergejoin * partner path. But if we've not guessed the right ordering of secondary * keys, we may end up evaluating clauses as qpquals when they could have * been done as mergeclauses. (In practice, it's rare that there's more * than two or three mergeclauses, so expending a huge amount of thought * on that is probably not worth it.) * * The pathkey order returned by select_outer_pathkeys_for_merge() has * some heuristics behind it (see that function), so be sure to try it * exactly as-is as well as making variants. */ all_pathkeys = select_outer_pathkeys_for_merge(root, extra->mergeclause_list, joinrel); foreach(l, all_pathkeys) { PathKey *front_pathkey = (PathKey *) lfirst(l); List *cur_mergeclauses; List *outerkeys; List *innerkeys; List *merge_pathkeys; /* Make a pathkey list with this guy first */ if (l != list_head(all_pathkeys)) outerkeys = lcons(front_pathkey, list_delete_nth_cell(list_copy(all_pathkeys), foreach_current_index(l))); else outerkeys = all_pathkeys; /* no work at first one... */ /* Sort the mergeclauses into the corresponding ordering */ cur_mergeclauses = find_mergeclauses_for_outer_pathkeys(root, outerkeys, extra->mergeclause_list); /* Should have used them all... */ Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list)); /* Build sort pathkeys for the inner side */ innerkeys = make_inner_pathkeys_for_merge(root, cur_mergeclauses, outerkeys); /* Build pathkeys representing output sort order */ merge_pathkeys = build_join_pathkeys(root, joinrel, jointype, outerkeys); /* * And now we can make the path. * * Note: it's possible that the cheapest paths will already be sorted * properly. try_mergejoin_path will detect that case and suppress an * explicit sort step, so we needn't do so here. */ try_mergejoin_path(root, joinrel, outer_path, inner_path, merge_pathkeys, cur_mergeclauses, outerkeys, innerkeys, jointype, extra, false); /* * If we have partial outer and parallel safe inner path then try * partial mergejoin path. */ if (cheapest_partial_outer && cheapest_safe_inner) try_partial_mergejoin_path(root, joinrel, cheapest_partial_outer, cheapest_safe_inner, merge_pathkeys, cur_mergeclauses, outerkeys, innerkeys, jointype, extra); } } /* * generate_mergejoin_paths * Creates possible mergejoin paths for input outerpath. * * We generate mergejoins if mergejoin clauses are available. We have * two ways to generate the inner path for a mergejoin: sort the cheapest * inner path, or use an inner path that is already suitably ordered for the * merge. If we have several mergeclauses, it could be that there is no inner * path (or only a very expensive one) for the full list of mergeclauses, but * better paths exist if we truncate the mergeclause list (thereby discarding * some sort key requirements). So, we consider truncations of the * mergeclause list as well as the full list. (Ideally we'd consider all * subsets of the mergeclause list, but that seems way too expensive.) */ static void generate_mergejoin_paths(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *innerrel, Path *outerpath, JoinType jointype, JoinPathExtraData *extra, bool useallclauses, Path *inner_cheapest_total, List *merge_pathkeys, bool is_partial) { List *mergeclauses; List *innersortkeys; List *trialsortkeys; Path *cheapest_startup_inner; Path *cheapest_total_inner; JoinType save_jointype = jointype; int num_sortkeys; int sortkeycnt; if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER) jointype = JOIN_INNER; /* Look for useful mergeclauses (if any) */ mergeclauses = find_mergeclauses_for_outer_pathkeys(root, outerpath->pathkeys, extra->mergeclause_list); /* * Done with this outer path if no chance for a mergejoin. * * Special corner case: for "x FULL JOIN y ON true", there will be no join * clauses at all. Ordinarily we'd generate a clauseless nestloop path, * but since mergejoin is our only join type that supports FULL JOIN * without any join clauses, it's necessary to generate a clauseless * mergejoin path instead. */ if (mergeclauses == NIL) { if (jointype == JOIN_FULL) /* okay to try for mergejoin */ ; else return; } if (useallclauses && list_length(mergeclauses) != list_length(extra->mergeclause_list)) return; /* Compute the required ordering of the inner path */ innersortkeys = make_inner_pathkeys_for_merge(root, mergeclauses, outerpath->pathkeys); /* * Generate a mergejoin on the basis of sorting the cheapest inner. Since * a sort will be needed, only cheapest total cost matters. (But * try_mergejoin_path will do the right thing if inner_cheapest_total is * already correctly sorted.) */ try_mergejoin_path(root, joinrel, outerpath, inner_cheapest_total, merge_pathkeys, mergeclauses, NIL, innersortkeys, jointype, extra, is_partial); /* Can't do anything else if inner path needs to be unique'd */ if (save_jointype == JOIN_UNIQUE_INNER) return; /* * Look for presorted inner paths that satisfy the innersortkey list --- * or any truncation thereof, if we are allowed to build a mergejoin using * a subset of the merge clauses. Here, we consider both cheap startup * cost and cheap total cost. * * Currently we do not consider parameterized inner paths here. This * interacts with decisions elsewhere that also discriminate against * mergejoins with parameterized inputs; see comments in * src/backend/optimizer/README. * * As we shorten the sortkey list, we should consider only paths that are * strictly cheaper than (in particular, not the same as) any path found * in an earlier iteration. Otherwise we'd be intentionally using fewer * merge keys than a given path allows (treating the rest as plain * joinquals), which is unlikely to be a good idea. Also, eliminating * paths here on the basis of compare_path_costs is a lot cheaper than * building the mergejoin path only to throw it away. * * If inner_cheapest_total is well enough sorted to have not required a * sort in the path made above, we shouldn't make a duplicate path with * it, either. We handle that case with the same logic that handles the * previous consideration, by initializing the variables that track * cheapest-so-far properly. Note that we do NOT reject * inner_cheapest_total if we find it matches some shorter set of * pathkeys. That case corresponds to using fewer mergekeys to avoid * sorting inner_cheapest_total, whereas we did sort it above, so the * plans being considered are different. */ if (pathkeys_contained_in(innersortkeys, inner_cheapest_total->pathkeys)) { /* inner_cheapest_total didn't require a sort */ cheapest_startup_inner = inner_cheapest_total; cheapest_total_inner = inner_cheapest_total; } else { /* it did require a sort, at least for the full set of keys */ cheapest_startup_inner = NULL; cheapest_total_inner = NULL; } num_sortkeys = list_length(innersortkeys); if (num_sortkeys > 1 && !useallclauses) trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */ else trialsortkeys = innersortkeys; /* won't really truncate */ for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--) { Path *innerpath; List *newclauses = NIL; /* * Look for an inner path ordered well enough for the first * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified * destructively, which is why we made a copy... */ trialsortkeys = list_truncate(trialsortkeys, sortkeycnt); innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist, trialsortkeys, NULL, TOTAL_COST, is_partial); if (innerpath != NULL && (cheapest_total_inner == NULL || compare_path_costs(innerpath, cheapest_total_inner, TOTAL_COST) < 0)) { /* Found a cheap (or even-cheaper) sorted path */ /* Select the right mergeclauses, if we didn't already */ if (sortkeycnt < num_sortkeys) { newclauses = trim_mergeclauses_for_inner_pathkeys(root, mergeclauses, trialsortkeys); Assert(newclauses != NIL); } else newclauses = mergeclauses; try_mergejoin_path(root, joinrel, outerpath, innerpath, merge_pathkeys, newclauses, NIL, NIL, jointype, extra, is_partial); cheapest_total_inner = innerpath; } /* Same on the basis of cheapest startup cost ... */ innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist, trialsortkeys, NULL, STARTUP_COST, is_partial); if (innerpath != NULL && (cheapest_startup_inner == NULL || compare_path_costs(innerpath, cheapest_startup_inner, STARTUP_COST) < 0)) { /* Found a cheap (or even-cheaper) sorted path */ if (innerpath != cheapest_total_inner) { /* * Avoid rebuilding clause list if we already made one; saves * memory in big join trees... */ if (newclauses == NIL) { if (sortkeycnt < num_sortkeys) { newclauses = trim_mergeclauses_for_inner_pathkeys(root, mergeclauses, trialsortkeys); Assert(newclauses != NIL); } else newclauses = mergeclauses; } try_mergejoin_path(root, joinrel, outerpath, innerpath, merge_pathkeys, newclauses, NIL, NIL, jointype, extra, is_partial); } cheapest_startup_inner = innerpath; } /* * Don't consider truncated sortkeys if we need all clauses. */ if (useallclauses) break; } } /* * match_unsorted_outer * Creates possible join paths for processing a single join relation * 'joinrel' by employing either iterative substitution or * mergejoining on each of its possible outer paths (considering * only outer paths that are already ordered well enough for merging). * * We always generate a nestloop path for each available outer path. * In fact we may generate as many as five: one on the cheapest-total-cost * inner path, one on the same with materialization, one on the * cheapest-startup-cost inner path (if different), one on the * cheapest-total inner-indexscan path (if any), and one on the * cheapest-startup inner-indexscan path (if different). * * We also consider mergejoins if mergejoin clauses are available. See * detailed comments in generate_mergejoin_paths. * * 'joinrel' is the join relation * 'outerrel' is the outer join relation * 'innerrel' is the inner join relation * 'jointype' is the type of join to do * 'extra' contains additional input values */ static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra) { JoinType save_jointype = jointype; bool nestjoinOK; bool useallclauses; Path *inner_cheapest_total = innerrel->cheapest_total_path; Path *matpath = NULL; ListCell *lc1; /* * For now we do not support RIGHT_SEMI join in mergejoin or nestloop * join. */ if (jointype == JOIN_RIGHT_SEMI) return; /* * Nestloop only supports inner, left, semi, and anti joins. Also, if we * are doing a right, right-anti or full mergejoin, we must use *all* the * mergeclauses as join clauses, else we will not have a valid plan. * (Although these two flags are currently inverses, keep them separate * for clarity and possible future changes.) */ switch (jointype) { case JOIN_INNER: case JOIN_LEFT: case JOIN_SEMI: case JOIN_ANTI: nestjoinOK = true; useallclauses = false; break; case JOIN_RIGHT: case JOIN_RIGHT_ANTI: case JOIN_FULL: nestjoinOK = false; useallclauses = true; break; case JOIN_UNIQUE_OUTER: case JOIN_UNIQUE_INNER: jointype = JOIN_INNER; nestjoinOK = true; useallclauses = false; break; default: elog(ERROR, "unrecognized join type: %d", (int) jointype); nestjoinOK = false; /* keep compiler quiet */ useallclauses = false; break; } /* * If inner_cheapest_total is parameterized by the outer rel, ignore it; * we will consider it below as a member of cheapest_parameterized_paths, * but the other possibilities considered in this routine aren't usable. */ if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel)) inner_cheapest_total = NULL; /* * If we need to unique-ify the inner path, we will consider only the * cheapest-total inner. */ if (save_jointype == JOIN_UNIQUE_INNER) { /* No way to do this with an inner path parameterized by outer rel */ if (inner_cheapest_total == NULL) return; inner_cheapest_total = (Path *) create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo); Assert(inner_cheapest_total); } else if (nestjoinOK) { /* * Consider materializing the cheapest inner path, unless * enable_material is off or the path in question materializes its * output anyway. */ if (enable_material && inner_cheapest_total != NULL && !ExecMaterializesOutput(inner_cheapest_total->pathtype)) matpath = (Path *) create_material_path(innerrel, inner_cheapest_total); } foreach(lc1, outerrel->pathlist) { Path *outerpath = (Path *) lfirst(lc1); List *merge_pathkeys; /* * We cannot use an outer path that is parameterized by the inner rel. */ if (PATH_PARAM_BY_REL(outerpath, innerrel)) continue; /* * If we need to unique-ify the outer path, it's pointless to consider * any but the cheapest outer. (XXX we don't consider parameterized * outers, nor inners, for unique-ified cases. Should we?) */ if (save_jointype == JOIN_UNIQUE_OUTER) { if (outerpath != outerrel->cheapest_total_path) continue; outerpath = (Path *) create_unique_path(root, outerrel, outerpath, extra->sjinfo); Assert(outerpath); } /* * The result will have this sort order (even if it is implemented as * a nestloop, and even if some of the mergeclauses are implemented by * qpquals rather than as true mergeclauses): */ merge_pathkeys = build_join_pathkeys(root, joinrel, jointype, outerpath->pathkeys); if (save_jointype == JOIN_UNIQUE_INNER) { /* * Consider nestloop join, but only with the unique-ified cheapest * inner path */ try_nestloop_path(root, joinrel, outerpath, inner_cheapest_total, merge_pathkeys, jointype, extra); } else if (nestjoinOK) { /* * Consider nestloop joins using this outer path and various * available paths for the inner relation. We consider the * cheapest-total paths for each available parameterization of the * inner relation, including the unparameterized case. */ ListCell *lc2; foreach(lc2, innerrel->cheapest_parameterized_paths) { Path *innerpath = (Path *) lfirst(lc2); Path *mpath; try_nestloop_path(root, joinrel, outerpath, innerpath, merge_pathkeys, jointype, extra); /* * Try generating a memoize path and see if that makes the * nested loop any cheaper. */ mpath = get_memoize_path(root, innerrel, outerrel, innerpath, outerpath, jointype, extra); if (mpath != NULL) try_nestloop_path(root, joinrel, outerpath, mpath, merge_pathkeys, jointype, extra); } /* Also consider materialized form of the cheapest inner path */ if (matpath != NULL) try_nestloop_path(root, joinrel, outerpath, matpath, merge_pathkeys, jointype, extra); } /* Can't do anything else if outer path needs to be unique'd */ if (save_jointype == JOIN_UNIQUE_OUTER) continue; /* Can't do anything else if inner rel is parameterized by outer */ if (inner_cheapest_total == NULL) continue; /* Generate merge join paths */ generate_mergejoin_paths(root, joinrel, innerrel, outerpath, save_jointype, extra, useallclauses, inner_cheapest_total, merge_pathkeys, false); } /* * Consider partial nestloop and mergejoin plan if outerrel has any * partial path and the joinrel is parallel-safe. However, we can't * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and * therefore we won't be able to properly guarantee uniqueness. Nor can * we handle joins needing lateral rels, since partial paths must not be * parameterized. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT and * JOIN_RIGHT_ANTI, because they can produce false null extended rows. */ if (joinrel->consider_parallel && save_jointype != JOIN_UNIQUE_OUTER && save_jointype != JOIN_FULL && save_jointype != JOIN_RIGHT && save_jointype != JOIN_RIGHT_ANTI && outerrel->partial_pathlist != NIL && bms_is_empty(joinrel->lateral_relids)) { if (nestjoinOK) consider_parallel_nestloop(root, joinrel, outerrel, innerrel, save_jointype, extra); /* * If inner_cheapest_total is NULL or non parallel-safe then find the * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we * can't use any alternative inner path. */ if (inner_cheapest_total == NULL || !inner_cheapest_total->parallel_safe) { if (save_jointype == JOIN_UNIQUE_INNER) return; inner_cheapest_total = get_cheapest_parallel_safe_total_inner(innerrel->pathlist); } if (inner_cheapest_total) consider_parallel_mergejoin(root, joinrel, outerrel, innerrel, save_jointype, extra, inner_cheapest_total); } } /* * consider_parallel_mergejoin * Try to build partial paths for a joinrel by joining a partial path * for the outer relation to a complete path for the inner relation. * * 'joinrel' is the join relation * 'outerrel' is the outer join relation * 'innerrel' is the inner join relation * 'jointype' is the type of join to do * 'extra' contains additional input values * 'inner_cheapest_total' cheapest total path for innerrel */ static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total) { ListCell *lc1; /* generate merge join path for each partial outer path */ foreach(lc1, outerrel->partial_pathlist) { Path *outerpath = (Path *) lfirst(lc1); List *merge_pathkeys; /* * Figure out what useful ordering any paths we create will have. */ merge_pathkeys = build_join_pathkeys(root, joinrel, jointype, outerpath->pathkeys); generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype, extra, false, inner_cheapest_total, merge_pathkeys, true); } } /* * consider_parallel_nestloop * Try to build partial paths for a joinrel by joining a partial path for the * outer relation to a complete path for the inner relation. * * 'joinrel' is the join relation * 'outerrel' is the outer join relation * 'innerrel' is the inner join relation * 'jointype' is the type of join to do * 'extra' contains additional input values */ static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra) { JoinType save_jointype = jointype; Path *inner_cheapest_total = innerrel->cheapest_total_path; Path *matpath = NULL; ListCell *lc1; if (jointype == JOIN_UNIQUE_INNER) jointype = JOIN_INNER; /* * Consider materializing the cheapest inner path, unless: 1) we're doing * JOIN_UNIQUE_INNER, because in this case we have to unique-ify the * cheapest inner path, 2) enable_material is off, 3) the cheapest inner * path is not parallel-safe, 4) the cheapest inner path is parameterized * by the outer rel, or 5) the cheapest inner path materializes its output * anyway. */ if (save_jointype != JOIN_UNIQUE_INNER && enable_material && inner_cheapest_total->parallel_safe && !PATH_PARAM_BY_REL(inner_cheapest_total, outerrel) && !ExecMaterializesOutput(inner_cheapest_total->pathtype)) { matpath = (Path *) create_material_path(innerrel, inner_cheapest_total); Assert(matpath->parallel_safe); } foreach(lc1, outerrel->partial_pathlist) { Path *outerpath = (Path *) lfirst(lc1); List *pathkeys; ListCell *lc2; /* Figure out what useful ordering any paths we create will have. */ pathkeys = build_join_pathkeys(root, joinrel, jointype, outerpath->pathkeys); /* * Try the cheapest parameterized paths; only those which will produce * an unparameterized path when joined to this outerrel will survive * try_partial_nestloop_path. The cheapest unparameterized path is * also in this list. */ foreach(lc2, innerrel->cheapest_parameterized_paths) { Path *innerpath = (Path *) lfirst(lc2); Path *mpath; /* Can't join to an inner path that is not parallel-safe */ if (!innerpath->parallel_safe) continue; /* * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's * cheapest_total_path, and we have to unique-ify it. (We might * be able to relax this to allow other safe, unparameterized * inner paths, but right now create_unique_path is not on board * with that.) */ if (save_jointype == JOIN_UNIQUE_INNER) { if (innerpath != innerrel->cheapest_total_path) continue; innerpath = (Path *) create_unique_path(root, innerrel, innerpath, extra->sjinfo); Assert(innerpath); } try_partial_nestloop_path(root, joinrel, outerpath, innerpath, pathkeys, jointype, extra); /* * Try generating a memoize path and see if that makes the nested * loop any cheaper. */ mpath = get_memoize_path(root, innerrel, outerrel, innerpath, outerpath, jointype, extra); if (mpath != NULL) try_partial_nestloop_path(root, joinrel, outerpath, mpath, pathkeys, jointype, extra); } /* Also consider materialized form of the cheapest inner path */ if (matpath != NULL) try_partial_nestloop_path(root, joinrel, outerpath, matpath, pathkeys, jointype, extra); } } /* * hash_inner_and_outer * Create hashjoin join paths by explicitly hashing both the outer and * inner keys of each available hash clause. * * 'joinrel' is the join relation * 'outerrel' is the outer join relation * 'innerrel' is the inner join relation * 'jointype' is the type of join to do * 'extra' contains additional input values */ static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra) { JoinType save_jointype = jointype; bool isouterjoin = IS_OUTER_JOIN(jointype); List *hashclauses; ListCell *l; /* * We need to build only one hashclauses list for any given pair of outer * and inner relations; all of the hashable clauses will be used as keys. * * Scan the join's restrictinfo list to find hashjoinable clauses that are * usable with this pair of sub-relations. */ hashclauses = NIL; foreach(l, extra->restrictlist) { RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l); /* * If processing an outer join, only use its own join clauses for * hashing. For inner joins we need not be so picky. */ if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids)) continue; if (!restrictinfo->can_join || restrictinfo->hashjoinoperator == InvalidOid) continue; /* not hashjoinable */ /* * Check if clause has the form "outer op inner" or "inner op outer". */ if (!clause_sides_match_join(restrictinfo, outerrel->relids, innerrel->relids)) continue; /* no good for these input relations */ /* * If clause has the form "inner op outer", check if its operator has * valid commutator. This is necessary because hashclauses in this * form will get commuted in createplan.c to put the outer var on the * left (see get_switched_clauses). This probably shouldn't ever * fail, since hashable operators ought to have commutators, but be * paranoid. * * The clause being hashjoinable indicates that it's an OpExpr. */ if (!restrictinfo->outer_is_left && !OidIsValid(get_commutator(castNode(OpExpr, restrictinfo->clause)->opno))) continue; hashclauses = lappend(hashclauses, restrictinfo); } /* If we found any usable hashclauses, make paths */ if (hashclauses) { /* * We consider both the cheapest-total-cost and cheapest-startup-cost * outer paths. There's no need to consider any but the * cheapest-total-cost inner path, however. */ Path *cheapest_startup_outer = outerrel->cheapest_startup_path; Path *cheapest_total_outer = outerrel->cheapest_total_path; Path *cheapest_total_inner = innerrel->cheapest_total_path; /* * If either cheapest-total path is parameterized by the other rel, we * can't use a hashjoin. (There's no use looking for alternative * input paths, since these should already be the least-parameterized * available paths.) */ if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) || PATH_PARAM_BY_REL(cheapest_total_inner, outerrel)) return; /* Unique-ify if need be; we ignore parameterized possibilities */ if (jointype == JOIN_UNIQUE_OUTER) { cheapest_total_outer = (Path *) create_unique_path(root, outerrel, cheapest_total_outer, extra->sjinfo); Assert(cheapest_total_outer); jointype = JOIN_INNER; try_hashjoin_path(root, joinrel, cheapest_total_outer, cheapest_total_inner, hashclauses, jointype, extra); /* no possibility of cheap startup here */ } else if (jointype == JOIN_UNIQUE_INNER) { cheapest_total_inner = (Path *) create_unique_path(root, innerrel, cheapest_total_inner, extra->sjinfo); Assert(cheapest_total_inner); jointype = JOIN_INNER; try_hashjoin_path(root, joinrel, cheapest_total_outer, cheapest_total_inner, hashclauses, jointype, extra); if (cheapest_startup_outer != NULL && cheapest_startup_outer != cheapest_total_outer) try_hashjoin_path(root, joinrel, cheapest_startup_outer, cheapest_total_inner, hashclauses, jointype, extra); } else { /* * For other jointypes, we consider the cheapest startup outer * together with the cheapest total inner, and then consider * pairings of cheapest-total paths including parameterized ones. * There is no use in generating parameterized paths on the basis * of possibly cheap startup cost, so this is sufficient. */ ListCell *lc1; ListCell *lc2; if (cheapest_startup_outer != NULL) try_hashjoin_path(root, joinrel, cheapest_startup_outer, cheapest_total_inner, hashclauses, jointype, extra); foreach(lc1, outerrel->cheapest_parameterized_paths) { Path *outerpath = (Path *) lfirst(lc1); /* * We cannot use an outer path that is parameterized by the * inner rel. */ if (PATH_PARAM_BY_REL(outerpath, innerrel)) continue; foreach(lc2, innerrel->cheapest_parameterized_paths) { Path *innerpath = (Path *) lfirst(lc2); /* * We cannot use an inner path that is parameterized by * the outer rel, either. */ if (PATH_PARAM_BY_REL(innerpath, outerrel)) continue; if (outerpath == cheapest_startup_outer && innerpath == cheapest_total_inner) continue; /* already tried it */ try_hashjoin_path(root, joinrel, outerpath, innerpath, hashclauses, jointype, extra); } } } /* * If the joinrel is parallel-safe, we may be able to consider a * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER, * because the outer path will be partial, and therefore we won't be * able to properly guarantee uniqueness. Also, the resulting path * must not be parameterized. */ if (joinrel->consider_parallel && save_jointype != JOIN_UNIQUE_OUTER && outerrel->partial_pathlist != NIL && bms_is_empty(joinrel->lateral_relids)) { Path *cheapest_partial_outer; Path *cheapest_partial_inner = NULL; Path *cheapest_safe_inner = NULL; cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist); /* * Can we use a partial inner plan too, so that we can build a * shared hash table in parallel? We can't handle * JOIN_UNIQUE_INNER because we can't guarantee uniqueness. */ if (innerrel->partial_pathlist != NIL && save_jointype != JOIN_UNIQUE_INNER && enable_parallel_hash) { cheapest_partial_inner = (Path *) linitial(innerrel->partial_pathlist); try_partial_hashjoin_path(root, joinrel, cheapest_partial_outer, cheapest_partial_inner, hashclauses, jointype, extra, true /* parallel_hash */ ); } /* * Normally, given that the joinrel is parallel-safe, the cheapest * total inner path will also be parallel-safe, but if not, we'll * have to search for the cheapest safe, unparameterized inner * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative * inner path. If full, right, right-semi or right-anti join, we * can't use parallelism (building the hash table in each backend) * because no one process has all the match bits. */ if (save_jointype == JOIN_FULL || save_jointype == JOIN_RIGHT || save_jointype == JOIN_RIGHT_SEMI || save_jointype == JOIN_RIGHT_ANTI) cheapest_safe_inner = NULL; else if (cheapest_total_inner->parallel_safe) cheapest_safe_inner = cheapest_total_inner; else if (save_jointype != JOIN_UNIQUE_INNER) cheapest_safe_inner = get_cheapest_parallel_safe_total_inner(innerrel->pathlist); if (cheapest_safe_inner != NULL) try_partial_hashjoin_path(root, joinrel, cheapest_partial_outer, cheapest_safe_inner, hashclauses, jointype, extra, false /* parallel_hash */ ); } } } /* * select_mergejoin_clauses * Select mergejoin clauses that are usable for a particular join. * Returns a list of RestrictInfo nodes for those clauses. * * *mergejoin_allowed is normally set to true, but it is set to false if * this is a right-semi join, or this is a right/right-anti/full join and * there are nonmergejoinable join clauses. The executor's mergejoin * machinery cannot handle such cases, so we have to avoid generating a * mergejoin plan. (Note that this flag does NOT consider whether there are * actually any mergejoinable clauses. This is correct because in some * cases we need to build a clauseless mergejoin. Simply returning NIL is * therefore not enough to distinguish safe from unsafe cases.) * * We also mark each selected RestrictInfo to show which side is currently * being considered as outer. These are transient markings that are only * good for the duration of the current add_paths_to_joinrel() call! * * We examine each restrictinfo clause known for the join to see * if it is mergejoinable and involves vars from the two sub-relations * currently of interest. */ static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed) { List *result_list = NIL; bool isouterjoin = IS_OUTER_JOIN(jointype); bool have_nonmergeable_joinclause = false; ListCell *l; /* * For now we do not support RIGHT_SEMI join in mergejoin: the benefit of * swapping inputs tends to be small here. */ if (jointype == JOIN_RIGHT_SEMI) { *mergejoin_allowed = false; return NIL; } foreach(l, restrictlist) { RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l); /* * If processing an outer join, only use its own join clauses in the * merge. For inner joins we can use pushed-down clauses too. (Note: * we don't set have_nonmergeable_joinclause here because pushed-down * clauses will become otherquals not joinquals.) */ if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids)) continue; /* Check that clause is a mergeable operator clause */ if (!restrictinfo->can_join || restrictinfo->mergeopfamilies == NIL) { /* * The executor can handle extra joinquals that are constants, but * not anything else, when doing right/right-anti/full merge join. * (The reason to support constants is so we can do FULL JOIN ON * FALSE.) */ if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const)) have_nonmergeable_joinclause = true; continue; /* not mergejoinable */ } /* * Check if clause has the form "outer op inner" or "inner op outer". */ if (!clause_sides_match_join(restrictinfo, outerrel->relids, innerrel->relids)) { have_nonmergeable_joinclause = true; continue; /* no good for these input relations */ } /* * If clause has the form "inner op outer", check if its operator has * valid commutator. This is necessary because mergejoin clauses in * this form will get commuted in createplan.c to put the outer var on * the left (see get_switched_clauses). This probably shouldn't ever * fail, since mergejoinable operators ought to have commutators, but * be paranoid. * * The clause being mergejoinable indicates that it's an OpExpr. */ if (!restrictinfo->outer_is_left && !OidIsValid(get_commutator(castNode(OpExpr, restrictinfo->clause)->opno))) { have_nonmergeable_joinclause = true; continue; } /* * Insist that each side have a non-redundant eclass. This * restriction is needed because various bits of the planner expect * that each clause in a merge be associable with some pathkey in a * canonical pathkey list, but redundant eclasses can't appear in * canonical sort orderings. (XXX it might be worth relaxing this, * but not enough time to address it for 8.3.) */ update_mergeclause_eclasses(root, restrictinfo); if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) || EC_MUST_BE_REDUNDANT(restrictinfo->right_ec)) { have_nonmergeable_joinclause = true; continue; /* can't handle redundant eclasses */ } result_list = lappend(result_list, restrictinfo); } /* * Report whether mergejoin is allowed (see comment at top of function). */ switch (jointype) { case JOIN_RIGHT: case JOIN_RIGHT_ANTI: case JOIN_FULL: *mergejoin_allowed = !have_nonmergeable_joinclause; break; default: *mergejoin_allowed = true; break; } return result_list; }