LCOV - code coverage report
Current view: top level - src/backend/optimizer/path - joinpath.c (source / functions) Coverage Total Hit
Test: PostgreSQL 20devel Lines: 98.3 % 582 572
Test Date: 2026-11-19 06:16:28 Functions: 100.0 % 20 20
Legend: Lines:     hit not hit
Branches: + taken - not taken # not executed
Branches: 90.4 % 697 630

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

Generated by: LCOV version 2.0-1