From 5cd7b682427d0e912b3ddf7f4910d52089e0df71 Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Wed, 2 Nov 2011 13:33:10 -0400
Subject: [PATCH] Revert "Stop btree indexscans upon reaching nulls in either
direction."
This reverts commit 048fffed55ff1d6d346130e4a6b7be434e81e82c.
As pointed out by Naoya Anzai, we need to do more work to make that
idea handle end-of-index cases, and it is looking like too much risk
for a back-patch. So bug #6278 is only going to be fixed in HEAD.
---
src/backend/access/nbtree/nbtutils.c | 107 ++++++++++++++++-----------
1 file changed, 65 insertions(+), 42 deletions(-)
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 4dda244f01..f87eadcdec 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -176,11 +176,11 @@ _bt_freestack(BTStack stack)
* Also, for a DESC column, we commute (flip) all the sk_strategy numbers
* so that the index sorts in the desired direction.
*
- * One key purpose of this routine is to discover which scan keys must be
- * satisfied to continue the scan. It also attempts to eliminate redundant
- * keys and detect contradictory keys. (If the index opfamily provides
- * incomplete sets of cross-type operators, we may fail to detect redundant
- * or contradictory keys, but we can survive that.)
+ * One key purpose of this routine is to discover how many scan keys
+ * must be satisfied to continue the scan. It also attempts to eliminate
+ * redundant keys and detect contradictory keys. (If the index opfamily
+ * provides incomplete sets of cross-type operators, we may fail to detect
+ * redundant or contradictory keys, but we can survive that.)
*
* The output keys must be sorted by index attribute. Presently we expect
* (but verify) that the input keys are already so sorted --- this is done
@@ -215,16 +215,6 @@ _bt_freestack(BTStack stack)
* </<= keys if we can't compare them. The logic about required keys still
* works if we don't eliminate redundant keys.
*
- * Note that the reason we need direction-sensitive required-key flags is
- * precisely that we may not be able to eliminate redundant keys. Suppose
- * we have "x > 4::int AND x > 10::bigint", and we are unable to determine
- * which key is more restrictive for lack of a suitable cross-type operator.
- * _bt_first will arbitrarily pick one of the keys to do the initial
- * positioning with. If it picks x > 4, then the x > 10 condition will fail
- * until we reach index entries > 10; but we can't stop the scan just because
- * x > 10 is failing. On the other hand, if we are scanning backwards, then
- * failure of either key is indeed enough to stop the scan.
- *
* 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->qual_ok = FALSE,
* indicating the scan need not be run at all since no tuples can match.
@@ -953,16 +943,15 @@ _bt_checkkeys(IndexScanDesc scan,
}
/*
- * Tuple fails this qual. If it's a required qual, then we can
- * conclude no further tuples will pass, either. We can stop
- * regardless of the scan direction, because we know that NULLs
- * sort to one end or the other of the range of values. If this
- * tuple doesn't pass, then no future ones will either, until we
- * reach the next set of values of the higher-order index attrs
- * (if any) ... and those attrs must have equality quals, else
- * this one wouldn't be marked required.
+ * 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.
*/
- if (key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))
+ if ((key->sk_flags & SK_BT_REQFWD) &&
+ ScanDirectionIsForward(dir))
+ *continuescan = false;
+ else if ((key->sk_flags & SK_BT_REQBKWD) &&
+ ScanDirectionIsBackward(dir))
*continuescan = false;
/*
@@ -973,15 +962,32 @@ _bt_checkkeys(IndexScanDesc scan,
if (isNull)
{
- /*
- * The index entry is NULL, so it must fail this qual (we assume
- * all btree operators are strict). Furthermore, we know that
- * all remaining entries with the same higher-order index attr
- * values must be NULLs too. So, just as above, we can stop the
- * scan regardless of direction, if the qual is required.
- */
- if (key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))
- *continuescan = false;
+ if (key->sk_flags & SK_BT_NULLS_FIRST)
+ {
+ /*
+ * Since NULLs are sorted before non-NULLs, we know we have
+ * reached the lower limit of the range of values for this
+ * index attr. On a backward scan, we can stop if this qual
+ * is one of the "must match" subset. On a forward scan,
+ * however, we should keep going.
+ */
+ if ((key->sk_flags & SK_BT_REQBKWD) &&
+ ScanDirectionIsBackward(dir))
+ *continuescan = false;
+ }
+ else
+ {
+ /*
+ * Since NULLs are sorted after non-NULLs, we know we have
+ * reached the upper limit of the range of values for this
+ * index attr. On a forward scan, we can stop if this qual is
+ * one of the "must match" subset. On a backward scan,
+ * however, we should keep going.
+ */
+ if ((key->sk_flags & SK_BT_REQFWD) &&
+ ScanDirectionIsForward(dir))
+ *continuescan = false;
+ }
/*
* In any case, this indextuple doesn't match the qual.
@@ -1060,15 +1066,32 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, TupleDesc tupdesc,
if (isNull)
{
- /*
- * The index entry is NULL, so it must fail this qual (we assume
- * all btree operators are strict). Furthermore, we know that
- * all remaining entries with the same higher-order index attr
- * values must be NULLs too. So, just as above, we can stop the
- * scan regardless of direction, if the qual is required.
- */
- if (subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))
- *continuescan = false;
+ if (subkey->sk_flags & SK_BT_NULLS_FIRST)
+ {
+ /*
+ * Since NULLs are sorted before non-NULLs, we know we have
+ * reached the lower limit of the range of values for this
+ * index attr. On a backward scan, we can stop if this qual is
+ * one of the "must match" subset. On a forward scan,
+ * however, we should keep going.
+ */
+ if ((subkey->sk_flags & SK_BT_REQBKWD) &&
+ ScanDirectionIsBackward(dir))
+ *continuescan = false;
+ }
+ else
+ {
+ /*
+ * Since NULLs are sorted after non-NULLs, we know we have
+ * reached the upper limit of the range of values for this
+ * index attr. On a forward scan, we can stop if this qual is
+ * one of the "must match" subset. On a backward scan,
+ * however, we should keep going.
+ */
+ if ((subkey->sk_flags & SK_BT_REQFWD) &&
+ ScanDirectionIsForward(dir))
+ *continuescan = false;
+ }
/*
* In any case, this indextuple doesn't match the qual.
--
2.40.0