Skip to content

Commit 4b754d6

Browse files
akorotkovakorotkov
committed
Avoid full scan of GIN indexes when possible
The strategy of GIN index scan is driven by opclass-specific extract_query method. This method that needed search mode is GIN_SEARCH_MODE_ALL. This mode means that matching tuple may contain none of extracted entries. Simple example is '!term' tsquery, which doesn't need any term to exist in matching tsvector. In order to handle such scan key GIN calculates virtual entry, which contains all TIDs of all entries of attribute. In fact this is full scan of index attribute. And typically this is very slow, but allows to handle some queries correctly in GIN. However, current algorithm calculate such virtual entry for each GIN_SEARCH_MODE_ALL scan key even if they are multiple for the same attribute. This is clearly not optimal. This commit improves the situation by introduction of "exclude only" scan keys. Such scan keys are not capable to return set of matching TIDs. Instead, they are capable only to filter TIDs produced by normal scan keys. Therefore, each attribute should contain at least one normal scan key, while rest of them may be "exclude only" if search mode is GIN_SEARCH_MODE_ALL. The same optimization might be applied to the whole scan, not per-attribute. But that leads to NULL values elimination problem. There is trade-off between multiple possible ways to do this. We probably want to do this later using some cost-based decision algorithm. Discussion: https://postgr.es/m/CAOBaU_YGP5-BEt5Cc0%3DzMve92vocPzD%2BXiZgiZs1kjY0cj%3DXBg%40mail.gmail.com Author: Nikita Glukhov, Alexander Korotkov, Tom Lane, Julien Rouhaud Reviewed-by: Julien Rouhaud, Tomas Vondra, Tom Lane
1 parent 41c6f9d commit 4b754d6

File tree

10 files changed

+579
-77
lines changed

10 files changed

+579
-77
lines changed

‎contrib/pg_trgm/expected/pg_trgm.out

+101
Original file line numberDiff line numberDiff line change
@@ -3498,6 +3498,107 @@ select count(*) from test_trgm where t ~ '[qwerty]{2}-?[qwerty]{2}';
34983498
1000
34993499
(1 row)
35003500

3501+
-- check handling of indexquals that generate no searchable conditions
3502+
explain (costs off)
3503+
select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
3504+
QUERY PLAN
3505+
-----------------------------------------------------------------------------
3506+
Aggregate
3507+
-> Bitmap Heap Scan on test_trgm
3508+
Recheck Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qwerty%'::text))
3509+
-> Bitmap Index Scan on trgm_idx
3510+
Index Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qwerty%'::text))
3511+
(5 rows)
3512+
3513+
select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
3514+
count
3515+
-------
3516+
19
3517+
(1 row)
3518+
3519+
explain (costs off)
3520+
select count(*) from test_trgm where t like '%99%' and t like '%qw%';
3521+
QUERY PLAN
3522+
-------------------------------------------------------------------------
3523+
Aggregate
3524+
-> Bitmap Heap Scan on test_trgm
3525+
Recheck Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qw%'::text))
3526+
-> Bitmap Index Scan on trgm_idx
3527+
Index Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qw%'::text))
3528+
(5 rows)
3529+
3530+
select count(*) from test_trgm where t like '%99%' and t like '%qw%';
3531+
count
3532+
-------
3533+
19
3534+
(1 row)
3535+
3536+
-- ensure that pending-list items are handled correctly, too
3537+
create temp table t_test_trgm(t text COLLATE "C");
3538+
create index t_trgm_idx on t_test_trgm using gin (t gin_trgm_ops);
3539+
insert into t_test_trgm values ('qwerty99'), ('qwerty01');
3540+
explain (costs off)
3541+
select count(*) from t_test_trgm where t like '%99%' and t like '%qwerty%';
3542+
QUERY PLAN
3543+
-----------------------------------------------------------------------------
3544+
Aggregate
3545+
-> Bitmap Heap Scan on t_test_trgm
3546+
Recheck Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qwerty%'::text))
3547+
-> Bitmap Index Scan on t_trgm_idx
3548+
Index Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qwerty%'::text))
3549+
(5 rows)
3550+
3551+
select count(*) from t_test_trgm where t like '%99%' and t like '%qwerty%';
3552+
count
3553+
-------
3554+
1
3555+
(1 row)
3556+
3557+
explain (costs off)
3558+
select count(*) from t_test_trgm where t like '%99%' and t like '%qw%';
3559+
QUERY PLAN
3560+
-------------------------------------------------------------------------
3561+
Aggregate
3562+
-> Bitmap Heap Scan on t_test_trgm
3563+
Recheck Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qw%'::text))
3564+
-> Bitmap Index Scan on t_trgm_idx
3565+
Index Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qw%'::text))
3566+
(5 rows)
3567+
3568+
select count(*) from t_test_trgm where t like '%99%' and t like '%qw%';
3569+
count
3570+
-------
3571+
1
3572+
(1 row)
3573+
3574+
-- run the same queries with sequential scan to check the results
3575+
set enable_bitmapscan=off;
3576+
set enable_seqscan=on;
3577+
select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
3578+
count
3579+
-------
3580+
19
3581+
(1 row)
3582+
3583+
select count(*) from test_trgm where t like '%99%' and t like '%qw%';
3584+
count
3585+
-------
3586+
19
3587+
(1 row)
3588+
3589+
select count(*) from t_test_trgm where t like '%99%' and t like '%qwerty%';
3590+
count
3591+
-------
3592+
1
3593+
(1 row)
3594+
3595+
select count(*) from t_test_trgm where t like '%99%' and t like '%qw%';
3596+
count
3597+
-------
3598+
1
3599+
(1 row)
3600+
3601+
reset enable_bitmapscan;
35013602
create table test2(t text COLLATE "C");
35023603
insert into test2 values ('abcdef');
35033604
insert into test2 values ('quark');

