diff options
| -rw-r--r-- | src/backend/access/nbtree/nbtsearch.c | 6 | ||||
| -rw-r--r-- | src/backend/access/nbtree/nbtutils.c | 138 | ||||
| -rw-r--r-- | src/include/access/nbtree.h | 22 |
3 files changed, 92 insertions, 74 deletions
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c index 904629af30d..8805d32de9b 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.100 2006/01/17 00:09:01 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.101 2006/01/23 22:31:40 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -509,8 +509,8 @@ _bt_first(IndexScanDesc scan, ScanDirection dir) pgstat_count_index_scan(&scan->xs_pgstat_info); /* - * Examine the scan keys and eliminate any redundant keys; also discover - * how many keys must be matched to continue the scan. + * Examine the scan keys and eliminate any redundant keys; also mark the + * keys that must be matched to continue the scan. */ _bt_preprocess_keys(scan); diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c index ddd59444e28..b715383871a 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.68 2006/01/17 00:09:01 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/access/nbtree/nbtutils.c,v 1.69 2006/01/23 22:31:40 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -178,20 +178,21 @@ _bt_formitem(IndexTuple itup) * within each attribute may be done as a byproduct of the processing here, * but no other code depends on that. * - * Aside from preparing so->keyData[], this routine sets - * so->numberOfRequiredKeys to the number of quals that must be satisfied to - * continue the scan. _bt_checkkeys uses this. For example, if the quals + * The output keys are marked with flags SK_BT_REQFWD and/or SK_BT_REQBKWD + * if they must be satisfied in order to continue the scan forward or backward + * respectively. _bt_checkkeys uses these flags. For example, if the quals * are "x = 1 AND y < 4 AND z < 5", then _bt_checkkeys will reject a tuple * (1,2,7), but we must continue the scan in case there are tuples (1,3,z). * But once we reach tuples like (1,4,z) we can stop scanning because no - * later tuples could match. This is reflected by setting - * so->numberOfRequiredKeys to 2, the number of leading keys that must be - * 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. 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. + * later tuples could match. This is reflected by marking the x and y keys, + * but not the z key, with SK_BT_REQFWD. In general, the keys for leading + * attributes with "=" keys are marked both SK_BT_REQFWD and SK_BT_REQBKWD. + * For the first attribute without an "=" key, any "<" and "<=" keys are + * marked SK_BT_REQFWD while any ">" and ">=" keys are marked SK_BT_REQBKWD. + * This can be seen to be correct 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 @@ -203,8 +204,9 @@ _bt_formitem(IndexTuple itup) * we could handle comparison of a RHS of the index datatype with a RHS of * another type, but that seems too much pain for too little gain.) So, * keys whose operator has a nondefault subtype (ie, its RHS is not of the - * index datatype) are ignored here, except for noting whether they impose - * an "=" condition or not. + * index datatype) are ignored here, except for noting whether they include + * an "=" condition or not. The logic about required keys still works if + * we don't eliminate redundant keys. * * As a byproduct of this work, we can detect contradictory quals such * as "x = 1 AND x > 2". If we see that, we return so->quals_ok = FALSE, @@ -239,7 +241,6 @@ _bt_preprocess_keys(IndexScanDesc scan) /* initialize result variables */ so->qual_ok = true; so->numberOfKeys = 0; - so->numberOfRequiredKeys = 0; scan->keys_are_unique = false; if (numberOfKeys < 1) @@ -271,8 +272,27 @@ _bt_preprocess_keys(IndexScanDesc scan) } memcpy(outkeys, inkeys, sizeof(ScanKeyData)); so->numberOfKeys = 1; - if (cur->sk_attno == 1) - so->numberOfRequiredKeys = 1; + /* We can mark the qual as required if it's for first index col */ + if (outkeys->sk_attno == 1) + { + switch (outkeys->sk_strategy) + { + case BTLessStrategyNumber: + case BTLessEqualStrategyNumber: + outkeys->sk_flags |= SK_BT_REQFWD; + break; + case BTEqualStrategyNumber: + outkeys->sk_flags |= (SK_BT_REQFWD | SK_BT_REQBKWD); + break; + case BTGreaterEqualStrategyNumber: + case BTGreaterStrategyNumber: + outkeys->sk_flags |= SK_BT_REQBKWD; + break; + default: + elog(ERROR, "unrecognized StrategyNumber: %d", + (int) outkeys->sk_strategy); + } + } return; } @@ -400,21 +420,40 @@ _bt_preprocess_keys(IndexScanDesc scan) } /* - * Emit the cleaned-up keys into the outkeys[] array. + * Emit the cleaned-up keys into the outkeys[] array, and then + * mark them if they are required. They are required (possibly + * only in one direction) if all attrs before this one had "=". */ for (j = BTMaxStrategyNumber; --j >= 0;) { if (xform[j]) - memcpy(&outkeys[new_numberOfKeys++], xform[j], - sizeof(ScanKeyData)); - } + { + ScanKey outkey = &outkeys[new_numberOfKeys++]; - /* - * If all attrs before this one had "=", include these keys into - * the required-keys count. - */ - if (priorNumberOfEqualCols == attno - 1) - so->numberOfRequiredKeys = new_numberOfKeys; + memcpy(outkey, xform[j], sizeof(ScanKeyData)); + if (priorNumberOfEqualCols == attno - 1) + { + switch (outkey->sk_strategy) + { + case BTLessStrategyNumber: + case BTLessEqualStrategyNumber: + outkey->sk_flags |= SK_BT_REQFWD; + break; + case BTEqualStrategyNumber: + outkey->sk_flags |= (SK_BT_REQFWD | + SK_BT_REQBKWD); + break; + case BTGreaterEqualStrategyNumber: + case BTGreaterStrategyNumber: + outkey->sk_flags |= SK_BT_REQBKWD; + break; + default: + elog(ERROR, "unrecognized StrategyNumber: %d", + (int) outkey->sk_strategy); + } + } + } + } /* * Exit loop here if done. @@ -578,8 +617,7 @@ _bt_checkkeys(IndexScanDesc scan, * match" subset. On a backward scan, however, we should keep * going. */ - if (ikey < so->numberOfRequiredKeys && - ScanDirectionIsForward(dir)) + if ((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsForward(dir)) *continuescan = false; /* @@ -593,45 +631,21 @@ _bt_checkkeys(IndexScanDesc scan, if (!DatumGetBool(test)) { /* - * Tuple fails this qual. If it's a required qual, then we may be - * able to conclude no further tuples will pass, either. We have - * to look at the scan direction and the qual type. - * - * Note: the only case in which we would keep going after failing - * a required qual is if there are partially-redundant quals that - * _bt_preprocess_keys() was unable to eliminate. For example, - * given "x > 4 AND x > 10" where both are cross-type comparisons - * and so not removable, we might start the scan at the x = 4 - * boundary point. The "x > 10" condition will fail until we pass - * x = 10, but we must not stop the scan on its account. + * Tuple fails this qual. If it's a required qual for the current + * scan direction, then we can conclude no further tuples will + * pass, either. * * Note: because we stop the scan as soon as any required equality * qual fails, it is critical that equality quals be used for the * initial positioning in _bt_first() when they are available. See * comments in _bt_first(). */ - if (ikey < so->numberOfRequiredKeys) - { - switch (key->sk_strategy) - { - case BTLessStrategyNumber: - case BTLessEqualStrategyNumber: - if (ScanDirectionIsForward(dir)) - *continuescan = false; - break; - case BTEqualStrategyNumber: - *continuescan = false; - break; - case BTGreaterEqualStrategyNumber: - case BTGreaterStrategyNumber: - if (ScanDirectionIsBackward(dir)) - *continuescan = false; - break; - default: - elog(ERROR, "unrecognized StrategyNumber: %d", - key->sk_strategy); - } - } + if ((key->sk_flags & SK_BT_REQFWD) && + ScanDirectionIsForward(dir)) + *continuescan = false; + else if ((key->sk_flags & SK_BT_REQBKWD) && + ScanDirectionIsBackward(dir)) + *continuescan = false; /* * In any case, this indextuple doesn't match the qual. diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h index 5a3ec5f1efe..eda7f80f5d9 100644 --- a/src/include/access/nbtree.h +++ b/src/include/access/nbtree.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/access/nbtree.h,v 1.89 2005/12/07 19:37:53 tgl Exp $ + * $PostgreSQL: pgsql/src/include/access/nbtree.h,v 1.90 2006/01/23 22:31:41 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -368,16 +368,15 @@ typedef BTStackData *BTStack; /* * BTScanOpaqueData is used to remember which buffers we're currently - * examining in the scan. We keep these buffers pinned (but not locked, - * see nbtree.c) and recorded in the opaque entry of the scan to avoid + * examining in an indexscan. Between calls to btgettuple or btgetmulti, + * we keep these buffers pinned (but not locked, see nbtree.c) to avoid * doing a ReadBuffer() for every tuple in the index. * - * And it's used to remember actual scankey info (we need it - * if some scankeys evaled at runtime). + * We also store preprocessed versions of the scan keys in this structure. + * See _bt_preprocess_keys() for details of the preprocessing. * * curHeapIptr & mrkHeapIptr are heap iptr-s from current/marked - * index tuples: we don't adjust scans on insertions (and, if LLL - * is ON, don't hold locks on index pages between passes) - we + * index tuples: we don't adjust scans on insertions - instead we * use these pointers to restore index scan positions... * - vadim 07/29/98 */ @@ -391,14 +390,19 @@ typedef struct BTScanOpaqueData /* these fields are set by _bt_preprocess_keys(): */ bool qual_ok; /* false if qual can never be satisfied */ int numberOfKeys; /* number of preprocessed scan keys */ - int numberOfRequiredKeys; /* number of keys that must be matched - * to continue the scan */ ScanKey keyData; /* array of preprocessed scan keys */ } BTScanOpaqueData; typedef BTScanOpaqueData *BTScanOpaque; /* + * We use these private sk_flags bits in preprocessed scan keys + */ +#define SK_BT_REQFWD 0x00010000 /* required to continue forward scan */ +#define SK_BT_REQBKWD 0x00020000 /* required to continue backward scan */ + + +/* * prototypes for functions in nbtree.c (external entry points for btree) */ extern Datum btbuild(PG_FUNCTION_ARGS); |