From 42f77244e75a7f82bd87ccf72bdd9d2eb2005f69 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Wed, 2 Nov 2011 13:36:31 -0400 Subject: [PATCH] Revert "Stop btree indexscans upon reaching nulls in either direction." This reverts commit 7357f92a3ef1faff0ce85f55f3c5a7f4dc820eaa. 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 30a51203ec0..3686d31b843 100644 --- 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) * 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. @@ -943,16 +933,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; /* @@ -963,15 +952,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. @@ -1049,15 +1055,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.39.5