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-2003, PostgreSQL Global Development Group
11 * Portions Copyright (c) 1994, Regents of the University of California
14 * $PostgreSQL: pgsql/src/backend/optimizer/path/pathkeys.c,v 1.58 2004/05/30 23:40:28 neilc 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 "optimizer/var.h"
27 #include "parser/parsetree.h"
28 #include "parser/parse_expr.h"
29 #include "parser/parse_func.h"
30 #include "utils/lsyscache.h"
31 #include "utils/memutils.h"
34 static PathKeyItem *makePathKeyItem(Node *key, Oid sortop, bool checkType);
35 static List *make_canonical_pathkey(Query *root, PathKeyItem *item);
36 static Var *find_indexkey_var(Query *root, RelOptInfo *rel,
42 * create a PathKeyItem node
45 makePathKeyItem(Node *key, Oid sortop, bool checkType)
47 PathKeyItem *item = makeNode(PathKeyItem);
50 * Some callers pass expressions that are not necessarily of the same
51 * type as the sort operator expects as input (for example when dealing
52 * with an index that uses binary-compatible operators). We must relabel
53 * these with the correct type so that the key expressions will be seen
54 * as equal() to expressions that have been correctly labeled.
61 op_input_types(sortop, &lefttype, &righttype);
62 if (exprType(key) != lefttype)
63 key = (Node *) makeRelabelType((Expr *) key,
69 item->sortop = sortop;
75 * The given clause has a mergejoinable operator, so its two sides
76 * can be considered equal after restriction clause application; in
77 * particular, any pathkey mentioning one side (with the correct sortop)
78 * can be expanded to include the other as well. Record the exprs and
79 * associated sortops in the query's equi_key_list for future use.
81 * The query's equi_key_list field points to a list of sublists of PathKeyItem
82 * nodes, where each sublist is a set of two or more exprs+sortops that have
83 * been identified as logically equivalent (and, therefore, we may consider
84 * any two in a set to be equal). As described above, we will subsequently
85 * use direct pointers to one of these sublists to represent any pathkey
86 * that involves an equijoined variable.
89 add_equijoined_keys(Query *root, RestrictInfo *restrictinfo)
91 Expr *clause = restrictinfo->clause;
92 PathKeyItem *item1 = makePathKeyItem(get_leftop(clause),
93 restrictinfo->left_sortop,
95 PathKeyItem *item2 = makePathKeyItem(get_rightop(clause),
96 restrictinfo->right_sortop,
101 /* We might see a clause X=X; don't make a single-element list from it */
102 if (equal(item1, item2))
106 * Our plan is to make a two-element set, then sweep through the
107 * existing equijoin sets looking for matches to item1 or item2. When
108 * we find one, we remove that set from equi_key_list and union it
109 * into our new set. When done, we add the new set to the front of
112 * It may well be that the two items we're given are already known to be
113 * equijoin-equivalent, in which case we don't need to change our data
114 * structure. If we find both of them in the same equivalence set to
115 * start with, we can quit immediately.
117 * This is a standard UNION-FIND problem, for which there exist better
118 * data structures than simple lists. If this code ever proves to be
119 * a bottleneck then it could be sped up --- but for now, simple is
124 /* cannot use foreach here because of possible lremove */
125 cursetlink = list_head(root->equi_key_list);
128 List *curset = (List *) lfirst(cursetlink);
129 bool item1here = list_member(curset, item1);
130 bool item2here = list_member(curset, item2);
132 /* must advance cursetlink before lremove possibly pfree's it */
133 cursetlink = lnext(cursetlink);
135 if (item1here || item2here)
138 * If find both in same equivalence set, no need to do any
141 if (item1here && item2here)
143 /* Better not have seen only one in an earlier set... */
144 Assert(newset == NIL);
148 /* Build the new set only when we know we must */
150 newset = list_make2(item1, item2);
152 /* Found a set to merge into our new set */
153 newset = list_union(newset, curset);
156 * Remove old set from equi_key_list.
158 root->equi_key_list = list_delete_ptr(root->equi_key_list, curset);
159 list_free(curset); /* might as well recycle old cons cells */
163 /* Build the new set only when we know we must */
165 newset = list_make2(item1, item2);
167 root->equi_key_list = lcons(newset, root->equi_key_list);
171 * generate_implied_equalities
172 * Scan the completed equi_key_list for the query, and generate explicit
173 * qualifications (WHERE clauses) for all the pairwise equalities not
174 * already mentioned in the quals; or remove qualifications found to be
177 * Adding deduced equalities is useful because the additional clauses help
178 * the selectivity-estimation code and may allow better joins to be chosen;
179 * and in fact it's *necessary* to ensure that sort keys we think are
180 * equivalent really are (see src/backend/optimizer/README for more info).
182 * If an equi_key_list set includes any constants then we adopt a different
183 * strategy: we record all the "var = const" deductions we can make, and
184 * actively remove all the "var = var" clauses that are implied by the set
185 * (including the clauses that originally gave rise to the set!). The reason
186 * is that given input like "a = b AND b = 42", once we have deduced "a = 42"
187 * there is no longer any need to apply the clause "a = b"; not only is
188 * it a waste of time to check it, but we will misestimate selectivity if the
189 * clause is left in. So we must remove it. For this purpose, any pathkey
190 * item that mentions no Vars of the current level can be taken as a constant.
191 * (The only case where this would be risky is if the item contains volatile
192 * functions; but we will never consider such an expression to be a pathkey
193 * at all, because check_mergejoinable() will reject it.)
195 * This routine just walks the equi_key_list to find all pairwise equalities.
196 * We call process_implied_equality (in plan/initsplan.c) to adjust the
197 * restrictinfo datastructures for each pair.
200 generate_implied_equalities(Query *root)
202 ListCell *cursetlink;
204 foreach(cursetlink, root->equi_key_list)
206 List *curset = (List *) lfirst(cursetlink);
207 int nitems = list_length(curset);
214 * A set containing only two items cannot imply any equalities
215 * beyond the one that created the set, so we can skip it.
221 * Collect info about relids mentioned in each item. For this
222 * routine we only really care whether there are any at all in
223 * each item, but process_implied_equality() needs the exact sets,
224 * so we may as well pull them here.
226 relids = (Relids *) palloc(nitems * sizeof(Relids));
229 foreach(ptr1, curset)
231 PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
233 relids[i1] = pull_varnos(item1->key);
234 if (bms_is_empty(relids[i1]))
240 * Match each item in the set with all that appear after it (it's
241 * sufficient to generate A=B, need not process B=A too).
244 foreach(ptr1, curset)
246 PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
247 bool i1_is_variable = !bms_is_empty(relids[i1]);
251 for_each_cell(ptr2, lnext(ptr1))
253 PathKeyItem *item2 = (PathKeyItem *) lfirst(ptr2);
254 bool i2_is_variable = !bms_is_empty(relids[i2]);
257 * If it's "const = const" then just ignore it altogether.
258 * There is no place in the restrictinfo structure to
259 * store it. (If the two consts are in fact unequal, then
260 * propagating the comparison to Vars will cause us to
261 * produce zero rows out, as expected.)
263 if (i1_is_variable || i2_is_variable)
266 * Tell process_implied_equality to delete the clause,
267 * not add it, if it's "var = var" and we have
268 * constants present in the list.
270 bool delete_it = (have_consts &&
274 process_implied_equality(root,
275 item1->key, item2->key,
276 item1->sortop, item2->sortop,
277 relids[i1], relids[i2],
289 * Detect whether two expressions are known equal due to equijoin clauses.
291 * Note: does not bother to check for "equal(item1, item2)"; caller must
292 * check that case if it's possible to pass identical items.
295 exprs_known_equal(Query *root, Node *item1, Node *item2)
297 ListCell *cursetlink;
299 foreach(cursetlink, root->equi_key_list)
301 List *curset = (List *) lfirst(cursetlink);
302 bool item1member = false;
303 bool item2member = false;
308 PathKeyItem *pitem = (PathKeyItem *) lfirst(ptr);
310 if (equal(item1, pitem->key))
312 else if (equal(item2, pitem->key))
314 /* Exit as soon as equality is proven */
315 if (item1member && item2member)
324 * make_canonical_pathkey
325 * Given a PathKeyItem, find the equi_key_list subset it is a member of,
326 * if any. If so, return a pointer to that sublist, which is the
327 * canonical representation (for this query) of that PathKeyItem's
328 * equivalence set. If it is not found, add a singleton "equivalence set"
329 * to the equi_key_list and return that --- see compare_pathkeys.
331 * Note that this function must not be used until after we have completed
332 * scanning the WHERE clause for equijoin operators.
335 make_canonical_pathkey(Query *root, PathKeyItem *item)
338 ListCell *cursetlink;
340 foreach(cursetlink, root->equi_key_list)
342 List *curset = (List *) lfirst(cursetlink);
344 if (list_member(curset, item))
347 newset = list_make1(item);
348 root->equi_key_list = lcons(newset, root->equi_key_list);
353 * canonicalize_pathkeys
354 * Convert a not-necessarily-canonical pathkeys list to canonical form.
356 * Note that this function must not be used until after we have completed
357 * scanning the WHERE clause for equijoin operators.
360 canonicalize_pathkeys(Query *root, List *pathkeys)
362 List *new_pathkeys = NIL;
367 List *pathkey = (List *) lfirst(l);
372 * It's sufficient to look at the first entry in the sublist; if
373 * there are more entries, they're already part of an equivalence
376 Assert(pathkey != NIL);
377 item = (PathKeyItem *) linitial(pathkey);
378 cpathkey = make_canonical_pathkey(root, item);
381 * Eliminate redundant ordering requests --- ORDER BY A,A is the
382 * same as ORDER BY A. We want to check this only after we have
383 * canonicalized the keys, so that equivalent-key knowledge is
384 * used when deciding if an item is redundant.
386 if (!list_member_ptr(new_pathkeys, cpathkey))
387 new_pathkeys = lappend(new_pathkeys, cpathkey);
394 * count_canonical_peers
395 * Given a PathKeyItem, find the equi_key_list subset it is a member of,
396 * if any. If so, return the number of other members of the set.
397 * If not, return 0 (without actually adding it to our equi_key_list).
399 * This is a hack to support the rather bogus heuristics in
400 * build_subquery_pathkeys.
403 count_canonical_peers(Query *root, PathKeyItem *item)
405 ListCell *cursetlink;
407 foreach(cursetlink, root->equi_key_list)
409 List *curset = (List *) lfirst(cursetlink);
411 if (list_member(curset, item))
412 return list_length(curset) - 1;
417 /****************************************************************************
418 * PATHKEY COMPARISONS
419 ****************************************************************************/
423 * Compare two pathkeys to see if they are equivalent, and if not whether
424 * one is "better" than the other.
426 * This function may only be applied to canonicalized pathkey lists.
427 * In the canonical representation, sublists can be checked for equality
428 * by simple pointer comparison.
431 compare_pathkeys(List *keys1, List *keys2)
436 forboth(key1, keys1, key2, keys2)
438 List *subkey1 = (List *) lfirst(key1);
439 List *subkey2 = (List *) lfirst(key2);
442 * XXX would like to check that we've been given canonicalized
443 * input, but query root not accessible here...
446 Assert(list_member_ptr(root->equi_key_list, subkey1));
447 Assert(list_member_ptr(root->equi_key_list, subkey2));
451 * We will never have two subkeys where one is a subset of the
452 * other, because of the canonicalization process. Either they
453 * are equal or they ain't. Furthermore, we only need pointer
454 * comparison to detect equality.
456 if (subkey1 != subkey2)
457 return PATHKEYS_DIFFERENT; /* no need to keep looking */
461 * If we reached the end of only one list, the other is longer and
462 * therefore not a subset. (We assume the additional sublist(s) of
463 * the other list are not NIL --- no pathkey list should ever have a
466 if (key1 == NULL && key2 == NULL)
467 return PATHKEYS_EQUAL;
469 return PATHKEYS_BETTER1; /* key1 is longer */
470 return PATHKEYS_BETTER2; /* key2 is longer */
474 * compare_noncanonical_pathkeys
475 * Compare two pathkeys to see if they are equivalent, and if not whether
476 * one is "better" than the other. This is used when we must compare
477 * non-canonicalized pathkeys.
479 * A pathkey can be considered better than another if it is a superset:
480 * it contains all the keys of the other plus more. For example, either
481 * ((A) (B)) or ((A B)) is better than ((A)).
483 * Currently, the only user of this routine is grouping_planner(),
484 * and it will only pass single-element sublists (from
485 * make_pathkeys_for_sortclauses). Therefore we don't have to do the
486 * full two-way-subset-inclusion test on each pair of sublists that is
487 * implied by the above statement. Instead we just verify they are
488 * singleton lists and then do an equal(). This could be improved if
492 compare_noncanonical_pathkeys(List *keys1, List *keys2)
497 forboth(key1, keys1, key2, keys2)
499 List *subkey1 = (List *) lfirst(key1);
500 List *subkey2 = (List *) lfirst(key2);
502 Assert(list_length(subkey1) == 1);
503 Assert(list_length(subkey2) == 1);
504 if (!equal(subkey1, subkey2))
505 return PATHKEYS_DIFFERENT; /* no need to keep looking */
509 * If we reached the end of only one list, the other is longer and
510 * therefore not a subset. (We assume the additional sublist(s) of
511 * the other list are not NIL --- no pathkey list should ever have a
514 if (key1 == NULL && key2 == NULL)
515 return PATHKEYS_EQUAL;
517 return PATHKEYS_BETTER1; /* key1 is longer */
518 return PATHKEYS_BETTER2; /* key2 is longer */
522 * pathkeys_contained_in
523 * Common special case of compare_pathkeys: we just want to know
524 * if keys2 are at least as well sorted as keys1.
527 pathkeys_contained_in(List *keys1, List *keys2)
529 switch (compare_pathkeys(keys1, keys2))
532 case PATHKEYS_BETTER2:
541 * noncanonical_pathkeys_contained_in
542 * The same, when we don't have canonical pathkeys.
545 noncanonical_pathkeys_contained_in(List *keys1, List *keys2)
547 switch (compare_noncanonical_pathkeys(keys1, keys2))
550 case PATHKEYS_BETTER2:
559 * get_cheapest_path_for_pathkeys
560 * Find the cheapest path (according to the specified criterion) that
561 * satisfies the given pathkeys. Return NULL if no such path.
563 * 'paths' is a list of possible paths that all generate the same relation
564 * 'pathkeys' represents a required ordering (already canonicalized!)
565 * 'cost_criterion' is STARTUP_COST or TOTAL_COST
568 get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
569 CostSelector cost_criterion)
571 Path *matched_path = NULL;
576 Path *path = (Path *) lfirst(l);
579 * Since cost comparison is a lot cheaper than pathkey comparison,
580 * do that first. (XXX is that still true?)
582 if (matched_path != NULL &&
583 compare_path_costs(matched_path, path, cost_criterion) <= 0)
586 if (pathkeys_contained_in(pathkeys, path->pathkeys))
593 * get_cheapest_fractional_path_for_pathkeys
594 * Find the cheapest path (for retrieving a specified fraction of all
595 * the tuples) that satisfies the given pathkeys.
596 * Return NULL if no such path.
598 * See compare_fractional_path_costs() for the interpretation of the fraction
601 * 'paths' is a list of possible paths that all generate the same relation
602 * 'pathkeys' represents a required ordering (already canonicalized!)
603 * 'fraction' is the fraction of the total tuples expected to be retrieved
606 get_cheapest_fractional_path_for_pathkeys(List *paths,
610 Path *matched_path = NULL;
615 Path *path = (Path *) lfirst(l);
618 * Since cost comparison is a lot cheaper than pathkey comparison,
621 if (matched_path != NULL &&
622 compare_fractional_path_costs(matched_path, path, fraction) <= 0)
625 if (pathkeys_contained_in(pathkeys, path->pathkeys))
631 /****************************************************************************
632 * NEW PATHKEY FORMATION
633 ****************************************************************************/
636 * build_index_pathkeys
637 * Build a pathkeys list that describes the ordering induced by an index
638 * scan using the given index. (Note that an unordered index doesn't
639 * induce any ordering; such an index will have no sortop OIDS in
640 * its "ordering" field, and we will return NIL.)
642 * If 'scandir' is BackwardScanDirection, attempt to build pathkeys
643 * representing a backwards scan of the index. Return NIL if can't do it.
645 * We generate the full pathkeys list whether or not all are useful for the
646 * current query. Caller should do truncate_useless_pathkeys().
649 build_index_pathkeys(Query *root,
652 ScanDirection scandir)
655 int *indexkeys = index->indexkeys;
656 Oid *ordering = index->ordering;
657 ListCell *indexprs_item = list_head(index->indexprs);
659 while (*ordering != InvalidOid)
667 if (ScanDirectionIsBackward(scandir))
669 sortop = get_commutator(sortop);
670 if (sortop == InvalidOid)
671 break; /* oops, no reverse sort operator? */
676 /* simple index column */
677 indexkey = (Node *) find_indexkey_var(root, rel, *indexkeys);
681 /* expression --- assume we need not copy it */
682 if (indexprs_item == NULL)
683 elog(ERROR, "wrong number of index expressions");
684 indexkey = (Node *) lfirst(indexprs_item);
685 indexprs_item = lnext(indexprs_item);
688 /* OK, make a sublist for this sort key */
689 item = makePathKeyItem(indexkey, sortop, true);
690 cpathkey = make_canonical_pathkey(root, item);
693 * Eliminate redundant ordering info; could happen if query is
694 * such that index keys are equijoined...
696 if (!list_member_ptr(retval, cpathkey))
697 retval = lappend(retval, cpathkey);
707 * Find or make a Var node for the specified attribute of the rel.
709 * We first look for the var in the rel's target list, because that's
710 * easy and fast. But the var might not be there (this should normally
711 * only happen for vars that are used in WHERE restriction clauses,
712 * but not in join clauses or in the SELECT target list). In that case,
713 * gin up a Var node the hard way.
716 find_indexkey_var(Query *root, RelOptInfo *rel, AttrNumber varattno)
724 foreach(temp, FastListValue(&rel->reltargetlist))
726 Var *var = (Var *) lfirst(temp);
729 var->varattno == varattno)
734 reloid = getrelid(relid, root->rtable);
735 get_atttypetypmod(reloid, varattno, &vartypeid, &type_mod);
737 return makeVar(relid, varattno, vartypeid, type_mod, 0);
741 * build_subquery_pathkeys
742 * Build a pathkeys list that describes the ordering of a subquery's
743 * result (in the terms of the outer query). The subquery must already
744 * have been planned, so that its query_pathkeys field has been set.
746 * It is not necessary for caller to do truncate_useless_pathkeys(),
747 * because we select keys in a way that takes usefulness of the keys into
751 build_subquery_pathkeys(Query *root, RelOptInfo *rel, Query *subquery)
755 int outer_query_keys = list_length(root->query_pathkeys);
756 List *sub_tlist = rel->subplan->targetlist;
759 foreach(i, subquery->query_pathkeys)
761 List *sub_pathkey = (List *) lfirst(i);
763 PathKeyItem *best_item = NULL;
768 * The sub_pathkey could contain multiple elements (representing
769 * knowledge that multiple items are effectively equal). Each
770 * element might match none, one, or more of the output columns
771 * that are visible to the outer query. This means we may have
772 * multiple possible representations of the sub_pathkey in the
773 * context of the outer query. Ideally we would generate them all
774 * and put them all into a pathkey list of the outer query,
775 * thereby propagating equality knowledge up to the outer query.
776 * Right now we cannot do so, because the outer query's canonical
777 * pathkey sets are already frozen when this is called. Instead
778 * we prefer the one that has the highest "score" (number of
779 * canonical pathkey peers, plus one if it matches the outer
780 * query_pathkeys). This is the most likely to be useful in the
783 foreach(j, sub_pathkey)
785 PathKeyItem *sub_item = (PathKeyItem *) lfirst(j);
786 Node *sub_key = sub_item->key;
789 foreach(k, sub_tlist)
791 TargetEntry *tle = (TargetEntry *) lfirst(k);
793 if (!tle->resdom->resjunk &&
794 equal(tle->expr, sub_key))
796 /* Found a representation for this sub_key */
798 PathKeyItem *outer_item;
801 outer_var = makeVar(rel->relid,
803 tle->resdom->restype,
804 tle->resdom->restypmod,
806 outer_item = makePathKeyItem((Node *) outer_var,
809 /* score = # of mergejoin peers */
810 score = count_canonical_peers(root, outer_item);
811 /* +1 if it matches the proper query_pathkeys item */
812 if (retvallen < outer_query_keys &&
813 list_member(list_nth(root->query_pathkeys, retvallen), outer_item))
815 if (score > best_score)
817 best_item = outer_item;
825 * If we couldn't find a representation of this sub_pathkey, we're
826 * done (we can't use the ones to its right, either).
831 /* Canonicalize the chosen item (we did not before) */
832 cpathkey = make_canonical_pathkey(root, best_item);
835 * Eliminate redundant ordering info; could happen if outer query
836 * equijoins subquery keys...
838 if (!list_member_ptr(retval, cpathkey))
840 retval = lappend(retval, cpathkey);
849 * build_join_pathkeys
850 * Build the path keys for a join relation constructed by mergejoin or
851 * nestloop join. These keys should include all the path key vars of the
852 * outer path (since the join will retain the ordering of the outer path)
853 * plus any vars of the inner path that are equijoined to the outer vars.
855 * Per the discussion in backend/optimizer/README, equijoined inner vars
856 * can be considered path keys of the result, just the same as the outer
857 * vars they were joined with; furthermore, it doesn't matter what kind
858 * of join algorithm is actually used.
860 * 'joinrel' is the join relation that paths are being formed for
861 * 'outer_pathkeys' is the list of the current outer path's path keys
863 * Returns the list of new path keys.
866 build_join_pathkeys(Query *root,
868 List *outer_pathkeys)
871 * This used to be quite a complex bit of code, but now that all
872 * pathkey sublists start out life canonicalized, we don't have to do
873 * a darn thing here! The inner-rel vars we used to need to add are
874 * *already* part of the outer pathkey!
876 * We do, however, need to truncate the pathkeys list, since it may
877 * contain pathkeys that were useful for forming this joinrel but are
878 * uninteresting to higher levels.
880 return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
883 /****************************************************************************
884 * PATHKEYS AND SORT CLAUSES
885 ****************************************************************************/
888 * make_pathkeys_for_sortclauses
889 * Generate a pathkeys list that represents the sort order specified
890 * by a list of SortClauses (GroupClauses will work too!)
892 * NB: the result is NOT in canonical form, but must be passed through
893 * canonicalize_pathkeys() before it can be used for comparisons or
894 * labeling relation sort orders. (We do things this way because
895 * grouping_planner needs to be able to construct requested pathkeys
896 * before the pathkey equivalence sets have been created for the query.)
898 * 'sortclauses' is a list of SortClause or GroupClause nodes
899 * 'tlist' is the targetlist to find the referenced tlist entries in
902 make_pathkeys_for_sortclauses(List *sortclauses,
905 List *pathkeys = NIL;
908 foreach(l, sortclauses)
910 SortClause *sortcl = (SortClause *) lfirst(l);
912 PathKeyItem *pathkey;
914 sortkey = get_sortgroupclause_expr(sortcl, tlist);
915 pathkey = makePathKeyItem(sortkey, sortcl->sortop, true);
918 * The pathkey becomes a one-element sublist, for now;
919 * canonicalize_pathkeys() might replace it with a longer sublist
922 pathkeys = lappend(pathkeys, list_make1(pathkey));
927 /****************************************************************************
928 * PATHKEYS AND MERGECLAUSES
929 ****************************************************************************/
932 * cache_mergeclause_pathkeys
933 * Make the cached pathkeys valid in a mergeclause restrictinfo.
935 * RestrictInfo contains fields in which we may cache the result
936 * of looking up the canonical pathkeys for the left and right sides
937 * of the mergeclause. (Note that in normal cases they will be the
938 * same, but not if the mergeclause appears above an OUTER JOIN.)
939 * This is a worthwhile savings because these routines will be invoked
940 * many times when dealing with a many-relation query.
942 * We have to be careful that the cached values are palloc'd in the same
943 * context the RestrictInfo node itself is in. This is not currently a
944 * problem for normal planning, but it is an issue for GEQO planning.
947 cache_mergeclause_pathkeys(Query *root, RestrictInfo *restrictinfo)
951 MemoryContext oldcontext;
953 Assert(restrictinfo->mergejoinoperator != InvalidOid);
955 if (restrictinfo->left_pathkey == NIL)
957 oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(restrictinfo));
958 key = get_leftop(restrictinfo->clause);
959 item = makePathKeyItem(key, restrictinfo->left_sortop, false);
960 restrictinfo->left_pathkey = make_canonical_pathkey(root, item);
961 MemoryContextSwitchTo(oldcontext);
963 if (restrictinfo->right_pathkey == NIL)
965 oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(restrictinfo));
966 key = get_rightop(restrictinfo->clause);
967 item = makePathKeyItem(key, restrictinfo->right_sortop, false);
968 restrictinfo->right_pathkey = make_canonical_pathkey(root, item);
969 MemoryContextSwitchTo(oldcontext);
974 * find_mergeclauses_for_pathkeys
975 * This routine attempts to find a set of mergeclauses that can be
976 * used with a specified ordering for one of the input relations.
977 * If successful, it returns a list of mergeclauses.
979 * 'pathkeys' is a pathkeys list showing the ordering of an input path.
980 * It doesn't matter whether it is for the inner or outer path.
981 * 'restrictinfos' is a list of mergejoinable restriction clauses for the
982 * join relation being formed.
984 * The result is NIL if no merge can be done, else a maximal list of
985 * usable mergeclauses (represented as a list of their restrictinfo nodes).
987 * XXX Ideally we ought to be considering context, ie what path orderings
988 * are available on the other side of the join, rather than just making
989 * an arbitrary choice among the mergeclauses that will work for this side
993 find_mergeclauses_for_pathkeys(Query *root,
997 List *mergeclauses = NIL;
1000 /* make sure we have pathkeys cached in the clauses */
1001 foreach(i, restrictinfos)
1003 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
1005 cache_mergeclause_pathkeys(root, restrictinfo);
1008 foreach(i, pathkeys)
1010 List *pathkey = (List *) lfirst(i);
1011 List *matched_restrictinfos = NIL;
1015 * We can match a pathkey against either left or right side of any
1016 * mergejoin clause. (We examine both sides since we aren't told
1017 * if the given pathkeys are for inner or outer input path; no
1018 * confusion is possible.) Furthermore, if there are multiple
1019 * matching clauses, take them all. In plain inner-join scenarios
1020 * we expect only one match, because redundant-mergeclause
1021 * elimination will have removed any redundant mergeclauses from
1022 * the input list. However, in outer-join scenarios there might be
1023 * multiple matches. An example is
1025 * select * from a full join b on a.v1 = b.v1 and a.v2 = b.v2 and
1028 * Given the pathkeys ((a.v1), (a.v2)) it is okay to return all three
1029 * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and
1030 * indeed we *must* do so or we will be unable to form a valid
1033 foreach(j, restrictinfos)
1035 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
1038 * We can compare canonical pathkey sublists by simple pointer
1039 * equality; see compare_pathkeys.
1041 if ((pathkey == restrictinfo->left_pathkey ||
1042 pathkey == restrictinfo->right_pathkey) &&
1043 !list_member_ptr(mergeclauses, restrictinfo))
1045 matched_restrictinfos = lappend(matched_restrictinfos,
1051 * If we didn't find a mergeclause, we're done --- any additional
1052 * sort-key positions in the pathkeys are useless. (But we can
1053 * still mergejoin if we found at least one mergeclause.)
1055 if (matched_restrictinfos == NIL)
1059 * If we did find usable mergeclause(s) for this sort-key
1060 * position, add them to result list.
1062 mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1065 return mergeclauses;
1069 * make_pathkeys_for_mergeclauses
1070 * Builds a pathkey list representing the explicit sort order that
1071 * must be applied to a path in order to make it usable for the
1072 * given mergeclauses.
1074 * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
1075 * that will be used in a merge join.
1076 * 'rel' is the relation the pathkeys will apply to (ie, either the inner
1077 * or outer side of the proposed join rel).
1079 * Returns a pathkeys list that can be applied to the indicated relation.
1081 * Note that it is not this routine's job to decide whether sorting is
1082 * actually needed for a particular input path. Assume a sort is necessary;
1083 * just make the keys, eh?
1086 make_pathkeys_for_mergeclauses(Query *root,
1090 List *pathkeys = NIL;
1093 foreach(l, mergeclauses)
1095 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1098 cache_mergeclause_pathkeys(root, restrictinfo);
1100 if (bms_is_subset(restrictinfo->left_relids, rel->relids))
1102 /* Rel is left side of mergeclause */
1103 pathkey = restrictinfo->left_pathkey;
1105 else if (bms_is_subset(restrictinfo->right_relids, rel->relids))
1107 /* Rel is right side of mergeclause */
1108 pathkey = restrictinfo->right_pathkey;
1112 elog(ERROR, "could not identify which side of mergeclause to use");
1113 pathkey = NIL; /* keep compiler quiet */
1117 * When we are given multiple merge clauses, it's possible that
1118 * some clauses refer to the same vars as earlier clauses. There's
1119 * no reason for us to specify sort keys like (A,B,A) when (A,B)
1120 * will do --- and adding redundant sort keys makes add_path think
1121 * that this sort order is different from ones that are really the
1122 * same, so don't do it. Since we now have a canonicalized
1123 * pathkey, a simple ptrMember test is sufficient to detect
1126 if (!list_member_ptr(pathkeys, pathkey))
1127 pathkeys = lappend(pathkeys, pathkey);
1133 /****************************************************************************
1134 * PATHKEY USEFULNESS CHECKS
1136 * We only want to remember as many of the pathkeys of a path as have some
1137 * potential use, either for subsequent mergejoins or for meeting the query's
1138 * requested output ordering. This ensures that add_path() won't consider
1139 * a path to have a usefully different ordering unless it really is useful.
1140 * These routines check for usefulness of given pathkeys.
1141 ****************************************************************************/
1144 * pathkeys_useful_for_merging
1145 * Count the number of pathkeys that may be useful for mergejoins
1146 * above the given relation (by looking at its joininfo lists).
1148 * We consider a pathkey potentially useful if it corresponds to the merge
1149 * ordering of either side of any joinclause for the rel. This might be
1150 * overoptimistic, since joinclauses that appear in different join lists
1151 * might never be usable at the same time, but trying to be exact is likely
1152 * to be more trouble than it's worth.
1155 pathkeys_useful_for_merging(Query *root, RelOptInfo *rel, List *pathkeys)
1160 foreach(i, pathkeys)
1162 List *pathkey = (List *) lfirst(i);
1163 bool matched = false;
1166 foreach(j, rel->joininfo)
1168 JoinInfo *joininfo = (JoinInfo *) lfirst(j);
1171 foreach(k, joininfo->jinfo_restrictinfo)
1173 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(k);
1175 if (restrictinfo->mergejoinoperator == InvalidOid)
1177 cache_mergeclause_pathkeys(root, restrictinfo);
1180 * We can compare canonical pathkey sublists by simple
1181 * pointer equality; see compare_pathkeys.
1183 if (pathkey == restrictinfo->left_pathkey ||
1184 pathkey == restrictinfo->right_pathkey)
1196 * If we didn't find a mergeclause, we're done --- any additional
1197 * sort-key positions in the pathkeys are useless. (But we can
1198 * still mergejoin if we found at least one mergeclause.)
1210 * pathkeys_useful_for_ordering
1211 * Count the number of pathkeys that are useful for meeting the
1212 * query's requested output ordering.
1214 * Unlike merge pathkeys, this is an all-or-nothing affair: it does us
1215 * no good to order by just the first key(s) of the requested ordering.
1216 * So the result is always either 0 or list_length(root->query_pathkeys).
1219 pathkeys_useful_for_ordering(Query *root, List *pathkeys)
1221 if (root->query_pathkeys == NIL)
1222 return 0; /* no special ordering requested */
1224 if (pathkeys == NIL)
1225 return 0; /* unordered path */
1227 if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
1229 /* It's useful ... or at least the first N keys are */
1230 return list_length(root->query_pathkeys);
1233 return 0; /* path ordering not useful */
1237 * truncate_useless_pathkeys
1238 * Shorten the given pathkey list to just the useful pathkeys.
1241 truncate_useless_pathkeys(Query *root,
1248 nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
1249 nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
1250 if (nuseful2 > nuseful)
1254 * Note: not safe to modify input list destructively, but we can avoid
1255 * copying the list if we're not actually going to change it
1257 if (nuseful == list_length(pathkeys))
1260 return list_truncate(list_copy(pathkeys), nuseful);