1 /*-------------------------------------------------------------------------
4 * Utilities for matching and building path keys
6 * See src/backend/optimizer/README for a great deal of information about
7 * the nature and use of path keys.
10 * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group
11 * Portions Copyright (c) 1994, Regents of the University of California
14 * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.32 2001/03/22 06:16:14 momjian Exp $
16 *-------------------------------------------------------------------------
20 #include "nodes/makefuncs.h"
21 #include "optimizer/clauses.h"
22 #include "optimizer/pathnode.h"
23 #include "optimizer/paths.h"
24 #include "optimizer/planmain.h"
25 #include "optimizer/tlist.h"
26 #include "parser/parsetree.h"
27 #include "parser/parse_func.h"
28 #include "utils/lsyscache.h"
31 static PathKeyItem *makePathKeyItem(Node *key, Oid sortop);
32 static List *make_canonical_pathkey(Query *root, PathKeyItem *item);
33 static Var *find_indexkey_var(Query *root, RelOptInfo *rel,
39 * create a PathKeyItem node
42 makePathKeyItem(Node *key, Oid sortop)
44 PathKeyItem *item = makeNode(PathKeyItem);
47 item->sortop = sortop;
53 * The given clause has a mergejoinable operator, so its two sides
54 * can be considered equal after restriction clause application; in
55 * particular, any pathkey mentioning one side (with the correct sortop)
56 * can be expanded to include the other as well. Record the vars and
57 * associated sortops in the query's equi_key_list for future use.
59 * The query's equi_key_list field points to a list of sublists of PathKeyItem
60 * nodes, where each sublist is a set of two or more vars+sortops that have
61 * been identified as logically equivalent (and, therefore, we may consider
62 * any two in a set to be equal). As described above, we will subsequently
63 * use direct pointers to one of these sublists to represent any pathkey
64 * that involves an equijoined variable.
66 * This code would actually work fine with expressions more complex than
67 * a single Var, but currently it won't see any because check_mergejoinable
68 * won't accept such clauses as mergejoinable.
71 add_equijoined_keys(Query *root, RestrictInfo *restrictinfo)
73 Expr *clause = restrictinfo->clause;
74 PathKeyItem *item1 = makePathKeyItem((Node *) get_leftop(clause),
75 restrictinfo->left_sortop);
76 PathKeyItem *item2 = makePathKeyItem((Node *) get_rightop(clause),
77 restrictinfo->right_sortop);
81 /* We might see a clause X=X; don't make a single-element list from it */
82 if (equal(item1, item2))
86 * Our plan is to make a two-element set, then sweep through the
87 * existing equijoin sets looking for matches to item1 or item2. When
88 * we find one, we remove that set from equi_key_list and union it
89 * into our new set. When done, we add the new set to the front of
92 * It may well be that the two items we're given are already known to be
93 * equijoin-equivalent, in which case we don't need to change our data
94 * structure. If we find both of them in the same equivalence set to
95 * start with, we can quit immediately.
97 * This is a standard UNION-FIND problem, for which there exist better
98 * data structures than simple lists. If this code ever proves to be
99 * a bottleneck then it could be sped up --- but for now, simple is
104 foreach(cursetlink, root->equi_key_list)
106 List *curset = lfirst(cursetlink);
107 bool item1here = member(item1, curset);
108 bool item2here = member(item2, curset);
110 if (item1here || item2here)
114 * If find both in same equivalence set, no need to do any
117 if (item1here && item2here)
119 /* Better not have seen only one in an earlier set... */
120 Assert(newset == NIL);
124 /* Build the new set only when we know we must */
126 newset = makeList2(item1, item2);
128 /* Found a set to merge into our new set */
129 newset = set_union(newset, curset);
132 * Remove old set from equi_key_list. NOTE this does not
133 * change lnext(cursetlink), so the foreach loop doesn't
136 root->equi_key_list = lremove(curset, root->equi_key_list);
137 freeList(curset); /* might as well recycle old cons cells */
141 /* Build the new set only when we know we must */
143 newset = makeList2(item1, item2);
145 root->equi_key_list = lcons(newset, root->equi_key_list);
149 * generate_implied_equalities
150 * Scan the completed equi_key_list for the query, and generate explicit
151 * qualifications (WHERE clauses) for all the pairwise equalities not
152 * already mentioned in the quals. This is useful because the additional
153 * clauses help the selectivity-estimation code, and in fact it's
154 * *necessary* to ensure that sort keys we think are equivalent really
155 * are (see src/backend/optimizer/README for more info).
157 * This routine just walks the equi_key_list to find all pairwise equalities.
158 * We call process_implied_equality (in plan/initsplan.c) to determine whether
159 * each is already known and add it to the proper restrictinfo list if not.
162 generate_implied_equalities(Query *root)
166 foreach(cursetlink, root->equi_key_list)
168 List *curset = lfirst(cursetlink);
172 * A set containing only two items cannot imply any equalities
173 * beyond the one that created the set, so we can skip it.
175 if (length(curset) < 3)
179 * Match each item in the set with all that appear after it (it's
180 * sufficient to generate A=B, need not process B=A too).
182 foreach(ptr1, curset)
184 PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
187 foreach(ptr2, lnext(ptr1))
189 PathKeyItem *item2 = (PathKeyItem *) lfirst(ptr2);
191 process_implied_equality(root, item1->key, item2->key,
192 item1->sortop, item2->sortop);
199 * make_canonical_pathkey
200 * Given a PathKeyItem, find the equi_key_list subset it is a member of,
201 * if any. If so, return a pointer to that sublist, which is the
202 * canonical representation (for this query) of that PathKeyItem's
203 * equivalence set. If it is not found, add a singleton "equivalence set"
204 * to the equi_key_list and return that --- see compare_pathkeys.
206 * Note that this function must not be used until after we have completed
207 * scanning the WHERE clause for equijoin operators.
210 make_canonical_pathkey(Query *root, PathKeyItem *item)
215 foreach(cursetlink, root->equi_key_list)
217 List *curset = lfirst(cursetlink);
219 if (member(item, curset))
222 newset = makeList1(item);
223 root->equi_key_list = lcons(newset, root->equi_key_list);
228 * canonicalize_pathkeys
229 * Convert a not-necessarily-canonical pathkeys list to canonical form.
231 * Note that this function must not be used until after we have completed
232 * scanning the WHERE clause for equijoin operators.
235 canonicalize_pathkeys(Query *root, List *pathkeys)
237 List *new_pathkeys = NIL;
242 List *pathkey = (List *) lfirst(i);
247 * It's sufficient to look at the first entry in the sublist; if
248 * there are more entries, they're already part of an equivalence
251 Assert(pathkey != NIL);
252 item = (PathKeyItem *) lfirst(pathkey);
253 cpathkey = make_canonical_pathkey(root, item);
256 * Eliminate redundant ordering requests --- ORDER BY A,A is the
257 * same as ORDER BY A. We want to check this only after we have
258 * canonicalized the keys, so that equivalent-key knowledge is
259 * used when deciding if an item is redundant.
261 if (!ptrMember(cpathkey, new_pathkeys))
262 new_pathkeys = lappend(new_pathkeys, cpathkey);
267 /****************************************************************************
268 * PATHKEY COMPARISONS
269 ****************************************************************************/
273 * Compare two pathkeys to see if they are equivalent, and if not whether
274 * one is "better" than the other.
276 * This function may only be applied to canonicalized pathkey lists.
277 * In the canonical representation, sublists can be checked for equality
278 * by simple pointer comparison.
281 compare_pathkeys(List *keys1, List *keys2)
286 for (key1 = keys1, key2 = keys2;
287 key1 != NIL && key2 != NIL;
288 key1 = lnext(key1), key2 = lnext(key2))
290 List *subkey1 = lfirst(key1);
291 List *subkey2 = lfirst(key2);
294 * XXX would like to check that we've been given canonicalized
295 * input, but query root not accessible here...
298 Assert(ptrMember(subkey1, root->equi_key_list));
299 Assert(ptrMember(subkey2, root->equi_key_list));
303 * We will never have two subkeys where one is a subset of the
304 * other, because of the canonicalization process. Either they
305 * are equal or they ain't. Furthermore, we only need pointer
306 * comparison to detect equality.
308 if (subkey1 != subkey2)
309 return PATHKEYS_DIFFERENT; /* no need to keep looking */
313 * If we reached the end of only one list, the other is longer and
314 * therefore not a subset. (We assume the additional sublist(s) of
315 * the other list are not NIL --- no pathkey list should ever have a
318 if (key1 == NIL && key2 == NIL)
319 return PATHKEYS_EQUAL;
321 return PATHKEYS_BETTER1;/* key1 is longer */
322 return PATHKEYS_BETTER2; /* key2 is longer */
326 * compare_noncanonical_pathkeys
327 * Compare two pathkeys to see if they are equivalent, and if not whether
328 * one is "better" than the other. This is used when we must compare
329 * non-canonicalized pathkeys.
331 * A pathkey can be considered better than another if it is a superset:
332 * it contains all the keys of the other plus more. For example, either
333 * ((A) (B)) or ((A B)) is better than ((A)).
335 * Currently, the only user of this routine is grouping_planner(),
336 * and it will only pass single-element sublists (from
337 * make_pathkeys_for_sortclauses). Therefore we don't have to do the
338 * full two-way-subset-inclusion test on each pair of sublists that is
339 * implied by the above statement. Instead we just verify they are
340 * singleton lists and then do an equal(). This could be improved if
344 compare_noncanonical_pathkeys(List *keys1, List *keys2)
349 for (key1 = keys1, key2 = keys2;
350 key1 != NIL && key2 != NIL;
351 key1 = lnext(key1), key2 = lnext(key2))
353 List *subkey1 = lfirst(key1);
354 List *subkey2 = lfirst(key2);
356 Assert(length(subkey1) == 1);
357 Assert(length(subkey2) == 1);
358 if (!equal(subkey1, subkey2))
359 return PATHKEYS_DIFFERENT; /* no need to keep looking */
363 * If we reached the end of only one list, the other is longer and
364 * therefore not a subset. (We assume the additional sublist(s) of
365 * the other list are not NIL --- no pathkey list should ever have a
368 if (key1 == NIL && key2 == NIL)
369 return PATHKEYS_EQUAL;
371 return PATHKEYS_BETTER1;/* key1 is longer */
372 return PATHKEYS_BETTER2; /* key2 is longer */
376 * pathkeys_contained_in
377 * Common special case of compare_pathkeys: we just want to know
378 * if keys2 are at least as well sorted as keys1.
381 pathkeys_contained_in(List *keys1, List *keys2)
383 switch (compare_pathkeys(keys1, keys2))
386 case PATHKEYS_BETTER2:
395 * noncanonical_pathkeys_contained_in
396 * The same, when we don't have canonical pathkeys.
399 noncanonical_pathkeys_contained_in(List *keys1, List *keys2)
401 switch (compare_noncanonical_pathkeys(keys1, keys2))
404 case PATHKEYS_BETTER2:
413 * get_cheapest_path_for_pathkeys
414 * Find the cheapest path (according to the specified criterion) that
415 * satisfies the given pathkeys. Return NULL if no such path.
417 * 'paths' is a list of possible paths that all generate the same relation
418 * 'pathkeys' represents a required ordering (already canonicalized!)
419 * 'cost_criterion' is STARTUP_COST or TOTAL_COST
422 get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
423 CostSelector cost_criterion)
425 Path *matched_path = NULL;
430 Path *path = (Path *) lfirst(i);
433 * Since cost comparison is a lot cheaper than pathkey comparison,
434 * do that first. (XXX is that still true?)
436 if (matched_path != NULL &&
437 compare_path_costs(matched_path, path, cost_criterion) <= 0)
440 if (pathkeys_contained_in(pathkeys, path->pathkeys))
447 * get_cheapest_fractional_path_for_pathkeys
448 * Find the cheapest path (for retrieving a specified fraction of all
449 * the tuples) that satisfies the given pathkeys.
450 * Return NULL if no such path.
452 * See compare_fractional_path_costs() for the interpretation of the fraction
455 * 'paths' is a list of possible paths that all generate the same relation
456 * 'pathkeys' represents a required ordering (already canonicalized!)
457 * 'fraction' is the fraction of the total tuples expected to be retrieved
460 get_cheapest_fractional_path_for_pathkeys(List *paths,
464 Path *matched_path = NULL;
469 Path *path = (Path *) lfirst(i);
472 * Since cost comparison is a lot cheaper than pathkey comparison,
475 if (matched_path != NULL &&
476 compare_fractional_path_costs(matched_path, path, fraction) <= 0)
479 if (pathkeys_contained_in(pathkeys, path->pathkeys))
485 /****************************************************************************
486 * NEW PATHKEY FORMATION
487 ****************************************************************************/
490 * build_index_pathkeys
491 * Build a pathkeys list that describes the ordering induced by an index
492 * scan using the given index. (Note that an unordered index doesn't
493 * induce any ordering; such an index will have no sortop OIDS in
494 * its "ordering" field, and we will return NIL.)
496 * If 'scandir' is BackwardScanDirection, attempt to build pathkeys
497 * representing a backwards scan of the index. Return NIL if can't do it.
500 build_index_pathkeys(Query *root,
503 ScanDirection scandir)
506 int *indexkeys = index->indexkeys;
507 Oid *ordering = index->ordering;
511 if (!indexkeys || indexkeys[0] == 0 ||
512 !ordering || ordering[0] == InvalidOid)
513 return NIL; /* unordered index? */
517 /* Functional index: build a representation of the function call */
518 Func *funcnode = makeNode(Func);
519 List *funcargs = NIL;
521 funcnode->funcid = index->indproc;
522 funcnode->functype = get_func_rettype(index->indproc);
523 funcnode->func_fcache = NULL;
525 while (*indexkeys != 0)
527 funcargs = lappend(funcargs,
528 find_indexkey_var(root, rel, *indexkeys));
533 if (ScanDirectionIsBackward(scandir))
535 sortop = get_commutator(sortop);
536 if (sortop == InvalidOid)
537 return NIL; /* oops, no reverse sort operator? */
540 /* Make a one-sublist pathkeys list for the function expression */
541 item = makePathKeyItem((Node *) make_funcclause(funcnode, funcargs),
543 retval = makeList1(make_canonical_pathkey(root, item));
547 /* Normal non-functional index */
548 while (*indexkeys != 0 && *ordering != InvalidOid)
550 Var *relvar = find_indexkey_var(root, rel, *indexkeys);
554 if (ScanDirectionIsBackward(scandir))
556 sortop = get_commutator(sortop);
557 if (sortop == InvalidOid)
558 break; /* oops, no reverse sort operator? */
561 /* OK, make a sublist for this sort key */
562 item = makePathKeyItem((Node *) relvar, sortop);
563 cpathkey = make_canonical_pathkey(root, item);
566 * Eliminate redundant ordering info; could happen if query is
567 * such that index keys are equijoined...
569 if (!ptrMember(cpathkey, retval))
570 retval = lappend(retval, cpathkey);
580 * Find or make a Var node for the specified attribute of the rel.
582 * We first look for the var in the rel's target list, because that's
583 * easy and fast. But the var might not be there (this should normally
584 * only happen for vars that are used in WHERE restriction clauses,
585 * but not in join clauses or in the SELECT target list). In that case,
586 * gin up a Var node the hard way.
589 find_indexkey_var(Query *root, RelOptInfo *rel, AttrNumber varattno)
597 foreach(temp, rel->targetlist)
599 Var *tle_var = get_expr(lfirst(temp));
601 if (IsA(tle_var, Var) &&tle_var->varattno == varattno)
605 relid = lfirsti(rel->relids);
606 reloid = getrelid(relid, root->rtable);
607 vartypeid = get_atttype(reloid, varattno);
608 type_mod = get_atttypmod(reloid, varattno);
610 return makeVar(relid, varattno, vartypeid, type_mod, 0);
614 * build_join_pathkeys
615 * Build the path keys for a join relation constructed by mergejoin or
616 * nestloop join. These keys should include all the path key vars of the
617 * outer path (since the join will retain the ordering of the outer path)
618 * plus any vars of the inner path that are equijoined to the outer vars.
620 * Per the discussion in backend/optimizer/README, equijoined inner vars
621 * can be considered path keys of the result, just the same as the outer
622 * vars they were joined with; furthermore, it doesn't matter what kind
623 * of join algorithm is actually used.
625 * 'joinrel' is the join relation that paths are being formed for
626 * 'outer_pathkeys' is the list of the current outer path's path keys
628 * Returns the list of new path keys.
631 build_join_pathkeys(Query *root,
633 List *outer_pathkeys)
637 * This used to be quite a complex bit of code, but now that all
638 * pathkey sublists start out life canonicalized, we don't have to do
639 * a darn thing here! The inner-rel vars we used to need to add are
640 * *already* part of the outer pathkey!
642 * We do, however, need to truncate the pathkeys list, since it may
643 * contain pathkeys that were useful for forming this joinrel but are
644 * uninteresting to higher levels.
646 return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
649 /****************************************************************************
650 * PATHKEYS AND SORT CLAUSES
651 ****************************************************************************/
654 * make_pathkeys_for_sortclauses
655 * Generate a pathkeys list that represents the sort order specified
656 * by a list of SortClauses (GroupClauses will work too!)
658 * NB: the result is NOT in canonical form, but must be passed through
659 * canonicalize_pathkeys() before it can be used for comparisons or
660 * labeling relation sort orders. (We do things this way because
661 * grouping_planner needs to be able to construct requested pathkeys
662 * before the pathkey equivalence sets have been created for the query.)
664 * 'sortclauses' is a list of SortClause or GroupClause nodes
665 * 'tlist' is the targetlist to find the referenced tlist entries in
668 make_pathkeys_for_sortclauses(List *sortclauses,
671 List *pathkeys = NIL;
674 foreach(i, sortclauses)
676 SortClause *sortcl = (SortClause *) lfirst(i);
678 PathKeyItem *pathkey;
680 sortkey = get_sortgroupclause_expr(sortcl, tlist);
681 pathkey = makePathKeyItem(sortkey, sortcl->sortop);
684 * The pathkey becomes a one-element sublist, for now;
685 * canonicalize_pathkeys() might replace it with a longer sublist
688 pathkeys = lappend(pathkeys, makeList1(pathkey));
693 /****************************************************************************
694 * PATHKEYS AND MERGECLAUSES
695 ****************************************************************************/
698 * cache_mergeclause_pathkeys
699 * Make the cached pathkeys valid in a mergeclause restrictinfo.
701 * RestrictInfo contains fields in which we may cache the result
702 * of looking up the canonical pathkeys for the left and right sides
703 * of the mergeclause. (Note that in normal cases they will be the
704 * same, but not if the mergeclause appears above an OUTER JOIN.)
705 * This is a worthwhile savings because these routines will be invoked
706 * many times when dealing with a many-relation query.
709 cache_mergeclause_pathkeys(Query *root, RestrictInfo *restrictinfo)
714 Assert(restrictinfo->mergejoinoperator != InvalidOid);
716 if (restrictinfo->left_pathkey == NIL)
718 key = (Node *) get_leftop(restrictinfo->clause);
719 item = makePathKeyItem(key, restrictinfo->left_sortop);
720 restrictinfo->left_pathkey = make_canonical_pathkey(root, item);
722 if (restrictinfo->right_pathkey == NIL)
724 key = (Node *) get_rightop(restrictinfo->clause);
725 item = makePathKeyItem(key, restrictinfo->right_sortop);
726 restrictinfo->right_pathkey = make_canonical_pathkey(root, item);
731 * find_mergeclauses_for_pathkeys
732 * This routine attempts to find a set of mergeclauses that can be
733 * used with a specified ordering for one of the input relations.
734 * If successful, it returns a list of mergeclauses.
736 * 'pathkeys' is a pathkeys list showing the ordering of an input path.
737 * It doesn't matter whether it is for the inner or outer path.
738 * 'restrictinfos' is a list of mergejoinable restriction clauses for the
739 * join relation being formed.
741 * The result is NIL if no merge can be done, else a maximal list of
742 * usable mergeclauses (represented as a list of their restrictinfo nodes).
744 * XXX Ideally we ought to be considering context, ie what path orderings
745 * are available on the other side of the join, rather than just making
746 * an arbitrary choice among the mergeclauses that will work for this side
750 find_mergeclauses_for_pathkeys(Query *root,
754 List *mergeclauses = NIL;
759 List *pathkey = lfirst(i);
760 RestrictInfo *matched_restrictinfo = NULL;
764 * We can match a pathkey against either left or right side of any
765 * mergejoin clause we haven't used yet. For the moment we use a
766 * dumb "greedy" algorithm with no backtracking. Is it worth
767 * being any smarter to make a longer list of usable mergeclauses?
770 foreach(j, restrictinfos)
772 RestrictInfo *restrictinfo = lfirst(j);
774 cache_mergeclause_pathkeys(root, restrictinfo);
777 * We can compare canonical pathkey sublists by simple pointer
778 * equality; see compare_pathkeys.
780 if ((pathkey == restrictinfo->left_pathkey ||
781 pathkey == restrictinfo->right_pathkey) &&
782 !ptrMember(restrictinfo, mergeclauses))
784 matched_restrictinfo = restrictinfo;
790 * If we didn't find a mergeclause, we're done --- any additional
791 * sort-key positions in the pathkeys are useless. (But we can
792 * still mergejoin if we found at least one mergeclause.)
794 if (!matched_restrictinfo)
798 * If we did find a usable mergeclause for this sort-key position,
799 * add it to result list.
801 mergeclauses = lappend(mergeclauses, matched_restrictinfo);
808 * make_pathkeys_for_mergeclauses
809 * Builds a pathkey list representing the explicit sort order that
810 * must be applied to a path in order to make it usable for the
811 * given mergeclauses.
813 * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
814 * that will be used in a merge join.
815 * 'rel' is the relation the pathkeys will apply to (ie, either the inner
816 * or outer side of the proposed join rel).
818 * Returns a pathkeys list that can be applied to the indicated relation.
820 * Note that it is not this routine's job to decide whether sorting is
821 * actually needed for a particular input path. Assume a sort is necessary;
822 * just make the keys, eh?
825 make_pathkeys_for_mergeclauses(Query *root,
829 List *pathkeys = NIL;
832 foreach(i, mergeclauses)
834 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
838 cache_mergeclause_pathkeys(root, restrictinfo);
840 key = (Node *) get_leftop(restrictinfo->clause);
841 if (IsA(key, Var) &&intMember(((Var *) key)->varno, rel->relids))
843 /* Rel is left side of mergeclause */
844 pathkey = restrictinfo->left_pathkey;
848 key = (Node *) get_rightop(restrictinfo->clause);
849 if (IsA(key, Var) &&intMember(((Var *) key)->varno, rel->relids))
851 /* Rel is right side of mergeclause */
852 pathkey = restrictinfo->right_pathkey;
856 elog(ERROR, "make_pathkeys_for_mergeclauses: can't identify which side of mergeclause to use");
857 pathkey = NIL; /* keep compiler quiet */
862 * When we are given multiple merge clauses, it's possible that
863 * some clauses refer to the same vars as earlier clauses. There's
864 * no reason for us to specify sort keys like (A,B,A) when (A,B)
865 * will do --- and adding redundant sort keys makes add_path think
866 * that this sort order is different from ones that are really the
867 * same, so don't do it. Since we now have a canonicalized
868 * pathkey, a simple ptrMember test is sufficient to detect
871 if (!ptrMember(pathkey, pathkeys))
872 pathkeys = lappend(pathkeys, pathkey);
878 /****************************************************************************
879 * PATHKEY USEFULNESS CHECKS
881 * We only want to remember as many of the pathkeys of a path as have some
882 * potential use, either for subsequent mergejoins or for meeting the query's
883 * requested output ordering. This ensures that add_path() won't consider
884 * a path to have a usefully different ordering unless it really is useful.
885 * These routines check for usefulness of given pathkeys.
886 ****************************************************************************/
889 * pathkeys_useful_for_merging
890 * Count the number of pathkeys that may be useful for mergejoins
891 * above the given relation (by looking at its joininfo lists).
893 * We consider a pathkey potentially useful if it corresponds to the merge
894 * ordering of either side of any joinclause for the rel. This might be
895 * overoptimistic, since joinclauses that appear in different join lists
896 * might never be usable at the same time, but trying to be exact is likely
897 * to be more trouble than it's worth.
900 pathkeys_useful_for_merging(Query *root, RelOptInfo *rel, List *pathkeys)
907 List *pathkey = lfirst(i);
908 bool matched = false;
911 foreach(j, rel->joininfo)
913 JoinInfo *joininfo = (JoinInfo *) lfirst(j);
916 foreach(k, joininfo->jinfo_restrictinfo)
918 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(k);
920 if (restrictinfo->mergejoinoperator == InvalidOid)
922 cache_mergeclause_pathkeys(root, restrictinfo);
925 * We can compare canonical pathkey sublists by simple
926 * pointer equality; see compare_pathkeys.
928 if (pathkey == restrictinfo->left_pathkey ||
929 pathkey == restrictinfo->right_pathkey)
941 * If we didn't find a mergeclause, we're done --- any additional
942 * sort-key positions in the pathkeys are useless. (But we can
943 * still mergejoin if we found at least one mergeclause.)
955 * pathkeys_useful_for_ordering
956 * Count the number of pathkeys that are useful for meeting the
957 * query's requested output ordering.
959 * Unlike merge pathkeys, this is an all-or-nothing affair: it does us
960 * no good to order by just the first key(s) of the requested ordering.
961 * So the result is always either 0 or length(root->query_pathkeys).
964 pathkeys_useful_for_ordering(Query *root, List *pathkeys)
966 if (root->query_pathkeys == NIL)
967 return 0; /* no special ordering requested */
970 return 0; /* unordered path */
972 if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
974 /* It's useful ... or at least the first N keys are */
975 return length(root->query_pathkeys);
978 return 0; /* path ordering not useful */
982 * truncate_useless_pathkeys
983 * Shorten the given pathkey list to just the useful pathkeys.
986 truncate_useless_pathkeys(Query *root,
993 nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
994 nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
995 if (nuseful2 > nuseful)
999 * Note: not safe to modify input list destructively, but we can avoid
1000 * copying the list if we're not actually going to change it
1002 if (nuseful == length(pathkeys))
1005 return ltruncate(nuseful, listCopy(pathkeys));