LCOV - code coverage report
Current view: top level - src/backend/optimizer/path - pathkeys.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 470 497 94.6 %
Date: 2023-12-07 07:10:44 Functions: 32 32 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * pathkeys.c
       4             :  *    Utilities for matching and building path keys
       5             :  *
       6             :  * See src/backend/optimizer/README for a great deal of information about
       7             :  * the nature and use of path keys.
       8             :  *
       9             :  *
      10             :  * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
      11             :  * Portions Copyright (c) 1994, Regents of the University of California
      12             :  *
      13             :  * IDENTIFICATION
      14             :  *    src/backend/optimizer/path/pathkeys.c
      15             :  *
      16             :  *-------------------------------------------------------------------------
      17             :  */
      18             : #include "postgres.h"
      19             : 
      20             : #include "access/stratnum.h"
      21             : #include "catalog/pg_opfamily.h"
      22             : #include "nodes/makefuncs.h"
      23             : #include "nodes/nodeFuncs.h"
      24             : #include "nodes/plannodes.h"
      25             : #include "optimizer/optimizer.h"
      26             : #include "optimizer/pathnode.h"
      27             : #include "optimizer/paths.h"
      28             : #include "partitioning/partbounds.h"
      29             : #include "utils/lsyscache.h"
      30             : 
      31             : 
      32             : static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
      33             : static bool matches_boolean_partition_clause(RestrictInfo *rinfo,
      34             :                                              RelOptInfo *partrel,
      35             :                                              int partkeycol);
      36             : static Var *find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle);
      37             : static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
      38             : 
      39             : 
      40             : /****************************************************************************
      41             :  *      PATHKEY CONSTRUCTION AND REDUNDANCY TESTING
      42             :  ****************************************************************************/
      43             : 
      44             : /*
      45             :  * make_canonical_pathkey
      46             :  *    Given the parameters for a PathKey, find any pre-existing matching
      47             :  *    pathkey in the query's list of "canonical" pathkeys.  Make a new
      48             :  *    entry if there's not one already.
      49             :  *
      50             :  * Note that this function must not be used until after we have completed
      51             :  * merging EquivalenceClasses.
      52             :  */
      53             : PathKey *
      54     1629346 : make_canonical_pathkey(PlannerInfo *root,
      55             :                        EquivalenceClass *eclass, Oid opfamily,
      56             :                        int strategy, bool nulls_first)
      57             : {
      58             :     PathKey    *pk;
      59             :     ListCell   *lc;
      60             :     MemoryContext oldcontext;
      61             : 
      62             :     /* Can't make canonical pathkeys if the set of ECs might still change */
      63     1629346 :     if (!root->ec_merging_done)
      64           0 :         elog(ERROR, "too soon to build canonical pathkeys");
      65             : 
      66             :     /* The passed eclass might be non-canonical, so chase up to the top */
      67     1629346 :     while (eclass->ec_merged)
      68           0 :         eclass = eclass->ec_merged;
      69             : 
      70     8067854 :     foreach(lc, root->canon_pathkeys)
      71             :     {
      72     7612306 :         pk = (PathKey *) lfirst(lc);
      73     7612306 :         if (eclass == pk->pk_eclass &&
      74     1560034 :             opfamily == pk->pk_opfamily &&
      75     1560034 :             strategy == pk->pk_strategy &&
      76     1173852 :             nulls_first == pk->pk_nulls_first)
      77     1173798 :             return pk;
      78             :     }
      79             : 
      80             :     /*
      81             :      * Be sure canonical pathkeys are allocated in the main planning context.
      82             :      * Not an issue in normal planning, but it is for GEQO.
      83             :      */
      84      455548 :     oldcontext = MemoryContextSwitchTo(root->planner_cxt);
      85             : 
      86      455548 :     pk = makeNode(PathKey);
      87      455548 :     pk->pk_eclass = eclass;
      88      455548 :     pk->pk_opfamily = opfamily;
      89      455548 :     pk->pk_strategy = strategy;
      90      455548 :     pk->pk_nulls_first = nulls_first;
      91             : 
      92      455548 :     root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
      93             : 
      94      455548 :     MemoryContextSwitchTo(oldcontext);
      95             : 
      96      455548 :     return pk;
      97             : }
      98             : 
      99             : /*
     100             :  * append_pathkeys
     101             :  *      Append all non-redundant PathKeys in 'source' onto 'target' and
     102             :  *      returns the updated 'target' list.
     103             :  */
     104             : List *
     105        1414 : append_pathkeys(List *target, List *source)
     106             : {
     107             :     ListCell   *lc;
     108             : 
     109             :     Assert(target != NIL);
     110             : 
     111        2882 :     foreach(lc, source)
     112             :     {
     113        1468 :         PathKey    *pk = lfirst_node(PathKey, lc);
     114             : 
     115        1468 :         if (!pathkey_is_redundant(pk, target))
     116        1330 :             target = lappend(target, pk);
     117             :     }
     118        1414 :     return target;
     119             : }
     120             : 
     121             : /*
     122             :  * pathkey_is_redundant
     123             :  *     Is a pathkey redundant with one already in the given list?
     124             :  *
     125             :  * We detect two cases:
     126             :  *
     127             :  * 1. If the new pathkey's equivalence class contains a constant, and isn't
     128             :  * below an outer join, then we can disregard it as a sort key.  An example:
     129             :  *          SELECT ... WHERE x = 42 ORDER BY x, y;
     130             :  * We may as well just sort by y.  Note that because of opfamily matching,
     131             :  * this is semantically correct: we know that the equality constraint is one
     132             :  * that actually binds the variable to a single value in the terms of any
     133             :  * ordering operator that might go with the eclass.  This rule not only lets
     134             :  * us simplify (or even skip) explicit sorts, but also allows matching index
     135             :  * sort orders to a query when there are don't-care index columns.
     136             :  *
     137             :  * 2. If the new pathkey's equivalence class is the same as that of any
     138             :  * existing member of the pathkey list, then it is redundant.  Some examples:
     139             :  *          SELECT ... ORDER BY x, x;
     140             :  *          SELECT ... ORDER BY x, x DESC;
     141             :  *          SELECT ... WHERE x = y ORDER BY x, y;
     142             :  * In all these cases the second sort key cannot distinguish values that are
     143             :  * considered equal by the first, and so there's no point in using it.
     144             :  * Note in particular that we need not compare opfamily (all the opfamilies
     145             :  * of the EC have the same notion of equality) nor sort direction.
     146             :  *
     147             :  * Both the given pathkey and the list members must be canonical for this
     148             :  * to work properly, but that's okay since we no longer ever construct any
     149             :  * non-canonical pathkeys.  (Note: the notion of a pathkey *list* being
     150             :  * canonical includes the additional requirement of no redundant entries,
     151             :  * which is exactly what we are checking for here.)
     152             :  *
     153             :  * Because the equivclass.c machinery forms only one copy of any EC per query,
     154             :  * pointer comparison is enough to decide whether canonical ECs are the same.
     155             :  */
     156             : static bool
     157     1730248 : pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
     158             : {
     159     1730248 :     EquivalenceClass *new_ec = new_pathkey->pk_eclass;
     160             :     ListCell   *lc;
     161             : 
     162             :     /* Check for EC containing a constant --- unconditionally redundant */
     163     1730248 :     if (EC_MUST_BE_REDUNDANT(new_ec))
     164      229404 :         return true;
     165             : 
     166             :     /* If same EC already used in list, then redundant */
     167     1691036 :     foreach(lc, pathkeys)
     168             :     {
     169      190842 :         PathKey    *old_pathkey = (PathKey *) lfirst(lc);
     170             : 
     171      190842 :         if (new_ec == old_pathkey->pk_eclass)
     172         650 :             return true;
     173             :     }
     174             : 
     175     1500194 :     return false;
     176             : }
     177             : 
     178             : /*
     179             :  * make_pathkey_from_sortinfo
     180             :  *    Given an expression and sort-order information, create a PathKey.
     181             :  *    The result is always a "canonical" PathKey, but it might be redundant.
     182             :  *
     183             :  * If the PathKey is being generated from a SortGroupClause, sortref should be
     184             :  * the SortGroupClause's SortGroupRef; otherwise zero.
     185             :  *
     186             :  * If rel is not NULL, it identifies a specific relation we're considering
     187             :  * a path for, and indicates that child EC members for that relation can be
     188             :  * considered.  Otherwise child members are ignored.  (See the comments for
     189             :  * get_eclass_for_sort_expr.)
     190             :  *
     191             :  * create_it is true if we should create any missing EquivalenceClass
     192             :  * needed to represent the sort key.  If it's false, we return NULL if the
     193             :  * sort key isn't already present in any EquivalenceClass.
     194             :  */
     195             : static PathKey *
     196     1356360 : make_pathkey_from_sortinfo(PlannerInfo *root,
     197             :                            Expr *expr,
     198             :                            Oid opfamily,
     199             :                            Oid opcintype,
     200             :                            Oid collation,
     201             :                            bool reverse_sort,
     202             :                            bool nulls_first,
     203             :                            Index sortref,
     204             :                            Relids rel,
     205             :                            bool create_it)
     206             : {
     207             :     int16       strategy;
     208             :     Oid         equality_op;
     209             :     List       *opfamilies;
     210             :     EquivalenceClass *eclass;
     211             : 
     212     1356360 :     strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
     213             : 
     214             :     /*
     215             :      * EquivalenceClasses need to contain opfamily lists based on the family
     216             :      * membership of mergejoinable equality operators, which could belong to
     217             :      * more than one opfamily.  So we have to look up the opfamily's equality
     218             :      * operator and get its membership.
     219             :      */
     220     1356360 :     equality_op = get_opfamily_member(opfamily,
     221             :                                       opcintype,
     222             :                                       opcintype,
     223             :                                       BTEqualStrategyNumber);
     224     1356360 :     if (!OidIsValid(equality_op))   /* shouldn't happen */
     225           0 :         elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
     226             :              BTEqualStrategyNumber, opcintype, opcintype, opfamily);
     227     1356360 :     opfamilies = get_mergejoin_opfamilies(equality_op);
     228     1356360 :     if (!opfamilies)            /* certainly should find some */
     229           0 :         elog(ERROR, "could not find opfamilies for equality operator %u",
     230             :              equality_op);
     231             : 
     232             :     /* Now find or (optionally) create a matching EquivalenceClass */
     233     1356360 :     eclass = get_eclass_for_sort_expr(root, expr,
     234             :                                       opfamilies, opcintype, collation,
     235             :                                       sortref, rel, create_it);
     236             : 
     237             :     /* Fail if no EC and !create_it */
     238     1356360 :     if (!eclass)
     239      490342 :         return NULL;
     240             : 
     241             :     /* And finally we can find or create a PathKey node */
     242      866018 :     return make_canonical_pathkey(root, eclass, opfamily,
     243             :                                   strategy, nulls_first);
     244             : }
     245             : 
     246             : /*
     247             :  * make_pathkey_from_sortop
     248             :  *    Like make_pathkey_from_sortinfo, but work from a sort operator.
     249             :  *
     250             :  * This should eventually go away, but we need to restructure SortGroupClause
     251             :  * first.
     252             :  */
     253             : static PathKey *
     254       93836 : make_pathkey_from_sortop(PlannerInfo *root,
     255             :                          Expr *expr,
     256             :                          Oid ordering_op,
     257             :                          bool nulls_first,
     258             :                          Index sortref,
     259             :                          bool create_it)
     260             : {
     261             :     Oid         opfamily,
     262             :                 opcintype,
     263             :                 collation;
     264             :     int16       strategy;
     265             : 
     266             :     /* Find the operator in pg_amop --- failure shouldn't happen */
     267       93836 :     if (!get_ordering_op_properties(ordering_op,
     268             :                                     &opfamily, &opcintype, &strategy))
     269           0 :         elog(ERROR, "operator %u is not a valid ordering operator",
     270             :              ordering_op);
     271             : 
     272             :     /* Because SortGroupClause doesn't carry collation, consult the expr */
     273       93836 :     collation = exprCollation((Node *) expr);
     274             : 
     275       93836 :     return make_pathkey_from_sortinfo(root,
     276             :                                       expr,
     277             :                                       opfamily,
     278             :                                       opcintype,
     279             :                                       collation,
     280             :                                       (strategy == BTGreaterStrategyNumber),
     281             :                                       nulls_first,
     282             :                                       sortref,
     283             :                                       NULL,
     284             :                                       create_it);
     285             : }
     286             : 
     287             : 
     288             : /****************************************************************************
     289             :  *      PATHKEY COMPARISONS
     290             :  ****************************************************************************/
     291             : 
     292             : /*
     293             :  * compare_pathkeys
     294             :  *    Compare two pathkeys to see if they are equivalent, and if not whether
     295             :  *    one is "better" than the other.
     296             :  *
     297             :  *    We assume the pathkeys are canonical, and so they can be checked for
     298             :  *    equality by simple pointer comparison.
     299             :  */
     300             : PathKeysComparison
     301     8992996 : compare_pathkeys(List *keys1, List *keys2)
     302             : {
     303             :     ListCell   *key1,
     304             :                *key2;
     305             : 
     306             :     /*
     307             :      * Fall out quickly if we are passed two identical lists.  This mostly
     308             :      * catches the case where both are NIL, but that's common enough to
     309             :      * warrant the test.
     310             :      */
     311     8992996 :     if (keys1 == keys2)
     312     3515690 :         return PATHKEYS_EQUAL;
     313             : 
     314     6817966 :     forboth(key1, keys1, key2, keys2)
     315             :     {
     316     1897774 :         PathKey    *pathkey1 = (PathKey *) lfirst(key1);
     317     1897774 :         PathKey    *pathkey2 = (PathKey *) lfirst(key2);
     318             : 
     319     1897774 :         if (pathkey1 != pathkey2)
     320      557114 :             return PATHKEYS_DIFFERENT;  /* no need to keep looking */
     321             :     }
     322             : 
     323             :     /*
     324             :      * If we reached the end of only one list, the other is longer and
     325             :      * therefore not a subset.
     326             :      */
     327     4920192 :     if (key1 != NULL)
     328     3358378 :         return PATHKEYS_BETTER1;    /* key1 is longer */
     329     1561814 :     if (key2 != NULL)
     330      477486 :         return PATHKEYS_BETTER2;    /* key2 is longer */
     331     1084328 :     return PATHKEYS_EQUAL;
     332             : }
     333             : 
     334             : /*
     335             :  * pathkeys_contained_in
     336             :  *    Common special case of compare_pathkeys: we just want to know
     337             :  *    if keys2 are at least as well sorted as keys1.
     338             :  */
     339             : bool
     340     3230018 : pathkeys_contained_in(List *keys1, List *keys2)
     341             : {
     342     3230018 :     switch (compare_pathkeys(keys1, keys2))
     343             :     {
     344      798678 :         case PATHKEYS_EQUAL:
     345             :         case PATHKEYS_BETTER2:
     346      798678 :             return true;
     347     2431340 :         default:
     348     2431340 :             break;
     349             :     }
     350     2431340 :     return false;
     351             : }
     352             : 
     353             : /*
     354             :  * pathkeys_count_contained_in
     355             :  *    Same as pathkeys_contained_in, but also sets length of longest
     356             :  *    common prefix of keys1 and keys2.
     357             :  */
     358             : bool
     359      794008 : pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
     360             : {
     361      794008 :     int         n = 0;
     362             :     ListCell   *key1,
     363             :                *key2;
     364             : 
     365             :     /*
     366             :      * See if we can avoiding looping through both lists. This optimization
     367             :      * gains us several percent in planning time in a worst-case test.
     368             :      */
     369      794008 :     if (keys1 == keys2)
     370             :     {
     371       35696 :         *n_common = list_length(keys1);
     372       35696 :         return true;
     373             :     }
     374      758312 :     else if (keys1 == NIL)
     375             :     {
     376          28 :         *n_common = 0;
     377          28 :         return true;
     378             :     }
     379      758284 :     else if (keys2 == NIL)
     380             :     {
     381       63692 :         *n_common = 0;
     382       63692 :         return false;
     383             :     }
     384             : 
     385             :     /*
     386             :      * If both lists are non-empty, iterate through both to find out how many
     387             :      * items are shared.
     388             :      */
     389      920852 :     forboth(key1, keys1, key2, keys2)
     390             :     {
     391      723502 :         PathKey    *pathkey1 = (PathKey *) lfirst(key1);
     392      723502 :         PathKey    *pathkey2 = (PathKey *) lfirst(key2);
     393             : 
     394      723502 :         if (pathkey1 != pathkey2)
     395             :         {
     396      497242 :             *n_common = n;
     397      497242 :             return false;
     398             :         }
     399      226260 :         n++;
     400             :     }
     401             : 
     402             :     /* If we ended with a null value, then we've processed the whole list. */
     403      197350 :     *n_common = n;
     404      197350 :     return (key1 == NULL);
     405             : }
     406             : 
     407             : /*
     408             :  * get_cheapest_path_for_pathkeys
     409             :  *    Find the cheapest path (according to the specified criterion) that
     410             :  *    satisfies the given pathkeys and parameterization, and is parallel-safe
     411             :  *    if required.
     412             :  *    Return NULL if no such path.
     413             :  *
     414             :  * 'paths' is a list of possible paths that all generate the same relation
     415             :  * 'pathkeys' represents a required ordering (in canonical form!)
     416             :  * 'required_outer' denotes allowable outer relations for parameterized paths
     417             :  * 'cost_criterion' is STARTUP_COST or TOTAL_COST
     418             :  * 'require_parallel_safe' causes us to consider only parallel-safe paths
     419             :  */
     420             : Path *
     421      677896 : get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
     422             :                                Relids required_outer,
     423             :                                CostSelector cost_criterion,
     424             :                                bool require_parallel_safe)
     425             : {
     426      677896 :     Path       *matched_path = NULL;
     427             :     ListCell   *l;
     428             : 
     429     2384490 :     foreach(l, paths)
     430             :     {
     431     1706594 :         Path       *path = (Path *) lfirst(l);
     432             : 
     433             :         /* If required, reject paths that are not parallel-safe */
     434     1706594 :         if (require_parallel_safe && !path->parallel_safe)
     435         264 :             continue;
     436             : 
     437             :         /*
     438             :          * Since cost comparison is a lot cheaper than pathkey comparison, do
     439             :          * that first.  (XXX is that still true?)
     440             :          */
     441     1776848 :         if (matched_path != NULL &&
     442       70518 :             compare_path_costs(matched_path, path, cost_criterion) <= 0)
     443       60550 :             continue;
     444             : 
     445     2369012 :         if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
     446      723232 :             bms_is_subset(PATH_REQ_OUTER(path), required_outer))
     447      442528 :             matched_path = path;
     448             :     }
     449      677896 :     return matched_path;
     450             : }
     451             : 
     452             : /*
     453             :  * get_cheapest_fractional_path_for_pathkeys
     454             :  *    Find the cheapest path (for retrieving a specified fraction of all
     455             :  *    the tuples) that satisfies the given pathkeys and parameterization.
     456             :  *    Return NULL if no such path.
     457             :  *
     458             :  * See compare_fractional_path_costs() for the interpretation of the fraction
     459             :  * parameter.
     460             :  *
     461             :  * 'paths' is a list of possible paths that all generate the same relation
     462             :  * 'pathkeys' represents a required ordering (in canonical form!)
     463             :  * 'required_outer' denotes allowable outer relations for parameterized paths
     464             :  * 'fraction' is the fraction of the total tuples expected to be retrieved
     465             :  */
     466             : Path *
     467        1636 : get_cheapest_fractional_path_for_pathkeys(List *paths,
     468             :                                           List *pathkeys,
     469             :                                           Relids required_outer,
     470             :                                           double fraction)
     471             : {
     472        1636 :     Path       *matched_path = NULL;
     473             :     ListCell   *l;
     474             : 
     475        4488 :     foreach(l, paths)
     476             :     {
     477        2852 :         Path       *path = (Path *) lfirst(l);
     478             : 
     479             :         /*
     480             :          * Since cost comparison is a lot cheaper than pathkey comparison, do
     481             :          * that first.  (XXX is that still true?)
     482             :          */
     483        3222 :         if (matched_path != NULL &&
     484         370 :             compare_fractional_path_costs(matched_path, path, fraction) <= 0)
     485         184 :             continue;
     486             : 
     487        3784 :         if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
     488        1116 :             bms_is_subset(PATH_REQ_OUTER(path), required_outer))
     489        1076 :             matched_path = path;
     490             :     }
     491        1636 :     return matched_path;
     492             : }
     493             : 
     494             : 
     495             : /*
     496             :  * get_cheapest_parallel_safe_total_inner
     497             :  *    Find the unparameterized parallel-safe path with the least total cost.
     498             :  */
     499             : Path *
     500       47964 : get_cheapest_parallel_safe_total_inner(List *paths)
     501             : {
     502             :     ListCell   *l;
     503             : 
     504       54286 :     foreach(l, paths)
     505             :     {
     506       53544 :         Path       *innerpath = (Path *) lfirst(l);
     507             : 
     508       53544 :         if (innerpath->parallel_safe &&
     509       51698 :             bms_is_empty(PATH_REQ_OUTER(innerpath)))
     510       47222 :             return innerpath;
     511             :     }
     512             : 
     513         742 :     return NULL;
     514             : }
     515             : 
     516             : /****************************************************************************
     517             :  *      NEW PATHKEY FORMATION
     518             :  ****************************************************************************/
     519             : 
     520             : /*
     521             :  * build_index_pathkeys
     522             :  *    Build a pathkeys list that describes the ordering induced by an index
     523             :  *    scan using the given index.  (Note that an unordered index doesn't
     524             :  *    induce any ordering, so we return NIL.)
     525             :  *
     526             :  * If 'scandir' is BackwardScanDirection, build pathkeys representing a
     527             :  * backwards scan of the index.
     528             :  *
     529             :  * We iterate only key columns of covering indexes, since non-key columns
     530             :  * don't influence index ordering.  The result is canonical, meaning that
     531             :  * redundant pathkeys are removed; it may therefore have fewer entries than
     532             :  * there are key columns in the index.
     533             :  *
     534             :  * Another reason for stopping early is that we may be able to tell that
     535             :  * an index column's sort order is uninteresting for this query.  However,
     536             :  * that test is just based on the existence of an EquivalenceClass and not
     537             :  * on position in pathkey lists, so it's not complete.  Caller should call
     538             :  * truncate_useless_pathkeys() to possibly remove more pathkeys.
     539             :  */
     540             : List *
     541      972560 : build_index_pathkeys(PlannerInfo *root,
     542             :                      IndexOptInfo *index,
     543             :                      ScanDirection scandir)
     544             : {
     545      972560 :     List       *retval = NIL;
     546             :     ListCell   *lc;
     547             :     int         i;
     548             : 
     549      972560 :     if (index->sortopfamily == NULL)
     550           0 :         return NIL;             /* non-orderable index */
     551             : 
     552      972560 :     i = 0;
     553     1714504 :     foreach(lc, index->indextlist)
     554             :     {
     555     1217696 :         TargetEntry *indextle = (TargetEntry *) lfirst(lc);
     556             :         Expr       *indexkey;
     557             :         bool        reverse_sort;
     558             :         bool        nulls_first;
     559             :         PathKey    *cpathkey;
     560             : 
     561             :         /*
     562             :          * INCLUDE columns are stored in index unordered, so they don't
     563             :          * support ordered index scan.
     564             :          */
     565     1217696 :         if (i >= index->nkeycolumns)
     566           0 :             break;
     567             : 
     568             :         /* We assume we don't need to make a copy of the tlist item */
     569     1217696 :         indexkey = indextle->expr;
     570             : 
     571     1217696 :         if (ScanDirectionIsBackward(scandir))
     572             :         {
     573      608848 :             reverse_sort = !index->reverse_sort[i];
     574      608848 :             nulls_first = !index->nulls_first[i];
     575             :         }
     576             :         else
     577             :         {
     578      608848 :             reverse_sort = index->reverse_sort[i];
     579      608848 :             nulls_first = index->nulls_first[i];
     580             :         }
     581             : 
     582             :         /*
     583             :          * OK, try to make a canonical pathkey for this sort key.
     584             :          */
     585     1217696 :         cpathkey = make_pathkey_from_sortinfo(root,
     586             :                                               indexkey,
     587     1217696 :                                               index->sortopfamily[i],
     588     1217696 :                                               index->opcintype[i],
     589     1217696 :                                               index->indexcollations[i],
     590             :                                               reverse_sort,
     591             :                                               nulls_first,
     592             :                                               0,
     593     1217696 :                                               index->rel->relids,
     594             :                                               false);
     595             : 
     596     1217696 :         if (cpathkey)
     597             :         {
     598             :             /*
     599             :              * We found the sort key in an EquivalenceClass, so it's relevant
     600             :              * for this query.  Add it to list, unless it's redundant.
     601             :              */
     602      741836 :             if (!pathkey_is_redundant(cpathkey, retval))
     603      532892 :                 retval = lappend(retval, cpathkey);
     604             :         }
     605             :         else
     606             :         {
     607             :             /*
     608             :              * Boolean index keys might be redundant even if they do not
     609             :              * appear in an EquivalenceClass, because of our special treatment
     610             :              * of boolean equality conditions --- see the comment for
     611             :              * indexcol_is_bool_constant_for_query().  If that applies, we can
     612             :              * continue to examine lower-order index columns.  Otherwise, the
     613             :              * sort key is not an interesting sort order for this query, so we
     614             :              * should stop considering index columns; any lower-order sort
     615             :              * keys won't be useful either.
     616             :              */
     617      475860 :             if (!indexcol_is_bool_constant_for_query(root, index, i))
     618      475752 :                 break;
     619             :         }
     620             : 
     621      741944 :         i++;
     622             :     }
     623             : 
     624      972560 :     return retval;
     625             : }
     626             : 
     627             : /*
     628             :  * partkey_is_bool_constant_for_query
     629             :  *
     630             :  * If a partition key column is constrained to have a constant value by the
     631             :  * query's WHERE conditions, then it's irrelevant for sort-order
     632             :  * considerations.  Usually that means we have a restriction clause
     633             :  * WHERE partkeycol = constant, which gets turned into an EquivalenceClass
     634             :  * containing a constant, which is recognized as redundant by
     635             :  * build_partition_pathkeys().  But if the partition key column is a
     636             :  * boolean variable (or expression), then we are not going to see such a
     637             :  * WHERE clause, because expression preprocessing will have simplified it
     638             :  * to "WHERE partkeycol" or "WHERE NOT partkeycol".  So we are not going
     639             :  * to have a matching EquivalenceClass (unless the query also contains
     640             :  * "ORDER BY partkeycol").  To allow such cases to work the same as they would
     641             :  * for non-boolean values, this function is provided to detect whether the
     642             :  * specified partition key column matches a boolean restriction clause.
     643             :  */
     644             : static bool
     645       14128 : partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
     646             : {
     647       14128 :     PartitionScheme partscheme = partrel->part_scheme;
     648             :     ListCell   *lc;
     649             : 
     650             :     /*
     651             :      * If the partkey isn't boolean, we can't possibly get a match.
     652             :      *
     653             :      * Partitioning currently can only use built-in AMs, so checking for
     654             :      * built-in boolean opfamilies is good enough.
     655             :      */
     656       14128 :     if (!IsBuiltinBooleanOpfamily(partscheme->partopfamily[partkeycol]))
     657       13792 :         return false;
     658             : 
     659             :     /* Check each restriction clause for the partitioned rel */
     660         456 :     foreach(lc, partrel->baserestrictinfo)
     661             :     {
     662         360 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
     663             : 
     664             :         /* Ignore pseudoconstant quals, they won't match */
     665         360 :         if (rinfo->pseudoconstant)
     666           0 :             continue;
     667             : 
     668             :         /* See if we can match the clause's expression to the partkey column */
     669         360 :         if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
     670         240 :             return true;
     671             :     }
     672             : 
     673          96 :     return false;
     674             : }
     675             : 
     676             : /*
     677             :  * matches_boolean_partition_clause
     678             :  *      Determine if the boolean clause described by rinfo matches
     679             :  *      partrel's partkeycol-th partition key column.
     680             :  *
     681             :  * "Matches" can be either an exact match (equivalent to partkey = true),
     682             :  * or a NOT above an exact match (equivalent to partkey = false).
     683             :  */
     684             : static bool
     685         360 : matches_boolean_partition_clause(RestrictInfo *rinfo,
     686             :                                  RelOptInfo *partrel, int partkeycol)
     687             : {
     688         360 :     Node       *clause = (Node *) rinfo->clause;
     689         360 :     Node       *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
     690             : 
     691             :     /* Direct match? */
     692         360 :     if (equal(partexpr, clause))
     693         120 :         return true;
     694             :     /* NOT clause? */
     695         240 :     else if (is_notclause(clause))
     696             :     {
     697         144 :         Node       *arg = (Node *) get_notclausearg((Expr *) clause);
     698             : 
     699         144 :         if (equal(partexpr, arg))
     700         120 :             return true;
     701             :     }
     702             : 
     703         120 :     return false;
     704             : }
     705             : 
     706             : /*
     707             :  * build_partition_pathkeys
     708             :  *    Build a pathkeys list that describes the ordering induced by the
     709             :  *    partitions of partrel, under either forward or backward scan
     710             :  *    as per scandir.
     711             :  *
     712             :  * Caller must have checked that the partitions are properly ordered,
     713             :  * as detected by partitions_are_ordered().
     714             :  *
     715             :  * Sets *partialkeys to true if pathkeys were only built for a prefix of the
     716             :  * partition key, or false if the pathkeys include all columns of the
     717             :  * partition key.
     718             :  */
     719             : List *
     720       42452 : build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
     721             :                          ScanDirection scandir, bool *partialkeys)
     722             : {
     723       42452 :     List       *retval = NIL;
     724       42452 :     PartitionScheme partscheme = partrel->part_scheme;
     725             :     int         i;
     726             : 
     727             :     Assert(partscheme != NULL);
     728             :     Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
     729             :     /* For now, we can only cope with baserels */
     730             :     Assert(IS_SIMPLE_REL(partrel));
     731             : 
     732       72780 :     for (i = 0; i < partscheme->partnatts; i++)
     733             :     {
     734             :         PathKey    *cpathkey;
     735       44216 :         Expr       *keyCol = (Expr *) linitial(partrel->partexprs[i]);
     736             : 
     737             :         /*
     738             :          * Try to make a canonical pathkey for this partkey.
     739             :          *
     740             :          * We assume the PartitionDesc lists any NULL partition last, so we
     741             :          * treat the scan like a NULLS LAST index: we have nulls_first for
     742             :          * backwards scan only.
     743             :          */
     744       44216 :         cpathkey = make_pathkey_from_sortinfo(root,
     745             :                                               keyCol,
     746       44216 :                                               partscheme->partopfamily[i],
     747       44216 :                                               partscheme->partopcintype[i],
     748       44216 :                                               partscheme->partcollation[i],
     749             :                                               ScanDirectionIsBackward(scandir),
     750             :                                               ScanDirectionIsBackward(scandir),
     751             :                                               0,
     752             :                                               partrel->relids,
     753             :                                               false);
     754             : 
     755             : 
     756       44216 :         if (cpathkey)
     757             :         {
     758             :             /*
     759             :              * We found the sort key in an EquivalenceClass, so it's relevant
     760             :              * for this query.  Add it to list, unless it's redundant.
     761             :              */
     762       30088 :             if (!pathkey_is_redundant(cpathkey, retval))
     763       10720 :                 retval = lappend(retval, cpathkey);
     764             :         }
     765             :         else
     766             :         {
     767             :             /*
     768             :              * Boolean partition keys might be redundant even if they do not
     769             :              * appear in an EquivalenceClass, because of our special treatment
     770             :              * of boolean equality conditions --- see the comment for
     771             :              * partkey_is_bool_constant_for_query().  If that applies, we can
     772             :              * continue to examine lower-order partition keys.  Otherwise, the
     773             :              * sort key is not an interesting sort order for this query, so we
     774             :              * should stop considering partition columns; any lower-order sort
     775             :              * keys won't be useful either.
     776             :              */
     777       14128 :             if (!partkey_is_bool_constant_for_query(partrel, i))
     778             :             {
     779       13888 :                 *partialkeys = true;
     780       13888 :                 return retval;
     781             :             }
     782             :         }
     783             :     }
     784             : 
     785       28564 :     *partialkeys = false;
     786       28564 :     return retval;
     787             : }
     788             : 
     789             : /*
     790             :  * build_expression_pathkey
     791             :  *    Build a pathkeys list that describes an ordering by a single expression
     792             :  *    using the given sort operator.
     793             :  *
     794             :  * expr and rel are as for make_pathkey_from_sortinfo.
     795             :  * We induce the other arguments assuming default sort order for the operator.
     796             :  *
     797             :  * Similarly to make_pathkey_from_sortinfo, the result is NIL if create_it
     798             :  * is false and the expression isn't already in some EquivalenceClass.
     799             :  */
     800             : List *
     801         612 : build_expression_pathkey(PlannerInfo *root,
     802             :                          Expr *expr,
     803             :                          Oid opno,
     804             :                          Relids rel,
     805             :                          bool create_it)
     806             : {
     807             :     List       *pathkeys;
     808             :     Oid         opfamily,
     809             :                 opcintype;
     810             :     int16       strategy;
     811             :     PathKey    *cpathkey;
     812             : 
     813             :     /* Find the operator in pg_amop --- failure shouldn't happen */
     814         612 :     if (!get_ordering_op_properties(opno,
     815             :                                     &opfamily, &opcintype, &strategy))
     816           0 :         elog(ERROR, "operator %u is not a valid ordering operator",
     817             :              opno);
     818             : 
     819         612 :     cpathkey = make_pathkey_from_sortinfo(root,
     820             :                                           expr,
     821             :                                           opfamily,
     822             :                                           opcintype,
     823             :                                           exprCollation((Node *) expr),
     824             :                                           (strategy == BTGreaterStrategyNumber),
     825             :                                           (strategy == BTGreaterStrategyNumber),
     826             :                                           0,
     827             :                                           rel,
     828             :                                           create_it);
     829             : 
     830         612 :     if (cpathkey)
     831         258 :         pathkeys = list_make1(cpathkey);
     832             :     else
     833         354 :         pathkeys = NIL;
     834             : 
     835         612 :     return pathkeys;
     836             : }
     837             : 
     838             : /*
     839             :  * convert_subquery_pathkeys
     840             :  *    Build a pathkeys list that describes the ordering of a subquery's
     841             :  *    result, in the terms of the outer query.  This is essentially a
     842             :  *    task of conversion.
     843             :  *
     844             :  * 'rel': outer query's RelOptInfo for the subquery relation.
     845             :  * 'subquery_pathkeys': the subquery's output pathkeys, in its terms.
     846             :  * 'subquery_tlist': the subquery's output targetlist, in its terms.
     847             :  *
     848             :  * We intentionally don't do truncate_useless_pathkeys() here, because there
     849             :  * are situations where seeing the raw ordering of the subquery is helpful.
     850             :  * For example, if it returns ORDER BY x DESC, that may prompt us to
     851             :  * construct a mergejoin using DESC order rather than ASC order; but the
     852             :  * right_merge_direction heuristic would have us throw the knowledge away.
     853             :  */
     854             : List *
     855        6996 : convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
     856             :                           List *subquery_pathkeys,
     857             :                           List *subquery_tlist)
     858             : {
     859        6996 :     List       *retval = NIL;
     860        6996 :     int         retvallen = 0;
     861        6996 :     int         outer_query_keys = list_length(root->query_pathkeys);
     862             :     ListCell   *i;
     863             : 
     864        7714 :     foreach(i, subquery_pathkeys)
     865             :     {
     866        1994 :         PathKey    *sub_pathkey = (PathKey *) lfirst(i);
     867        1994 :         EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
     868        1994 :         PathKey    *best_pathkey = NULL;
     869             : 
     870        1994 :         if (sub_eclass->ec_has_volatile)
     871             :         {
     872             :             /*
     873             :              * If the sub_pathkey's EquivalenceClass is volatile, then it must
     874             :              * have come from an ORDER BY clause, and we have to match it to
     875             :              * that same targetlist entry.
     876             :              */
     877             :             TargetEntry *tle;
     878             :             Var        *outer_var;
     879             : 
     880          24 :             if (sub_eclass->ec_sortref == 0) /* can't happen */
     881           0 :                 elog(ERROR, "volatile EquivalenceClass has no sortref");
     882          24 :             tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
     883             :             Assert(tle);
     884             :             /* Is TLE actually available to the outer query? */
     885          24 :             outer_var = find_var_for_subquery_tle(rel, tle);
     886          24 :             if (outer_var)
     887             :             {
     888             :                 /* We can represent this sub_pathkey */
     889             :                 EquivalenceMember *sub_member;
     890             :                 EquivalenceClass *outer_ec;
     891             : 
     892             :                 Assert(list_length(sub_eclass->ec_members) == 1);
     893           0 :                 sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
     894             : 
     895             :                 /*
     896             :                  * Note: it might look funny to be setting sortref = 0 for a
     897             :                  * reference to a volatile sub_eclass.  However, the
     898             :                  * expression is *not* volatile in the outer query: it's just
     899             :                  * a Var referencing whatever the subquery emitted. (IOW, the
     900             :                  * outer query isn't going to re-execute the volatile
     901             :                  * expression itself.)  So this is okay.
     902             :                  */
     903             :                 outer_ec =
     904           0 :                     get_eclass_for_sort_expr(root,
     905             :                                              (Expr *) outer_var,
     906             :                                              sub_eclass->ec_opfamilies,
     907             :                                              sub_member->em_datatype,
     908             :                                              sub_eclass->ec_collation,
     909             :                                              0,
     910             :                                              rel->relids,
     911             :                                              false);
     912             : 
     913             :                 /*
     914             :                  * If we don't find a matching EC, sub-pathkey isn't
     915             :                  * interesting to the outer query
     916             :                  */
     917           0 :                 if (outer_ec)
     918             :                     best_pathkey =
     919           0 :                         make_canonical_pathkey(root,
     920             :                                                outer_ec,
     921             :                                                sub_pathkey->pk_opfamily,
     922             :                                                sub_pathkey->pk_strategy,
     923           0 :                                                sub_pathkey->pk_nulls_first);
     924             :             }
     925             :         }
     926             :         else
     927             :         {
     928             :             /*
     929             :              * Otherwise, the sub_pathkey's EquivalenceClass could contain
     930             :              * multiple elements (representing knowledge that multiple items
     931             :              * are effectively equal).  Each element might match none, one, or
     932             :              * more of the output columns that are visible to the outer query.
     933             :              * This means we may have multiple possible representations of the
     934             :              * sub_pathkey in the context of the outer query.  Ideally we
     935             :              * would generate them all and put them all into an EC of the
     936             :              * outer query, thereby propagating equality knowledge up to the
     937             :              * outer query.  Right now we cannot do so, because the outer
     938             :              * query's EquivalenceClasses are already frozen when this is
     939             :              * called. Instead we prefer the one that has the highest "score"
     940             :              * (number of EC peers, plus one if it matches the outer
     941             :              * query_pathkeys). This is the most likely to be useful in the
     942             :              * outer query.
     943             :              */
     944        1970 :             int         best_score = -1;
     945             :             ListCell   *j;
     946             : 
     947        4150 :             foreach(j, sub_eclass->ec_members)
     948             :             {
     949        2180 :                 EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
     950        2180 :                 Expr       *sub_expr = sub_member->em_expr;
     951        2180 :                 Oid         sub_expr_type = sub_member->em_datatype;
     952        2180 :                 Oid         sub_expr_coll = sub_eclass->ec_collation;
     953             :                 ListCell   *k;
     954             : 
     955        2180 :                 if (sub_member->em_is_child)
     956         158 :                     continue;   /* ignore children here */
     957             : 
     958       13246 :                 foreach(k, subquery_tlist)
     959             :                 {
     960       11224 :                     TargetEntry *tle = (TargetEntry *) lfirst(k);
     961             :                     Var        *outer_var;
     962             :                     Expr       *tle_expr;
     963             :                     EquivalenceClass *outer_ec;
     964             :                     PathKey    *outer_pk;
     965             :                     int         score;
     966             : 
     967             :                     /* Is TLE actually available to the outer query? */
     968       11224 :                     outer_var = find_var_for_subquery_tle(rel, tle);
     969       11224 :                     if (!outer_var)
     970        5830 :                         continue;
     971             : 
     972             :                     /*
     973             :                      * The targetlist entry is considered to match if it
     974             :                      * matches after sort-key canonicalization.  That is
     975             :                      * needed since the sub_expr has been through the same
     976             :                      * process.
     977             :                      */
     978        5394 :                     tle_expr = canonicalize_ec_expression(tle->expr,
     979             :                                                           sub_expr_type,
     980             :                                                           sub_expr_coll);
     981        5394 :                     if (!equal(tle_expr, sub_expr))
     982        4062 :                         continue;
     983             : 
     984             :                     /* See if we have a matching EC for the TLE */
     985        1332 :                     outer_ec = get_eclass_for_sort_expr(root,
     986             :                                                         (Expr *) outer_var,
     987             :                                                         sub_eclass->ec_opfamilies,
     988             :                                                         sub_expr_type,
     989             :                                                         sub_expr_coll,
     990             :                                                         0,
     991             :                                                         rel->relids,
     992             :                                                         false);
     993             : 
     994             :                     /*
     995             :                      * If we don't find a matching EC, this sub-pathkey isn't
     996             :                      * interesting to the outer query
     997             :                      */
     998        1332 :                     if (!outer_ec)
     999         614 :                         continue;
    1000             : 
    1001         718 :                     outer_pk = make_canonical_pathkey(root,
    1002             :                                                       outer_ec,
    1003             :                                                       sub_pathkey->pk_opfamily,
    1004             :                                                       sub_pathkey->pk_strategy,
    1005         718 :                                                       sub_pathkey->pk_nulls_first);
    1006             :                     /* score = # of equivalence peers */
    1007         718 :                     score = list_length(outer_ec->ec_members) - 1;
    1008             :                     /* +1 if it matches the proper query_pathkeys item */
    1009        1280 :                     if (retvallen < outer_query_keys &&
    1010         562 :                         list_nth(root->query_pathkeys, retvallen) == outer_pk)
    1011         456 :                         score++;
    1012         718 :                     if (score > best_score)
    1013             :                     {
    1014         718 :                         best_pathkey = outer_pk;
    1015         718 :                         best_score = score;
    1016             :                     }
    1017             :                 }
    1018             :             }
    1019             :         }
    1020             : 
    1021             :         /*
    1022             :          * If we couldn't find a representation of this sub_pathkey, we're
    1023             :          * done (we can't use the ones to its right, either).
    1024             :          */
    1025        1994 :         if (!best_pathkey)
    1026        1276 :             break;
    1027             : 
    1028             :         /*
    1029             :          * Eliminate redundant ordering info; could happen if outer query
    1030             :          * equivalences subquery keys...
    1031             :          */
    1032         718 :         if (!pathkey_is_redundant(best_pathkey, retval))
    1033             :         {
    1034         718 :             retval = lappend(retval, best_pathkey);
    1035         718 :             retvallen++;
    1036             :         }
    1037             :     }
    1038             : 
    1039        6996 :     return retval;
    1040             : }
    1041             : 
    1042             : /*
    1043             :  * find_var_for_subquery_tle
    1044             :  *
    1045             :  * If the given subquery tlist entry is due to be emitted by the subquery's
    1046             :  * scan node, return a Var for it, else return NULL.
    1047             :  *
    1048             :  * We need this to ensure that we don't return pathkeys describing values
    1049             :  * that are unavailable above the level of the subquery scan.
    1050             :  */
    1051             : static Var *
    1052       11248 : find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
    1053             : {
    1054             :     ListCell   *lc;
    1055             : 
    1056             :     /* If the TLE is resjunk, it's certainly not visible to the outer query */
    1057       11248 :     if (tle->resjunk)
    1058           0 :         return NULL;
    1059             : 
    1060             :     /* Search the rel's targetlist to see what it will return */
    1061       44790 :     foreach(lc, rel->reltarget->exprs)
    1062             :     {
    1063       38936 :         Var        *var = (Var *) lfirst(lc);
    1064             : 
    1065             :         /* Ignore placeholders */
    1066       38936 :         if (!IsA(var, Var))
    1067          24 :             continue;
    1068             :         Assert(var->varno == rel->relid);
    1069             : 
    1070             :         /* If we find a Var referencing this TLE, we're good */
    1071       38912 :         if (var->varattno == tle->resno)
    1072        5394 :             return copyObject(var); /* Make a copy for safety */
    1073             :     }
    1074        5854 :     return NULL;
    1075             : }
    1076             : 
    1077             : /*
    1078             :  * build_join_pathkeys
    1079             :  *    Build the path keys for a join relation constructed by mergejoin or
    1080             :  *    nestloop join.  This is normally the same as the outer path's keys.
    1081             :  *
    1082             :  *    EXCEPTION: in a FULL, RIGHT or RIGHT_ANTI join, we cannot treat the
    1083             :  *    result as having the outer path's path keys, because null lefthand rows
    1084             :  *    may be inserted at random points.  It must be treated as unsorted.
    1085             :  *
    1086             :  *    We truncate away any pathkeys that are uninteresting for higher joins.
    1087             :  *
    1088             :  * 'joinrel' is the join relation that paths are being formed for
    1089             :  * 'jointype' is the join type (inner, left, full, etc)
    1090             :  * 'outer_pathkeys' is the list of the current outer path's path keys
    1091             :  *
    1092             :  * Returns the list of new path keys.
    1093             :  */
    1094             : List *
    1095     1431990 : build_join_pathkeys(PlannerInfo *root,
    1096             :                     RelOptInfo *joinrel,
    1097             :                     JoinType jointype,
    1098             :                     List *outer_pathkeys)
    1099             : {
    1100     1431990 :     if (jointype == JOIN_FULL ||
    1101     1184560 :         jointype == JOIN_RIGHT ||
    1102             :         jointype == JOIN_RIGHT_ANTI)
    1103      260948 :         return NIL;
    1104             : 
    1105             :     /*
    1106             :      * This used to be quite a complex bit of code, but now that all pathkey
    1107             :      * sublists start out life canonicalized, we don't have to do a darn thing
    1108             :      * here!
    1109             :      *
    1110             :      * We do, however, need to truncate the pathkeys list, since it may
    1111             :      * contain pathkeys that were useful for forming this joinrel but are
    1112             :      * uninteresting to higher levels.
    1113             :      */
    1114     1171042 :     return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
    1115             : }
    1116             : 
    1117             : /****************************************************************************
    1118             :  *      PATHKEYS AND SORT CLAUSES
    1119             :  ****************************************************************************/
    1120             : 
    1121             : /*
    1122             :  * make_pathkeys_for_sortclauses
    1123             :  *      Generate a pathkeys list that represents the sort order specified
    1124             :  *      by a list of SortGroupClauses
    1125             :  *
    1126             :  * The resulting PathKeys are always in canonical form.  (Actually, there
    1127             :  * is no longer any code anywhere that creates non-canonical PathKeys.)
    1128             :  *
    1129             :  * 'sortclauses' is a list of SortGroupClause nodes
    1130             :  * 'tlist' is the targetlist to find the referenced tlist entries in
    1131             :  */
    1132             : List *
    1133      457910 : make_pathkeys_for_sortclauses(PlannerInfo *root,
    1134             :                               List *sortclauses,
    1135             :                               List *tlist)
    1136             : {
    1137             :     List       *result;
    1138             :     bool        sortable;
    1139             : 
    1140      457910 :     result = make_pathkeys_for_sortclauses_extended(root,
    1141             :                                                     &sortclauses,
    1142             :                                                     tlist,
    1143             :                                                     false,
    1144             :                                                     &sortable);
    1145             :     /* It's caller error if not all clauses were sortable */
    1146             :     Assert(sortable);
    1147      457910 :     return result;
    1148             : }
    1149             : 
    1150             : /*
    1151             :  * make_pathkeys_for_sortclauses_extended
    1152             :  *      Generate a pathkeys list that represents the sort order specified
    1153             :  *      by a list of SortGroupClauses
    1154             :  *
    1155             :  * The comments for make_pathkeys_for_sortclauses apply here too. In addition:
    1156             :  *
    1157             :  * If remove_redundant is true, then any sort clauses that are found to
    1158             :  * give rise to redundant pathkeys are removed from the sortclauses list
    1159             :  * (which therefore must be pass-by-reference in this version).
    1160             :  *
    1161             :  * *sortable is set to true if all the sort clauses are in fact sortable.
    1162             :  * If any are not, they are ignored except for setting *sortable false.
    1163             :  * (In that case, the output pathkey list isn't really useful.  However,
    1164             :  * we process the whole sortclauses list anyway, because it's still valid
    1165             :  * to remove any clauses that can be proven redundant via the eclass logic.
    1166             :  * Even though we'll have to hash in that case, we might as well not hash
    1167             :  * redundant columns.)
    1168             :  */
    1169             : List *
    1170      465844 : make_pathkeys_for_sortclauses_extended(PlannerInfo *root,
    1171             :                                        List **sortclauses,
    1172             :                                        List *tlist,
    1173             :                                        bool remove_redundant,
    1174             :                                        bool *sortable)
    1175             : {
    1176      465844 :     List       *pathkeys = NIL;
    1177             :     ListCell   *l;
    1178             : 
    1179      465844 :     *sortable = true;
    1180      559686 :     foreach(l, *sortclauses)
    1181             :     {
    1182       93842 :         SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
    1183             :         Expr       *sortkey;
    1184             :         PathKey    *pathkey;
    1185             : 
    1186       93842 :         sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
    1187       93842 :         if (!OidIsValid(sortcl->sortop))
    1188             :         {
    1189           6 :             *sortable = false;
    1190           6 :             continue;
    1191             :         }
    1192       93836 :         pathkey = make_pathkey_from_sortop(root,
    1193             :                                            sortkey,
    1194             :                                            sortcl->sortop,
    1195       93836 :                                            sortcl->nulls_first,
    1196             :                                            sortcl->tleSortGroupRef,
    1197             :                                            true);
    1198             : 
    1199             :         /* Canonical form eliminates redundant ordering keys */
    1200       93836 :         if (!pathkey_is_redundant(pathkey, pathkeys))
    1201       92406 :             pathkeys = lappend(pathkeys, pathkey);
    1202        1430 :         else if (remove_redundant)
    1203         616 :             *sortclauses = foreach_delete_current(*sortclauses, l);
    1204             :     }
    1205      465844 :     return pathkeys;
    1206             : }
    1207             : 
    1208             : /****************************************************************************
    1209             :  *      PATHKEYS AND MERGECLAUSES
    1210             :  ****************************************************************************/
    1211             : 
    1212             : /*
    1213             :  * initialize_mergeclause_eclasses
    1214             :  *      Set the EquivalenceClass links in a mergeclause restrictinfo.
    1215             :  *
    1216             :  * RestrictInfo contains fields in which we may cache pointers to
    1217             :  * EquivalenceClasses for the left and right inputs of the mergeclause.
    1218             :  * (If the mergeclause is a true equivalence clause these will be the
    1219             :  * same EquivalenceClass, otherwise not.)  If the mergeclause is either
    1220             :  * used to generate an EquivalenceClass, or derived from an EquivalenceClass,
    1221             :  * then it's easy to set up the left_ec and right_ec members --- otherwise,
    1222             :  * this function should be called to set them up.  We will generate new
    1223             :  * EquivalenceClauses if necessary to represent the mergeclause's left and
    1224             :  * right sides.
    1225             :  *
    1226             :  * Note this is called before EC merging is complete, so the links won't
    1227             :  * necessarily point to canonical ECs.  Before they are actually used for
    1228             :  * anything, update_mergeclause_eclasses must be called to ensure that
    1229             :  * they've been updated to point to canonical ECs.
    1230             :  */
    1231             : void
    1232       49308 : initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
    1233             : {
    1234       49308 :     Expr       *clause = restrictinfo->clause;
    1235             :     Oid         lefttype,
    1236             :                 righttype;
    1237             : 
    1238             :     /* Should be a mergeclause ... */
    1239             :     Assert(restrictinfo->mergeopfamilies != NIL);
    1240             :     /* ... with links not yet set */
    1241             :     Assert(restrictinfo->left_ec == NULL);
    1242             :     Assert(restrictinfo->right_ec == NULL);
    1243             : 
    1244             :     /* Need the declared input types of the operator */
    1245       49308 :     op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
    1246             : 
    1247             :     /* Find or create a matching EquivalenceClass for each side */
    1248       49308 :     restrictinfo->left_ec =
    1249       49308 :         get_eclass_for_sort_expr(root,
    1250       49308 :                                  (Expr *) get_leftop(clause),
    1251             :                                  restrictinfo->mergeopfamilies,
    1252             :                                  lefttype,
    1253             :                                  ((OpExpr *) clause)->inputcollid,
    1254             :                                  0,
    1255             :                                  NULL,
    1256             :                                  true);
    1257       49308 :     restrictinfo->right_ec =
    1258       49308 :         get_eclass_for_sort_expr(root,
    1259       49308 :                                  (Expr *) get_rightop(clause),
    1260             :                                  restrictinfo->mergeopfamilies,
    1261             :                                  righttype,
    1262             :                                  ((OpExpr *) clause)->inputcollid,
    1263             :                                  0,
    1264             :                                  NULL,
    1265             :                                  true);
    1266       49308 : }
    1267             : 
    1268             : /*
    1269             :  * update_mergeclause_eclasses
    1270             :  *      Make the cached EquivalenceClass links valid in a mergeclause
    1271             :  *      restrictinfo.
    1272             :  *
    1273             :  * These pointers should have been set by process_equivalence or
    1274             :  * initialize_mergeclause_eclasses, but they might have been set to
    1275             :  * non-canonical ECs that got merged later.  Chase up to the canonical
    1276             :  * merged parent if so.
    1277             :  */
    1278             : void
    1279     3702116 : update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
    1280             : {
    1281             :     /* Should be a merge clause ... */
    1282             :     Assert(restrictinfo->mergeopfamilies != NIL);
    1283             :     /* ... with pointers already set */
    1284             :     Assert(restrictinfo->left_ec != NULL);
    1285             :     Assert(restrictinfo->right_ec != NULL);
    1286             : 
    1287             :     /* Chase up to the top as needed */
    1288     3702116 :     while (restrictinfo->left_ec->ec_merged)
    1289           0 :         restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
    1290     3702116 :     while (restrictinfo->right_ec->ec_merged)
    1291           0 :         restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
    1292     3702116 : }
    1293             : 
    1294             : /*
    1295             :  * find_mergeclauses_for_outer_pathkeys
    1296             :  *    This routine attempts to find a list of mergeclauses that can be
    1297             :  *    used with a specified ordering for the join's outer relation.
    1298             :  *    If successful, it returns a list of mergeclauses.
    1299             :  *
    1300             :  * 'pathkeys' is a pathkeys list showing the ordering of an outer-rel path.
    1301             :  * 'restrictinfos' is a list of mergejoinable restriction clauses for the
    1302             :  *          join relation being formed, in no particular order.
    1303             :  *
    1304             :  * The restrictinfos must be marked (via outer_is_left) to show which side
    1305             :  * of each clause is associated with the current outer path.  (See
    1306             :  * select_mergejoin_clauses())
    1307             :  *
    1308             :  * The result is NIL if no merge can be done, else a maximal list of
    1309             :  * usable mergeclauses (represented as a list of their restrictinfo nodes).
    1310             :  * The list is ordered to match the pathkeys, as required for execution.
    1311             :  */
    1312             : List *
    1313     1403964 : find_mergeclauses_for_outer_pathkeys(PlannerInfo *root,
    1314             :                                      List *pathkeys,
    1315             :                                      List *restrictinfos)
    1316             : {
    1317     1403964 :     List       *mergeclauses = NIL;
    1318             :     ListCell   *i;
    1319             : 
    1320             :     /* make sure we have eclasses cached in the clauses */
    1321     2886308 :     foreach(i, restrictinfos)
    1322             :     {
    1323     1482344 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
    1324             : 
    1325     1482344 :         update_mergeclause_eclasses(root, rinfo);
    1326             :     }
    1327             : 
    1328     2273732 :     foreach(i, pathkeys)
    1329             :     {
    1330     1031052 :         PathKey    *pathkey = (PathKey *) lfirst(i);
    1331     1031052 :         EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
    1332     1031052 :         List       *matched_restrictinfos = NIL;
    1333             :         ListCell   *j;
    1334             : 
    1335             :         /*----------
    1336             :          * A mergejoin clause matches a pathkey if it has the same EC.
    1337             :          * If there are multiple matching clauses, take them all.  In plain
    1338             :          * inner-join scenarios we expect only one match, because
    1339             :          * equivalence-class processing will have removed any redundant
    1340             :          * mergeclauses.  However, in outer-join scenarios there might be
    1341             :          * multiple matches.  An example is
    1342             :          *
    1343             :          *  select * from a full join b
    1344             :          *      on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
    1345             :          *
    1346             :          * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
    1347             :          * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
    1348             :          * we *must* do so or we will be unable to form a valid plan.
    1349             :          *
    1350             :          * We expect that the given pathkeys list is canonical, which means
    1351             :          * no two members have the same EC, so it's not possible for this
    1352             :          * code to enter the same mergeclause into the result list twice.
    1353             :          *
    1354             :          * It's possible that multiple matching clauses might have different
    1355             :          * ECs on the other side, in which case the order we put them into our
    1356             :          * result makes a difference in the pathkeys required for the inner
    1357             :          * input rel.  However this routine hasn't got any info about which
    1358             :          * order would be best, so we don't worry about that.
    1359             :          *
    1360             :          * It's also possible that the selected mergejoin clauses produce
    1361             :          * a noncanonical ordering of pathkeys for the inner side, ie, we
    1362             :          * might select clauses that reference b.v1, b.v2, b.v1 in that
    1363             :          * order.  This is not harmful in itself, though it suggests that
    1364             :          * the clauses are partially redundant.  Since the alternative is
    1365             :          * to omit mergejoin clauses and thereby possibly fail to generate a
    1366             :          * plan altogether, we live with it.  make_inner_pathkeys_for_merge()
    1367             :          * has to delete duplicates when it constructs the inner pathkeys
    1368             :          * list, and we also have to deal with such cases specially in
    1369             :          * create_mergejoin_plan().
    1370             :          *----------
    1371             :          */
    1372     2296852 :         foreach(j, restrictinfos)
    1373             :         {
    1374     1265800 :             RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
    1375             :             EquivalenceClass *clause_ec;
    1376             : 
    1377     2531600 :             clause_ec = rinfo->outer_is_left ?
    1378     1265800 :                 rinfo->left_ec : rinfo->right_ec;
    1379     1265800 :             if (clause_ec == pathkey_ec)
    1380      869894 :                 matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
    1381             :         }
    1382             : 
    1383             :         /*
    1384             :          * If we didn't find a mergeclause, we're done --- any additional
    1385             :          * sort-key positions in the pathkeys are useless.  (But we can still
    1386             :          * mergejoin if we found at least one mergeclause.)
    1387             :          */
    1388     1031052 :         if (matched_restrictinfos == NIL)
    1389      161284 :             break;
    1390             : 
    1391             :         /*
    1392             :          * If we did find usable mergeclause(s) for this sort-key position,
    1393             :          * add them to result list.
    1394             :          */
    1395      869768 :         mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
    1396             :     }
    1397             : 
    1398     1403964 :     return mergeclauses;
    1399             : }
    1400             : 
    1401             : /*
    1402             :  * select_outer_pathkeys_for_merge
    1403             :  *    Builds a pathkey list representing a possible sort ordering
    1404             :  *    that can be used with the given mergeclauses.
    1405             :  *
    1406             :  * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
    1407             :  *          that will be used in a merge join.
    1408             :  * 'joinrel' is the join relation we are trying to construct.
    1409             :  *
    1410             :  * The restrictinfos must be marked (via outer_is_left) to show which side
    1411             :  * of each clause is associated with the current outer path.  (See
    1412             :  * select_mergejoin_clauses())
    1413             :  *
    1414             :  * Returns a pathkeys list that can be applied to the outer relation.
    1415             :  *
    1416             :  * Since we assume here that a sort is required, there is no particular use
    1417             :  * in matching any available ordering of the outerrel.  (joinpath.c has an
    1418             :  * entirely separate code path for considering sort-free mergejoins.)  Rather,
    1419             :  * it's interesting to try to match, or match a prefix of the requested
    1420             :  * query_pathkeys so that a second output sort may be avoided or an
    1421             :  * incremental sort may be done instead.  We can get away with just a prefix
    1422             :  * of the query_pathkeys when that prefix covers the entire join condition.
    1423             :  * Failing that, we try to list "more popular" keys  (those with the most
    1424             :  * unmatched EquivalenceClass peers) earlier, in hopes of making the resulting
    1425             :  * ordering useful for as many higher-level mergejoins as possible.
    1426             :  */
    1427             : List *
    1428      494446 : select_outer_pathkeys_for_merge(PlannerInfo *root,
    1429             :                                 List *mergeclauses,
    1430             :                                 RelOptInfo *joinrel)
    1431             : {
    1432      494446 :     List       *pathkeys = NIL;
    1433      494446 :     int         nClauses = list_length(mergeclauses);
    1434             :     EquivalenceClass **ecs;
    1435             :     int        *scores;
    1436             :     int         necs;
    1437             :     ListCell   *lc;
    1438             :     int         j;
    1439             : 
    1440             :     /* Might have no mergeclauses */
    1441      494446 :     if (nClauses == 0)
    1442       82948 :         return NIL;
    1443             : 
    1444             :     /*
    1445             :      * Make arrays of the ECs used by the mergeclauses (dropping any
    1446             :      * duplicates) and their "popularity" scores.
    1447             :      */
    1448      411498 :     ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
    1449      411498 :     scores = (int *) palloc(nClauses * sizeof(int));
    1450      411498 :     necs = 0;
    1451             : 
    1452      863790 :     foreach(lc, mergeclauses)
    1453             :     {
    1454      452292 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1455             :         EquivalenceClass *oeclass;
    1456             :         int         score;
    1457             :         ListCell   *lc2;
    1458             : 
    1459             :         /* get the outer eclass */
    1460      452292 :         update_mergeclause_eclasses(root, rinfo);
    1461             : 
    1462      452292 :         if (rinfo->outer_is_left)
    1463      227388 :             oeclass = rinfo->left_ec;
    1464             :         else
    1465      224904 :             oeclass = rinfo->right_ec;
    1466             : 
    1467             :         /* reject duplicates */
    1468      495338 :         for (j = 0; j < necs; j++)
    1469             :         {
    1470       43118 :             if (ecs[j] == oeclass)
    1471          72 :                 break;
    1472             :         }
    1473      452292 :         if (j < necs)
    1474          72 :             continue;
    1475             : 
    1476             :         /* compute score */
    1477      452220 :         score = 0;
    1478     1374524 :         foreach(lc2, oeclass->ec_members)
    1479             :         {
    1480      922304 :             EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
    1481             : 
    1482             :             /* Potential future join partner? */
    1483      922304 :             if (!em->em_is_const && !em->em_is_child &&
    1484      799322 :                 !bms_overlap(em->em_relids, joinrel->relids))
    1485       60154 :                 score++;
    1486             :         }
    1487             : 
    1488      452220 :         ecs[necs] = oeclass;
    1489      452220 :         scores[necs] = score;
    1490      452220 :         necs++;
    1491             :     }
    1492             : 
    1493             :     /*
    1494             :      * Find out if we have all the ECs mentioned in query_pathkeys; if so we
    1495             :      * can generate a sort order that's also useful for final output. If we
    1496             :      * only have a prefix of the query_pathkeys, and that prefix is the entire
    1497             :      * join condition, then it's useful to use the prefix as the pathkeys as
    1498             :      * this increases the chances that an incremental sort will be able to be
    1499             :      * used by the upper planner.
    1500             :      */
    1501      411498 :     if (root->query_pathkeys)
    1502             :     {
    1503      207572 :         int         matches = 0;
    1504             : 
    1505      258628 :         foreach(lc, root->query_pathkeys)
    1506             :         {
    1507      246106 :             PathKey    *query_pathkey = (PathKey *) lfirst(lc);
    1508      246106 :             EquivalenceClass *query_ec = query_pathkey->pk_eclass;
    1509             : 
    1510      462758 :             for (j = 0; j < necs; j++)
    1511             :             {
    1512      267708 :                 if (ecs[j] == query_ec)
    1513       51056 :                     break;      /* found match */
    1514             :             }
    1515      246106 :             if (j >= necs)
    1516      195050 :                 break;          /* didn't find match */
    1517             : 
    1518       51056 :             matches++;
    1519             :         }
    1520             :         /* if we got to the end of the list, we have them all */
    1521      207572 :         if (lc == NULL)
    1522             :         {
    1523             :             /* copy query_pathkeys as starting point for our output */
    1524       12522 :             pathkeys = list_copy(root->query_pathkeys);
    1525             :             /* mark their ECs as already-emitted */
    1526       25680 :             foreach(lc, root->query_pathkeys)
    1527             :             {
    1528       13158 :                 PathKey    *query_pathkey = (PathKey *) lfirst(lc);
    1529       13158 :                 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
    1530             : 
    1531       13842 :                 for (j = 0; j < necs; j++)
    1532             :                 {
    1533       13842 :                     if (ecs[j] == query_ec)
    1534             :                     {
    1535       13158 :                         scores[j] = -1;
    1536       13158 :                         break;
    1537             :                     }
    1538             :                 }
    1539             :             }
    1540             :         }
    1541             : 
    1542             :         /*
    1543             :          * If we didn't match to all of the query_pathkeys, but did match to
    1544             :          * all of the join clauses then we'll make use of these as partially
    1545             :          * sorted input is better than nothing for the upper planner as it may
    1546             :          * lead to incremental sorts instead of full sorts.
    1547             :          */
    1548      195050 :         else if (matches == nClauses)
    1549             :         {
    1550       30856 :             pathkeys = list_copy_head(root->query_pathkeys, matches);
    1551             : 
    1552             :             /* we have all of the join pathkeys, so nothing more to do */
    1553       30856 :             pfree(ecs);
    1554       30856 :             pfree(scores);
    1555             : 
    1556       30856 :             return pathkeys;
    1557             :         }
    1558             :     }
    1559             : 
    1560             :     /*
    1561             :      * Add remaining ECs to the list in popularity order, using a default sort
    1562             :      * ordering.  (We could use qsort() here, but the list length is usually
    1563             :      * so small it's not worth it.)
    1564             :      */
    1565             :     for (;;)
    1566      408194 :     {
    1567             :         int         best_j;
    1568             :         int         best_score;
    1569             :         EquivalenceClass *ec;
    1570             :         PathKey    *pathkey;
    1571             : 
    1572      788836 :         best_j = 0;
    1573      788836 :         best_score = scores[0];
    1574      911732 :         for (j = 1; j < necs; j++)
    1575             :         {
    1576      122896 :             if (scores[j] > best_score)
    1577             :             {
    1578       40032 :                 best_j = j;
    1579       40032 :                 best_score = scores[j];
    1580             :             }
    1581             :         }
    1582      788836 :         if (best_score < 0)
    1583      380642 :             break;              /* all done */
    1584      408194 :         ec = ecs[best_j];
    1585      408194 :         scores[best_j] = -1;
    1586      408194 :         pathkey = make_canonical_pathkey(root,
    1587             :                                          ec,
    1588      408194 :                                          linitial_oid(ec->ec_opfamilies),
    1589             :                                          BTLessStrategyNumber,
    1590             :                                          false);
    1591             :         /* can't be redundant because no duplicate ECs */
    1592             :         Assert(!pathkey_is_redundant(pathkey, pathkeys));
    1593      408194 :         pathkeys = lappend(pathkeys, pathkey);
    1594             :     }
    1595             : 
    1596      380642 :     pfree(ecs);
    1597      380642 :     pfree(scores);
    1598             : 
    1599      380642 :     return pathkeys;
    1600             : }
    1601             : 
    1602             : /*
    1603             :  * make_inner_pathkeys_for_merge
    1604             :  *    Builds a pathkey list representing the explicit sort order that
    1605             :  *    must be applied to an inner path to make it usable with the
    1606             :  *    given mergeclauses.
    1607             :  *
    1608             :  * 'mergeclauses' is a list of RestrictInfos for the mergejoin clauses
    1609             :  *          that will be used in a merge join, in order.
    1610             :  * 'outer_pathkeys' are the already-known canonical pathkeys for the outer
    1611             :  *          side of the join.
    1612             :  *
    1613             :  * The restrictinfos must be marked (via outer_is_left) to show which side
    1614             :  * of each clause is associated with the current outer path.  (See
    1615             :  * select_mergejoin_clauses())
    1616             :  *
    1617             :  * Returns a pathkeys list that can be applied to the inner relation.
    1618             :  *
    1619             :  * Note that it is not this routine's job to decide whether sorting is
    1620             :  * actually needed for a particular input path.  Assume a sort is necessary;
    1621             :  * just make the keys, eh?
    1622             :  */
    1623             : List *
    1624      766130 : make_inner_pathkeys_for_merge(PlannerInfo *root,
    1625             :                               List *mergeclauses,
    1626             :                               List *outer_pathkeys)
    1627             : {
    1628      766130 :     List       *pathkeys = NIL;
    1629             :     EquivalenceClass *lastoeclass;
    1630             :     PathKey    *opathkey;
    1631             :     ListCell   *lc;
    1632             :     ListCell   *lop;
    1633             : 
    1634      766130 :     lastoeclass = NULL;
    1635      766130 :     opathkey = NULL;
    1636      766130 :     lop = list_head(outer_pathkeys);
    1637             : 
    1638     1628432 :     foreach(lc, mergeclauses)
    1639             :     {
    1640      862302 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1641             :         EquivalenceClass *oeclass;
    1642             :         EquivalenceClass *ieclass;
    1643             :         PathKey    *pathkey;
    1644             : 
    1645      862302 :         update_mergeclause_eclasses(root, rinfo);
    1646             : 
    1647      862302 :         if (rinfo->outer_is_left)
    1648             :         {
    1649      449496 :             oeclass = rinfo->left_ec;
    1650      449496 :             ieclass = rinfo->right_ec;
    1651             :         }
    1652             :         else
    1653             :         {
    1654      412806 :             oeclass = rinfo->right_ec;
    1655      412806 :             ieclass = rinfo->left_ec;
    1656             :         }
    1657             : 
    1658             :         /* outer eclass should match current or next pathkeys */
    1659             :         /* we check this carefully for debugging reasons */
    1660      862302 :         if (oeclass != lastoeclass)
    1661             :         {
    1662      862188 :             if (!lop)
    1663           0 :                 elog(ERROR, "too few pathkeys for mergeclauses");
    1664      862188 :             opathkey = (PathKey *) lfirst(lop);
    1665      862188 :             lop = lnext(outer_pathkeys, lop);
    1666      862188 :             lastoeclass = opathkey->pk_eclass;
    1667      862188 :             if (oeclass != lastoeclass)
    1668           0 :                 elog(ERROR, "outer pathkeys do not match mergeclause");
    1669             :         }
    1670             : 
    1671             :         /*
    1672             :          * Often, we'll have same EC on both sides, in which case the outer
    1673             :          * pathkey is also canonical for the inner side, and we can skip a
    1674             :          * useless search.
    1675             :          */
    1676      862302 :         if (ieclass == oeclass)
    1677      508500 :             pathkey = opathkey;
    1678             :         else
    1679      353802 :             pathkey = make_canonical_pathkey(root,
    1680             :                                              ieclass,
    1681             :                                              opathkey->pk_opfamily,
    1682             :                                              opathkey->pk_strategy,
    1683      353802 :                                              opathkey->pk_nulls_first);
    1684             : 
    1685             :         /*
    1686             :          * Don't generate redundant pathkeys (which can happen if multiple
    1687             :          * mergeclauses refer to the same EC).  Because we do this, the output
    1688             :          * pathkey list isn't necessarily ordered like the mergeclauses, which
    1689             :          * complicates life for create_mergejoin_plan().  But if we didn't,
    1690             :          * we'd have a noncanonical sort key list, which would be bad; for one
    1691             :          * reason, it certainly wouldn't match any available sort order for
    1692             :          * the input relation.
    1693             :          */
    1694      862302 :         if (!pathkey_is_redundant(pathkey, pathkeys))
    1695      862128 :             pathkeys = lappend(pathkeys, pathkey);
    1696             :     }
    1697             : 
    1698      766130 :     return pathkeys;
    1699             : }
    1700             : 
    1701             : /*
    1702             :  * trim_mergeclauses_for_inner_pathkeys
    1703             :  *    This routine trims a list of mergeclauses to include just those that
    1704             :  *    work with a specified ordering for the join's inner relation.
    1705             :  *
    1706             :  * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses for the
    1707             :  *          join relation being formed, in an order known to work for the
    1708             :  *          currently-considered sort ordering of the join's outer rel.
    1709             :  * 'pathkeys' is a pathkeys list showing the ordering of an inner-rel path;
    1710             :  *          it should be equal to, or a truncation of, the result of
    1711             :  *          make_inner_pathkeys_for_merge for these mergeclauses.
    1712             :  *
    1713             :  * What we return will be a prefix of the given mergeclauses list.
    1714             :  *
    1715             :  * We need this logic because make_inner_pathkeys_for_merge's result isn't
    1716             :  * necessarily in the same order as the mergeclauses.  That means that if we
    1717             :  * consider an inner-rel pathkey list that is a truncation of that result,
    1718             :  * we might need to drop mergeclauses even though they match a surviving inner
    1719             :  * pathkey.  This happens when they are to the right of a mergeclause that
    1720             :  * matches a removed inner pathkey.
    1721             :  *
    1722             :  * The mergeclauses must be marked (via outer_is_left) to show which side
    1723             :  * of each clause is associated with the current outer path.  (See
    1724             :  * select_mergejoin_clauses())
    1725             :  */
    1726             : List *
    1727        2390 : trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root,
    1728             :                                      List *mergeclauses,
    1729             :                                      List *pathkeys)
    1730             : {
    1731        2390 :     List       *new_mergeclauses = NIL;
    1732             :     PathKey    *pathkey;
    1733             :     EquivalenceClass *pathkey_ec;
    1734             :     bool        matched_pathkey;
    1735             :     ListCell   *lip;
    1736             :     ListCell   *i;
    1737             : 
    1738             :     /* No pathkeys => no mergeclauses (though we don't expect this case) */
    1739        2390 :     if (pathkeys == NIL)
    1740           0 :         return NIL;
    1741             :     /* Initialize to consider first pathkey */
    1742        2390 :     lip = list_head(pathkeys);
    1743        2390 :     pathkey = (PathKey *) lfirst(lip);
    1744        2390 :     pathkey_ec = pathkey->pk_eclass;
    1745        2390 :     lip = lnext(pathkeys, lip);
    1746        2390 :     matched_pathkey = false;
    1747             : 
    1748             :     /* Scan mergeclauses to see how many we can use */
    1749        4780 :     foreach(i, mergeclauses)
    1750             :     {
    1751        4780 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
    1752             :         EquivalenceClass *clause_ec;
    1753             : 
    1754             :         /* Assume we needn't do update_mergeclause_eclasses again here */
    1755             : 
    1756             :         /* Check clause's inner-rel EC against current pathkey */
    1757        9560 :         clause_ec = rinfo->outer_is_left ?
    1758        4780 :             rinfo->right_ec : rinfo->left_ec;
    1759             : 
    1760             :         /* If we don't have a match, attempt to advance to next pathkey */
    1761        4780 :         if (clause_ec != pathkey_ec)
    1762             :         {
    1763             :             /* If we had no clauses matching this inner pathkey, must stop */
    1764        2390 :             if (!matched_pathkey)
    1765           0 :                 break;
    1766             : 
    1767             :             /* Advance to next inner pathkey, if any */
    1768        2390 :             if (lip == NULL)
    1769        2390 :                 break;
    1770           0 :             pathkey = (PathKey *) lfirst(lip);
    1771           0 :             pathkey_ec = pathkey->pk_eclass;
    1772           0 :             lip = lnext(pathkeys, lip);
    1773           0 :             matched_pathkey = false;
    1774             :         }
    1775             : 
    1776             :         /* If mergeclause matches current inner pathkey, we can use it */
    1777        2390 :         if (clause_ec == pathkey_ec)
    1778             :         {
    1779        2390 :             new_mergeclauses = lappend(new_mergeclauses, rinfo);
    1780        2390 :             matched_pathkey = true;
    1781             :         }
    1782             :         else
    1783             :         {
    1784             :             /* Else, no hope of adding any more mergeclauses */
    1785           0 :             break;
    1786             :         }
    1787             :     }
    1788             : 
    1789        2390 :     return new_mergeclauses;
    1790             : }
    1791             : 
    1792             : 
    1793             : /****************************************************************************
    1794             :  *      PATHKEY USEFULNESS CHECKS
    1795             :  *
    1796             :  * We only want to remember as many of the pathkeys of a path as have some
    1797             :  * potential use, either for subsequent mergejoins or for meeting the query's
    1798             :  * requested output ordering.  This ensures that add_path() won't consider
    1799             :  * a path to have a usefully different ordering unless it really is useful.
    1800             :  * These routines check for usefulness of given pathkeys.
    1801             :  ****************************************************************************/
    1802             : 
    1803             : /*
    1804             :  * pathkeys_useful_for_merging
    1805             :  *      Count the number of pathkeys that may be useful for mergejoins
    1806             :  *      above the given relation.
    1807             :  *
    1808             :  * We consider a pathkey potentially useful if it corresponds to the merge
    1809             :  * ordering of either side of any joinclause for the rel.  This might be
    1810             :  * overoptimistic, since joinclauses that require different other relations
    1811             :  * might never be usable at the same time, but trying to be exact is likely
    1812             :  * to be more trouble than it's worth.
    1813             :  *
    1814             :  * To avoid doubling the number of mergejoin paths considered, we would like
    1815             :  * to consider only one of the two scan directions (ASC or DESC) as useful
    1816             :  * for merging for any given target column.  The choice is arbitrary unless
    1817             :  * one of the directions happens to match an ORDER BY key, in which case
    1818             :  * that direction should be preferred, in hopes of avoiding a final sort step.
    1819             :  * right_merge_direction() implements this heuristic.
    1820             :  */
    1821             : static int
    1822     2143602 : pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
    1823             : {
    1824     2143602 :     int         useful = 0;
    1825             :     ListCell   *i;
    1826             : 
    1827     2633720 :     foreach(i, pathkeys)
    1828             :     {
    1829     1286262 :         PathKey    *pathkey = (PathKey *) lfirst(i);
    1830     1286262 :         bool        matched = false;
    1831             :         ListCell   *j;
    1832             : 
    1833             :         /* If "wrong" direction, not useful for merging */
    1834     1286262 :         if (!right_merge_direction(root, pathkey))
    1835      241278 :             break;
    1836             : 
    1837             :         /*
    1838             :          * First look into the EquivalenceClass of the pathkey, to see if
    1839             :          * there are any members not yet joined to the rel.  If so, it's
    1840             :          * surely possible to generate a mergejoin clause using them.
    1841             :          */
    1842     1598402 :         if (rel->has_eclass_joins &&
    1843      553418 :             eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
    1844      314070 :             matched = true;
    1845             :         else
    1846             :         {
    1847             :             /*
    1848             :              * Otherwise search the rel's joininfo list, which contains
    1849             :              * non-EquivalenceClass-derivable join clauses that might
    1850             :              * nonetheless be mergejoinable.
    1851             :              */
    1852     1126772 :             foreach(j, rel->joininfo)
    1853             :             {
    1854      571906 :                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
    1855             : 
    1856      571906 :                 if (restrictinfo->mergeopfamilies == NIL)
    1857      127644 :                     continue;
    1858      444262 :                 update_mergeclause_eclasses(root, restrictinfo);
    1859             : 
    1860      444262 :                 if (pathkey->pk_eclass == restrictinfo->left_ec ||
    1861      361630 :                     pathkey->pk_eclass == restrictinfo->right_ec)
    1862             :                 {
    1863      176048 :                     matched = true;
    1864      176048 :                     break;
    1865             :                 }
    1866             :             }
    1867             :         }
    1868             : 
    1869             :         /*
    1870             :          * If we didn't find a mergeclause, we're done --- any additional
    1871             :          * sort-key positions in the pathkeys are useless.  (But we can still
    1872             :          * mergejoin if we found at least one mergeclause.)
    1873             :          */
    1874     1044984 :         if (matched)
    1875      490118 :             useful++;
    1876             :         else
    1877      554866 :             break;
    1878             :     }
    1879             : 
    1880     2143602 :     return useful;
    1881             : }
    1882             : 
    1883             : /*
    1884             :  * right_merge_direction
    1885             :  *      Check whether the pathkey embodies the preferred sort direction
    1886             :  *      for merging its target column.
    1887             :  */
    1888             : static bool
    1889     1286262 : right_merge_direction(PlannerInfo *root, PathKey *pathkey)
    1890             : {
    1891             :     ListCell   *l;
    1892             : 
    1893     2118822 :     foreach(l, root->query_pathkeys)
    1894             :     {
    1895     1092606 :         PathKey    *query_pathkey = (PathKey *) lfirst(l);
    1896             : 
    1897     1092606 :         if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
    1898      260046 :             pathkey->pk_opfamily == query_pathkey->pk_opfamily)
    1899             :         {
    1900             :             /*
    1901             :              * Found a matching query sort column.  Prefer this pathkey's
    1902             :              * direction iff it matches.  Note that we ignore pk_nulls_first,
    1903             :              * which means that a sort might be needed anyway ... but we still
    1904             :              * want to prefer only one of the two possible directions, and we
    1905             :              * might as well use this one.
    1906             :              */
    1907      260046 :             return (pathkey->pk_strategy == query_pathkey->pk_strategy);
    1908             :         }
    1909             :     }
    1910             : 
    1911             :     /* If no matching ORDER BY request, prefer the ASC direction */
    1912     1026216 :     return (pathkey->pk_strategy == BTLessStrategyNumber);
    1913             : }
    1914             : 
    1915             : /*
    1916             :  * pathkeys_useful_for_ordering
    1917             :  *      Count the number of pathkeys that are useful for meeting the
    1918             :  *      query's requested output ordering.
    1919             :  *
    1920             :  * Because we the have the possibility of incremental sort, a prefix list of
    1921             :  * keys is potentially useful for improving the performance of the requested
    1922             :  * ordering. Thus we return 0, if no valuable keys are found, or the number
    1923             :  * of leading keys shared by the list and the requested ordering..
    1924             :  */
    1925             : static int
    1926     2143602 : pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
    1927             : {
    1928             :     int         n_common_pathkeys;
    1929             : 
    1930     2143602 :     if (root->query_pathkeys == NIL)
    1931     1095720 :         return 0;               /* no special ordering requested */
    1932             : 
    1933     1047882 :     if (pathkeys == NIL)
    1934      386420 :         return 0;               /* unordered path */
    1935             : 
    1936      661462 :     (void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys,
    1937             :                                        &n_common_pathkeys);
    1938             : 
    1939      661462 :     return n_common_pathkeys;
    1940             : }
    1941             : 
    1942             : /*
    1943             :  * truncate_useless_pathkeys
    1944             :  *      Shorten the given pathkey list to just the useful pathkeys.
    1945             :  */
    1946             : List *
    1947     2143602 : truncate_useless_pathkeys(PlannerInfo *root,
    1948             :                           RelOptInfo *rel,
    1949             :                           List *pathkeys)
    1950             : {
    1951             :     int         nuseful;
    1952             :     int         nuseful2;
    1953             : 
    1954     2143602 :     nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
    1955     2143602 :     nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
    1956     2143602 :     if (nuseful2 > nuseful)
    1957      105526 :         nuseful = nuseful2;
    1958             : 
    1959             :     /*
    1960             :      * Note: not safe to modify input list destructively, but we can avoid
    1961             :      * copying the list if we're not actually going to change it
    1962             :      */
    1963     2143602 :     if (nuseful == 0)
    1964     1592874 :         return NIL;
    1965      550728 :     else if (nuseful == list_length(pathkeys))
    1966      525282 :         return pathkeys;
    1967             :     else
    1968       25446 :         return list_copy_head(pathkeys, nuseful);
    1969             : }
    1970             : 
    1971             : /*
    1972             :  * has_useful_pathkeys
    1973             :  *      Detect whether the specified rel could have any pathkeys that are
    1974             :  *      useful according to truncate_useless_pathkeys().
    1975             :  *
    1976             :  * This is a cheap test that lets us skip building pathkeys at all in very
    1977             :  * simple queries.  It's OK to err in the direction of returning "true" when
    1978             :  * there really aren't any usable pathkeys, but erring in the other direction
    1979             :  * is bad --- so keep this in sync with the routines above!
    1980             :  *
    1981             :  * We could make the test more complex, for example checking to see if any of
    1982             :  * the joinclauses are really mergejoinable, but that likely wouldn't win
    1983             :  * often enough to repay the extra cycles.  Queries with neither a join nor
    1984             :  * a sort are reasonably common, though, so this much work seems worthwhile.
    1985             :  */
    1986             : bool
    1987      702766 : has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel)
    1988             : {
    1989      702766 :     if (rel->joininfo != NIL || rel->has_eclass_joins)
    1990      438670 :         return true;            /* might be able to use pathkeys for merging */
    1991      264096 :     if (root->query_pathkeys != NIL)
    1992       64790 :         return true;            /* might be able to use them for ordering */
    1993      199306 :     return false;               /* definitely useless */
    1994             : }

Generated by: LCOV version 1.14