X-Git-Url: https://granicus.if.org/sourcecode?a=blobdiff_plain;f=src%2Fbackend%2Foptimizer%2Fpath%2Findxpath.c;h=7bb4a8eaeb1d83066413fb1e9c34c8b496e2d08b;hb=71ed7eb4941ddb32700a51a8b8b3403eceeca4a9;hp=8b54b664024c36300fd285310f4bfbbf092690b4;hpb=6724a5078748946b8150700125571b6ea62feca8;p=postgresql diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 8b54b66402..7bb4a8eaeb 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -2,136 +2,185 @@ * * indxpath.c * Routines to determine which indices are usable for scanning a - * given relation + * given relation, and create IndexPaths accordingly. * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.44 1999/02/13 23:16:16 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.77 2000/01/22 23:50:14 tgl Exp $ * *------------------------------------------------------------------------- */ +#include #include #include "postgres.h" -#include "access/attnum.h" #include "access/heapam.h" #include "access/nbtree.h" #include "catalog/catname.h" #include "catalog/pg_amop.h" -#include "catalog/pg_type.h" +#include "catalog/pg_operator.h" #include "executor/executor.h" -#include "fmgr.h" +#include "mb/pg_wchar.h" #include "nodes/makefuncs.h" #include "nodes/nodeFuncs.h" -#include "nodes/pg_list.h" -#include "nodes/relation.h" #include "optimizer/clauses.h" -#include "optimizer/restrictinfo.h" #include "optimizer/cost.h" -#include "optimizer/internal.h" -#include "optimizer/keys.h" -#include "optimizer/ordering.h" +#include "optimizer/pathnode.h" #include "optimizer/paths.h" #include "optimizer/plancat.h" -#include "optimizer/pathnode.h" -#include "optimizer/xfunc.h" -#include "parser/parsetree.h" /* for getrelid() */ -#include "parser/parse_expr.h" /* for exprType() */ -#include "parser/parse_oper.h" /* for oprid() and oper() */ -#include "parser/parse_coerce.h"/* for IS_BINARY_COMPATIBLE() */ +#include "optimizer/restrictinfo.h" +#include "optimizer/var.h" +#include "parser/parse_coerce.h" +#include "parser/parse_expr.h" +#include "parser/parse_oper.h" +#include "parser/parsetree.h" +#include "utils/builtins.h" #include "utils/lsyscache.h" - - -static void match_index_orclauses(RelOptInfo *rel, RelOptInfo *index, int indexkey, - int xclass, List *restrictinfo_list); -static bool match_index_to_operand(int indexkey, Expr *operand, - RelOptInfo *rel, RelOptInfo *index); -static List *match_index_orclause(RelOptInfo *rel, RelOptInfo *index, int indexkey, - int xclass, List *or_clauses, List *other_matching_indices); -static List *group_clauses_by_indexkey(RelOptInfo *rel, RelOptInfo *index, - int *indexkeys, Oid *classes, List *restrictinfo_list); -static List *group_clauses_by_ikey_for_joins(RelOptInfo *rel, RelOptInfo *index, - int *indexkeys, Oid *classes, List *join_cinfo_list, List *restr_cinfo_list); -static RestrictInfo *match_clause_to_indexkey(RelOptInfo *rel, RelOptInfo *index, int indexkey, - int xclass, RestrictInfo *restrictInfo, bool join); +#include "utils/syscache.h" + + +#define is_indexable_operator(clause,opclass,relam,indexkey_on_left) \ + (indexable_operator(clause,opclass,relam,indexkey_on_left) != InvalidOid) + +typedef enum { + Prefix_None, Prefix_Partial, Prefix_Exact +} Prefix_Status; + +static void match_index_orclauses(RelOptInfo *rel, IndexOptInfo *index, + int indexkey, Oid opclass, + List *restrictinfo_list); +static List *match_index_orclause(RelOptInfo *rel, IndexOptInfo *index, + int indexkey, Oid opclass, + List *or_clauses, + List *other_matching_indices); +static bool match_or_subclause_to_indexkey(RelOptInfo *rel, + IndexOptInfo *index, + int indexkey, Oid opclass, + Expr *clause); +static List *group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index, + int *indexkeys, Oid *classes, + List *restrictinfo_list); +static List *group_clauses_by_ikey_for_joins(RelOptInfo *rel, + IndexOptInfo *index, + int *indexkeys, Oid *classes, + List *join_cinfo_list, + List *restr_cinfo_list); +static bool match_clause_to_indexkey(RelOptInfo *rel, IndexOptInfo *index, + int indexkey, Oid opclass, + Expr *clause, bool join); static bool pred_test(List *predicate_list, List *restrictinfo_list, - List *joininfo_list); + List *joininfo_list); static bool one_pred_test(Expr *predicate, List *restrictinfo_list); static bool one_pred_clause_expr_test(Expr *predicate, Node *clause); static bool one_pred_clause_test(Expr *predicate, Node *clause); static bool clause_pred_clause_test(Expr *predicate, Node *clause); -static List *indexable_joinclauses(RelOptInfo *rel, RelOptInfo *index, - List *joininfo_list, List *restrictinfo_list); -static List *index_innerjoin(Query *root, RelOptInfo *rel, - List *clausegroup_list, RelOptInfo *index); -static List *create_index_paths(Query *root, RelOptInfo *rel, RelOptInfo *index, - List *clausegroup_list, bool join); -static List *add_index_paths(List *indexpaths, List *new_indexpaths); -static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index); - - -/* find_index_paths() - * Finds all possible index paths by determining which indices in the - * list 'indices' are usable. +static void indexable_joinclauses(RelOptInfo *rel, IndexOptInfo *index, + List *joininfo_list, List *restrictinfo_list, + List **clausegroups, List **outerrelids); +static List *index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index, + List *clausegroup_list, List *outerrelids_list); +static bool useful_for_mergejoin(RelOptInfo *rel, IndexOptInfo *index, + List *joininfo_list); +static bool useful_for_ordering(Query *root, RelOptInfo *rel, + IndexOptInfo *index); +static bool match_index_to_operand(int indexkey, Var *operand, + RelOptInfo *rel, IndexOptInfo *index); +static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel, + IndexOptInfo *index); +static bool match_special_index_operator(Expr *clause, Oid opclass, Oid relam, + bool indexkey_on_left); +static Prefix_Status like_fixed_prefix(char *patt, char **prefix); +static Prefix_Status regex_fixed_prefix(char *patt, bool case_insensitive, + char **prefix); +static List *prefix_quals(Var *leftop, Oid expr_op, + char *prefix, Prefix_Status pstatus); +static char *make_greater_string(const char * str, Oid datatype); +static Oid find_operator(const char * opname, Oid datatype); +static Datum string_to_datum(const char * str, Oid datatype); +static Const *string_to_const(const char * str, Oid datatype); +static bool string_lessthan(const char * str1, const char * str2, + Oid datatype); + + +/* + * create_index_paths() + * Generate all interesting index paths for the given relation. * - * To be usable, an index must match against either a set of - * restriction clauses or join clauses. + * 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, + * or match the query's ORDER BY condition. * - * Note that the current implementation requires that there exist - * matching clauses for every key in the index (i.e., no partial - * matches are allowed). + * There are two basic kinds of index scans. A "plain" index scan uses + * only restriction clauses (possibly none at all) in its indexqual, + * so it can be applied in any context. An "innerjoin" index scan uses + * join clauses (plus restriction clauses, if available) in its indexqual. + * Therefore it can only be used as the inner relation of a nestloop + * join against an outer rel that includes all the other rels mentioned + * in its join clauses. In that context, values for the other rels' + * attributes are available and fixed during any one scan of the indexpath. * - * If an index can't be used with restriction clauses, but its keys - * match those of the result sort order (according to information stored - * within 'sortkeys'), then the index is also considered. + * This routine's return value is a list of plain IndexPaths for each + * index the routine deems potentially interesting for the current query + * (at most one IndexPath per index on the given relation). An innerjoin + * path is also generated for each interesting combination of outer join + * relations. The innerjoin paths are *not* in the return list, but are + * appended to the "innerjoin" list of the relation itself. * - * 'rel' is the relation entry to which these index paths correspond - * 'indices' is a list of possible index paths - * 'restrictinfo_list' is a list of restriction restrictinfo nodes for 'rel' + * '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' * 'joininfo_list' is a list of joininfo nodes for 'rel' - * 'sortkeys' is a node describing the result sort order (from - * (find_sortkeys)) - * - * Returns a list of index nodes. * + * Returns a list of IndexPath access path descriptors. Additional + * IndexPath nodes may also be added to the rel->innerjoin list. */ List * -find_index_paths(Query *root, - RelOptInfo *rel, - List *indices, - List *restrictinfo_list, - List *joininfo_list) +create_index_paths(Query *root, + RelOptInfo *rel, + List *indices, + List *restrictinfo_list, + List *joininfo_list) { - List *scanclausegroups = NIL; - List *scanpaths = NIL; - RelOptInfo *index = (RelOptInfo *) NULL; - List *joinclausegroups = NIL; - List *joinpaths = NIL; List *retval = NIL; List *ilist; foreach(ilist, indices) { - index = (RelOptInfo *) lfirst(ilist); + IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist); + List *restrictclauses; + List *joinclausegroups; + List *joinouterrelids; /* - * If this is a partial index, return if it fails the predicate - * test + * If this is a partial index, we can only use it if it passes + * the predicate test. */ if (index->indpred != NIL) if (!pred_test(index->indpred, restrictinfo_list, joininfo_list)) continue; /* - * 1. Try matching the index against subclauses of an 'or' clause. - * The fields of the restrictinfo nodes are marked with lists of the - * matching indices. No path are actually created. We currently - * only look to match the first key. We don't find multi-key - * index cases where an AND matches the first key, and the OR - * matches the second key. + * 1. Try matching the index against subclauses of restriction 'or' + * clauses (ie, 'or' clauses that reference only this relation). + * The restrictinfo nodes for the 'or' clauses are marked with lists + * of the matching indices. No paths are actually created now; + * that will be done in orindxpath.c after all indexes for the rel + * have been examined. (We need to do it that way because we can + * potentially use a different index for each subclause of an 'or', + * so we can't build a path for an 'or' clause until all indexes have + * been matched against it.) + * + * We currently only look to match the first key of each index against + * 'or' subclauses. There are cases where a later key of a multi-key + * index could be used (if other top-level clauses match earlier keys + * of the index), but our poor brains are hurting already... + * + * We don't even think about special handling of 'or' clauses that + * involve more than one relation (ie, are join clauses). + * Can we do anything useful with those? */ match_index_orclauses(rel, index, @@ -140,156 +189,130 @@ find_index_paths(Query *root, restrictinfo_list); /* - * 2. If the keys of this index match any of the available - * restriction clauses, then create pathnodes corresponding to - * each group of usable clauses. + * 2. If the keys of this index match any of the available non-'or' + * restriction clauses, then create a path using those clauses + * as indexquals. */ - scanclausegroups = group_clauses_by_indexkey(rel, - index, - index->indexkeys, - index->classlist, - restrictinfo_list); - - scanpaths = NIL; - if (scanclausegroups != NIL) - scanpaths = create_index_paths(root, - rel, - index, - scanclausegroups, - false); + restrictclauses = group_clauses_by_indexkey(rel, + index, + index->indexkeys, + index->classlist, + restrictinfo_list); + + if (restrictclauses != NIL) + retval = lappend(retval, + create_index_path(root, rel, index, + restrictclauses)); /* - * 3. If this index can be used with any join clause, then create - * pathnodes for each group of usable clauses. An index can be - * used with a join clause if its ordering is useful for a - * mergejoin, or if the index can possibly be used for scanning - * the inner relation of a nestloop join. + * 3. If this index can be used for a mergejoin, then create an + * 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. 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. */ - joinclausegroups = indexable_joinclauses(rel, index, joininfo_list, restrictinfo_list); - joinpaths = NIL; - - if (joinclausegroups != NIL) + if (restrictclauses == NIL) { - List *new_join_paths = create_index_paths(root, rel, - index, - joinclausegroups, - true); - List *innerjoin_paths = index_innerjoin(root, rel, joinclausegroups, index); - - rel->innerjoin = nconc(rel->innerjoin, innerjoin_paths); - joinpaths = new_join_paths; + if (useful_for_mergejoin(rel, index, joininfo_list) || + useful_for_ordering(root, rel, index)) + retval = lappend(retval, + create_index_path(root, rel, index, NIL)); } /* - * Some sanity checks to make sure that the indexpath is valid. + * 4. Create an innerjoin index path for each combination of + * other rels used in available join clauses. These paths will + * be considered as the inner side of nestloop joins against + * those sets of other rels. indexable_joinclauses() finds sets + * of clauses that can be used with each combination of outer rels, + * and index_innerjoin builds the paths themselves. We add the + * paths to the rel's innerjoin list, NOT to the result list. */ - if (joinpaths != NULL) - retval = add_index_paths(joinpaths, retval); - if (scanpaths != NULL) - retval = add_index_paths(scanpaths, retval); + indexable_joinclauses(rel, index, + joininfo_list, restrictinfo_list, + &joinclausegroups, + &joinouterrelids); + if (joinclausegroups != NIL) + { + rel->innerjoin = nconc(rel->innerjoin, + index_innerjoin(root, rel, index, + joinclausegroups, + joinouterrelids)); + } } return retval; - } /**************************************************************************** - * ---- ROUTINES TO MATCH 'OR' CLAUSES ---- + * ---- ROUTINES TO PROCESS 'OR' CLAUSES ---- ****************************************************************************/ /* * match_index_orclauses * Attempt to match an index against subclauses within 'or' clauses. - * If the index does match, then the clause is marked with information - * about the index. + * Each subclause that does match is marked with the index's node. * - * Essentially, this adds 'index' to the list of indices in the - * RestrictInfo field of each of the clauses which it matches. + * Essentially, this adds 'index' to the list of subclause indices in + * the RestrictInfo field of each of the 'or' clauses where it matches. + * NOTE: we can use storage in the RestrictInfo for this purpose because + * this processing is only done on single-relation restriction clauses. + * Therefore, we will never have indexes for more than one relation + * mentioned in the same RestrictInfo node's list. * * 'rel' is the node of the relation on which the index is defined. * 'index' is the index node. - * 'indexkey' is the (single) key of the index + * 'indexkey' is the (single) key of the index that we will consider. * 'class' is the class of the operator corresponding to 'indexkey'. * 'restrictinfo_list' is the list of available restriction clauses. - * - * Returns nothing. - * */ static void match_index_orclauses(RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, int indexkey, - int xclass, + Oid opclass, List *restrictinfo_list) { - RestrictInfo *restrictinfo = (RestrictInfo *) NULL; - List *i = NIL; + List *i; foreach(i, restrictinfo_list) { - restrictinfo = (RestrictInfo *) lfirst(i); - if (valid_or_clause(restrictinfo)) - { + RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i); + if (restriction_is_or_clause(restrictinfo)) + { /* - * Mark the 'or' clause with a list of indices which match - * each of its subclauses. The list is generated by adding - * 'index' to the existing list where appropriate. + * Add this index to the subclause index list for each + * subclause that it matches. */ - restrictinfo->indexids = match_index_orclause(rel, index, indexkey, - xclass, + restrictinfo->subclauseindices = + match_index_orclause(rel, index, + indexkey, opclass, restrictinfo->clause->args, - restrictinfo->indexids); + restrictinfo->subclauseindices); } } } -/* match_index_to_operand() - * Generalize test for a match between an existing index's key - * and the operand on the rhs of a restriction clause. Now check - * for functional indices as well. - */ -static bool -match_index_to_operand(int indexkey, - Expr *operand, - RelOptInfo *rel, - RelOptInfo *index) -{ - bool result; - - /* - * Normal index. - */ - if (index->indproc == InvalidOid) - { - result = match_indexkey_operand(indexkey, (Var *) operand, rel); - return result; - } - - /* - * functional index check - */ - result = function_index_operand(operand, rel, index); - return result; -} - /* * match_index_orclause * Attempts to match an index against the subclauses of an 'or' clause. * * A match means that: - * (1) the operator within the subclause can be used with one - * of the index's operator classes, and - * (2) there is a usable key that matches the variable within a - * searchable clause. + * (1) the operator within the subclause can be used with the + * index's specified operator class, and + * (2) one operand of the subclause matches the index key. * - * 'or_clauses' are the remaining subclauses within the 'or' clause + * 'or_clauses' is the list of subclauses within the 'or' clause * 'other_matching_indices' is the list of information on other indices * that have already been matched to subclauses within this * particular 'or' clause (i.e., a list previously generated by - * this routine) + * this routine), or NIL if this routine has not previously been + * run for this 'or' clause. * * Returns a list of the form ((a b c) (d e f) nil (g h) ...) where * a,b,c are nodes of indices that match the first subclause in @@ -298,20 +321,22 @@ match_index_to_operand(int indexkey, */ static List * match_index_orclause(RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, int indexkey, - int xclass, + Oid opclass, List *or_clauses, List *other_matching_indices) { - Node *clause = NULL; - List *matching_indices = other_matching_indices; - List *index_list = NIL; + List *matching_indices; + List *index_list; List *clist; - /* first time through, we create index list */ + /* first time through, we create list of same length as OR clause, + * containing an empty sublist for each subclause. + */ if (!other_matching_indices) { + matching_indices = NIL; foreach(clist, or_clauses) matching_indices = lcons(NIL, matching_indices); } @@ -322,29 +347,54 @@ match_index_orclause(RelOptInfo *rel, foreach(clist, or_clauses) { - clause = lfirst(clist); - - if (is_opclause(clause) && - op_class(((Oper *) ((Expr *) clause)->oper)->opno, - xclass, index->relam) && - ((match_index_to_operand(indexkey, - (Expr *) get_leftop((Expr *) clause), - rel, - index) && - IsA(get_rightop((Expr *) clause), Const)) || - (match_index_to_operand(indexkey, - (Expr *) get_rightop((Expr *) clause), - rel, - index) && - IsA(get_leftop((Expr *) clause), Const)))) - lfirst(matching_indices) = lcons(index, lfirst(matching_indices)); + Expr *clause = lfirst(clist); + + if (match_or_subclause_to_indexkey(rel, index, indexkey, opclass, + clause)) + { + /* OK to add this index to sublist for this subclause */ + lfirst(matching_indices) = lcons(index, + lfirst(matching_indices)); + } matching_indices = lnext(matching_indices); } + return index_list; +} +/* + * See if a subclause of an OR clause matches an index. + * + * We accept the subclause if it is an operator clause that matches the + * index, or if it is an AND clause all of whose members are operators + * that match the index. (XXX Would accepting a single match be useful?) + */ +static bool +match_or_subclause_to_indexkey(RelOptInfo *rel, + IndexOptInfo *index, + int indexkey, + Oid opclass, + Expr *clause) +{ + if (and_clause((Node *) clause)) + { + List *item; + + foreach(item, clause->args) + { + if (! match_clause_to_indexkey(rel, index, indexkey, opclass, + lfirst(item), false)) + return false; + } + return true; + } + else + return match_clause_to_indexkey(rel, index, indexkey, opclass, + clause, false); } + /**************************************************************************** * ---- ROUTINES TO CHECK RESTRICTIONS ---- ****************************************************************************/ @@ -365,102 +415,99 @@ match_index_orclause(RelOptInfo *rel, /* * group_clauses_by_indexkey - * Determines whether there are clauses which will match each and every - * one of the remaining keys of an index. + * Generates a list of restriction clauses that can be used with an index. * - * 'rel' is the node of the relation corresponding to the index. - * 'indexkeys' are the remaining index keys to be matched. + * 'rel' is the node of the relation itself. + * 'index' is a index on 'rel'. + * 'indexkeys' are the index keys to be matched. * 'classes' are the classes of the index operators on those keys. - * 'clauses' is either: - * (1) the list of available restriction clauses on a single - * relation, or - * (2) a list of join clauses between 'rel' and a fixed set of - * relations, - * depending on the value of 'join'. + * 'restrictinfo_list' is the list of available restriction clauses for 'rel'. * - * NOTE: it works now for restriction clauses only. - vadim 03/18/97 + * Returns a list of all the RestrictInfo nodes for clauses that can be + * used with this index. * - * Returns all possible groups of clauses that will match (given that - * one or more clauses can match any of the remaining keys). - * E.g., if you have clauses A, B, and C, ((A B) (A C)) might be - * returned for an index with 2 keys. + * The list is ordered by index key (but as far as I can tell, this is + * an implementation artifact of this routine, and is not depended on by + * any user of the returned list --- tgl 7/99). * + * Note that in a multi-key index, we stop if we find a key that cannot be + * used with any clause. For example, given an index on (A,B,C), we might + * return (C1 C2 C3 C4) if we find that clauses C1 and C2 use column A, + * clauses C3 and C4 use column B, and no clauses use column C. But if + * no clauses match B we will return (C1 C2), whether or not there are + * clauses matching column C, because the executor couldn't use them anyway. */ static List * group_clauses_by_indexkey(RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, int *indexkeys, Oid *classes, List *restrictinfo_list) { - List *curCinfo = NIL; - RestrictInfo *matched_clause = (RestrictInfo *) NULL; - List *clausegroup = NIL; - int curIndxKey; - Oid curClass; + List *clausegroup_list = NIL; if (restrictinfo_list == NIL || indexkeys[0] == 0) return NIL; do { - List *tempgroup = NIL; - - curIndxKey = indexkeys[0]; - curClass = classes[0]; + int curIndxKey = indexkeys[0]; + Oid curClass = classes[0]; + List *clausegroup = NIL; + List *curCinfo; foreach(curCinfo, restrictinfo_list) { - RestrictInfo *temp = (RestrictInfo *) lfirst(curCinfo); - - matched_clause = match_clause_to_indexkey(rel, - index, - curIndxKey, - curClass, - temp, - false); - if (!matched_clause) - continue; - - tempgroup = lappend(tempgroup, matched_clause); + RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo); + + if (match_clause_to_indexkey(rel, + index, + curIndxKey, + curClass, + rinfo->clause, + false)) + clausegroup = lappend(clausegroup, rinfo); } - if (tempgroup == NIL) + + /* If no clauses match this key, we're done; we don't want to + * look at keys to its right. + */ + if (clausegroup == NIL) break; - clausegroup = nconc(clausegroup, tempgroup); + clausegroup_list = nconc(clausegroup_list, clausegroup); indexkeys++; classes++; } while (!DoneMatchingIndexKeys(indexkeys, index)); - /* clausegroup holds all matched clauses ordered by indexkeys */ - - if (clausegroup != NIL) - return lcons(clausegroup, NIL); - return NIL; + /* clausegroup_list holds all matched clauses ordered by indexkeys */ + return clausegroup_list; } /* * group_clauses_by_ikey_for_joins - * special edition of group_clauses_by_indexkey - will - * match join & restriction clauses. See comment in indexable_joinclauses. - * - vadim 03/18/97 + * Generates a list of join clauses that can be used with an index + * to scan the inner side of a nestloop join. * + * This is much like group_clauses_by_indexkey(), but we consider both + * join and restriction clauses. For each indexkey in the index, we + * accept both join and restriction clauses that match it, since both + * will make useful indexquals if the index is being used to scan the + * inner side of a nestloop join. But there must be at least one matching + * join clause, or we return NIL indicating that this index isn't useful + * for nestloop joining. */ static List * group_clauses_by_ikey_for_joins(RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, int *indexkeys, Oid *classes, List *join_cinfo_list, List *restr_cinfo_list) { - List *curCinfo = NIL; - RestrictInfo *matched_clause = (RestrictInfo *) NULL; - List *clausegroup = NIL; - int curIndxKey; - Oid curClass; + List *clausegroup_list = NIL; bool jfound = false; if (join_cinfo_list == NIL || indexkeys[0] == 0) @@ -468,302 +515,381 @@ group_clauses_by_ikey_for_joins(RelOptInfo *rel, do { - List *tempgroup = NIL; - - curIndxKey = indexkeys[0]; - curClass = classes[0]; + int curIndxKey = indexkeys[0]; + Oid curClass = classes[0]; + List *clausegroup = NIL; + List *curCinfo; foreach(curCinfo, join_cinfo_list) { - RestrictInfo *temp = (RestrictInfo *) lfirst(curCinfo); - - matched_clause = match_clause_to_indexkey(rel, - index, - curIndxKey, - curClass, - temp, - true); - if (!matched_clause) - continue; - - tempgroup = lappend(tempgroup, matched_clause); - jfound = true; + RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo); + + if (match_clause_to_indexkey(rel, + index, + curIndxKey, + curClass, + rinfo->clause, + true)) + { + clausegroup = lappend(clausegroup, rinfo); + jfound = true; + } } foreach(curCinfo, restr_cinfo_list) { - RestrictInfo *temp = (RestrictInfo *) lfirst(curCinfo); - - matched_clause = match_clause_to_indexkey(rel, - index, - curIndxKey, - curClass, - temp, - false); - if (!matched_clause) - continue; - - tempgroup = lappend(tempgroup, matched_clause); + RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo); + + if (match_clause_to_indexkey(rel, + index, + curIndxKey, + curClass, + rinfo->clause, + false)) + clausegroup = lappend(clausegroup, rinfo); } - if (tempgroup == NIL) + + /* If no clauses match this key, we're done; we don't want to + * look at keys to its right. + */ + if (clausegroup == NIL) break; - clausegroup = nconc(clausegroup, tempgroup); + clausegroup_list = nconc(clausegroup_list, clausegroup); indexkeys++; classes++; } while (!DoneMatchingIndexKeys(indexkeys, index)); - /* clausegroup holds all matched clauses ordered by indexkeys */ - - if (clausegroup != NIL) + /* + * if no join clause was matched then there ain't clauses for + * joins at all. + */ + if (!jfound) { - - /* - * if no one join clause was matched then there ain't clauses for - * joins at all. - */ - if (!jfound) - { - freeList(clausegroup); - return NIL; - } - return lcons(clausegroup, NIL); + freeList(clausegroup_list); + return NIL; } - return NIL; + + /* clausegroup_list holds all matched clauses ordered by indexkeys */ + return clausegroup_list; } -/* - * IndexScanableClause () MACRO - * - * Generalize condition on which we match a clause with an index. - * Now we can match with functional indices. - */ -#define IndexScanableOperand(opnd, indkeys, rel, index) \ - ((index->indproc == InvalidOid) ? \ - match_indexkey_operand(indkeys, opnd, rel) : \ - function_index_operand((Expr*)opnd,rel,index)) /* - * There was - * equal_indexkey_var(indkeys,opnd) : \ - * above, and now - * match_indexkey_operand(indkeys, opnd, rel) : \ - * - vadim 01/22/97 - */ - -/* match_clause_to_indexkey() - * Finds the first of a relation's available restriction clauses that - * matches a key of an index. + * match_clause_to_indexkey() + * Determines whether a restriction or join clause matches + * a key of an index. * - * To match, the clause must: - * (1) be in the form (op var const) if the clause is a single- - * relation clause, and - * (2) contain an operator which is in the same class as the index - * operator for this key. + * To match, the clause: + + * (1a) for a restriction clause: must be in the form (indexkey op const) + * or (const op indexkey), or + * (1b) for a join clause: must be in the form (indexkey op others) + * or (others op indexkey), where others is an expression involving + * only vars of the other relation(s); and + * (2) must contain an operator which is in the same class as the index + * operator for this key, or is a "special" operator as recognized + * by match_special_index_operator(). * - * If the clause being matched is a join clause, then 'join' is t. + * Presently, the executor can only deal with indexquals that have the + * indexkey on the left, so we can only use clauses that have the indexkey + * on the right if we can commute the clause to put the key on the left. + * We do not actually do the commuting here, but we check whether a + * suitable commutator operator is available. * - * Returns a single restrictinfo node corresponding to the matching - * clause. + * Note that in the join case, we already know that the clause as a + * whole uses vars from the interesting set of relations. But we need + * to defend against expressions like (a.f1 OP (b.f2 OP a.f3)); that's + * not processable by an indexscan nestloop join, whereas + * (a.f1 OP (b.f2 OP c.f3)) is. * - * NOTE: returns nil if clause is an or_clause. + * 'rel' is the relation of interest. + * 'index' is an index on 'rel'. + * 'indexkey' is a key of 'index'. + * 'opclass' is the corresponding operator class. + * 'clause' is the clause to be tested. + * 'join' is true if we are considering this clause for joins. * + * Returns true if the clause can be used with this index key. + * + * NOTE: returns false if clause is an OR or AND clause; to the extent + * we cope with those at all, it is done by higher-level routines. */ -static RestrictInfo * +static bool match_clause_to_indexkey(RelOptInfo *rel, - RelOptInfo *index, + IndexOptInfo *index, int indexkey, - int xclass, - RestrictInfo *restrictInfo, + Oid opclass, + Expr *clause, bool join) { - Expr *clause = restrictInfo->clause; Var *leftop, *rightop; - Oid join_op = InvalidOid; - Oid restrict_op = InvalidOid; - bool isIndexable = false; - - if (or_clause((Node *) clause) || - not_clause((Node *) clause) || single_node((Node *) clause)) - return (RestrictInfo *) NULL; + /* Clause must be a binary opclause. */ + if (! is_opclause((Node *) clause)) + return false; leftop = get_leftop(clause); rightop = get_rightop(clause); + if (! leftop || ! rightop) + return false; - /* - * If this is not a join clause, check for clauses of the form: - * (operator var/func constant) and (operator constant var/func) - */ if (!join) { + /* + * Not considering joins, so check for clauses of the form: + * (indexkey operator constant) or (constant operator indexkey). + * We will accept a Param as being constant. + */ + if ((IsA(rightop, Const) || IsA(rightop, Param)) && + match_index_to_operand(indexkey, leftop, rel, index)) + { + if (is_indexable_operator(clause, opclass, index->relam, true)) + return true; + /* + * If we didn't find a member of the index's opclass, + * see whether it is a "special" indexable operator. + */ + if (match_special_index_operator(clause, opclass, index->relam, + true)) + return true; + return false; + } + if ((IsA(leftop, Const) || IsA(leftop, Param)) && + match_index_to_operand(indexkey, rightop, rel, index)) + { + if (is_indexable_operator(clause, opclass, index->relam, false)) + return true; + /* + * If we didn't find a member of the index's opclass, + * see whether it is a "special" indexable operator. + */ + if (match_special_index_operator(clause, opclass, index->relam, + false)) + return true; + return false; + } + } + else + { /* - * Check for standard s-argable clause + * Check for an indexqual that could be handled by a nestloop join. + * We need the index key to be compared against an expression + * that uses none of the indexed relation's vars. */ - if ((rightop && IsA(rightop, Const)) || - (rightop && IsA(rightop, Param))) + if (match_index_to_operand(indexkey, leftop, rel, index)) { - restrict_op = ((Oper *) ((Expr *) clause)->oper)->opno; + List *othervarnos = pull_varnos((Node *) rightop); + bool isIndexable; - isIndexable = (op_class(restrict_op, xclass, index->relam) && - IndexScanableOperand(leftop, - indexkey, - rel, - index)); + isIndexable = ! intMember(lfirsti(rel->relids), othervarnos); + freeList(othervarnos); + if (isIndexable && + is_indexable_operator(clause, opclass, index->relam, true)) + return true; + } + else if (match_index_to_operand(indexkey, rightop, rel, index)) + { + List *othervarnos = pull_varnos((Node *) leftop); + bool isIndexable; -#ifndef IGNORE_BINARY_COMPATIBLE_INDICES + isIndexable = ! intMember(lfirsti(rel->relids), othervarnos); + freeList(othervarnos); + if (isIndexable && + is_indexable_operator(clause, opclass, index->relam, false)) + return true; + } + } - /* - * Didn't find an index? Then maybe we can find another - * binary-compatible index instead... thomas 1998-08-14 - */ - if (!isIndexable) - { - Oid ltype; - Oid rtype; + return false; +} - ltype = exprType((Node *) leftop); - rtype = exprType((Node *) rightop); +/* + * indexable_operator + * Does a binary opclause contain an operator matching the index's + * access method? + * + * If the indexkey is on the right, what we actually want to know + * is whether the operator has a commutator operator that matches + * the index's access method. + * + * We try both the straightforward match and matches that rely on + * recognizing binary-compatible datatypes. For example, if we have + * an expression like "oid = 123", the operator will be oideqint4, + * which we need to replace with oideq in order to recognize it as + * matching an oid_ops index on the oid field. + * + * Returns the OID of the matching operator, or InvalidOid if no match. + * Note that the returned OID will be different from the one in the given + * expression if we used a binary-compatible substitution. Also note that + * if indexkey_on_left is FALSE (meaning we need to commute), the returned + * OID is *not* commuted; it can be plugged directly into the given clause. + */ +Oid +indexable_operator(Expr *clause, Oid opclass, Oid relam, + bool indexkey_on_left) +{ + Oid expr_op = ((Oper *) clause->oper)->opno; + Oid commuted_op; + Oid ltype, + rtype; + + /* Get the commuted operator if necessary */ + if (indexkey_on_left) + commuted_op = expr_op; + else + commuted_op = get_commutator(expr_op); + if (commuted_op == InvalidOid) + return InvalidOid; - /* - * make sure we have two different binary-compatible - * types... - */ - if ((ltype != rtype) - && IS_BINARY_COMPATIBLE(ltype, rtype)) - { - char *opname; - Operator newop; - - opname = get_opname(restrict_op); - if (opname != NULL) - newop = oper(opname, ltype, ltype, TRUE); - else - newop = NULL; - - /* actually have a different operator to try? */ - if (HeapTupleIsValid(newop) && (oprid(newop) != restrict_op)) - { - restrict_op = oprid(newop); - - isIndexable = (op_class(restrict_op, xclass, index->relam) && - IndexScanableOperand(leftop, - indexkey, - rel, - index)); - - if (isIndexable) - ((Oper *) ((Expr *) clause)->oper)->opno = restrict_op; - } - } - } -#endif - } + /* Done if the (commuted) operator is a member of the index's AM */ + if (op_class(commuted_op, opclass, relam)) + return expr_op; - /* - * Must try to commute the clause to standard s-arg format. - */ - else if ((leftop && IsA(leftop, Const)) || - (leftop && IsA(leftop, Param))) - { - restrict_op = get_commutator(((Oper *) ((Expr *) clause)->oper)->opno); + /* + * Maybe the index uses a binary-compatible operator set. + */ + ltype = exprType((Node *) get_leftop(clause)); + rtype = exprType((Node *) get_rightop(clause)); - isIndexable = ((restrict_op != InvalidOid) && - op_class(restrict_op, xclass, index->relam) && - IndexScanableOperand(rightop, - indexkey, rel, index)); + /* + * make sure we have two different binary-compatible types... + */ + if (ltype != rtype && IS_BINARY_COMPATIBLE(ltype, rtype)) + { + char *opname = get_opname(expr_op); + Operator newop; -#ifndef IGNORE_BINARY_COMPATIBLE_INDICES - if (!isIndexable) - { - Oid ltype; - Oid rtype; - - ltype = exprType((Node *) leftop); - rtype = exprType((Node *) rightop); - - if ((ltype != rtype) - && IS_BINARY_COMPATIBLE(ltype, rtype)) - { - char *opname; - Operator newop; - - restrict_op = ((Oper *) ((Expr *) clause)->oper)->opno; - - opname = get_opname(restrict_op); - if (opname != NULL) - newop = oper(opname, rtype, rtype, TRUE); - else - newop = NULL; - - if (HeapTupleIsValid(newop) && (oprid(newop) != restrict_op)) - { - restrict_op = get_commutator(oprid(newop)); - - isIndexable = ((restrict_op != InvalidOid) && - op_class(restrict_op, xclass, index->relam) && - IndexScanableOperand(rightop, - indexkey, - rel, - index)); - - if (isIndexable) - ((Oper *) ((Expr *) clause)->oper)->opno = oprid(newop); - } - } - } -#endif + if (opname == NULL) + return InvalidOid; /* probably shouldn't happen */ - if (isIndexable) - { + /* Use the datatype of the index key */ + if (indexkey_on_left) + newop = oper(opname, ltype, ltype, TRUE); + else + newop = oper(opname, rtype, rtype, TRUE); + if (HeapTupleIsValid(newop)) + { + Oid new_expr_op = oprid(newop); + + if (new_expr_op != expr_op) + { /* - * In place list modification. (op const var/func) -> (op - * var/func const) + * OK, we found a binary-compatible operator of the same name; + * now does it match the index? */ - CommuteClause((Node *) clause); + if (indexkey_on_left) + commuted_op = new_expr_op; + else + commuted_op = get_commutator(new_expr_op); + if (commuted_op == InvalidOid) + return InvalidOid; + + if (op_class(commuted_op, opclass, relam)) + return new_expr_op; } } } - /* - * Check for an indexable scan on one of the join relations. clause is - * of the form (operator var/func var/func) - */ - else - { - if (rightop - && match_index_to_operand(indexkey, (Expr *) rightop, rel, index)) - { + return InvalidOid; +} - join_op = get_commutator(((Oper *) ((Expr *) clause)->oper)->opno); +/* + * 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, + IndexOptInfo *index, + List *joininfo_list) +{ + int *indexkeys = index->indexkeys; + Oid *ordering = index->ordering; + List *i; - } - else if (leftop - && match_index_to_operand(indexkey, - (Expr *) leftop, rel, index)) - join_op = ((Oper *) ((Expr *) clause)->oper)->opno; + 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; - if (join_op && op_class(join_op, xclass, index->relam) && - is_joinable((Node *) clause)) + foreach(j, joininfo->jinfo_restrictinfo) { - isIndexable = true; + RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j); - /* - * If we're using the operand's commutator we must commute the - * clause. - */ - if (join_op != ((Oper *) ((Expr *) clause)->oper)->opno) - CommuteClause((Node *) clause); + 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, + IndexOptInfo *index) +{ + List *index_pathkeys; - if (isIndexable) - return restrictInfo; + if (root->query_pathkeys == NIL) + return false; /* no special ordering requested */ - return NULL; + 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; } /**************************************************************************** @@ -968,7 +1094,8 @@ one_pred_clause_test(Expr *predicate, Node *clause) * this test should always be considered false. */ -StrategyNumber BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = { +static StrategyNumber +BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = { {2, 2, 0, 0, 0}, {1, 2, 0, 0, 0}, {1, 2, 3, 4, 5}, @@ -1009,7 +1136,7 @@ clause_pred_clause_test(Expr *predicate, Node *clause) HeapScanDesc scan; HeapTuple tuple; ScanKeyData entry[3]; - Form_pg_amop form; + Form_pg_amop aform; pred_var = (Var *) get_leftop(predicate); pred_const = (Const *) get_rightop(predicate); @@ -1019,6 +1146,7 @@ clause_pred_clause_test(Expr *predicate, Node *clause) /* Check the basic form; for now, only allow the simplest case */ if (!is_opclause(clause) || !IsA(clause_var, Var) || + clause_const == NULL || !IsA(clause_const, Const) || !IsA(predicate->oper, Oper) || !IsA(pred_var, Var) || @@ -1050,7 +1178,7 @@ clause_pred_clause_test(Expr *predicate, Node *clause) F_OIDEQ, ObjectIdGetDatum(pred_op)); - relation = heap_openr(AccessMethodOperatorRelationName); + relation = heap_openr(AccessMethodOperatorRelationName, AccessShareLock); /* * The following assumes that any given operator will only be in a @@ -1065,15 +1193,17 @@ clause_pred_clause_test(Expr *predicate, Node *clause) if (!HeapTupleIsValid(tuple)) { elog(DEBUG, "clause_pred_clause_test: unknown pred_op"); + heap_endscan(scan); + heap_close(relation, AccessShareLock); return false; } - form = (Form_pg_amop) GETSTRUCT(tuple); + aform = (Form_pg_amop) GETSTRUCT(tuple); /* Get the predicate operator's strategy number (1 to 5) */ - pred_strategy = (StrategyNumber) form->amopstrategy; + pred_strategy = (StrategyNumber) aform->amopstrategy; /* Remember which operator class this strategy number came from */ - opclass_id = form->amopclaid; + opclass_id = aform->amopclaid; heap_endscan(scan); @@ -1096,12 +1226,14 @@ clause_pred_clause_test(Expr *predicate, Node *clause) if (!HeapTupleIsValid(tuple)) { elog(DEBUG, "clause_pred_clause_test: unknown clause_op"); + heap_endscan(scan); + heap_close(relation, AccessShareLock); return false; } - form = (Form_pg_amop) GETSTRUCT(tuple); + aform = (Form_pg_amop) GETSTRUCT(tuple); /* Get the restriction clause operator's strategy number (1 to 5) */ - clause_strategy = (StrategyNumber) form->amopstrategy; + clause_strategy = (StrategyNumber) aform->amopstrategy; heap_endscan(scan); @@ -1111,8 +1243,10 @@ clause_pred_clause_test(Expr *predicate, Node *clause) test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1]; if (test_strategy == 0) + { + heap_close(relation, AccessShareLock); return false; /* the implication cannot be determined */ - + } /* * 4. From the same opclass, find the operator for the test strategy @@ -1128,14 +1262,18 @@ clause_pred_clause_test(Expr *predicate, Node *clause) if (!HeapTupleIsValid(tuple)) { elog(DEBUG, "clause_pred_clause_test: unknown test_op"); + heap_endscan(scan); + heap_close(relation, AccessShareLock); return false; } - form = (Form_pg_amop) GETSTRUCT(tuple); + aform = (Form_pg_amop) GETSTRUCT(tuple); /* Get the test operator */ - test_op = form->amopopr; + test_op = aform->amopopr; + heap_endscan(scan); + heap_close(relation, AccessShareLock); /* * 5. Evaluate the test @@ -1170,229 +1308,160 @@ clause_pred_clause_test(Expr *predicate, Node *clause) /* * indexable_joinclauses * Finds all groups of join clauses from among 'joininfo_list' that can - * be used in conjunction with 'index'. + * be used in conjunction with 'index' for the inner scan of a nestjoin. * - * The first clause in the group is marked as having the other relation - * in the join clause as its outer join relation. + * Each clause group comes from a single joininfo node plus the current + * rel's restrictinfo list. Therefore, every clause in the group references + * the current rel plus the same set of other rels (except for the restrict + * clauses, which only reference the current rel). Therefore, this set + * of clauses could be used as an indexqual if the relation is scanned + * as the inner side of a nestloop join when the outer side contains + * (at least) all those "other rels". * - * Returns a list of these clause groups. + * XXX Actually, given that we are considering a join that requires an + * outer rel set (A,B,C), we should use all qual clauses that reference + * any subset of these rels, not just the full set or none. This is + * doable with a doubly nested loop over joininfo_list; is it worth it? * - * Added: restrictinfo_list - list of restriction RestrictInfos. It's to - * support multi-column indices in joins and for cases - * when a key is in both join & restriction clauses. - vadim 03/18/97 + * Returns two parallel lists of the same length: the clause groups, + * and the required outer rel set for each one. * + * 'rel' is the relation for which 'index' is defined + * 'joininfo_list' is the list of JoinInfo nodes for 'rel' + * 'restrictinfo_list' is the list of restriction clauses for 'rel' + * '*clausegroups' receives a list of clause sublists + * '*outerrelids' receives a list of relid lists */ -static List * -indexable_joinclauses(RelOptInfo *rel, RelOptInfo *index, - List *joininfo_list, List *restrictinfo_list) +static void +indexable_joinclauses(RelOptInfo *rel, IndexOptInfo *index, + List *joininfo_list, List *restrictinfo_list, + List **clausegroups, List **outerrelids) { - JoinInfo *joininfo = (JoinInfo *) NULL; List *cg_list = NIL; - List *i = NIL; - List *clausegroups = NIL; + List *relid_list = NIL; + List *i; foreach(i, joininfo_list) { - joininfo = (JoinInfo *) lfirst(i); - - if (joininfo->jinfo_restrictinfo == NIL) - continue; - clausegroups = group_clauses_by_ikey_for_joins(rel, - index, - index->indexkeys, - index->classlist, + JoinInfo *joininfo = (JoinInfo *) lfirst(i); + List *clausegroup; + + clausegroup = group_clauses_by_ikey_for_joins(rel, + index, + index->indexkeys, + index->classlist, joininfo->jinfo_restrictinfo, - restrictinfo_list); + restrictinfo_list); - if (clausegroups != NIL) + if (clausegroup != NIL) { - List *clauses = lfirst(clausegroups); - - ((RestrictInfo *) lfirst(clauses))->restrictinfojoinid = joininfo->otherrels; + cg_list = lappend(cg_list, clausegroup); + relid_list = lappend(relid_list, joininfo->unjoined_relids); } - cg_list = nconc(cg_list, clausegroups); } - return cg_list; + + *clausegroups = cg_list; + *outerrelids = relid_list; } /**************************************************************************** * ---- PATH CREATION UTILITIES ---- ****************************************************************************/ -/* - * extract_restrict_clauses - - * the list of clause info contains join clauses and restriction clauses. - * This routine returns the restriction clauses only. - */ -#ifdef NOT_USED -static List * -extract_restrict_clauses(List *clausegroup) -{ - List *restrict_cls = NIL; - List *l; - - foreach(l, clausegroup) - { - RestrictInfo *cinfo = lfirst(l); - - if (!is_joinable((Node *) cinfo->clause)) - restrict_cls = lappend(restrict_cls, cinfo); - } - return restrict_cls; -} - -#endif - /* * index_innerjoin * Creates index path nodes corresponding to paths to be used as inner * relations in nestloop joins. * - * 'clausegroup-list' is a list of list of restrictinfo nodes which can use - * 'index' on their inner relation. + * 'rel' is the relation for which 'index' is defined + * 'clausegroup_list' is a list of lists of restrictinfo nodes which can use + * 'index'. Each sublist refers to the same set of outer rels. + * 'outerrelids_list' is a list of the required outer rels for each sublist + * of join clauses. * * Returns a list of index pathnodes. - * */ static List * -index_innerjoin(Query *root, RelOptInfo *rel, List *clausegroup_list, - RelOptInfo *index) +index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index, + List *clausegroup_list, List *outerrelids_list) { - List *clausegroup = NIL; - List *cg_list = NIL; - List *i = NIL; - IndexPath *pathnode = (IndexPath *) NULL; - Cost temp_selec; - float temp_pages; + List *path_list = NIL; + List *i; foreach(i, clausegroup_list) { - List *attnos, - *values, - *flags; - - clausegroup = lfirst(i); - pathnode = makeNode(IndexPath); - - get_joinvars(lfirsti(rel->relids), clausegroup, - &attnos, &values, &flags); - index_selectivity(lfirsti(index->relids), - index->classlist, - get_opnos(clausegroup), - getrelid(lfirsti(rel->relids), - root->rtable), - attnos, - values, - flags, - length(clausegroup), - &temp_pages, - &temp_selec); + List *clausegroup = lfirst(i); + IndexPath *pathnode = makeNode(IndexPath); + List *indexquals; + + /* XXX this code ought to be merged with create_index_path? */ pathnode->path.pathtype = T_IndexScan; pathnode->path.parent = rel; - pathnode->path.pathorder = makeNode(PathOrder); - pathnode->path.pathorder->ordtype = SORTOP_ORDER; - pathnode->path.pathorder->ord.sortop = index->ordering; - pathnode->path.pathkeys = NIL; - - pathnode->indexid = index->relids; - pathnode->indexkeys = index->indexkeys; - pathnode->indexqual = clausegroup; - - pathnode->path.joinid = ((RestrictInfo *) lfirst(clausegroup))->restrictinfojoinid; - - pathnode->path.path_cost = cost_index((Oid) lfirsti(index->relids), - (int) temp_pages, - temp_selec, - rel->pages, - rel->tuples, - index->pages, - index->tuples, - true); + pathnode->path.pathkeys = build_index_pathkeys(root, rel, index); - /* - * copy restrictinfo list into path for expensive function - * processing -- JMH, 7/7/92 + indexquals = get_actual_clauses(clausegroup); + /* expand special operators to indexquals the executor can handle */ + indexquals = expand_indexqual_conditions(indexquals); + + /* Note that we are making a pathnode for a single-scan indexscan; + * therefore, both indexid and indexqual should be single-element + * lists. */ - pathnode->path.loc_restrictinfo = set_difference(copyObject((Node *) rel->restrictinfo), - clausegroup); + pathnode->indexid = lconsi(index->indexoid, NIL); + pathnode->indexqual = lcons(indexquals, NIL); -#if 0 /* fix xfunc */ - /* add in cost for expensive functions! -- JMH, 7/7/92 */ - if (XfuncMode != XFUNC_OFF) - { - ((Path *) pathnode)->path_cost += xfunc_get_path_cost((Path *) pathnode); - } -#endif - cg_list = lappend(cg_list, pathnode); + /* joinrelids saves the rels needed on the outer side of the join */ + pathnode->joinrelids = lfirst(outerrelids_list); + + pathnode->path.path_cost = cost_index(root, rel, index, indexquals, + true); + + path_list = lappend(path_list, pathnode); + outerrelids_list = lnext(outerrelids_list); } - return cg_list; + return path_list; } +/**************************************************************************** + * ---- ROUTINES TO CHECK OPERANDS ---- + ****************************************************************************/ + /* - * create_index_paths - * Creates a list of index path nodes for each group of clauses - * (restriction or join) that can be used in conjunction with an index. - * - * 'rel' is the relation for which 'index' is defined - * 'clausegroup-list' is the list of clause groups (lists of restrictinfo - * nodes) grouped by mergejoinorder - * 'join' is a flag indicating whether or not the clauses are join - * clauses - * - * Returns a list of new index path nodes. - * + * match_index_to_operand() + * Generalized test for a match between an index's key + * and the operand on one side of a restriction or join clause. + * Now check for functional indices as well. */ -static List * -create_index_paths(Query *root, - RelOptInfo *rel, - RelOptInfo *index, - List *clausegroup_list, - bool join) +static bool +match_index_to_operand(int indexkey, + Var *operand, + RelOptInfo *rel, + IndexOptInfo *index) { - List *clausegroup = NIL; - List *ip_list = NIL; - List *i = NIL; - List *j = NIL; - IndexPath *temp_path; - - foreach(i, clausegroup_list) + if (index->indproc == InvalidOid) { - RestrictInfo *restrictinfo; - List *temp_node = NIL; - bool temp = true; - - clausegroup = lfirst(i); - - foreach(j, clausegroup) - { - restrictinfo = (RestrictInfo *) lfirst(j); - if (!(is_joinable((Node *) restrictinfo->clause) && - equal_path_merge_ordering(index->ordering, - restrictinfo->mergejoinorder))) - temp = false; - } - - if (!join || temp) - { /* restriction, ordering scan */ - temp_path = create_index_path(root, rel, index, clausegroup, join); - temp_node = lcons(temp_path, NIL); - ip_list = nconc(ip_list, temp_node); - } + /* + * Normal index. + */ + if (IsA(operand, Var) && + lfirsti(rel->relids) == operand->varno && + indexkey == operand->varattno) + return true; + else + return false; } - return ip_list; -} -static List * -add_index_paths(List *indexpaths, List *new_indexpaths) -{ - return append(indexpaths, new_indexpaths); + /* + * functional index check + */ + return function_index_operand((Expr *) operand, rel, index); } static bool -function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index) +function_index_operand(Expr *funcOpnd, RelOptInfo *rel, IndexOptInfo *index) { - Oid heapRelid = (Oid) lfirsti(rel->relids); + int relvarno = lfirsti(rel->relids); Func *function; List *funcargs; int *indexKeys = index->indexkeys; @@ -1402,8 +1471,8 @@ function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index) /* * sanity check, make sure we know what we're dealing with here. */ - if (funcOpnd == NULL || - nodeTag(funcOpnd) != T_Expr || funcOpnd->opType != FUNC_EXPR || + if (funcOpnd == NULL || ! IsA(funcOpnd, Expr) || + funcOpnd->opType != FUNC_EXPR || funcOpnd->oper == NULL || indexKeys == NULL) return false; @@ -1416,35 +1485,645 @@ function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index) /* * Check that the arguments correspond to the same arguments used to * create the functional index. To do this we must check that 1. - * refer to the right relatiion. 2. the args have the right attr. + * refer to the right relation. 2. the args have the right attr. * numbers in the right order. - * - * - * Check all args refer to the correct relation (i.e. the one with the - * functional index defined on it (rel). To do this we can simply - * compare range table entry numbers, they must be the same. */ + i = 0; foreach(arg, funcargs) { - if (heapRelid != ((Var *) lfirst(arg))->varno) + Var *var = (Var *) lfirst(arg); + + if (! IsA(var, Var)) + return false; + if (indexKeys[i] == 0) return false; + if (var->varno != relvarno || var->varattno != indexKeys[i]) + return false; + + i++; + } + + if (indexKeys[i] != 0) + return false; /* not enough arguments */ + + return true; +} + +/**************************************************************************** + * ---- ROUTINES FOR "SPECIAL" INDEXABLE OPERATORS ---- + ****************************************************************************/ + +/*---------- + * These routines handle special optimization of operators that can be + * used with index scans even though they are not known to the executor's + * indexscan machinery. The key idea is that these operators allow us + * to derive approximate indexscan qual clauses, such that any tuples + * that pass the operator clause itself must also satisfy the simpler + * indexscan condition(s). Then we can use the indexscan machinery + * to avoid scanning as much of the table as we'd otherwise have to, + * while applying the original operator as a qpqual condition to ensure + * we deliver only the tuples we want. (In essence, we're using a regular + * index as if it were a lossy index.) + * + * An example of what we're doing is + * textfield LIKE 'abc%' + * from which we can generate the indexscanable conditions + * textfield >= 'abc' AND textfield < 'abd' + * which allow efficient scanning of an index on textfield. + * (In reality, character set and collation issues make the transformation + * from LIKE to indexscan limits rather harder than one might think ... + * but that's the basic idea.) + * + * Two routines are provided here, match_special_index_operator() and + * expand_indexqual_conditions(). match_special_index_operator() is + * just an auxiliary function for match_clause_to_indexkey(); after + * the latter fails to recognize a restriction opclause's operator + * as a member of an index's opclass, it asks match_special_index_operator() + * whether the clause should be considered an indexqual anyway. + * expand_indexqual_conditions() converts a list of "raw" indexqual + * conditions (with implicit AND semantics across list elements) into + * a list that the executor can actually handle. For operators that + * are members of the index's opclass this transformation is a no-op, + * but operators recognized by match_special_index_operator() must be + * converted into one or more "regular" indexqual conditions. + *---------- + */ + +/* + * match_special_index_operator + * Recognize restriction clauses that can be used to generate + * additional indexscanable qualifications. + * + * The given clause is already known to be a binary opclause having + * the form (indexkey OP const/param) or (const/param OP indexkey), + * but the OP proved not to be one of the index's opclass operators. + * Return 'true' if we can do something with it anyway. + */ +static bool +match_special_index_operator(Expr *clause, Oid opclass, Oid relam, + bool indexkey_on_left) +{ + bool isIndexable = false; + Var *leftop, + *rightop; + Oid expr_op; + Datum constvalue; + char *patt; + char *prefix; + + /* Currently, all known special operators require the indexkey + * on the left, but this test could be pushed into the switch statement + * if some are added that do not... + */ + if (! indexkey_on_left) + return false; + + /* we know these will succeed */ + leftop = get_leftop(clause); + rightop = get_rightop(clause); + expr_op = ((Oper *) clause->oper)->opno; + + /* again, required for all current special ops: */ + if (! IsA(rightop, Const) || + ((Const *) rightop)->constisnull) + return false; + constvalue = ((Const *) rightop)->constvalue; + + switch (expr_op) + { + case OID_TEXT_LIKE_OP: + case OID_BPCHAR_LIKE_OP: + case OID_VARCHAR_LIKE_OP: + case OID_NAME_LIKE_OP: + /* the right-hand const is type text for all of these */ + patt = textout((text *) DatumGetPointer(constvalue)); + isIndexable = like_fixed_prefix(patt, &prefix) != Prefix_None; + if (prefix) pfree(prefix); + pfree(patt); + break; + + case OID_TEXT_REGEXEQ_OP: + case OID_BPCHAR_REGEXEQ_OP: + case OID_VARCHAR_REGEXEQ_OP: + case OID_NAME_REGEXEQ_OP: + /* the right-hand const is type text for all of these */ + patt = textout((text *) DatumGetPointer(constvalue)); + isIndexable = regex_fixed_prefix(patt, false, &prefix) != Prefix_None; + if (prefix) pfree(prefix); + pfree(patt); + break; + + case OID_TEXT_ICREGEXEQ_OP: + case OID_BPCHAR_ICREGEXEQ_OP: + case OID_VARCHAR_ICREGEXEQ_OP: + case OID_NAME_ICREGEXEQ_OP: + /* the right-hand const is type text for all of these */ + patt = textout((text *) DatumGetPointer(constvalue)); + isIndexable = regex_fixed_prefix(patt, true, &prefix) != Prefix_None; + if (prefix) pfree(prefix); + pfree(patt); + break; } + /* done if the expression doesn't look indexable */ + if (! isIndexable) + return false; + /* - * check attr numbers and order. + * Must also check that index's opclass supports the operators we will + * want to apply. (A hash index, for example, will not support ">=".) + * We cheat a little by not checking for availability of "=" ... any + * index type should support "=", methinks. */ - i = 0; - foreach(arg, funcargs) + switch (expr_op) { + case OID_TEXT_LIKE_OP: + case OID_TEXT_REGEXEQ_OP: + case OID_TEXT_ICREGEXEQ_OP: + if (! op_class(find_operator(">=", TEXTOID), opclass, relam) || + ! op_class(find_operator("<", TEXTOID), opclass, relam)) + isIndexable = false; + break; - if (indexKeys[i] == 0) - return false; + case OID_BPCHAR_LIKE_OP: + case OID_BPCHAR_REGEXEQ_OP: + case OID_BPCHAR_ICREGEXEQ_OP: + if (! op_class(find_operator(">=", BPCHAROID), opclass, relam) || + ! op_class(find_operator("<", BPCHAROID), opclass, relam)) + isIndexable = false; + break; - if (((Var *) lfirst(arg))->varattno != indexKeys[i]) - return false; + case OID_VARCHAR_LIKE_OP: + case OID_VARCHAR_REGEXEQ_OP: + case OID_VARCHAR_ICREGEXEQ_OP: + if (! op_class(find_operator(">=", VARCHAROID), opclass, relam) || + ! op_class(find_operator("<", VARCHAROID), opclass, relam)) + isIndexable = false; + break; - i++; + case OID_NAME_LIKE_OP: + case OID_NAME_REGEXEQ_OP: + case OID_NAME_ICREGEXEQ_OP: + if (! op_class(find_operator(">=", NAMEOID), opclass, relam) || + ! op_class(find_operator("<", NAMEOID), opclass, relam)) + isIndexable = false; + break; } - return true; + return isIndexable; +} + +/* + * expand_indexqual_conditions + * Given a list of (implicitly ANDed) indexqual clauses, + * expand any "special" index operators into clauses that the indexscan + * machinery will know what to do with. Clauses that were not + * recognized by match_special_index_operator() must be passed through + * unchanged. + */ +List * +expand_indexqual_conditions(List *indexquals) +{ + List *resultquals = NIL; + List *q; + + foreach(q, indexquals) + { + Expr *clause = (Expr *) lfirst(q); + /* we know these will succeed */ + Var *leftop = get_leftop(clause); + Var *rightop = get_rightop(clause); + Oid expr_op = ((Oper *) clause->oper)->opno; + Datum constvalue; + char *patt; + char *prefix; + Prefix_Status pstatus; + + switch (expr_op) + { + /* + * LIKE and regex operators are not members of any index opclass, + * so if we find one in an indexqual list we can assume that + * it was accepted by match_special_index_operator(). + */ + case OID_TEXT_LIKE_OP: + case OID_BPCHAR_LIKE_OP: + case OID_VARCHAR_LIKE_OP: + case OID_NAME_LIKE_OP: + /* the right-hand const is type text for all of these */ + constvalue = ((Const *) rightop)->constvalue; + patt = textout((text *) DatumGetPointer(constvalue)); + pstatus = like_fixed_prefix(patt, &prefix); + resultquals = nconc(resultquals, + prefix_quals(leftop, expr_op, + prefix, pstatus)); + if (prefix) pfree(prefix); + pfree(patt); + break; + + case OID_TEXT_REGEXEQ_OP: + case OID_BPCHAR_REGEXEQ_OP: + case OID_VARCHAR_REGEXEQ_OP: + case OID_NAME_REGEXEQ_OP: + /* the right-hand const is type text for all of these */ + constvalue = ((Const *) rightop)->constvalue; + patt = textout((text *) DatumGetPointer(constvalue)); + pstatus = regex_fixed_prefix(patt, false, &prefix); + resultquals = nconc(resultquals, + prefix_quals(leftop, expr_op, + prefix, pstatus)); + if (prefix) pfree(prefix); + pfree(patt); + break; + + case OID_TEXT_ICREGEXEQ_OP: + case OID_BPCHAR_ICREGEXEQ_OP: + case OID_VARCHAR_ICREGEXEQ_OP: + case OID_NAME_ICREGEXEQ_OP: + /* the right-hand const is type text for all of these */ + constvalue = ((Const *) rightop)->constvalue; + patt = textout((text *) DatumGetPointer(constvalue)); + pstatus = regex_fixed_prefix(patt, true, &prefix); + resultquals = nconc(resultquals, + prefix_quals(leftop, expr_op, + prefix, pstatus)); + if (prefix) pfree(prefix); + pfree(patt); + break; + + default: + resultquals = lappend(resultquals, clause); + break; + } + } + + return resultquals; +} + +/* + * Extract the fixed prefix, if any, for a LIKE pattern. + * *prefix is set to a palloc'd prefix string, + * or to NULL if no fixed prefix exists for the pattern. + * The return value distinguishes no fixed prefix, a partial prefix, + * or an exact-match-only pattern. + */ +static Prefix_Status +like_fixed_prefix(char *patt, char **prefix) +{ + char *match; + int pos, + match_pos; + + *prefix = match = palloc(strlen(patt)+1); + match_pos = 0; + + for (pos = 0; patt[pos]; pos++) + { + /* % and _ are wildcard characters in LIKE */ + if (patt[pos] == '%' || + patt[pos] == '_') + break; + /* Backslash quotes the next character */ + if (patt[pos] == '\\') + { + pos++; + if (patt[pos] == '\0') + break; + } + /* + * NOTE: this code used to think that %% meant a literal %, + * but textlike() itself does not think that, and the SQL92 + * spec doesn't say any such thing either. + */ + match[match_pos++] = patt[pos]; + } + + match[match_pos] = '\0'; + + /* in LIKE, an empty pattern is an exact match! */ + if (patt[pos] == '\0') + return Prefix_Exact; /* reached end of pattern, so exact */ + + if (match_pos > 0) + return Prefix_Partial; + return Prefix_None; +} + +/* + * Extract the fixed prefix, if any, for a regex pattern. + * *prefix is set to a palloc'd prefix string, + * or to NULL if no fixed prefix exists for the pattern. + * The return value distinguishes no fixed prefix, a partial prefix, + * or an exact-match-only pattern. + */ +static Prefix_Status +regex_fixed_prefix(char *patt, bool case_insensitive, + char **prefix) +{ + char *match; + int pos, + match_pos; + + *prefix = NULL; + + /* Pattern must be anchored left */ + if (patt[0] != '^') + return Prefix_None; + + /* Cannot optimize if unquoted | { } is present in pattern */ + for (pos = 1; patt[pos]; pos++) + { + if (patt[pos] == '|' || + patt[pos] == '{' || + patt[pos] == '}') + return Prefix_None; + if (patt[pos] == '\\') + { + pos++; + if (patt[pos] == '\0') + break; + } + } + + /* OK, allocate space for pattern */ + *prefix = match = palloc(strlen(patt)+1); + match_pos = 0; + + /* note start at pos 1 to skip leading ^ */ + for (pos = 1; patt[pos]; pos++) + { + if (patt[pos] == '.' || + patt[pos] == '?' || + patt[pos] == '*' || + patt[pos] == '[' || + patt[pos] == '$' || + /* XXX I suspect isalpha() is not an adequately locale-sensitive + * test for characters that can vary under case folding? + */ + (case_insensitive && isalpha(patt[pos]))) + break; + if (patt[pos] == '\\') + { + pos++; + if (patt[pos] == '\0') + break; + } + match[match_pos++] = patt[pos]; + } + + match[match_pos] = '\0'; + + if (patt[pos] == '$' && patt[pos+1] == '\0') + return Prefix_Exact; /* pattern specifies exact match */ + + if (match_pos > 0) + return Prefix_Partial; + return Prefix_None; +} + +/* + * Given a fixed prefix that all the "leftop" values must have, + * generate suitable indexqual condition(s). expr_op is the original + * LIKE or regex operator; we use it to deduce the appropriate comparison + * operators. + */ +static List * +prefix_quals(Var *leftop, Oid expr_op, + char *prefix, Prefix_Status pstatus) +{ + List *result; + Oid datatype; + Oid oproid; + Const *con; + Oper *op; + Expr *expr; + char *greaterstr; + + Assert(pstatus != Prefix_None); + + switch (expr_op) + { + case OID_TEXT_LIKE_OP: + case OID_TEXT_REGEXEQ_OP: + case OID_TEXT_ICREGEXEQ_OP: + datatype = TEXTOID; + break; + + case OID_BPCHAR_LIKE_OP: + case OID_BPCHAR_REGEXEQ_OP: + case OID_BPCHAR_ICREGEXEQ_OP: + datatype = BPCHAROID; + break; + + case OID_VARCHAR_LIKE_OP: + case OID_VARCHAR_REGEXEQ_OP: + case OID_VARCHAR_ICREGEXEQ_OP: + datatype = VARCHAROID; + break; + + case OID_NAME_LIKE_OP: + case OID_NAME_REGEXEQ_OP: + case OID_NAME_ICREGEXEQ_OP: + datatype = NAMEOID; + break; + + default: + elog(ERROR, "prefix_quals: unexpected operator %u", expr_op); + return NIL; + } + + /* + * If we found an exact-match pattern, generate an "=" indexqual. + */ + if (pstatus == Prefix_Exact) + { + oproid = find_operator("=", datatype); + if (oproid == InvalidOid) + elog(ERROR, "prefix_quals: no = operator for type %u", datatype); + con = string_to_const(prefix, datatype); + op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL); + expr = make_opclause(op, leftop, (Var *) con); + result = lcons(expr, NIL); + return result; + } + + /* + * Otherwise, we have a nonempty required prefix of the values. + * + * We can always say "x >= prefix". + */ + oproid = find_operator(">=", datatype); + if (oproid == InvalidOid) + elog(ERROR, "prefix_quals: no >= operator for type %u", datatype); + con = string_to_const(prefix, datatype); + op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL); + expr = make_opclause(op, leftop, (Var *) con); + result = lcons(expr, NIL); + + /* + * If we can create a string larger than the prefix, say "x < greaterstr". + */ + greaterstr = make_greater_string(prefix, datatype); + if (greaterstr) + { + oproid = find_operator("<", datatype); + if (oproid == InvalidOid) + elog(ERROR, "prefix_quals: no < operator for type %u", datatype); + con = string_to_const(greaterstr, datatype); + op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL); + expr = make_opclause(op, leftop, (Var *) con); + result = lappend(result, expr); + pfree(greaterstr); + } + + return result; +} + +/* + * Try to generate a string greater than the given string or any string it is + * a prefix of. If successful, return a palloc'd string; else return NULL. + * + * To work correctly in non-ASCII locales with weird collation orders, + * we cannot simply increment "foo" to "fop" --- we have to check whether + * we actually produced a string greater than the given one. If not, + * increment the righthand byte again and repeat. If we max out the righthand + * byte, truncate off the last character and start incrementing the next. + * For example, if "z" were the last character in the sort order, then we + * could produce "foo" as a string greater than "fonz". + * + * This could be rather slow in the worst case, but in most cases we won't + * have to try more than one or two strings before succeeding. + * + * XXX in a sufficiently weird locale, this might produce incorrect results? + * For example, in German I believe "ss" is treated specially --- if we are + * given "foos" and return "foot", will this actually be greater than "fooss"? + */ +static char * +make_greater_string(const char * str, Oid datatype) +{ + char *workstr; + int len; + + /* Make a modifiable copy, which will be our return value if successful */ + workstr = pstrdup((char *) str); + + while ((len = strlen(workstr)) > 0) + { + unsigned char *lastchar = (unsigned char *) (workstr + len - 1); + + /* + * Try to generate a larger string by incrementing the last byte. + */ + while (*lastchar < (unsigned char) 255) + { + (*lastchar)++; + if (string_lessthan(str, workstr, datatype)) + return workstr; /* Success! */ + } + /* + * Truncate off the last character, which might be more than 1 byte + * in MULTIBYTE case. + */ +#ifdef MULTIBYTE + len = pg_mbcliplen((const unsigned char *) workstr, len, len-1); + workstr[len] = '\0'; +#else + *lastchar = '\0'; +#endif + } + + /* Failed... */ + pfree(workstr); + return NULL; +} + +/* + * Handy subroutines for match_special_index_operator() and friends. + */ + +/* See if there is a binary op of the given name for the given datatype */ +static Oid +find_operator(const char * opname, Oid datatype) +{ + HeapTuple optup; + + optup = SearchSysCacheTuple(OPERNAME, + PointerGetDatum(opname), + ObjectIdGetDatum(datatype), + ObjectIdGetDatum(datatype), + CharGetDatum('b')); + if (!HeapTupleIsValid(optup)) + return InvalidOid; + return optup->t_data->t_oid; +} + +/* + * Generate a Datum of the appropriate type from a C string. + * Note that all of the supported types are pass-by-ref, so the + * returned value should be pfree'd if no longer needed. + */ +static Datum +string_to_datum(const char * str, Oid datatype) +{ + /* We cheat a little by assuming that textin() will do for + * bpchar and varchar constants too... + */ + if (datatype == NAMEOID) + return PointerGetDatum(namein((char *) str)); + else + return PointerGetDatum(textin((char *) str)); +} + +/* + * Generate a Const node of the appropriate type from a C string. + */ +static Const * +string_to_const(const char * str, Oid datatype) +{ + Datum conval = string_to_datum(str, datatype); + + return makeConst(datatype, ((datatype == NAMEOID) ? NAMEDATALEN : -1), + conval, false, false, false, false); +} + +/* + * Test whether two strings are "<" according to the rules of the given + * datatype. We do this the hard way, ie, actually calling the type's + * "<" operator function, to ensure we get the right result... + */ +static bool +string_lessthan(const char * str1, const char * str2, Oid datatype) +{ + Datum datum1 = string_to_datum(str1, datatype); + Datum datum2 = string_to_datum(str2, datatype); + bool result; + + switch (datatype) + { + case TEXTOID: + result = text_lt((text *) datum1, (text *) datum2); + break; + + case BPCHAROID: + result = bpcharlt((char *) datum1, (char *) datum2); + break; + + case VARCHAROID: + result = varcharlt((char *) datum1, (char *) datum2); + break; + + case NAMEOID: + result = namelt((NameData *) datum1, (NameData *) datum2); + break; + + default: + elog(ERROR, "string_lessthan: unexpected datatype %u", datatype); + result = false; + break; + } + + pfree(DatumGetPointer(datum1)); + pfree(DatumGetPointer(datum2)); + + return result; }