Skip to content

Commit 882368e

Browse files
tglsfdctglsfdc
committed
Fix btree stop-at-nulls logic properly.
As pointed out by Naoya Anzai, my previous try at this was a few bricks shy of a load, because I had forgotten that the initial-positioning logic might not try to skip over nulls at the end of the index the scan will start from. We ought to fix that, because it represents an unnecessary inefficiency, but first let's get the scan-stop logic back to a safe state. With this patch, we preserve the performance benefit requested in bug #6278 for the case of scanning forward into NULLs (in a NULLS LAST index), but the reverse case of scanning backward across NULLs when there's no suitable initial-positioning qual is still inefficient.
1 parent 750f70b commit 882368e

File tree

3 files changed

+156
-30
lines changed

3 files changed

+156
-30
lines changed

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

Lines changed: 78 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -609,7 +609,7 @@ _bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir)
609609
* so that the index sorts in the desired direction.
610610
*
611611
* One key purpose of this routine is to discover which scan keys must be
612-
* satisfied to continue the scan. It also attempts to eliminate redundant
612+
* satisfied to continue the scan. It also attempts to eliminate redundant
613613
* keys and detect contradictory keys. (If the index opfamily provides
614614
* incomplete sets of cross-type operators, we may fail to detect redundant
615615
* or contradictory keys, but we can survive that.)
@@ -647,15 +647,18 @@ _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
650+
* Note that one reason we need direction-sensitive required-key flags is
651651
* precisely that we may not be able to eliminate redundant keys. Suppose
652652
* we have "x > 4::int AND x > 10::bigint", and we are unable to determine
653653
* which key is more restrictive for lack of a suitable cross-type operator.
654654
* _bt_first will arbitrarily pick one of the keys to do the initial
655655
* positioning with. If it picks x > 4, then the x > 10 condition will fail
656656
* until we reach index entries > 10; but we can't stop the scan just because
657657
* 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.
658+
* failure of either key is indeed enough to stop the scan. (In general, when
659+
* inequality keys are present, the initial-positioning code only promises to
660+
* position before the first possible match, not exactly at the first match,
661+
* for a forward scan; or after the last match for a backward scan.)
659662
*
660663
* As a byproduct of this work, we can detect contradictory quals such
661664
* as "x = 1 AND x > 2". If we see that, we return so->qual_ok = FALSE,
@@ -1394,16 +1397,15 @@ _bt_checkkeys(IndexScanDesc scan,
13941397
}
13951398

13961399
/*
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.
1400+
* Tuple fails this qual. If it's a required qual for the current
1401+
* scan direction, then we can conclude no further tuples will
1402+
* pass, either.
14051403
*/
1406-
if (key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))
1404+
if ((key->sk_flags & SK_BT_REQFWD) &&
1405+
ScanDirectionIsForward(dir))
1406+
*continuescan = false;
1407+
else if ((key->sk_flags & SK_BT_REQBKWD) &&
1408+
ScanDirectionIsBackward(dir))
14071409
*continuescan = false;
14081410

14091411
/*
@@ -1414,15 +1416,38 @@ _bt_checkkeys(IndexScanDesc scan,
14141416

14151417
if (isNull)
14161418
{
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;
1419+
if (key->sk_flags & SK_BT_NULLS_FIRST)
1420+
{
1421+
/*
1422+
* Since NULLs are sorted before non-NULLs, we know we have
1423+
* reached the lower limit of the range of values for this
1424+
* index attr. On a backward scan, we can stop if this qual
1425+
* is one of the "must match" subset. We can stop regardless
1426+
* of whether the qual is > or <, so long as it's required,
1427+
* because it's not possible for any future tuples to pass.
1428+
* On a forward scan, however, we must keep going, because we
1429+
* may have initially positioned to the start of the index.
1430+
*/
1431+
if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
1432+
ScanDirectionIsBackward(dir))
1433+
*continuescan = false;
1434+
}
1435+
else
1436+
{
1437+
/*
1438+
* Since NULLs are sorted after non-NULLs, we know we have
1439+
* reached the upper limit of the range of values for this
1440+
* index attr. On a forward scan, we can stop if this qual is
1441+
* one of the "must match" subset. We can stop regardless of
1442+
* whether the qual is > or <, so long as it's required,
1443+
* because it's not possible for any future tuples to pass.
1444+
* On a backward scan, however, we must keep going, because we
1445+
* may have initially positioned to the end of the index.
1446+
*/
1447+
if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
1448+
ScanDirectionIsForward(dir))
1449+
*continuescan = false;
1450+
}
14261451

