*
* 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.48 1999/02/15 05:21:04 momjian Exp $
+ * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.77 2000/01/22 23:50:14 tgl Exp $
*
*-------------------------------------------------------------------------
*/
+#include <ctype.h>
#include <math.h>
#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,
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)
{
- joinpaths = create_index_paths(root, rel,
- index,
- joinclausegroups,
- true);
- rel->innerjoin = nconc(rel->innerjoin,
- index_innerjoin(root, rel,
- joinclausegroups, index));
+ 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
*/
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);
}
foreach(clist, or_clauses)
{
- clause = lfirst(clist);
+ Expr *clause = lfirst(clist);
- if (is_opclause(clause))
+ if (match_or_subclause_to_indexkey(rel, index, indexkey, opclass,
+ clause))
{
- Expr *left = (Expr *) get_leftop((Expr *) clause);
- Expr *right = (Expr *) get_rightop((Expr *) clause);
- if (left && right &&
- op_class(((Oper *) ((Expr *) clause)->oper)->opno,
- xclass, index->relam) &&
- ((IsA(right, Const) &&
- match_index_to_operand(indexkey, left, rel, index)) ||
- (IsA(left, Const) &&
- match_index_to_operand(indexkey, right, rel, index))))
- lfirst(matching_indices) = lcons(index,
- lfirst(matching_indices));
+ /* 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 ----
****************************************************************************/
/*
* 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)
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:
+
+ * (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().
*
- * 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.
+ * 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.
*
- * If the clause being matched is a join clause, then 'join' is t.
+ * 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.
*
- * Returns a single restrictinfo node corresponding to the matching
- * 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.
*
- * NOTE: returns nil if clause is an or_clause.
+ * 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;
+}
- if (isIndexable)
- return restrictInfo;
+/*
+ * 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;
- return NULL;
+ 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;
}
/****************************************************************************
* 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},
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);
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
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);
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);
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
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
/*
* 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->unjoined_rels;
+ 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;
- 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);
- ip_list = lappend(ip_list, temp_path);
- }
+ /*
+ * 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;
/*
* 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;
/*
* 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;
}
projects / postgresql / blobdiff