diff options
Diffstat (limited to 'src/backend/optimizer')
| -rw-r--r-- | src/backend/optimizer/path/indxpath.c | 604 | ||||
| -rw-r--r-- | src/backend/optimizer/path/orindxpath.c | 89 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/createplan.c | 40 | ||||
| -rw-r--r-- | src/backend/optimizer/util/clauses.c | 18 | ||||
| -rw-r--r-- | src/backend/optimizer/util/pathnode.c | 57 |
5 files changed, 610 insertions, 198 deletions
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 2f1002c78f5..670a41c60ad 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -8,10 +8,11 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.65 1999/07/25 23:07:24 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.66 1999/07/27 03:51:01 tgl Exp $ * *------------------------------------------------------------------------- */ +#include <ctype.h> #include <math.h> #include "postgres.h" @@ -20,6 +21,7 @@ #include "access/nbtree.h" #include "catalog/catname.h" #include "catalog/pg_amop.h" +#include "catalog/pg_operator.h" #include "executor/executor.h" #include "nodes/makefuncs.h" #include "nodes/nodeFuncs.h" @@ -35,8 +37,13 @@ #include "parser/parse_expr.h" #include "parser/parse_oper.h" #include "parser/parsetree.h" +#include "utils/builtins.h" #include "utils/lsyscache.h" +#include "utils/syscache.h" +typedef enum { + Prefix_None, Prefix_Partial, Prefix_Exact +} Prefix_Status; static void match_index_orclauses(RelOptInfo *rel, RelOptInfo *index, int indexkey, int xclass, List *restrictinfo_list); @@ -65,6 +72,12 @@ static List *create_index_path_group(Query *root, RelOptInfo *rel, RelOptInfo *i static bool match_index_to_operand(int indexkey, Expr *operand, RelOptInfo *rel, RelOptInfo *index); static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index); +static bool match_special_index_operator(Expr *clause, 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); /* @@ -502,7 +515,8 @@ group_clauses_by_ikey_for_joins(RelOptInfo *rel, * or (var op var) for a join clause, where the var or one * of the vars matches the index key; and * (2) contain an operator which is in the same class as the index - * operator for this key. + * operator for this key, or is a "special" operator as recognized + * by match_special_index_operator(). * * In the restriction case, we can cope with (const op var) by commuting * the clause to (var op const), if there is a commutator operator. @@ -539,6 +553,7 @@ match_clause_to_indexkey(RelOptInfo *rel, bool isIndexable = false; Var *leftop, *rightop; + Oid expr_op; if (! is_opclause((Node *) clause)) return false; @@ -546,6 +561,7 @@ match_clause_to_indexkey(RelOptInfo *rel, rightop = get_rightop(clause); if (! leftop || ! rightop) return false; + expr_op = ((Oper *) clause->oper)->opno; if (!join) { @@ -553,23 +569,17 @@ match_clause_to_indexkey(RelOptInfo *rel, * Not considering joins, so check for clauses of the form: * (var/func operator constant) and (constant operator var/func) */ - Oid restrict_op = InvalidOid; /* * Check for standard s-argable clause */ - if (IsA(rightop, Const) || IsA(rightop, Param)) + if ((IsA(rightop, Const) || IsA(rightop, Param)) && + match_index_to_operand(indexkey, (Expr *) leftop, + rel, index)) { - restrict_op = ((Oper *) ((Expr *) clause)->oper)->opno; - - isIndexable = (op_class(restrict_op, xclass, index->relam) && - match_index_to_operand(indexkey, - (Expr *) leftop, - rel, - index)); + isIndexable = op_class(expr_op, xclass, index->relam); #ifndef IGNORE_BINARY_COMPATIBLE_INDICES - /* * Didn't find an index? Then maybe we can find another * binary-compatible index instead... thomas 1998-08-14 @@ -583,88 +593,70 @@ match_clause_to_indexkey(RelOptInfo *rel, * make sure we have two different binary-compatible * types... */ - if ((ltype != rtype) - && IS_BINARY_COMPATIBLE(ltype, rtype)) + if (ltype != rtype && IS_BINARY_COMPATIBLE(ltype, rtype)) { - char *opname; - Operator newop; + char *opname = get_opname(expr_op); + Operator newop = NULL; - 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)) + if (HeapTupleIsValid(newop) && oprid(newop) != expr_op) { - restrict_op = oprid(newop); - - isIndexable = (op_class(restrict_op, xclass, index->relam) && - match_index_to_operand(indexkey, - (Expr *) leftop, - rel, - index)); - + expr_op = oprid(newop); + isIndexable = op_class(expr_op, xclass, index->relam); if (isIndexable) - ((Oper *) ((Expr *) clause)->oper)->opno = restrict_op; + ((Oper *) clause->oper)->opno = expr_op; } } } #endif + + /* + * If we didn't find a member of the index's opclass, + * see whether it is a "special" indexable operator. + */ + if (!isIndexable) + isIndexable = match_special_index_operator(clause, true); + } /* * Must try to commute the clause to standard s-arg format. + * XXX do we really have to commute it? The executor doesn't care! */ - else if (IsA(leftop, Const) || IsA(leftop, Param)) + else if ((IsA(leftop, Const) || IsA(leftop, Param)) && + match_index_to_operand(indexkey, (Expr *) rightop, + rel, index)) { - restrict_op = get_commutator(((Oper *) ((Expr *) clause)->oper)->opno); + Oid commuted_op = get_commutator(expr_op); - isIndexable = ((restrict_op != InvalidOid) && - op_class(restrict_op, xclass, index->relam) && - match_index_to_operand(indexkey, - (Expr *) rightop, - rel, - index)); + isIndexable = ((commuted_op != InvalidOid) && + op_class(commuted_op, xclass, index->relam)); #ifndef IGNORE_BINARY_COMPATIBLE_INDICES if (!isIndexable) { - Oid ltype; - Oid rtype; - - ltype = exprType((Node *) leftop); - rtype = exprType((Node *) rightop); + Oid ltype = exprType((Node *) leftop); + Oid rtype = exprType((Node *) rightop); - if ((ltype != rtype) - && IS_BINARY_COMPATIBLE(ltype, rtype)) + if (ltype != rtype && IS_BINARY_COMPATIBLE(ltype, rtype)) { - char *opname; - Operator newop; + char *opname = get_opname(expr_op); + Operator newop = NULL; - restrict_op = ((Oper *) ((Expr *) clause)->oper)->opno; - - opname = get_opname(restrict_op); + /* note we use rtype, ie, the indexkey's type */ if (opname != NULL) newop = oper(opname, rtype, rtype, TRUE); - else - newop = NULL; - if (HeapTupleIsValid(newop) && (oprid(newop) != restrict_op)) + if (HeapTupleIsValid(newop) && oprid(newop) != expr_op) { - restrict_op = get_commutator(oprid(newop)); - - isIndexable = ((restrict_op != InvalidOid) && - op_class(restrict_op, xclass, index->relam) && - match_index_to_operand(indexkey, - (Expr *) rightop, - rel, - index)); - + expr_op = get_commutator(oprid(newop)); + isIndexable = (expr_op != InvalidOid) && + op_class(expr_op, xclass, index->relam); if (isIndexable) - ((Oper *) ((Expr *) clause)->oper)->opno = oprid(newop); + ((Oper *) clause->oper)->opno = oprid(newop); } } } @@ -672,13 +664,22 @@ match_clause_to_indexkey(RelOptInfo *rel, if (isIndexable) { - /* * In place list modification. (op const var/func) -> (op * var/func const) */ CommuteClause((Node *) clause); } + else + { + /* + * If we didn't find a member of the index's opclass, + * see whether it is a "special" indexable operator. + * (match_special_index_operator must commute the + * clause itself, if it wants to.) + */ + isIndexable = match_special_index_operator(clause, false); + } } } else @@ -694,10 +695,10 @@ match_clause_to_indexkey(RelOptInfo *rel, if (match_index_to_operand(indexkey, (Expr *) leftop, rel, index)) - join_op = ((Oper *) ((Expr *) clause)->oper)->opno; + join_op = expr_op; else if (match_index_to_operand(indexkey, (Expr *) rightop, rel, index)) - join_op = get_commutator(((Oper *) ((Expr *) clause)->oper)->opno); + join_op = get_commutator(expr_op); if (join_op && op_class(join_op, xclass, index->relam) && is_joinable((Node *) clause)) @@ -1221,6 +1222,8 @@ index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index, float selec; indexquals = get_actual_clauses(clausegroup); + /* expand special operators to indexquals the executor can handle */ + indexquals = expand_indexqual_conditions(indexquals); index_selectivity(root, lfirsti(rel->relids), @@ -1258,18 +1261,6 @@ index_innerjoin(Query *root, RelOptInfo *rel, RelOptInfo *index, index->tuples, true); - /* - * copy restrictinfo list into path for expensive function - * processing -- JMH, 7/7/92 - */ - pathnode->path.loc_restrictinfo = set_difference(copyObject((Node *) rel->restrictinfo), - clausegroup); - -#ifdef NOT_USED /* 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 path_list = lappend(path_list, pathnode); outerrelids_list = lnext(outerrelids_list); } @@ -1419,3 +1410,460 @@ function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index) 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, 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; + } + + 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 with 1 spare byte, + * 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)+2); + 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 with 1 spare byte, + * 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)+2); + 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; + HeapTuple optup; + void *conval; + Const *con; + Oper *op; + Expr *expr; + int prefixlen; + + 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) + { + optup = SearchSysCacheTuple(OPRNAME, + PointerGetDatum("="), + ObjectIdGetDatum(datatype), + ObjectIdGetDatum(datatype), + CharGetDatum('b')); + if (!HeapTupleIsValid(optup)) + elog(ERROR, "prefix_quals: no = operator for type %u", datatype); + /* Note: we cheat a little by assuming that textin() will do for + * bpchar and varchar constants too... + */ + conval = (datatype == NAMEOID) ? + (void*) namein(prefix) : (void*) textin(prefix); + con = makeConst(datatype, ((datatype == NAMEOID) ? NAMEDATALEN : -1), + PointerGetDatum(conval), + false, false, false, false); + op = makeOper(optup->t_data->t_oid, 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". + */ + optup = SearchSysCacheTuple(OPRNAME, + PointerGetDatum(">="), + ObjectIdGetDatum(datatype), + ObjectIdGetDatum(datatype), + CharGetDatum('b')); + if (!HeapTupleIsValid(optup)) + elog(ERROR, "prefix_quals: no >= operator for type %u", datatype); + conval = (datatype == NAMEOID) ? + (void*) namein(prefix) : (void*) textin(prefix); + con = makeConst(datatype, ((datatype == NAMEOID) ? NAMEDATALEN : -1), + PointerGetDatum(conval), + false, false, false, false); + op = makeOper(optup->t_data->t_oid, InvalidOid, BOOLOID, 0, NULL); + expr = make_opclause(op, leftop, (Var *) con); + result = lcons(expr, NIL); + + /* + * In ASCII locale we say "x <= prefix\377". This does not + * work for non-ASCII collation orders, and it's not really + * right even for ASCII. FIX ME! + * Note we assume the passed prefix string is workspace with + * an extra byte, as created by the xxx_fixed_prefix routines above. + */ +#ifndef USE_LOCALE + prefixlen = strlen(prefix); + prefix[prefixlen] = '\377'; + prefix[prefixlen+1] = '\0'; + + optup = SearchSysCacheTuple(OPRNAME, + PointerGetDatum("<="), + ObjectIdGetDatum(datatype), + ObjectIdGetDatum(datatype), + CharGetDatum('b')); + if (!HeapTupleIsValid(optup)) + elog(ERROR, "prefix_quals: no <= operator for type %u", datatype); + conval = (datatype == NAMEOID) ? + (void*) namein(prefix) : (void*) textin(prefix); + con = makeConst(datatype, ((datatype == NAMEOID) ? NAMEDATALEN : -1), + PointerGetDatum(conval), + false, false, false, false); + op = makeOper(optup->t_data->t_oid, InvalidOid, BOOLOID, 0, NULL); + expr = make_opclause(op, leftop, (Var *) con); + result = lappend(result, expr); +#endif + + return result; +} diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c index 39fa69cdef8..450b8d7b2dc 100644 --- a/src/backend/optimizer/path/orindxpath.c +++ b/src/backend/optimizer/path/orindxpath.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.30 1999/07/25 23:07:24 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.31 1999/07/27 03:51:02 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -28,11 +28,13 @@ static void best_or_subclause_indices(Query *root, RelOptInfo *rel, List *subclauses, List *indices, + List **indexquals, List **indexids, Cost *cost, Cost *selec); static void best_or_subclause_index(Query *root, RelOptInfo *rel, - Expr *subclause, List *indices, - int *indexid, Cost *cost, Cost *selec); + List *indexqual, List *indices, + int *retIndexid, + Cost *retCost, Cost *retSelec); /* @@ -84,8 +86,8 @@ create_or_index_paths(Query *root, * best available index for each subclause. */ IndexPath *pathnode = makeNode(IndexPath); + List *indexquals; List *indexids; - List *orclause; Cost cost; Cost selec; @@ -93,6 +95,7 @@ create_or_index_paths(Query *root, rel, clausenode->clause->args, clausenode->indexids, + &indexquals, &indexids, &cost, &selec); @@ -111,43 +114,11 @@ create_or_index_paths(Query *root, pathnode->path.pathorder->ord.sortop = NULL; pathnode->path.pathkeys = NIL; - /* - * Generate an indexqual list from the OR clause's args. - * We want two levels of sublist: the first is implicit OR - * and the second is implicit AND. (Currently, we will never - * see a sub-AND-clause because of cnfify(), but someday maybe - * the code below will do something useful...) - */ - pathnode->indexqual = NIL; - foreach(orclause, clausenode->clause->args) - { - Expr *subclause = (Expr *) lfirst(orclause); - List *sublist; - - if (and_clause((Node *) subclause)) - sublist = subclause->args; - else - sublist = lcons(subclause, NIL); - /* expansion call... */ - pathnode->indexqual = lappend(pathnode->indexqual, - sublist); - } + pathnode->indexqual = indexquals; pathnode->indexid = indexids; pathnode->path.path_cost = cost; clausenode->selectivity = (Cost) selec; - /* - * copy restrictinfo list into path for expensive function - * processing -- JMH, 7/7/92 - */ - pathnode->path.loc_restrictinfo = set_difference(copyObject((Node *) rel->restrictinfo), - lcons(clausenode, NIL)); - -#ifdef NOT_USED /* 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 path_list = lappend(path_list, pathnode); } } @@ -163,11 +134,21 @@ create_or_index_paths(Query *root, * indices. The cost is the sum of the individual index costs, since * the executor will perform a scan for each subclause of the 'or'. * + * This routine also creates the indexquals and indexids lists that will + * be needed by the executor. The indexquals list has one entry for each + * scan of the base rel, which is a sublist of indexqual conditions to + * apply in that scan. The implicit semantics are AND across each sublist + * of quals, and OR across the toplevel list (note that the executor + * takes care not to return any single tuple more than once). The indexids + * list gives the index to be used in each scan. + * * 'rel' is the node of the relation on which the indexes are defined * 'subclauses' are the subclauses of the 'or' clause * 'indices' is a list of sublists of the index nodes that matched each * subclause of the 'or' clause - * '*indexids' gets a list of the best index ID to use for each subclause + * '*indexquals' gets the constructed indexquals for the path (a list + * of sublists of clauses, one sublist per scan of the base rel) + * '*indexids' gets a list of the index IDs for each scan of the rel * '*cost' gets the total cost of the path * '*selec' gets the total selectivity of the path. */ @@ -176,27 +157,41 @@ best_or_subclause_indices(Query *root, RelOptInfo *rel, List *subclauses, List *indices, + List **indexquals, /* return value */ List **indexids, /* return value */ Cost *cost, /* return value */ Cost *selec) /* return value */ { List *slist; + *indexquals = NIL; *indexids = NIL; - *selec = (Cost) 0.0; *cost = (Cost) 0.0; + *selec = (Cost) 0.0; foreach(slist, subclauses) { + Expr *subclause = lfirst(slist); + List *indexqual; int best_indexid; Cost best_cost; Cost best_selec; - best_or_subclause_index(root, rel, lfirst(slist), lfirst(indices), + /* Convert this 'or' subclause to an indexqual list */ + indexqual = make_ands_implicit(subclause); + /* expand special operators to indexquals the executor can handle */ + indexqual = expand_indexqual_conditions(indexqual); + + best_or_subclause_index(root, rel, indexqual, lfirst(indices), &best_indexid, &best_cost, &best_selec); + *indexquals = lappend(*indexquals, indexqual); *indexids = lappendi(*indexids, best_indexid); *cost += best_cost; + /* We approximate the selectivity as the sum of the clause + * selectivities (but not more than 1). + * XXX This is too pessimistic, isn't it? + */ *selec += best_selec; if (*selec > (Cost) 1.0) *selec = (Cost) 1.0; @@ -212,7 +207,7 @@ best_or_subclause_indices(Query *root, * the least expensive. * * 'rel' is the node of the relation on which the index is defined - * 'subclause' is the subclause + * 'indexqual' is the indexqual list derived from the subclause * 'indices' is a list of index nodes that match the subclause * '*retIndexid' gets the ID of the best index * '*retCost' gets the cost of a scan with that index @@ -221,14 +216,13 @@ best_or_subclause_indices(Query *root, static void best_or_subclause_index(Query *root, RelOptInfo *rel, - Expr *subclause, + List *indexqual, List *indices, int *retIndexid, /* return value */ Cost *retCost, /* return value */ Cost *retSelec) /* return value */ { bool first_run = true; - List *indexquals; List *ilist; /* if we don't match anything, return zeros */ @@ -236,13 +230,6 @@ best_or_subclause_index(Query *root, *retCost = (Cost) 0.0; *retSelec = (Cost) 0.0; - /* convert 'or' subclause to an indexqual list */ - if (and_clause((Node *) subclause)) - indexquals = subclause->args; - else - indexquals = lcons(subclause, NIL); - /* expansion call... */ - foreach(ilist, indices) { RelOptInfo *index = (RelOptInfo *) lfirst(ilist); @@ -254,7 +241,7 @@ best_or_subclause_index(Query *root, index_selectivity(root, lfirsti(rel->relids), indexid, - indexquals, + indexqual, &npages, &selec); diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 0148d4912e1..18837cf2824 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.63 1999/07/24 23:21:11 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.64 1999/07/27 03:51:03 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -151,15 +151,11 @@ create_scan_node(Path *best_path, List *tlist) List *scan_clauses; /* - * Extract the relevant clauses from the parent relation and replace - * the operator OIDs with the corresponding regproc ids. - * - * now that local predicate clauses are copied into paths in - * find_rel_paths() and then (possibly) pulled up in - * xfunc_trypullup(), we get the relevant clauses from the path - * itself, not its parent relation. --- JMH, 6/15/92 + * Extract the relevant restriction clauses from the parent relation; + * the executor must apply all these restrictions during the scan. + * Fix regproc ids in the restriction clauses. */ - scan_clauses = fix_opids(get_actual_clauses(best_path->loc_restrictinfo)); + scan_clauses = fix_opids(get_actual_clauses(best_path->parent->restrictinfo)); switch (best_path->pathtype) { @@ -245,8 +241,7 @@ create_join_node(JoinPath *best_path, List *tlist) best_path->path.pathtype); } -#if 0 - +#ifdef NOT_USED /* * * Expensive function pullups may have pulled local predicates * * into this path node. Put them in the qpqual of the plan node. * @@ -282,11 +277,10 @@ create_seqscan_node(Path *best_path, List *tlist, List *scan_clauses) List *temp; temp = best_path->parent->relids; - if (temp == NULL) - elog(ERROR, "scanrelid is empty"); - else - scan_relid = (Index) lfirsti(temp); /* ??? who takes care of - * lnext? - ay */ + /* there should be exactly one base rel involved... */ + Assert(length(temp) == 1); + scan_relid = (Index) lfirsti(temp); + scan_node = make_seqscan(tlist, scan_clauses, scan_relid, @@ -319,6 +313,9 @@ create_indexscan_node(IndexPath *best_path, IndexScan *scan_node; bool lossy = false; + /* there should be exactly one base rel involved... */ + Assert(length(best_path->path.parent->relids) == 1); + /* check and see if any indices are lossy */ foreach(ixid, best_path->indexid) { @@ -345,9 +342,9 @@ create_indexscan_node(IndexPath *best_path, * lossy indices the indxqual predicates need to be double-checked * after the index fetches the best-guess tuples. * - * There should not be any clauses in scan_clauses that duplicate - * expressions checked by the index, but just in case, we will - * get rid of them via set_difference. + * Since the indexquals were generated from the restriction clauses + * given by scan_clauses, there will normally be some duplications + * between the lists. Get rid of the duplicates, then add back if lossy. */ if (length(indxqual) > 1) { @@ -387,9 +384,8 @@ create_indexscan_node(IndexPath *best_path, qpqual = NIL; /* - * Fix opids in the completed indxqual. We don't want to do this sooner - * since it would screw up the set_difference calcs above. Really, - * this ought to only happen at final exit from the planner... + * Fix opids in the completed indxqual. + * XXX this ought to only happen at final exit from the planner... */ indxqual = fix_opids(indxqual); diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c index 442ebad1e7b..de9ef509382 100644 --- a/src/backend/optimizer/util/clauses.c +++ b/src/backend/optimizer/util/clauses.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.42 1999/07/25 23:07:25 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.43 1999/07/27 03:51:04 tgl Exp $ * * HISTORY * AUTHOR DATE MAJOR EVENT @@ -293,8 +293,9 @@ make_andclause(List *andclauses) /* * Sometimes (such as in the result of cnfify), we use lists of expression - * nodes with implicit AND semantics. This function converts back to an - * explicit-AND representation. + * nodes with implicit AND semantics. These functions convert between an + * AND-semantics expression list and the ordinary representation of a + * boolean expression. */ Expr * make_ands_explicit(List *andclauses) @@ -307,6 +308,17 @@ make_ands_explicit(List *andclauses) return make_andclause(andclauses); } +List * +make_ands_implicit(Expr *clause) +{ + if (clause == NULL) + return NIL; + else if (and_clause((Node *) clause)) + return clause->args; + else + return lcons(clause, NIL); +} + /***************************************************************************** * CASE clause functions *****************************************************************************/ diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 658ee57baaa..aa0aedb4530 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.48 1999/07/25 23:07:26 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.49 1999/07/27 03:51:05 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -21,6 +21,7 @@ #include "optimizer/keys.h" #include "optimizer/ordering.h" #include "optimizer/pathnode.h" +#include "optimizer/paths.h" #include "optimizer/plancat.h" #include "optimizer/restrictinfo.h" #include "parser/parsetree.h" @@ -288,22 +289,12 @@ create_seqscan_path(RelOptInfo *rel) pathnode->pathorder->ord.sortop = NULL; pathnode->pathkeys = NIL; - /* - * copy restrictinfo list into path for expensive function processing - * JMH, 7/7/92 - */ - pathnode->loc_restrictinfo = (List *) copyObject((Node *) rel->restrictinfo); - if (rel->relids != NULL) relid = lfirsti(rel->relids); pathnode->path_cost = cost_seqscan(relid, rel->pages, rel->tuples); - /* add in expensive functions cost! -- JMH, 7/7/92 */ -#ifdef NOT_USED - if (XfuncMode != XFUNC_OFF) - pathnode->path_cost += xfunc_get_path_cost(pathnode); -#endif + return pathnode; } @@ -345,13 +336,6 @@ create_index_path(Query *root, pathnode->indexqual = NIL; /* - * copy restrictinfo list into path for expensive function processing - * JMH, 7/7/92 - */ - pathnode->path.loc_restrictinfo = set_difference((List *) copyObject((Node *) rel->restrictinfo), - restriction_clauses); - - /* * The index must have an ordering for the path to have (ordering) * keys, and vice versa. */ @@ -403,6 +387,8 @@ create_index_path(Query *root, Cost clausesel; indexquals = get_actual_clauses(restriction_clauses); + /* expand special operators to indexquals the executor can handle */ + indexquals = expand_indexqual_conditions(indexquals); index_selectivity(root, lfirsti(rel->relids), @@ -425,20 +411,18 @@ create_index_path(Query *root, * Set selectivities of clauses used with index to the selectivity * of this index, subdividing the selectivity equally over each of * the clauses. + * * XXX Can this divide the selectivities in a better way? + * * XXX In fact, why the heck are we doing this at all? We already - * set the cost for the indexpath. + * set the cost for the indexpath, and it's far from obvious that + * the selectivity of the path should have any effect on estimates + * made for other contexts... */ clausesel = pow(selec, 1.0 / (double) length(restriction_clauses)); set_clause_selectivities(restriction_clauses, clausesel); } -#ifdef NOT_USED - /* add in expensive functions cost! -- JMH, 7/7/92 */ - if (XfuncMode != XFUNC_OFF) - pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode); -#endif - return pathnode; } @@ -473,7 +457,6 @@ create_nestloop_path(RelOptInfo *joinrel, pathnode->path.pathkeys = pathkeys; pathnode->path.joinid = NIL; pathnode->path.outerjoincost = (Cost) 0.0; - pathnode->path.loc_restrictinfo = NIL; pathnode->path.pathorder = makeNode(PathOrder); if (pathkeys) @@ -497,11 +480,7 @@ create_nestloop_path(RelOptInfo *joinrel, page_size(outer_rel->size, outer_rel->width), IsA(inner_path, IndexPath)); - /* add in expensive function costs -- JMH 7/7/92 */ -#ifdef NOT_USED - if (XfuncMode != XFUNC_OFF) - pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode); -#endif + return pathnode; } @@ -550,7 +529,6 @@ create_mergejoin_path(RelOptInfo *joinrel, pathnode->jpath.path.pathorder->ordtype = MERGE_ORDER; pathnode->jpath.path.pathorder->ord.merge = order; pathnode->path_mergeclauses = mergeclauses; - pathnode->jpath.path.loc_restrictinfo = NIL; pathnode->outersortkeys = outersortkeys; pathnode->innersortkeys = innersortkeys; pathnode->jpath.path.path_cost = cost_mergejoin(outer_path->path_cost, @@ -561,11 +539,7 @@ create_mergejoin_path(RelOptInfo *joinrel, innersize, outerwidth, innerwidth); - /* add in expensive function costs -- JMH 7/7/92 */ -#ifdef NOT_USED - if (XfuncMode != XFUNC_OFF) - pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode); -#endif + return pathnode; } @@ -608,7 +582,6 @@ create_hashjoin_path(RelOptInfo *joinrel, pathnode->jpath.outerjoinpath = outer_path; pathnode->jpath.innerjoinpath = inner_path; pathnode->jpath.pathinfo = joinrel->restrictinfo; - pathnode->jpath.path.loc_restrictinfo = NIL; pathnode->jpath.path.pathkeys = pathkeys; pathnode->jpath.path.pathorder = makeNode(PathOrder); pathnode->jpath.path.pathorder->ordtype = SORTOP_ORDER; @@ -625,10 +598,6 @@ create_hashjoin_path(RelOptInfo *joinrel, innerkeys, outersize, innersize, outerwidth, innerwidth); - /* add in expensive function costs -- JMH 7/7/92 */ -#ifdef NOT_USED - if (XfuncMode != XFUNC_OFF) - pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode); -#endif + return pathnode; } |