‎contrib/pg_trgm/sql/pg_trgm.sql

+27
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,33 @@ select t,similarity(t,'gwertyu0988') as sml from test_trgm where t % 'gwertyu098
5555
select t,similarity(t,'gwertyu1988') as sml from test_trgm where t % 'gwertyu1988' order by sml desc, t;
5656
select count(*) from test_trgm where t ~ '[qwerty]{2}-?[qwerty]{2}';
5757

58+
-- check handling of indexquals that generate no searchable conditions
59+
explain (costs off)
60+
select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
61+
select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
62+
explain (costs off)
63+
select count(*) from test_trgm where t like '%99%' and t like '%qw%';
64+
select count(*) from test_trgm where t like '%99%' and t like '%qw%';
65+
-- ensure that pending-list items are handled correctly, too
66+
create temp table t_test_trgm(t text COLLATE "C");
67+
create index t_trgm_idx on t_test_trgm using gin (t gin_trgm_ops);
68+
insert into t_test_trgm values ('qwerty99'), ('qwerty01');
69+
explain (costs off)
70+
select count(*) from t_test_trgm where t like '%99%' and t like '%qwerty%';
71+
select count(*) from t_test_trgm where t like '%99%' and t like '%qwerty%';
72+
explain (costs off)
73+
select count(*) from t_test_trgm where t like '%99%' and t like '%qw%';
74+
select count(*) from t_test_trgm where t like '%99%' and t like '%qw%';
75+
76+
-- run the same queries with sequential scan to check the results
77+
set enable_bitmapscan=off;
78+
set enable_seqscan=on;
79+
select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
80+
select count(*) from test_trgm where t like '%99%' and t like '%qw%';
81+
select count(*) from t_test_trgm where t like '%99%' and t like '%qwerty%';
82+
select count(*) from t_test_trgm where t like '%99%' and t like '%qw%';
83+
reset enable_bitmapscan;
84+
5885
create table test2(t text COLLATE "C");
5986
insert into test2 values ('abcdef');
6087
insert into test2 values ('quark');

‎src/backend/access/gin/ginget.c

+64-20
Original file line numberDiff line numberDiff line change
@@ -528,8 +528,20 @@ startScanKey(GinState *ginstate, GinScanOpaque so, GinScanKey key)
528528
* order, until the consistent function says that none of the remaining
529529
* entries can form a match, without any items from the required set. The
530530
* rest go to the additional set.
531+
*
532+
* Exclude-only scan keys are known to have no required entries.
531533
*/
532-
if (key->nentries > 1)
534+
if (key->excludeOnly)
535+
{
536+
MemoryContextSwitchTo(so->keyCtx);
537+
538+
key->nrequired = 0;
539+
key->nadditional = key->nentries;
540+
key->additionalEntries = palloc(key->nadditional * sizeof(GinScanEntry));
541+
for (i = 0; i < key->nadditional; i++)
542+
key->additionalEntries[i] = key->scanEntry[i];
543+
}
544+
else if (key->nentries > 1)
533545
{
534546
MemoryContextSwitchTo(so->tempCtx);
535547

@@ -1008,37 +1020,52 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key,
10081020
minItem = entry->curItem;
10091021
}
10101022

