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-2005, 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.71 2005/07/28 22:27:00 tgl 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 void generate_outer_join_implications(PlannerInfo *root,
38 static void sub_generate_join_implications(PlannerInfo *root,
39 List *equi_key_set, Relids *relids,
40 Node *item1, Oid sortop1,
42 static void process_implied_const_eq(PlannerInfo *root,
43 List *equi_key_set, Relids *relids,
44 Node *item1, Oid sortop1,
47 static List *make_canonical_pathkey(PlannerInfo *root, PathKeyItem *item);
48 static Var *find_indexkey_var(PlannerInfo *root, RelOptInfo *rel,
54 * create a PathKeyItem node
57 makePathKeyItem(Node *key, Oid sortop, bool checkType)
59 PathKeyItem *item = makeNode(PathKeyItem);
62 * Some callers pass expressions that are not necessarily of the same
63 * type as the sort operator expects as input (for example when
64 * dealing with an index that uses binary-compatible operators). We
65 * must relabel these with the correct type so that the key
66 * expressions will be seen as equal() to expressions that have been
74 op_input_types(sortop, &lefttype, &righttype);
75 if (exprType(key) != lefttype)
76 key = (Node *) makeRelabelType((Expr *) key,
82 item->sortop = sortop;
88 * The given clause has a mergejoinable operator, so its two sides
89 * can be considered equal after restriction clause application; in
90 * particular, any pathkey mentioning one side (with the correct sortop)
91 * can be expanded to include the other as well. Record the exprs and
92 * associated sortops in the query's equi_key_list for future use.
94 * The query's equi_key_list field points to a list of sublists of PathKeyItem
95 * nodes, where each sublist is a set of two or more exprs+sortops that have
96 * been identified as logically equivalent (and, therefore, we may consider
97 * any two in a set to be equal). As described above, we will subsequently
98 * use direct pointers to one of these sublists to represent any pathkey
99 * that involves an equijoined variable.
102 add_equijoined_keys(PlannerInfo *root, RestrictInfo *restrictinfo)
104 Expr *clause = restrictinfo->clause;
105 PathKeyItem *item1 = makePathKeyItem(get_leftop(clause),
106 restrictinfo->left_sortop,
108 PathKeyItem *item2 = makePathKeyItem(get_rightop(clause),
109 restrictinfo->right_sortop,
112 ListCell *cursetlink;
114 /* We might see a clause X=X; don't make a single-element list from it */
115 if (equal(item1, item2))
119 * Our plan is to make a two-element set, then sweep through the
120 * existing equijoin sets looking for matches to item1 or item2. When
121 * we find one, we remove that set from equi_key_list and union it
122 * into our new set. When done, we add the new set to the front of
125 * It may well be that the two items we're given are already known to be
126 * equijoin-equivalent, in which case we don't need to change our data
127 * structure. If we find both of them in the same equivalence set to
128 * start with, we can quit immediately.
130 * This is a standard UNION-FIND problem, for which there exist better
131 * data structures than simple lists. If this code ever proves to be
132 * a bottleneck then it could be sped up --- but for now, simple is
137 /* cannot use foreach here because of possible lremove */
138 cursetlink = list_head(root->equi_key_list);
141 List *curset = (List *) lfirst(cursetlink);
142 bool item1here = list_member(curset, item1);
143 bool item2here = list_member(curset, item2);
145 /* must advance cursetlink before lremove possibly pfree's it */
146 cursetlink = lnext(cursetlink);
148 if (item1here || item2here)
151 * If find both in same equivalence set, no need to do any
154 if (item1here && item2here)
156 /* Better not have seen only one in an earlier set... */
157 Assert(newset == NIL);
161 /* Build the new set only when we know we must */
163 newset = list_make2(item1, item2);
165 /* Found a set to merge into our new set */
166 newset = list_concat_unique(newset, curset);
169 * Remove old set from equi_key_list.
171 root->equi_key_list = list_delete_ptr(root->equi_key_list, curset);
172 list_free(curset); /* might as well recycle old cons cells */
176 /* Build the new set only when we know we must */
178 newset = list_make2(item1, item2);
180 root->equi_key_list = lcons(newset, root->equi_key_list);
184 * generate_implied_equalities
185 * Scan the completed equi_key_list for the query, and generate explicit
186 * qualifications (WHERE clauses) for all the pairwise equalities not
187 * already mentioned in the quals; or remove qualifications found to be
190 * Adding deduced equalities is useful because the additional clauses help
191 * the selectivity-estimation code and may allow better joins to be chosen;
192 * and in fact it's *necessary* to ensure that sort keys we think are
193 * equivalent really are (see src/backend/optimizer/README for more info).
195 * If an equi_key_list set includes any constants then we adopt a different
196 * strategy: we record all the "var = const" deductions we can make, and
197 * actively remove all the "var = var" clauses that are implied by the set
198 * (including the clauses that originally gave rise to the set!). The reason
199 * is that given input like "a = b AND b = 42", once we have deduced "a = 42"
200 * there is no longer any need to apply the clause "a = b"; not only is
201 * it a waste of time to check it, but we will misestimate selectivity if the
202 * clause is left in. So we must remove it. For this purpose, any pathkey
203 * item that mentions no Vars of the current level can be taken as a constant.
204 * (The only case where this would be risky is if the item contains volatile
205 * functions; but we will never consider such an expression to be a pathkey
206 * at all, because check_mergejoinable() will reject it.)
208 * Also, when we have constants in an equi_key_list we can try to propagate
209 * the constants into outer joins; see generate_outer_join_implications
212 * This routine just walks the equi_key_list to find all pairwise equalities.
213 * We call process_implied_equality (in plan/initsplan.c) to adjust the
214 * restrictinfo datastructures for each pair.
217 generate_implied_equalities(PlannerInfo *root)
219 ListCell *cursetlink;
221 foreach(cursetlink, root->equi_key_list)
223 List *curset = (List *) lfirst(cursetlink);
224 int nitems = list_length(curset);
231 * A set containing only two items cannot imply any equalities
232 * beyond the one that created the set, so we can skip it ---
233 * unless outer joins appear in the query.
235 if (nitems < 3 && !root->hasOuterJoins)
239 * Collect info about relids mentioned in each item. For this
240 * routine we only really care whether there are any at all in
241 * each item, but process_implied_equality() needs the exact sets,
242 * so we may as well pull them here.
244 relids = (Relids *) palloc(nitems * sizeof(Relids));
247 foreach(ptr1, curset)
249 PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
251 relids[i1] = pull_varnos(item1->key);
252 if (bms_is_empty(relids[i1]))
258 * Match each item in the set with all that appear after it (it's
259 * sufficient to generate A=B, need not process B=A too).
261 * A set containing only two items cannot imply any equalities
262 * beyond the one that created the set, so we can skip this
263 * processing in that case.
268 foreach(ptr1, curset)
270 PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
271 bool i1_is_variable = !bms_is_empty(relids[i1]);
275 for_each_cell(ptr2, lnext(ptr1))
277 PathKeyItem *item2 = (PathKeyItem *) lfirst(ptr2);
278 bool i2_is_variable = !bms_is_empty(relids[i2]);
281 * If it's "const = const" then just ignore it altogether.
282 * There is no place in the restrictinfo structure to
283 * store it. (If the two consts are in fact unequal, then
284 * propagating the comparison to Vars will cause us to
285 * produce zero rows out, as expected.)
287 if (i1_is_variable || i2_is_variable)
290 * Tell process_implied_equality to delete the clause,
291 * not add it, if it's "var = var" and we have
292 * constants present in the list.
294 bool delete_it = (have_consts &&
298 process_implied_equality(root,
299 item1->key, item2->key,
300 item1->sortop, item2->sortop,
301 relids[i1], relids[i2],
311 * If we have constant(s) and outer joins, try to propagate the
312 * constants through outer-join quals.
314 if (have_consts && root->hasOuterJoins)
315 generate_outer_join_implications(root, curset, relids);
320 * generate_outer_join_implications
321 * Generate clauses that can be deduced in outer-join situations.
323 * When we have mergejoinable clauses A = B that are outer-join clauses,
324 * we can't blindly combine them with other clauses A = C to deduce B = C,
325 * since in fact the "equality" A = B won't necessarily hold above the
326 * outer join (one of the variables might be NULL instead). Nonetheless
327 * there are cases where we can add qual clauses using transitivity.
329 * One case that we look for here is an outer-join clause OUTERVAR = INNERVAR
330 * combined with a pushed-down (valid everywhere) clause OUTERVAR = CONSTANT.
331 * It is safe and useful to push a clause INNERVAR = CONSTANT into the
332 * evaluation of the inner (nullable) relation, because any inner rows not
333 * meeting this condition will not contribute to the outer-join result anyway.
334 * (Any outer rows they could join to will be eliminated by the pushed-down
337 * Note that the above rule does not work for full outer joins, nor for
338 * pushed-down restrictions on an inner-side variable; nor is it very
339 * interesting to consider cases where the pushed-down clause involves
340 * relations entirely outside the outer join, since such clauses couldn't
341 * be pushed into the inner side's scan anyway. So the restriction to
342 * outervar = pseudoconstant is not really giving up anything.
344 * For full-join cases, we can only do something useful if it's a FULL JOIN
345 * USING and a merged column has a restriction MERGEDVAR = CONSTANT. By
346 * the time it gets here, the restriction will look like
347 * COALESCE(LEFTVAR, RIGHTVAR) = CONSTANT
348 * and we will have a join clause LEFTVAR = RIGHTVAR that we can match the
349 * COALESCE expression to. In this situation we can push LEFTVAR = CONSTANT
350 * and RIGHTVAR = CONSTANT into the input relations, since any rows not
351 * meeting these conditions cannot contribute to the join result.
353 * Again, there isn't any traction to be gained by trying to deal with
354 * clauses comparing a mergedvar to a non-pseudoconstant. So we can make
355 * use of the equi_key_lists to quickly find the interesting pushed-down
356 * clauses. The interesting outer-join clauses were accumulated for us by
357 * distribute_qual_to_rels.
359 * equi_key_set: a list of PathKeyItems that are known globally equivalent,
360 * at least one of which is a pseudoconstant.
361 * relids: an array of Relids sets showing the relation membership of each
362 * PathKeyItem in equi_key_set.
365 generate_outer_join_implications(PlannerInfo *root,
372 /* Process each non-constant element of equi_key_set */
373 foreach(l, equi_key_set)
375 PathKeyItem *item1 = (PathKeyItem *) lfirst(l);
377 if (!bms_is_empty(relids[i]))
379 sub_generate_join_implications(root, equi_key_set, relids,
389 * sub_generate_join_implications
390 * Propagate a constant equality through outer join clauses.
392 * The item described by item1/sortop1/item1_relids has been determined
393 * to be equal to the constant(s) listed in equi_key_set. Recursively
394 * trace out the implications of this.
396 * equi_key_set and relids are as for generate_outer_join_implications.
399 sub_generate_join_implications(PlannerInfo *root,
400 List *equi_key_set, Relids *relids,
401 Node *item1, Oid sortop1, Relids item1_relids)
407 * Examine each mergejoinable outer-join clause with OUTERVAR on left,
408 * looking for an OUTERVAR identical to item1
410 foreach(l, root->left_join_clauses)
412 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
413 Node *leftop = get_leftop(rinfo->clause);
415 if (equal(leftop, item1) && rinfo->left_sortop == sortop1)
418 * Match, so find constant member(s) of set and generate
419 * implied INNERVAR = CONSTANT
421 Node *rightop = get_rightop(rinfo->clause);
423 process_implied_const_eq(root, equi_key_set, relids,
429 * We can remove explicit tests of this outer-join qual, too,
430 * since we now have tests forcing each of its sides
433 process_implied_equality(root,
435 rinfo->left_sortop, rinfo->right_sortop,
436 rinfo->left_relids, rinfo->right_relids,
439 * And recurse to see if we can deduce anything from
440 * INNERVAR = CONSTANT
442 sub_generate_join_implications(root, equi_key_set, relids,
445 rinfo->right_relids);
449 /* The same, looking at clauses with OUTERVAR on right */
450 foreach(l, root->right_join_clauses)
452 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
453 Node *rightop = get_rightop(rinfo->clause);
455 if (equal(rightop, item1) && rinfo->right_sortop == sortop1)
458 * Match, so find constant member(s) of set and generate
459 * implied INNERVAR = CONSTANT
461 Node *leftop = get_leftop(rinfo->clause);
463 process_implied_const_eq(root, equi_key_set, relids,
469 * We can remove explicit tests of this outer-join qual, too,
470 * since we now have tests forcing each of its sides
473 process_implied_equality(root,
475 rinfo->left_sortop, rinfo->right_sortop,
476 rinfo->left_relids, rinfo->right_relids,
479 * And recurse to see if we can deduce anything from
480 * INNERVAR = CONSTANT
482 sub_generate_join_implications(root, equi_key_set, relids,
490 * Only COALESCE(x,y) items can possibly match full joins
492 if (IsA(item1, CoalesceExpr))
494 CoalesceExpr *cexpr = (CoalesceExpr *) item1;
498 if (list_length(cexpr->args) != 2)
500 cfirst = (Node *) linitial(cexpr->args);
501 csecond = (Node *) lsecond(cexpr->args);
504 * Examine each mergejoinable full-join clause, looking for a
505 * clause of the form "x = y" matching the COALESCE(x,y) expression
507 foreach(l, root->full_join_clauses)
509 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
510 Node *leftop = get_leftop(rinfo->clause);
511 Node *rightop = get_rightop(rinfo->clause);
514 * We can assume the COALESCE() inputs are in the same order
515 * as the join clause, since both were automatically generated
516 * in the cases we care about.
518 * XXX currently this may fail to match in cross-type cases
519 * because the COALESCE will contain typecast operations while
520 * the join clause may not (if there is a cross-type mergejoin
521 * operator available for the two column types).
522 * Is it OK to strip implicit coercions from the COALESCE
523 * arguments? What of the sortops in such cases?
525 if (equal(leftop, cfirst) &&
526 equal(rightop, csecond) &&
527 rinfo->left_sortop == sortop1 &&
528 rinfo->right_sortop == sortop1)
531 * Match, so find constant member(s) of set and generate
532 * implied LEFTVAR = CONSTANT
534 process_implied_const_eq(root, equi_key_set, relids,
539 /* ... and RIGHTVAR = CONSTANT */
540 process_implied_const_eq(root, equi_key_set, relids,
545 /* ... and remove COALESCE() = CONSTANT */
546 process_implied_const_eq(root, equi_key_set, relids,
552 * We can remove explicit tests of this outer-join qual, too,
553 * since we now have tests forcing each of its sides
556 process_implied_equality(root,
564 * And recurse to see if we can deduce anything from
567 sub_generate_join_implications(root, equi_key_set, relids,
571 /* ... and RIGHTVAR = CONSTANT */
572 sub_generate_join_implications(root, equi_key_set, relids,
575 rinfo->right_relids);
583 * process_implied_const_eq
584 * Apply process_implied_equality with the given item and each
585 * pseudoconstant member of equi_key_set.
587 * equi_key_set and relids are as for generate_outer_join_implications,
588 * the other parameters as for process_implied_equality.
591 process_implied_const_eq(PlannerInfo *root, List *equi_key_set, Relids *relids,
592 Node *item1, Oid sortop1, Relids item1_relids,
599 foreach(l, equi_key_set)
601 PathKeyItem *item2 = (PathKeyItem *) lfirst(l);
603 if (bms_is_empty(relids[i]))
605 process_implied_equality(root,
607 sortop1, item2->sortop,
614 /* Caller screwed up if no constants in list */
620 * Detect whether two expressions are known equal due to equijoin clauses.
622 * Note: does not bother to check for "equal(item1, item2)"; caller must
623 * check that case if it's possible to pass identical items.
626 exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
628 ListCell *cursetlink;
630 foreach(cursetlink, root->equi_key_list)
632 List *curset = (List *) lfirst(cursetlink);
633 bool item1member = false;
634 bool item2member = false;
639 PathKeyItem *pitem = (PathKeyItem *) lfirst(ptr);
641 if (equal(item1, pitem->key))
643 else if (equal(item2, pitem->key))
645 /* Exit as soon as equality is proven */
646 if (item1member && item2member)
655 * make_canonical_pathkey
656 * Given a PathKeyItem, find the equi_key_list subset it is a member of,
657 * if any. If so, return a pointer to that sublist, which is the
658 * canonical representation (for this query) of that PathKeyItem's
659 * equivalence set. If it is not found, add a singleton "equivalence set"
660 * to the equi_key_list and return that --- see compare_pathkeys.
662 * Note that this function must not be used until after we have completed
663 * scanning the WHERE clause for equijoin operators.
666 make_canonical_pathkey(PlannerInfo *root, PathKeyItem *item)
669 ListCell *cursetlink;
671 foreach(cursetlink, root->equi_key_list)
673 List *curset = (List *) lfirst(cursetlink);
675 if (list_member(curset, item))
678 newset = list_make1(item);
679 root->equi_key_list = lcons(newset, root->equi_key_list);
684 * canonicalize_pathkeys
685 * Convert a not-necessarily-canonical pathkeys list to canonical form.
687 * Note that this function must not be used until after we have completed
688 * scanning the WHERE clause for equijoin operators.
691 canonicalize_pathkeys(PlannerInfo *root, List *pathkeys)
693 List *new_pathkeys = NIL;
698 List *pathkey = (List *) lfirst(l);
703 * It's sufficient to look at the first entry in the sublist; if
704 * there are more entries, they're already part of an equivalence
707 Assert(pathkey != NIL);
708 item = (PathKeyItem *) linitial(pathkey);
709 cpathkey = make_canonical_pathkey(root, item);
712 * Eliminate redundant ordering requests --- ORDER BY A,A is the
713 * same as ORDER BY A. We want to check this only after we have
714 * canonicalized the keys, so that equivalent-key knowledge is
715 * used when deciding if an item is redundant.
717 new_pathkeys = list_append_unique_ptr(new_pathkeys, cpathkey);
724 * count_canonical_peers
725 * Given a PathKeyItem, find the equi_key_list subset it is a member of,
726 * if any. If so, return the number of other members of the set.
727 * If not, return 0 (without actually adding it to our equi_key_list).
729 * This is a hack to support the rather bogus heuristics in
730 * convert_subquery_pathkeys.
733 count_canonical_peers(PlannerInfo *root, PathKeyItem *item)
735 ListCell *cursetlink;
737 foreach(cursetlink, root->equi_key_list)
739 List *curset = (List *) lfirst(cursetlink);
741 if (list_member(curset, item))
742 return list_length(curset) - 1;
747 /****************************************************************************
748 * PATHKEY COMPARISONS
749 ****************************************************************************/
753 * Compare two pathkeys to see if they are equivalent, and if not whether
754 * one is "better" than the other.
756 * This function may only be applied to canonicalized pathkey lists.
757 * In the canonical representation, sublists can be checked for equality
758 * by simple pointer comparison.
761 compare_pathkeys(List *keys1, List *keys2)
766 forboth(key1, keys1, key2, keys2)
768 List *subkey1 = (List *) lfirst(key1);
769 List *subkey2 = (List *) lfirst(key2);
772 * XXX would like to check that we've been given canonicalized
773 * input, but PlannerInfo not accessible here...
776 Assert(list_member_ptr(root->equi_key_list, subkey1));
777 Assert(list_member_ptr(root->equi_key_list, subkey2));
781 * We will never have two subkeys where one is a subset of the
782 * other, because of the canonicalization process. Either they
783 * are equal or they ain't. Furthermore, we only need pointer
784 * comparison to detect equality.
786 if (subkey1 != subkey2)
787 return PATHKEYS_DIFFERENT; /* no need to keep looking */
791 * If we reached the end of only one list, the other is longer and
792 * therefore not a subset. (We assume the additional sublist(s) of
793 * the other list are not NIL --- no pathkey list should ever have a
796 if (key1 == NULL && key2 == NULL)
797 return PATHKEYS_EQUAL;
799 return PATHKEYS_BETTER1; /* key1 is longer */
800 return PATHKEYS_BETTER2; /* key2 is longer */
804 * compare_noncanonical_pathkeys
805 * Compare two pathkeys to see if they are equivalent, and if not whether
806 * one is "better" than the other. This is used when we must compare
807 * non-canonicalized pathkeys.
809 * A pathkey can be considered better than another if it is a superset:
810 * it contains all the keys of the other plus more. For example, either
811 * ((A) (B)) or ((A B)) is better than ((A)).
813 * Currently, the only user of this routine is grouping_planner(),
814 * and it will only pass single-element sublists (from
815 * make_pathkeys_for_sortclauses). Therefore we don't have to do the
816 * full two-way-subset-inclusion test on each pair of sublists that is
817 * implied by the above statement. Instead we just verify they are
818 * singleton lists and then do an equal(). This could be improved if
822 compare_noncanonical_pathkeys(List *keys1, List *keys2)
827 forboth(key1, keys1, key2, keys2)
829 List *subkey1 = (List *) lfirst(key1);
830 List *subkey2 = (List *) lfirst(key2);
832 Assert(list_length(subkey1) == 1);
833 Assert(list_length(subkey2) == 1);
834 if (!equal(subkey1, subkey2))
835 return PATHKEYS_DIFFERENT; /* no need to keep looking */
839 * If we reached the end of only one list, the other is longer and
840 * therefore not a subset. (We assume the additional sublist(s) of
841 * the other list are not NIL --- no pathkey list should ever have a
844 if (key1 == NULL && key2 == NULL)
845 return PATHKEYS_EQUAL;
847 return PATHKEYS_BETTER1; /* key1 is longer */
848 return PATHKEYS_BETTER2; /* key2 is longer */
852 * pathkeys_contained_in
853 * Common special case of compare_pathkeys: we just want to know
854 * if keys2 are at least as well sorted as keys1.
857 pathkeys_contained_in(List *keys1, List *keys2)
859 switch (compare_pathkeys(keys1, keys2))
862 case PATHKEYS_BETTER2:
871 * noncanonical_pathkeys_contained_in
872 * The same, when we don't have canonical pathkeys.
875 noncanonical_pathkeys_contained_in(List *keys1, List *keys2)
877 switch (compare_noncanonical_pathkeys(keys1, keys2))
880 case PATHKEYS_BETTER2:
889 * get_cheapest_path_for_pathkeys
890 * Find the cheapest path (according to the specified criterion) that
891 * satisfies the given pathkeys. Return NULL if no such path.
893 * 'paths' is a list of possible paths that all generate the same relation
894 * 'pathkeys' represents a required ordering (already canonicalized!)
895 * 'cost_criterion' is STARTUP_COST or TOTAL_COST
898 get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
899 CostSelector cost_criterion)
901 Path *matched_path = NULL;
906 Path *path = (Path *) lfirst(l);
909 * Since cost comparison is a lot cheaper than pathkey comparison,
910 * do that first. (XXX is that still true?)
912 if (matched_path != NULL &&
913 compare_path_costs(matched_path, path, cost_criterion) <= 0)
916 if (pathkeys_contained_in(pathkeys, path->pathkeys))
923 * get_cheapest_fractional_path_for_pathkeys
924 * Find the cheapest path (for retrieving a specified fraction of all
925 * the tuples) that satisfies the given pathkeys.
926 * Return NULL if no such path.
928 * See compare_fractional_path_costs() for the interpretation of the fraction
931 * 'paths' is a list of possible paths that all generate the same relation
932 * 'pathkeys' represents a required ordering (already canonicalized!)
933 * 'fraction' is the fraction of the total tuples expected to be retrieved
936 get_cheapest_fractional_path_for_pathkeys(List *paths,
940 Path *matched_path = NULL;
945 Path *path = (Path *) lfirst(l);
948 * Since cost comparison is a lot cheaper than pathkey comparison,
951 if (matched_path != NULL &&
952 compare_fractional_path_costs(matched_path, path, fraction) <= 0)
955 if (pathkeys_contained_in(pathkeys, path->pathkeys))
961 /****************************************************************************
962 * NEW PATHKEY FORMATION
963 ****************************************************************************/
966 * build_index_pathkeys
967 * Build a pathkeys list that describes the ordering induced by an index
968 * scan using the given index. (Note that an unordered index doesn't
969 * induce any ordering; such an index will have no sortop OIDS in
970 * its "ordering" field, and we will return NIL.)
972 * If 'scandir' is BackwardScanDirection, attempt to build pathkeys
973 * representing a backwards scan of the index. Return NIL if can't do it.
975 * We generate the full pathkeys list whether or not all are useful for the
976 * current query. Caller should do truncate_useless_pathkeys().
979 build_index_pathkeys(PlannerInfo *root,
981 ScanDirection scandir)
984 int *indexkeys = index->indexkeys;
985 Oid *ordering = index->ordering;
986 ListCell *indexprs_item = list_head(index->indexprs);
988 while (*ordering != InvalidOid)
996 if (ScanDirectionIsBackward(scandir))
998 sortop = get_commutator(sortop);
999 if (sortop == InvalidOid)
1000 break; /* oops, no reverse sort operator? */
1003 if (*indexkeys != 0)
1005 /* simple index column */
1006 indexkey = (Node *) find_indexkey_var(root, index->rel,
1011 /* expression --- assume we need not copy it */
1012 if (indexprs_item == NULL)
1013 elog(ERROR, "wrong number of index expressions");
1014 indexkey = (Node *) lfirst(indexprs_item);
1015 indexprs_item = lnext(indexprs_item);
1018 /* OK, make a sublist for this sort key */
1019 item = makePathKeyItem(indexkey, sortop, true);
1020 cpathkey = make_canonical_pathkey(root, item);
1023 * Eliminate redundant ordering info; could happen if query is
1024 * such that index keys are equijoined...
1026 retval = list_append_unique_ptr(retval, cpathkey);
1036 * Find or make a Var node for the specified attribute of the rel.
1038 * We first look for the var in the rel's target list, because that's
1039 * easy and fast. But the var might not be there (this should normally
1040 * only happen for vars that are used in WHERE restriction clauses,
1041 * but not in join clauses or in the SELECT target list). In that case,
1042 * gin up a Var node the hard way.
1045 find_indexkey_var(PlannerInfo *root, RelOptInfo *rel, AttrNumber varattno)
1053 foreach(temp, rel->reltargetlist)
1055 Var *var = (Var *) lfirst(temp);
1057 if (IsA(var, Var) &&
1058 var->varattno == varattno)
1063 reloid = getrelid(relid, root->parse->rtable);
1064 get_atttypetypmod(reloid, varattno, &vartypeid, &type_mod);
1066 return makeVar(relid, varattno, vartypeid, type_mod, 0);
1070 * convert_subquery_pathkeys
1071 * Build a pathkeys list that describes the ordering of a subquery's
1072 * result, in the terms of the outer query. This is essentially a
1073 * task of conversion.
1075 * 'rel': outer query's RelOptInfo for the subquery relation.
1076 * 'subquery_pathkeys': the subquery's output pathkeys, in its terms.
1078 * It is not necessary for caller to do truncate_useless_pathkeys(),
1079 * because we select keys in a way that takes usefulness of the keys into
1083 convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
1084 List *subquery_pathkeys)
1088 int outer_query_keys = list_length(root->query_pathkeys);
1089 List *sub_tlist = rel->subplan->targetlist;
1092 foreach(i, subquery_pathkeys)
1094 List *sub_pathkey = (List *) lfirst(i);
1096 PathKeyItem *best_item = NULL;
1101 * The sub_pathkey could contain multiple elements (representing
1102 * knowledge that multiple items are effectively equal). Each
1103 * element might match none, one, or more of the output columns
1104 * that are visible to the outer query. This means we may have
1105 * multiple possible representations of the sub_pathkey in the
1106 * context of the outer query. Ideally we would generate them all
1107 * and put them all into a pathkey list of the outer query,
1108 * thereby propagating equality knowledge up to the outer query.
1109 * Right now we cannot do so, because the outer query's canonical
1110 * pathkey sets are already frozen when this is called. Instead
1111 * we prefer the one that has the highest "score" (number of
1112 * canonical pathkey peers, plus one if it matches the outer
1113 * query_pathkeys). This is the most likely to be useful in the
1116 foreach(j, sub_pathkey)
1118 PathKeyItem *sub_item = (PathKeyItem *) lfirst(j);
1119 Node *sub_key = sub_item->key;
1122 foreach(k, sub_tlist)
1124 TargetEntry *tle = (TargetEntry *) lfirst(k);
1126 if (!tle->resjunk &&
1127 equal(tle->expr, sub_key))
1129 /* Found a representation for this sub_key */
1131 PathKeyItem *outer_item;
1134 outer_var = makeVar(rel->relid,
1136 exprType((Node *) tle->expr),
1137 exprTypmod((Node *) tle->expr),
1139 outer_item = makePathKeyItem((Node *) outer_var,
1142 /* score = # of mergejoin peers */
1143 score = count_canonical_peers(root, outer_item);
1144 /* +1 if it matches the proper query_pathkeys item */
1145 if (retvallen < outer_query_keys &&
1146 list_member(list_nth(root->query_pathkeys, retvallen), outer_item))
1148 if (score > best_score)
1150 best_item = outer_item;
1158 * If we couldn't find a representation of this sub_pathkey, we're
1159 * done (we can't use the ones to its right, either).
1164 /* Canonicalize the chosen item (we did not before) */
1165 cpathkey = make_canonical_pathkey(root, best_item);
1168 * Eliminate redundant ordering info; could happen if outer query
1169 * equijoins subquery keys...
1171 if (!list_member_ptr(retval, cpathkey))
1173 retval = lappend(retval, cpathkey);
1182 * build_join_pathkeys
1183 * Build the path keys for a join relation constructed by mergejoin or
1184 * nestloop join. These keys should include all the path key vars of the
1185 * outer path (since the join will retain the ordering of the outer path)
1186 * plus any vars of the inner path that are equijoined to the outer vars.
1188 * Per the discussion in backend/optimizer/README, equijoined inner vars
1189 * can be considered path keys of the result, just the same as the outer
1190 * vars they were joined with; furthermore, it doesn't matter what kind
1191 * of join algorithm is actually used.
1193 * EXCEPTION: in a FULL or RIGHT join, we cannot treat the result as
1194 * having the outer path's path keys, because null lefthand rows may be
1195 * inserted at random points. It must be treated as unsorted.
1197 * 'joinrel' is the join relation that paths are being formed for
1198 * 'jointype' is the join type (inner, left, full, etc)
1199 * 'outer_pathkeys' is the list of the current outer path's path keys
1201 * Returns the list of new path keys.
1204 build_join_pathkeys(PlannerInfo *root,
1205 RelOptInfo *joinrel,
1207 List *outer_pathkeys)
1209 if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
1213 * This used to be quite a complex bit of code, but now that all
1214 * pathkey sublists start out life canonicalized, we don't have to do
1215 * a darn thing here! The inner-rel vars we used to need to add are
1216 * *already* part of the outer pathkey!
1218 * We do, however, need to truncate the pathkeys list, since it may
1219 * contain pathkeys that were useful for forming this joinrel but are
1220 * uninteresting to higher levels.
1222 return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1225 /****************************************************************************
1226 * PATHKEYS AND SORT CLAUSES
1227 ****************************************************************************/
1230 * make_pathkeys_for_sortclauses
1231 * Generate a pathkeys list that represents the sort order specified
1232 * by a list of SortClauses (GroupClauses will work too!)
1234 * NB: the result is NOT in canonical form, but must be passed through
1235 * canonicalize_pathkeys() before it can be used for comparisons or
1236 * labeling relation sort orders. (We do things this way because
1237 * grouping_planner needs to be able to construct requested pathkeys
1238 * before the pathkey equivalence sets have been created for the query.)
1240 * 'sortclauses' is a list of SortClause or GroupClause nodes
1241 * 'tlist' is the targetlist to find the referenced tlist entries in
1244 make_pathkeys_for_sortclauses(List *sortclauses,
1247 List *pathkeys = NIL;
1250 foreach(l, sortclauses)
1252 SortClause *sortcl = (SortClause *) lfirst(l);
1254 PathKeyItem *pathkey;
1256 sortkey = get_sortgroupclause_expr(sortcl, tlist);
1257 pathkey = makePathKeyItem(sortkey, sortcl->sortop, true);
1260 * The pathkey becomes a one-element sublist, for now;
1261 * canonicalize_pathkeys() might replace it with a longer sublist
1264 pathkeys = lappend(pathkeys, list_make1(pathkey));
1269 /****************************************************************************
1270 * PATHKEYS AND MERGECLAUSES
1271 ****************************************************************************/
1274 * cache_mergeclause_pathkeys
1275 * Make the cached pathkeys valid in a mergeclause restrictinfo.
1277 * RestrictInfo contains fields in which we may cache the result
1278 * of looking up the canonical pathkeys for the left and right sides
1279 * of the mergeclause. (Note that in normal cases they will be the
1280 * same, but not if the mergeclause appears above an OUTER JOIN.)
1281 * This is a worthwhile savings because these routines will be invoked
1282 * many times when dealing with a many-relation query.
1284 * We have to be careful that the cached values are palloc'd in the same
1285 * context the RestrictInfo node itself is in. This is not currently a
1286 * problem for normal planning, but it is an issue for GEQO planning.
1289 cache_mergeclause_pathkeys(PlannerInfo *root, RestrictInfo *restrictinfo)
1293 MemoryContext oldcontext;
1295 Assert(restrictinfo->mergejoinoperator != InvalidOid);
1297 if (restrictinfo->left_pathkey == NIL)
1299 oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(restrictinfo));
1300 key = get_leftop(restrictinfo->clause);
1301 item = makePathKeyItem(key, restrictinfo->left_sortop, false);
1302 restrictinfo->left_pathkey = make_canonical_pathkey(root, item);
1303 MemoryContextSwitchTo(oldcontext);
1305 if (restrictinfo->right_pathkey == NIL)
1307 oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(restrictinfo));
1308 key = get_rightop(restrictinfo->clause);
1309 item = makePathKeyItem(key, restrictinfo->right_sortop, false);
1310 restrictinfo->right_pathkey = make_canonical_pathkey(root, item);
1311 MemoryContextSwitchTo(oldcontext);
1316 * find_mergeclauses_for_pathkeys
1317 * This routine attempts to find a set of mergeclauses that can be
1318 * used with a specified ordering for one of the input relations.
1319 * If successful, it returns a list of mergeclauses.
1321 * 'pathkeys' is a pathkeys list showing the ordering of an input path.
1322 * It doesn't matter whether it is for the inner or outer path.
1323 * 'restrictinfos' is a list of mergejoinable restriction clauses for the
1324 * join relation being formed.
1326 * The result is NIL if no merge can be done, else a maximal list of
1327 * usable mergeclauses (represented as a list of their restrictinfo nodes).
1329 * XXX Ideally we ought to be considering context, ie what path orderings
1330 * are available on the other side of the join, rather than just making
1331 * an arbitrary choice among the mergeclauses that will work for this side
1335 find_mergeclauses_for_pathkeys(PlannerInfo *root,
1337 List *restrictinfos)
1339 List *mergeclauses = NIL;
1342 /* make sure we have pathkeys cached in the clauses */
1343 foreach(i, restrictinfos)
1345 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
1347 cache_mergeclause_pathkeys(root, restrictinfo);
1350 foreach(i, pathkeys)
1352 List *pathkey = (List *) lfirst(i);
1353 List *matched_restrictinfos = NIL;
1357 * We can match a pathkey against either left or right side of any
1358 * mergejoin clause. (We examine both sides since we aren't told
1359 * if the given pathkeys are for inner or outer input path; no
1360 * confusion is possible.) Furthermore, if there are multiple
1361 * matching clauses, take them all. In plain inner-join scenarios
1362 * we expect only one match, because redundant-mergeclause
1363 * elimination will have removed any redundant mergeclauses from
1364 * the input list. However, in outer-join scenarios there might be
1365 * multiple matches. An example is
1367 * select * from a full join b on a.v1 = b.v1 and a.v2 = b.v2 and
1370 * Given the pathkeys ((a.v1), (a.v2)) it is okay to return all three
1371 * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and
1372 * indeed we *must* do so or we will be unable to form a valid
1375 foreach(j, restrictinfos)
1377 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
1380 * We can compare canonical pathkey sublists by simple pointer
1381 * equality; see compare_pathkeys.
1383 if ((pathkey == restrictinfo->left_pathkey ||
1384 pathkey == restrictinfo->right_pathkey) &&
1385 !list_member_ptr(mergeclauses, restrictinfo))
1387 matched_restrictinfos = lappend(matched_restrictinfos,
1393 * If we didn't find a mergeclause, we're done --- any additional
1394 * sort-key positions in the pathkeys are useless. (But we can
1395 * still mergejoin if we found at least one mergeclause.)
1397 if (matched_restrictinfos == NIL)
1401 * If we did find usable mergeclause(s) for this sort-key
1402 * position, add them to result list.
1404 mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1407 return mergeclauses;
1411 * make_pathkeys_for_mergeclauses
1412 * Builds a pathkey list representing the explicit sort order that
1413 * must be applied to a path in order to make it usable for the
1414 * given mergeclauses.
1416 * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
1417 * that will be used in a merge join.
1418 * 'rel' is the relation the pathkeys will apply to (ie, either the inner
1419 * or outer side of the proposed join rel).
1421 * Returns a pathkeys list that can be applied to the indicated relation.
1423 * Note that it is not this routine's job to decide whether sorting is
1424 * actually needed for a particular input path. Assume a sort is necessary;
1425 * just make the keys, eh?
1428 make_pathkeys_for_mergeclauses(PlannerInfo *root,
1432 List *pathkeys = NIL;
1435 foreach(l, mergeclauses)
1437 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1440 cache_mergeclause_pathkeys(root, restrictinfo);
1442 if (bms_is_subset(restrictinfo->left_relids, rel->relids))
1444 /* Rel is left side of mergeclause */
1445 pathkey = restrictinfo->left_pathkey;
1447 else if (bms_is_subset(restrictinfo->right_relids, rel->relids))
1449 /* Rel is right side of mergeclause */
1450 pathkey = restrictinfo->right_pathkey;
1454 elog(ERROR, "could not identify which side of mergeclause to use");
1455 pathkey = NIL; /* keep compiler quiet */
1459 * When we are given multiple merge clauses, it's possible that
1460 * some clauses refer to the same vars as earlier clauses. There's
1461 * no reason for us to specify sort keys like (A,B,A) when (A,B)
1462 * will do --- and adding redundant sort keys makes add_path think
1463 * that this sort order is different from ones that are really the
1464 * same, so don't do it. Since we now have a canonicalized
1465 * pathkey, a simple ptrMember test is sufficient to detect
1468 pathkeys = list_append_unique_ptr(pathkeys, pathkey);
1474 /****************************************************************************
1475 * PATHKEY USEFULNESS CHECKS
1477 * We only want to remember as many of the pathkeys of a path as have some
1478 * potential use, either for subsequent mergejoins or for meeting the query's
1479 * requested output ordering. This ensures that add_path() won't consider
1480 * a path to have a usefully different ordering unless it really is useful.
1481 * These routines check for usefulness of given pathkeys.
1482 ****************************************************************************/
1485 * pathkeys_useful_for_merging
1486 * Count the number of pathkeys that may be useful for mergejoins
1487 * above the given relation (by looking at its joininfo list).
1489 * We consider a pathkey potentially useful if it corresponds to the merge
1490 * ordering of either side of any joinclause for the rel. This might be
1491 * overoptimistic, since joinclauses that require different other relations
1492 * might never be usable at the same time, but trying to be exact is likely
1493 * to be more trouble than it's worth.
1496 pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
1501 foreach(i, pathkeys)
1503 List *pathkey = (List *) lfirst(i);
1504 bool matched = false;
1507 foreach(j, rel->joininfo)
1509 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
1511 if (restrictinfo->mergejoinoperator == InvalidOid)
1513 cache_mergeclause_pathkeys(root, restrictinfo);
1516 * We can compare canonical pathkey sublists by simple
1517 * pointer equality; see compare_pathkeys.
1519 if (pathkey == restrictinfo->left_pathkey ||
1520 pathkey == restrictinfo->right_pathkey)
1528 * If we didn't find a mergeclause, we're done --- any additional
1529 * sort-key positions in the pathkeys are useless. (But we can
1530 * still mergejoin if we found at least one mergeclause.)
1542 * pathkeys_useful_for_ordering
1543 * Count the number of pathkeys that are useful for meeting the
1544 * query's requested output ordering.
1546 * Unlike merge pathkeys, this is an all-or-nothing affair: it does us
1547 * no good to order by just the first key(s) of the requested ordering.
1548 * So the result is always either 0 or list_length(root->query_pathkeys).
1551 pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
1553 if (root->query_pathkeys == NIL)
1554 return 0; /* no special ordering requested */
1556 if (pathkeys == NIL)
1557 return 0; /* unordered path */
1559 if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
1561 /* It's useful ... or at least the first N keys are */
1562 return list_length(root->query_pathkeys);
1565 return 0; /* path ordering not useful */
1569 * truncate_useless_pathkeys
1570 * Shorten the given pathkey list to just the useful pathkeys.
1573 truncate_useless_pathkeys(PlannerInfo *root,
1580 nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
1581 nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
1582 if (nuseful2 > nuseful)
1586 * Note: not safe to modify input list destructively, but we can avoid
1587 * copying the list if we're not actually going to change it
1589 if (nuseful == list_length(pathkeys))
1592 return list_truncate(list_copy(pathkeys), nuseful);