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

Commitb3f1a13

Browse files
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 thatuse 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 convertedto "WHERE a >= 6 AND b = 2" by a new preprocessing step that takes placeafter low_compare and high_compare have been finalized. That way, theinitial call to _bt_first can use "WHERE a >= 6 AND b = 2" to find aninitial position, rather than just using "WHERE a > 5" -- "b = 2" can beapplied during every _bt_first call. There's a decent chance that thiswill allow such a scan to avoid the extra search that might otherwise beneeded to determine the lowest "a" value still satisfying "WHERE a > 5".The transformation process can only lower the total number of indexpages read when the use of a more restrictive set of initial positioningkeys in _bt_first actually allows the scan to land on some later leafpage directly, relative to the unoptimized case (or on an earlier leafpage directly, when scanning backwards). But the savings can really addup 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 transformationto its "y" array (up to 1 extra search can be avoided per "x" element).Follow-up to commit92fe23d, 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 parent21a152b commitb3f1a13

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
staticbool_bt_skiparray_shrink(IndexScanDescscan,ScanKeyskey,
5252
BTArrayKeyInfo*array,bool*qual_ok);
53+
staticvoid_bt_skiparray_strat_adjust(IndexScanDescscan,ScanKeyarraysk,
54+
BTArrayKeyInfo*array);
55+
staticvoid_bt_skiparray_strat_decrement(IndexScanDescscan,ScanKeyarraysk,
56+
BTArrayKeyInfo*array);
57+
staticvoid_bt_skiparray_strat_increment(IndexScanDescscan,ScanKeyarraysk,
58+
BTArrayKeyInfo*array);
5359
staticScanKey_bt_preprocess_array_keys(IndexScanDescscan,int*new_numberOfKeys);
5460
staticvoid_bt_preprocess_array_keys_final(IndexScanDescscan,int*keyDataMap);
5561
staticint_bt_num_array_keys(IndexScanDescscan,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+
staticvoid
1340+
_bt_skiparray_strat_adjust(IndexScanDescscan,ScanKeyarraysk,
1341+
BTArrayKeyInfo*array)
1342+
{
1343+
BTScanOpaqueso= (BTScanOpaque)scan->opaque;
1344+
MemoryContextoldContext;
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+
staticvoid
1370+
_bt_skiparray_strat_decrement(IndexScanDescscan,ScanKeyarraysk,
1371+
BTArrayKeyInfo*array)
1372+
{
1373+
Relationrel=scan->indexRelation;
1374+
Oidopfamily=rel->rd_opfamily[arraysk->sk_attno-1],
1375+
opcintype=rel->rd_opcintype[arraysk->sk_attno-1],
1376+
leop;
1377+
RegProcedurecmp_proc;
1378+
ScanKeyhigh_compare=array->high_compare;
1379+
Datumorig_sk_argument=high_compare->sk_argument,
1380+
new_sk_argument;
1381+
booluflow;
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+
BTScanOpaqueso= (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+
staticvoid
1422+
_bt_skiparray_strat_increment(IndexScanDescscan,ScanKeyarraysk,
1423+
BTArrayKeyInfo*array)
1424+
{
1425+
Relationrel=scan->indexRelation;
1426+
Oidopfamily=rel->rd_opfamily[arraysk->sk_attno-1],
1427+
opcintype=rel->rd_opcintype[arraysk->sk_attno-1],
1428+
geop;
1429+
RegProcedurecmp_proc;
1430+
ScanKeylow_compare=array->low_compare;
1431+
Datumorig_sk_argument=low_compare->sk_argument,
1432+
new_sk_argument;
1433+
booloflow;
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+
BTScanOpaqueso= (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<3and thousand<=2AND tenthous=1001
994994
ORDER BY thousand;
995995

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

0 commit comments

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