1011-
if (allFinished)
1023+
if (allFinished && !key->excludeOnly)
10121024
{
10131025
/* all entries are finished */
10141026
key->isFinished = true;
10151027
return;
10161028
}
10171029

1018-
/*
1019-
* Ok, we now know that there are no matches < minItem.
1020-
*
1021-
* If minItem is lossy, it means that there were no exact items on the
1022-
* page among requiredEntries, because lossy pointers sort after exact
1023-
* items. However, there might be exact items for the same page among
1024-
* additionalEntries, so we mustn't advance past them.
1025-
*/
1026-
if (ItemPointerIsLossyPage(&minItem))
1030+
if (!key->excludeOnly)
10271031
{
1028-
if (GinItemPointerGetBlockNumber(&advancePast) <
1029-
GinItemPointerGetBlockNumber(&minItem))
1032+
/*
1033+
* For a normal scan key, we now know there are no matches < minItem.
1034+
*
1035+
* If minItem is lossy, it means that there were no exact items on the
1036+
* page among requiredEntries, because lossy pointers sort after exact
1037+
* items. However, there might be exact items for the same page among
1038+
* additionalEntries, so we mustn't advance past them.
1039+
*/
1040+
if (ItemPointerIsLossyPage(&minItem))
10301041
{
1042+
if (GinItemPointerGetBlockNumber(&advancePast) <
1043+
GinItemPointerGetBlockNumber(&minItem))
1044+
{
1045+
ItemPointerSet(&advancePast,
1046+
GinItemPointerGetBlockNumber(&minItem),
1047+
InvalidOffsetNumber);
1048+
}
1049+
}
1050+
else
1051+
{
1052+
Assert(GinItemPointerGetOffsetNumber(&minItem) > 0);
10311053
ItemPointerSet(&advancePast,
10321054
GinItemPointerGetBlockNumber(&minItem),
1033-
InvalidOffsetNumber);
1055+
OffsetNumberPrev(GinItemPointerGetOffsetNumber(&minItem)));
10341056
}
10351057
}
10361058
else
10371059
{
1038-
Assert(GinItemPointerGetOffsetNumber(&minItem) > 0);
1039-
ItemPointerSet(&advancePast,
1040-
GinItemPointerGetBlockNumber(&minItem),
1041-
OffsetNumberPrev(GinItemPointerGetOffsetNumber(&minItem)));
1060+
/*
1061+
* excludeOnly scan keys don't have any entries that are necessarily
1062+
* present in matching items. So, we consider the item just after
1063+
* advancePast.
1064+
*/
1065+
Assert(key->nrequired == 0);
1066+
ItemPointerSet(&minItem,
1067+
GinItemPointerGetBlockNumber(&advancePast),
1068+
OffsetNumberNext(GinItemPointerGetOffsetNumber(&advancePast)));
10421069
}
10431070

10441071
/*
@@ -1266,6 +1293,20 @@ scanGetItem(IndexScanDesc scan, ItemPointerData advancePast,
12661293
{
12671294
GinScanKey key = so->keys + i;
12681295

1296+
/*
1297+
* If we're considering a lossy page, skip excludeOnly keys, They
1298+
* can't exclude the whole page anyway.
1299+
*/
1300+
if (ItemPointerIsLossyPage(item) && key->excludeOnly)
1301+
{
1302+
/*
1303+
* ginNewScanKey() should never mark the first key as
1304+
* excludeOnly.
1305+
*/
1306+
Assert(i > 0);
1307+
continue;
1308+
}
1309+
12691310
/* Fetch the next item for this key that is > advancePast. */
12701311
keyGetItem(&so->ginstate, so->tempCtx, key, advancePast,
12711312
scan->xs_snapshot);
@@ -1736,11 +1777,14 @@ collectMatchesForHeapRow(IndexScanDesc scan, pendingPosition *pos)
17361777
}
17371778

17381779
/*
1739-
* Now return "true" if all scan keys have at least one matching datum
1780+
* All scan keys except excludeOnly require at least one entry to match.
1781+
* excludeOnly keys are an exception, because their implied
1782+
* GIN_CAT_EMPTY_QUERY scanEntry always matches. So return "true" if all
1783+
* non-excludeOnly scan keys have at least one match.
17401784
*/
17411785
for (i = 0; i < so->nkeys; i++)
17421786
{
1743-
if (pos->hasMatchKey[i] == false)
1787+
if (pos->hasMatchKey[i] == false && !so->keys[i].excludeOnly)
17441788
return false;
17451789
}
17461790

0 commit comments

Comments
 (0)