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-2002, 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.40 2002/09/04 20:31:20 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)
113 * If find both in same equivalence set, no need to do any
116 if (item1here && item2here)
118 /* Better not have seen only one in an earlier set... */
119 Assert(newset == NIL);
123 /* Build the new set only when we know we must */
125 newset = makeList2(item1, item2);
127 /* Found a set to merge into our new set */
128 newset = set_union(newset, curset);
131 * Remove old set from equi_key_list. NOTE this does not
132 * change lnext(cursetlink), so the foreach loop doesn't
135 root->equi_key_list = lremove(curset, root->equi_key_list);
136 freeList(curset); /* might as well recycle old cons cells */
140 /* Build the new set only when we know we must */
142 newset = makeList2(item1, item2);
144 root->equi_key_list = lcons(newset, root->equi_key_list);
148 * generate_implied_equalities
149 * Scan the completed equi_key_list for the query, and generate explicit
150 * qualifications (WHERE clauses) for all the pairwise equalities not
151 * already mentioned in the quals. This is useful because the additional
152 * clauses help the selectivity-estimation code, and in fact it's
153 * *necessary* to ensure that sort keys we think are equivalent really
154 * are (see src/backend/optimizer/README for more info).
156 * This routine just walks the equi_key_list to find all pairwise equalities.
157 * We call process_implied_equality (in plan/initsplan.c) to determine whether
158 * each is already known and add it to the proper restrictinfo list if not.
161 generate_implied_equalities(Query *root)
165 foreach(cursetlink, root->equi_key_list)
167 List *curset = lfirst(cursetlink);
171 * A set containing only two items cannot imply any equalities
172 * beyond the one that created the set, so we can skip it.
174 if (length(curset) < 3)
178 * Match each item in the set with all that appear after it (it's
179 * sufficient to generate A=B, need not process B=A too).
181 foreach(ptr1, curset)
183 PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
186 foreach(ptr2, lnext(ptr1))
188 PathKeyItem *item2 = (PathKeyItem *) lfirst(ptr2);
190 process_implied_equality(root, item1->key, item2->key,
191 item1->sortop, item2->sortop);
198 * make_canonical_pathkey
199 * Given a PathKeyItem, find the equi_key_list subset it is a member of,
200 * if any. If so, return a pointer to that sublist, which is the
201 * canonical representation (for this query) of that PathKeyItem's
202 * equivalence set. If it is not found, add a singleton "equivalence set"
203 * to the equi_key_list and return that --- see compare_pathkeys.
205 * Note that this function must not be used until after we have completed
206 * scanning the WHERE clause for equijoin operators.
209 make_canonical_pathkey(Query *root, PathKeyItem *item)
214 foreach(cursetlink, root->equi_key_list)
216 List *curset = lfirst(cursetlink);
218 if (member(item, curset))
221 newset = makeList1(item);
222 root->equi_key_list = lcons(newset, root->equi_key_list);
227 * canonicalize_pathkeys
228 * Convert a not-necessarily-canonical pathkeys list to canonical form.
230 * Note that this function must not be used until after we have completed
231 * scanning the WHERE clause for equijoin operators.
234 canonicalize_pathkeys(Query *root, List *pathkeys)
236 List *new_pathkeys = NIL;
241 List *pathkey = (List *) lfirst(i);
246 * It's sufficient to look at the first entry in the sublist; if
247 * there are more entries, they're already part of an equivalence
250 Assert(pathkey != NIL);
251 item = (PathKeyItem *) lfirst(pathkey);
252 cpathkey = make_canonical_pathkey(root, item);
255 * Eliminate redundant ordering requests --- ORDER BY A,A is the
256 * same as ORDER BY A. We want to check this only after we have
257 * canonicalized the keys, so that equivalent-key knowledge is
258 * used when deciding if an item is redundant.
260 if (!ptrMember(cpathkey, new_pathkeys))
261 new_pathkeys = lappend(new_pathkeys, cpathkey);
266 /****************************************************************************
267 * PATHKEY COMPARISONS
268 ****************************************************************************/
272 * Compare two pathkeys to see if they are equivalent, and if not whether
273 * one is "better" than the other.
275 * This function may only be applied to canonicalized pathkey lists.
276 * In the canonical representation, sublists can be checked for equality
277 * by simple pointer comparison.
280 compare_pathkeys(List *keys1, List *keys2)
285 for (key1 = keys1, key2 = keys2;
286 key1 != NIL && key2 != NIL;
287 key1 = lnext(key1), key2 = lnext(key2))
289 List *subkey1 = lfirst(key1);
290 List *subkey2 = lfirst(key2);
293 * XXX would like to check that we've been given canonicalized
294 * input, but query root not accessible here...
297 Assert(ptrMember(subkey1, root->equi_key_list));
298 Assert(ptrMember(subkey2, root->equi_key_list));
302 * We will never have two subkeys where one is a subset of the
303 * other, because of the canonicalization process. Either they
304 * are equal or they ain't. Furthermore, we only need pointer
305 * comparison to detect equality.
307 if (subkey1 != subkey2)
308 return PATHKEYS_DIFFERENT; /* no need to keep looking */
312 * If we reached the end of only one list, the other is longer and
313 * therefore not a subset. (We assume the additional sublist(s) of
314 * the other list are not NIL --- no pathkey list should ever have a
317 if (key1 == NIL && key2 == NIL)
318 return PATHKEYS_EQUAL;
320 return PATHKEYS_BETTER1; /* key1 is longer */
321 return PATHKEYS_BETTER2; /* key2 is longer */
325 * compare_noncanonical_pathkeys
326 * Compare two pathkeys to see if they are equivalent, and if not whether
327 * one is "better" than the other. This is used when we must compare
328 * non-canonicalized pathkeys.
330 * A pathkey can be considered better than another if it is a superset:
331 * it contains all the keys of the other plus more. For example, either
332 * ((A) (B)) or ((A B)) is better than ((A)).
334 * Currently, the only user of this routine is grouping_planner(),
335 * and it will only pass single-element sublists (from
336 * make_pathkeys_for_sortclauses). Therefore we don't have to do the
337 * full two-way-subset-inclusion test on each pair of sublists that is
338 * implied by the above statement. Instead we just verify they are
339 * singleton lists and then do an equal(). This could be improved if
343 compare_noncanonical_pathkeys(List *keys1, List *keys2)
348 for (key1 = keys1, key2 = keys2;
349 key1 != NIL && key2 != NIL;
350 key1 = lnext(key1), key2 = lnext(key2))
352 List *subkey1 = lfirst(key1);
353 List *subkey2 = lfirst(key2);
355 Assert(length(subkey1) == 1);
356 Assert(length(subkey2) == 1);
357 if (!equal(subkey1, subkey2))
358 return PATHKEYS_DIFFERENT; /* no need to keep looking */
362 * If we reached the end of only one list, the other is longer and
363 * therefore not a subset. (We assume the additional sublist(s) of
364 * the other list are not NIL --- no pathkey list should ever have a
367 if (key1 == NIL && key2 == NIL)
368 return PATHKEYS_EQUAL;
370 return PATHKEYS_BETTER1; /* key1 is longer */
371 return PATHKEYS_BETTER2; /* key2 is longer */
375 * pathkeys_contained_in
376 * Common special case of compare_pathkeys: we just want to know
377 * if keys2 are at least as well sorted as keys1.
380 pathkeys_contained_in(List *keys1, List *keys2)
382 switch (compare_pathkeys(keys1, keys2))
385 case PATHKEYS_BETTER2:
394 * noncanonical_pathkeys_contained_in
395 * The same, when we don't have canonical pathkeys.
398 noncanonical_pathkeys_contained_in(List *keys1, List *keys2)
400 switch (compare_noncanonical_pathkeys(keys1, keys2))
403 case PATHKEYS_BETTER2:
412 * get_cheapest_path_for_pathkeys
413 * Find the cheapest path (according to the specified criterion) that
414 * satisfies the given pathkeys. Return NULL if no such path.
416 * 'paths' is a list of possible paths that all generate the same relation
417 * 'pathkeys' represents a required ordering (already canonicalized!)
418 * 'cost_criterion' is STARTUP_COST or TOTAL_COST
421 get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
422 CostSelector cost_criterion)
424 Path *matched_path = NULL;
429 Path *path = (Path *) lfirst(i);
432 * Since cost comparison is a lot cheaper than pathkey comparison,
433 * do that first. (XXX is that still true?)
435 if (matched_path != NULL &&
436 compare_path_costs(matched_path, path, cost_criterion) <= 0)
439 if (pathkeys_contained_in(pathkeys, path->pathkeys))
446 * get_cheapest_fractional_path_for_pathkeys
447 * Find the cheapest path (for retrieving a specified fraction of all
448 * the tuples) that satisfies the given pathkeys.
449 * Return NULL if no such path.
451 * See compare_fractional_path_costs() for the interpretation of the fraction
454 * 'paths' is a list of possible paths that all generate the same relation
455 * 'pathkeys' represents a required ordering (already canonicalized!)
456 * 'fraction' is the fraction of the total tuples expected to be retrieved
459 get_cheapest_fractional_path_for_pathkeys(List *paths,
463 Path *matched_path = NULL;
468 Path *path = (Path *) lfirst(i);
471 * Since cost comparison is a lot cheaper than pathkey comparison,
474 if (matched_path != NULL &&
475 compare_fractional_path_costs(matched_path, path, fraction) <= 0)
478 if (pathkeys_contained_in(pathkeys, path->pathkeys))
484 /****************************************************************************
485 * NEW PATHKEY FORMATION
486 ****************************************************************************/
489 * build_index_pathkeys
490 * Build a pathkeys list that describes the ordering induced by an index
491 * scan using the given index. (Note that an unordered index doesn't
492 * induce any ordering; such an index will have no sortop OIDS in
493 * its "ordering" field, and we will return NIL.)
495 * If 'scandir' is BackwardScanDirection, attempt to build pathkeys
496 * representing a backwards scan of the index. Return NIL if can't do it.
499 build_index_pathkeys(Query *root,
502 ScanDirection scandir)
505 int *indexkeys = index->indexkeys;
506 Oid *ordering = index->ordering;
510 if (!indexkeys || indexkeys[0] == 0 ||
511 !ordering || ordering[0] == InvalidOid)
512 return NIL; /* unordered index? */
516 /* Functional index: build a representation of the function call */
517 Func *funcnode = makeNode(Func);
518 List *funcargs = NIL;
520 funcnode->funcid = index->indproc;
521 funcnode->funcresulttype = get_func_rettype(index->indproc);
522 funcnode->funcretset = false; /* can never be a set */
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)
636 * This used to be quite a complex bit of code, but now that all
637 * pathkey sublists start out life canonicalized, we don't have to do
638 * a darn thing here! The inner-rel vars we used to need to add are
639 * *already* part of the outer pathkey!
641 * We do, however, need to truncate the pathkeys list, since it may
642 * contain pathkeys that were useful for forming this joinrel but are
643 * uninteresting to higher levels.
645 return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
648 /****************************************************************************
649 * PATHKEYS AND SORT CLAUSES
650 ****************************************************************************/
653 * make_pathkeys_for_sortclauses
654 * Generate a pathkeys list that represents the sort order specified
655 * by a list of SortClauses (GroupClauses will work too!)
657 * NB: the result is NOT in canonical form, but must be passed through
658 * canonicalize_pathkeys() before it can be used for comparisons or
659 * labeling relation sort orders. (We do things this way because
660 * grouping_planner needs to be able to construct requested pathkeys
661 * before the pathkey equivalence sets have been created for the query.)
663 * 'sortclauses' is a list of SortClause or GroupClause nodes
664 * 'tlist' is the targetlist to find the referenced tlist entries in
667 make_pathkeys_for_sortclauses(List *sortclauses,
670 List *pathkeys = NIL;
673 foreach(i, sortclauses)
675 SortClause *sortcl = (SortClause *) lfirst(i);
677 PathKeyItem *pathkey;
679 sortkey = get_sortgroupclause_expr(sortcl, tlist);
680 pathkey = makePathKeyItem(sortkey, sortcl->sortop);
683 * The pathkey becomes a one-element sublist, for now;
684 * canonicalize_pathkeys() might replace it with a longer sublist
687 pathkeys = lappend(pathkeys, makeList1(pathkey));
692 /****************************************************************************
693 * PATHKEYS AND MERGECLAUSES
694 ****************************************************************************/
697 * cache_mergeclause_pathkeys
698 * Make the cached pathkeys valid in a mergeclause restrictinfo.
700 * RestrictInfo contains fields in which we may cache the result
701 * of looking up the canonical pathkeys for the left and right sides
702 * of the mergeclause. (Note that in normal cases they will be the
703 * same, but not if the mergeclause appears above an OUTER JOIN.)
704 * This is a worthwhile savings because these routines will be invoked
705 * many times when dealing with a many-relation query.
708 cache_mergeclause_pathkeys(Query *root, RestrictInfo *restrictinfo)
713 Assert(restrictinfo->mergejoinoperator != InvalidOid);
715 if (restrictinfo->left_pathkey == NIL)
717 key = (Node *) get_leftop(restrictinfo->clause);
718 item = makePathKeyItem(key, restrictinfo->left_sortop);
719 restrictinfo->left_pathkey = make_canonical_pathkey(root, item);
721 if (restrictinfo->right_pathkey == NIL)
723 key = (Node *) get_rightop(restrictinfo->clause);
724 item = makePathKeyItem(key, restrictinfo->right_sortop);
725 restrictinfo->right_pathkey = make_canonical_pathkey(root, item);
730 * find_mergeclauses_for_pathkeys
731 * This routine attempts to find a set of mergeclauses that can be
732 * used with a specified ordering for one of the input relations.
733 * If successful, it returns a list of mergeclauses.
735 * 'pathkeys' is a pathkeys list showing the ordering of an input path.
736 * It doesn't matter whether it is for the inner or outer path.
737 * 'restrictinfos' is a list of mergejoinable restriction clauses for the
738 * join relation being formed.
740 * The result is NIL if no merge can be done, else a maximal list of
741 * usable mergeclauses (represented as a list of their restrictinfo nodes).
743 * XXX Ideally we ought to be considering context, ie what path orderings
744 * are available on the other side of the join, rather than just making
745 * an arbitrary choice among the mergeclauses that will work for this side
749 find_mergeclauses_for_pathkeys(Query *root,
753 List *mergeclauses = NIL;
756 /* make sure we have pathkeys cached in the clauses */
757 foreach(i, restrictinfos)
759 RestrictInfo *restrictinfo = lfirst(i);
761 cache_mergeclause_pathkeys(root, restrictinfo);
766 List *pathkey = lfirst(i);
767 List *matched_restrictinfos = NIL;
771 * We can match a pathkey against either left or right side of any
772 * mergejoin clause. (We examine both sides since we aren't told
773 * if the given pathkeys are for inner or outer input path; no
774 * confusion is possible.) Furthermore, if there are multiple
775 * matching clauses, take them all. In plain inner-join scenarios
776 * we expect only one match, because redundant-mergeclause
777 * elimination will have removed any redundant mergeclauses from
778 * the input list. However, in outer-join scenarios there might be
779 * multiple matches. An example is
781 * select * from a full join b on a.v1 = b.v1 and a.v2 = b.v2 and
784 * Given the pathkeys ((a.v1), (a.v2)) it is okay to return all three
785 * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and
786 * indeed we *must* do so or we will be unable to form a valid
789 foreach(j, restrictinfos)
791 RestrictInfo *restrictinfo = lfirst(j);
794 * We can compare canonical pathkey sublists by simple pointer
795 * equality; see compare_pathkeys.
797 if ((pathkey == restrictinfo->left_pathkey ||
798 pathkey == restrictinfo->right_pathkey) &&
799 !ptrMember(restrictinfo, mergeclauses))
801 matched_restrictinfos = lappend(matched_restrictinfos,
807 * If we didn't find a mergeclause, we're done --- any additional
808 * sort-key positions in the pathkeys are useless. (But we can
809 * still mergejoin if we found at least one mergeclause.)
811 if (matched_restrictinfos == NIL)
815 * If we did find usable mergeclause(s) for this sort-key
816 * position, add them to result list.
818 mergeclauses = nconc(mergeclauses, matched_restrictinfos);
825 * make_pathkeys_for_mergeclauses
826 * Builds a pathkey list representing the explicit sort order that
827 * must be applied to a path in order to make it usable for the
828 * given mergeclauses.
830 * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
831 * that will be used in a merge join.
832 * 'rel' is the relation the pathkeys will apply to (ie, either the inner
833 * or outer side of the proposed join rel).
835 * Returns a pathkeys list that can be applied to the indicated relation.
837 * Note that it is not this routine's job to decide whether sorting is
838 * actually needed for a particular input path. Assume a sort is necessary;
839 * just make the keys, eh?
842 make_pathkeys_for_mergeclauses(Query *root,
846 List *pathkeys = NIL;
849 foreach(i, mergeclauses)
851 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
855 cache_mergeclause_pathkeys(root, restrictinfo);
857 key = (Node *) get_leftop(restrictinfo->clause);
859 VARISRELMEMBER(((Var *) key)->varno, rel))
861 /* Rel is left side of mergeclause */
862 pathkey = restrictinfo->left_pathkey;
866 key = (Node *) get_rightop(restrictinfo->clause);
868 VARISRELMEMBER(((Var *) key)->varno, rel))
870 /* Rel is right side of mergeclause */
871 pathkey = restrictinfo->right_pathkey;
875 elog(ERROR, "make_pathkeys_for_mergeclauses: can't identify which side of mergeclause to use");
876 pathkey = NIL; /* keep compiler quiet */
881 * When we are given multiple merge clauses, it's possible that
882 * some clauses refer to the same vars as earlier clauses. There's
883 * no reason for us to specify sort keys like (A,B,A) when (A,B)
884 * will do --- and adding redundant sort keys makes add_path think
885 * that this sort order is different from ones that are really the
886 * same, so don't do it. Since we now have a canonicalized
887 * pathkey, a simple ptrMember test is sufficient to detect
890 if (!ptrMember(pathkey, pathkeys))
891 pathkeys = lappend(pathkeys, pathkey);
897 /****************************************************************************
898 * PATHKEY USEFULNESS CHECKS
900 * We only want to remember as many of the pathkeys of a path as have some
901 * potential use, either for subsequent mergejoins or for meeting the query's
902 * requested output ordering. This ensures that add_path() won't consider
903 * a path to have a usefully different ordering unless it really is useful.
904 * These routines check for usefulness of given pathkeys.
905 ****************************************************************************/
908 * pathkeys_useful_for_merging
909 * Count the number of pathkeys that may be useful for mergejoins
910 * above the given relation (by looking at its joininfo lists).
912 * We consider a pathkey potentially useful if it corresponds to the merge
913 * ordering of either side of any joinclause for the rel. This might be
914 * overoptimistic, since joinclauses that appear in different join lists
915 * might never be usable at the same time, but trying to be exact is likely
916 * to be more trouble than it's worth.
919 pathkeys_useful_for_merging(Query *root, RelOptInfo *rel, List *pathkeys)
926 List *pathkey = lfirst(i);
927 bool matched = false;
930 foreach(j, rel->joininfo)
932 JoinInfo *joininfo = (JoinInfo *) lfirst(j);
935 foreach(k, joininfo->jinfo_restrictinfo)
937 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(k);
939 if (restrictinfo->mergejoinoperator == InvalidOid)
941 cache_mergeclause_pathkeys(root, restrictinfo);
944 * We can compare canonical pathkey sublists by simple
945 * pointer equality; see compare_pathkeys.
947 if (pathkey == restrictinfo->left_pathkey ||
948 pathkey == restrictinfo->right_pathkey)
960 * If we didn't find a mergeclause, we're done --- any additional
961 * sort-key positions in the pathkeys are useless. (But we can
962 * still mergejoin if we found at least one mergeclause.)
974 * pathkeys_useful_for_ordering
975 * Count the number of pathkeys that are useful for meeting the
976 * query's requested output ordering.
978 * Unlike merge pathkeys, this is an all-or-nothing affair: it does us
979 * no good to order by just the first key(s) of the requested ordering.
980 * So the result is always either 0 or length(root->query_pathkeys).
983 pathkeys_useful_for_ordering(Query *root, List *pathkeys)
985 if (root->query_pathkeys == NIL)
986 return 0; /* no special ordering requested */
989 return 0; /* unordered path */
991 if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
993 /* It's useful ... or at least the first N keys are */
994 return length(root->query_pathkeys);
997 return 0; /* path ordering not useful */
1001 * truncate_useless_pathkeys
1002 * Shorten the given pathkey list to just the useful pathkeys.
1005 truncate_useless_pathkeys(Query *root,
1012 nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
1013 nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
1014 if (nuseful2 > nuseful)
1018 * Note: not safe to modify input list destructively, but we can avoid
1019 * copying the list if we're not actually going to change it
1021 if (nuseful == length(pathkeys))
1024 return ltruncate(nuseful, listCopy(pathkeys));