granicus.if.org Git - postgresql/blob - src/backend/optimizer/path/pathkeys.c

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