aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/backend/access/nbtree/nbtsearch.c6
-rw-r--r--src/backend/access/nbtree/nbtutils.c138
-rw-r--r--src/include/access/nbtree.h22
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);