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