diff options
Diffstat (limited to 'src/backend')
| -rw-r--r-- | src/backend/access/index/indexam.c | 24 | ||||
| -rw-r--r-- | src/backend/access/nbtree/nbtsearch.c | 12 | ||||
| -rw-r--r-- | src/backend/access/nbtree/nbtutils.c | 17 | ||||
| -rw-r--r-- | src/backend/optimizer/path/indxpath.c | 53 | ||||
| -rw-r--r-- | src/backend/optimizer/util/plancat.c | 5 | ||||
| -rw-r--r-- | src/backend/utils/adt/selfuncs.c | 122 |
6 files changed, 154 insertions, 79 deletions
diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c index 81c2114976e..a445efc7154 100644 --- a/src/backend/access/index/indexam.c +++ b/src/backend/access/index/indexam.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/access/index/indexam.c,v 1.82 2005/05/27 23:31:20 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/access/index/indexam.c,v 1.83 2005/06/13 23:14:48 tgl Exp $ * * INTERFACE ROUTINES * index_open - open an index relation by relation OID @@ -25,7 +25,6 @@ * index_getmulti - get multiple tuples from a scan * index_bulk_delete - bulk deletion of index tuples * index_vacuum_cleanup - post-deletion cleanup of an index - * index_cost_estimator - fetch amcostestimate procedure OID * index_getprocid - get a support procedure OID * index_getprocinfo - get a support procedure's lookup info * @@ -719,27 +718,6 @@ index_vacuum_cleanup(Relation indexRelation, } /* ---------------- - * index_cost_estimator - * - * Fetch the amcostestimate procedure OID for an index. - * - * We could combine fetching and calling the procedure, - * as index_insert does for example; but that would require - * importing a bunch of planner/optimizer stuff into this file. - * ---------------- - */ -RegProcedure -index_cost_estimator(Relation indexRelation) -{ - FmgrInfo *procedure; - - RELATION_CHECKS; - GET_REL_PROCEDURE(amcostestimate); - - return procedure->fn_oid; -} - -/* ---------------- * index_getprocid * * Some indexed access methods may require support routines that are diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c index 17b3b0dcddf..824d5ea70e6 100644 --- a/src/backend/access/nbtree/nbtsearch.c +++ b/src/backend/access/nbtree/nbtsearch.c @@ -8,7 +8,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.91 2005/03/29 00:16:52 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.92 2005/06/13 23:14:48 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -594,15 +594,17 @@ _bt_first(IndexScanDesc scan, ScanDirection dir) } /* - * Done if that was the last attribute. + * Done if that was the last attribute, or if next key + * is not in sequence (implying no boundary key is available + * for the next attribute). */ - if (i >= so->numberOfKeys) + if (i >= so->numberOfKeys || + cur->sk_attno != curattr + 1) break; /* - * Reset for next attr, which should be in sequence. + * Reset for next attr. */ - Assert(cur->sk_attno == curattr + 1); curattr = cur->sk_attno; chosen = NULL; } diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c index 96a3f05a5d6..9a5f8d7ac90 100644 --- a/src/backend/access/nbtree/nbtutils.c +++ b/src/backend/access/nbtree/nbtutils.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/access/nbtree/nbtutils.c,v 1.62 2004/12/31 21:59:22 pgsql Exp $ + * $PostgreSQL: pgsql/src/backend/access/nbtree/nbtutils.c,v 1.63 2005/06/13 23:14:48 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -190,7 +190,9 @@ _bt_formitem(IndexTuple itup) * matched to continue the scan. In general, numberOfRequiredKeys is equal * to the number of keys for leading attributes with "=" keys, plus the * key(s) for the first non "=" attribute, which can be seen to be correct - * by considering the above example. + * by considering the above example. Note in particular that if there are no + * keys for a given attribute, the keys for subsequent attributes can never + * be required; for instance "WHERE y = 4" requires a full-index scan. * * If possible, redundant keys are eliminated: we keep only the tightest * >/>= bound and the tightest </<= bound, and if there's an = key then @@ -248,8 +250,8 @@ _bt_preprocess_keys(IndexScanDesc scan) outkeys = so->keyData; cur = &inkeys[0]; /* we check that input keys are correctly ordered */ - if (cur->sk_attno != 1) - elog(ERROR, "key(s) for attribute 1 missed"); + if (cur->sk_attno < 1) + elog(ERROR, "btree index keys must be ordered by attribute"); /* We can short-circuit most of the work if there's just one key */ if (numberOfKeys == 1) @@ -270,7 +272,8 @@ _bt_preprocess_keys(IndexScanDesc scan) } memcpy(outkeys, inkeys, sizeof(ScanKeyData)); so->numberOfKeys = 1; - so->numberOfRequiredKeys = 1; + if (cur->sk_attno == 1) + so->numberOfRequiredKeys = 1; return; } @@ -324,8 +327,8 @@ _bt_preprocess_keys(IndexScanDesc scan) int priorNumberOfEqualCols = numberOfEqualCols; /* check input keys are correctly ordered */ - if (i < numberOfKeys && cur->sk_attno != attno + 1) - elog(ERROR, "key(s) for attribute %d missed", attno + 1); + if (i < numberOfKeys && cur->sk_attno < attno) + elog(ERROR, "btree index keys must be ordered by attribute"); /* * If = has been specified, no other key will be used. In case diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 9c1874d5907..525304f5cb3 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.183 2005/06/10 22:25:36 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.184 2005/06/13 23:14:48 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -87,7 +87,8 @@ static Const *string_to_const(const char *str, Oid datatype); * * 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. + * or match the query's ORDER BY condition, or have a predicate that + * matches the query's qual condition. * * There are two basic kinds of index scans. A "plain" index scan uses * only restriction clauses (possibly none at all) in its indexqual, @@ -210,6 +211,7 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel) * 'clauses' is the current list of clauses (RestrictInfo nodes) * 'outer_clauses' is the list of additional upper-level clauses * 'istoplevel' is true if clauses are the rel's top-level restriction list + * (outer_clauses must be NIL when this is true) * 'isjoininner' is true if forming an inner indexscan (so some of the * given clauses are join clauses) * 'outer_relids' identifies the outer side of the join (pass NULL @@ -295,13 +297,12 @@ find_usable_indexes(PlannerInfo *root, RelOptInfo *rel, * selectivity of the predicate might alone make the index useful. * * Note: not all index AMs support scans with no restriction clauses. - * We assume here that the AM does so if and only if it supports - * ordered scans. (It would probably be better if there were a - * specific flag for this in pg_am, but there's not.) + * We can't generate a scan over an index with amoptionalkey = false + * unless there's at least one restriction clause. */ if (restrictclauses != NIL || - useful_pathkeys != NIL || - (index->indpred != NIL && index_is_ordered)) + (index->amoptionalkey && + (useful_pathkeys != NIL || index->indpred != NIL))) { ipath = create_index_path(root, index, restrictclauses, @@ -608,6 +609,11 @@ bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel, List *paths) * group_clauses_by_indexkey * Find restriction clauses that can be used with an index. * + * Returns a list of sublists of RestrictInfo nodes for clauses that can be + * used with this index. Each sublist contains clauses that can be used + * with one index key (in no particular order); the top list is ordered by + * index key. (This is depended on by expand_indexqual_conditions().) + * * As explained in the comments for find_usable_indexes(), we can use * clauses from either of the given lists, but the result is required to * use at least one clause from the "current clauses" list. We return @@ -616,18 +622,14 @@ bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel, List *paths) * outer_relids determines what Vars will be allowed on the other side * of a possible index qual; see match_clause_to_indexcol(). * - * Returns a list of sublists of RestrictInfo nodes for clauses that can be - * used with this index. Each sublist contains clauses that can be used - * with one index key (in no particular order); the top list is ordered by - * index key. (This is depended on by expand_indexqual_conditions().) + * If the index has amoptionalkey = false, we give up and return NIL when + * there are no restriction clauses matching the first index key. Otherwise, + * we return NIL if there are no restriction clauses matching any index key. + * A non-NIL result will have one (possibly empty) sublist for each index key. * - * 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. - * Therefore, there are no empty sublists in the result. + * Example: given an index on (A,B,C), we would return ((C1 C2) () (C3 C4)) + * if we find that clauses C1 and C2 use column A, clauses C3 and C4 use + * column C, and no clauses use column B. */ List * group_clauses_by_indexkey(IndexOptInfo *index, @@ -680,11 +682,10 @@ group_clauses_by_indexkey(IndexOptInfo *index, } /* - * If no clauses match this key, we're done; we don't want to look - * at keys to its right. + * If no clauses match this key, check for amoptionalkey restriction. */ - if (clausegroup == NIL) - break; + if (clausegroup == NIL && !index->amoptionalkey && indexcol == 0) + return NIL; clausegroup_list = lappend(clausegroup_list, clausegroup); @@ -1581,11 +1582,9 @@ match_special_index_operator(Expr *clause, Oid opclass, * will know what to do with. * * The input list is ordered by index key, and so the output list is too. - * (The latter is not depended on by any part of the planner, so far as I can - * tell; but some parts of the executor do assume that the indexqual list - * ultimately delivered to the executor is so ordered. One such place is - * _bt_preprocess_keys() in the btree support. Perhaps that ought to be fixed - * someday --- tgl 7/00) + * (The latter is not depended on by any part of the core planner, I believe, + * but parts of the executor require it, and so do the amcostestimate + * functions.) */ List * expand_indexqual_conditions(IndexOptInfo *index, List *clausegroups) diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c index a8dcdae9a2f..067e9f701ca 100644 --- a/src/backend/optimizer/util/plancat.c +++ b/src/backend/optimizer/util/plancat.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.111 2005/06/05 22:32:56 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.112 2005/06/13 23:14:48 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -161,7 +161,8 @@ get_relation_info(Oid relationObjectId, RelOptInfo *rel) } info->relam = indexRelation->rd_rel->relam; - info->amcostestimate = index_cost_estimator(indexRelation); + info->amcostestimate = indexRelation->rd_am->amcostestimate; + info->amoptionalkey = indexRelation->rd_am->amoptionalkey; /* * Fetch the ordering operators associated with the index, if diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index 0b03f27c39c..204d37bf415 100644 --- a/src/backend/utils/adt/selfuncs.c +++ b/src/backend/utils/adt/selfuncs.c @@ -15,7 +15,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/utils/adt/selfuncs.c,v 1.181 2005/06/10 22:25:36 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/utils/adt/selfuncs.c,v 1.182 2005/06/13 23:14:48 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -4195,18 +4195,23 @@ string_to_bytea_const(const char *str, size_t str_len) * don't have any better idea about how to estimate. Index-type-specific * knowledge can be incorporated in the type-specific routines. * + * One bit of index-type-specific knowledge we can relatively easily use + * in genericcostestimate is the estimate of the number of index tuples + * visited. If numIndexTuples is not 0 then it is used as the estimate, + * otherwise we compute a generic estimate. + * *------------------------------------------------------------------------- */ static void genericcostestimate(PlannerInfo *root, IndexOptInfo *index, List *indexQuals, + double numIndexTuples, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation) { - double numIndexTuples; double numIndexPages; QualCost index_qual_cost; double qual_op_cost; @@ -4254,20 +4259,20 @@ genericcostestimate(PlannerInfo *root, JOIN_INNER); /* - * Estimate the number of tuples that will be visited. We do it in - * this rather peculiar-looking way in order to get the right answer - * for partial indexes. We can bound the number of tuples by the - * index size, in any case. + * If caller didn't give us an estimate, estimate the number of index + * tuples that will be visited. We do it in this rather peculiar-looking + * way in order to get the right answer for partial indexes. */ - numIndexTuples = *indexSelectivity * index->rel->tuples; - - if (numIndexTuples > index->tuples) - numIndexTuples = index->tuples; + if (numIndexTuples <= 0.0) + numIndexTuples = *indexSelectivity * index->rel->tuples; /* - * Always estimate at least one tuple is touched, even when + * We can bound the number of tuples by the index size in any case. + * Also, always estimate at least one tuple is touched, even when * indexSelectivity estimate is tiny. */ + if (numIndexTuples > index->tuples) + numIndexTuples = index->tuples; if (numIndexTuples < 1.0) numIndexTuples = 1.0; @@ -4337,8 +4342,95 @@ btcostestimate(PG_FUNCTION_ARGS) Oid relid; AttrNumber colnum; HeapTuple tuple; + double numIndexTuples; + List *indexBoundQuals; + int indexcol; + bool eqQualHere; + ListCell *l; + + /* + * For a btree scan, only leading '=' quals plus inequality quals + * for the immediately next attribute contribute to index selectivity + * (these are the "boundary quals" that determine the starting and + * stopping points of the index scan). Additional quals can suppress + * visits to the heap, so it's OK to count them in indexSelectivity, + * but they should not count for estimating numIndexTuples. So we must + * examine the given indexQuals to find out which ones count as boundary + * quals. We rely on the knowledge that they are given in index column + * order. + */ + indexBoundQuals = NIL; + indexcol = 0; + eqQualHere = false; + foreach(l, indexQuals) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); + Expr *clause; + Oid clause_op; + int op_strategy; + + Assert(IsA(rinfo, RestrictInfo)); + clause = rinfo->clause; + Assert(IsA(clause, OpExpr)); + clause_op = ((OpExpr *) clause)->opno; + if (match_index_to_operand(get_leftop(clause), indexcol, index)) + { + /* clause_op is correct */ + } + else if (match_index_to_operand(get_rightop(clause), indexcol, index)) + { + /* Must flip operator to get the opclass member */ + clause_op = get_commutator(clause_op); + } + else + { + /* Must be past the end of quals for indexcol, try next */ + if (!eqQualHere) + break; /* done if no '=' qual for indexcol */ + indexcol++; + eqQualHere = false; + if (match_index_to_operand(get_leftop(clause), indexcol, index)) + { + /* clause_op is correct */ + } + else if (match_index_to_operand(get_rightop(clause), + indexcol, index)) + { + /* Must flip operator to get the opclass member */ + clause_op = get_commutator(clause_op); + } + else + { + /* No quals for new indexcol, so we are done */ + break; + } + } + op_strategy = get_op_opclass_strategy(clause_op, + index->classlist[indexcol]); + Assert(op_strategy != 0); /* not a member of opclass?? */ + if (op_strategy == BTEqualStrategyNumber) + eqQualHere = true; + indexBoundQuals = lappend(indexBoundQuals, rinfo); + } + + /* + * If index is unique and we found an '=' clause for each column, + * we can just assume numIndexTuples = 1 and skip the expensive + * clauselist_selectivity calculations. + */ + if (index->unique && indexcol == index->ncolumns - 1 && eqQualHere) + numIndexTuples = 1.0; + else + { + Selectivity btreeSelectivity; + + btreeSelectivity = clauselist_selectivity(root, indexBoundQuals, + index->rel->relid, + JOIN_INNER); + numIndexTuples = btreeSelectivity * index->rel->tuples; + } - genericcostestimate(root, index, indexQuals, + genericcostestimate(root, index, indexQuals, numIndexTuples, indexStartupCost, indexTotalCost, indexSelectivity, indexCorrelation); @@ -4414,7 +4506,7 @@ rtcostestimate(PG_FUNCTION_ARGS) Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5); double *indexCorrelation = (double *) PG_GETARG_POINTER(6); - genericcostestimate(root, index, indexQuals, + genericcostestimate(root, index, indexQuals, 0.0, indexStartupCost, indexTotalCost, indexSelectivity, indexCorrelation); @@ -4432,7 +4524,7 @@ hashcostestimate(PG_FUNCTION_ARGS) Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5); double *indexCorrelation = (double *) PG_GETARG_POINTER(6); - genericcostestimate(root, index, indexQuals, + genericcostestimate(root, index, indexQuals, 0.0, indexStartupCost, indexTotalCost, indexSelectivity, indexCorrelation); @@ -4450,7 +4542,7 @@ gistcostestimate(PG_FUNCTION_ARGS) Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5); double *indexCorrelation = (double *) PG_GETARG_POINTER(6); - genericcostestimate(root, index, indexQuals, + genericcostestimate(root, index, indexQuals, 0.0, indexStartupCost, indexTotalCost, indexSelectivity, indexCorrelation); |