LCOV - code coverage report
Current view: top level - src/backend/optimizer/path - pathkeys.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 550 575 95.7 %
Date: 2024-04-25 02:12:45 Functions: 37 37 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-2024, 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/nodeFuncs.h"
      23             : #include "optimizer/cost.h"
      24             : #include "optimizer/optimizer.h"
      25             : #include "optimizer/pathnode.h"
      26             : #include "optimizer/paths.h"
      27             : #include "partitioning/partbounds.h"
      28             : #include "utils/lsyscache.h"
      29             : 
      30             : /* Consider reordering of GROUP BY keys? */
      31             : bool        enable_group_by_reordering = true;
      32             : 
      33             : static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
      34             : static bool matches_boolean_partition_clause(RestrictInfo *rinfo,
      35             :                                              RelOptInfo *partrel,
      36             :                                              int partkeycol);
      37             : static Var *find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle);
      38             : static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
      39             : 
      40             : 
      41             : /****************************************************************************
      42             :  *      PATHKEY CONSTRUCTION AND REDUNDANCY TESTING
      43             :  ****************************************************************************/
      44             : 
      45             : /*
      46             :  * make_canonical_pathkey
      47             :  *    Given the parameters for a PathKey, find any pre-existing matching
      48             :  *    pathkey in the query's list of "canonical" pathkeys.  Make a new
      49             :  *    entry if there's not one already.
      50             :  *
      51             :  * Note that this function must not be used until after we have completed
      52             :  * merging EquivalenceClasses.
      53             :  */
      54             : PathKey *
      55     1830770 : make_canonical_pathkey(PlannerInfo *root,
      56             :                        EquivalenceClass *eclass, Oid opfamily,
      57             :                        int strategy, bool nulls_first)
      58             : {
      59             :     PathKey    *pk;
      60             :     ListCell   *lc;
      61             :     MemoryContext oldcontext;
      62             : 
      63             :     /* Can't make canonical pathkeys if the set of ECs might still change */
      64     1830770 :     if (!root->ec_merging_done)
      65           0 :         elog(ERROR, "too soon to build canonical pathkeys");
      66             : 
      67             :     /* The passed eclass might be non-canonical, so chase up to the top */
      68     1830770 :     while (eclass->ec_merged)
      69           0 :         eclass = eclass->ec_merged;
      70             : 
      71     9349498 :     foreach(lc, root->canon_pathkeys)
      72             :     {
      73     8821162 :         pk = (PathKey *) lfirst(lc);
      74     8821162 :         if (eclass == pk->pk_eclass &&
      75     1725964 :             opfamily == pk->pk_opfamily &&
      76     1725964 :             strategy == pk->pk_strategy &&
      77     1302488 :             nulls_first == pk->pk_nulls_first)
      78     1302434 :             return pk;
      79             :     }
      80             : 
      81             :     /*
      82             :      * Be sure canonical pathkeys are allocated in the main planning context.
      83             :      * Not an issue in normal planning, but it is for GEQO.
      84             :      */
      85      528336 :     oldcontext = MemoryContextSwitchTo(root->planner_cxt);
      86             : 
      87      528336 :     pk = makeNode(PathKey);
      88      528336 :     pk->pk_eclass = eclass;
      89      528336 :     pk->pk_opfamily = opfamily;
      90      528336 :     pk->pk_strategy = strategy;
      91      528336 :     pk->pk_nulls_first = nulls_first;
      92             : 
      93      528336 :     root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
      94             : 
      95      528336 :     MemoryContextSwitchTo(oldcontext);
      96             : 
      97      528336 :     return pk;
      98             : }
      99             : 
     100             : /*
     101             :  * append_pathkeys
     102             :  *      Append all non-redundant PathKeys in 'source' onto 'target' and
     103             :  *      returns the updated 'target' list.
     104             :  */
     105             : List *
     106        1438 : append_pathkeys(List *target, List *source)
     107             : {
     108             :     ListCell   *lc;
     109             : 
     110             :     Assert(target != NIL);
     111             : 
     112        2942 :     foreach(lc, source)
     113             :     {
     114        1504 :         PathKey    *pk = lfirst_node(PathKey, lc);
     115             : 
     116        1504 :         if (!pathkey_is_redundant(pk, target))
     117        1366 :             target = lappend(target, pk);
     118             :     }
     119        1438 :     return target;
     120             : }
     121             : 
     122             : /*
     123             :  * pathkey_is_redundant
     124             :  *     Is a pathkey redundant with one already in the given list?
     125             :  *
     126             :  * We detect two cases:
     127             :  *
     128             :  * 1. If the new pathkey's equivalence class contains a constant, and isn't
     129             :  * below an outer join, then we can disregard it as a sort key.  An example:
     130             :  *          SELECT ... WHERE x = 42 ORDER BY x, y;
     131             :  * We may as well just sort by y.  Note that because of opfamily matching,
     132             :  * this is semantically correct: we know that the equality constraint is one
     133             :  * that actually binds the variable to a single value in the terms of any
     134             :  * ordering operator that might go with the eclass.  This rule not only lets
     135             :  * us simplify (or even skip) explicit sorts, but also allows matching index
     136             :  * sort orders to a query when there are don't-care index columns.
     137             :  *
     138             :  * 2. If the new pathkey's equivalence class is the same as that of any
     139             :  * existing member of the pathkey list, then it is redundant.  Some examples:
     140             :  *          SELECT ... ORDER BY x, x;
     141             :  *          SELECT ... ORDER BY x, x DESC;
     142             :  *          SELECT ... WHERE x = y ORDER BY x, y;
     143             :  * In all these cases the second sort key cannot distinguish values that are
     144             :  * considered equal by the first, and so there's no point in using it.
     145             :  * Note in particular that we need not compare opfamily (all the opfamilies
     146             :  * of the EC have the same notion of equality) nor sort direction.
     147             :  *
     148             :  * Both the given pathkey and the list members must be canonical for this
     149             :  * to work properly, but that's okay since we no longer ever construct any
     150             :  * non-canonical pathkeys.  (Note: the notion of a pathkey *list* being
     151             :  * canonical includes the additional requirement of no redundant entries,
     152             :  * which is exactly what we are checking for here.)
     153             :  *
     154             :  * Because the equivclass.c machinery forms only one copy of any EC per query,
     155             :  * pointer comparison is enough to decide whether canonical ECs are the same.
     156             :  */
     157             : static bool
     158     1949736 : pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
     159             : {
     160     1949736 :     EquivalenceClass *new_ec = new_pathkey->pk_eclass;
     161             :     ListCell   *lc;
     162             : 
     163             :     /* Check for EC containing a constant --- unconditionally redundant */
     164     1949736 :     if (EC_MUST_BE_REDUNDANT(new_ec))
     165      257250 :         return true;
     166             : 
     167             :     /* If same EC already used in list, then redundant */
     168     1945836 :     foreach(lc, pathkeys)
     169             :     {
     170      254008 :         PathKey    *old_pathkey = (PathKey *) lfirst(lc);
     171             : 
     172      254008 :         if (new_ec == old_pathkey->pk_eclass)
     173         658 :             return true;
     174             :     }
     175             : 
     176     1691828 :     return false;
     177             : }
     178             : 
     179             : /*
     180             :  * make_pathkey_from_sortinfo
     181             :  *    Given an expression and sort-order information, create a PathKey.
     182             :  *    The result is always a "canonical" PathKey, but it might be redundant.
     183             :  *
     184             :  * If the PathKey is being generated from a SortGroupClause, sortref should be
     185             :  * the SortGroupClause's SortGroupRef; otherwise zero.
     186             :  *
     187             :  * If rel is not NULL, it identifies a specific relation we're considering
     188             :  * a path for, and indicates that child EC members for that relation can be
     189             :  * considered.  Otherwise child members are ignored.  (See the comments for
     190             :  * get_eclass_for_sort_expr.)
     191             :  *
     192             :  * create_it is true if we should create any missing EquivalenceClass
     193             :  * needed to represent the sort key.  If it's false, we return NULL if the
     194             :  * sort key isn't already present in any EquivalenceClass.
     195             :  */
     196             : static PathKey *
     197     1518842 : make_pathkey_from_sortinfo(PlannerInfo *root,
     198             :                            Expr *expr,
     199             :                            Oid opfamily,
     200             :                            Oid opcintype,
     201             :                            Oid collation,
     202             :                            bool reverse_sort,
     203             :                            bool nulls_first,
     204             :                            Index sortref,
     205             :                            Relids rel,
     206             :                            bool create_it)
     207             : {
     208             :     int16       strategy;
     209             :     Oid         equality_op;
     210             :     List       *opfamilies;
     211             :     EquivalenceClass *eclass;
     212             : 
     213     1518842 :     strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
     214             : 
     215             :     /*
     216             :      * EquivalenceClasses need to contain opfamily lists based on the family
     217             :      * membership of mergejoinable equality operators, which could belong to
     218             :      * more than one opfamily.  So we have to look up the opfamily's equality
     219             :      * operator and get its membership.
     220             :      */
     221     1518842 :     equality_op = get_opfamily_member(opfamily,
     222             :                                       opcintype,
     223             :                                       opcintype,
     224             :                                       BTEqualStrategyNumber);
     225     1518842 :     if (!OidIsValid(equality_op))   /* shouldn't happen */
     226           0 :         elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
     227             :              BTEqualStrategyNumber, opcintype, opcintype, opfamily);
     228     1518842 :     opfamilies = get_mergejoin_opfamilies(equality_op);
     229     1518842 :     if (!opfamilies)            /* certainly should find some */
     230           0 :         elog(ERROR, "could not find opfamilies for equality operator %u",
     231             :              equality_op);
     232             : 
     233             :     /* Now find or (optionally) create a matching EquivalenceClass */
     234     1518842 :     eclass = get_eclass_for_sort_expr(root, expr,
     235             :                                       opfamilies, opcintype, collation,
     236             :                                       sortref, rel, create_it);
     237             : 
     238             :     /* Fail if no EC and !create_it */
     239     1518842 :     if (!eclass)
     240      522096 :         return NULL;
     241             : 
     242             :     /* And finally we can find or create a PathKey node */
     243      996746 :     return make_canonical_pathkey(root, eclass, opfamily,
     244             :                                   strategy, nulls_first);
     245             : }
     246             : 
     247             : /*
     248             :  * make_pathkey_from_sortop
     249             :  *    Like make_pathkey_from_sortinfo, but work from a sort operator.
     250             :  *
     251             :  * This should eventually go away, but we need to restructure SortGroupClause
     252             :  * first.
     253             :  */
     254             : static PathKey *
     255      149914 : make_pathkey_from_sortop(PlannerInfo *root,
     256             :                          Expr *expr,
     257             :                          Oid ordering_op,
     258             :                          bool nulls_first,
     259             :                          Index sortref,
     260             :                          bool create_it)
     261             : {
     262             :     Oid         opfamily,
     263             :                 opcintype,
     264             :                 collation;
     265             :     int16       strategy;
     266             : 
     267             :     /* Find the operator in pg_amop --- failure shouldn't happen */
     268      149914 :     if (!get_ordering_op_properties(ordering_op,
     269             :                                     &opfamily, &opcintype, &strategy))
     270           0 :         elog(ERROR, "operator %u is not a valid ordering operator",
     271             :              ordering_op);
     272             : 
     273             :     /* Because SortGroupClause doesn't carry collation, consult the expr */
     274      149914 :     collation = exprCollation((Node *) expr);
     275             : 
     276      149914 :     return make_pathkey_from_sortinfo(root,
     277             :                                       expr,
     278             :                                       opfamily,
     279             :                                       opcintype,
     280             :                                       collation,
     281             :                                       (strategy == BTGreaterStrategyNumber),
     282             :                                       nulls_first,
     283             :                                       sortref,
     284             :                                       NULL,
     285             :                                       create_it);
     286             : }
     287             : 
     288             : 
     289             : /****************************************************************************
     290             :  *      PATHKEY COMPARISONS
     291             :  ****************************************************************************/
     292             : 
     293             : /*
     294             :  * compare_pathkeys
     295             :  *    Compare two pathkeys to see if they are equivalent, and if not whether
     296             :  *    one is "better" than the other.
     297             :  *
     298             :  *    We assume the pathkeys are canonical, and so they can be checked for
     299             :  *    equality by simple pointer comparison.
     300             :  */
     301             : PathKeysComparison
     302     9960450 : compare_pathkeys(List *keys1, List *keys2)
     303             : {
     304             :     ListCell   *key1,
     305             :                *key2;
     306             : 
     307             :     /*
     308             :      * Fall out quickly if we are passed two identical lists.  This mostly
     309             :      * catches the case where both are NIL, but that's common enough to
     310             :      * warrant the test.
     311             :      */
     312     9960450 :     if (keys1 == keys2)
     313     3768022 :         return PATHKEYS_EQUAL;
     314             : 
     315     7684618 :     forboth(key1, keys1, key2, keys2)
     316             :     {
     317     2140472 :         PathKey    *pathkey1 = (PathKey *) lfirst(key1);
     318     2140472 :         PathKey    *pathkey2 = (PathKey *) lfirst(key2);
     319             : 
     320     2140472 :         if (pathkey1 != pathkey2)
     321      648282 :             return PATHKEYS_DIFFERENT;  /* no need to keep looking */
     322             :     }
     323             : 
     324             :     /*
     325             :      * If we reached the end of only one list, the other is longer and
     326             :      * therefore not a subset.
     327             :      */
     328     5544146 :     if (key1 != NULL)
     329     3806884 :         return PATHKEYS_BETTER1;    /* key1 is longer */
     330     1737262 :     if (key2 != NULL)
     331      532574 :         return PATHKEYS_BETTER2;    /* key2 is longer */
     332     1204688 :     return PATHKEYS_EQUAL;
     333             : }
     334             : 
     335             : /*
     336             :  * pathkeys_contained_in
     337             :  *    Common special case of compare_pathkeys: we just want to know
     338             :  *    if keys2 are at least as well sorted as keys1.
     339             :  */
     340             : bool
     341     3493140 : pathkeys_contained_in(List *keys1, List *keys2)
     342             : {
     343     3493140 :     switch (compare_pathkeys(keys1, keys2))
     344             :     {
     345      851312 :         case PATHKEYS_EQUAL:
     346             :         case PATHKEYS_BETTER2:
     347      851312 :             return true;
     348     2641828 :         default:
     349     2641828 :             break;
     350             :     }
     351     2641828 :     return false;
     352             : }
     353             : 
     354             : /*
     355             :  * group_keys_reorder_by_pathkeys
     356             :  *      Reorder GROUP BY pathkeys and clauses to match the input pathkeys.
     357             :  *
     358             :  * 'pathkeys' is an input list of pathkeys
     359             :  * '*group_pathkeys' and '*group_clauses' are pathkeys and clauses lists to
     360             :  *      reorder.  The pointers are redirected to new lists, original lists
     361             :  *      stay untouched.
     362             :  * 'num_groupby_pathkeys' is the number of first '*group_pathkeys' items to
     363             :  *      search matching pathkeys.
     364             :  *
     365             :  * Returns the number of GROUP BY keys with a matching pathkey.
     366             :  */
     367             : static int
     368        4060 : group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
     369             :                                List **group_clauses,
     370             :                                int num_groupby_pathkeys)
     371             : {
     372        4060 :     List       *new_group_pathkeys = NIL,
     373        4060 :                *new_group_clauses = NIL;
     374             :     List       *grouping_pathkeys;
     375             :     ListCell   *lc;
     376             :     int         n;
     377             : 
     378        4060 :     if (pathkeys == NIL || *group_pathkeys == NIL)
     379          86 :         return 0;
     380             : 
     381             :     /*
     382             :      * We're going to search within just the first num_groupby_pathkeys of
     383             :      * *group_pathkeys.  The thing is that root->group_pathkeys is passed as
     384             :      * *group_pathkeys containing grouping pathkeys altogether with aggregate
     385             :      * pathkeys.  If we process aggregate pathkeys we could get an invalid
     386             :      * result of get_sortgroupref_clause_noerr(), because their
     387             :      * pathkey->pk_eclass->ec_sortref doesn't reference query targetlist.  So,
     388             :      * we allocate a separate list of pathkeys for lookups.
     389             :      */
     390        3974 :     grouping_pathkeys = list_copy_head(*group_pathkeys, num_groupby_pathkeys);
     391             : 
     392             :     /*
     393             :      * Walk the pathkeys (determining ordering of the input path) and see if
     394             :      * there's a matching GROUP BY key. If we find one, we append it to the
     395             :      * list, and do the same for the clauses.
     396             :      *
     397             :      * Once we find the first pathkey without a matching GROUP BY key, the
     398             :      * rest of the pathkeys are useless and can't be used to evaluate the
     399             :      * grouping, so we abort the loop and ignore the remaining pathkeys.
     400             :      */
     401        7908 :     foreach(lc, pathkeys)
     402             :     {
     403        7788 :         PathKey    *pathkey = (PathKey *) lfirst(lc);
     404             :         SortGroupClause *sgc;
     405             : 
     406             :         /*
     407             :          * Pathkeys are built in a way that allows simply comparing pointers.
     408             :          * Give up if we can't find the matching pointer.  Also give up if
     409             :          * there is no sortclause reference for some reason.
     410             :          */
     411        7788 :         if (foreach_current_index(lc) >= num_groupby_pathkeys ||
     412        5208 :             !list_member_ptr(grouping_pathkeys, pathkey) ||
     413        3934 :             pathkey->pk_eclass->ec_sortref == 0)
     414             :             break;
     415             : 
     416             :         /*
     417             :          * Since 1349d27 pathkey coming from underlying node can be in the
     418             :          * root->group_pathkeys but not in the processed_groupClause. So, we
     419             :          * should be careful here.
     420             :          */
     421        3934 :         sgc = get_sortgroupref_clause_noerr(pathkey->pk_eclass->ec_sortref,
     422             :                                             *group_clauses);
     423        3934 :         if (!sgc)
     424             :             /* The grouping clause does not cover this pathkey */
     425           0 :             break;
     426             : 
     427             :         /*
     428             :          * Sort group clause should have an ordering operator as long as there
     429             :          * is an associated pathkey.
     430             :          */
     431             :         Assert(OidIsValid(sgc->sortop));
     432             : 
     433        3934 :         new_group_pathkeys = lappend(new_group_pathkeys, pathkey);
     434        3934 :         new_group_clauses = lappend(new_group_clauses, sgc);
     435             :     }
     436             : 
     437             :     /* remember the number of pathkeys with a matching GROUP BY key */
     438        3974 :     n = list_length(new_group_pathkeys);
     439             : 
     440             :     /* append the remaining group pathkeys (will be treated as not sorted) */
     441        3974 :     *group_pathkeys = list_concat_unique_ptr(new_group_pathkeys,
     442             :                                              *group_pathkeys);
     443        3974 :     *group_clauses = list_concat_unique_ptr(new_group_clauses,
     444             :                                             *group_clauses);
     445             : 
     446        3974 :     list_free(grouping_pathkeys);
     447        3974 :     return n;
     448             : }
     449             : 
     450             : /*
     451             :  * pathkeys_are_duplicate
     452             :  *      Check if give pathkeys are already contained the list of
     453             :  *      PathKeyInfo's.
     454             :  */
     455             : static bool
     456         230 : pathkeys_are_duplicate(List *infos, List *pathkeys)
     457             : {
     458             :     ListCell   *lc;
     459             : 
     460         362 :     foreach(lc, infos)
     461             :     {
     462         236 :         PathKeyInfo *info = lfirst_node(PathKeyInfo, lc);
     463             : 
     464         236 :         if (compare_pathkeys(pathkeys, info->pathkeys) == PATHKEYS_EQUAL)
     465         104 :             return true;
     466             :     }
     467         126 :     return false;
     468             : }
     469             : 
     470             : /*
     471             :  * get_useful_group_keys_orderings
     472             :  *      Determine which orderings of GROUP BY keys are potentially interesting.
     473             :  *
     474             :  * Returns a list of PathKeyInfo items, each representing an interesting
     475             :  * ordering of GROUP BY keys.  Each item stores pathkeys and clauses in the
     476             :  * matching order.
     477             :  *
     478             :  * The function considers (and keeps) multiple GROUP BY orderings:
     479             :  *
     480             :  * - the original ordering, as specified by the GROUP BY clause,
     481             :  * - GROUP BY keys reordered to match 'path' ordering (as much as possible),
     482             :  * - GROUP BY keys to match target ORDER BY clause (as much as possible).
     483             :  */
     484             : List *
     485       42100 : get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
     486             : {
     487       42100 :     Query      *parse = root->parse;
     488       42100 :     List       *infos = NIL;
     489             :     PathKeyInfo *info;
     490             : 
     491       42100 :     List       *pathkeys = root->group_pathkeys;
     492       42100 :     List       *clauses = root->processed_groupClause;
     493             : 
     494             :     /* always return at least the original pathkeys/clauses */
     495       42100 :     info = makeNode(PathKeyInfo);
     496       42100 :     info->pathkeys = pathkeys;
     497       42100 :     info->clauses = clauses;
     498       42100 :     infos = lappend(infos, info);
     499             : 
     500             :     /*
     501             :      * Should we try generating alternative orderings of the group keys? If
     502             :      * not, we produce only the order specified in the query, i.e. the
     503             :      * optimization is effectively disabled.
     504             :      */
     505       42100 :     if (!enable_group_by_reordering)
     506           0 :         return infos;
     507             : 
     508             :     /*
     509             :      * Grouping sets have own and more complex logic to decide the ordering.
     510             :      */
     511       42100 :     if (parse->groupingSets)
     512         800 :         return infos;
     513             : 
     514             :     /*
     515             :      * If the path is sorted in some way, try reordering the group keys to
     516             :      * match the path as much of the ordering as possible.  Then thanks to
     517             :      * incremental sort we would get this sort as cheap as possible.
     518             :      */
     519       41300 :     if (path->pathkeys &&
     520        3000 :         !pathkeys_contained_in(path->pathkeys, root->group_pathkeys))
     521             :     {
     522             :         int         n;
     523             : 
     524         116 :         n = group_keys_reorder_by_pathkeys(path->pathkeys, &pathkeys, &clauses,
     525             :                                            root->num_groupby_pathkeys);
     526             : 
     527         116 :         if (n > 0 &&
     528          96 :             (enable_incremental_sort || n == root->num_groupby_pathkeys) &&
     529          96 :             !pathkeys_are_duplicate(infos, pathkeys))
     530             :         {
     531          96 :             info = makeNode(PathKeyInfo);
     532          96 :             info->pathkeys = pathkeys;
     533          96 :             info->clauses = clauses;
     534             : 
     535          96 :             infos = lappend(infos, info);
     536             :         }
     537             :     }
     538             : 
     539             :     /*
     540             :      * Try reordering pathkeys to minimize the sort cost (this time consider
     541             :      * the ORDER BY clause).
     542             :      */
     543       41300 :     if (root->sort_pathkeys &&
     544        5698 :         !pathkeys_contained_in(root->sort_pathkeys, root->group_pathkeys))
     545             :     {
     546             :         int         n;
     547             : 
     548        3944 :         n = group_keys_reorder_by_pathkeys(root->sort_pathkeys, &pathkeys,
     549             :                                            &clauses,
     550             :                                            root->num_groupby_pathkeys);
     551             : 
     552        3944 :         if (n > 0 &&
     553        3544 :             (enable_incremental_sort || n == list_length(root->sort_pathkeys)) &&
     554         134 :             !pathkeys_are_duplicate(infos, pathkeys))
     555             :         {
     556          30 :             info = makeNode(PathKeyInfo);
     557          30 :             info->pathkeys = pathkeys;
     558          30 :             info->clauses = clauses;
     559             : 
     560          30 :             infos = lappend(infos, info);
     561             :         }
     562             :     }
     563             : 
     564       41300 :     return infos;
     565             : }
     566             : 
     567             : /*
     568             :  * pathkeys_count_contained_in
     569             :  *    Same as pathkeys_contained_in, but also sets length of longest
     570             :  *    common prefix of keys1 and keys2.
     571             :  */
     572             : bool
     573     4838496 : pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
     574             : {
     575     4838496 :     int         n = 0;
     576             :     ListCell   *key1,
     577             :                *key2;
     578             : 
     579             :     /*
     580             :      * See if we can avoiding looping through both lists. This optimization
     581             :      * gains us several percent in planning time in a worst-case test.
     582             :      */
     583     4838496 :     if (keys1 == keys2)
     584             :     {
     585     1282458 :         *n_common = list_length(keys1);
     586     1282458 :         return true;
     587             :     }
     588     3556038 :     else if (keys1 == NIL)
     589             :     {
     590     1399012 :         *n_common = 0;
     591     1399012 :         return true;
     592             :     }
     593     2157026 :     else if (keys2 == NIL)
     594             :     {
     595      800684 :         *n_common = 0;
     596      800684 :         return false;
     597             :     }
     598             : 
     599             :     /*
     600             :      * If both lists are non-empty, iterate through both to find out how many
     601             :      * items are shared.
     602             :      */
     603     1756262 :     forboth(key1, keys1, key2, keys2)
     604             :     {
     605     1393788 :         PathKey    *pathkey1 = (PathKey *) lfirst(key1);
     606     1393788 :         PathKey    *pathkey2 = (PathKey *) lfirst(key2);
     607             : 
     608     1393788 :         if (pathkey1 != pathkey2)
     609             :         {
     610      993868 :             *n_common = n;
     611      993868 :             return false;
     612             :         }
     613      399920 :         n++;
     614             :     }
     615             : 
     616             :     /* If we ended with a null value, then we've processed the whole list. */
     617      362474 :     *n_common = n;
     618      362474 :     return (key1 == NULL);
     619             : }
     620             : 
     621             : /*
     622             :  * get_cheapest_path_for_pathkeys
     623             :  *    Find the cheapest path (according to the specified criterion) that
     624             :  *    satisfies the given pathkeys and parameterization, and is parallel-safe
     625             :  *    if required.
     626             :  *    Return NULL if no such path.
     627             :  *
     628             :  * 'paths' is a list of possible paths that all generate the same relation
     629             :  * 'pathkeys' represents a required ordering (in canonical form!)
     630             :  * 'required_outer' denotes allowable outer relations for parameterized paths
     631             :  * 'cost_criterion' is STARTUP_COST or TOTAL_COST
     632             :  * 'require_parallel_safe' causes us to consider only parallel-safe paths
     633             :  */
     634             : Path *
     635      729296 : get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
     636             :                                Relids required_outer,
     637             :                                CostSelector cost_criterion,
     638             :                                bool require_parallel_safe)
     639             : {
     640      729296 :     Path       *matched_path = NULL;
     641             :     ListCell   *l;
     642             : 
     643     2589030 :     foreach(l, paths)
     644             :     {
     645     1859734 :         Path       *path = (Path *) lfirst(l);
     646             : 
     647             :         /* If required, reject paths that are not parallel-safe */
     648     1859734 :         if (require_parallel_safe && !path->parallel_safe)
     649         264 :             continue;
     650             : 
     651             :         /*
     652             :          * Since cost comparison is a lot cheaper than pathkey comparison, do
     653             :          * that first.  (XXX is that still true?)
     654             :          */
     655     1935120 :         if (matched_path != NULL &&
     656       75650 :             compare_path_costs(matched_path, path, cost_criterion) <= 0)
     657       64564 :             continue;
     658             : 
     659     2562190 :         if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
     660      767284 :             bms_is_subset(PATH_REQ_OUTER(path), required_outer))
     661      474800 :             matched_path = path;
     662             :     }
     663      729296 :     return matched_path;
     664             : }
     665             : 
     666             : /*
     667             :  * get_cheapest_fractional_path_for_pathkeys
     668             :  *    Find the cheapest path (for retrieving a specified fraction of all
     669             :  *    the tuples) that satisfies the given pathkeys and parameterization.
     670             :  *    Return NULL if no such path.
     671             :  *
     672             :  * See compare_fractional_path_costs() for the interpretation of the fraction
     673             :  * parameter.
     674             :  *
     675             :  * 'paths' is a list of possible paths that all generate the same relation
     676             :  * 'pathkeys' represents a required ordering (in canonical form!)
     677             :  * 'required_outer' denotes allowable outer relations for parameterized paths
     678             :  * 'fraction' is the fraction of the total tuples expected to be retrieved
     679             :  */
     680             : Path *
     681        1666 : get_cheapest_fractional_path_for_pathkeys(List *paths,
     682             :                                           List *pathkeys,
     683             :                                           Relids required_outer,
     684             :                                           double fraction)
     685             : {
     686        1666 :     Path       *matched_path = NULL;
     687             :     ListCell   *l;
     688             : 
     689        4554 :     foreach(l, paths)
     690             :     {
     691        2888 :         Path       *path = (Path *) lfirst(l);
     692             : 
     693             :         /*
     694             :          * Since cost comparison is a lot cheaper than pathkey comparison, do
     695             :          * that first.  (XXX is that still true?)
     696             :          */
     697        3258 :         if (matched_path != NULL &&
     698         370 :             compare_fractional_path_costs(matched_path, path, fraction) <= 0)
     699         184 :             continue;
     700             : 
     701        3826 :         if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
     702        1122 :             bms_is_subset(PATH_REQ_OUTER(path), required_outer))
     703        1082 :             matched_path = path;
     704             :     }
     705        1666 :     return matched_path;
     706             : }
     707             : 
     708             : 
     709             : /*
     710             :  * get_cheapest_parallel_safe_total_inner
     711             :  *    Find the unparameterized parallel-safe path with the least total cost.
     712             :  */
     713             : Path *
     714       51512 : get_cheapest_parallel_safe_total_inner(List *paths)
     715             : {
     716             :     ListCell   *l;
     717             : 
     718       58358 :     foreach(l, paths)
     719             :     {
     720       57236 :         Path       *innerpath = (Path *) lfirst(l);
     721             : 
     722       57236 :         if (innerpath->parallel_safe &&
     723       55274 :             bms_is_empty(PATH_REQ_OUTER(innerpath)))
     724       50390 :             return innerpath;
     725             :     }
     726             : 
     727        1122 :     return NULL;
     728             : }
     729             : 
     730             : /****************************************************************************
     731             :  *      NEW PATHKEY FORMATION
     732             :  ****************************************************************************/
     733             : 
     734             : /*
     735             :  * build_index_pathkeys
     736             :  *    Build a pathkeys list that describes the ordering induced by an index
     737             :  *    scan using the given index.  (Note that an unordered index doesn't
     738             :  *    induce any ordering, so we return NIL.)
     739             :  *
     740             :  * If 'scandir' is BackwardScanDirection, build pathkeys representing a
     741             :  * backwards scan of the index.
     742             :  *
     743             :  * We iterate only key columns of covering indexes, since non-key columns
     744             :  * don't influence index ordering.  The result is canonical, meaning that
     745             :  * redundant pathkeys are removed; it may therefore have fewer entries than
     746             :  * there are key columns in the index.
     747             :  *
     748             :  * Another reason for stopping early is that we may be able to tell that
     749             :  * an index column's sort order is uninteresting for this query.  However,
     750             :  * that test is just based on the existence of an EquivalenceClass and not
     751             :  * on position in pathkey lists, so it's not complete.  Caller should call
     752             :  * truncate_useless_pathkeys() to possibly remove more pathkeys.
     753             :  */
     754             : List *
     755     1057740 : build_index_pathkeys(PlannerInfo *root,
     756             :                      IndexOptInfo *index,
     757             :                      ScanDirection scandir)
     758             : {
     759     1057740 :     List       *retval = NIL;
     760             :     ListCell   *lc;
     761             :     int         i;
     762             : 
     763     1057740 :     if (index->sortopfamily == NULL)
     764           0 :         return NIL;             /* non-orderable index */
     765             : 
     766     1057740 :     i = 0;
     767     1873484 :     foreach(lc, index->indextlist)
     768             :     {
     769     1322532 :         TargetEntry *indextle = (TargetEntry *) lfirst(lc);
     770             :         Expr       *indexkey;
     771             :         bool        reverse_sort;
     772             :         bool        nulls_first;
     773             :         PathKey    *cpathkey;
     774             : 
     775             :         /*
     776             :          * INCLUDE columns are stored in index unordered, so they don't
     777             :          * support ordered index scan.
     778             :          */
     779     1322532 :         if (i >= index->nkeycolumns)
     780           0 :             break;
     781             : 
     782             :         /* We assume we don't need to make a copy of the tlist item */
     783     1322532 :         indexkey = indextle->expr;
     784             : 
     785     1322532 :         if (ScanDirectionIsBackward(scandir))
     786             :         {
     787      661266 :             reverse_sort = !index->reverse_sort[i];
     788      661266 :             nulls_first = !index->nulls_first[i];
     789             :         }
     790             :         else
     791             :         {
     792      661266 :             reverse_sort = index->reverse_sort[i];
     793      661266 :             nulls_first = index->nulls_first[i];
     794             :         }
     795             : 
     796             :         /*
     797             :          * OK, try to make a canonical pathkey for this sort key.
     798             :          */
     799     1322532 :         cpathkey = make_pathkey_from_sortinfo(root,
     800             :                                               indexkey,
     801     1322532 :                                               index->sortopfamily[i],
     802     1322532 :                                               index->opcintype[i],
     803     1322532 :                                               index->indexcollations[i],
     804             :                                               reverse_sort,
     805             :                                               nulls_first,
     806             :                                               0,
     807     1322532 :                                               index->rel->relids,
     808             :                                               false);
     809             : 
     810     1322532 :         if (cpathkey)
     811             :         {
     812             :             /*
     813             :              * We found the sort key in an EquivalenceClass, so it's relevant
     814             :              * for this query.  Add it to list, unless it's redundant.
     815             :              */
     816      815636 :             if (!pathkey_is_redundant(cpathkey, retval))
     817      591864 :                 retval = lappend(retval, cpathkey);
     818             :         }
     819             :         else
     820             :         {
     821             :             /*
     822             :              * Boolean index keys might be redundant even if they do not
     823             :              * appear in an EquivalenceClass, because of our special treatment
     824             :              * of boolean equality conditions --- see the comment for
     825             :              * indexcol_is_bool_constant_for_query().  If that applies, we can
     826             :              * continue to examine lower-order index columns.  Otherwise, the
     827             :              * sort key is not an interesting sort order for this query, so we
     828             :              * should stop considering index columns; any lower-order sort
     829             :              * keys won't be useful either.
     830             :              */
     831      506896 :             if (!indexcol_is_bool_constant_for_query(root, index, i))
     832      506788 :                 break;
     833             :         }
     834             : 
     835      815744 :         i++;
     836             :     }
     837             : 
     838     1057740 :     return retval;
     839             : }
     840             : 
     841             : /*
     842             :  * partkey_is_bool_constant_for_query
     843             :  *
     844             :  * If a partition key column is constrained to have a constant value by the
     845             :  * query's WHERE conditions, then it's irrelevant for sort-order
     846             :  * considerations.  Usually that means we have a restriction clause
     847             :  * WHERE partkeycol = constant, which gets turned into an EquivalenceClass
     848             :  * containing a constant, which is recognized as redundant by
     849             :  * build_partition_pathkeys().  But if the partition key column is a
     850             :  * boolean variable (or expression), then we are not going to see such a
     851             :  * WHERE clause, because expression preprocessing will have simplified it
     852             :  * to "WHERE partkeycol" or "WHERE NOT partkeycol".  So we are not going
     853             :  * to have a matching EquivalenceClass (unless the query also contains
     854             :  * "ORDER BY partkeycol").  To allow such cases to work the same as they would
     855             :  * for non-boolean values, this function is provided to detect whether the
     856             :  * specified partition key column matches a boolean restriction clause.
     857             :  */
     858             : static bool
     859       14840 : partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
     860             : {
     861       14840 :     PartitionScheme partscheme = partrel->part_scheme;
     862             :     ListCell   *lc;
     863             : 
     864             :     /*
     865             :      * If the partkey isn't boolean, we can't possibly get a match.
     866             :      *
     867             :      * Partitioning currently can only use built-in AMs, so checking for
     868             :      * built-in boolean opfamilies is good enough.
     869             :      */
     870       14840 :     if (!IsBuiltinBooleanOpfamily(partscheme->partopfamily[partkeycol]))
     871       14360 :         return false;
     872             : 
     873             :     /* Check each restriction clause for the partitioned rel */
     874         792 :     foreach(lc, partrel->baserestrictinfo)
     875             :     {
     876         552 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
     877             : 
     878             :         /* Ignore pseudoconstant quals, they won't match */
     879         552 :         if (rinfo->pseudoconstant)
     880           0 :             continue;
     881             : 
     882             :         /* See if we can match the clause's expression to the partkey column */
     883         552 :         if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
     884         240 :             return true;
     885             :     }
     886             : 
     887         240 :     return false;
     888             : }
     889             : 
     890             : /*
     891             :  * matches_boolean_partition_clause
     892             :  *      Determine if the boolean clause described by rinfo matches
     893             :  *      partrel's partkeycol-th partition key column.
     894             :  *
     895             :  * "Matches" can be either an exact match (equivalent to partkey = true),
     896             :  * or a NOT above an exact match (equivalent to partkey = false).
     897             :  */
     898             : static bool
     899         552 : matches_boolean_partition_clause(RestrictInfo *rinfo,
     900             :                                  RelOptInfo *partrel, int partkeycol)
     901             : {
     902         552 :     Node       *clause = (Node *) rinfo->clause;
     903         552 :     Node       *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
     904             : 
     905             :     /* Direct match? */
     906         552 :     if (equal(partexpr, clause))
     907         120 :         return true;
     908             :     /* NOT clause? */
     909         432 :     else if (is_notclause(clause))
     910             :     {
     911         144 :         Node       *arg = (Node *) get_notclausearg((Expr *) clause);
     912             : 
     913         144 :         if (equal(partexpr, arg))
     914         120 :             return true;
     915             :     }
     916             : 
     917         312 :     return false;
     918             : }
     919             : 
     920             : /*
     921             :  * build_partition_pathkeys
     922             :  *    Build a pathkeys list that describes the ordering induced by the
     923             :  *    partitions of partrel, under either forward or backward scan
     924             :  *    as per scandir.
     925             :  *
     926             :  * Caller must have checked that the partitions are properly ordered,
     927             :  * as detected by partitions_are_ordered().
     928             :  *
     929             :  * Sets *partialkeys to true if pathkeys were only built for a prefix of the
     930             :  * partition key, or false if the pathkeys include all columns of the
     931             :  * partition key.
     932             :  */
     933             : List *
     934       43892 : build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
     935             :                          ScanDirection scandir, bool *partialkeys)
     936             : {
     937       43892 :     List       *retval = NIL;
     938       43892 :     PartitionScheme partscheme = partrel->part_scheme;
     939             :     int         i;
     940             : 
     941             :     Assert(partscheme != NULL);
     942             :     Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
     943             :     /* For now, we can only cope with baserels */
     944             :     Assert(IS_SIMPLE_REL(partrel));
     945             : 
     946       75008 :     for (i = 0; i < partscheme->partnatts; i++)
     947             :     {
     948             :         PathKey    *cpathkey;
     949       45716 :         Expr       *keyCol = (Expr *) linitial(partrel->partexprs[i]);
     950             : 
     951             :         /*
     952             :          * Try to make a canonical pathkey for this partkey.
     953             :          *
     954             :          * We assume the PartitionDesc lists any NULL partition last, so we
     955             :          * treat the scan like a NULLS LAST index: we have nulls_first for
     956             :          * backwards scan only.
     957             :          */
     958       45716 :         cpathkey = make_pathkey_from_sortinfo(root,
     959             :                                               keyCol,
     960       45716 :                                               partscheme->partopfamily[i],
     961       45716 :                                               partscheme->partopcintype[i],
     962       45716 :                                               partscheme->partcollation[i],
     963             :                                               ScanDirectionIsBackward(scandir),
     964             :                                               ScanDirectionIsBackward(scandir),
     965             :                                               0,
     966             :                                               partrel->relids,
     967             :                                               false);
     968             : 
     969             : 
     970       45716 :         if (cpathkey)
     971             :         {
     972             :             /*
     973             :              * We found the sort key in an EquivalenceClass, so it's relevant
     974             :              * for this query.  Add it to list, unless it's redundant.
     975             :              */
     976       30876 :             if (!pathkey_is_redundant(cpathkey, retval))
     977       11188 :                 retval = lappend(retval, cpathkey);
     978             :         }
     979             :         else
     980             :         {
     981             :             /*
     982             :              * Boolean partition keys might be redundant even if they do not
     983             :              * appear in an EquivalenceClass, because of our special treatment
     984             :              * of boolean equality conditions --- see the comment for
     985             :              * partkey_is_bool_constant_for_query().  If that applies, we can
     986             :              * continue to examine lower-order partition keys.  Otherwise, the
     987             :              * sort key is not an interesting sort order for this query, so we
     988             :              * should stop considering partition columns; any lower-order sort
     989             :              * keys won't be useful either.
     990             :              */
     991       14840 :             if (!partkey_is_bool_constant_for_query(partrel, i))
     992             :             {
     993       14600 :                 *partialkeys = true;
     994       14600 :                 return retval;
     995             :             }
     996             :         }
     997             :     }
     998             : 
     999       29292 :     *partialkeys = false;
    1000       29292 :     return retval;
    1001             : }
    1002             : 
    1003             : /*
    1004             :  * build_expression_pathkey
    1005             :  *    Build a pathkeys list that describes an ordering by a single expression
    1006             :  *    using the given sort operator.
    1007             :  *
    1008             :  * expr and rel are as for make_pathkey_from_sortinfo.
    1009             :  * We induce the other arguments assuming default sort order for the operator.
    1010             :  *
    1011             :  * Similarly to make_pathkey_from_sortinfo, the result is NIL if create_it
    1012             :  * is false and the expression isn't already in some EquivalenceClass.
    1013             :  */
    1014             : List *
    1015         680 : build_expression_pathkey(PlannerInfo *root,
    1016             :                          Expr *expr,
    1017             :                          Oid opno,
    1018             :                          Relids rel,
    1019             :                          bool create_it)
    1020             : {
    1021             :     List       *pathkeys;
    1022             :     Oid         opfamily,
    1023             :                 opcintype;
    1024             :     int16       strategy;
    1025             :     PathKey    *cpathkey;
    1026             : 
    1027             :     /* Find the operator in pg_amop --- failure shouldn't happen */
    1028         680 :     if (!get_ordering_op_properties(opno,
    1029             :                                     &opfamily, &opcintype, &strategy))
    1030           0 :         elog(ERROR, "operator %u is not a valid ordering operator",
    1031             :              opno);
    1032             : 
    1033         680 :     cpathkey = make_pathkey_from_sortinfo(root,
    1034             :                                           expr,
    1035             :                                           opfamily,
    1036             :                                           opcintype,
    1037             :                                           exprCollation((Node *) expr),
    1038             :                                           (strategy == BTGreaterStrategyNumber),
    1039             :                                           (strategy == BTGreaterStrategyNumber),
    1040             :                                           0,
    1041             :                                           rel,
    1042             :                                           create_it);
    1043             : 
    1044         680 :     if (cpathkey)
    1045         320 :         pathkeys = list_make1(cpathkey);
    1046             :     else
    1047         360 :         pathkeys = NIL;
    1048             : 
    1049         680 :     return pathkeys;
    1050             : }
    1051             : 
    1052             : /*
    1053             :  * convert_subquery_pathkeys
    1054             :  *    Build a pathkeys list that describes the ordering of a subquery's
    1055             :  *    result, in the terms of the outer query.  This is essentially a
    1056             :  *    task of conversion.
    1057             :  *
    1058             :  * 'rel': outer query's RelOptInfo for the subquery relation.
    1059             :  * 'subquery_pathkeys': the subquery's output pathkeys, in its terms.
    1060             :  * 'subquery_tlist': the subquery's output targetlist, in its terms.
    1061             :  *
    1062             :  * We intentionally don't do truncate_useless_pathkeys() here, because there
    1063             :  * are situations where seeing the raw ordering of the subquery is helpful.
    1064             :  * For example, if it returns ORDER BY x DESC, that may prompt us to
    1065             :  * construct a mergejoin using DESC order rather than ASC order; but the
    1066             :  * right_merge_direction heuristic would have us throw the knowledge away.
    1067             :  */
    1068             : List *
    1069       42510 : convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
    1070             :                           List *subquery_pathkeys,
    1071             :                           List *subquery_tlist)
    1072             : {
    1073       42510 :     List       *retval = NIL;
    1074       42510 :     int         retvallen = 0;
    1075       42510 :     int         outer_query_keys = list_length(root->query_pathkeys);
    1076             :     ListCell   *i;
    1077             : 
    1078       71962 :     foreach(i, subquery_pathkeys)
    1079             :     {
    1080       31950 :         PathKey    *sub_pathkey = (PathKey *) lfirst(i);
    1081       31950 :         EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
    1082       31950 :         PathKey    *best_pathkey = NULL;
    1083             : 
    1084       31950 :         if (sub_eclass->ec_has_volatile)
    1085             :         {
    1086             :             /*
    1087             :              * If the sub_pathkey's EquivalenceClass is volatile, then it must
    1088             :              * have come from an ORDER BY clause, and we have to match it to
    1089             :              * that same targetlist entry.
    1090             :              */
    1091             :             TargetEntry *tle;
    1092             :             Var        *outer_var;
    1093             : 
    1094          84 :             if (sub_eclass->ec_sortref == 0) /* can't happen */
    1095           0 :                 elog(ERROR, "volatile EquivalenceClass has no sortref");
    1096          84 :             tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
    1097             :             Assert(tle);
    1098             :             /* Is TLE actually available to the outer query? */
    1099          84 :             outer_var = find_var_for_subquery_tle(rel, tle);
    1100          84 :             if (outer_var)
    1101             :             {
    1102             :                 /* We can represent this sub_pathkey */
    1103             :                 EquivalenceMember *sub_member;
    1104             :                 EquivalenceClass *outer_ec;
    1105             : 
    1106             :                 Assert(list_length(sub_eclass->ec_members) == 1);
    1107          60 :                 sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
    1108             : 
    1109             :                 /*
    1110             :                  * Note: it might look funny to be setting sortref = 0 for a
    1111             :                  * reference to a volatile sub_eclass.  However, the
    1112             :                  * expression is *not* volatile in the outer query: it's just
    1113             :                  * a Var referencing whatever the subquery emitted. (IOW, the
    1114             :                  * outer query isn't going to re-execute the volatile
    1115             :                  * expression itself.)  So this is okay.
    1116             :                  */
    1117             :                 outer_ec =
    1118          60 :                     get_eclass_for_sort_expr(root,
    1119             :                                              (Expr *) outer_var,
    1120             :                                              sub_eclass->ec_opfamilies,
    1121             :                                              sub_member->em_datatype,
    1122             :                                              sub_eclass->ec_collation,
    1123             :                                              0,
    1124             :                                              rel->relids,
    1125             :                                              false);
    1126             : 
    1127             :                 /*
    1128             :                  * If we don't find a matching EC, sub-pathkey isn't
    1129             :                  * interesting to the outer query
    1130             :                  */
    1131          60 :                 if (outer_ec)
    1132             :                     best_pathkey =
    1133          12 :                         make_canonical_pathkey(root,
    1134             :                                                outer_ec,
    1135             :                                                sub_pathkey->pk_opfamily,
    1136             :                                                sub_pathkey->pk_strategy,
    1137          12 :                                                sub_pathkey->pk_nulls_first);
    1138             :             }
    1139             :         }
    1140             :         else
    1141             :         {
    1142             :             /*
    1143             :              * Otherwise, the sub_pathkey's EquivalenceClass could contain
    1144             :              * multiple elements (representing knowledge that multiple items
    1145             :              * are effectively equal).  Each element might match none, one, or
    1146             :              * more of the output columns that are visible to the outer query.
    1147             :              * This means we may have multiple possible representations of the
    1148             :              * sub_pathkey in the context of the outer query.  Ideally we
    1149             :              * would generate them all and put them all into an EC of the
    1150             :              * outer query, thereby propagating equality knowledge up to the
    1151             :              * outer query.  Right now we cannot do so, because the outer
    1152             :              * query's EquivalenceClasses are already frozen when this is
    1153             :              * called. Instead we prefer the one that has the highest "score"
    1154             :              * (number of EC peers, plus one if it matches the outer
    1155             :              * query_pathkeys). This is the most likely to be useful in the
    1156             :              * outer query.
    1157             :              */
    1158       31866 :             int         best_score = -1;
    1159             :             ListCell   *j;
    1160             : 
    1161       65134 :             foreach(j, sub_eclass->ec_members)
    1162             :             {
    1163       33268 :                 EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
    1164       33268 :                 Expr       *sub_expr = sub_member->em_expr;
    1165       33268 :                 Oid         sub_expr_type = sub_member->em_datatype;
    1166       33268 :                 Oid         sub_expr_coll = sub_eclass->ec_collation;
    1167             :                 ListCell   *k;
    1168             : 
    1169       33268 :                 if (sub_member->em_is_child)
    1170         978 :                     continue;   /* ignore children here */
    1171             : 
    1172      143854 :                 foreach(k, subquery_tlist)
    1173             :                 {
    1174      111564 :                     TargetEntry *tle = (TargetEntry *) lfirst(k);
    1175             :                     Var        *outer_var;
    1176             :                     Expr       *tle_expr;
    1177             :                     EquivalenceClass *outer_ec;
    1178             :                     PathKey    *outer_pk;
    1179             :                     int         score;
    1180             : 
    1181             :                     /* Is TLE actually available to the outer query? */
    1182      111564 :                     outer_var = find_var_for_subquery_tle(rel, tle);
    1183      111564 :                     if (!outer_var)
    1184       38392 :                         continue;
    1185             : 
    1186             :                     /*
    1187             :                      * The targetlist entry is considered to match if it
    1188             :                      * matches after sort-key canonicalization.  That is
    1189             :                      * needed since the sub_expr has been through the same
    1190             :                      * process.
    1191             :                      */
    1192       73172 :                     tle_expr = canonicalize_ec_expression(tle->expr,
    1193             :                                                           sub_expr_type,
    1194             :                                                           sub_expr_coll);
    1195       73172 :                     if (!equal(tle_expr, sub_expr))
    1196       42762 :                         continue;
    1197             : 
    1198             :                     /* See if we have a matching EC for the TLE */
    1199       30410 :                     outer_ec = get_eclass_for_sort_expr(root,
    1200             :                                                         (Expr *) outer_var,
    1201             :                                                         sub_eclass->ec_opfamilies,
    1202             :                                                         sub_expr_type,
    1203             :                                                         sub_expr_coll,
    1204             :                                                         0,
    1205             :                                                         rel->relids,
    1206             :                                                         false);
    1207             : 
    1208             :                     /*
    1209             :                      * If we don't find a matching EC, this sub-pathkey isn't
    1210             :                      * interesting to the outer query
    1211             :                      */
    1212       30410 :                     if (!outer_ec)
    1213         954 :                         continue;
    1214             : 
    1215       29456 :                     outer_pk = make_canonical_pathkey(root,
    1216             :                                                       outer_ec,
    1217             :                                                       sub_pathkey->pk_opfamily,
    1218             :                                                       sub_pathkey->pk_strategy,
    1219       29456 :                                                       sub_pathkey->pk_nulls_first);
    1220             :                     /* score = # of equivalence peers */
    1221       29456 :                     score = list_length(outer_ec->ec_members) - 1;
    1222             :                     /* +1 if it matches the proper query_pathkeys item */
    1223       58732 :                     if (retvallen < outer_query_keys &&
    1224       29276 :                         list_nth(root->query_pathkeys, retvallen) == outer_pk)
    1225       28170 :                         score++;
    1226       29456 :                     if (score > best_score)
    1227             :                     {
    1228       29440 :                         best_pathkey = outer_pk;
    1229       29440 :                         best_score = score;
    1230             :                     }
    1231             :                 }
    1232             :             }
    1233             :         }
    1234             : 
    1235             :         /*
    1236             :          * If we couldn't find a representation of this sub_pathkey, we're
    1237             :          * done (we can't use the ones to its right, either).
    1238             :          */
    1239       31950 :         if (!best_pathkey)
    1240        2498 :             break;
    1241             : 
    1242             :         /*
    1243             :          * Eliminate redundant ordering info; could happen if outer query
    1244             :          * equivalences subquery keys...
    1245             :          */
    1246       29452 :         if (!pathkey_is_redundant(best_pathkey, retval))
    1247             :         {
    1248       29446 :             retval = lappend(retval, best_pathkey);
    1249       29446 :             retvallen++;
    1250             :         }
    1251             :     }
    1252             : 
    1253       42510 :     return retval;
    1254             : }
    1255             : 
    1256             : /*
    1257             :  * find_var_for_subquery_tle
    1258             :  *
    1259             :  * If the given subquery tlist entry is due to be emitted by the subquery's
    1260             :  * scan node, return a Var for it, else return NULL.
    1261             :  *
    1262             :  * We need this to ensure that we don't return pathkeys describing values
    1263             :  * that are unavailable above the level of the subquery scan.
    1264             :  */
    1265             : static Var *
    1266      111648 : find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
    1267             : {
    1268             :     ListCell   *lc;
    1269             : 
    1270             :     /* If the TLE is resjunk, it's certainly not visible to the outer query */
    1271      111648 :     if (tle->resjunk)
    1272           0 :         return NULL;
    1273             : 
    1274             :     /* Search the rel's targetlist to see what it will return */
    1275      344944 :     foreach(lc, rel->reltarget->exprs)
    1276             :     {
    1277      306528 :         Var        *var = (Var *) lfirst(lc);
    1278             : 
    1279             :         /* Ignore placeholders */
    1280      306528 :         if (!IsA(var, Var))
    1281       91636 :             continue;
    1282             :         Assert(var->varno == rel->relid);
    1283             : 
    1284             :         /* If we find a Var referencing this TLE, we're good */
    1285      214892 :         if (var->varattno == tle->resno)
    1286       73232 :             return copyObject(var); /* Make a copy for safety */
    1287             :     }
    1288       38416 :     return NULL;
    1289             : }
    1290             : 
    1291             : /*
    1292             :  * build_join_pathkeys
    1293             :  *    Build the path keys for a join relation constructed by mergejoin or
    1294             :  *    nestloop join.  This is normally the same as the outer path's keys.
    1295             :  *
    1296             :  *    EXCEPTION: in a FULL, RIGHT or RIGHT_ANTI join, we cannot treat the
    1297             :  *    result as having the outer path's path keys, because null lefthand rows
    1298             :  *    may be inserted at random points.  It must be treated as unsorted.
    1299             :  *
    1300             :  *    We truncate away any pathkeys that are uninteresting for higher joins.
    1301             :  *
    1302             :  * 'joinrel' is the join relation that paths are being formed for
    1303             :  * 'jointype' is the join type (inner, left, full, etc)
    1304             :  * 'outer_pathkeys' is the list of the current outer path's path keys
    1305             :  *
    1306             :  * Returns the list of new path keys.
    1307             :  */
    1308             : List *
    1309     1557846 : build_join_pathkeys(PlannerInfo *root,
    1310             :                     RelOptInfo *joinrel,
    1311             :                     JoinType jointype,
    1312             :                     List *outer_pathkeys)
    1313             : {
    1314     1557846 :     if (jointype == JOIN_FULL ||
    1315     1293312 :         jointype == JOIN_RIGHT ||
    1316             :         jointype == JOIN_RIGHT_ANTI)
    1317      278646 :         return NIL;
    1318             : 
    1319             :     /*
    1320             :      * This used to be quite a complex bit of code, but now that all pathkey
    1321             :      * sublists start out life canonicalized, we don't have to do a darn thing
    1322             :      * here!
    1323             :      *
    1324             :      * We do, however, need to truncate the pathkeys list, since it may
    1325             :      * contain pathkeys that were useful for forming this joinrel but are
    1326             :      * uninteresting to higher levels.
    1327             :      */
    1328     1279200 :     return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
    1329             : }
    1330             : 
    1331             : /****************************************************************************
    1332             :  *      PATHKEYS AND SORT CLAUSES
    1333             :  ****************************************************************************/
    1334             : 
    1335             : /*
    1336             :  * make_pathkeys_for_sortclauses
    1337             :  *      Generate a pathkeys list that represents the sort order specified
    1338             :  *      by a list of SortGroupClauses
    1339             :  *
    1340             :  * The resulting PathKeys are always in canonical form.  (Actually, there
    1341             :  * is no longer any code anywhere that creates non-canonical PathKeys.)
    1342             :  *
    1343             :  * 'sortclauses' is a list of SortGroupClause nodes
    1344             :  * 'tlist' is the targetlist to find the referenced tlist entries in
    1345             :  */
    1346             : List *
    1347      502164 : make_pathkeys_for_sortclauses(PlannerInfo *root,
    1348             :                               List *sortclauses,
    1349             :                               List *tlist)
    1350             : {
    1351             :     List       *result;
    1352             :     bool        sortable;
    1353             : 
    1354      502164 :     result = make_pathkeys_for_sortclauses_extended(root,
    1355             :                                                     &sortclauses,
    1356             :                                                     tlist,
    1357             :                                                     false,
    1358             :                                                     &sortable);
    1359             :     /* It's caller error if not all clauses were sortable */
    1360             :     Assert(sortable);
    1361      502164 :     return result;
    1362             : }
    1363             : 
    1364             : /*
    1365             :  * make_pathkeys_for_sortclauses_extended
    1366             :  *      Generate a pathkeys list that represents the sort order specified
    1367             :  *      by a list of SortGroupClauses
    1368             :  *
    1369             :  * The comments for make_pathkeys_for_sortclauses apply here too. In addition:
    1370             :  *
    1371             :  * If remove_redundant is true, then any sort clauses that are found to
    1372             :  * give rise to redundant pathkeys are removed from the sortclauses list
    1373             :  * (which therefore must be pass-by-reference in this version).
    1374             :  *
    1375             :  * *sortable is set to true if all the sort clauses are in fact sortable.
    1376             :  * If any are not, they are ignored except for setting *sortable false.
    1377             :  * (In that case, the output pathkey list isn't really useful.  However,
    1378             :  * we process the whole sortclauses list anyway, because it's still valid
    1379             :  * to remove any clauses that can be proven redundant via the eclass logic.
    1380             :  * Even though we'll have to hash in that case, we might as well not hash
    1381             :  * redundant columns.)
    1382             :  */
    1383             : List *
    1384      520880 : make_pathkeys_for_sortclauses_extended(PlannerInfo *root,
    1385             :                                        List **sortclauses,
    1386             :                                        List *tlist,
    1387             :                                        bool remove_redundant,
    1388             :                                        bool *sortable)
    1389             : {
    1390      520880 :     List       *pathkeys = NIL;
    1391             :     ListCell   *l;
    1392             : 
    1393      520880 :     *sortable = true;
    1394      670952 :     foreach(l, *sortclauses)
    1395             :     {
    1396      150072 :         SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
    1397             :         Expr       *sortkey;
    1398             :         PathKey    *pathkey;
    1399             : 
    1400      150072 :         sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
    1401      150072 :         if (!OidIsValid(sortcl->sortop))
    1402             :         {
    1403         158 :             *sortable = false;
    1404         158 :             continue;
    1405             :         }
    1406      149914 :         pathkey = make_pathkey_from_sortop(root,
    1407             :                                            sortkey,
    1408             :                                            sortcl->sortop,
    1409      149914 :                                            sortcl->nulls_first,
    1410             :                                            sortcl->tleSortGroupRef,
    1411             :                                            true);
    1412             : 
    1413             :         /* Canonical form eliminates redundant ordering keys */
    1414      149914 :         if (!pathkey_is_redundant(pathkey, pathkeys))
    1415      135784 :             pathkeys = lappend(pathkeys, pathkey);
    1416       14130 :         else if (remove_redundant)
    1417         622 :             *sortclauses = foreach_delete_current(*sortclauses, l);
    1418             :     }
    1419      520880 :     return pathkeys;
    1420             : }
    1421             : 
    1422             : /****************************************************************************
    1423             :  *      PATHKEYS AND MERGECLAUSES
    1424             :  ****************************************************************************/
    1425             : 
    1426             : /*
    1427             :  * initialize_mergeclause_eclasses
    1428             :  *      Set the EquivalenceClass links in a mergeclause restrictinfo.
    1429             :  *
    1430             :  * RestrictInfo contains fields in which we may cache pointers to
    1431             :  * EquivalenceClasses for the left and right inputs of the mergeclause.
    1432             :  * (If the mergeclause is a true equivalence clause these will be the
    1433             :  * same EquivalenceClass, otherwise not.)  If the mergeclause is either
    1434             :  * used to generate an EquivalenceClass, or derived from an EquivalenceClass,
    1435             :  * then it's easy to set up the left_ec and right_ec members --- otherwise,
    1436             :  * this function should be called to set them up.  We will generate new
    1437             :  * EquivalenceClauses if necessary to represent the mergeclause's left and
    1438             :  * right sides.
    1439             :  *
    1440             :  * Note this is called before EC merging is complete, so the links won't
    1441             :  * necessarily point to canonical ECs.  Before they are actually used for
    1442             :  * anything, update_mergeclause_eclasses must be called to ensure that
    1443             :  * they've been updated to point to canonical ECs.
    1444             :  */
    1445             : void
    1446       52904 : initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
    1447             : {
    1448       52904 :     Expr       *clause = restrictinfo->clause;
    1449             :     Oid         lefttype,
    1450             :                 righttype;
    1451             : 
    1452             :     /* Should be a mergeclause ... */
    1453             :     Assert(restrictinfo->mergeopfamilies != NIL);
    1454             :     /* ... with links not yet set */
    1455             :     Assert(restrictinfo->left_ec == NULL);
    1456             :     Assert(restrictinfo->right_ec == NULL);
    1457             : 
    1458             :     /* Need the declared input types of the operator */
    1459       52904 :     op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
    1460             : 
    1461             :     /* Find or create a matching EquivalenceClass for each side */
    1462       52904 :     restrictinfo->left_ec =
    1463       52904 :         get_eclass_for_sort_expr(root,
    1464       52904 :                                  (Expr *) get_leftop(clause),
    1465             :                                  restrictinfo->mergeopfamilies,
    1466             :                                  lefttype,
    1467             :                                  ((OpExpr *) clause)->inputcollid,
    1468             :                                  0,
    1469             :                                  NULL,
    1470             :                                  true);
    1471       52904 :     restrictinfo->right_ec =
    1472       52904 :         get_eclass_for_sort_expr(root,
    1473       52904 :                                  (Expr *) get_rightop(clause),
    1474             :                                  restrictinfo->mergeopfamilies,
    1475             :                                  righttype,
    1476             :                                  ((OpExpr *) clause)->inputcollid,
    1477             :                                  0,
    1478             :                                  NULL,
    1479             :                                  true);
    1480       52904 : }
    1481             : 
    1482             : /*
    1483             :  * update_mergeclause_eclasses
    1484             :  *      Make the cached EquivalenceClass links valid in a mergeclause
    1485             :  *      restrictinfo.
    1486             :  *
    1487             :  * These pointers should have been set by process_equivalence or
    1488             :  * initialize_mergeclause_eclasses, but they might have been set to
    1489             :  * non-canonical ECs that got merged later.  Chase up to the canonical
    1490             :  * merged parent if so.
    1491             :  */
    1492             : void
    1493     3972078 : update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
    1494             : {
    1495             :     /* Should be a merge clause ... */
    1496             :     Assert(restrictinfo->mergeopfamilies != NIL);
    1497             :     /* ... with pointers already set */
    1498             :     Assert(restrictinfo->left_ec != NULL);
    1499             :     Assert(restrictinfo->right_ec != NULL);
    1500             : 
    1501             :     /* Chase up to the top as needed */
    1502     3972078 :     while (restrictinfo->left_ec->ec_merged)
    1503           0 :         restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
    1504     3972078 :     while (restrictinfo->right_ec->ec_merged)
    1505           0 :         restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
    1506     3972078 : }
    1507             : 
    1508             : /*
    1509             :  * find_mergeclauses_for_outer_pathkeys
    1510             :  *    This routine attempts to find a list of mergeclauses that can be
    1511             :  *    used with a specified ordering for the join's outer relation.
    1512             :  *    If successful, it returns a list of mergeclauses.
    1513             :  *
    1514             :  * 'pathkeys' is a pathkeys list showing the ordering of an outer-rel path.
    1515             :  * 'restrictinfos' is a list of mergejoinable restriction clauses for the
    1516             :  *          join relation being formed, in no particular order.
    1517             :  *
    1518             :  * The restrictinfos must be marked (via outer_is_left) to show which side
    1519             :  * of each clause is associated with the current outer path.  (See
    1520             :  * select_mergejoin_clauses())
    1521             :  *
    1522             :  * The result is NIL if no merge can be done, else a maximal list of
    1523             :  * usable mergeclauses (represented as a list of their restrictinfo nodes).
    1524             :  * The list is ordered to match the pathkeys, as required for execution.
    1525             :  */
    1526             : List *
    1527     1528500 : find_mergeclauses_for_outer_pathkeys(PlannerInfo *root,
    1528             :                                      List *pathkeys,
    1529             :                                      List *restrictinfos)
    1530             : {
    1531     1528500 :     List       *mergeclauses = NIL;
    1532             :     ListCell   *i;
    1533             : 
    1534             :     /* make sure we have eclasses cached in the clauses */
    1535     3134146 :     foreach(i, restrictinfos)
    1536             :     {
    1537     1605646 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
    1538             : 
    1539     1605646 :         update_mergeclause_eclasses(root, rinfo);
    1540             :     }
    1541             : 
    1542     2458812 :     foreach(i, pathkeys)
    1543             :     {
    1544     1125422 :         PathKey    *pathkey = (PathKey *) lfirst(i);
    1545     1125422 :         EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
    1546     1125422 :         List       *matched_restrictinfos = NIL;
    1547             :         ListCell   *j;
    1548             : 
    1549             :         /*----------
    1550             :          * A mergejoin clause matches a pathkey if it has the same EC.
    1551             :          * If there are multiple matching clauses, take them all.  In plain
    1552             :          * inner-join scenarios we expect only one match, because
    1553             :          * equivalence-class processing will have removed any redundant
    1554             :          * mergeclauses.  However, in outer-join scenarios there might be
    1555             :          * multiple matches.  An example is
    1556             :          *
    1557             :          *  select * from a full join b
    1558             :          *      on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
    1559             :          *
    1560             :          * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
    1561             :          * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
    1562             :          * we *must* do so or we will be unable to form a valid plan.
    1563             :          *
    1564             :          * We expect that the given pathkeys list is canonical, which means
    1565             :          * no two members have the same EC, so it's not possible for this
    1566             :          * code to enter the same mergeclause into the result list twice.
    1567             :          *
    1568             :          * It's possible that multiple matching clauses might have different
    1569             :          * ECs on the other side, in which case the order we put them into our
    1570             :          * result makes a difference in the pathkeys required for the inner
    1571             :          * input rel.  However this routine hasn't got any info about which
    1572             :          * order would be best, so we don't worry about that.
    1573             :          *
    1574             :          * It's also possible that the selected mergejoin clauses produce
    1575             :          * a noncanonical ordering of pathkeys for the inner side, ie, we
    1576             :          * might select clauses that reference b.v1, b.v2, b.v1 in that
    1577             :          * order.  This is not harmful in itself, though it suggests that
    1578             :          * the clauses are partially redundant.  Since the alternative is
    1579             :          * to omit mergejoin clauses and thereby possibly fail to generate a
    1580             :          * plan altogether, we live with it.  make_inner_pathkeys_for_merge()
    1581             :          * has to delete duplicates when it constructs the inner pathkeys
    1582             :          * list, and we also have to deal with such cases specially in
    1583             :          * create_mergejoin_plan().
    1584             :          *----------
    1585             :          */
    1586     2495304 :         foreach(j, restrictinfos)
    1587             :         {
    1588     1369882 :             RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
    1589             :             EquivalenceClass *clause_ec;
    1590             : 
    1591     2739764 :             clause_ec = rinfo->outer_is_left ?
    1592     1369882 :                 rinfo->left_ec : rinfo->right_ec;
    1593     1369882 :             if (clause_ec == pathkey_ec)
    1594      930438 :                 matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
    1595             :         }
    1596             : 
    1597             :         /*
    1598             :          * If we didn't find a mergeclause, we're done --- any additional
    1599             :          * sort-key positions in the pathkeys are useless.  (But we can still
    1600             :          * mergejoin if we found at least one mergeclause.)
    1601             :          */
    1602     1125422 :         if (matched_restrictinfos == NIL)
    1603      195110 :             break;
    1604             : 
    1605             :         /*
    1606             :          * If we did find usable mergeclause(s) for this sort-key position,
    1607             :          * add them to result list.
    1608             :          */
    1609      930312 :         mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
    1610             :     }
    1611             : 
    1612     1528500 :     return mergeclauses;
    1613             : }
    1614             : 
    1615             : /*
    1616             :  * select_outer_pathkeys_for_merge
    1617             :  *    Builds a pathkey list representing a possible sort ordering
    1618             :  *    that can be used with the given mergeclauses.
    1619             :  *
    1620             :  * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
    1621             :  *          that will be used in a merge join.
    1622             :  * 'joinrel' is the join relation we are trying to construct.
    1623             :  *
    1624             :  * The restrictinfos must be marked (via outer_is_left) to show which side
    1625             :  * of each clause is associated with the current outer path.  (See
    1626             :  * select_mergejoin_clauses())
    1627             :  *
    1628             :  * Returns a pathkeys list that can be applied to the outer relation.
    1629             :  *
    1630             :  * Since we assume here that a sort is required, there is no particular use
    1631             :  * in matching any available ordering of the outerrel.  (joinpath.c has an
    1632             :  * entirely separate code path for considering sort-free mergejoins.)  Rather,
    1633             :  * it's interesting to try to match, or match a prefix of the requested
    1634             :  * query_pathkeys so that a second output sort may be avoided or an
    1635             :  * incremental sort may be done instead.  We can get away with just a prefix
    1636             :  * of the query_pathkeys when that prefix covers the entire join condition.
    1637             :  * Failing that, we try to list "more popular" keys  (those with the most
    1638             :  * unmatched EquivalenceClass peers) earlier, in hopes of making the resulting
    1639             :  * ordering useful for as many higher-level mergejoins as possible.
    1640             :  */
    1641             : List *
    1642      530800 : select_outer_pathkeys_for_merge(PlannerInfo *root,
    1643             :                                 List *mergeclauses,
    1644             :                                 RelOptInfo *joinrel)
    1645             : {
    1646      530800 :     List       *pathkeys = NIL;
    1647      530800 :     int         nClauses = list_length(mergeclauses);
    1648             :     EquivalenceClass **ecs;
    1649             :     int        *scores;
    1650             :     int         necs;
    1651             :     ListCell   *lc;
    1652             :     int         j;
    1653             : 
    1654             :     /* Might have no mergeclauses */
    1655      530800 :     if (nClauses == 0)
    1656       90290 :         return NIL;
    1657             : 
    1658             :     /*
    1659             :      * Make arrays of the ECs used by the mergeclauses (dropping any
    1660             :      * duplicates) and their "popularity" scores.
    1661             :      */
    1662      440510 :     ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
    1663      440510 :     scores = (int *) palloc(nClauses * sizeof(int));
    1664      440510 :     necs = 0;
    1665             : 
    1666      924212 :     foreach(lc, mergeclauses)
    1667             :     {
    1668      483702 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1669             :         EquivalenceClass *oeclass;
    1670             :         int         score;
    1671             :         ListCell   *lc2;
    1672             : 
    1673             :         /* get the outer eclass */
    1674      483702 :         update_mergeclause_eclasses(root, rinfo);
    1675             : 
    1676      483702 :         if (rinfo->outer_is_left)
    1677      243132 :             oeclass = rinfo->left_ec;
    1678             :         else
    1679      240570 :             oeclass = rinfo->right_ec;
    1680             : 
    1681             :         /* reject duplicates */
    1682      529158 :         for (j = 0; j < necs; j++)
    1683             :         {
    1684       45528 :             if (ecs[j] == oeclass)
    1685          72 :                 break;
    1686             :         }
    1687      483702 :         if (j < necs)
    1688          72 :             continue;
    1689             : 
    1690             :         /* compute score */
    1691      483630 :         score = 0;
    1692     1462330 :         foreach(lc2, oeclass->ec_members)
    1693             :         {
    1694      978700 :             EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
    1695             : 
    1696             :             /* Potential future join partner? */
    1697      978700 :             if (!em->em_is_const && !em->em_is_child &&
    1698      854296 :                 !bms_overlap(em->em_relids, joinrel->relids))
    1699       62466 :                 score++;
    1700             :         }
    1701             : 
    1702      483630 :         ecs[necs] = oeclass;
    1703      483630 :         scores[necs] = score;
    1704      483630 :         necs++;
    1705             :     }
    1706             : 
    1707             :     /*
    1708             :      * Find out if we have all the ECs mentioned in query_pathkeys; if so we
    1709             :      * can generate a sort order that's also useful for final output. If we
    1710             :      * only have a prefix of the query_pathkeys, and that prefix is the entire
    1711             :      * join condition, then it's useful to use the prefix as the pathkeys as
    1712             :      * this increases the chances that an incremental sort will be able to be
    1713             :      * used by the upper planner.
    1714             :      */
    1715      440510 :     if (root->query_pathkeys)
    1716             :     {
    1717      292054 :         int         matches = 0;
    1718             : 
    1719      360200 :         foreach(lc, root->query_pathkeys)
    1720             :         {
    1721      346994 :             PathKey    *query_pathkey = (PathKey *) lfirst(lc);
    1722      346994 :             EquivalenceClass *query_ec = query_pathkey->pk_eclass;
    1723             : 
    1724      660820 :             for (j = 0; j < necs; j++)
    1725             :             {
    1726      381972 :                 if (ecs[j] == query_ec)
    1727       68146 :                     break;      /* found match */
    1728             :             }
    1729      346994 :             if (j >= necs)
    1730      278848 :                 break;          /* didn't find match */
    1731             : 
    1732       68146 :             matches++;
    1733             :         }
    1734             :         /* if we got to the end of the list, we have them all */
    1735      292054 :         if (lc == NULL)
    1736             :         {
    1737             :             /* copy query_pathkeys as starting point for our output */
    1738       13206 :             pathkeys = list_copy(root->query_pathkeys);
    1739             :             /* mark their ECs as already-emitted */
    1740       27086 :             foreach(lc, root->query_pathkeys)
    1741             :             {
    1742       13880 :                 PathKey    *query_pathkey = (PathKey *) lfirst(lc);
    1743       13880 :                 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
    1744             : 
    1745       14620 :                 for (j = 0; j < necs; j++)
    1746             :                 {
    1747       14620 :                     if (ecs[j] == query_ec)
    1748             :                     {
    1749       13880 :                         scores[j] = -1;
    1750       13880 :                         break;
    1751             :                     }
    1752             :                 }
    1753             :             }
    1754             :         }
    1755             : 
    1756             :         /*
    1757             :          * If we didn't match to all of the query_pathkeys, but did match to
    1758             :          * all of the join clauses then we'll make use of these as partially
    1759             :          * sorted input is better than nothing for the upper planner as it may
    1760             :          * lead to incremental sorts instead of full sorts.
    1761             :          */
    1762      278848 :         else if (matches == nClauses)
    1763             :         {
    1764       43508 :             pathkeys = list_copy_head(root->query_pathkeys, matches);
    1765             : 
    1766             :             /* we have all of the join pathkeys, so nothing more to do */
    1767       43508 :             pfree(ecs);
    1768       43508 :             pfree(scores);
    1769             : 
    1770       43508 :             return pathkeys;
    1771             :         }
    1772             :     }
    1773             : 
    1774             :     /*
    1775             :      * Add remaining ECs to the list in popularity order, using a default sort
    1776             :      * ordering.  (We could use qsort() here, but the list length is usually
    1777             :      * so small it's not worth it.)
    1778             :      */
    1779             :     for (;;)
    1780      426230 :     {
    1781             :         int         best_j;
    1782             :         int         best_score;
    1783             :         EquivalenceClass *ec;
    1784             :         PathKey    *pathkey;
    1785             : 
    1786      823232 :         best_j = 0;
    1787      823232 :         best_score = scores[0];
    1788      953252 :         for (j = 1; j < necs; j++)
    1789             :         {
    1790      130020 :             if (scores[j] > best_score)
    1791             :             {
    1792       42374 :                 best_j = j;
    1793       42374 :                 best_score = scores[j];
    1794             :             }
    1795             :         }
    1796      823232 :         if (best_score < 0)
    1797      397002 :             break;              /* all done */
    1798      426230 :         ec = ecs[best_j];
    1799      426230 :         scores[best_j] = -1;
    1800      426230 :         pathkey = make_canonical_pathkey(root,
    1801             :                                          ec,
    1802      426230 :                                          linitial_oid(ec->ec_opfamilies),
    1803             :                                          BTLessStrategyNumber,
    1804             :                                          false);
    1805             :         /* can't be redundant because no duplicate ECs */
    1806             :         Assert(!pathkey_is_redundant(pathkey, pathkeys));
    1807      426230 :         pathkeys = lappend(pathkeys, pathkey);
    1808             :     }
    1809             : 
    1810      397002 :     pfree(ecs);
    1811      397002 :     pfree(scores);
    1812             : 
    1813      397002 :     return pathkeys;
    1814             : }
    1815             : 
    1816             : /*
    1817             :  * make_inner_pathkeys_for_merge
    1818             :  *    Builds a pathkey list representing the explicit sort order that
    1819             :  *    must be applied to an inner path to make it usable with the
    1820             :  *    given mergeclauses.
    1821             :  *
    1822             :  * 'mergeclauses' is a list of RestrictInfos for the mergejoin clauses
    1823             :  *          that will be used in a merge join, in order.
    1824             :  * 'outer_pathkeys' are the already-known canonical pathkeys for the outer
    1825             :  *          side of the join.
    1826             :  *
    1827             :  * The restrictinfos must be marked (via outer_is_left) to show which side
    1828             :  * of each clause is associated with the current outer path.  (See
    1829             :  * select_mergejoin_clauses())
    1830             :  *
    1831             :  * Returns a pathkeys list that can be applied to the inner relation.
    1832             :  *
    1833             :  * Note that it is not this routine's job to decide whether sorting is
    1834             :  * actually needed for a particular input path.  Assume a sort is necessary;
    1835             :  * just make the keys, eh?
    1836             :  */
    1837             : List *
    1838      820618 : make_inner_pathkeys_for_merge(PlannerInfo *root,
    1839             :                               List *mergeclauses,
    1840             :                               List *outer_pathkeys)
    1841             : {
    1842      820618 :     List       *pathkeys = NIL;
    1843             :     EquivalenceClass *lastoeclass;
    1844             :     PathKey    *opathkey;
    1845             :     ListCell   *lc;
    1846             :     ListCell   *lop;
    1847             : 
    1848      820618 :     lastoeclass = NULL;
    1849      820618 :     opathkey = NULL;
    1850      820618 :     lop = list_head(outer_pathkeys);
    1851             : 
    1852     1742972 :     foreach(lc, mergeclauses)
    1853             :     {
    1854      922354 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1855             :         EquivalenceClass *oeclass;
    1856             :         EquivalenceClass *ieclass;
    1857             :         PathKey    *pathkey;
    1858             : 
    1859      922354 :         update_mergeclause_eclasses(root, rinfo);
    1860             : 
    1861      922354 :         if (rinfo->outer_is_left)
    1862             :         {
    1863      479912 :             oeclass = rinfo->left_ec;
    1864      479912 :             ieclass = rinfo->right_ec;
    1865             :         }
    1866             :         else
    1867             :         {
    1868      442442 :             oeclass = rinfo->right_ec;
    1869      442442 :             ieclass = rinfo->left_ec;
    1870             :         }
    1871             : 
    1872             :         /* outer eclass should match current or next pathkeys */
    1873             :         /* we check this carefully for debugging reasons */
    1874      922354 :         if (oeclass != lastoeclass)
    1875             :         {
    1876      922240 :             if (!lop)
    1877           0 :                 elog(ERROR, "too few pathkeys for mergeclauses");
    1878      922240 :             opathkey = (PathKey *) lfirst(lop);
    1879      922240 :             lop = lnext(outer_pathkeys, lop);
    1880      922240 :             lastoeclass = opathkey->pk_eclass;
    1881      922240 :             if (oeclass != lastoeclass)
    1882           0 :                 elog(ERROR, "outer pathkeys do not match mergeclause");
    1883             :         }
    1884             : 
    1885             :         /*
    1886             :          * Often, we'll have same EC on both sides, in which case the outer
    1887             :          * pathkey is also canonical for the inner side, and we can skip a
    1888             :          * useless search.
    1889             :          */
    1890      922354 :         if (ieclass == oeclass)
    1891      544634 :             pathkey = opathkey;
    1892             :         else
    1893      377720 :             pathkey = make_canonical_pathkey(root,
    1894             :                                              ieclass,
    1895             :                                              opathkey->pk_opfamily,
    1896             :                                              opathkey->pk_strategy,
    1897      377720 :                                              opathkey->pk_nulls_first);
    1898             : 
    1899             :         /*
    1900             :          * Don't generate redundant pathkeys (which can happen if multiple
    1901             :          * mergeclauses refer to the same EC).  Because we do this, the output
    1902             :          * pathkey list isn't necessarily ordered like the mergeclauses, which
    1903             :          * complicates life for create_mergejoin_plan().  But if we didn't,
    1904             :          * we'd have a noncanonical sort key list, which would be bad; for one
    1905             :          * reason, it certainly wouldn't match any available sort order for
    1906             :          * the input relation.
    1907             :          */
    1908      922354 :         if (!pathkey_is_redundant(pathkey, pathkeys))
    1909      922180 :             pathkeys = lappend(pathkeys, pathkey);
    1910             :     }
    1911             : 
    1912      820618 :     return pathkeys;
    1913             : }
    1914             : 
    1915             : /*
    1916             :  * trim_mergeclauses_for_inner_pathkeys
    1917             :  *    This routine trims a list of mergeclauses to include just those that
    1918             :  *    work with a specified ordering for the join's inner relation.
    1919             :  *
    1920             :  * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses for the
    1921             :  *          join relation being formed, in an order known to work for the
    1922             :  *          currently-considered sort ordering of the join's outer rel.
    1923             :  * 'pathkeys' is a pathkeys list showing the ordering of an inner-rel path;
    1924             :  *          it should be equal to, or a truncation of, the result of
    1925             :  *          make_inner_pathkeys_for_merge for these mergeclauses.
    1926             :  *
    1927             :  * What we return will be a prefix of the given mergeclauses list.
    1928             :  *
    1929             :  * We need this logic because make_inner_pathkeys_for_merge's result isn't
    1930             :  * necessarily in the same order as the mergeclauses.  That means that if we
    1931             :  * consider an inner-rel pathkey list that is a truncation of that result,
    1932             :  * we might need to drop mergeclauses even though they match a surviving inner
    1933             :  * pathkey.  This happens when they are to the right of a mergeclause that
    1934             :  * matches a removed inner pathkey.
    1935             :  *
    1936             :  * The mergeclauses must be marked (via outer_is_left) to show which side
    1937             :  * of each clause is associated with the current outer path.  (See
    1938             :  * select_mergejoin_clauses())
    1939             :  */
    1940             : List *
    1941        2550 : trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root,
    1942             :                                      List *mergeclauses,
    1943             :                                      List *pathkeys)
    1944             : {
    1945        2550 :     List       *new_mergeclauses = NIL;
    1946             :     PathKey    *pathkey;
    1947             :     EquivalenceClass *pathkey_ec;
    1948             :     bool        matched_pathkey;
    1949             :     ListCell   *lip;
    1950             :     ListCell   *i;
    1951             : 
    1952             :     /* No pathkeys => no mergeclauses (though we don't expect this case) */
    1953        2550 :     if (pathkeys == NIL)
    1954           0 :         return NIL;
    1955             :     /* Initialize to consider first pathkey */
    1956        2550 :     lip = list_head(pathkeys);
    1957        2550 :     pathkey = (PathKey *) lfirst(lip);
    1958        2550 :     pathkey_ec = pathkey->pk_eclass;
    1959        2550 :     lip = lnext(pathkeys, lip);
    1960        2550 :     matched_pathkey = false;
    1961             : 
    1962             :     /* Scan mergeclauses to see how many we can use */
    1963        5100 :     foreach(i, mergeclauses)
    1964             :     {
    1965        5100 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
    1966             :         EquivalenceClass *clause_ec;
    1967             : 
    1968             :         /* Assume we needn't do update_mergeclause_eclasses again here */
    1969             : 
    1970             :         /* Check clause's inner-rel EC against current pathkey */
    1971       10200 :         clause_ec = rinfo->outer_is_left ?
    1972        5100 :             rinfo->right_ec : rinfo->left_ec;
    1973             : 
    1974             :         /* If we don't have a match, attempt to advance to next pathkey */
    1975        5100 :         if (clause_ec != pathkey_ec)
    1976             :         {
    1977             :             /* If we had no clauses matching this inner pathkey, must stop */
    1978        2550 :             if (!matched_pathkey)
    1979           0 :                 break;
    1980             : 
    1981             :             /* Advance to next inner pathkey, if any */
    1982        2550 :             if (lip == NULL)
    1983        2550 :                 break;
    1984           0 :             pathkey = (PathKey *) lfirst(lip);
    1985           0 :             pathkey_ec = pathkey->pk_eclass;
    1986           0 :             lip = lnext(pathkeys, lip);
    1987           0 :             matched_pathkey = false;
    1988             :         }
    1989             : 
    1990             :         /* If mergeclause matches current inner pathkey, we can use it */
    1991        2550 :         if (clause_ec == pathkey_ec)
    1992             :         {
    1993        2550 :             new_mergeclauses = lappend(new_mergeclauses, rinfo);
    1994        2550 :             matched_pathkey = true;
    1995             :         }
    1996             :         else
    1997             :         {
    1998             :             /* Else, no hope of adding any more mergeclauses */
    1999           0 :             break;
    2000             :         }
    2001             :     }
    2002             : 
    2003        2550 :     return new_mergeclauses;
    2004             : }
    2005             : 
    2006             : 
    2007             : /****************************************************************************
    2008             :  *      PATHKEY USEFULNESS CHECKS
    2009             :  *
    2010             :  * We only want to remember as many of the pathkeys of a path as have some
    2011             :  * potential use, either for subsequent mergejoins or for meeting the query's
    2012             :  * requested output ordering.  This ensures that add_path() won't consider
    2013             :  * a path to have a usefully different ordering unless it really is useful.
    2014             :  * These routines check for usefulness of given pathkeys.
    2015             :  ****************************************************************************/
    2016             : 
    2017             : /*
    2018             :  * pathkeys_useful_for_merging
    2019             :  *      Count the number of pathkeys that may be useful for mergejoins
    2020             :  *      above the given relation.
    2021             :  *
    2022             :  * We consider a pathkey potentially useful if it corresponds to the merge
    2023             :  * ordering of either side of any joinclause for the rel.  This might be
    2024             :  * overoptimistic, since joinclauses that require different other relations
    2025             :  * might never be usable at the same time, but trying to be exact is likely
    2026             :  * to be more trouble than it's worth.
    2027             :  *
    2028             :  * To avoid doubling the number of mergejoin paths considered, we would like
    2029             :  * to consider only one of the two scan directions (ASC or DESC) as useful
    2030             :  * for merging for any given target column.  The choice is arbitrary unless
    2031             :  * one of the directions happens to match an ORDER BY key, in which case
    2032             :  * that direction should be preferred, in hopes of avoiding a final sort step.
    2033             :  * right_merge_direction() implements this heuristic.
    2034             :  */
    2035             : static int
    2036     2336940 : pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
    2037             : {
    2038     2336940 :     int         useful = 0;
    2039             :     ListCell   *i;
    2040             : 
    2041     2860976 :     foreach(i, pathkeys)
    2042             :     {
    2043     1420974 :         PathKey    *pathkey = (PathKey *) lfirst(i);
    2044     1420974 :         bool        matched = false;
    2045             :         ListCell   *j;
    2046             : 
    2047             :         /* If "wrong" direction, not useful for merging */
    2048     1420974 :         if (!right_merge_direction(root, pathkey))
    2049      268556 :             break;
    2050             : 
    2051             :         /*
    2052             :          * First look into the EquivalenceClass of the pathkey, to see if
    2053             :          * there are any members not yet joined to the rel.  If so, it's
    2054             :          * surely possible to generate a mergejoin clause using them.
    2055             :          */
    2056     1762462 :         if (rel->has_eclass_joins &&
    2057      610044 :             eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
    2058      338624 :             matched = true;
    2059             :         else
    2060             :         {
    2061             :             /*
    2062             :              * Otherwise search the rel's joininfo list, which contains
    2063             :              * non-EquivalenceClass-derivable join clauses that might
    2064             :              * nonetheless be mergejoinable.
    2065             :              */
    2066     1240926 :             foreach(j, rel->joininfo)
    2067             :             {
    2068      612544 :                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
    2069             : 
    2070      612544 :                 if (restrictinfo->mergeopfamilies == NIL)
    2071      146100 :                     continue;
    2072      466444 :                 update_mergeclause_eclasses(root, restrictinfo);
    2073             : 
    2074      466444 :                 if (pathkey->pk_eclass == restrictinfo->left_ec ||
    2075      379224 :                     pathkey->pk_eclass == restrictinfo->right_ec)
    2076             :                 {
    2077      185412 :                     matched = true;
    2078      185412 :                     break;
    2079             :                 }
    2080             :             }
    2081             :         }
    2082             : 
    2083             :         /*
    2084             :          * If we didn't find a mergeclause, we're done --- any additional
    2085             :          * sort-key positions in the pathkeys are useless.  (But we can still
    2086             :          * mergejoin if we found at least one mergeclause.)
    2087             :          */
    2088     1152418 :         if (matched)
    2089      524036 :             useful++;
    2090             :         else
    2091      628382 :             break;
    2092             :     }
    2093             : 
    2094     2336940 :     return useful;
    2095             : }
    2096             : 
    2097             : /*
    2098             :  * right_merge_direction
    2099             :  *      Check whether the pathkey embodies the preferred sort direction
    2100             :  *      for merging its target column.
    2101             :  */
    2102             : static bool
    2103     1420974 : right_merge_direction(PlannerInfo *root, PathKey *pathkey)
    2104             : {
    2105             :     ListCell   *l;
    2106             : 
    2107     2802948 :     foreach(l, root->query_pathkeys)
    2108             :     {
    2109     1755868 :         PathKey    *query_pathkey = (PathKey *) lfirst(l);
    2110             : 
    2111     1755868 :         if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
    2112      373894 :             pathkey->pk_opfamily == query_pathkey->pk_opfamily)
    2113             :         {
    2114             :             /*
    2115             :              * Found a matching query sort column.  Prefer this pathkey's
    2116             :              * direction iff it matches.  Note that we ignore pk_nulls_first,
    2117             :              * which means that a sort might be needed anyway ... but we still
    2118             :              * want to prefer only one of the two possible directions, and we
    2119             :              * might as well use this one.
    2120             :              */
    2121      373894 :             return (pathkey->pk_strategy == query_pathkey->pk_strategy);
    2122             :         }
    2123             :     }
    2124             : 
    2125             :     /* If no matching ORDER BY request, prefer the ASC direction */
    2126     1047080 :     return (pathkey->pk_strategy == BTLessStrategyNumber);
    2127             : }
    2128             : 
    2129             : /*
    2130             :  * pathkeys_useful_for_ordering
    2131             :  *      Count the number of pathkeys that are useful for meeting the
    2132             :  *      query's requested output ordering.
    2133             :  *
    2134             :  * Because we the have the possibility of incremental sort, a prefix list of
    2135             :  * keys is potentially useful for improving the performance of the requested
    2136             :  * ordering. Thus we return 0, if no valuable keys are found, or the number
    2137             :  * of leading keys shared by the list and the requested ordering..
    2138             :  */
    2139             : static int
    2140     2336940 : pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
    2141             : {
    2142             :     int         n_common_pathkeys;
    2143             : 
    2144     2336940 :     (void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys,
    2145             :                                        &n_common_pathkeys);
    2146             : 
    2147     2336940 :     return n_common_pathkeys;
    2148             : }
    2149             : 
    2150             : /*
    2151             :  * pathkeys_useful_for_grouping
    2152             :  *      Count the number of pathkeys that are useful for grouping (instead of
    2153             :  *      explicit sort)
    2154             :  *
    2155             :  * Group pathkeys could be reordered to benefit from the ordering. The
    2156             :  * ordering may not be "complete" and may require incremental sort, but that's
    2157             :  * fine. So we simply count prefix pathkeys with a matching group key, and
    2158             :  * stop once we find the first pathkey without a match.
    2159             :  *
    2160             :  * So e.g. with pathkeys (a,b,c) and group keys (a,b,e) this determines (a,b)
    2161             :  * pathkeys are useful for grouping, and we might do incremental sort to get
    2162             :  * path ordered by (a,b,e).
    2163             :  *
    2164             :  * This logic is necessary to retain paths with ordering not matching grouping
    2165             :  * keys directly, without the reordering.
    2166             :  *
    2167             :  * Returns the length of pathkey prefix with matching group keys.
    2168             :  */
    2169             : static int
    2170     2336940 : pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
    2171             : {
    2172             :     ListCell   *key;
    2173     2336940 :     int         n = 0;
    2174             : 
    2175             :     /* no special ordering requested for grouping */
    2176     2336940 :     if (root->group_pathkeys == NIL)
    2177     2314316 :         return 0;
    2178             : 
    2179             :     /* walk the pathkeys and search for matching group key */
    2180       27948 :     foreach(key, pathkeys)
    2181             :     {
    2182       10984 :         PathKey    *pathkey = (PathKey *) lfirst(key);
    2183             : 
    2184             :         /* no matching group key, we're done */
    2185       10984 :         if (!list_member_ptr(root->group_pathkeys, pathkey))
    2186        5660 :             break;
    2187             : 
    2188        5324 :         n++;
    2189             :     }
    2190             : 
    2191       22624 :     return n;
    2192             : }
    2193             : 
    2194             : /*
    2195             :  * pathkeys_useful_for_setop
    2196             :  *      Count the number of leading common pathkeys root's 'setop_pathkeys' in
    2197             :  *      'pathkeys'.
    2198             :  */
    2199             : static int
    2200     2336940 : pathkeys_useful_for_setop(PlannerInfo *root, List *pathkeys)
    2201             : {
    2202             :     int         n_common_pathkeys;
    2203             : 
    2204     2336940 :     (void) pathkeys_count_contained_in(root->setop_pathkeys, pathkeys,
    2205             :                                        &n_common_pathkeys);
    2206             : 
    2207     2336940 :     return n_common_pathkeys;
    2208             : }
    2209             : 
    2210             : /*
    2211             :  * truncate_useless_pathkeys
    2212             :  *      Shorten the given pathkey list to just the useful pathkeys.
    2213             :  */
    2214             : List *
    2215     2336940 : truncate_useless_pathkeys(PlannerInfo *root,
    2216             :                           RelOptInfo *rel,
    2217             :                           List *pathkeys)
    2218             : {
    2219             :     int         nuseful;
    2220             :     int         nuseful2;
    2221             : 
    2222     2336940 :     nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
    2223     2336940 :     nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
    2224     2336940 :     if (nuseful2 > nuseful)
    2225      160194 :         nuseful = nuseful2;
    2226     2336940 :     nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
    2227     2336940 :     if (nuseful2 > nuseful)
    2228         242 :         nuseful = nuseful2;
    2229     2336940 :     nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
    2230     2336940 :     if (nuseful2 > nuseful)
    2231           0 :         nuseful = nuseful2;
    2232             : 
    2233             :     /*
    2234             :      * Note: not safe to modify input list destructively, but we can avoid
    2235             :      * copying the list if we're not actually going to change it
    2236             :      */
    2237     2336940 :     if (nuseful == 0)
    2238     1700628 :         return NIL;
    2239      636312 :     else if (nuseful == list_length(pathkeys))
    2240      606824 :         return pathkeys;
    2241             :     else
    2242       29488 :         return list_copy_head(pathkeys, nuseful);
    2243             : }
    2244             : 
    2245             : /*
    2246             :  * has_useful_pathkeys
    2247             :  *      Detect whether the specified rel could have any pathkeys that are
    2248             :  *      useful according to truncate_useless_pathkeys().
    2249             :  *
    2250             :  * This is a cheap test that lets us skip building pathkeys at all in very
    2251             :  * simple queries.  It's OK to err in the direction of returning "true" when
    2252             :  * there really aren't any usable pathkeys, but erring in the other direction
    2253             :  * is bad --- so keep this in sync with the routines above!
    2254             :  *
    2255             :  * We could make the test more complex, for example checking to see if any of
    2256             :  * the joinclauses are really mergejoinable, but that likely wouldn't win
    2257             :  * often enough to repay the extra cycles.  Queries with neither a join nor
    2258             :  * a sort are reasonably common, though, so this much work seems worthwhile.
    2259             :  */
    2260             : bool
    2261      752438 : has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel)
    2262             : {
    2263      752438 :     if (rel->joininfo != NIL || rel->has_eclass_joins)
    2264      470906 :         return true;            /* might be able to use pathkeys for merging */
    2265      281532 :     if (root->group_pathkeys != NIL)
    2266        5512 :         return true;            /* might be able to use pathkeys for grouping */
    2267      276020 :     if (root->query_pathkeys != NIL)
    2268       70078 :         return true;            /* might be able to use them for ordering */
    2269      205942 :     return false;               /* definitely useless */
    2270             : }

Generated by: LCOV version 1.14