Skip to content

Commit b3f1a13

Browse files
petergeogheganpetergeoghegan
committed
Avoid extra index searches through preprocessing.
Transform low_compare and high_compare nbtree skip array inequalities (with opclasses that offer skip support) in such a way as to allow _bt_first to consistently apply later keys when it descends the tree. This can lower the number of index searches for multi-column scans that use a ">" key on one of the index's prefix columns (or use a "<" key, when scanning backwards) when it precedes some later lower-order key. For example, an index qual "WHERE a > 5 AND b = 2" will now be converted to "WHERE a >= 6 AND b = 2" by a new preprocessing step that takes place after low_compare and high_compare have been finalized. That way, the initial call to _bt_first can use "WHERE a >= 6 AND b = 2" to find an initial position, rather than just using "WHERE a > 5" -- "b = 2" can be applied during every _bt_first call. There's a decent chance that this will allow such a scan to avoid the extra search that might otherwise be needed to determine the lowest "a" value still satisfying "WHERE a > 5". The transformation process can only lower the total number of index pages read when the use of a more restrictive set of initial positioning keys in _bt_first actually allows the scan to land on some later leaf page directly, relative to the unoptimized case (or on an earlier leaf page directly, when scanning backwards). But the savings can really add up in cases where an affected skip array comes after some other array. For example, a scan indexqual "WHERE x IN (1, 2, 3) AND y > 5 AND z = 2" can save as many as 3 _bt_first calls by applying the new transformation to its "y" array (up to 1 extra search can be avoided per "x" element). Follow-up to commit 92fe23d, which added nbtree skip scan. Author: Peter Geoghegan <pg@bowt.ie> Reviewed-By: Matthias van de Meent <boekewurm+postgres@gmail.com> Discussion: https://postgr.es/m/CAH2-Wz=FJ78K3WsF3iWNxWnUCY9f=Jdg3QPxaXE=uYUbmuRz5Q@mail.gmail.com
1 parent 21a152b commit b3f1a13

File tree

3 files changed

+211
-0
lines changed

3 files changed

+211
-0
lines changed

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

