/*------------------------------------------------------------------------- * * 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 <math.h>#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() */ /* * 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) \#define PATH_PARAM_BY_REL_SELF(path, rel) \#define PATH_PARAM_BY_REL(path, rel) \static void try_partial_mergejoin_path(PlannerInfo *root,static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel,static void consider_parallel_nestloop(PlannerInfo *root,static void consider_parallel_mergejoin(PlannerInfo *root,static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,static List *select_mergejoin_clauses(PlannerInfo *root,bool *mergejoin_allowed);static void generate_mergejoin_paths(PlannerInfo *root,bool useallclauses,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 bool mergejoin_allowed = true ;/* * 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)else /* * 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 . false ; /* well, unproven */ break ;case JOIN_UNIQUE_INNER:break ;case JOIN_UNIQUE_OUTER:false );break ;default :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)/* * 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)/* * 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 . /* * 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) &&/* full joins constrain both sides symmetrically */ if (sjinfo2->jointype == JOIN_FULL &&/* * 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 . /* * 1 . Consider mergejoin paths where both relations must be explicitly * sorted . Skip this if we can ' t mergejoin . if (mergejoin_allowed)/* * 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)#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)#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)/* * 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 &&/* * 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)/* * 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 /* * 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) &&/* * 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_CHECKINGstatic inline bool bool result = false ;if (bms_overlap(unsatisfied, root->outer_join_rels))if (!bms_is_member(sjinfo->ojrelid, unsatisfied))continue ; /* not relevant */ if (bms_overlap(satisfied, sjinfo->min_righthand) ||true ; /* doesn't work */ break ;/* Waste no memory when we reject a path here */ 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 bool *binary_mode)false ;/* Add join clauses from param_info to the hash key */ if (param_info != NULL)/* * Bail if the rinfo is not compatible . We need a join OpExpr * with 2 args . if (!IsA(opexpr, OpExpr) || list_length(opexpr->args) != 2 ||return false ;if (rinfo->outer_is_left)else /* can't do memoize if we can't hash the outer type */ if (!OidIsValid(hasheqoperator))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))/* * 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))true ;/* Now add any lateral vars to the cache key too */ /* Reject if there are any volatile functions in lateral vars */ if (contain_volatile_functions(expr))return false ;/* can't use memoize without a valid hash proc and equals operator */ if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr))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))/* * 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 . 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 */* 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;/* 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),continue ;/* Fetch Vars and PHVs of lateral references within PlaceHolderVars */ 0 );if (IsA(node, Var))0 );if (bms_is_member(var->varno, phinfo->ph_lateral))else if (IsA(node, PlaceHolderVar))0 );if (bms_is_subset(find_placeholder_info(root, phv)->ph_eval_at,else false );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 *bool binary_mode;/* 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 . /* * 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 ||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 ||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)if (inner_path->param_info == NULL)return NULL;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;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)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,return (Path *) create_memoize_path(root,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 /* * 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 &&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)else if (outerrel->top_parent_relids)else /* * 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 . if (required_outer &&/* Waste no memory when we reject a path here */ return ;/* If we got past that, we shouldn't have any unsafe outer-join refs */ /* * 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) &&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 . if (add_path_precheck(joinrel, workspace.disabled_nodes,else /* Waste no memory when we reject a path here */ /* * 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 /* * 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 . if (inner_path->param_info != NULL)/* * 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)else 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) &&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 . if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,return ;/* Might be good enough to be worth trying, so let's try it. */ /* * try_mergejoin_path * Consider a merge join path ; if it appears useful , push it into * the joinrel ' s pathlist via add_path ( ) . static void bool is_partial)int outer_presorted_keys = 0 ;if (is_partial)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 &&return ;/* * Check to see if proposed path is still parameterized , and reject if the * parameterization wouldn ' t be sensible . if (required_outer &&/* Waste no memory when we reject a path here */ 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 &&if (innersortkeys &&/* * See comments in try_nestloop_path ( ) . if (add_path_precheck(joinrel, workspace.disabled_nodes,else /* Waste no memory when we reject a path here */ /* * 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 int outer_presorted_keys = 0 ;/* * See comments in try_partial_hashjoin_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 &&if (innersortkeys &&/* * See comments in try_partial_nestloop_path ( ) . if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,return ;/* Might be good enough to be worth trying, so let's try it. */ /* * try_hashjoin_path * Consider a hash join path ; if it appears useful , push it into * the joinrel ' s pathlist via add_path ( ) . static void /* * 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 &&return ;/* * Check to see if proposed path is still parameterized , and reject if the * parameterization wouldn ' t be sensible . if (required_outer &&/* Waste no memory when we reject a path here */ return ;/* * See comments in try_nestloop_path ( ) . Also note that hashjoin paths * never have any output pathkeys , per comments in create_hashjoin_path . false );if (add_path_precheck(joinrel, workspace.disabled_nodes,false , /* parallel_hash */ else /* Waste no memory when we reject a path here */ /* * 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 bool parallel_hash)/* * 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 . 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 . if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,return ;/* Might be good enough to be worth trying, so let's try it. */ /* * 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 /* 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 . /* * 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) ||return ;/* * If unique - ification is requested , do it and then handle as a plain * inner join . if (jointype == JOIN_UNIQUE_OUTER)else if (jointype == JOIN_UNIQUE_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 &&if (inner_path->parallel_safe)else if (save_jointype != JOIN_UNIQUE_INNER)/* * 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 . /* Make a pathkey list with this guy first */ if (l != list_head(all_pathkeys))else /* no work at first one... */ /* Sort the mergeclauses into the corresponding ordering */ /* Should have used them all... */ /* Build sort pathkeys for the inner side */ /* Build pathkeys representing output sort order */ /* * 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 . false );/* * If we have partial outer and parallel safe inner path then try * partial mergejoin path . if (cheapest_partial_outer && cheapest_safe_inner)/* * 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 bool useallclauses,bool is_partial)int num_sortkeys;int sortkeycnt;if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)/* Look for useful mergeclauses (if any) */ /* * 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 &&return ;/* Compute the required ordering of the inner path */ /* * 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 . ) /* 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 didn't require a sort */ else /* it did require a sort, at least for the full set of keys */ if (num_sortkeys > 1 && !useallclauses)/* need modifiable copy */ else /* won't really truncate */ for (sortkeycnt = num_sortkeys; sortkeycnt > 0 ; sortkeycnt--)/* * 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 . . . if (innerpath != NULL &&0 ))/* Found a cheap (or even-cheaper) sorted path */ /* Select the right mergeclauses, if we didn't already */ if (sortkeycnt < num_sortkeys)else /* Same on the basis of cheapest startup cost ... */ if (innerpath != NULL &&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)else /* * 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 bool nestjoinOK;bool useallclauses;/* * 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:true ;false ;break ;case JOIN_RIGHT:case JOIN_RIGHT_ANTI:case JOIN_FULL:false ;true ;break ;case JOIN_UNIQUE_OUTER:case JOIN_UNIQUE_INNER:true ;false ;break ;default :"unrecognized join type: %d" ,int ) jointype);false ; /* keep compiler quiet */ 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))/* * 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 ;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 &&/* * 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 ;/* * 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 ) : if (save_jointype == JOIN_UNIQUE_INNER)/* * Consider nestloop join , but only with the unique - ified cheapest * inner path 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 . /* * Try generating a memoize path and see if that makes the * nested loop any cheaper . if (mpath != NULL)/* Also consider materialized form of the cheapest inner path */ if (matpath != NULL)/* 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 */ 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 &&if (nestjoinOK)/* * 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 ||if (save_jointype == JOIN_UNIQUE_INNER)return ;if (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 /* generate merge join path for each partial outer path */ /* * Figure out what useful ordering any paths we create will have . false , inner_cheapest_total,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 if (jointype == JOIN_UNIQUE_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 &&/* Figure out what useful ordering any paths we create will have. */ /* * 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 . /* 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 ;/* * Try generating a memoize path and see if that makes the nested * loop any cheaper . if (mpath != NULL)/* Also consider materialized form of the cheapest inner path */ if (matpath != NULL)/* * 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 bool isouterjoin = IS_OUTER_JOIN(jointype);/* * 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 . /* * 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 ||continue ; /* not hashjoinable */ /* * Check if clause has the form " outer op inner " or " inner op outer " . if (!clause_sides_match_join(restrictinfo, outerrel->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 &&continue ;/* 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 . /* * 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) ||return ;/* Unique-ify if need be; we ignore parameterized possibilities */ if (jointype == JOIN_UNIQUE_OUTER)/* no possibility of cheap startup here */ else if (jointype == JOIN_UNIQUE_INNER)if (cheapest_startup_outer != NULL &&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 . if (cheapest_startup_outer != NULL)/* * We cannot use an outer path that is parameterized by the * inner rel . if (PATH_PARAM_BY_REL(outerpath, innerrel))continue ;/* * 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 &&continue ; /* already tried it */ /* * 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 . * * Similarly , we can ' t handle JOIN_RIGHT_SEMI , because the hash table * is either a shared hash table or a private hash table per backend . * In the shared case , there is no concurrency protection for the * match flags , so multiple workers could inspect and set the flags * concurrently , potentially producing incorrect results . In the * private case , each worker has its own copy of the hash table , so no * single process has all the match flags . * * Also , the resulting path must not be parameterized . if (joinrel->consider_parallel &&/* * 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 &&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 , 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 ||else if (cheapest_total_inner->parallel_safe)else if (save_jointype != JOIN_UNIQUE_INNER)if (cheapest_safe_inner != NULL)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 *bool *mergejoin_allowed)bool isouterjoin = IS_OUTER_JOIN(jointype);bool have_nonmergeable_joinclause = false ;/* * 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)false ;return NIL;/* * 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 ||/* * 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 ))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,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 &&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 . ) if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||true ;continue ; /* can't handle redundant eclasses */ /* * Report whether mergejoin is allowed ( see comment at top of function ) . switch (jointype)case JOIN_RIGHT:case JOIN_RIGHT_ANTI:case JOIN_FULL:break ;default :true ;break ;return result_list;
Messung V0.5 in Prozent C=93 H=100 G=96
¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.75Angebot
(Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können 2026-10-01)
¤ *Eine klare Vorstellung vom Zielzustand
