diff options
Diffstat (limited to 'src/backend/optimizer/path')
| -rw-r--r-- | src/backend/optimizer/path/indxpath.c | 178 | ||||
| -rw-r--r-- | src/backend/optimizer/path/joinpath.c | 8 | ||||
| -rw-r--r-- | src/backend/optimizer/path/pathkeys.c | 82 |
3 files changed, 192 insertions, 76 deletions
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 99ce241fed1..6af480629e2 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.69 1999/08/16 02:17:50 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.70 1999/08/21 03:49:00 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -70,6 +70,8 @@ static List *index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index, List *clausegroup_list, List *outerrelids_list); static bool useful_for_mergejoin(RelOptInfo *rel, RelOptInfo *index, List *joininfo_list); +static bool useful_for_ordering(Query *root, RelOptInfo *rel, + RelOptInfo *index); static bool match_index_to_operand(int indexkey, Var *operand, RelOptInfo *rel, RelOptInfo *index); static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index); @@ -86,7 +88,8 @@ static List *prefix_quals(Var *leftop, Oid expr_op, * Generate all interesting index paths for the given relation. * * To be considered for an index scan, an index must match one or more - * restriction clauses or join clauses from the query's qual condition. + * restriction clauses or join clauses from the query's qual condition, + * or match the query's ORDER BY condition. * * There are two basic kinds of index scans. A "plain" index scan uses * only restriction clauses (possibly none at all) in its indexqual, @@ -104,14 +107,6 @@ static List *prefix_quals(Var *leftop, Oid expr_op, * relations. The innerjoin paths are *not* in the return list, but are * appended to the "innerjoin" list of the relation itself. * - * XXX An index scan might also be used simply to order the result. We - * probably should create an index path for any index that matches the - * query's ORDER BY condition, even if it doesn't seem useful for join - * or restriction clauses. But currently, such a path would never - * survive the path selection process, so there's no point. The selection - * process needs to award bonus scores to indexscans that produce a - * suitably-ordered result... - * * 'rel' is the relation for which we want to generate index paths * 'indices' is a list of available indexes for 'rel' * 'restrictinfo_list' is a list of restrictinfo nodes for 'rel' @@ -192,13 +187,16 @@ create_index_paths(Query *root, * index path for it even if there were no restriction clauses. * (If there were, there is no need to make another index path.) * This will allow the index to be considered as a base for a - * mergejoin in later processing. + * mergejoin in later processing. Similarly, if the index matches + * the ordering that is needed for the overall query result, make + * an index path for it even if there is no other reason to do so. */ - if (restrictclauses == NIL && - useful_for_mergejoin(rel, index, joininfo_list)) + if (restrictclauses == NIL) { - retval = lappend(retval, - create_index_path(root, rel, index, NIL)); + if (useful_for_mergejoin(rel, index, joininfo_list) || + useful_for_ordering(root, rel, index)) + retval = lappend(retval, + create_index_path(root, rel, index, NIL)); } /* @@ -748,6 +746,101 @@ indexable_operator(Expr *clause, int xclass, Oid relam, return false; } +/* + * useful_for_mergejoin + * Determine whether the given index can support a mergejoin based + * on any available join clause. + * + * We look to see whether the first indexkey of the index matches the + * left or right sides of any of the mergejoinable clauses and provides + * the ordering needed for that side. If so, the index is useful. + * Matching a second or later indexkey is not useful unless there is + * also a mergeclause for the first indexkey, so we need not consider + * secondary indexkeys at this stage. + * + * 'rel' is the relation for which 'index' is defined + * 'joininfo_list' is the list of JoinInfo nodes for 'rel' + */ +static bool +useful_for_mergejoin(RelOptInfo *rel, + RelOptInfo *index, + List *joininfo_list) +{ + int *indexkeys = index->indexkeys; + Oid *ordering = index->ordering; + List *i; + + if (!indexkeys || indexkeys[0] == 0 || + !ordering || ordering[0] == InvalidOid) + return false; /* unordered index is not useful */ + + foreach(i, joininfo_list) + { + JoinInfo *joininfo = (JoinInfo *) lfirst(i); + List *j; + + foreach(j, joininfo->jinfo_restrictinfo) + { + RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j); + + if (restrictinfo->mergejoinoperator) + { + if (restrictinfo->left_sortop == ordering[0] && + match_index_to_operand(indexkeys[0], + get_leftop(restrictinfo->clause), + rel, index)) + return true; + if (restrictinfo->right_sortop == ordering[0] && + match_index_to_operand(indexkeys[0], + get_rightop(restrictinfo->clause), + rel, index)) + return true; + } + } + } + return false; +} + +/* + * useful_for_ordering + * Determine whether the given index can produce an ordering matching + * the order that is wanted for the query result. + * + * We check to see whether either forward or backward scan direction can + * match the specified pathkeys. + * + * 'rel' is the relation for which 'index' is defined + */ +static bool +useful_for_ordering(Query *root, + RelOptInfo *rel, + RelOptInfo *index) +{ + List *index_pathkeys; + + if (root->query_pathkeys == NIL) + return false; /* no special ordering requested */ + + index_pathkeys = build_index_pathkeys(root, rel, index); + + if (index_pathkeys == NIL) + return false; /* unordered index */ + + if (pathkeys_contained_in(root->query_pathkeys, index_pathkeys)) + return true; + + /* caution: commute_pathkeys destructively modifies its argument; + * safe because we just built the index_pathkeys for local use here. + */ + if (commute_pathkeys(index_pathkeys)) + { + if (pathkeys_contained_in(root->query_pathkeys, index_pathkeys)) + return true; /* useful as a reverse-order path */ + } + + return false; +} + /**************************************************************************** * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ---- ****************************************************************************/ @@ -1285,61 +1378,6 @@ index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index, return path_list; } -/* - * useful_for_mergejoin - * Determine whether the given index can support a mergejoin based - * on any available join clause. - * - * We look to see whether the first indexkey of the index matches the - * left or right sides of any of the mergejoinable clauses and provides - * the ordering needed for that side. If so, the index is useful. - * Matching a second or later indexkey is not useful unless there is - * also a mergeclause for the first indexkey, so we need not consider - * secondary indexkeys at this stage. - * - * 'rel' is the relation for which 'index' is defined - * 'joininfo_list' is the list of JoinInfo nodes for 'rel' - */ -static bool -useful_for_mergejoin(RelOptInfo *rel, - RelOptInfo *index, - List *joininfo_list) -{ - int *indexkeys = index->indexkeys; - Oid *ordering = index->ordering; - List *i; - - if (!indexkeys || indexkeys[0] == 0 || - !ordering || ordering[0] == InvalidOid) - return false; /* unordered index is not useful */ - - foreach(i, joininfo_list) - { - JoinInfo *joininfo = (JoinInfo *) lfirst(i); - List *j; - - foreach(j, joininfo->jinfo_restrictinfo) - { - RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j); - - if (restrictinfo->mergejoinoperator) - { - if (restrictinfo->left_sortop == ordering[0] && - match_index_to_operand(indexkeys[0], - get_leftop(restrictinfo->clause), - rel, index)) - return true; - if (restrictinfo->right_sortop == ordering[0] && - match_index_to_operand(indexkeys[0], - get_rightop(restrictinfo->clause), - rel, index)) - return true; - } - } - } - return false; -} - /**************************************************************************** * ---- ROUTINES TO CHECK OPERANDS ---- ****************************************************************************/ diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c index 55891d87a95..c1ac6a2c4d8 100644 --- a/src/backend/optimizer/path/joinpath.c +++ b/src/backend/optimizer/path/joinpath.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.45 1999/08/16 02:17:51 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.46 1999/08/21 03:49:00 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -408,7 +408,8 @@ match_unsorted_outer(RelOptInfo *joinrel, trialinnerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist, ltruncate(clausecount, - trialsortkeys)); + trialsortkeys), + false); if (trialinnerpath != NULL && trialinnerpath->path_cost < cheapest_cost) { @@ -488,7 +489,8 @@ match_unsorted_inner(RelOptInfo *joinrel, /* Look for an outer path already ordered well enough to merge */ mergeouterpath = get_cheapest_path_for_pathkeys(outerrel->pathlist, - outersortkeys); + outersortkeys, + false); /* Should we use the mergeouter, or sort the cheapest outer? */ if (mergeouterpath != NULL && diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 44a7b614b69..41a3ff35b48 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.14 1999/08/16 02:17:52 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.15 1999/08/21 03:49:01 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -20,6 +20,7 @@ #include "optimizer/tlist.h" #include "optimizer/var.h" #include "parser/parsetree.h" +#include "parser/parse_func.h" #include "utils/lsyscache.h" static PathKeyItem *makePathKeyItem(Node *key, Oid sortop); @@ -89,6 +90,11 @@ static List *build_join_pathkey(List *pathkeys, List *join_rel_tlist, * executor might have to split the join into multiple batches. Therefore * a Hashjoin is always given NIL pathkeys. * + * Pathkeys are also useful to represent an ordering that we wish to achieve, + * since they are easily compared to the pathkeys of a potential candidate + * path. So, SortClause lists are turned into pathkeys lists for use inside + * the optimizer. + * * -- bjm & tgl *-------------------- */ @@ -254,9 +260,11 @@ pathkeys_contained_in(List *keys1, List *keys2) * * 'paths' is a list of possible paths (either inner or outer) * 'pathkeys' represents a required ordering + * if 'indexpaths_only' is true, only IndexPaths will be considered. */ Path * -get_cheapest_path_for_pathkeys(List *paths, List *pathkeys) +get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, + bool indexpaths_only) { Path *matched_path = NULL; List *i; @@ -265,6 +273,9 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys) { Path *path = (Path *) lfirst(i); + if (indexpaths_only && ! IsA(path, IndexPath)) + continue; + if (pathkeys_contained_in(pathkeys, path->pathkeys)) { if (matched_path == NULL || @@ -314,7 +325,8 @@ build_index_pathkeys(Query *root, RelOptInfo *rel, RelOptInfo *index) funcnode->funcisindex = false; funcnode->funcsize = 0; funcnode->func_fcache = NULL; - funcnode->func_tlist = NIL; + /* we assume here that the function returns a base type... */ + funcnode->func_tlist = setup_base_tlist(funcnode->functype); funcnode->func_planlist = NIL; while (*indexkeys != 0) @@ -516,6 +528,70 @@ build_join_pathkey(List *pathkey, return new_pathkey; } +/* + * commute_pathkeys + * Attempt to commute the operators in a set of pathkeys, producing + * pathkeys that describe the reverse sort order (DESC instead of ASC). + * Returns TRUE if successful (all the operators have commutators). + * + * CAUTION: given pathkeys are modified in place, even if not successful!! + * Usually, caller should have just built or copied the pathkeys list to + * ensure there are no unwanted side-effects. + */ +bool +commute_pathkeys(List *pathkeys) +{ + List *i; + + foreach(i, pathkeys) + { + List *pathkey = lfirst(i); + List *j; + + foreach(j, pathkey) + { + PathKeyItem *key = lfirst(j); + + key->sortop = get_commutator(key->sortop); + if (key->sortop == InvalidOid) + return false; + } + } + return true; /* successful */ +} + +/**************************************************************************** + * PATHKEYS AND SORT CLAUSES + ****************************************************************************/ + +/* + * make_pathkeys_for_sortclauses + * Generate a pathkeys list that represents the sort order specified + * by a list of SortClauses (GroupClauses will work too!) + * + * 'sortclauses' is a list of SortClause or GroupClause nodes + * 'tlist' is the targetlist to find the referenced tlist entries in + */ +List * +make_pathkeys_for_sortclauses(List *sortclauses, List *tlist) +{ + List *pathkeys = NIL; + List *i; + + foreach(i, sortclauses) + { + SortClause *sortcl = (SortClause *) lfirst(i); + Node *sortkey; + PathKeyItem *pathkey; + + sortkey = get_sortgroupclause_expr(sortcl, tlist); + pathkey = makePathKeyItem(sortkey, sortcl->sortop); + /* pathkey becomes a one-element sublist */ + pathkeys = lappend(pathkeys, lcons(pathkey, NIL)); + } + return pathkeys; +} + /**************************************************************************** * PATHKEYS AND MERGECLAUSES ****************************************************************************/ |