Lines changed: 180 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,6 +50,12 @@ static bool _bt_saoparray_shrink(IndexScanDesc scan, ScanKey arraysk,
5050
BTArrayKeyInfo *array, bool *qual_ok);
5151
static bool _bt_skiparray_shrink(IndexScanDesc scan, ScanKey skey,
5252
BTArrayKeyInfo *array, bool *qual_ok);
53+
static void _bt_skiparray_strat_adjust(IndexScanDesc scan, ScanKey arraysk,
54+
BTArrayKeyInfo *array);
55+
static void _bt_skiparray_strat_decrement(IndexScanDesc scan, ScanKey arraysk,
56+
BTArrayKeyInfo *array);
57+
static void _bt_skiparray_strat_increment(IndexScanDesc scan, ScanKey arraysk,
58+
BTArrayKeyInfo *array);
5359
static ScanKey _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys);
5460
static void _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap);
5561
static int _bt_num_array_keys(IndexScanDesc scan, Oid *skip_eq_ops_out,
@@ -1296,6 +1302,171 @@ _bt_skiparray_shrink(IndexScanDesc scan, ScanKey skey, BTArrayKeyInfo *array,
12961302
return true;
12971303
}
12981304

1305+
/*
1306+
* Applies the opfamily's skip support routine to convert the skip array's >
1307+
* low_compare key (if any) into a >= key, and to convert its < high_compare
1308+
* key (if any) into a <= key. Decrements the high_compare key's sk_argument,
1309+
* and/or increments the low_compare key's sk_argument (also adjusts their
1310+
* operator strategies, while changing the operator as appropriate).
1311+
*
1312+
* This optional optimization reduces the number of descents required within
1313+
* _bt_first. Whenever _bt_first is called with a skip array whose current
1314+
* array element is the sentinel value MINVAL, using a transformed >= key
1315+
* instead of using the original > key makes it safe to include lower-order
1316+
* scan keys in the insertion scan key (there must be lower-order scan keys
1317+
* after the skip array). We will avoid an extra _bt_first to find the first
1318+
* value in the index > sk_argument -- at least when the first real matching
1319+
* value in the index happens to be an exact match for the sk_argument value
1320+
* that we produced here by incrementing the original input key's sk_argument.
1321+
* (Backwards scans derive the same benefit when they encounter the sentinel
1322+
* value MAXVAL, by converting the high_compare key from < to <=.)
1323+
*
1324+
* Note: The transformation is only correct when it cannot allow the scan to
1325+
* overlook matching tuples, but we don't have enough semantic information to
1326+
* safely make sure that can't happen during scans with cross-type operators.
1327+
* That's why we'll never apply the transformation in cross-type scenarios.
1328+
* For example, if we attempted to convert "sales_ts > '2024-01-01'::date"
1329+
* into "sales_ts >= '2024-01-02'::date" given a "sales_ts" attribute whose
1330+
* input opclass is timestamp_ops, the scan would overlook almost all (or all)
1331+
* tuples for sales that fell on '2024-01-01'.
1332+
*
1333+
* Note: We can safely modify array->low_compare/array->high_compare in place
1334+
* because they just point to copies of our scan->keyData[] input scan keys
1335+
* (namely the copies returned by _bt_preprocess_array_keys to be used as
1336+
* input into the standard preprocessing steps in _bt_preprocess_keys).
1337+
* Everything will be reset if there's a rescan.
1338+
*/
1339+
static void
1340+
_bt_skiparray_strat_adjust(IndexScanDesc scan, ScanKey arraysk,
1341+
BTArrayKeyInfo *array)
1342+
{
1343+
BTScanOpaque so = (BTScanOpaque) scan->opaque;
1344+
MemoryContext oldContext;
1345+
1346+
/*
1347+
* Called last among all preprocessing steps, when the skip array's final
1348+
* low_compare and high_compare have both been chosen
1349+
*/
1350+
Assert(arraysk->sk_flags & SK_BT_SKIP);
1351+
Assert(array->num_elems == -1 && !array->null_elem && array->sksup);
1352+
1353+
oldContext = MemoryContextSwitchTo(so->arrayContext);
1354+
1355+
if (array->high_compare &&
1356+
array->high_compare->sk_strategy == BTLessStrategyNumber)
1357+
_bt_skiparray_strat_decrement(scan, arraysk, array);
1358+
1359+
if (array->low_compare &&
1360+
array->low_compare->sk_strategy == BTGreaterStrategyNumber)
1361+
_bt_skiparray_strat_increment(scan, arraysk, array);
1362+
1363+
MemoryContextSwitchTo(oldContext);
1364+
}
1365+
1366+
/*
1367+
* Convert skip array's > low_compare key into a >= key
1368+
*/
1369+
static void
1370+
_bt_skiparray_strat_decrement(IndexScanDesc scan, ScanKey arraysk,
1371+
BTArrayKeyInfo *array)
1372+
{
1373+
Relation rel = scan->indexRelation;
1374+
Oid opfamily = rel->rd_opfamily[arraysk->sk_attno - 1],
1375+
opcintype = rel->rd_opcintype[arraysk->sk_attno - 1],
1376+
leop;
1377+
RegProcedure cmp_proc;
1378+
ScanKey high_compare = array->high_compare;
1379+
Datum orig_sk_argument = high_compare->sk_argument,
1380+
new_sk_argument;
1381+
bool uflow;
1382+
1383+
Assert(high_compare->sk_strategy == BTLessStrategyNumber);
1384+
1385+
/*
1386+
* Only perform the transformation when the operator type matches the
1387+
* index attribute's input opclass type
1388+
*/
1389+
if (high_compare->sk_subtype != opcintype &&
1390+
high_compare->sk_subtype != InvalidOid)
1391+
return;
1392+
1393+
/* Decrement, handling underflow by marking the qual unsatisfiable */
1394+
new_sk_argument = array->sksup->decrement(rel, orig_sk_argument, &uflow);
1395+
if (uflow)
1396+
{
1397+
BTScanOpaque so = (BTScanOpaque) scan->opaque;
1398+
1399+
so->qual_ok = false;
1400+
return;
1401+
}
1402+
1403+
/* Look up <= operator (might fail) */
1404+
leop = get_opfamily_member(opfamily, opcintype, opcintype,
1405+
BTLessEqualStrategyNumber);
1406+
if (!OidIsValid(leop))
1407+
return;
1408+
cmp_proc = get_opcode(leop);
1409+
if (RegProcedureIsValid(cmp_proc))
1410+
{
1411+
/* Transform < high_compare key into <= key */
1412+
fmgr_info(cmp_proc, &high_compare->sk_func);
1413+
high_compare->sk_argument = new_sk_argument;
1414+
high_compare->sk_strategy = BTLessEqualStrategyNumber;
1415+
}
1416+
}
1417+
1418+
/*
1419+
* Convert skip array's < low_compare key into a <= key
1420+
*/
1421+
static void
1422+
_bt_skiparray_strat_increment(IndexScanDesc scan, ScanKey arraysk,
1423+
BTArrayKeyInfo *array)
1424+
{
1425+
Relation rel = scan->indexRelation;
1426+
Oid opfamily = rel->rd_opfamily[arraysk->sk_attno - 1],
1427+
opcintype = rel->rd_opcintype[arraysk->sk_attno - 1],
1428+
geop;
1429+
RegProcedure cmp_proc;
1430+
ScanKey low_compare = array->low_compare;
1431+
Datum orig_sk_argument = low_compare->sk_argument,
1432+
new_sk_argument;
1433+
bool oflow;
1434+
1435+
Assert(low_compare->sk_strategy == BTGreaterStrategyNumber);
1436+
1437+
/*
1438+
* Only perform the transformation when the operator type matches the
1439+
* index attribute's input opclass type
1440+
*/
1441+
if (low_compare->sk_subtype != opcintype &&
1442+
low_compare->sk_subtype != InvalidOid)
1443+
return;
1444+
1445+
/* Increment, handling overflow by marking the qual unsatisfiable */
1446+
new_sk_argument = array->sksup->increment(rel, orig_sk_argument, &oflow);
1447+
if (oflow)
1448+
{
1449+
BTScanOpaque so = (BTScanOpaque) scan->opaque;
1450+
1451+
so->qual_ok = false;
1452+
return;
1453+
}
1454+
1455+
/* Look up >= operator (might fail) */
1456+
geop = get_opfamily_member(opfamily, opcintype, opcintype,
1457+
BTGreaterEqualStrategyNumber);
1458+
if (!OidIsValid(geop))
1459+
return;
1460+
cmp_proc = get_opcode(geop);
1461+
if (RegProcedureIsValid(cmp_proc))
1462+
{
1463+
/* Transform > low_compare key into >= key */
1464+
fmgr_info(cmp_proc, &low_compare->sk_func);
1465+
low_compare->sk_argument = new_sk_argument;
1466+
low_compare->sk_strategy = BTGreaterEqualStrategyNumber;
1467+
}
1468+
}
1469+
12991470
/*
13001471
* _bt_preprocess_array_keys() -- Preprocess SK_SEARCHARRAY scan keys
13011472
*
@@ -1839,6 +2010,15 @@ _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap)
18392010
}
18402011
else
18412012
{
2013+
/*
2014+
* Any skip array low_compare and high_compare scan keys
2015+
* are now final. Transform the array's > low_compare key
2016+
* into a >= key (and < high_compare keys into a <= key).
2017+
*/
2018+
if (array->num_elems == -1 && array->sksup &&
2019+
!array->null_elem)
2020+
_bt_skiparray_strat_adjust(scan, outkey, array);
2021+
18422022
/* Match found, so done with this array */
18432023
arrayidx++;
18442024
}

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

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2589,6 +2589,27 @@ ORDER BY thousand;
25892589
1 | 1001
25902590
(1 row)
25912591

