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

Commit4b754d6

Browse files
committed
Avoid full scan of GIN indexes when possible
The strategy of GIN index scan is driven by opclass-specific extract_querymethod. This method that needed search mode is GIN_SEARCH_MODE_ALL. Thismode means that matching tuple may contain none of extracted entries. Simpleexample is '!term' tsquery, which doesn't need any term to exist in matchingtsvector.In order to handle such scan key GIN calculates virtual entry, which containsall TIDs of all entries of attribute. In fact this is full scan of indexattribute. And typically this is very slow, but allows to handle some queriescorrectly in GIN. However, current algorithm calculate such virtual entry foreach GIN_SEARCH_MODE_ALL scan key even if they are multiple for the sameattribute. 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, theyare capable only to filter TIDs produced by normal scan keys. Therefore,each attribute should contain at least one normal scan key, while rest of themmay 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 betweenmultiple possible ways to do this. We probably want to do this later usingsome cost-based decision algorithm.Discussion:https://postgr.es/m/CAOBaU_YGP5-BEt5Cc0%3DzMve92vocPzD%2BXiZgiZs1kjY0cj%3DXBg%40mail.gmail.comAuthor: Nikita Glukhov, Alexander Korotkov, Tom Lane, Julien RouhaudReviewed-by: Julien Rouhaud, Tomas Vondra, Tom Lane
1 parent41c6f9d commit4b754d6

File tree

10 files changed

+579
-77
lines changed

10 files changed

+579
-77
lines changed

‎contrib/pg_trgm/expected/pg_trgm.out

Lines changed: 101 additions & 0 deletions
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

Lines changed: 27 additions & 0 deletions
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 smlfrom test_trgmwhere t %'gwertyu1988'order by smldesc, t;
5656
selectcount(*)from test_trgmwhere t ~'[qwerty]{2}-?[qwerty]{2}';
5757

58+
-- check handling of indexquals that generate no searchable conditions
59+
explain (costs off)
60+
selectcount(*)from test_trgmwhere tlike'%99%'and tlike'%qwerty%';
61+
selectcount(*)from test_trgmwhere tlike'%99%'and tlike'%qwerty%';
62+
explain (costs off)
63+
selectcount(*)from test_trgmwhere tlike'%99%'and tlike'%qw%';
64+
selectcount(*)from test_trgmwhere tlike'%99%'and tlike'%qw%';
65+
-- ensure that pending-list items are handled correctly, too
66+
create temp table t_test_trgm(ttext COLLATE"C");
67+
createindext_trgm_idxon t_test_trgm using gin (t gin_trgm_ops);
68+
insert into t_test_trgmvalues ('qwerty99'), ('qwerty01');
69+
explain (costs off)
70+
selectcount(*)from t_test_trgmwhere tlike'%99%'and tlike'%qwerty%';
71+
selectcount(*)from t_test_trgmwhere tlike'%99%'and tlike'%qwerty%';
72+
explain (costs off)
73+
selectcount(*)from t_test_trgmwhere tlike'%99%'and tlike'%qw%';
74+
selectcount(*)from t_test_trgmwhere tlike'%99%'and tlike'%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+
selectcount(*)from test_trgmwhere tlike'%99%'and tlike'%qwerty%';
80+
selectcount(*)from test_trgmwhere tlike'%99%'and tlike'%qw%';
81+
selectcount(*)from t_test_trgmwhere tlike'%99%'and tlike'%qwerty%';
82+
selectcount(*)from t_test_trgmwhere tlike'%99%'and tlike'%qw%';
83+
reset enable_bitmapscan;
84+
5885
createtabletest2(ttext COLLATE"C");
5986
insert into test2values ('abcdef');
6087
insert into test2values ('quark');

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

Lines changed: 64 additions & 20 deletions
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+
elseif (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
GinScanKeykey=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)
[8]ページ先頭
©2009-2025 Movatter.jp