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

Commit6980f81

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 parent6743a87 commit6980f81

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
@@ -608,11 +608,11 @@ _bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir)
608608
* Also, for a DESC column, we commute (flip) all the sk_strategy numbers
609609
* so that the index sorts in the desired direction.
610610
*
611-
* One key purpose of this routine is to discoverhow manyscan keys
612-
*must besatisfied to continue the scan.It also attempts to eliminate
613-
*redundantkeys and detect contradictory keys. (If the index opfamily
614-
*providesincomplete sets of cross-type operators, we may fail to detect
615-
*redundantor contradictory keys, but we can survive that.)
611+
* One key purpose of this routine is to discoverwhichscan keys must be
612+
* satisfied to continue the scan.It also attempts to eliminate redundant
613+
* keys and detect contradictory keys. (If the index opfamily provides
614+
* incomplete sets of cross-type operators, we may fail to detect redundant
615+
* or contradictory keys, but we can survive that.)
616616
*
617617
* The output keys must be sorted by index attribute. Presently we expect
618618
* (but verify) that the input keys are already so sorted --- this is done
@@ -647,6 +647,16 @@ _bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir)
647647
* </<= keys if we can't compare them. The logic about required keys still
648648
* works if we don't eliminate redundant keys.
649649
*
650+
* Note that the reason we need direction-sensitive required-key flags is
651+
* precisely that we may not be able to eliminate redundant keys. Suppose
652+
* we have "x > 4::int AND x > 10::bigint", and we are unable to determine
653+
* which key is more restrictive for lack of a suitable cross-type operator.
654+
* _bt_first will arbitrarily pick one of the keys to do the initial
655+
* positioning with. If it picks x > 4, then the x > 10 condition will fail
656+
* until we reach index entries > 10; but we can't stop the scan just because
657+
* x > 10 is failing. On the other hand, if we are scanning backwards, then
658+
* failure of either key is indeed enough to stop the scan.
659+
*
650660
* As a byproduct of this work, we can detect contradictory quals such
651661
* as "x = 1 AND x > 2". If we see that, we return so->qual_ok = FALSE,
652662
* indicating the scan need not be run at all since no tuples can match.
@@ -1384,15 +1394,16 @@ _bt_checkkeys(IndexScanDesc scan,
13841394
}
13851395

13861396
/*
1387-
* Tuple fails this qual. If it's a required qual for the current
1388-
* scan direction, then we can conclude no further tuples will
1389-
* pass, either.
1397+
* Tuple fails this qual. If it's a required qual, then we can
1398+
* conclude no further tuples will pass, either. We can stop
1399+
* regardless of the scan direction, because we know that NULLs
1400+
* sort to one end or the other of the range of values. If this
1401+
* tuple doesn't pass, then no future ones will either, until we
1402+
* reach the next set of values of the higher-order index attrs
1403+
* (if any) ... and those attrs must have equality quals, else
1404+
* this one wouldn't be marked required.
13901405
*/
1391-
if ((key->sk_flags&SK_BT_REQFWD)&&
1392-
ScanDirectionIsForward(dir))
1393-
*continuescan= false;
1394-
elseif ((key->sk_flags&SK_BT_REQBKWD)&&
1395-
ScanDirectionIsBackward(dir))
1406+
if (key->sk_flags& (SK_BT_REQFWD |SK_BT_REQBKWD))
13961407
*continuescan= false;
13971408

13981409
/*
@@ -1403,32 +1414,15 @@ _bt_checkkeys(IndexScanDesc scan,
14031414

14041415
if (isNull)
14051416
{
1406-
if (key->sk_flags&SK_BT_NULLS_FIRST)
1407-
{
1408-
/*
1409-
* Since NULLs are sorted before non-NULLs, we know we have
1410-
* reached the lower limit of the range of values for this
1411-
* index attr.On a backward scan, we can stop if this qual
1412-
* is one of the "must match" subset. On a forward scan,
1413-
* however, we should keep going.
1414-
*/
1415-
if ((key->sk_flags&SK_BT_REQBKWD)&&
1416-
ScanDirectionIsBackward(dir))
1417-
*continuescan= false;
1418-
}
1419-
else
1420-
{
1421-
/*
1422-
* Since NULLs are sorted after non-NULLs, we know we have
1423-
* reached the upper limit of the range of values for this
1424-
* index attr.On a forward scan, we can stop if this qual is
1425-
* one of the "must match" subset.On a backward scan,
1426-
* however, we should keep going.
1427-
*/
1428-
if ((key->sk_flags&SK_BT_REQFWD)&&
1429-
ScanDirectionIsForward(dir))
1430-
*continuescan= false;
1431-
}
1417+
/*
1418+
* The index entry is NULL, so it must fail this qual (we assume
1419+
* all btree operators are strict). Furthermore, we know that
1420+
* all remaining entries with the same higher-order index attr
1421+
* values must be NULLs too. So, just as above, we can stop the
1422+
* scan regardless of direction, if the qual is required.
1423+
*/
1424+
if (key->sk_flags& (SK_BT_REQFWD |SK_BT_REQBKWD))
1425+
*continuescan= false;
14321426

14331427
/*
14341428
* In any case, this indextuple doesn't match the qual.
@@ -1508,32 +1502,15 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, TupleDesc tupdesc,
15081502

15091503
if (isNull)
15101504
{
1511-
if (subkey->sk_flags&SK_BT_NULLS_FIRST)
1512-
{
1513-
/*
1514-
* Since NULLs are sorted before non-NULLs, we know we have
1515-
* reached the lower limit of the range of values for this
1516-
* index attr. On a backward scan, we can stop if this qual is
1517-
* one of the "must match" subset.On a forward scan,
1518-
* however, we should keep going.
1519-
*/
1520-
if ((subkey->sk_flags&SK_BT_REQBKWD)&&
1521-
ScanDirectionIsBackward(dir))
1522-
*continuescan= false;
1523-
}
1524-
else
1525-
{
1526-
/*
1527-
* Since NULLs are sorted after non-NULLs, we know we have
1528-
* reached the upper limit of the range of values for this
1529-
* index attr. On a forward scan, we can stop if this qual is
1530-
* one of the "must match" subset.On a backward scan,
1531-
* however, we should keep going.
1532-
*/
1533-
if ((subkey->sk_flags&SK_BT_REQFWD)&&
1534-
ScanDirectionIsForward(dir))
1535-
*continuescan= false;
1536-
}
1505+
/*
1506+
* The index entry is NULL, so it must fail this qual (we assume
1507+
* all btree operators are strict). Furthermore, we know that
1508+
* all remaining entries with the same higher-order index attr
1509+
* values must be NULLs too. So, just as above, we can stop the
1510+
* scan regardless of direction, if the qual is required.
1511+
*/
1512+
if (subkey->sk_flags& (SK_BT_REQFWD |SK_BT_REQBKWD))
1513+
*continuescan= false;
15371514

15381515
/*
15391516
* In any case, this indextuple doesn't match the qual.

0 commit comments

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