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

Generated by: LCOV version 1.13