LCOV - code coverage report
Current view: top level - src/backend/optimizer/path - joinpath.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 569 580 98.1 %
Date: 2025-04-24 12:15:10 Functions: 18 18 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.14