1/*-------------------------------------------------------------------------
4 * Routines to find all possible paths for processing a set of joins
6 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/optimizer/path/joinpath.c
13 *-------------------------------------------------------------------------
32/* Hook for plugins to get control in add_paths_to_joinrel() */
36 * Paths parameterized by a parent rel can be considered to be parameterized
37 * by any of its children, when we are performing partitionwise joins. These
38 * macros simplify checking for such cases. Beware multiple eval of args.
40 #define PATH_PARAM_BY_PARENT(path, rel) \
41 ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), \
42 (rel)->top_parent_relids))
43 #define PATH_PARAM_BY_REL_SELF(path, rel) \
44 ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids))
46 #define PATH_PARAM_BY_REL(path, rel) \
47 (PATH_PARAM_BY_REL_SELF(path, rel) || PATH_PARAM_BY_PARENT(path, rel))
77 Path *inner_cheapest_total);
87 bool *mergejoin_allowed);
95 Path *inner_cheapest_total,
101 * add_paths_to_joinrel
102 * Given a join relation and two component rels from which it can be made,
103 * consider all possible paths that use the two component rels as outer
104 * and inner rel respectively. Add these paths to the join rel's pathlist
105 * if they survive comparison with other paths (and remove any existing
106 * paths that are dominated by these paths).
108 * Modifies the pathlist field of the joinrel node to contain the best
109 * paths found so far.
111 * jointype is not necessarily the same as sjinfo->jointype; it might be
112 * "flipped around" if we are considering joining the rels in the opposite
113 * direction from what's indicated in sjinfo.
115 * Also, this routine accepts the special JoinTypes JOIN_UNIQUE_OUTER and
116 * JOIN_UNIQUE_INNER to indicate that the outer or inner relation has been
117 * unique-ified and a regular inner join should then be applied. These values
118 * are not allowed to propagate outside this routine, however. Path cost
119 * estimation code, as well as match_unsorted_outer, may need to recognize that
120 * it's dealing with such a case --- the combination of nominal jointype INNER
121 * with sjinfo->jointype == JOIN_SEMI indicates that.
134 bool mergejoin_allowed =
true;
139 * PlannerInfo doesn't contain the SpecialJoinInfos created for joins
140 * between child relations, even if there is a SpecialJoinInfo node for
141 * the join between the topmost parents. So, while calculating Relids set
142 * representing the restriction, consider relids of topmost parent of
148 joinrelids = joinrel->
relids;
156 * See if the inner relation is provably unique for this outer rel.
158 * We have some special cases: for JOIN_SEMI, it doesn't matter since the
159 * executor can make the equivalent optimization anyway. It also doesn't
160 * help enable use of Memoize, since a semijoin with a provably unique
161 * inner side should have been reduced to an inner join in that case.
162 * Therefore, we need not expend planner cycles on proofs. (For
163 * JOIN_ANTI, although it doesn't help the executor for the same reason,
164 * it can benefit Memoize paths.) For JOIN_UNIQUE_INNER, we must be
165 * considering a semijoin whose inner side is not provably unique (else
166 * reduce_unique_semijoins would've simplified it), so there's no point in
167 * calling innerrel_is_unique. However, if the LHS covers all of the
168 * semijoin's min_lefthand, then it's appropriate to set inner_unique
169 * because the unique relation produced by create_unique_paths will be
170 * unique relative to the LHS. (If we have an LHS that's only part of the
171 * min_lefthand, that is *not* true.) For JOIN_UNIQUE_OUTER, pass
172 * JOIN_INNER to avoid letting that value escape this module.
204 * If the outer or inner relation has been unique-ified, handle as a plain
211 * Find potential mergejoin clauses. We can skip this if we are not
212 * interested in doing a mergejoin. However, mergejoin may be our only
213 * way of implementing a full outer join, so override enable_mergejoin if
226 * If it's SEMI, ANTI, or inner_unique join, compute correction factors
227 * for cost estimation. These will be the same for all paths.
231 jointype, sjinfo, restrictlist,
235 * Decide whether it's sensible to generate parameterized paths for this
236 * joinrel, and if so, which relations such paths should require. There
237 * is usually no need to create a parameterized result path unless there
238 * is a join order restriction that prevents joining one of our input rels
239 * directly to the parameter source rel instead of joining to the other
240 * input rel. (But see allow_star_schema_join().) This restriction
241 * reduces the number of parameterized paths we have to deal with at
242 * higher join levels, without compromising the quality of the resulting
243 * plan. We express the restriction as a Relids set that must overlap the
244 * parameterization of any proposed join path. Note: param_source_rels
245 * should contain only baserels, not OJ relids, so starting from
246 * all_baserels not all_query_rels is correct.
248 foreach(lc,
root->join_info_list)
253 * SJ is relevant to this join if we have some part of its RHS
254 * (possibly not all of it), and haven't yet joined to its LHS. (This
255 * test is pretty simplistic, but should be sufficient considering the
256 * join has already been proven legal.) If the SJ is relevant, it
257 * presents constraints for joining to anything not in its RHS.
265 /* full joins constrain both sides symmetrically */
275 * However, when a LATERAL subquery is involved, there will simply not be
276 * any paths for the joinrel that aren't parameterized by whatever the
277 * subquery is parameterized by, unless its parameterization is resolved
278 * within the joinrel. So we might as well allow additional dependencies
279 * on whatever residual lateral dependencies the joinrel will have.
285 * 1. Consider mergejoin paths where both relations must be explicitly
286 * sorted. Skip this if we can't mergejoin.
288 if (mergejoin_allowed)
293 * 2. Consider paths where the outer relation need not be explicitly
294 * sorted. This includes both nestloops and mergejoins where the outer
295 * path is already ordered. Again, skip this if we can't mergejoin.
296 * (That's okay because we know that nestloop can't handle
297 * right/right-anti/right-semi/full joins at all, so it wouldn't work in
298 * the prohibited cases either.)
300 if (mergejoin_allowed)
307 * 3. Consider paths where the inner relation need not be explicitly
308 * sorted. This includes mergejoins only (nestloops were already built in
309 * match_unsorted_outer).
311 * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
312 * significant difference between the inner and outer side of a mergejoin,
313 * so match_unsorted_inner creates no paths that aren't equivalent to
314 * those made by match_unsorted_outer when add_paths_to_joinrel() is
315 * invoked with the two rels given in the other order.
317 if (mergejoin_allowed)
318 match_unsorted_inner(
root, joinrel, outerrel, innerrel,
323 * 4. Consider paths where both outer and inner relations must be hashed
324 * before being joined. As above, disregard enable_hashjoin for full
325 * joins, because there may be no other alternative.
332 * 5. If inner and outer relations are foreign tables (or joins) belonging
333 * to the same server and assigned to the same user to check access
334 * permissions as, give the FDW a chance to push down joins.
336 if (joinrel->fdwroutine &&
337 joinrel->fdwroutine->GetForeignJoinPaths)
338 joinrel->fdwroutine->GetForeignJoinPaths(
root, joinrel,
340 save_jointype, &extra);
343 * 6. Finally, give extensions a chance to manipulate the path list. They
344 * could add new paths (such as CustomPaths) by calling add_path(), or
345 * add_partial_path() if parallel aware. They could also delete or modify
346 * paths added by the core code.
350 save_jointype, &extra);
354 * We override the param_source_rels heuristic to accept nestloop paths in
355 * which the outer rel satisfies some but not all of the inner path's
356 * parameterization. This is necessary to get good plans for star-schema
357 * scenarios, in which a parameterized path for a large table may require
358 * parameters from multiple small tables that will not get joined directly to
359 * each other. We can handle that by stacking nestloops that have the small
360 * tables on the outside; but this breaks the rule the param_source_rels
361 * heuristic is based on, namely that parameters should not be passed down
362 * across joins unless there's a join-order-constraint-based reason to do so.
363 * So we ignore the param_source_rels restriction when this case applies.
365 * allow_star_schema_join() returns true if the param_source_rels restriction
366 * should be overridden, ie, it's okay to perform this join.
374 * It's a star-schema case if the outer rel provides some but not all of
375 * the inner rel's parameterization.
377 return (
bms_overlap(inner_paramrels, outerrelids) &&
382 * If the parameterization is only partly satisfied by the outer rel,
383 * the unsatisfied part can't include any outer-join relids that could
384 * null rels of the satisfied part. That would imply that we're trying
385 * to use a clause involving a Var with nonempty varnullingrels at
386 * a join level where that value isn't yet computable.
388 * In practice, this test never finds a problem because earlier join order
389 * restrictions prevent us from attempting a join that would cause a problem.
390 * (That's unsurprising, because the code worked before we ever added
391 * outer-join relids to expression relids.) It still seems worth checking
392 * as a backstop, but we only do so in assert-enabled builds.
394#ifdef USE_ASSERT_CHECKING
408 foreach(lc,
root->join_info_list)
413 continue;
/* not relevant */
418 result =
true;
/* doesn't work */
424 /* Waste no memory when we reject a path here */
430#endif /* USE_ASSERT_CHECKING */
433 * paraminfo_get_equal_hashops
434 * Determine if the clauses in param_info and innerrel's lateral vars
436 * Returns true if hashing is possible, otherwise false.
438 * Additionally, on success we collect the outer expressions and the
439 * appropriate equality operators for each hashable parameter to innerrel.
440 * These are returned in parallel lists in *param_exprs and *operators.
441 * We also set *binary_mode to indicate whether strict binary matching is
447 List *ph_lateral_vars,
List **param_exprs,
448 List **operators,
bool *binary_mode)
456 *binary_mode =
false;
458 /* Add join clauses from param_info to the hash key */
459 if (param_info != NULL)
473 * Bail if the rinfo is not compatible. We need a join OpExpr
485 if (rinfo->outer_is_left)
488 hasheqoperator = rinfo->left_hasheqoperator;
493 hasheqoperator = rinfo->right_hasheqoperator;
496 /* can't do memoize if we can't hash the outer type */
505 * 'expr' may already exist as a parameter from a previous item in
506 * ppi_clauses. No need to include it again, however we'd better
507 * ensure we do switch into binary mode if required. See below.
511 *operators =
lappend_oid(*operators, hasheqoperator);
512 *param_exprs =
lappend(*param_exprs, expr);
516 * When the join operator is not hashable then it's possible that
517 * the operator will be able to distinguish something that the
518 * hash equality operator could not. For example with floating
519 * point types -0.0 and +0.0 are classed as equal by the hash
520 * function and equality function, but some other operator may be
521 * able to tell those values apart. This means that we must put
522 * memoize into binary comparison mode so that it does bit-by-bit
523 * comparisons rather than a "logical" comparison as it would
524 * using the hash equality operator.
531 /* Now add any lateral vars to the cache key too */
533 foreach(lc, lateral_vars)
538 /* Reject if there are any volatile functions in lateral vars */
549 /* can't use memoize without a valid hash proc and equals operator */
558 * 'expr' may already exist as a parameter from the ppi_clauses. No
559 * need to include it again, however we'd better ensure we do switch
565 *param_exprs =
lappend(*param_exprs, expr);
569 * We must go into binary mode as we don't have too much of an idea of
570 * how these lateral Vars are being used. See comment above when we
571 * set *binary_mode for the non-lateral Var case. This could be
572 * relaxed a bit if we had the RestrictInfos and knew the operators
573 * being used, however for cases like Vars that are arguments to
574 * functions we must operate in binary mode as we don't have
575 * visibility into what the function is doing with the Vars.
580 /* We're okay to use memoize */
585 * extract_lateral_vars_from_PHVs
586 * Extract lateral references within PlaceHolderVars that are due to be
587 * evaluated at 'innerrelids'.
595 /* Nothing would be found if the query contains no LATERAL RTEs */
596 if (!
root->hasLateralRTEs)
600 * No need to consider PHVs that are due to be evaluated at joinrels,
601 * since we do not add Memoize nodes on top of joinrel paths.
606 foreach(lc,
root->placeholder_list)
612 /* PHV is uninteresting if no lateral refs */
616 /* PHV is uninteresting if not due to be evaluated at innerrelids */
621 * If the PHV does not reference any rels in innerrelids, use its
622 * contained expression as a cache key rather than extracting the
623 * Vars/PHVs from it and using those. This can be beneficial in cases
624 * where the expression results in fewer distinct values to cache
630 ph_lateral_vars =
lappend(ph_lateral_vars, phinfo->
ph_var->phexpr);
634 /* Fetch Vars and PHVs of lateral references within PlaceHolderVars */
647 ph_lateral_vars =
lappend(ph_lateral_vars, node);
657 ph_lateral_vars =
lappend(ph_lateral_vars, node);
666 return ph_lateral_vars;
671 * If possible, make and return a Memoize path atop of 'inner_path'.
672 * Otherwise return NULL.
674 * Note that currently we do not add Memoize nodes on top of join relation
675 * paths. This is because the ParamPathInfos for join relation paths do not
676 * maintain ppi_clauses, as the set of relevant clauses varies depending on how
677 * the join is formed. In addition, joinrels do not maintain lateral_vars. So
678 * we do not have a way to extract cache keys from joinrels.
687 List *hash_operators;
690 List *ph_lateral_vars;
692 /* Obviously not if it's disabled */
697 * We can safely not bother with all this unless we expect to perform more
698 * than one inner scan. The first scan is always going to be a cache
699 * miss. This would likely fail later anyway based on costs, so this is
700 * really just to save some wasted effort.
702 if (outer_path->parent->
rows < 2)
706 * Extract lateral Vars/PHVs within PlaceHolderVars that are due to be
707 * evaluated at innerrel. These lateral Vars/PHVs could be used as
708 * memoize cache keys.
713 * We can only have a memoize node when there's some kind of cache key,
714 * either parameterized path clauses or lateral Vars. No cache key sounds
715 * more like something a Materialize node might be more useful for.
717 if ((inner_path->param_info == NULL ||
718 inner_path->param_info->ppi_clauses ==
NIL) &&
720 ph_lateral_vars ==
NIL)
724 * Currently we don't do this for SEMI and ANTI joins, because nested loop
725 * SEMI/ANTI joins don't scan the inner node to completion, which means
726 * memoize cannot mark the cache entry as complete. Nor can we mark the
727 * cache entry as complete after fetching the first inner tuple, because
728 * if that tuple and the current outer tuple don't satisfy the join
729 * clauses, a second inner tuple that satisfies the parameters would find
730 * the cache entry already marked as complete. The only exception is when
731 * the inner relation is provably unique, as in that case, there won't be
732 * a second matching tuple and we can safely mark the cache entry as
733 * complete after fetching the first inner tuple. Note that in such
734 * cases, the SEMI join should have been reduced to an inner join by
735 * reduce_unique_semijoins.
742 * Memoize normally marks cache entries as complete when it runs out of
743 * tuples to read from its subplan. However, with unique joins, Nested
744 * Loop will skip to the next outer tuple after finding the first matching
745 * inner tuple. This means that we may not read the inner side of the
746 * join to completion which leaves no opportunity to mark the cache entry
747 * as complete. To work around that, when the join is unique we
748 * automatically mark cache entries as complete after fetching the first
749 * tuple. This works when the entire join condition is parameterized.
750 * Otherwise, when the parameterization is only a subset of the join
751 * condition, we can't be sure which part of it causes the join to be
752 * unique. This means there are no guarantees that only 1 tuple will be
753 * read. We cannot mark the cache entry as complete after reading the
754 * first tuple without that guarantee. This means the scope of Memoize
755 * node's usefulness is limited to only outer rows that have no join
756 * partner as this is the only case where Nested Loop would exhaust the
757 * inner scan of a unique join. Since the scope is limited to that, we
758 * just don't bother making a memoize path in this case.
760 * Lateral vars needn't be considered here as they're not considered when
761 * determining if the join is unique.
767 if (inner_path->param_info == NULL)
770 ppi_serials = inner_path->param_info->ppi_serials;
780 * We can't use a memoize node if there are volatile functions in the
781 * inner rel's target list or restrict list. A cache hit could reduce the
782 * number of calls to these functions.
796 * Also check the parameterized path restrictinfos for volatile functions.
797 * Indexed functions must be immutable so shouldn't have any volatile
798 * functions, however, with a lateral join the inner scan may not be an
801 if (inner_path->param_info != NULL)
803 foreach(lc, inner_path->param_info->ppi_clauses)
812 /* Check if we have hash ops for each parameter to the path */
814 inner_path->param_info,
815 outerrel->top_parent ?
816 outerrel->top_parent : outerrel,
838 * Consider a nestloop join path; if it appears useful, push it into
839 * the joinrel's pathlist via add_path().
860 * If we are forming an outer join at this join, it's nonsensical to use
861 * an input path that uses the outer join as part of its parameterization.
862 * (This can happen despite our join order restrictions, since those apply
863 * to what is in an input relation not what its parameters are.)
871 * Any parameterization of the input paths refers to topmost parents of
872 * the relevant relations, because reparameterize_path_by_child() hasn't
873 * been called yet. So we must consider topmost parents of the relations
874 * being joined, too, while determining parameterization of the result and
875 * checking for disallowed parameterization cases.
880 innerrelids = innerrel->
relids;
885 outerrelids = outerrel->
relids;
888 * Check to see if proposed path is still parameterized, and reject if the
889 * parameterization wouldn't be sensible --- unless allow_star_schema_join
890 * says to allow it anyway.
893 innerrelids, inner_paramrels);
894 if (required_outer &&
898 /* Waste no memory when we reject a path here */
903 /* If we got past that, we shouldn't have any unsafe outer-join refs */
904 Assert(!have_unsafe_outer_join_ref(
root, outerrelids, inner_paramrels));
907 * If the inner path is parameterized, it is parameterized by the topmost
908 * parent of the outer rel, not the outer rel itself. We will need to
909 * translate the parameterization, if this path is chosen, during
910 * create_plan(). Here we just check whether we will be able to perform
911 * the translation, and if not avoid creating a nestloop path.
921 * Do a precheck to quickly eliminate obviously-inferior paths. We
922 * calculate a cheap lower bound on the path's cost and then use
923 * add_path_precheck() to see if the path is clearly going to be dominated
924 * by some existing path for the joinrel. If not, do the full pushup with
925 * creating a fully valid path structure and submitting it to add_path().
926 * The latter two steps are expensive enough to make this two-phase
927 * methodology worthwhile.
930 outer_path, inner_path, extra);
934 pathkeys, required_outer))
950 /* Waste no memory when we reject a path here */
956 * try_partial_nestloop_path
957 * Consider a partial nestloop join path; if it appears useful, push it into
958 * the joinrel's partial_pathlist via add_partial_path().
972 * If the inner path is parameterized, the parameterization must be fully
973 * satisfied by the proposed outer path. Parameterized partial paths are
974 * not supported. The caller should already have verified that no lateral
975 * rels are required here.
979 if (inner_path->param_info != NULL)
981 Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
986 * The inner and outer paths are parameterized, if at all, by the top
987 * level parents, not the child relations, so we must use those relids
988 * for our parameterization tests.
993 outerrelids = outerrel->
relids;
1000 * If the inner path is parameterized, it is parameterized by the topmost
1001 * parent of the outer rel, not the outer rel itself. We will need to
1002 * translate the parameterization, if this path is chosen, during
1003 * create_plan(). Here we just check whether we will be able to perform
1004 * the translation, and if not avoid creating a nestloop path.
1011 * Before creating a path, get a quick lower bound on what it is likely to
1012 * cost. Bail out right away if it looks terrible.
1015 outer_path, inner_path, extra);
1020 /* Might be good enough to be worth trying, so let's try it. */
1035 * try_mergejoin_path
1036 * Consider a merge join path; if it appears useful, push it into
1037 * the joinrel's pathlist via add_path().
1046 List *outersortkeys,
1047 List *innersortkeys,
1053 int outer_presorted_keys = 0;
1072 * If we are forming an outer join at this join, it's nonsensical to use
1073 * an input path that uses the outer join as part of its parameterization.
1074 * (This can happen despite our join order restrictions, since those apply
1075 * to what is in an input relation not what its parameters are.)
1083 * Check to see if proposed path is still parameterized, and reject if the
1084 * parameterization wouldn't be sensible.
1088 if (required_outer &&
1091 /* Waste no memory when we reject a path here */
1097 * If the given paths are already well enough ordered, we can skip doing
1100 * We need to determine the number of presorted keys of the outer path to
1101 * decide whether explicit incremental sort can be applied when
1102 * outersortkeys is not NIL. We do not need to do the same for the inner
1103 * path though, as incremental sort currently does not support
1106 if (outersortkeys &&
1108 &outer_presorted_keys))
1109 outersortkeys =
NIL;
1110 if (innersortkeys &&
1112 innersortkeys =
NIL;
1115 * See comments in try_nestloop_path().
1118 outer_path, inner_path,
1119 outersortkeys, innersortkeys,
1120 outer_presorted_keys,
1125 pathkeys, required_outer))
1141 outer_presorted_keys));
1145 /* Waste no memory when we reject a path here */
1151 * try_partial_mergejoin_path
1152 * Consider a partial merge join path; if it appears useful, push it into
1153 * the joinrel's pathlist via add_partial_path().
1162 List *outersortkeys,
1163 List *innersortkeys,
1167 int outer_presorted_keys = 0;
1171 * See comments in try_partial_hashjoin_path().
1179 * If the given paths are already well enough ordered, we can skip doing
1182 * We need to determine the number of presorted keys of the outer path to
1183 * decide whether explicit incremental sort can be applied when
1184 * outersortkeys is not NIL. We do not need to do the same for the inner
1185 * path though, as incremental sort currently does not support
1188 if (outersortkeys &&
1190 &outer_presorted_keys))
1191 outersortkeys =
NIL;
1192 if (innersortkeys &&
1194 innersortkeys =
NIL;
1197 * See comments in try_partial_nestloop_path().
1200 outer_path, inner_path,
1201 outersortkeys, innersortkeys,
1202 outer_presorted_keys,
1209 /* Might be good enough to be worth trying, so let's try it. */
1224 outer_presorted_keys));
1229 * Consider a hash join path; if it appears useful, push it into
1230 * the joinrel's pathlist via add_path().
1245 * If we are forming an outer join at this join, it's nonsensical to use
1246 * an input path that uses the outer join as part of its parameterization.
1247 * (This can happen despite our join order restrictions, since those apply
1248 * to what is in an input relation not what its parameters are.)
1256 * Check to see if proposed path is still parameterized, and reject if the
1257 * parameterization wouldn't be sensible.
1261 if (required_outer &&
1264 /* Waste no memory when we reject a path here */
1270 * See comments in try_nestloop_path(). Also note that hashjoin paths
1271 * never have any output pathkeys, per comments in create_hashjoin_path.
1274 outer_path, inner_path, extra,
false);
1278 NIL, required_outer))
1288 false,
/* parallel_hash */
1295 /* Waste no memory when we reject a path here */
1301 * try_partial_hashjoin_path
1302 * Consider a partial hashjoin join path; if it appears useful, push it into
1303 * the joinrel's partial_pathlist via add_partial_path().
1304 * The outer side is partial. If parallel_hash is true, then the inner path
1305 * must be partial and will be run in parallel to create one or more shared
1306 * hash tables; otherwise the inner path must be complete and a copy of it
1307 * is run in every process to create separate identical private hash tables.
1322 * If the inner path is parameterized, we can't use a partial hashjoin.
1323 * Parameterized partial paths are not supported. The caller should
1324 * already have verified that no lateral rels are required here.
1332 * Before creating a path, get a quick lower bound on what it is likely to
1333 * cost. Bail out right away if it looks terrible.
1336 outer_path, inner_path, extra, parallel_hash);
1341 /* Might be good enough to be worth trying, so let's try it. */
1357 * sort_inner_and_outer
1358 * Create mergejoin join paths by explicitly sorting both the outer and
1359 * inner join relations on each available merge ordering.
1361 * 'joinrel' is the join relation
1362 * 'outerrel' is the outer join relation
1363 * 'innerrel' is the inner join relation
1364 * 'jointype' is the type of join to do
1365 * 'extra' contains additional input values
1377 Path *cheapest_partial_outer = NULL;
1378 Path *cheapest_safe_inner = NULL;
1382 /* Nothing to do if there are no available mergejoin clauses */
1387 * We only consider the cheapest-total-cost input paths, since we are
1388 * assuming here that a sort is required. We will consider
1389 * cheapest-startup-cost input paths later, and only if they don't need a
1392 * This function intentionally does not consider parameterized input
1393 * paths, except when the cheapest-total is parameterized. If we did so,
1394 * we'd have a combinatorial explosion of mergejoin paths of dubious
1395 * value. This interacts with decisions elsewhere that also discriminate
1396 * against mergejoins with parameterized inputs; see comments in
1397 * src/backend/optimizer/README.
1403 * If either cheapest-total path is parameterized by the other rel, we
1404 * can't use a mergejoin. (There's no use looking for alternative input
1405 * paths, since these should already be the least-parameterized available
1413 * If the joinrel is parallel-safe, we may be able to consider a partial
1414 * merge join. However, we can't handle JOIN_FULL, JOIN_RIGHT and
1415 * JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1416 * Also, the resulting path must not be parameterized.
1428 cheapest_safe_inner = inner_path;
1430 cheapest_safe_inner =
1435 * Each possible ordering of the available mergejoin clauses will generate
1436 * a differently-sorted result path at essentially the same cost. We have
1437 * no basis for choosing one over another at this level of joining, but
1438 * some sort orders may be more useful than others for higher-level
1439 * mergejoins, so it's worth considering multiple orderings.
1441 * Actually, it's not quite true that every mergeclause ordering will
1442 * generate a different path order, because some of the clauses may be
1443 * partially redundant (refer to the same EquivalenceClasses). Therefore,
1444 * what we do is convert the mergeclause list to a list of canonical
1445 * pathkeys, and then consider different orderings of the pathkeys.
1447 * Generating a path for *every* permutation of the pathkeys doesn't seem
1448 * like a winning strategy; the cost in planning time is too high. For
1449 * now, we generate one path for each pathkey, listing that pathkey first
1450 * and the rest in random order. This should allow at least a one-clause
1451 * mergejoin without re-sorting against any other possible mergejoin
1452 * partner path. But if we've not guessed the right ordering of secondary
1453 * keys, we may end up evaluating clauses as qpquals when they could have
1454 * been done as mergeclauses. (In practice, it's rare that there's more
1455 * than two or three mergeclauses, so expending a huge amount of thought
1456 * on that is probably not worth it.)
1458 * The pathkey order returned by select_outer_pathkeys_for_merge() has
1459 * some heuristics behind it (see that function), so be sure to try it
1460 * exactly as-is as well as making variants.
1466 foreach(l, all_pathkeys)
1469 List *cur_mergeclauses;
1472 List *merge_pathkeys;
1474 /* Make a pathkey list with this guy first */
1476 outerkeys =
lcons(front_pathkey,
1480 outerkeys = all_pathkeys;
/* no work at first one... */
1482 /* Sort the mergeclauses into the corresponding ordering */
1488 /* Should have used them all... */
1491 /* Build sort pathkeys for the inner side */
1496 /* Build pathkeys representing output sort order */
1501 * And now we can make the path.
1503 * Note: it's possible that the cheapest paths will already be sorted
1504 * properly. try_mergejoin_path will detect that case and suppress an
1505 * explicit sort step, so we needn't do so here.
1520 * If we have partial outer and parallel safe inner path then try
1521 * partial mergejoin path.
1523 if (cheapest_partial_outer && cheapest_safe_inner)
1526 cheapest_partial_outer,
1527 cheapest_safe_inner,
1538 * generate_mergejoin_paths
1539 * Creates possible mergejoin paths for input outerpath.
1541 * We generate mergejoins if mergejoin clauses are available. We have
1542 * two ways to generate the inner path for a mergejoin: sort the cheapest
1543 * inner path, or use an inner path that is already suitably ordered for the
1544 * merge. If we have several mergeclauses, it could be that there is no inner
1545 * path (or only a very expensive one) for the full list of mergeclauses, but
1546 * better paths exist if we truncate the mergeclause list (thereby discarding
1547 * some sort key requirements). So, we consider truncations of the
1548 * mergeclause list as well as the full list. (Ideally we'd consider all
1549 * subsets of the mergeclause list, but that seems way too expensive.)
1559 Path *inner_cheapest_total,
1560 List *merge_pathkeys,
1564 List *innersortkeys;
1565 List *trialsortkeys;
1566 Path *cheapest_startup_inner;
1567 Path *cheapest_total_inner;
1571 /* Look for useful mergeclauses (if any) */
1578 * Done with this outer path if no chance for a mergejoin.
1580 * Special corner case: for "x FULL JOIN y ON true", there will be no join
1581 * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1582 * but since mergejoin is our only join type that supports FULL JOIN
1583 * without any join clauses, it's necessary to generate a clauseless
1584 * mergejoin path instead.
1586 if (mergeclauses ==
NIL)
1589 /* okay to try for mergejoin */ ;
1593 if (useallclauses &&
1597 /* Compute the required ordering of the inner path */
1603 * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1604 * a sort will be needed, only cheapest total cost matters. (But
1605 * try_mergejoin_path will do the right thing if inner_cheapest_total is
1606 * already correctly sorted.)
1611 inner_cheapest_total,
1621 * Look for presorted inner paths that satisfy the innersortkey list ---
1622 * or any truncation thereof, if we are allowed to build a mergejoin using
1623 * a subset of the merge clauses. Here, we consider both cheap startup
1624 * cost and cheap total cost.
1626 * Currently we do not consider parameterized inner paths here. This
1627 * interacts with decisions elsewhere that also discriminate against
1628 * mergejoins with parameterized inputs; see comments in
1629 * src/backend/optimizer/README.
1631 * As we shorten the sortkey list, we should consider only paths that are
1632 * strictly cheaper than (in particular, not the same as) any path found
1633 * in an earlier iteration. Otherwise we'd be intentionally using fewer
1634 * merge keys than a given path allows (treating the rest as plain
1635 * joinquals), which is unlikely to be a good idea. Also, eliminating
1636 * paths here on the basis of compare_path_costs is a lot cheaper than
1637 * building the mergejoin path only to throw it away.
1639 * If inner_cheapest_total is well enough sorted to have not required a
1640 * sort in the path made above, we shouldn't make a duplicate path with
1641 * it, either. We handle that case with the same logic that handles the
1642 * previous consideration, by initializing the variables that track
1643 * cheapest-so-far properly. Note that we do NOT reject
1644 * inner_cheapest_total if we find it matches some shorter set of
1645 * pathkeys. That case corresponds to using fewer mergekeys to avoid
1646 * sorting inner_cheapest_total, whereas we did sort it above, so the
1647 * plans being considered are different.
1652 /* inner_cheapest_total didn't require a sort */
1653 cheapest_startup_inner = inner_cheapest_total;
1654 cheapest_total_inner = inner_cheapest_total;
1658 /* it did require a sort, at least for the full set of keys */
1659 cheapest_startup_inner = NULL;
1660 cheapest_total_inner = NULL;
1663 if (num_sortkeys > 1 && !useallclauses)
1664 trialsortkeys =
list_copy(innersortkeys);
/* need modifiable copy */
1666 trialsortkeys = innersortkeys;
/* won't really truncate */
1668 for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1674 * Look for an inner path ordered well enough for the first
1675 * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1676 * destructively, which is why we made a copy...
1684 if (innerpath != NULL &&
1685 (cheapest_total_inner == NULL ||
1689 /* Found a cheap (or even-cheaper) sorted path */
1690 /* Select the right mergeclauses, if we didn't already */
1691 if (sortkeycnt < num_sortkeys)
1700 newclauses = mergeclauses;
1712 cheapest_total_inner = innerpath;
1714 /* Same on the basis of cheapest startup cost ... */
1720 if (innerpath != NULL &&
1721 (cheapest_startup_inner == NULL ||
1725 /* Found a cheap (or even-cheaper) sorted path */
1726 if (innerpath != cheapest_total_inner)
1729 * Avoid rebuilding clause list if we already made one; saves
1730 * memory in big join trees...
1732 if (newclauses ==
NIL)
1734 if (sortkeycnt < num_sortkeys)
1743 newclauses = mergeclauses;
1757 cheapest_startup_inner = innerpath;
1761 * Don't consider truncated sortkeys if we need all clauses.
1769 * match_unsorted_outer
1770 * Creates possible join paths for processing a single join relation
1771 * 'joinrel' by employing either iterative substitution or
1772 * mergejoining on each of its possible outer paths (considering
1773 * only outer paths that are already ordered well enough for merging).
1775 * We always generate a nestloop path for each available outer path.
1776 * In fact we may generate as many as five: one on the cheapest-total-cost
1777 * inner path, one on the same with materialization, one on the
1778 * cheapest-startup-cost inner path (if different), one on the
1779 * cheapest-total inner-indexscan path (if any), and one on the
1780 * cheapest-startup inner-indexscan path (if different).
1782 * We also consider mergejoins if mergejoin clauses are available. See
1783 * detailed comments in generate_mergejoin_paths.
1785 * 'joinrel' is the join relation
1786 * 'outerrel' is the outer join relation
1787 * 'innerrel' is the inner join relation
1788 * 'jointype' is the type of join to do
1789 * 'extra' contains additional input values
1802 Path *matpath = NULL;
1806 * For now we do not support RIGHT_SEMI join in mergejoin or nestloop
1813 * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1814 * are doing a right, right-anti or full mergejoin, we must use *all* the
1815 * mergeclauses as join clauses, else we will not have a valid plan.
1816 * (Although these two flags are currently inverses, keep them separate
1817 * for clarity and possible future changes.)
1826 useallclauses =
false;
1832 useallclauses =
true;
1835 elog(
ERROR,
"unrecognized join type: %d",
1837 nestjoinOK =
false;
/* keep compiler quiet */
1838 useallclauses =
false;
1843 * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1844 * we will consider it below as a member of cheapest_parameterized_paths,
1845 * but the other possibilities considered in this routine aren't usable.
1847 * Furthermore, if the inner side is a unique-ified relation, we cannot
1848 * generate any valid paths here, because the inner rel's dependency on
1849 * the outer rel makes unique-ification meaningless.
1853 inner_cheapest_total = NULL;
1862 * Consider materializing the cheapest inner path, unless
1863 * enable_material is off or the path in question materializes its
1875 List *merge_pathkeys;
1878 * We cannot use an outer path that is parameterized by the inner rel.
1884 * The result will have this sort order (even if it is implemented as
1885 * a nestloop, and even if some of the mergeclauses are implemented by
1886 * qpquals rather than as true mergeclauses):
1894 * Consider nestloop joins using this outer path and various
1895 * available paths for the inner relation. We consider the
1896 * cheapest-total paths for each available parameterization of the
1897 * inner relation, including the unparameterized case.
1915 * Try generating a memoize path and see if that makes the
1916 * nested loop any cheaper.
1919 innerpath, outerpath, jointype,
1931 /* Also consider materialized form of the cheapest inner path */
1932 if (matpath != NULL)
1942 /* Can't do anything else if inner rel is parameterized by outer */
1943 if (inner_cheapest_total == NULL)
1946 /* Generate merge join paths */
1948 jointype, extra, useallclauses,
1949 inner_cheapest_total, merge_pathkeys,
1954 * Consider partial nestloop and mergejoin plan if outerrel has any
1955 * partial path and the joinrel is parallel-safe. However, we can't
1956 * handle joins needing lateral rels, since partial paths must not be
1957 * parameterized. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT and
1958 * JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1972 * If inner_cheapest_total is NULL or non parallel-safe then find the
1973 * cheapest total parallel safe path.
1975 if (inner_cheapest_total == NULL ||
1978 inner_cheapest_total =
1982 if (inner_cheapest_total)
1985 inner_cheapest_total);
1990 * consider_parallel_mergejoin
1991 * Try to build partial paths for a joinrel by joining a partial path
1992 * for the outer relation to a complete path for the inner relation.
1994 * 'joinrel' is the join relation
1995 * 'outerrel' is the outer join relation
1996 * 'innerrel' is the inner join relation
1997 * 'jointype' is the type of join to do
1998 * 'extra' contains additional input values
1999 * 'inner_cheapest_total' cheapest total path for innerrel
2008 Path *inner_cheapest_total)
2012 /* generate merge join path for each partial outer path */
2016 List *merge_pathkeys;
2019 * Figure out what useful ordering any paths we create will have.
2025 extra,
false, inner_cheapest_total,
2026 merge_pathkeys,
true);
2031 * consider_parallel_nestloop
2032 * Try to build partial paths for a joinrel by joining a partial path for the
2033 * outer relation to a complete path for the inner relation.
2035 * 'joinrel' is the join relation
2036 * 'outerrel' is the outer join relation
2037 * 'innerrel' is the inner join relation
2038 * 'jointype' is the type of join to do
2039 * 'extra' contains additional input values
2050 Path *matpath = NULL;
2054 * Consider materializing the cheapest inner path, unless: 1)
2055 * enable_material is off, 2) the cheapest inner path is not
2056 * parallel-safe, 3) the cheapest inner path is parameterized by the outer
2057 * rel, or 4) the cheapest inner path materializes its output anyway.
2074 /* Figure out what useful ordering any paths we create will have. */
2079 * Try the cheapest parameterized paths; only those which will produce
2080 * an unparameterized path when joined to this outerrel will survive
2081 * try_partial_nestloop_path. The cheapest unparameterized path is
2082 * also in this list.
2089 /* Can't join to an inner path that is not parallel-safe */
2094 pathkeys, jointype, extra);
2097 * Try generating a memoize path and see if that makes the nested
2101 innerpath, outerpath, jointype,
2105 pathkeys, jointype, extra);
2108 /* Also consider materialized form of the cheapest inner path */
2109 if (matpath != NULL)
2111 pathkeys, jointype, extra);
2116 * hash_inner_and_outer
2117 * Create hashjoin join paths by explicitly hashing both the outer and
2118 * inner keys of each available hash clause.
2120 * 'joinrel' is the join relation
2121 * 'outerrel' is the outer join relation
2122 * 'innerrel' is the inner join relation
2123 * 'jointype' is the type of join to do
2124 * 'extra' contains additional input values
2139 * We need to build only one hashclauses list for any given pair of outer
2140 * and inner relations; all of the hashable clauses will be used as keys.
2142 * Scan the join's restrictinfo list to find hashjoinable clauses that are
2143 * usable with this pair of sub-relations.
2151 * If processing an outer join, only use its own join clauses for
2152 * hashing. For inner joins we need not be so picky.
2157 if (!restrictinfo->can_join ||
2158 restrictinfo->hashjoinoperator ==
InvalidOid)
2159 continue;
/* not hashjoinable */
2162 * Check if clause has the form "outer op inner" or "inner op outer".
2166 continue;
/* no good for these input relations */
2169 * If clause has the form "inner op outer", check if its operator has
2170 * valid commutator. This is necessary because hashclauses in this
2171 * form will get commuted in createplan.c to put the outer var on the
2172 * left (see get_switched_clauses). This probably shouldn't ever
2173 * fail, since hashable operators ought to have commutators, but be
2176 * The clause being hashjoinable indicates that it's an OpExpr.
2178 if (!restrictinfo->outer_is_left &&
2182 hashclauses =
lappend(hashclauses, restrictinfo);
2185 /* If we found any usable hashclauses, make paths */
2189 * We consider both the cheapest-total-cost and cheapest-startup-cost
2190 * outer paths. There's no need to consider any but the
2191 * cheapest-total-cost inner path, however.
2200 * If either cheapest-total path is parameterized by the other rel, we
2201 * can't use a hashjoin. (There's no use looking for alternative
2202 * input paths, since these should already be the least-parameterized
2210 * Consider the cheapest startup outer together with the cheapest
2211 * total inner, and then consider pairings of cheapest-total paths
2212 * including parameterized ones. There is no use in generating
2213 * parameterized paths on the basis of possibly cheap startup cost, so
2214 * this is sufficient.
2216 if (cheapest_startup_outer != NULL)
2219 cheapest_startup_outer,
2220 cheapest_total_inner,
2230 * We cannot use an outer path that is parameterized by the inner
2241 * We cannot use an inner path that is parameterized by the
2242 * outer rel, either.
2247 if (outerpath == cheapest_startup_outer &&
2248 innerpath == cheapest_total_inner)
2249 continue;
/* already tried it */
2262 * If the joinrel is parallel-safe, we may be able to consider a
2263 * partial hash join. However, the resulting path must not be
2270 Path *cheapest_partial_outer;
2271 Path *cheapest_partial_inner = NULL;
2272 Path *cheapest_safe_inner = NULL;
2274 cheapest_partial_outer =
2278 * Can we use a partial inner plan too, so that we can build a
2279 * shared hash table in parallel?
2284 cheapest_partial_inner =
2287 cheapest_partial_outer,
2288 cheapest_partial_inner,
2289 hashclauses, jointype, extra,
2290 true /* parallel_hash */ );
2294 * Normally, given that the joinrel is parallel-safe, the cheapest
2295 * total inner path will also be parallel-safe, but if not, we'll
2296 * have to search for the cheapest safe, unparameterized inner
2297 * path. If full, right, right-semi or right-anti join, we can't
2298 * use parallelism (building the hash table in each backend)
2299 * because no one process has all the match bits.
2305 cheapest_safe_inner = NULL;
2307 cheapest_safe_inner = cheapest_total_inner;
2309 cheapest_safe_inner =
2312 if (cheapest_safe_inner != NULL)
2314 cheapest_partial_outer,
2315 cheapest_safe_inner,
2316 hashclauses, jointype, extra,
2317 false /* parallel_hash */ );
2323 * select_mergejoin_clauses
2324 * Select mergejoin clauses that are usable for a particular join.
2325 * Returns a list of RestrictInfo nodes for those clauses.
2327 * *mergejoin_allowed is normally set to true, but it is set to false if
2328 * this is a right-semi join, or this is a right/right-anti/full join and
2329 * there are nonmergejoinable join clauses. The executor's mergejoin
2330 * machinery cannot handle such cases, so we have to avoid generating a
2331 * mergejoin plan. (Note that this flag does NOT consider whether there are
2332 * actually any mergejoinable clauses. This is correct because in some
2333 * cases we need to build a clauseless mergejoin. Simply returning NIL is
2334 * therefore not enough to distinguish safe from unsafe cases.)
2336 * We also mark each selected RestrictInfo to show which side is currently
2337 * being considered as outer. These are transient markings that are only
2338 * good for the duration of the current add_paths_to_joinrel() call!
2340 * We examine each restrictinfo clause known for the join to see
2341 * if it is mergejoinable and involves vars from the two sub-relations
2342 * currently of interest.
2351 bool *mergejoin_allowed)
2355 bool have_nonmergeable_joinclause =
false;
2359 * For now we do not support RIGHT_SEMI join in mergejoin: the benefit of
2360 * swapping inputs tends to be small here.
2364 *mergejoin_allowed =
false;
2368 foreach(l, restrictlist)
2373 * If processing an outer join, only use its own join clauses in the
2374 * merge. For inner joins we can use pushed-down clauses too. (Note:
2375 * we don't set have_nonmergeable_joinclause here because pushed-down
2376 * clauses will become otherquals not joinquals.)
2381 /* Check that clause is a mergeable operator clause */
2382 if (!restrictinfo->can_join ||
2383 restrictinfo->mergeopfamilies ==
NIL)
2386 * The executor can handle extra joinquals that are constants, but
2387 * not anything else, when doing right/right-anti/full merge join.
2388 * (The reason to support constants is so we can do FULL JOIN ON
2392 have_nonmergeable_joinclause =
true;
2393 continue;
/* not mergejoinable */
2397 * Check if clause has the form "outer op inner" or "inner op outer".
2402 have_nonmergeable_joinclause =
true;
2403 continue;
/* no good for these input relations */
2407 * If clause has the form "inner op outer", check if its operator has
2408 * valid commutator. This is necessary because mergejoin clauses in
2409 * this form will get commuted in createplan.c to put the outer var on
2410 * the left (see get_switched_clauses). This probably shouldn't ever
2411 * fail, since mergejoinable operators ought to have commutators, but
2414 * The clause being mergejoinable indicates that it's an OpExpr.
2416 if (!restrictinfo->outer_is_left &&
2419 have_nonmergeable_joinclause =
true;
2424 * Insist that each side have a non-redundant eclass. This
2425 * restriction is needed because various bits of the planner expect
2426 * that each clause in a merge be associable with some pathkey in a
2427 * canonical pathkey list, but redundant eclasses can't appear in
2428 * canonical sort orderings. (XXX it might be worth relaxing this,
2429 * but not enough time to address it for 8.3.)
2436 have_nonmergeable_joinclause =
true;
2437 continue;
/* can't handle redundant eclasses */
2440 result_list =
lappend(result_list, restrictinfo);
2444 * Report whether mergejoin is allowed (see comment at top of function).
2451 *mergejoin_allowed = !have_nonmergeable_joinclause;
2454 *mergejoin_allowed =
true;
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
void bms_free(Bitmapset *a)
bool bms_is_member(int x, const Bitmapset *a)
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
BMS_Membership bms_membership(const Bitmapset *a)
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
#define OidIsValid(objectId)
bool contain_volatile_functions(Node *clause)
void compute_semi_anti_join_factors(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist, SemiAntiJoinFactors *semifactors)
void initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *hashclauses, Path *outer_path, Path *inner_path, JoinPathExtraData *extra, bool parallel_hash)
void initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *mergeclauses, Path *outer_path, Path *inner_path, List *outersortkeys, List *innersortkeys, int outer_presorted_keys, JoinPathExtraData *extra)
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
bool enable_parallel_hash
bool ExecMaterializesOutput(NodeTag plantype)
Assert(PointerIsAligned(start, uint64))
if(TABLE==NULL||TABLE_index==NULL)
static void try_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, 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 sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
static List * extract_lateral_vars_from_PHVs(PlannerInfo *root, Relids innerrelids)
void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
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)
static void try_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
static Path * get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
#define PATH_PARAM_BY_PARENT(path, rel)
set_join_pathlist_hook_type set_join_pathlist_hook
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)
static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
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)
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
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)
#define PATH_PARAM_BY_REL(path, rel)
static bool allow_star_schema_join(PlannerInfo *root, Relids outerrelids, Relids inner_paramrels)
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)
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
static void try_partial_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
List * lappend(List *list, void *datum)
List * list_delete_nth_cell(List *list, int n)
List * list_concat(List *list1, const List *list2)
List * list_copy(const List *oldlist)
List * lappend_oid(List *list, Oid datum)
List * lcons(void *datum, List *list)
void list_free(List *list)
List * list_truncate(List *list, int new_size)
bool list_member(const List *list, const void *datum)
Oid get_commutator(Oid opno)
Oid exprType(const Node *expr)
#define IsA(nodeptr, _type_)
#define IS_OUTER_JOIN(jointype)
#define castNode(_type_, nodeptr)
Path * get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
List * make_inner_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
List * find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, List *pathkeys, List *restrictinfos)
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
List * trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root, List *mergeclauses, List *pathkeys)
List * select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
bool pathkeys_contained_in(List *keys1, List *keys2)
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
bool path_is_reparameterizable_by_child(Path *path, RelOptInfo *child_rel)
MemoizePath * create_memoize_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *param_exprs, List *hash_operators, bool singlerow, bool binary_mode, Cardinality est_calls)
Relids calc_nestloop_required_outer(Relids outerrelids, Relids outer_paramrels, Relids innerrelids, Relids inner_paramrels)
HashPath * create_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, bool parallel_hash, List *restrict_clauses, Relids required_outer, List *hashclauses)
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath)
void add_path(RelOptInfo *parent_rel, Path *new_path)
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
bool add_path_precheck(RelOptInfo *parent_rel, int disabled_nodes, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
bool add_partial_path_precheck(RelOptInfo *parent_rel, int disabled_nodes, Cost total_cost, List *pathkeys)
MergePath * create_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, List *restrict_clauses, List *pathkeys, Relids required_outer, List *mergeclauses, List *outersortkeys, List *innersortkeys, int outer_presorted_keys)
NestPath * create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, List *restrict_clauses, List *pathkeys, Relids required_outer)
#define EC_MUST_BE_REDUNDANT(eclass)
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
#define PATH_REQ_OUTER(path)
#define RELATION_WAS_MADE_UNIQUE(rel, sjinfo, nominal_jointype)
void(* set_join_pathlist_hook_type)(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
static int list_length(const List *l)
#define foreach_current_index(var_or_cell)
#define foreach_node(type, var, lst)
static ListCell * list_head(const List *l)
PlaceHolderInfo * find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
static bool clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
struct PathTarget * reltarget
List * cheapest_parameterized_paths
struct Path * cheapest_startup_path
struct Path * cheapest_total_path
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
#define TYPECACHE_HASH_PROC
Relids pull_varnos(PlannerInfo *root, Node *node)
List * pull_vars_of_level(Node *node, int levelsup)