2592+
-- Skip array preprocessing increments "thousand > -1" to "thousand >= 0"
2593+
explain (costs off)
2594+
SELECT thousand, tenthous FROM tenk1
2595+
WHERE thousand > -1 AND tenthous IN (1001,3000)
2596+
ORDER BY thousand limit 2;
2597+
QUERY PLAN
2598+
--------------------------------------------------------------------------------------------------
2599+
Limit
2600+
-> Index Only Scan using tenk1_thous_tenthous on tenk1
2601+
Index Cond: ((thousand > '-1'::integer) AND (tenthous = ANY ('{1001,3000}'::integer[])))
2602+
(3 rows)
2603+
2604+
SELECT thousand, tenthous FROM tenk1
2605+
WHERE thousand > -1 AND tenthous IN (1001,3000)
2606+
ORDER BY thousand limit 2;
2607+
thousand | tenthous
2608+
----------+----------
2609+
0 | 3000
2610+
1 | 1001
2611+
(2 rows)
2612+
25922613
--
25932614
-- Check elimination of constant-NULL subexpressions
25942615
--

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

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -993,6 +993,16 @@ SELECT thousand, tenthous FROM tenk1
993993
WHERE thousand < 3 and thousand <= 2 AND tenthous = 1001
994994
ORDER BY thousand;
995995

996+
-- Skip array preprocessing increments "thousand > -1" to "thousand >= 0"
997+
explain (costs off)
998+
SELECT thousand, tenthous FROM tenk1
999+
WHERE thousand > -1 AND tenthous IN (1001,3000)
1000+
ORDER BY thousand limit 2;
1001+
1002+
SELECT thousand, tenthous FROM tenk1
1003+
WHERE thousand > -1 AND tenthous IN (1001,3000)
1004+
ORDER BY thousand limit 2;
1005+
9961006
--
9971007
-- Check elimination of constant-NULL subexpressions
9981008
--

0 commit comments

Comments
 (0)