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

Commit7357f92

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 parent5093944 commit7357f92

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
@@ -174,11 +174,11 @@ _bt_freestack(BTStack stack)
174174
* Also, for a DESC column, we commute (flip) all the sk_strategy numbers
175175
* so that the index sorts in the desired direction.
176176
*
177-
* One key purpose of this routine is to discoverhow manyscan keys
178-
*must besatisfied to continue the scan.It also attempts to eliminate
179-
*redundantkeys and detect contradictory keys. (If the index opfamily
180-
*providesincomplete sets of cross-type operators, we may fail to detect
181-
*redundantor contradictory keys, but we can survive that.)
177+
* One key purpose of this routine is to discoverwhichscan keys must be
178+
* satisfied to continue the scan.It also attempts to eliminate redundant
179+
* keys and detect contradictory keys. (If the index opfamily provides
180+
* incomplete sets of cross-type operators, we may fail to detect redundant
181+
* or contradictory keys, but we can survive that.)
182182
*
183183
* The output keys must be sorted by index attribute. Presently we expect
184184
* (but verify) that the input keys are already so sorted --- this is done
@@ -213,6 +213,16 @@ _bt_freestack(BTStack stack)
213213
* </<= keys if we can't compare them. The logic about required keys still
214214
* works if we don't eliminate redundant keys.
215215
*
216+
* Note that the reason we need direction-sensitive required-key flags is
217+
* precisely that we may not be able to eliminate redundant keys. Suppose
218+
* we have "x > 4::int AND x > 10::bigint", and we are unable to determine
219+
* which key is more restrictive for lack of a suitable cross-type operator.
220+
* _bt_first will arbitrarily pick one of the keys to do the initial
221+
* positioning with. If it picks x > 4, then the x > 10 condition will fail
222+
* until we reach index entries > 10; but we can't stop the scan just because
223+
* x > 10 is failing. On the other hand, if we are scanning backwards, then
224+
* failure of either key is indeed enough to stop the scan.
225+
*
216226
* As a byproduct of this work, we can detect contradictory quals such
217227
* as "x = 1 AND x > 2". If we see that, we return so->qual_ok = FALSE,
218228
* indicating the scan need not be run at all since no tuples can match.
@@ -933,15 +943,16 @@ _bt_checkkeys(IndexScanDesc scan,
933943
}
934944

935945
/*
936-
* Tuple fails this qual. If it's a required qual for the current
937-
* scan direction, then we can conclude no further tuples will
938-
* pass, either.
946+
* Tuple fails this qual. If it's a required qual, then we can
947+
* conclude no further tuples will pass, either. We can stop
948+
* regardless of the scan direction, because we know that NULLs
949+
* sort to one end or the other of the range of values. If this
950+
* tuple doesn't pass, then no future ones will either, until we
951+
* reach the next set of values of the higher-order index attrs
952+
* (if any) ... and those attrs must have equality quals, else
953+
* this one wouldn't be marked required.
939954
*/
940-
if ((key->sk_flags&SK_BT_REQFWD)&&
941-
ScanDirectionIsForward(dir))
942-
*continuescan= false;
943-
elseif ((key->sk_flags&SK_BT_REQBKWD)&&
944-
ScanDirectionIsBackward(dir))
955+
if (key->sk_flags& (SK_BT_REQFWD |SK_BT_REQBKWD))
945956
*continuescan= false;
946957

947958
/*
@@ -952,32 +963,15 @@ _bt_checkkeys(IndexScanDesc scan,
952963

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

982976
/*
983977
* In any case, this indextuple doesn't match the qual.
@@ -1055,32 +1049,15 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, TupleDesc tupdesc,
10551049

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

10851062
/*
10861063
* In any case, this indextuple doesn't match the qual.

0 commit comments

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