Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit048fffe

Browse files
committed
Stop btree indexscans upon reaching nulls in either direction.
The existing scan-direction-sensitive tests were overly complex, andfailed to stop the scan in cases where it's perfectly legitimate to do so.Per bug #6278 from Maksym Boguk.Back-patch to 8.3, which is as far back as the patch applies easily.Doesn't seem worth sweating over a relatively minor performance issue in8.2 at this late date. (But note that this was a performance regressionfrom 8.1 and before, so 8.2 is being left as an outlier.)
1 parent6cd309b commit048fffe

File tree

1 file changed

+42
-65
lines changed

1 file changed

+42
-65
lines changed

‎src/backend/access/nbtree/nbtutils.c‎

Lines changed: 42 additions & 65 deletions
Original file line numberDiff line numberDiff line change
@@ -176,11 +176,11 @@ _bt_freestack(BTStack stack)
176176
* Also, for a DESC column, we commute (flip) all the sk_strategy numbers
177177
* so that the index sorts in the desired direction.
178178
*
179-
* One key purpose of this routine is to discoverhow manyscan keys
180-
*must besatisfied to continue the scan.It also attempts to eliminate
181-
*redundantkeys and detect contradictory keys. (If the index opfamily
182-
*providesincomplete sets of cross-type operators, we may fail to detect
183-
*redundantor contradictory keys, but we can survive that.)
179+
* One key purpose of this routine is to discoverwhichscan keys must be
180+
* satisfied to continue the scan.It also attempts to eliminate redundant
181+
* keys and detect contradictory keys. (If the index opfamily provides
182+
* incomplete sets of cross-type operators, we may fail to detect redundant
183+
* or contradictory keys, but we can survive that.)
184184
*
185185
* The output keys must be sorted by index attribute. Presently we expect
186186
* (but verify) that the input keys are already so sorted --- this is done
@@ -215,6 +215,16 @@ _bt_freestack(BTStack stack)
215215
* </<= keys if we can't compare them. The logic about required keys still
216216
* works if we don't eliminate redundant keys.
217217
*
218+
* Note that the reason we need direction-sensitive required-key flags is
219+
* precisely that we may not be able to eliminate redundant keys. Suppose
220+
* we have "x > 4::int AND x > 10::bigint", and we are unable to determine
221+
* which key is more restrictive for lack of a suitable cross-type operator.
222+
* _bt_first will arbitrarily pick one of the keys to do the initial
223+
* positioning with. If it picks x > 4, then the x > 10 condition will fail
224+
* until we reach index entries > 10; but we can't stop the scan just because
225+
* x > 10 is failing. On the other hand, if we are scanning backwards, then
226+
* failure of either key is indeed enough to stop the scan.
227+
*
218228
* As a byproduct of this work, we can detect contradictory quals such
219229
* as "x = 1 AND x > 2". If we see that, we return so->qual_ok = FALSE,
220230
* indicating the scan need not be run at all since no tuples can match.
@@ -943,15 +953,16 @@ _bt_checkkeys(IndexScanDesc scan,
943953
}
944954

945955
/*
946-
* Tuple fails this qual. If it's a required qual for the current
947-
* scan direction, then we can conclude no further tuples will
948-
* pass, either.
956+
* Tuple fails this qual. If it's a required qual, then we can
957+
* conclude no further tuples will pass, either. We can stop
958+
* regardless of the scan direction, because we know that NULLs
959+
* sort to one end or the other of the range of values. If this
960+
* tuple doesn't pass, then no future ones will either, until we
961+
* reach the next set of values of the higher-order index attrs
962+
* (if any) ... and those attrs must have equality quals, else
963+
* this one wouldn't be marked required.
949964
*/
950-
if ((key->sk_flags&SK_BT_REQFWD)&&
951-
ScanDirectionIsForward(dir))
952-
*continuescan= false;
953-
elseif ((key->sk_flags&SK_BT_REQBKWD)&&
954-
ScanDirectionIsBackward(dir))
965+
if (key->sk_flags& (SK_BT_REQFWD |SK_BT_REQBKWD))
955966
*continuescan= false;
956967

957968
/*
@@ -962,32 +973,15 @@ _bt_checkkeys(IndexScanDesc scan,
962973

963974
if (isNull)
964975
{
965-
if (key->sk_flags&SK_BT_NULLS_FIRST)
966-
{
967-
/*
968-
* Since NULLs are sorted before non-NULLs, we know we have
969-
* reached the lower limit of the range of values for this
970-
* index attr.On a backward scan, we can stop if this qual
971-
* is one of the "must match" subset. On a forward scan,
972-
* however, we should keep going.
973-
*/
974-
if ((key->sk_flags&SK_BT_REQBKWD)&&
975-
ScanDirectionIsBackward(dir))
976-
*continuescan= false;
977-
}
978-
else
979-
{
980-
/*
981-
* Since NULLs are sorted after non-NULLs, we know we have
982-
* reached the upper limit of the range of values for this
983-
* index attr.On a forward scan, we can stop if this qual is
984-
* one of the "must match" subset.On a backward scan,
985-
* however, we should keep going.
986-
*/
987-
if ((key->sk_flags&SK_BT_REQFWD)&&
988-
ScanDirectionIsForward(dir))
989-
*continuescan= false;
990-
}
976+
/*
977+
* The index entry is NULL, so it must fail this qual (we assume
978+
* all btree operators are strict). Furthermore, we know that
979+
* all remaining entries with the same higher-order index attr
980+
* values must be NULLs too. So, just as above, we can stop the
981+
* scan regardless of direction, if the qual is required.
982+
*/
983+
if (key->sk_flags& (SK_BT_REQFWD |SK_BT_REQBKWD))
984+
*continuescan= false;
991985

992986
/*
993987
* In any case, this indextuple doesn't match the qual.
@@ -1066,32 +1060,15 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, TupleDesc tupdesc,
10661060

10671061
if (isNull)
10681062
{
1069-
if (subkey->sk_flags&SK_BT_NULLS_FIRST)
1070-
{
1071-
/*
1072-
* Since NULLs are sorted before non-NULLs, we know we have
1073-
* reached the lower limit of the range of values for this
1074-
* index attr. On a backward scan, we can stop if this qual is
1075-
* one of the "must match" subset.On a forward scan,
1076-
* however, we should keep going.
1077-
*/
1078-
if ((subkey->sk_flags&SK_BT_REQBKWD)&&
1079-
ScanDirectionIsBackward(dir))
1080-
*continuescan= false;
1081-
}
1082-
else
1083-
{
1084-
/*
1085-
* Since NULLs are sorted after non-NULLs, we know we have
1086-
* reached the upper limit of the range of values for this
1087-
* index attr. On a forward scan, we can stop if this qual is
1088-
* one of the "must match" subset.On a backward scan,
1089-
* however, we should keep going.
1090-
*/
1091-
if ((subkey->sk_flags&SK_BT_REQFWD)&&
1092-
ScanDirectionIsForward(dir))
1093-
*continuescan= false;
1094-
}
1063+
/*
1064+
* The index entry is NULL, so it must fail this qual (we assume
1065+
* all btree operators are strict). Furthermore, we know that
1066+
* all remaining entries with the same higher-order index attr
1067+
* values must be NULLs too. So, just as above, we can stop the
1068+
* scan regardless of direction, if the qual is required.
1069+
*/
1070+
if (subkey->sk_flags& (SK_BT_REQFWD |SK_BT_REQBKWD))
1071+
*continuescan= false;
10951072

10961073
/*
10971074
* In any case, this indextuple doesn't match the qual.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp