Revert "Stop btree indexscans upon reaching nulls in either direction."

tglsfdc · tglsfdc · commit 9f19cc28a439 · 2011-11-02T13:37:24.000-04:00
This reverts commit d23165b. 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.
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
@@ -174,11 +174,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
@@ -213,16 +213,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.
@@ -863,16 +853,15 @@ _bt_checkkeys(IndexScanDesc scan,
 				continue;		/* tuple satisfies this qual */
 
 			/*
-			 * 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;
 
 			/*
@@ -883,15 +872,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.
@@ -969,15 +975,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.
