diff options
Diffstat (limited to 'src/backend/optimizer/path/pathkeys.c')
| -rw-r--r-- | src/backend/optimizer/path/pathkeys.c | 1917 |
1 files changed, 1917 insertions, 0 deletions
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c new file mode 100644 index 0000000..86a35cd --- /dev/null +++ b/src/backend/optimizer/path/pathkeys.c @@ -0,0 +1,1917 @@ +/*------------------------------------------------------------------------- + * + * pathkeys.c + * Utilities for matching and building path keys + * + * See src/backend/optimizer/README for a great deal of information about + * the nature and use of path keys. + * + * + * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/optimizer/path/pathkeys.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "access/stratnum.h" +#include "catalog/pg_opfamily.h" +#include "nodes/makefuncs.h" +#include "nodes/nodeFuncs.h" +#include "nodes/plannodes.h" +#include "optimizer/optimizer.h" +#include "optimizer/pathnode.h" +#include "optimizer/paths.h" +#include "partitioning/partbounds.h" +#include "utils/lsyscache.h" + + +static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); +static bool matches_boolean_partition_clause(RestrictInfo *rinfo, + RelOptInfo *partrel, + int partkeycol); +static Var *find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle); +static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey); + + +/**************************************************************************** + * PATHKEY CONSTRUCTION AND REDUNDANCY TESTING + ****************************************************************************/ + +/* + * make_canonical_pathkey + * Given the parameters for a PathKey, find any pre-existing matching + * pathkey in the query's list of "canonical" pathkeys. Make a new + * entry if there's not one already. + * + * Note that this function must not be used until after we have completed + * merging EquivalenceClasses. + */ +PathKey * +make_canonical_pathkey(PlannerInfo *root, + EquivalenceClass *eclass, Oid opfamily, + int strategy, bool nulls_first) +{ + PathKey *pk; + ListCell *lc; + MemoryContext oldcontext; + + /* Can't make canonical pathkeys if the set of ECs might still change */ + if (!root->ec_merging_done) + elog(ERROR, "too soon to build canonical pathkeys"); + + /* The passed eclass might be non-canonical, so chase up to the top */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + foreach(lc, root->canon_pathkeys) + { + pk = (PathKey *) lfirst(lc); + if (eclass == pk->pk_eclass && + opfamily == pk->pk_opfamily && + strategy == pk->pk_strategy && + nulls_first == pk->pk_nulls_first) + return pk; + } + + /* + * Be sure canonical pathkeys are allocated in the main planning context. + * Not an issue in normal planning, but it is for GEQO. + */ + oldcontext = MemoryContextSwitchTo(root->planner_cxt); + + pk = makeNode(PathKey); + pk->pk_eclass = eclass; + pk->pk_opfamily = opfamily; + pk->pk_strategy = strategy; + pk->pk_nulls_first = nulls_first; + + root->canon_pathkeys = lappend(root->canon_pathkeys, pk); + + MemoryContextSwitchTo(oldcontext); + + return pk; +} + +/* + * pathkey_is_redundant + * Is a pathkey redundant with one already in the given list? + * + * We detect two cases: + * + * 1. If the new pathkey's equivalence class contains a constant, and isn't + * below an outer join, then we can disregard it as a sort key. An example: + * SELECT ... WHERE x = 42 ORDER BY x, y; + * We may as well just sort by y. Note that because of opfamily matching, + * this is semantically correct: we know that the equality constraint is one + * that actually binds the variable to a single value in the terms of any + * ordering operator that might go with the eclass. This rule not only lets + * us simplify (or even skip) explicit sorts, but also allows matching index + * sort orders to a query when there are don't-care index columns. + * + * 2. If the new pathkey's equivalence class is the same as that of any + * existing member of the pathkey list, then it is redundant. Some examples: + * SELECT ... ORDER BY x, x; + * SELECT ... ORDER BY x, x DESC; + * SELECT ... WHERE x = y ORDER BY x, y; + * In all these cases the second sort key cannot distinguish values that are + * considered equal by the first, and so there's no point in using it. + * Note in particular that we need not compare opfamily (all the opfamilies + * of the EC have the same notion of equality) nor sort direction. + * + * Both the given pathkey and the list members must be canonical for this + * to work properly, but that's okay since we no longer ever construct any + * non-canonical pathkeys. (Note: the notion of a pathkey *list* being + * canonical includes the additional requirement of no redundant entries, + * which is exactly what we are checking for here.) + * + * Because the equivclass.c machinery forms only one copy of any EC per query, + * pointer comparison is enough to decide whether canonical ECs are the same. + */ +static bool +pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys) +{ + EquivalenceClass *new_ec = new_pathkey->pk_eclass; + ListCell *lc; + + /* Check for EC containing a constant --- unconditionally redundant */ + if (EC_MUST_BE_REDUNDANT(new_ec)) + return true; + + /* If same EC already used in list, then redundant */ + foreach(lc, pathkeys) + { + PathKey *old_pathkey = (PathKey *) lfirst(lc); + + if (new_ec == old_pathkey->pk_eclass) + return true; + } + + return false; +} + +/* + * make_pathkey_from_sortinfo + * Given an expression and sort-order information, create a PathKey. + * The result is always a "canonical" PathKey, but it might be redundant. + * + * expr is the expression, and nullable_relids is the set of base relids + * that are potentially nullable below it. + * + * If the PathKey is being generated from a SortGroupClause, sortref should be + * the SortGroupClause's SortGroupRef; otherwise zero. + * + * If rel is not NULL, it identifies a specific relation we're considering + * a path for, and indicates that child EC members for that relation can be + * considered. Otherwise child members are ignored. (See the comments for + * get_eclass_for_sort_expr.) + * + * create_it is true if we should create any missing EquivalenceClass + * needed to represent the sort key. If it's false, we return NULL if the + * sort key isn't already present in any EquivalenceClass. + */ +static PathKey * +make_pathkey_from_sortinfo(PlannerInfo *root, + Expr *expr, + Relids nullable_relids, + Oid opfamily, + Oid opcintype, + Oid collation, + bool reverse_sort, + bool nulls_first, + Index sortref, + Relids rel, + bool create_it) +{ + int16 strategy; + Oid equality_op; + List *opfamilies; + EquivalenceClass *eclass; + + strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber; + + /* + * EquivalenceClasses need to contain opfamily lists based on the family + * membership of mergejoinable equality operators, which could belong to + * more than one opfamily. So we have to look up the opfamily's equality + * operator and get its membership. + */ + equality_op = get_opfamily_member(opfamily, + opcintype, + opcintype, + BTEqualStrategyNumber); + if (!OidIsValid(equality_op)) /* shouldn't happen */ + elog(ERROR, "missing operator %d(%u,%u) in opfamily %u", + BTEqualStrategyNumber, opcintype, opcintype, opfamily); + opfamilies = get_mergejoin_opfamilies(equality_op); + if (!opfamilies) /* certainly should find some */ + elog(ERROR, "could not find opfamilies for equality operator %u", + equality_op); + + /* Now find or (optionally) create a matching EquivalenceClass */ + eclass = get_eclass_for_sort_expr(root, expr, nullable_relids, + opfamilies, opcintype, collation, + sortref, rel, create_it); + + /* Fail if no EC and !create_it */ + if (!eclass) + return NULL; + + /* And finally we can find or create a PathKey node */ + return make_canonical_pathkey(root, eclass, opfamily, + strategy, nulls_first); +} + +/* + * make_pathkey_from_sortop + * Like make_pathkey_from_sortinfo, but work from a sort operator. + * + * This should eventually go away, but we need to restructure SortGroupClause + * first. + */ +static PathKey * +make_pathkey_from_sortop(PlannerInfo *root, + Expr *expr, + Relids nullable_relids, + Oid ordering_op, + bool nulls_first, + Index sortref, + bool create_it) +{ + Oid opfamily, + opcintype, + collation; + int16 strategy; + + /* Find the operator in pg_amop --- failure shouldn't happen */ + if (!get_ordering_op_properties(ordering_op, + &opfamily, &opcintype, &strategy)) + elog(ERROR, "operator %u is not a valid ordering operator", + ordering_op); + + /* Because SortGroupClause doesn't carry collation, consult the expr */ + collation = exprCollation((Node *) expr); + + return make_pathkey_from_sortinfo(root, + expr, + nullable_relids, + opfamily, + opcintype, + collation, + (strategy == BTGreaterStrategyNumber), + nulls_first, + sortref, + NULL, + create_it); +} + + +/**************************************************************************** + * PATHKEY COMPARISONS + ****************************************************************************/ + +/* + * compare_pathkeys + * Compare two pathkeys to see if they are equivalent, and if not whether + * one is "better" than the other. + * + * We assume the pathkeys are canonical, and so they can be checked for + * equality by simple pointer comparison. + */ +PathKeysComparison +compare_pathkeys(List *keys1, List *keys2) +{ + ListCell *key1, + *key2; + + /* + * Fall out quickly if we are passed two identical lists. This mostly + * catches the case where both are NIL, but that's common enough to + * warrant the test. + */ + if (keys1 == keys2) + return PATHKEYS_EQUAL; + + forboth(key1, keys1, key2, keys2) + { + PathKey *pathkey1 = (PathKey *) lfirst(key1); + PathKey *pathkey2 = (PathKey *) lfirst(key2); + + if (pathkey1 != pathkey2) + return PATHKEYS_DIFFERENT; /* no need to keep looking */ + } + + /* + * If we reached the end of only one list, the other is longer and + * therefore not a subset. + */ + if (key1 != NULL) + return PATHKEYS_BETTER1; /* key1 is longer */ + if (key2 != NULL) + return PATHKEYS_BETTER2; /* key2 is longer */ + return PATHKEYS_EQUAL; +} + +/* + * pathkeys_contained_in + * Common special case of compare_pathkeys: we just want to know + * if keys2 are at least as well sorted as keys1. + */ +bool +pathkeys_contained_in(List *keys1, List *keys2) +{ + switch (compare_pathkeys(keys1, keys2)) + { + case PATHKEYS_EQUAL: + case PATHKEYS_BETTER2: + return true; + default: + break; + } + return false; +} + +/* + * pathkeys_count_contained_in + * Same as pathkeys_contained_in, but also sets length of longest + * common prefix of keys1 and keys2. + */ +bool +pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common) +{ + int n = 0; + ListCell *key1, + *key2; + + /* + * See if we can avoiding looping through both lists. This optimization + * gains us several percent in planning time in a worst-case test. + */ + if (keys1 == keys2) + { + *n_common = list_length(keys1); + return true; + } + else if (keys1 == NIL) + { + *n_common = 0; + return true; + } + else if (keys2 == NIL) + { + *n_common = 0; + return false; + } + + /* + * If both lists are non-empty, iterate through both to find out how many + * items are shared. + */ + forboth(key1, keys1, key2, keys2) + { + PathKey *pathkey1 = (PathKey *) lfirst(key1); + PathKey *pathkey2 = (PathKey *) lfirst(key2); + + if (pathkey1 != pathkey2) + { + *n_common = n; + return false; + } + n++; + } + + /* If we ended with a null value, then we've processed the whole list. */ + *n_common = n; + return (key1 == NULL); +} + +/* + * get_cheapest_path_for_pathkeys + * Find the cheapest path (according to the specified criterion) that + * satisfies the given pathkeys and parameterization. + * Return NULL if no such path. + * + * 'paths' is a list of possible paths that all generate the same relation + * 'pathkeys' represents a required ordering (in canonical form!) + * 'required_outer' denotes allowable outer relations for parameterized paths + * 'cost_criterion' is STARTUP_COST or TOTAL_COST + * 'require_parallel_safe' causes us to consider only parallel-safe paths + */ +Path * +get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, + Relids required_outer, + CostSelector cost_criterion, + bool require_parallel_safe) +{ + Path *matched_path = NULL; + ListCell *l; + + foreach(l, paths) + { + Path *path = (Path *) lfirst(l); + + /* + * Since cost comparison is a lot cheaper than pathkey comparison, do + * that first. (XXX is that still true?) + */ + if (matched_path != NULL && + compare_path_costs(matched_path, path, cost_criterion) <= 0) + continue; + + if (require_parallel_safe && !path->parallel_safe) + continue; + + if (pathkeys_contained_in(pathkeys, path->pathkeys) && + bms_is_subset(PATH_REQ_OUTER(path), required_outer)) + matched_path = path; + } + return matched_path; +} + +/* + * get_cheapest_fractional_path_for_pathkeys + * Find the cheapest path (for retrieving a specified fraction of all + * the tuples) that satisfies the given pathkeys and parameterization. + * Return NULL if no such path. + * + * See compare_fractional_path_costs() for the interpretation of the fraction + * parameter. + * + * 'paths' is a list of possible paths that all generate the same relation + * 'pathkeys' represents a required ordering (in canonical form!) + * 'required_outer' denotes allowable outer relations for parameterized paths + * 'fraction' is the fraction of the total tuples expected to be retrieved + */ +Path * +get_cheapest_fractional_path_for_pathkeys(List *paths, + List *pathkeys, + Relids required_outer, + double fraction) +{ + Path *matched_path = NULL; + ListCell *l; + + foreach(l, paths) + { + Path *path = (Path *) lfirst(l); + + /* + * Since cost comparison is a lot cheaper than pathkey comparison, do + * that first. (XXX is that still true?) + */ + if (matched_path != NULL && + compare_fractional_path_costs(matched_path, path, fraction) <= 0) + continue; + + if (pathkeys_contained_in(pathkeys, path->pathkeys) && + bms_is_subset(PATH_REQ_OUTER(path), required_outer)) + matched_path = path; + } + return matched_path; +} + + +/* + * get_cheapest_parallel_safe_total_inner + * Find the unparameterized parallel-safe path with the least total cost. + */ +Path * +get_cheapest_parallel_safe_total_inner(List *paths) +{ + ListCell *l; + + foreach(l, paths) + { + Path *innerpath = (Path *) lfirst(l); + + if (innerpath->parallel_safe && + bms_is_empty(PATH_REQ_OUTER(innerpath))) + return innerpath; + } + + return NULL; +} + +/**************************************************************************** + * NEW PATHKEY FORMATION + ****************************************************************************/ + +/* + * build_index_pathkeys + * Build a pathkeys list that describes the ordering induced by an index + * scan using the given index. (Note that an unordered index doesn't + * induce any ordering, so we return NIL.) + * + * If 'scandir' is BackwardScanDirection, build pathkeys representing a + * backwards scan of the index. + * + * We iterate only key columns of covering indexes, since non-key columns + * don't influence index ordering. The result is canonical, meaning that + * redundant pathkeys are removed; it may therefore have fewer entries than + * there are key columns in the index. + * + * Another reason for stopping early is that we may be able to tell that + * an index column's sort order is uninteresting for this query. However, + * that test is just based on the existence of an EquivalenceClass and not + * on position in pathkey lists, so it's not complete. Caller should call + * truncate_useless_pathkeys() to possibly remove more pathkeys. + */ +List * +build_index_pathkeys(PlannerInfo *root, + IndexOptInfo *index, + ScanDirection scandir) +{ + List *retval = NIL; + ListCell *lc; + int i; + + if (index->sortopfamily == NULL) + return NIL; /* non-orderable index */ + + i = 0; + foreach(lc, index->indextlist) + { + TargetEntry *indextle = (TargetEntry *) lfirst(lc); + Expr *indexkey; + bool reverse_sort; + bool nulls_first; + PathKey *cpathkey; + + /* + * INCLUDE columns are stored in index unordered, so they don't + * support ordered index scan. + */ + if (i >= index->nkeycolumns) + break; + + /* We assume we don't need to make a copy of the tlist item */ + indexkey = indextle->expr; + + if (ScanDirectionIsBackward(scandir)) + { + reverse_sort = !index->reverse_sort[i]; + nulls_first = !index->nulls_first[i]; + } + else + { + reverse_sort = index->reverse_sort[i]; + nulls_first = index->nulls_first[i]; + } + + /* + * OK, try to make a canonical pathkey for this sort key. Note we're + * underneath any outer joins, so nullable_relids should be NULL. + */ + cpathkey = make_pathkey_from_sortinfo(root, + indexkey, + NULL, + index->sortopfamily[i], + index->opcintype[i], + index->indexcollations[i], + reverse_sort, + nulls_first, + 0, + index->rel->relids, + false); + + if (cpathkey) + { + /* + * We found the sort key in an EquivalenceClass, so it's relevant + * for this query. Add it to list, unless it's redundant. + */ + if (!pathkey_is_redundant(cpathkey, retval)) + retval = lappend(retval, cpathkey); + } + else + { + /* + * Boolean index keys might be redundant even if they do not + * appear in an EquivalenceClass, because of our special treatment + * of boolean equality conditions --- see the comment for + * indexcol_is_bool_constant_for_query(). If that applies, we can + * continue to examine lower-order index columns. Otherwise, the + * sort key is not an interesting sort order for this query, so we + * should stop considering index columns; any lower-order sort + * keys won't be useful either. + */ + if (!indexcol_is_bool_constant_for_query(root, index, i)) + break; + } + + i++; + } + + return retval; +} + +/* + * partkey_is_bool_constant_for_query + * + * If a partition key column is constrained to have a constant value by the + * query's WHERE conditions, then it's irrelevant for sort-order + * considerations. Usually that means we have a restriction clause + * WHERE partkeycol = constant, which gets turned into an EquivalenceClass + * containing a constant, which is recognized as redundant by + * build_partition_pathkeys(). But if the partition key column is a + * boolean variable (or expression), then we are not going to see such a + * WHERE clause, because expression preprocessing will have simplified it + * to "WHERE partkeycol" or "WHERE NOT partkeycol". So we are not going + * to have a matching EquivalenceClass (unless the query also contains + * "ORDER BY partkeycol"). To allow such cases to work the same as they would + * for non-boolean values, this function is provided to detect whether the + * specified partition key column matches a boolean restriction clause. + */ +static bool +partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol) +{ + PartitionScheme partscheme = partrel->part_scheme; + ListCell *lc; + + /* If the partkey isn't boolean, we can't possibly get a match */ + if (!IsBooleanOpfamily(partscheme->partopfamily[partkeycol])) + return false; + + /* Check each restriction clause for the partitioned rel */ + foreach(lc, partrel->baserestrictinfo) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); + + /* Ignore pseudoconstant quals, they won't match */ + if (rinfo->pseudoconstant) + continue; + + /* See if we can match the clause's expression to the partkey column */ + if (matches_boolean_partition_clause(rinfo, partrel, partkeycol)) + return true; + } + + return false; +} + +/* + * matches_boolean_partition_clause + * Determine if the boolean clause described by rinfo matches + * partrel's partkeycol-th partition key column. + * + * "Matches" can be either an exact match (equivalent to partkey = true), + * or a NOT above an exact match (equivalent to partkey = false). + */ +static bool +matches_boolean_partition_clause(RestrictInfo *rinfo, + RelOptInfo *partrel, int partkeycol) +{ + Node *clause = (Node *) rinfo->clause; + Node *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]); + + /* Direct match? */ + if (equal(partexpr, clause)) + return true; + /* NOT clause? */ + else if (is_notclause(clause)) + { + Node *arg = (Node *) get_notclausearg((Expr *) clause); + + if (equal(partexpr, arg)) + return true; + } + + return false; +} + +/* + * build_partition_pathkeys + * Build a pathkeys list that describes the ordering induced by the + * partitions of partrel, under either forward or backward scan + * as per scandir. + * + * Caller must have checked that the partitions are properly ordered, + * as detected by partitions_are_ordered(). + * + * Sets *partialkeys to true if pathkeys were only built for a prefix of the + * partition key, or false if the pathkeys include all columns of the + * partition key. + */ +List * +build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel, + ScanDirection scandir, bool *partialkeys) +{ + List *retval = NIL; + PartitionScheme partscheme = partrel->part_scheme; + int i; + + Assert(partscheme != NULL); + Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts)); + /* For now, we can only cope with baserels */ + Assert(IS_SIMPLE_REL(partrel)); + + for (i = 0; i < partscheme->partnatts; i++) + { + PathKey *cpathkey; + Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]); + + /* + * Try to make a canonical pathkey for this partkey. + * + * We're considering a baserel scan, so nullable_relids should be + * NULL. Also, we assume the PartitionDesc lists any NULL partition + * last, so we treat the scan like a NULLS LAST index: we have + * nulls_first for backwards scan only. + */ + cpathkey = make_pathkey_from_sortinfo(root, + keyCol, + NULL, + partscheme->partopfamily[i], + partscheme->partopcintype[i], + partscheme->partcollation[i], + ScanDirectionIsBackward(scandir), + ScanDirectionIsBackward(scandir), + 0, + partrel->relids, + false); + + + if (cpathkey) + { + /* + * We found the sort key in an EquivalenceClass, so it's relevant + * for this query. Add it to list, unless it's redundant. + */ + if (!pathkey_is_redundant(cpathkey, retval)) + retval = lappend(retval, cpathkey); + } + else + { + /* + * Boolean partition keys might be redundant even if they do not + * appear in an EquivalenceClass, because of our special treatment + * of boolean equality conditions --- see the comment for + * partkey_is_bool_constant_for_query(). If that applies, we can + * continue to examine lower-order partition keys. Otherwise, the + * sort key is not an interesting sort order for this query, so we + * should stop considering partition columns; any lower-order sort + * keys won't be useful either. + */ + if (!partkey_is_bool_constant_for_query(partrel, i)) + { + *partialkeys = true; + return retval; + } + } + } + + *partialkeys = false; + return retval; +} + +/* + * build_expression_pathkey + * Build a pathkeys list that describes an ordering by a single expression + * using the given sort operator. + * + * expr, nullable_relids, and rel are as for make_pathkey_from_sortinfo. + * We induce the other arguments assuming default sort order for the operator. + * + * Similarly to make_pathkey_from_sortinfo, the result is NIL if create_it + * is false and the expression isn't already in some EquivalenceClass. + */ +List * +build_expression_pathkey(PlannerInfo *root, + Expr *expr, + Relids nullable_relids, + Oid opno, + Relids rel, + bool create_it) +{ + List *pathkeys; + Oid opfamily, + opcintype; + int16 strategy; + PathKey *cpathkey; + + /* Find the operator in pg_amop --- failure shouldn't happen */ + if (!get_ordering_op_properties(opno, + &opfamily, &opcintype, &strategy)) + elog(ERROR, "operator %u is not a valid ordering operator", + opno); + + cpathkey = make_pathkey_from_sortinfo(root, + expr, + nullable_relids, + opfamily, + opcintype, + exprCollation((Node *) expr), + (strategy == BTGreaterStrategyNumber), + (strategy == BTGreaterStrategyNumber), + 0, + rel, + create_it); + + if (cpathkey) + pathkeys = list_make1(cpathkey); + else + pathkeys = NIL; + + return pathkeys; +} + +/* + * convert_subquery_pathkeys + * Build a pathkeys list that describes the ordering of a subquery's + * result, in the terms of the outer query. This is essentially a + * task of conversion. + * + * 'rel': outer query's RelOptInfo for the subquery relation. + * 'subquery_pathkeys': the subquery's output pathkeys, in its terms. + * 'subquery_tlist': the subquery's output targetlist, in its terms. + * + * We intentionally don't do truncate_useless_pathkeys() here, because there + * are situations where seeing the raw ordering of the subquery is helpful. + * For example, if it returns ORDER BY x DESC, that may prompt us to + * construct a mergejoin using DESC order rather than ASC order; but the + * right_merge_direction heuristic would have us throw the knowledge away. + */ +List * +convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel, + List *subquery_pathkeys, + List *subquery_tlist) +{ + List *retval = NIL; + int retvallen = 0; + int outer_query_keys = list_length(root->query_pathkeys); + ListCell *i; + + foreach(i, subquery_pathkeys) + { + PathKey *sub_pathkey = (PathKey *) lfirst(i); + EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass; + PathKey *best_pathkey = NULL; + + if (sub_eclass->ec_has_volatile) + { + /* + * If the sub_pathkey's EquivalenceClass is volatile, then it must + * have come from an ORDER BY clause, and we have to match it to + * that same targetlist entry. + */ + TargetEntry *tle; + Var *outer_var; + + if (sub_eclass->ec_sortref == 0) /* can't happen */ + elog(ERROR, "volatile EquivalenceClass has no sortref"); + tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist); + Assert(tle); + /* Is TLE actually available to the outer query? */ + outer_var = find_var_for_subquery_tle(rel, tle); + if (outer_var) + { + /* We can represent this sub_pathkey */ + EquivalenceMember *sub_member; + EquivalenceClass *outer_ec; + + Assert(list_length(sub_eclass->ec_members) == 1); + sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members); + + /* + * Note: it might look funny to be setting sortref = 0 for a + * reference to a volatile sub_eclass. However, the + * expression is *not* volatile in the outer query: it's just + * a Var referencing whatever the subquery emitted. (IOW, the + * outer query isn't going to re-execute the volatile + * expression itself.) So this is okay. Likewise, it's + * correct to pass nullable_relids = NULL, because we're + * underneath any outer joins appearing in the outer query. + */ + outer_ec = + get_eclass_for_sort_expr(root, + (Expr *) outer_var, + NULL, + sub_eclass->ec_opfamilies, + sub_member->em_datatype, + sub_eclass->ec_collation, + 0, + rel->relids, + false); + + /* + * If we don't find a matching EC, sub-pathkey isn't + * interesting to the outer query + */ + if (outer_ec) + best_pathkey = + make_canonical_pathkey(root, + outer_ec, + sub_pathkey->pk_opfamily, + sub_pathkey->pk_strategy, + sub_pathkey->pk_nulls_first); + } + } + else + { + /* + * Otherwise, the sub_pathkey's EquivalenceClass could contain + * multiple elements (representing knowledge that multiple items + * are effectively equal). Each element might match none, one, or + * more of the output columns that are visible to the outer query. + * This means we may have multiple possible representations of the + * sub_pathkey in the context of the outer query. Ideally we + * would generate them all and put them all into an EC of the + * outer query, thereby propagating equality knowledge up to the + * outer query. Right now we cannot do so, because the outer + * query's EquivalenceClasses are already frozen when this is + * called. Instead we prefer the one that has the highest "score" + * (number of EC peers, plus one if it matches the outer + * query_pathkeys). This is the most likely to be useful in the + * outer query. + */ + int best_score = -1; + ListCell *j; + + foreach(j, sub_eclass->ec_members) + { + EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j); + Expr *sub_expr = sub_member->em_expr; + Oid sub_expr_type = sub_member->em_datatype; + Oid sub_expr_coll = sub_eclass->ec_collation; + ListCell *k; + + if (sub_member->em_is_child) + continue; /* ignore children here */ + + foreach(k, subquery_tlist) + { + TargetEntry *tle = (TargetEntry *) lfirst(k); + Var *outer_var; + Expr *tle_expr; + EquivalenceClass *outer_ec; + PathKey *outer_pk; + int score; + + /* Is TLE actually available to the outer query? */ + outer_var = find_var_for_subquery_tle(rel, tle); + if (!outer_var) + continue; + + /* + * The targetlist entry is considered to match if it + * matches after sort-key canonicalization. That is + * needed since the sub_expr has been through the same + * process. + */ + tle_expr = canonicalize_ec_expression(tle->expr, + sub_expr_type, + sub_expr_coll); + if (!equal(tle_expr, sub_expr)) + continue; + + /* See if we have a matching EC for the TLE */ + outer_ec = get_eclass_for_sort_expr(root, + (Expr *) outer_var, + NULL, + sub_eclass->ec_opfamilies, + sub_expr_type, + sub_expr_coll, + 0, + rel->relids, + false); + + /* + * If we don't find a matching EC, this sub-pathkey isn't + * interesting to the outer query + */ + if (!outer_ec) + continue; + + outer_pk = make_canonical_pathkey(root, + outer_ec, + sub_pathkey->pk_opfamily, + sub_pathkey->pk_strategy, + sub_pathkey->pk_nulls_first); + /* score = # of equivalence peers */ + score = list_length(outer_ec->ec_members) - 1; + /* +1 if it matches the proper query_pathkeys item */ + if (retvallen < outer_query_keys && + list_nth(root->query_pathkeys, retvallen) == outer_pk) + score++; + if (score > best_score) + { + best_pathkey = outer_pk; + best_score = score; + } + } + } + } + + /* + * If we couldn't find a representation of this sub_pathkey, we're + * done (we can't use the ones to its right, either). + */ + if (!best_pathkey) + break; + + /* + * Eliminate redundant ordering info; could happen if outer query + * equivalences subquery keys... + */ + if (!pathkey_is_redundant(best_pathkey, retval)) + { + retval = lappend(retval, best_pathkey); + retvallen++; + } + } + + return retval; +} + +/* + * find_var_for_subquery_tle + * + * If the given subquery tlist entry is due to be emitted by the subquery's + * scan node, return a Var for it, else return NULL. + * + * We need this to ensure that we don't return pathkeys describing values + * that are unavailable above the level of the subquery scan. + */ +static Var * +find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle) +{ + ListCell *lc; + + /* If the TLE is resjunk, it's certainly not visible to the outer query */ + if (tle->resjunk) + return NULL; + + /* Search the rel's targetlist to see what it will return */ + foreach(lc, rel->reltarget->exprs) + { + Var *var = (Var *) lfirst(lc); + + /* Ignore placeholders */ + if (!IsA(var, Var)) + continue; + Assert(var->varno == rel->relid); + + /* If we find a Var referencing this TLE, we're good */ + if (var->varattno == tle->resno) + return copyObject(var); /* Make a copy for safety */ + } + return NULL; +} + +/* + * build_join_pathkeys + * Build the path keys for a join relation constructed by mergejoin or + * nestloop join. This is normally the same as the outer path's keys. + * + * EXCEPTION: in a FULL or RIGHT join, we cannot treat the result as + * having the outer path's path keys, because null lefthand rows may be + * inserted at random points. It must be treated as unsorted. + * + * We truncate away any pathkeys that are uninteresting for higher joins. + * + * 'joinrel' is the join relation that paths are being formed for + * 'jointype' is the join type (inner, left, full, etc) + * 'outer_pathkeys' is the list of the current outer path's path keys + * + * Returns the list of new path keys. + */ +List * +build_join_pathkeys(PlannerInfo *root, + RelOptInfo *joinrel, + JoinType jointype, + List *outer_pathkeys) +{ + if (jointype == JOIN_FULL || jointype == JOIN_RIGHT) + return NIL; + + /* + * This used to be quite a complex bit of code, but now that all pathkey + * sublists start out life canonicalized, we don't have to do a darn thing + * here! + * + * We do, however, need to truncate the pathkeys list, since it may + * contain pathkeys that were useful for forming this joinrel but are + * uninteresting to higher levels. + */ + return truncate_useless_pathkeys(root, joinrel, outer_pathkeys); +} + +/**************************************************************************** + * PATHKEYS AND SORT CLAUSES + ****************************************************************************/ + +/* + * make_pathkeys_for_sortclauses + * Generate a pathkeys list that represents the sort order specified + * by a list of SortGroupClauses + * + * The resulting PathKeys are always in canonical form. (Actually, there + * is no longer any code anywhere that creates non-canonical PathKeys.) + * + * We assume that root->nullable_baserels is the set of base relids that could + * have gone to NULL below the SortGroupClause expressions. This is okay if + * the expressions came from the query's top level (ORDER BY, DISTINCT, etc) + * and if this function is only invoked after deconstruct_jointree. In the + * future we might have to make callers pass in the appropriate + * nullable-relids set, but for now it seems unnecessary. + * + * 'sortclauses' is a list of SortGroupClause nodes + * 'tlist' is the targetlist to find the referenced tlist entries in + */ +List * +make_pathkeys_for_sortclauses(PlannerInfo *root, + List *sortclauses, + List *tlist) +{ + List *pathkeys = NIL; + ListCell *l; + + foreach(l, sortclauses) + { + SortGroupClause *sortcl = (SortGroupClause *) lfirst(l); + Expr *sortkey; + PathKey *pathkey; + + sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist); + Assert(OidIsValid(sortcl->sortop)); + pathkey = make_pathkey_from_sortop(root, + sortkey, + root->nullable_baserels, + sortcl->sortop, + sortcl->nulls_first, + sortcl->tleSortGroupRef, + true); + + /* Canonical form eliminates redundant ordering keys */ + if (!pathkey_is_redundant(pathkey, pathkeys)) + pathkeys = lappend(pathkeys, pathkey); + } + return pathkeys; +} + +/**************************************************************************** + * PATHKEYS AND MERGECLAUSES + ****************************************************************************/ + +/* + * initialize_mergeclause_eclasses + * Set the EquivalenceClass links in a mergeclause restrictinfo. + * + * RestrictInfo contains fields in which we may cache pointers to + * EquivalenceClasses for the left and right inputs of the mergeclause. + * (If the mergeclause is a true equivalence clause these will be the + * same EquivalenceClass, otherwise not.) If the mergeclause is either + * used to generate an EquivalenceClass, or derived from an EquivalenceClass, + * then it's easy to set up the left_ec and right_ec members --- otherwise, + * this function should be called to set them up. We will generate new + * EquivalenceClauses if necessary to represent the mergeclause's left and + * right sides. + * + * Note this is called before EC merging is complete, so the links won't + * necessarily point to canonical ECs. Before they are actually used for + * anything, update_mergeclause_eclasses must be called to ensure that + * they've been updated to point to canonical ECs. + */ +void +initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo) +{ + Expr *clause = restrictinfo->clause; + Oid lefttype, + righttype; + + /* Should be a mergeclause ... */ + Assert(restrictinfo->mergeopfamilies != NIL); + /* ... with links not yet set */ + Assert(restrictinfo->left_ec == NULL); + Assert(restrictinfo->right_ec == NULL); + + /* Need the declared input types of the operator */ + op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype); + + /* Find or create a matching EquivalenceClass for each side */ + restrictinfo->left_ec = + get_eclass_for_sort_expr(root, + (Expr *) get_leftop(clause), + restrictinfo->nullable_relids, + restrictinfo->mergeopfamilies, + lefttype, + ((OpExpr *) clause)->inputcollid, + 0, + NULL, + true); + restrictinfo->right_ec = + get_eclass_for_sort_expr(root, + (Expr *) get_rightop(clause), + restrictinfo->nullable_relids, + restrictinfo->mergeopfamilies, + righttype, + ((OpExpr *) clause)->inputcollid, + 0, + NULL, + true); +} + +/* + * update_mergeclause_eclasses + * Make the cached EquivalenceClass links valid in a mergeclause + * restrictinfo. + * + * These pointers should have been set by process_equivalence or + * initialize_mergeclause_eclasses, but they might have been set to + * non-canonical ECs that got merged later. Chase up to the canonical + * merged parent if so. + */ +void +update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo) +{ + /* Should be a merge clause ... */ + Assert(restrictinfo->mergeopfamilies != NIL); + /* ... with pointers already set */ + Assert(restrictinfo->left_ec != NULL); + Assert(restrictinfo->right_ec != NULL); + + /* Chase up to the top as needed */ + while (restrictinfo->left_ec->ec_merged) + restrictinfo->left_ec = restrictinfo->left_ec->ec_merged; + while (restrictinfo->right_ec->ec_merged) + restrictinfo->right_ec = restrictinfo->right_ec->ec_merged; +} + +/* + * find_mergeclauses_for_outer_pathkeys + * This routine attempts to find a list of mergeclauses that can be + * used with a specified ordering for the join's outer relation. + * If successful, it returns a list of mergeclauses. + * + * 'pathkeys' is a pathkeys list showing the ordering of an outer-rel path. + * 'restrictinfos' is a list of mergejoinable restriction clauses for the + * join relation being formed, in no particular order. + * + * The restrictinfos must be marked (via outer_is_left) to show which side + * of each clause is associated with the current outer path. (See + * select_mergejoin_clauses()) + * + * The result is NIL if no merge can be done, else a maximal list of + * usable mergeclauses (represented as a list of their restrictinfo nodes). + * The list is ordered to match the pathkeys, as required for execution. + */ +List * +find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, + List *pathkeys, + List *restrictinfos) +{ + List *mergeclauses = NIL; + ListCell *i; + + /* make sure we have eclasses cached in the clauses */ + foreach(i, restrictinfos) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(i); + + update_mergeclause_eclasses(root, rinfo); + } + + foreach(i, pathkeys) + { + PathKey *pathkey = (PathKey *) lfirst(i); + EquivalenceClass *pathkey_ec = pathkey->pk_eclass; + List *matched_restrictinfos = NIL; + ListCell *j; + + /*---------- + * A mergejoin clause matches a pathkey if it has the same EC. + * If there are multiple matching clauses, take them all. In plain + * inner-join scenarios we expect only one match, because + * equivalence-class processing will have removed any redundant + * mergeclauses. However, in outer-join scenarios there might be + * multiple matches. An example is + * + * select * from a full join b + * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2; + * + * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three + * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed + * we *must* do so or we will be unable to form a valid plan. + * + * We expect that the given pathkeys list is canonical, which means + * no two members have the same EC, so it's not possible for this + * code to enter the same mergeclause into the result list twice. + * + * It's possible that multiple matching clauses might have different + * ECs on the other side, in which case the order we put them into our + * result makes a difference in the pathkeys required for the inner + * input rel. However this routine hasn't got any info about which + * order would be best, so we don't worry about that. + * + * It's also possible that the selected mergejoin clauses produce + * a noncanonical ordering of pathkeys for the inner side, ie, we + * might select clauses that reference b.v1, b.v2, b.v1 in that + * order. This is not harmful in itself, though it suggests that + * the clauses are partially redundant. Since the alternative is + * to omit mergejoin clauses and thereby possibly fail to generate a + * plan altogether, we live with it. make_inner_pathkeys_for_merge() + * has to delete duplicates when it constructs the inner pathkeys + * list, and we also have to deal with such cases specially in + * create_mergejoin_plan(). + *---------- + */ + foreach(j, restrictinfos) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(j); + EquivalenceClass *clause_ec; + + clause_ec = rinfo->outer_is_left ? + rinfo->left_ec : rinfo->right_ec; + if (clause_ec == pathkey_ec) + matched_restrictinfos = lappend(matched_restrictinfos, rinfo); + } + + /* + * If we didn't find a mergeclause, we're done --- any additional + * sort-key positions in the pathkeys are useless. (But we can still + * mergejoin if we found at least one mergeclause.) + */ + if (matched_restrictinfos == NIL) + break; + + /* + * If we did find usable mergeclause(s) for this sort-key position, + * add them to result list. + */ + mergeclauses = list_concat(mergeclauses, matched_restrictinfos); + } + + return mergeclauses; +} + +/* + * select_outer_pathkeys_for_merge + * Builds a pathkey list representing a possible sort ordering + * that can be used with the given mergeclauses. + * + * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses + * that will be used in a merge join. + * 'joinrel' is the join relation we are trying to construct. + * + * The restrictinfos must be marked (via outer_is_left) to show which side + * of each clause is associated with the current outer path. (See + * select_mergejoin_clauses()) + * + * Returns a pathkeys list that can be applied to the outer relation. + * + * Since we assume here that a sort is required, there is no particular use + * in matching any available ordering of the outerrel. (joinpath.c has an + * entirely separate code path for considering sort-free mergejoins.) Rather, + * it's interesting to try to match the requested query_pathkeys so that a + * second output sort may be avoided; and failing that, we try to list "more + * popular" keys (those with the most unmatched EquivalenceClass peers) + * earlier, in hopes of making the resulting ordering useful for as many + * higher-level mergejoins as possible. + */ +List * +select_outer_pathkeys_for_merge(PlannerInfo *root, + List *mergeclauses, + RelOptInfo *joinrel) +{ + List *pathkeys = NIL; + int nClauses = list_length(mergeclauses); + EquivalenceClass **ecs; + int *scores; + int necs; + ListCell *lc; + int j; + + /* Might have no mergeclauses */ + if (nClauses == 0) + return NIL; + + /* + * Make arrays of the ECs used by the mergeclauses (dropping any + * duplicates) and their "popularity" scores. + */ + ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *)); + scores = (int *) palloc(nClauses * sizeof(int)); + necs = 0; + + foreach(lc, mergeclauses) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); + EquivalenceClass *oeclass; + int score; + ListCell *lc2; + + /* get the outer eclass */ + update_mergeclause_eclasses(root, rinfo); + + if (rinfo->outer_is_left) + oeclass = rinfo->left_ec; + else + oeclass = rinfo->right_ec; + + /* reject duplicates */ + for (j = 0; j < necs; j++) + { + if (ecs[j] == oeclass) + break; + } + if (j < necs) + continue; + + /* compute score */ + score = 0; + foreach(lc2, oeclass->ec_members) + { + EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2); + + /* Potential future join partner? */ + if (!em->em_is_const && !em->em_is_child && + !bms_overlap(em->em_relids, joinrel->relids)) + score++; + } + + ecs[necs] = oeclass; + scores[necs] = score; + necs++; + } + + /* + * Find out if we have all the ECs mentioned in query_pathkeys; if so we + * can generate a sort order that's also useful for final output. There is + * no percentage in a partial match, though, so we have to have 'em all. + */ + if (root->query_pathkeys) + { + foreach(lc, root->query_pathkeys) + { + PathKey *query_pathkey = (PathKey *) lfirst(lc); + EquivalenceClass *query_ec = query_pathkey->pk_eclass; + + for (j = 0; j < necs; j++) + { + if (ecs[j] == query_ec) + break; /* found match */ + } + if (j >= necs) + break; /* didn't find match */ + } + /* if we got to the end of the list, we have them all */ + if (lc == NULL) + { + /* copy query_pathkeys as starting point for our output */ + pathkeys = list_copy(root->query_pathkeys); + /* mark their ECs as already-emitted */ + foreach(lc, root->query_pathkeys) + { + PathKey *query_pathkey = (PathKey *) lfirst(lc); + EquivalenceClass *query_ec = query_pathkey->pk_eclass; + + for (j = 0; j < necs; j++) + { + if (ecs[j] == query_ec) + { + scores[j] = -1; + break; + } + } + } + } + } + + /* + * Add remaining ECs to the list in popularity order, using a default sort + * ordering. (We could use qsort() here, but the list length is usually + * so small it's not worth it.) + */ + for (;;) + { + int best_j; + int best_score; + EquivalenceClass *ec; + PathKey *pathkey; + + best_j = 0; + best_score = scores[0]; + for (j = 1; j < necs; j++) + { + if (scores[j] > best_score) + { + best_j = j; + best_score = scores[j]; + } + } + if (best_score < 0) + break; /* all done */ + ec = ecs[best_j]; + scores[best_j] = -1; + pathkey = make_canonical_pathkey(root, + ec, + linitial_oid(ec->ec_opfamilies), + BTLessStrategyNumber, + false); + /* can't be redundant because no duplicate ECs */ + Assert(!pathkey_is_redundant(pathkey, pathkeys)); + pathkeys = lappend(pathkeys, pathkey); + } + + pfree(ecs); + pfree(scores); + + return pathkeys; +} + +/* + * make_inner_pathkeys_for_merge + * Builds a pathkey list representing the explicit sort order that + * must be applied to an inner path to make it usable with the + * given mergeclauses. + * + * 'mergeclauses' is a list of RestrictInfos for the mergejoin clauses + * that will be used in a merge join, in order. + * 'outer_pathkeys' are the already-known canonical pathkeys for the outer + * side of the join. + * + * The restrictinfos must be marked (via outer_is_left) to show which side + * of each clause is associated with the current outer path. (See + * select_mergejoin_clauses()) + * + * Returns a pathkeys list that can be applied to the inner relation. + * + * Note that it is not this routine's job to decide whether sorting is + * actually needed for a particular input path. Assume a sort is necessary; + * just make the keys, eh? + */ +List * +make_inner_pathkeys_for_merge(PlannerInfo *root, + List *mergeclauses, + List *outer_pathkeys) +{ + List *pathkeys = NIL; + EquivalenceClass *lastoeclass; + PathKey *opathkey; + ListCell *lc; + ListCell *lop; + + lastoeclass = NULL; + opathkey = NULL; + lop = list_head(outer_pathkeys); + + foreach(lc, mergeclauses) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); + EquivalenceClass *oeclass; + EquivalenceClass *ieclass; + PathKey *pathkey; + + update_mergeclause_eclasses(root, rinfo); + + if (rinfo->outer_is_left) + { + oeclass = rinfo->left_ec; + ieclass = rinfo->right_ec; + } + else + { + oeclass = rinfo->right_ec; + ieclass = rinfo->left_ec; + } + + /* outer eclass should match current or next pathkeys */ + /* we check this carefully for debugging reasons */ + if (oeclass != lastoeclass) + { + if (!lop) + elog(ERROR, "too few pathkeys for mergeclauses"); + opathkey = (PathKey *) lfirst(lop); + lop = lnext(outer_pathkeys, lop); + lastoeclass = opathkey->pk_eclass; + if (oeclass != lastoeclass) + elog(ERROR, "outer pathkeys do not match mergeclause"); + } + + /* + * Often, we'll have same EC on both sides, in which case the outer + * pathkey is also canonical for the inner side, and we can skip a + * useless search. + */ + if (ieclass == oeclass) + pathkey = opathkey; + else + pathkey = make_canonical_pathkey(root, + ieclass, + opathkey->pk_opfamily, + opathkey->pk_strategy, + opathkey->pk_nulls_first); + + /* + * Don't generate redundant pathkeys (which can happen if multiple + * mergeclauses refer to the same EC). Because we do this, the output + * pathkey list isn't necessarily ordered like the mergeclauses, which + * complicates life for create_mergejoin_plan(). But if we didn't, + * we'd have a noncanonical sort key list, which would be bad; for one + * reason, it certainly wouldn't match any available sort order for + * the input relation. + */ + if (!pathkey_is_redundant(pathkey, pathkeys)) + pathkeys = lappend(pathkeys, pathkey); + } + + return pathkeys; +} + +/* + * trim_mergeclauses_for_inner_pathkeys + * This routine trims a list of mergeclauses to include just those that + * work with a specified ordering for the join's inner relation. + * + * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses for the + * join relation being formed, in an order known to work for the + * currently-considered sort ordering of the join's outer rel. + * 'pathkeys' is a pathkeys list showing the ordering of an inner-rel path; + * it should be equal to, or a truncation of, the result of + * make_inner_pathkeys_for_merge for these mergeclauses. + * + * What we return will be a prefix of the given mergeclauses list. + * + * We need this logic because make_inner_pathkeys_for_merge's result isn't + * necessarily in the same order as the mergeclauses. That means that if we + * consider an inner-rel pathkey list that is a truncation of that result, + * we might need to drop mergeclauses even though they match a surviving inner + * pathkey. This happens when they are to the right of a mergeclause that + * matches a removed inner pathkey. + * + * The mergeclauses must be marked (via outer_is_left) to show which side + * of each clause is associated with the current outer path. (See + * select_mergejoin_clauses()) + */ +List * +trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root, + List *mergeclauses, + List *pathkeys) +{ + List *new_mergeclauses = NIL; + PathKey *pathkey; + EquivalenceClass *pathkey_ec; + bool matched_pathkey; + ListCell *lip; + ListCell *i; + + /* No pathkeys => no mergeclauses (though we don't expect this case) */ + if (pathkeys == NIL) + return NIL; + /* Initialize to consider first pathkey */ + lip = list_head(pathkeys); + pathkey = (PathKey *) lfirst(lip); + pathkey_ec = pathkey->pk_eclass; + lip = lnext(pathkeys, lip); + matched_pathkey = false; + + /* Scan mergeclauses to see how many we can use */ + foreach(i, mergeclauses) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(i); + EquivalenceClass *clause_ec; + + /* Assume we needn't do update_mergeclause_eclasses again here */ + + /* Check clause's inner-rel EC against current pathkey */ + clause_ec = rinfo->outer_is_left ? + rinfo->right_ec : rinfo->left_ec; + + /* If we don't have a match, attempt to advance to next pathkey */ + if (clause_ec != pathkey_ec) + { + /* If we had no clauses matching this inner pathkey, must stop */ + if (!matched_pathkey) + break; + + /* Advance to next inner pathkey, if any */ + if (lip == NULL) + break; + pathkey = (PathKey *) lfirst(lip); + pathkey_ec = pathkey->pk_eclass; + lip = lnext(pathkeys, lip); + matched_pathkey = false; + } + + /* If mergeclause matches current inner pathkey, we can use it */ + if (clause_ec == pathkey_ec) + { + new_mergeclauses = lappend(new_mergeclauses, rinfo); + matched_pathkey = true; + } + else + { + /* Else, no hope of adding any more mergeclauses */ + break; + } + } + + return new_mergeclauses; +} + + +/**************************************************************************** + * PATHKEY USEFULNESS CHECKS + * + * We only want to remember as many of the pathkeys of a path as have some + * potential use, either for subsequent mergejoins or for meeting the query's + * requested output ordering. This ensures that add_path() won't consider + * a path to have a usefully different ordering unless it really is useful. + * These routines check for usefulness of given pathkeys. + ****************************************************************************/ + +/* + * pathkeys_useful_for_merging + * Count the number of pathkeys that may be useful for mergejoins + * above the given relation. + * + * We consider a pathkey potentially useful if it corresponds to the merge + * ordering of either side of any joinclause for the rel. This might be + * overoptimistic, since joinclauses that require different other relations + * might never be usable at the same time, but trying to be exact is likely + * to be more trouble than it's worth. + * + * To avoid doubling the number of mergejoin paths considered, we would like + * to consider only one of the two scan directions (ASC or DESC) as useful + * for merging for any given target column. The choice is arbitrary unless + * one of the directions happens to match an ORDER BY key, in which case + * that direction should be preferred, in hopes of avoiding a final sort step. + * right_merge_direction() implements this heuristic. + */ +static int +pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys) +{ + int useful = 0; + ListCell *i; + + foreach(i, pathkeys) + { + PathKey *pathkey = (PathKey *) lfirst(i); + bool matched = false; + ListCell *j; + + /* If "wrong" direction, not useful for merging */ + if (!right_merge_direction(root, pathkey)) + break; + + /* + * First look into the EquivalenceClass of the pathkey, to see if + * there are any members not yet joined to the rel. If so, it's + * surely possible to generate a mergejoin clause using them. + */ + if (rel->has_eclass_joins && + eclass_useful_for_merging(root, pathkey->pk_eclass, rel)) + matched = true; + else + { + /* + * Otherwise search the rel's joininfo list, which contains + * non-EquivalenceClass-derivable join clauses that might + * nonetheless be mergejoinable. + */ + foreach(j, rel->joininfo) + { + RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j); + + if (restrictinfo->mergeopfamilies == NIL) + continue; + update_mergeclause_eclasses(root, restrictinfo); + + if (pathkey->pk_eclass == restrictinfo->left_ec || + pathkey->pk_eclass == restrictinfo->right_ec) + { + matched = true; + break; + } + } + } + + /* + * If we didn't find a mergeclause, we're done --- any additional + * sort-key positions in the pathkeys are useless. (But we can still + * mergejoin if we found at least one mergeclause.) + */ + if (matched) + useful++; + else + break; + } + + return useful; +} + +/* + * right_merge_direction + * Check whether the pathkey embodies the preferred sort direction + * for merging its target column. + */ +static bool +right_merge_direction(PlannerInfo *root, PathKey *pathkey) +{ + ListCell *l; + + foreach(l, root->query_pathkeys) + { + PathKey *query_pathkey = (PathKey *) lfirst(l); + + if (pathkey->pk_eclass == query_pathkey->pk_eclass && + pathkey->pk_opfamily == query_pathkey->pk_opfamily) + { + /* + * Found a matching query sort column. Prefer this pathkey's + * direction iff it matches. Note that we ignore pk_nulls_first, + * which means that a sort might be needed anyway ... but we still + * want to prefer only one of the two possible directions, and we + * might as well use this one. + */ + return (pathkey->pk_strategy == query_pathkey->pk_strategy); + } + } + + /* If no matching ORDER BY request, prefer the ASC direction */ + return (pathkey->pk_strategy == BTLessStrategyNumber); +} + +/* + * pathkeys_useful_for_ordering + * Count the number of pathkeys that are useful for meeting the + * query's requested output ordering. + * + * Because we the have the possibility of incremental sort, a prefix list of + * keys is potentially useful for improving the performance of the requested + * ordering. Thus we return 0, if no valuable keys are found, or the number + * of leading keys shared by the list and the requested ordering.. + */ +static int +pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys) +{ + int n_common_pathkeys; + + if (root->query_pathkeys == NIL) + return 0; /* no special ordering requested */ + + if (pathkeys == NIL) + return 0; /* unordered path */ + + (void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys, + &n_common_pathkeys); + + return n_common_pathkeys; +} + +/* + * truncate_useless_pathkeys + * Shorten the given pathkey list to just the useful pathkeys. + */ +List * +truncate_useless_pathkeys(PlannerInfo *root, + RelOptInfo *rel, + List *pathkeys) +{ + int nuseful; + int nuseful2; + + nuseful = pathkeys_useful_for_merging(root, rel, pathkeys); + nuseful2 = pathkeys_useful_for_ordering(root, pathkeys); + if (nuseful2 > nuseful) + nuseful = nuseful2; + + /* + * Note: not safe to modify input list destructively, but we can avoid + * copying the list if we're not actually going to change it + */ + if (nuseful == 0) + return NIL; + else if (nuseful == list_length(pathkeys)) + return pathkeys; + else + return list_truncate(list_copy(pathkeys), nuseful); +} + +/* + * has_useful_pathkeys + * Detect whether the specified rel could have any pathkeys that are + * useful according to truncate_useless_pathkeys(). + * + * This is a cheap test that lets us skip building pathkeys at all in very + * simple queries. It's OK to err in the direction of returning "true" when + * there really aren't any usable pathkeys, but erring in the other direction + * is bad --- so keep this in sync with the routines above! + * + * We could make the test more complex, for example checking to see if any of + * the joinclauses are really mergejoinable, but that likely wouldn't win + * often enough to repay the extra cycles. Queries with neither a join nor + * a sort are reasonably common, though, so this much work seems worthwhile. + */ +bool +has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel) +{ + if (rel->joininfo != NIL || rel->has_eclass_joins) + return true; /* might be able to use pathkeys for merging */ + if (root->query_pathkeys != NIL) + return true; /* might be able to use them for ordering */ + return false; /* definitely useless */ +} |