14271452
/*
14281453
* In any case, this indextuple doesn't match the qual.
@@ -1502,15 +1527,38 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, TupleDesc tupdesc,
15021527

15031528
if (isNull)
15041529
{
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;
1530+
if (subkey->sk_flags & SK_BT_NULLS_FIRST)
1531+
{
1532+
/*
1533+
* Since NULLs are sorted before non-NULLs, we know we have
1534+
* reached the lower limit of the range of values for this
1535+
* index attr. On a backward scan, we can stop if this qual
1536+
* is one of the "must match" subset. We can stop regardless
1537+
* of whether the qual is > or <, so long as it's required,
1538+
* because it's not possible for any future tuples to pass.
1539+
* On a forward scan, however, we must keep going, because we
1540+
* may have initially positioned to the start of the index.
1541+
*/
1542+
if ((subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
1543+
ScanDirectionIsBackward(dir))
1544+
*continuescan = false;
1545+
}
1546+
else
1547+
{
1548+
/*
1549+
* Since NULLs are sorted after non-NULLs, we know we have
1550+
* reached the upper limit of the range of values for this
1551+
* index attr. On a forward scan, we can stop if this qual is
1552+
* one of the "must match" subset. We can stop regardless of
1553+
* whether the qual is > or <, so long as it's required,
1554+
* because it's not possible for any future tuples to pass.
1555+
* On a backward scan, however, we must keep going, because we
1556+
* may have initially positioned to the end of the index.
1557+
*/
1558+
if ((subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
1559+
ScanDirectionIsForward(dir))
1560+
*continuescan = false;
1561+
}
15141562

15151563
/*
15161564
* In any case, this indextuple doesn't match the qual.

‎src/test/regress/expected/create_index.out

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1405,6 +1405,60 @@ SELECT count(*) FROM onek_with_null WHERE unique1 IS NULL AND unique1 > 500;
14051405
0
14061406
(1 row)
14071407

1408+
DROP INDEX onek_nulltest;
1409+
-- Check initial-positioning logic too
1410+
CREATE UNIQUE INDEX onek_nulltest ON onek_with_null (unique2);
1411+
SET enable_seqscan = OFF;
1412+
SET enable_indexscan = ON;
1413+
SET enable_bitmapscan = OFF;
1414+
SELECT unique1, unique2 FROM onek_with_null
1415+
ORDER BY unique2 LIMIT 2;
1416+
unique1 | unique2
1417+
---------+---------
1418+
| -1
1419+
147 | 0
1420+
(2 rows)
1421+
1422+
SELECT unique1, unique2 FROM onek_with_null WHERE unique2 >= -1
1423+
ORDER BY unique2 LIMIT 2;
1424+
unique1 | unique2
1425+
---------+---------
1426+
| -1
1427+
147 | 0
1428+
(2 rows)
1429+
1430+
SELECT unique1, unique2 FROM onek_with_null WHERE unique2 >= 0
1431+
ORDER BY unique2 LIMIT 2;
1432+
unique1 | unique2
1433+
---------+---------
1434+
147 | 0
1435+
931 | 1
1436+
(2 rows)
1437+
1438+
SELECT unique1, unique2 FROM onek_with_null
1439+
ORDER BY unique2 DESC LIMIT 2;
1440+
unique1 | unique2
1441+
---------+---------
1442+
|
1443+
278 | 999
1444+
(2 rows)
1445+
1446+
SELECT unique1, unique2 FROM onek_with_null WHERE unique2 >= -1
1447+
ORDER BY unique2 DESC LIMIT 2;
1448+
unique1 | unique2
1449+
---------+---------
1450+
278 | 999
1451+
0 | 998
1452+
(2 rows)
1453+
1454+
SELECT unique1, unique2 FROM onek_with_null WHERE unique2 < 999
1455+
ORDER BY unique2 DESC LIMIT 2;
1456+
unique1 | unique2
1457+
---------+---------
1458+
0 | 998
1459+
744 | 997
1460+
(2 rows)
1461+
14081462
RESET enable_seqscan;
14091463
RESET enable_indexscan;
14101464
RESET enable_bitmapscan;

‎src/test/regress/sql/create_index.sql

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -487,6 +487,30 @@ SELECT count(*) FROM onek_with_null WHERE unique1 IS NULL AND unique2 IS NOT NUL
487487
SELECT count(*) FROM onek_with_null WHERE unique1 IS NOT NULL AND unique1 > 500;
488488
SELECT count(*) FROM onek_with_null WHERE unique1 IS NULL AND unique1 > 500;
489489

490+
DROP INDEX onek_nulltest;
491+
492+
-- Check initial-positioning logic too
493+
494+
CREATE UNIQUE INDEX onek_nulltest ON onek_with_null (unique2);
495+
496+
SET enable_seqscan = OFF;
497+
SET enable_indexscan = ON;
498+
SET enable_bitmapscan = OFF;
499+
500+
SELECT unique1, unique2 FROM onek_with_null
501+
ORDER BY unique2 LIMIT 2;
502+
SELECT unique1, unique2 FROM onek_with_null WHERE unique2 >= -1
503+
ORDER BY unique2 LIMIT 2;
504+
SELECT unique1, unique2 FROM onek_with_null WHERE unique2 >= 0
505+
ORDER BY unique2 LIMIT 2;
506+
507+
SELECT unique1, unique2 FROM onek_with_null
508+
ORDER BY unique2 DESC LIMIT 2;
509+
SELECT unique1, unique2 FROM onek_with_null WHERE unique2 >= -1
510+
ORDER BY unique2 DESC LIMIT 2;
511+
SELECT unique1, unique2 FROM onek_with_null WHERE unique2 < 999
512+
ORDER BY unique2 DESC LIMIT 2;
513+
490514
RESET enable_seqscan;
491515
RESET enable_indexscan;
492516
RESET enable_bitmapscan;

0 commit comments

Comments
 (0)