Header And Logo

PostgreSQL
| The world's most advanced open source database.

pathkeys.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * pathkeys.c
00004  *    Utilities for matching and building path keys
00005  *
00006  * See src/backend/optimizer/README for a great deal of information about
00007  * the nature and use of path keys.
00008  *
00009  *
00010  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00011  * Portions Copyright (c) 1994, Regents of the University of California
00012  *
00013  * IDENTIFICATION
00014  *    src/backend/optimizer/path/pathkeys.c
00015  *
00016  *-------------------------------------------------------------------------
00017  */
00018 #include "postgres.h"
00019 
00020 #include "access/skey.h"
00021 #include "nodes/makefuncs.h"
00022 #include "nodes/nodeFuncs.h"
00023 #include "nodes/plannodes.h"
00024 #include "optimizer/clauses.h"
00025 #include "optimizer/pathnode.h"
00026 #include "optimizer/paths.h"
00027 #include "optimizer/tlist.h"
00028 #include "utils/lsyscache.h"
00029 
00030 
00031 static PathKey *make_canonical_pathkey(PlannerInfo *root,
00032                        EquivalenceClass *eclass, Oid opfamily,
00033                        int strategy, bool nulls_first);
00034 static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
00035 static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
00036 
00037 
00038 /****************************************************************************
00039  *      PATHKEY CONSTRUCTION AND REDUNDANCY TESTING
00040  ****************************************************************************/
00041 
00042 /*
00043  * make_canonical_pathkey
00044  *    Given the parameters for a PathKey, find any pre-existing matching
00045  *    pathkey in the query's list of "canonical" pathkeys.  Make a new
00046  *    entry if there's not one already.
00047  *
00048  * Note that this function must not be used until after we have completed
00049  * merging EquivalenceClasses.  (We don't try to enforce that here; instead,
00050  * equivclass.c will complain if a merge occurs after root->canon_pathkeys
00051  * has become nonempty.)
00052  */
00053 static PathKey *
00054 make_canonical_pathkey(PlannerInfo *root,
00055                        EquivalenceClass *eclass, Oid opfamily,
00056                        int strategy, bool nulls_first)
00057 {
00058     PathKey    *pk;
00059     ListCell   *lc;
00060     MemoryContext oldcontext;
00061 
00062     /* The passed eclass might be non-canonical, so chase up to the top */
00063     while (eclass->ec_merged)
00064         eclass = eclass->ec_merged;
00065 
00066     foreach(lc, root->canon_pathkeys)
00067     {
00068         pk = (PathKey *) lfirst(lc);
00069         if (eclass == pk->pk_eclass &&
00070             opfamily == pk->pk_opfamily &&
00071             strategy == pk->pk_strategy &&
00072             nulls_first == pk->pk_nulls_first)
00073             return pk;
00074     }
00075 
00076     /*
00077      * Be sure canonical pathkeys are allocated in the main planning context.
00078      * Not an issue in normal planning, but it is for GEQO.
00079      */
00080     oldcontext = MemoryContextSwitchTo(root->planner_cxt);
00081 
00082     pk = makeNode(PathKey);
00083     pk->pk_eclass = eclass;
00084     pk->pk_opfamily = opfamily;
00085     pk->pk_strategy = strategy;
00086     pk->pk_nulls_first = nulls_first;
00087 
00088     root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
00089 
00090     MemoryContextSwitchTo(oldcontext);
00091 
00092     return pk;
00093 }
00094 
00095 /*
00096  * pathkey_is_redundant
00097  *     Is a pathkey redundant with one already in the given list?
00098  *
00099  * We detect two cases:
00100  *
00101  * 1. If the new pathkey's equivalence class contains a constant, and isn't
00102  * below an outer join, then we can disregard it as a sort key.  An example:
00103  *          SELECT ... WHERE x = 42 ORDER BY x, y;
00104  * We may as well just sort by y.  Note that because of opfamily matching,
00105  * this is semantically correct: we know that the equality constraint is one
00106  * that actually binds the variable to a single value in the terms of any
00107  * ordering operator that might go with the eclass.  This rule not only lets
00108  * us simplify (or even skip) explicit sorts, but also allows matching index
00109  * sort orders to a query when there are don't-care index columns.
00110  *
00111  * 2. If the new pathkey's equivalence class is the same as that of any
00112  * existing member of the pathkey list, then it is redundant.  Some examples:
00113  *          SELECT ... ORDER BY x, x;
00114  *          SELECT ... ORDER BY x, x DESC;
00115  *          SELECT ... WHERE x = y ORDER BY x, y;
00116  * In all these cases the second sort key cannot distinguish values that are
00117  * considered equal by the first, and so there's no point in using it.
00118  * Note in particular that we need not compare opfamily (all the opfamilies
00119  * of the EC have the same notion of equality) nor sort direction.
00120  *
00121  * Both the given pathkey and the list members must be canonical for this
00122  * to work properly, but that's okay since we no longer ever construct any
00123  * non-canonical pathkeys.  (Note: the notion of a pathkey *list* being
00124  * canonical includes the additional requirement of no redundant entries,
00125  * which is exactly what we are checking for here.)
00126  *
00127  * Because the equivclass.c machinery forms only one copy of any EC per query,
00128  * pointer comparison is enough to decide whether canonical ECs are the same.
00129  */
00130 static bool
00131 pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
00132 {
00133     EquivalenceClass *new_ec = new_pathkey->pk_eclass;
00134     ListCell   *lc;
00135 
00136     /* Check for EC containing a constant --- unconditionally redundant */
00137     if (EC_MUST_BE_REDUNDANT(new_ec))
00138         return true;
00139 
00140     /* If same EC already used in list, then redundant */
00141     foreach(lc, pathkeys)
00142     {
00143         PathKey    *old_pathkey = (PathKey *) lfirst(lc);
00144 
00145         if (new_ec == old_pathkey->pk_eclass)
00146             return true;
00147     }
00148 
00149     return false;
00150 }
00151 
00152 /*
00153  * make_pathkey_from_sortinfo
00154  *    Given an expression and sort-order information, create a PathKey.
00155  *    The result is always a "canonical" PathKey, but it might be redundant.
00156  *
00157  * If the PathKey is being generated from a SortGroupClause, sortref should be
00158  * the SortGroupClause's SortGroupRef; otherwise zero.
00159  *
00160  * If rel is not NULL, it identifies a specific relation we're considering
00161  * a path for, and indicates that child EC members for that relation can be
00162  * considered.  Otherwise child members are ignored.  (See the comments for
00163  * get_eclass_for_sort_expr.)
00164  *
00165  * create_it is TRUE if we should create any missing EquivalenceClass
00166  * needed to represent the sort key.  If it's FALSE, we return NULL if the
00167  * sort key isn't already present in any EquivalenceClass.
00168  */
00169 static PathKey *
00170 make_pathkey_from_sortinfo(PlannerInfo *root,
00171                            Expr *expr,
00172                            Oid opfamily,
00173                            Oid opcintype,
00174                            Oid collation,
00175                            bool reverse_sort,
00176                            bool nulls_first,
00177                            Index sortref,
00178                            Relids rel,
00179                            bool create_it)
00180 {
00181     int16       strategy;
00182     Oid         equality_op;
00183     List       *opfamilies;
00184     EquivalenceClass *eclass;
00185 
00186     strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
00187 
00188     /*
00189      * EquivalenceClasses need to contain opfamily lists based on the family
00190      * membership of mergejoinable equality operators, which could belong to
00191      * more than one opfamily.  So we have to look up the opfamily's equality
00192      * operator and get its membership.
00193      */
00194     equality_op = get_opfamily_member(opfamily,
00195                                       opcintype,
00196                                       opcintype,
00197                                       BTEqualStrategyNumber);
00198     if (!OidIsValid(equality_op))       /* shouldn't happen */
00199         elog(ERROR, "could not find equality operator for opfamily %u",
00200              opfamily);
00201     opfamilies = get_mergejoin_opfamilies(equality_op);
00202     if (!opfamilies)            /* certainly should find some */
00203         elog(ERROR, "could not find opfamilies for equality operator %u",
00204              equality_op);
00205 
00206     /* Now find or (optionally) create a matching EquivalenceClass */
00207     eclass = get_eclass_for_sort_expr(root, expr, opfamilies,
00208                                       opcintype, collation,
00209                                       sortref, rel, create_it);
00210 
00211     /* Fail if no EC and !create_it */
00212     if (!eclass)
00213         return NULL;
00214 
00215     /* And finally we can find or create a PathKey node */
00216     return make_canonical_pathkey(root, eclass, opfamily,
00217                                   strategy, nulls_first);
00218 }
00219 
00220 /*
00221  * make_pathkey_from_sortop
00222  *    Like make_pathkey_from_sortinfo, but work from a sort operator.
00223  *
00224  * This should eventually go away, but we need to restructure SortGroupClause
00225  * first.
00226  */
00227 static PathKey *
00228 make_pathkey_from_sortop(PlannerInfo *root,
00229                          Expr *expr,
00230                          Oid ordering_op,
00231                          bool nulls_first,
00232                          Index sortref,
00233                          bool create_it)
00234 {
00235     Oid         opfamily,
00236                 opcintype,
00237                 collation;
00238     int16       strategy;
00239 
00240     /* Find the operator in pg_amop --- failure shouldn't happen */
00241     if (!get_ordering_op_properties(ordering_op,
00242                                     &opfamily, &opcintype, &strategy))
00243         elog(ERROR, "operator %u is not a valid ordering operator",
00244              ordering_op);
00245 
00246     /* Because SortGroupClause doesn't carry collation, consult the expr */
00247     collation = exprCollation((Node *) expr);
00248 
00249     return make_pathkey_from_sortinfo(root,
00250                                       expr,
00251                                       opfamily,
00252                                       opcintype,
00253                                       collation,
00254                                       (strategy == BTGreaterStrategyNumber),
00255                                       nulls_first,
00256                                       sortref,
00257                                       NULL,
00258                                       create_it);
00259 }
00260 
00261 
00262 /****************************************************************************
00263  *      PATHKEY COMPARISONS
00264  ****************************************************************************/
00265 
00266 /*
00267  * compare_pathkeys
00268  *    Compare two pathkeys to see if they are equivalent, and if not whether
00269  *    one is "better" than the other.
00270  *
00271  *    We assume the pathkeys are canonical, and so they can be checked for
00272  *    equality by simple pointer comparison.
00273  */
00274 PathKeysComparison
00275 compare_pathkeys(List *keys1, List *keys2)
00276 {
00277     ListCell   *key1,
00278                *key2;
00279 
00280     /*
00281      * Fall out quickly if we are passed two identical lists.  This mostly
00282      * catches the case where both are NIL, but that's common enough to
00283      * warrant the test.
00284      */
00285     if (keys1 == keys2)
00286         return PATHKEYS_EQUAL;
00287 
00288     forboth(key1, keys1, key2, keys2)
00289     {
00290         PathKey    *pathkey1 = (PathKey *) lfirst(key1);
00291         PathKey    *pathkey2 = (PathKey *) lfirst(key2);
00292 
00293         if (pathkey1 != pathkey2)
00294             return PATHKEYS_DIFFERENT;  /* no need to keep looking */
00295     }
00296 
00297     /*
00298      * If we reached the end of only one list, the other is longer and
00299      * therefore not a subset.
00300      */
00301     if (key1 != NULL)
00302         return PATHKEYS_BETTER1;    /* key1 is longer */
00303     if (key2 != NULL)
00304         return PATHKEYS_BETTER2;    /* key2 is longer */
00305     return PATHKEYS_EQUAL;
00306 }
00307 
00308 /*
00309  * pathkeys_contained_in
00310  *    Common special case of compare_pathkeys: we just want to know
00311  *    if keys2 are at least as well sorted as keys1.
00312  */
00313 bool
00314 pathkeys_contained_in(List *keys1, List *keys2)
00315 {
00316     switch (compare_pathkeys(keys1, keys2))
00317     {
00318         case PATHKEYS_EQUAL:
00319         case PATHKEYS_BETTER2:
00320             return true;
00321         default:
00322             break;
00323     }
00324     return false;
00325 }
00326 
00327 /*
00328  * get_cheapest_path_for_pathkeys
00329  *    Find the cheapest path (according to the specified criterion) that
00330  *    satisfies the given pathkeys and parameterization.
00331  *    Return NULL if no such path.
00332  *
00333  * 'paths' is a list of possible paths that all generate the same relation
00334  * 'pathkeys' represents a required ordering (in canonical form!)
00335  * 'required_outer' denotes allowable outer relations for parameterized paths
00336  * 'cost_criterion' is STARTUP_COST or TOTAL_COST
00337  */
00338 Path *
00339 get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
00340                                Relids required_outer,
00341                                CostSelector cost_criterion)
00342 {
00343     Path       *matched_path = NULL;
00344     ListCell   *l;
00345 
00346     foreach(l, paths)
00347     {
00348         Path       *path = (Path *) lfirst(l);
00349 
00350         /*
00351          * Since cost comparison is a lot cheaper than pathkey comparison, do
00352          * that first.  (XXX is that still true?)
00353          */
00354         if (matched_path != NULL &&
00355             compare_path_costs(matched_path, path, cost_criterion) <= 0)
00356             continue;
00357 
00358         if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
00359             bms_is_subset(PATH_REQ_OUTER(path), required_outer))
00360             matched_path = path;
00361     }
00362     return matched_path;
00363 }
00364 
00365 /*
00366  * get_cheapest_fractional_path_for_pathkeys
00367  *    Find the cheapest path (for retrieving a specified fraction of all
00368  *    the tuples) that satisfies the given pathkeys and parameterization.
00369  *    Return NULL if no such path.
00370  *
00371  * See compare_fractional_path_costs() for the interpretation of the fraction
00372  * parameter.
00373  *
00374  * 'paths' is a list of possible paths that all generate the same relation
00375  * 'pathkeys' represents a required ordering (in canonical form!)
00376  * 'required_outer' denotes allowable outer relations for parameterized paths
00377  * 'fraction' is the fraction of the total tuples expected to be retrieved
00378  */
00379 Path *
00380 get_cheapest_fractional_path_for_pathkeys(List *paths,
00381                                           List *pathkeys,
00382                                           Relids required_outer,
00383                                           double fraction)
00384 {
00385     Path       *matched_path = NULL;
00386     ListCell   *l;
00387 
00388     foreach(l, paths)
00389     {
00390         Path       *path = (Path *) lfirst(l);
00391 
00392         /*
00393          * Since cost comparison is a lot cheaper than pathkey comparison, do
00394          * that first.  (XXX is that still true?)
00395          */
00396         if (matched_path != NULL &&
00397             compare_fractional_path_costs(matched_path, path, fraction) <= 0)
00398             continue;
00399 
00400         if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
00401             bms_is_subset(PATH_REQ_OUTER(path), required_outer))
00402             matched_path = path;
00403     }
00404     return matched_path;
00405 }
00406 
00407 /****************************************************************************
00408  *      NEW PATHKEY FORMATION
00409  ****************************************************************************/
00410 
00411 /*
00412  * build_index_pathkeys
00413  *    Build a pathkeys list that describes the ordering induced by an index
00414  *    scan using the given index.  (Note that an unordered index doesn't
00415  *    induce any ordering, so we return NIL.)
00416  *
00417  * If 'scandir' is BackwardScanDirection, build pathkeys representing a
00418  * backwards scan of the index.
00419  *
00420  * The result is canonical, meaning that redundant pathkeys are removed;
00421  * it may therefore have fewer entries than there are index columns.
00422  *
00423  * Another reason for stopping early is that we may be able to tell that
00424  * an index column's sort order is uninteresting for this query.  However,
00425  * that test is just based on the existence of an EquivalenceClass and not
00426  * on position in pathkey lists, so it's not complete.  Caller should call
00427  * truncate_useless_pathkeys() to possibly remove more pathkeys.
00428  */
00429 List *
00430 build_index_pathkeys(PlannerInfo *root,
00431                      IndexOptInfo *index,
00432                      ScanDirection scandir)
00433 {
00434     List       *retval = NIL;
00435     ListCell   *lc;
00436     int         i;
00437 
00438     if (index->sortopfamily == NULL)
00439         return NIL;             /* non-orderable index */
00440 
00441     i = 0;
00442     foreach(lc, index->indextlist)
00443     {
00444         TargetEntry *indextle = (TargetEntry *) lfirst(lc);
00445         Expr       *indexkey;
00446         bool        reverse_sort;
00447         bool        nulls_first;
00448         PathKey    *cpathkey;
00449 
00450         /* We assume we don't need to make a copy of the tlist item */
00451         indexkey = indextle->expr;
00452 
00453         if (ScanDirectionIsBackward(scandir))
00454         {
00455             reverse_sort = !index->reverse_sort[i];
00456             nulls_first = !index->nulls_first[i];
00457         }
00458         else
00459         {
00460             reverse_sort = index->reverse_sort[i];
00461             nulls_first = index->nulls_first[i];
00462         }
00463 
00464         /* OK, try to make a canonical pathkey for this sort key */
00465         cpathkey = make_pathkey_from_sortinfo(root,
00466                                               indexkey,
00467                                               index->sortopfamily[i],
00468                                               index->opcintype[i],
00469                                               index->indexcollations[i],
00470                                               reverse_sort,
00471                                               nulls_first,
00472                                               0,
00473                                               index->rel->relids,
00474                                               false);
00475 
00476         /*
00477          * If the sort key isn't already present in any EquivalenceClass, then
00478          * it's not an interesting sort order for this query.  So we can stop
00479          * now --- lower-order sort keys aren't useful either.
00480          */
00481         if (!cpathkey)
00482             break;
00483 
00484         /* Add to list unless redundant */
00485         if (!pathkey_is_redundant(cpathkey, retval))
00486             retval = lappend(retval, cpathkey);
00487 
00488         i++;
00489     }
00490 
00491     return retval;
00492 }
00493 
00494 /*
00495  * convert_subquery_pathkeys
00496  *    Build a pathkeys list that describes the ordering of a subquery's
00497  *    result, in the terms of the outer query.  This is essentially a
00498  *    task of conversion.
00499  *
00500  * 'rel': outer query's RelOptInfo for the subquery relation.
00501  * 'subquery_pathkeys': the subquery's output pathkeys, in its terms.
00502  *
00503  * It is not necessary for caller to do truncate_useless_pathkeys(),
00504  * because we select keys in a way that takes usefulness of the keys into
00505  * account.
00506  */
00507 List *
00508 convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
00509                           List *subquery_pathkeys)
00510 {
00511     List       *retval = NIL;
00512     int         retvallen = 0;
00513     int         outer_query_keys = list_length(root->query_pathkeys);
00514     List       *sub_tlist = rel->subplan->targetlist;
00515     ListCell   *i;
00516 
00517     foreach(i, subquery_pathkeys)
00518     {
00519         PathKey    *sub_pathkey = (PathKey *) lfirst(i);
00520         EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
00521         PathKey    *best_pathkey = NULL;
00522 
00523         if (sub_eclass->ec_has_volatile)
00524         {
00525             /*
00526              * If the sub_pathkey's EquivalenceClass is volatile, then it must
00527              * have come from an ORDER BY clause, and we have to match it to
00528              * that same targetlist entry.
00529              */
00530             TargetEntry *tle;
00531 
00532             if (sub_eclass->ec_sortref == 0)    /* can't happen */
00533                 elog(ERROR, "volatile EquivalenceClass has no sortref");
00534             tle = get_sortgroupref_tle(sub_eclass->ec_sortref, sub_tlist);
00535             Assert(tle);
00536             /* resjunk items aren't visible to outer query */
00537             if (!tle->resjunk)
00538             {
00539                 /* We can represent this sub_pathkey */
00540                 EquivalenceMember *sub_member;
00541                 Expr       *outer_expr;
00542                 EquivalenceClass *outer_ec;
00543 
00544                 Assert(list_length(sub_eclass->ec_members) == 1);
00545                 sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
00546                 outer_expr = (Expr *) makeVarFromTargetEntry(rel->relid, tle);
00547 
00548                 /*
00549                  * Note: it might look funny to be setting sortref = 0 for a
00550                  * reference to a volatile sub_eclass.  However, the
00551                  * expression is *not* volatile in the outer query: it's just
00552                  * a Var referencing whatever the subquery emitted. (IOW, the
00553                  * outer query isn't going to re-execute the volatile
00554                  * expression itself.)  So this is okay.
00555                  */
00556                 outer_ec =
00557                     get_eclass_for_sort_expr(root,
00558                                              outer_expr,
00559                                              sub_eclass->ec_opfamilies,
00560                                              sub_member->em_datatype,
00561                                              sub_eclass->ec_collation,
00562                                              0,
00563                                              rel->relids,
00564                                              false);
00565 
00566                 /*
00567                  * If we don't find a matching EC, sub-pathkey isn't
00568                  * interesting to the outer query
00569                  */
00570                 if (outer_ec)
00571                     best_pathkey =
00572                         make_canonical_pathkey(root,
00573                                                outer_ec,
00574                                                sub_pathkey->pk_opfamily,
00575                                                sub_pathkey->pk_strategy,
00576                                                sub_pathkey->pk_nulls_first);
00577             }
00578         }
00579         else
00580         {
00581             /*
00582              * Otherwise, the sub_pathkey's EquivalenceClass could contain
00583              * multiple elements (representing knowledge that multiple items
00584              * are effectively equal).  Each element might match none, one, or
00585              * more of the output columns that are visible to the outer query.
00586              * This means we may have multiple possible representations of the
00587              * sub_pathkey in the context of the outer query.  Ideally we
00588              * would generate them all and put them all into an EC of the
00589              * outer query, thereby propagating equality knowledge up to the
00590              * outer query.  Right now we cannot do so, because the outer
00591              * query's EquivalenceClasses are already frozen when this is
00592              * called. Instead we prefer the one that has the highest "score"
00593              * (number of EC peers, plus one if it matches the outer
00594              * query_pathkeys). This is the most likely to be useful in the
00595              * outer query.
00596              */
00597             int         best_score = -1;
00598             ListCell   *j;
00599 
00600             foreach(j, sub_eclass->ec_members)
00601             {
00602                 EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
00603                 Expr       *sub_expr = sub_member->em_expr;
00604                 Oid         sub_expr_type = sub_member->em_datatype;
00605                 Oid         sub_expr_coll = sub_eclass->ec_collation;
00606                 ListCell   *k;
00607 
00608                 if (sub_member->em_is_child)
00609                     continue;   /* ignore children here */
00610 
00611                 foreach(k, sub_tlist)
00612                 {
00613                     TargetEntry *tle = (TargetEntry *) lfirst(k);
00614                     Expr       *tle_expr;
00615                     Expr       *outer_expr;
00616                     EquivalenceClass *outer_ec;
00617                     PathKey    *outer_pk;
00618                     int         score;
00619 
00620                     /* resjunk items aren't visible to outer query */
00621                     if (tle->resjunk)
00622                         continue;
00623 
00624                     /*
00625                      * The targetlist entry is considered to match if it
00626                      * matches after sort-key canonicalization.  That is
00627                      * needed since the sub_expr has been through the same
00628                      * process.
00629                      */
00630                     tle_expr = canonicalize_ec_expression(tle->expr,
00631                                                           sub_expr_type,
00632                                                           sub_expr_coll);
00633                     if (!equal(tle_expr, sub_expr))
00634                         continue;
00635 
00636                     /*
00637                      * Build a representation of this targetlist entry as an
00638                      * outer Var.
00639                      */
00640                     outer_expr = (Expr *) makeVarFromTargetEntry(rel->relid,
00641                                                                  tle);
00642 
00643                     /* See if we have a matching EC for that */
00644                     outer_ec = get_eclass_for_sort_expr(root,
00645                                                         outer_expr,
00646                                                    sub_eclass->ec_opfamilies,
00647                                                         sub_expr_type,
00648                                                         sub_expr_coll,
00649                                                         0,
00650                                                         rel->relids,
00651                                                         false);
00652 
00653                     /*
00654                      * If we don't find a matching EC, this sub-pathkey isn't
00655                      * interesting to the outer query
00656                      */
00657                     if (!outer_ec)
00658                         continue;
00659 
00660                     outer_pk = make_canonical_pathkey(root,
00661                                                       outer_ec,
00662                                                     sub_pathkey->pk_opfamily,
00663                                                     sub_pathkey->pk_strategy,
00664                                                 sub_pathkey->pk_nulls_first);
00665                     /* score = # of equivalence peers */
00666                     score = list_length(outer_ec->ec_members) - 1;
00667                     /* +1 if it matches the proper query_pathkeys item */
00668                     if (retvallen < outer_query_keys &&
00669                         list_nth(root->query_pathkeys, retvallen) == outer_pk)
00670                         score++;
00671                     if (score > best_score)
00672                     {
00673                         best_pathkey = outer_pk;
00674                         best_score = score;
00675                     }
00676                 }
00677             }
00678         }
00679 
00680         /*
00681          * If we couldn't find a representation of this sub_pathkey, we're
00682          * done (we can't use the ones to its right, either).
00683          */
00684         if (!best_pathkey)
00685             break;
00686 
00687         /*
00688          * Eliminate redundant ordering info; could happen if outer query
00689          * equivalences subquery keys...
00690          */
00691         if (!pathkey_is_redundant(best_pathkey, retval))
00692         {
00693             retval = lappend(retval, best_pathkey);
00694             retvallen++;
00695         }
00696     }
00697 
00698     return retval;
00699 }
00700 
00701 /*
00702  * build_join_pathkeys
00703  *    Build the path keys for a join relation constructed by mergejoin or
00704  *    nestloop join.  This is normally the same as the outer path's keys.
00705  *
00706  *    EXCEPTION: in a FULL or RIGHT join, we cannot treat the result as
00707  *    having the outer path's path keys, because null lefthand rows may be
00708  *    inserted at random points.  It must be treated as unsorted.
00709  *
00710  *    We truncate away any pathkeys that are uninteresting for higher joins.
00711  *
00712  * 'joinrel' is the join relation that paths are being formed for
00713  * 'jointype' is the join type (inner, left, full, etc)
00714  * 'outer_pathkeys' is the list of the current outer path's path keys
00715  *
00716  * Returns the list of new path keys.
00717  */
00718 List *
00719 build_join_pathkeys(PlannerInfo *root,
00720                     RelOptInfo *joinrel,
00721                     JoinType jointype,
00722                     List *outer_pathkeys)
00723 {
00724     if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
00725         return NIL;
00726 
00727     /*
00728      * This used to be quite a complex bit of code, but now that all pathkey
00729      * sublists start out life canonicalized, we don't have to do a darn thing
00730      * here!
00731      *
00732      * We do, however, need to truncate the pathkeys list, since it may
00733      * contain pathkeys that were useful for forming this joinrel but are
00734      * uninteresting to higher levels.
00735      */
00736     return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
00737 }
00738 
00739 /****************************************************************************
00740  *      PATHKEYS AND SORT CLAUSES
00741  ****************************************************************************/
00742 
00743 /*
00744  * make_pathkeys_for_sortclauses
00745  *      Generate a pathkeys list that represents the sort order specified
00746  *      by a list of SortGroupClauses
00747  *
00748  * The resulting PathKeys are always in canonical form.  (Actually, there
00749  * is no longer any code anywhere that creates non-canonical PathKeys.)
00750  *
00751  * 'sortclauses' is a list of SortGroupClause nodes
00752  * 'tlist' is the targetlist to find the referenced tlist entries in
00753  */
00754 List *
00755 make_pathkeys_for_sortclauses(PlannerInfo *root,
00756                               List *sortclauses,
00757                               List *tlist)
00758 {
00759     List       *pathkeys = NIL;
00760     ListCell   *l;
00761 
00762     foreach(l, sortclauses)
00763     {
00764         SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
00765         Expr       *sortkey;
00766         PathKey    *pathkey;
00767 
00768         sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
00769         Assert(OidIsValid(sortcl->sortop));
00770         pathkey = make_pathkey_from_sortop(root,
00771                                            sortkey,
00772                                            sortcl->sortop,
00773                                            sortcl->nulls_first,
00774                                            sortcl->tleSortGroupRef,
00775                                            true);
00776 
00777         /* Canonical form eliminates redundant ordering keys */
00778         if (!pathkey_is_redundant(pathkey, pathkeys))
00779             pathkeys = lappend(pathkeys, pathkey);
00780     }
00781     return pathkeys;
00782 }
00783 
00784 /****************************************************************************
00785  *      PATHKEYS AND MERGECLAUSES
00786  ****************************************************************************/
00787 
00788 /*
00789  * initialize_mergeclause_eclasses
00790  *      Set the EquivalenceClass links in a mergeclause restrictinfo.
00791  *
00792  * RestrictInfo contains fields in which we may cache pointers to
00793  * EquivalenceClasses for the left and right inputs of the mergeclause.
00794  * (If the mergeclause is a true equivalence clause these will be the
00795  * same EquivalenceClass, otherwise not.)  If the mergeclause is either
00796  * used to generate an EquivalenceClass, or derived from an EquivalenceClass,
00797  * then it's easy to set up the left_ec and right_ec members --- otherwise,
00798  * this function should be called to set them up.  We will generate new
00799  * EquivalenceClauses if necessary to represent the mergeclause's left and
00800  * right sides.
00801  *
00802  * Note this is called before EC merging is complete, so the links won't
00803  * necessarily point to canonical ECs.  Before they are actually used for
00804  * anything, update_mergeclause_eclasses must be called to ensure that
00805  * they've been updated to point to canonical ECs.
00806  */
00807 void
00808 initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
00809 {
00810     Expr       *clause = restrictinfo->clause;
00811     Oid         lefttype,
00812                 righttype;
00813 
00814     /* Should be a mergeclause ... */
00815     Assert(restrictinfo->mergeopfamilies != NIL);
00816     /* ... with links not yet set */
00817     Assert(restrictinfo->left_ec == NULL);
00818     Assert(restrictinfo->right_ec == NULL);
00819 
00820     /* Need the declared input types of the operator */
00821     op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
00822 
00823     /* Find or create a matching EquivalenceClass for each side */
00824     restrictinfo->left_ec =
00825         get_eclass_for_sort_expr(root,
00826                                  (Expr *) get_leftop(clause),
00827                                  restrictinfo->mergeopfamilies,
00828                                  lefttype,
00829                                  ((OpExpr *) clause)->inputcollid,
00830                                  0,
00831                                  NULL,
00832                                  true);
00833     restrictinfo->right_ec =
00834         get_eclass_for_sort_expr(root,
00835                                  (Expr *) get_rightop(clause),
00836                                  restrictinfo->mergeopfamilies,
00837                                  righttype,
00838                                  ((OpExpr *) clause)->inputcollid,
00839                                  0,
00840                                  NULL,
00841                                  true);
00842 }
00843 
00844 /*
00845  * update_mergeclause_eclasses
00846  *      Make the cached EquivalenceClass links valid in a mergeclause
00847  *      restrictinfo.
00848  *
00849  * These pointers should have been set by process_equivalence or
00850  * initialize_mergeclause_eclasses, but they might have been set to
00851  * non-canonical ECs that got merged later.  Chase up to the canonical
00852  * merged parent if so.
00853  */
00854 void
00855 update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
00856 {
00857     /* Should be a merge clause ... */
00858     Assert(restrictinfo->mergeopfamilies != NIL);
00859     /* ... with pointers already set */
00860     Assert(restrictinfo->left_ec != NULL);
00861     Assert(restrictinfo->right_ec != NULL);
00862 
00863     /* Chase up to the top as needed */
00864     while (restrictinfo->left_ec->ec_merged)
00865         restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
00866     while (restrictinfo->right_ec->ec_merged)
00867         restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
00868 }
00869 
00870 /*
00871  * find_mergeclauses_for_pathkeys
00872  *    This routine attempts to find a set of mergeclauses that can be
00873  *    used with a specified ordering for one of the input relations.
00874  *    If successful, it returns a list of mergeclauses.
00875  *
00876  * 'pathkeys' is a pathkeys list showing the ordering of an input path.
00877  * 'outer_keys' is TRUE if these keys are for the outer input path,
00878  *          FALSE if for inner.
00879  * 'restrictinfos' is a list of mergejoinable restriction clauses for the
00880  *          join relation being formed.
00881  *
00882  * The restrictinfos must be marked (via outer_is_left) to show which side
00883  * of each clause is associated with the current outer path.  (See
00884  * select_mergejoin_clauses())
00885  *
00886  * The result is NIL if no merge can be done, else a maximal list of
00887  * usable mergeclauses (represented as a list of their restrictinfo nodes).
00888  */
00889 List *
00890 find_mergeclauses_for_pathkeys(PlannerInfo *root,
00891                                List *pathkeys,
00892                                bool outer_keys,
00893                                List *restrictinfos)
00894 {
00895     List       *mergeclauses = NIL;
00896     ListCell   *i;
00897 
00898     /* make sure we have eclasses cached in the clauses */
00899     foreach(i, restrictinfos)
00900     {
00901         RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
00902 
00903         update_mergeclause_eclasses(root, rinfo);
00904     }
00905 
00906     foreach(i, pathkeys)
00907     {
00908         PathKey    *pathkey = (PathKey *) lfirst(i);
00909         EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
00910         List       *matched_restrictinfos = NIL;
00911         ListCell   *j;
00912 
00913         /*----------
00914          * A mergejoin clause matches a pathkey if it has the same EC.
00915          * If there are multiple matching clauses, take them all.  In plain
00916          * inner-join scenarios we expect only one match, because
00917          * equivalence-class processing will have removed any redundant
00918          * mergeclauses.  However, in outer-join scenarios there might be
00919          * multiple matches.  An example is
00920          *
00921          *  select * from a full join b
00922          *      on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
00923          *
00924          * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
00925          * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
00926          * we *must* do so or we will be unable to form a valid plan.
00927          *
00928          * We expect that the given pathkeys list is canonical, which means
00929          * no two members have the same EC, so it's not possible for this
00930          * code to enter the same mergeclause into the result list twice.
00931          *
00932          * It's possible that multiple matching clauses might have different
00933          * ECs on the other side, in which case the order we put them into our
00934          * result makes a difference in the pathkeys required for the other
00935          * input path.  However this routine hasn't got any info about which
00936          * order would be best, so we don't worry about that.
00937          *
00938          * It's also possible that the selected mergejoin clauses produce
00939          * a noncanonical ordering of pathkeys for the other side, ie, we
00940          * might select clauses that reference b.v1, b.v2, b.v1 in that
00941          * order.  This is not harmful in itself, though it suggests that
00942          * the clauses are partially redundant.  Since it happens only with
00943          * redundant query conditions, we don't bother to eliminate it.
00944          * make_inner_pathkeys_for_merge() has to delete duplicates when
00945          * it constructs the canonical pathkeys list, and we also have to
00946          * deal with the case in create_mergejoin_plan().
00947          *----------
00948          */
00949         foreach(j, restrictinfos)
00950         {
00951             RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
00952             EquivalenceClass *clause_ec;
00953 
00954             if (outer_keys)
00955                 clause_ec = rinfo->outer_is_left ?
00956                     rinfo->left_ec : rinfo->right_ec;
00957             else
00958                 clause_ec = rinfo->outer_is_left ?
00959                     rinfo->right_ec : rinfo->left_ec;
00960             if (clause_ec == pathkey_ec)
00961                 matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
00962         }
00963 
00964         /*
00965          * If we didn't find a mergeclause, we're done --- any additional
00966          * sort-key positions in the pathkeys are useless.  (But we can still
00967          * mergejoin if we found at least one mergeclause.)
00968          */
00969         if (matched_restrictinfos == NIL)
00970             break;
00971 
00972         /*
00973          * If we did find usable mergeclause(s) for this sort-key position,
00974          * add them to result list.
00975          */
00976         mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
00977     }
00978 
00979     return mergeclauses;
00980 }
00981 
00982 /*
00983  * select_outer_pathkeys_for_merge
00984  *    Builds a pathkey list representing a possible sort ordering
00985  *    that can be used with the given mergeclauses.
00986  *
00987  * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
00988  *          that will be used in a merge join.
00989  * 'joinrel' is the join relation we are trying to construct.
00990  *
00991  * The restrictinfos must be marked (via outer_is_left) to show which side
00992  * of each clause is associated with the current outer path.  (See
00993  * select_mergejoin_clauses())
00994  *
00995  * Returns a pathkeys list that can be applied to the outer relation.
00996  *
00997  * Since we assume here that a sort is required, there is no particular use
00998  * in matching any available ordering of the outerrel.  (joinpath.c has an
00999  * entirely separate code path for considering sort-free mergejoins.)  Rather,
01000  * it's interesting to try to match the requested query_pathkeys so that a
01001  * second output sort may be avoided; and failing that, we try to list "more
01002  * popular" keys (those with the most unmatched EquivalenceClass peers)
01003  * earlier, in hopes of making the resulting ordering useful for as many
01004  * higher-level mergejoins as possible.
01005  */
01006 List *
01007 select_outer_pathkeys_for_merge(PlannerInfo *root,
01008                                 List *mergeclauses,
01009                                 RelOptInfo *joinrel)
01010 {
01011     List       *pathkeys = NIL;
01012     int         nClauses = list_length(mergeclauses);
01013     EquivalenceClass **ecs;
01014     int        *scores;
01015     int         necs;
01016     ListCell   *lc;
01017     int         j;
01018 
01019     /* Might have no mergeclauses */
01020     if (nClauses == 0)
01021         return NIL;
01022 
01023     /*
01024      * Make arrays of the ECs used by the mergeclauses (dropping any
01025      * duplicates) and their "popularity" scores.
01026      */
01027     ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
01028     scores = (int *) palloc(nClauses * sizeof(int));
01029     necs = 0;
01030 
01031     foreach(lc, mergeclauses)
01032     {
01033         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
01034         EquivalenceClass *oeclass;
01035         int         score;
01036         ListCell   *lc2;
01037 
01038         /* get the outer eclass */
01039         update_mergeclause_eclasses(root, rinfo);
01040 
01041         if (rinfo->outer_is_left)
01042             oeclass = rinfo->left_ec;
01043         else
01044             oeclass = rinfo->right_ec;
01045 
01046         /* reject duplicates */
01047         for (j = 0; j < necs; j++)
01048         {
01049             if (ecs[j] == oeclass)
01050                 break;
01051         }
01052         if (j < necs)
01053             continue;
01054 
01055         /* compute score */
01056         score = 0;
01057         foreach(lc2, oeclass->ec_members)
01058         {
01059             EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
01060 
01061             /* Potential future join partner? */
01062             if (!em->em_is_const && !em->em_is_child &&
01063                 !bms_overlap(em->em_relids, joinrel->relids))
01064                 score++;
01065         }
01066 
01067         ecs[necs] = oeclass;
01068         scores[necs] = score;
01069         necs++;
01070     }
01071 
01072     /*
01073      * Find out if we have all the ECs mentioned in query_pathkeys; if so we
01074      * can generate a sort order that's also useful for final output. There is
01075      * no percentage in a partial match, though, so we have to have 'em all.
01076      */
01077     if (root->query_pathkeys)
01078     {
01079         foreach(lc, root->query_pathkeys)
01080         {
01081             PathKey    *query_pathkey = (PathKey *) lfirst(lc);
01082             EquivalenceClass *query_ec = query_pathkey->pk_eclass;
01083 
01084             for (j = 0; j < necs; j++)
01085             {
01086                 if (ecs[j] == query_ec)
01087                     break;      /* found match */
01088             }
01089             if (j >= necs)
01090                 break;          /* didn't find match */
01091         }
01092         /* if we got to the end of the list, we have them all */
01093         if (lc == NULL)
01094         {
01095             /* copy query_pathkeys as starting point for our output */
01096             pathkeys = list_copy(root->query_pathkeys);
01097             /* mark their ECs as already-emitted */
01098             foreach(lc, root->query_pathkeys)
01099             {
01100                 PathKey    *query_pathkey = (PathKey *) lfirst(lc);
01101                 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
01102 
01103                 for (j = 0; j < necs; j++)
01104                 {
01105                     if (ecs[j] == query_ec)
01106                     {
01107                         scores[j] = -1;
01108                         break;
01109                     }
01110                 }
01111             }
01112         }
01113     }
01114 
01115     /*
01116      * Add remaining ECs to the list in popularity order, using a default sort
01117      * ordering.  (We could use qsort() here, but the list length is usually
01118      * so small it's not worth it.)
01119      */
01120     for (;;)
01121     {
01122         int         best_j;
01123         int         best_score;
01124         EquivalenceClass *ec;
01125         PathKey    *pathkey;
01126 
01127         best_j = 0;
01128         best_score = scores[0];
01129         for (j = 1; j < necs; j++)
01130         {
01131             if (scores[j] > best_score)
01132             {
01133                 best_j = j;
01134                 best_score = scores[j];
01135             }
01136         }
01137         if (best_score < 0)
01138             break;              /* all done */
01139         ec = ecs[best_j];
01140         scores[best_j] = -1;
01141         pathkey = make_canonical_pathkey(root,
01142                                          ec,
01143                                          linitial_oid(ec->ec_opfamilies),
01144                                          BTLessStrategyNumber,
01145                                          false);
01146         /* can't be redundant because no duplicate ECs */
01147         Assert(!pathkey_is_redundant(pathkey, pathkeys));
01148         pathkeys = lappend(pathkeys, pathkey);
01149     }
01150 
01151     pfree(ecs);
01152     pfree(scores);
01153 
01154     return pathkeys;
01155 }
01156 
01157 /*
01158  * make_inner_pathkeys_for_merge
01159  *    Builds a pathkey list representing the explicit sort order that
01160  *    must be applied to an inner path to make it usable with the
01161  *    given mergeclauses.
01162  *
01163  * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
01164  *          that will be used in a merge join.
01165  * 'outer_pathkeys' are the already-known canonical pathkeys for the outer
01166  *          side of the join.
01167  *
01168  * The restrictinfos must be marked (via outer_is_left) to show which side
01169  * of each clause is associated with the current outer path.  (See
01170  * select_mergejoin_clauses())
01171  *
01172  * Returns a pathkeys list that can be applied to the inner relation.
01173  *
01174  * Note that it is not this routine's job to decide whether sorting is
01175  * actually needed for a particular input path.  Assume a sort is necessary;
01176  * just make the keys, eh?
01177  */
01178 List *
01179 make_inner_pathkeys_for_merge(PlannerInfo *root,
01180                               List *mergeclauses,
01181                               List *outer_pathkeys)
01182 {
01183     List       *pathkeys = NIL;
01184     EquivalenceClass *lastoeclass;
01185     PathKey    *opathkey;
01186     ListCell   *lc;
01187     ListCell   *lop;
01188 
01189     lastoeclass = NULL;
01190     opathkey = NULL;
01191     lop = list_head(outer_pathkeys);
01192 
01193     foreach(lc, mergeclauses)
01194     {
01195         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
01196         EquivalenceClass *oeclass;
01197         EquivalenceClass *ieclass;
01198         PathKey    *pathkey;
01199 
01200         update_mergeclause_eclasses(root, rinfo);
01201 
01202         if (rinfo->outer_is_left)
01203         {
01204             oeclass = rinfo->left_ec;
01205             ieclass = rinfo->right_ec;
01206         }
01207         else
01208         {
01209             oeclass = rinfo->right_ec;
01210             ieclass = rinfo->left_ec;
01211         }
01212 
01213         /* outer eclass should match current or next pathkeys */
01214         /* we check this carefully for debugging reasons */
01215         if (oeclass != lastoeclass)
01216         {
01217             if (!lop)
01218                 elog(ERROR, "too few pathkeys for mergeclauses");
01219             opathkey = (PathKey *) lfirst(lop);
01220             lop = lnext(lop);
01221             lastoeclass = opathkey->pk_eclass;
01222             if (oeclass != lastoeclass)
01223                 elog(ERROR, "outer pathkeys do not match mergeclause");
01224         }
01225 
01226         /*
01227          * Often, we'll have same EC on both sides, in which case the outer
01228          * pathkey is also canonical for the inner side, and we can skip a
01229          * useless search.
01230          */
01231         if (ieclass == oeclass)
01232             pathkey = opathkey;
01233         else
01234             pathkey = make_canonical_pathkey(root,
01235                                              ieclass,
01236                                              opathkey->pk_opfamily,
01237                                              opathkey->pk_strategy,
01238                                              opathkey->pk_nulls_first);
01239 
01240         /*
01241          * Don't generate redundant pathkeys (can happen if multiple
01242          * mergeclauses refer to same EC).
01243          */
01244         if (!pathkey_is_redundant(pathkey, pathkeys))
01245             pathkeys = lappend(pathkeys, pathkey);
01246     }
01247 
01248     return pathkeys;
01249 }
01250 
01251 /****************************************************************************
01252  *      PATHKEY USEFULNESS CHECKS
01253  *
01254  * We only want to remember as many of the pathkeys of a path as have some
01255  * potential use, either for subsequent mergejoins or for meeting the query's
01256  * requested output ordering.  This ensures that add_path() won't consider
01257  * a path to have a usefully different ordering unless it really is useful.
01258  * These routines check for usefulness of given pathkeys.
01259  ****************************************************************************/
01260 
01261 /*
01262  * pathkeys_useful_for_merging
01263  *      Count the number of pathkeys that may be useful for mergejoins
01264  *      above the given relation.
01265  *
01266  * We consider a pathkey potentially useful if it corresponds to the merge
01267  * ordering of either side of any joinclause for the rel.  This might be
01268  * overoptimistic, since joinclauses that require different other relations
01269  * might never be usable at the same time, but trying to be exact is likely
01270  * to be more trouble than it's worth.
01271  *
01272  * To avoid doubling the number of mergejoin paths considered, we would like
01273  * to consider only one of the two scan directions (ASC or DESC) as useful
01274  * for merging for any given target column.  The choice is arbitrary unless
01275  * one of the directions happens to match an ORDER BY key, in which case
01276  * that direction should be preferred, in hopes of avoiding a final sort step.
01277  * right_merge_direction() implements this heuristic.
01278  */
01279 static int
01280 pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
01281 {
01282     int         useful = 0;
01283     ListCell   *i;
01284 
01285     foreach(i, pathkeys)
01286     {
01287         PathKey    *pathkey = (PathKey *) lfirst(i);
01288         bool        matched = false;
01289         ListCell   *j;
01290 
01291         /* If "wrong" direction, not useful for merging */
01292         if (!right_merge_direction(root, pathkey))
01293             break;
01294 
01295         /*
01296          * First look into the EquivalenceClass of the pathkey, to see if
01297          * there are any members not yet joined to the rel.  If so, it's
01298          * surely possible to generate a mergejoin clause using them.
01299          */
01300         if (rel->has_eclass_joins &&
01301             eclass_useful_for_merging(pathkey->pk_eclass, rel))
01302             matched = true;
01303         else
01304         {
01305             /*
01306              * Otherwise search the rel's joininfo list, which contains
01307              * non-EquivalenceClass-derivable join clauses that might
01308              * nonetheless be mergejoinable.
01309              */
01310             foreach(j, rel->joininfo)
01311             {
01312                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
01313 
01314                 if (restrictinfo->mergeopfamilies == NIL)
01315                     continue;
01316                 update_mergeclause_eclasses(root, restrictinfo);
01317 
01318                 if (pathkey->pk_eclass == restrictinfo->left_ec ||
01319                     pathkey->pk_eclass == restrictinfo->right_ec)
01320                 {
01321                     matched = true;
01322                     break;
01323                 }
01324             }
01325         }
01326 
01327         /*
01328          * If we didn't find a mergeclause, we're done --- any additional
01329          * sort-key positions in the pathkeys are useless.  (But we can still
01330          * mergejoin if we found at least one mergeclause.)
01331          */
01332         if (matched)
01333             useful++;
01334         else
01335             break;
01336     }
01337 
01338     return useful;
01339 }
01340 
01341 /*
01342  * right_merge_direction
01343  *      Check whether the pathkey embodies the preferred sort direction
01344  *      for merging its target column.
01345  */
01346 static bool
01347 right_merge_direction(PlannerInfo *root, PathKey *pathkey)
01348 {
01349     ListCell   *l;
01350 
01351     foreach(l, root->query_pathkeys)
01352     {
01353         PathKey    *query_pathkey = (PathKey *) lfirst(l);
01354 
01355         if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
01356             pathkey->pk_opfamily == query_pathkey->pk_opfamily)
01357         {
01358             /*
01359              * Found a matching query sort column.  Prefer this pathkey's
01360              * direction iff it matches.  Note that we ignore pk_nulls_first,
01361              * which means that a sort might be needed anyway ... but we still
01362              * want to prefer only one of the two possible directions, and we
01363              * might as well use this one.
01364              */
01365             return (pathkey->pk_strategy == query_pathkey->pk_strategy);
01366         }
01367     }
01368 
01369     /* If no matching ORDER BY request, prefer the ASC direction */
01370     return (pathkey->pk_strategy == BTLessStrategyNumber);
01371 }
01372 
01373 /*
01374  * pathkeys_useful_for_ordering
01375  *      Count the number of pathkeys that are useful for meeting the
01376  *      query's requested output ordering.
01377  *
01378  * Unlike merge pathkeys, this is an all-or-nothing affair: it does us
01379  * no good to order by just the first key(s) of the requested ordering.
01380  * So the result is always either 0 or list_length(root->query_pathkeys).
01381  */
01382 static int
01383 pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
01384 {
01385     if (root->query_pathkeys == NIL)
01386         return 0;               /* no special ordering requested */
01387 
01388     if (pathkeys == NIL)
01389         return 0;               /* unordered path */
01390 
01391     if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
01392     {
01393         /* It's useful ... or at least the first N keys are */
01394         return list_length(root->query_pathkeys);
01395     }
01396 
01397     return 0;                   /* path ordering not useful */
01398 }
01399 
01400 /*
01401  * truncate_useless_pathkeys
01402  *      Shorten the given pathkey list to just the useful pathkeys.
01403  */
01404 List *
01405 truncate_useless_pathkeys(PlannerInfo *root,
01406                           RelOptInfo *rel,
01407                           List *pathkeys)
01408 {
01409     int         nuseful;
01410     int         nuseful2;
01411 
01412     nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
01413     nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
01414     if (nuseful2 > nuseful)
01415         nuseful = nuseful2;
01416 
01417     /*
01418      * Note: not safe to modify input list destructively, but we can avoid
01419      * copying the list if we're not actually going to change it
01420      */
01421     if (nuseful == 0)
01422         return NIL;
01423     else if (nuseful == list_length(pathkeys))
01424         return pathkeys;
01425     else
01426         return list_truncate(list_copy(pathkeys), nuseful);
01427 }
01428 
01429 /*
01430  * has_useful_pathkeys
01431  *      Detect whether the specified rel could have any pathkeys that are
01432  *      useful according to truncate_useless_pathkeys().
01433  *
01434  * This is a cheap test that lets us skip building pathkeys at all in very
01435  * simple queries.  It's OK to err in the direction of returning "true" when
01436  * there really aren't any usable pathkeys, but erring in the other direction
01437  * is bad --- so keep this in sync with the routines above!
01438  *
01439  * We could make the test more complex, for example checking to see if any of
01440  * the joinclauses are really mergejoinable, but that likely wouldn't win
01441  * often enough to repay the extra cycles.  Queries with neither a join nor
01442  * a sort are reasonably common, though, so this much work seems worthwhile.
01443  */
01444 bool
01445 has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel)
01446 {
01447     if (rel->joininfo != NIL || rel->has_eclass_joins)
01448         return true;            /* might be able to use pathkeys for merging */
01449     if (root->query_pathkeys != NIL)
01450         return true;            /* might be able to use them for ordering */
01451     return false;               /* definitely useless */
01452 }