public inbox for [email protected]
help / color / mirror / Atom feedFrom: Nikita Glukhov <[email protected]>
Subject: [PATCH 1/5] Avoid GIN full scan for empty ALL keys
Date: Fri, 15 Nov 2019 17:15:12 +0300
---
contrib/pg_trgm/expected/pg_trgm.out | 62 ++++++++++++++++++++++++++++++++++++
contrib/pg_trgm/sql/pg_trgm.sql | 16 ++++++++++
src/backend/access/gin/ginget.c | 7 +++-
src/backend/access/gin/ginscan.c | 19 +++++++++--
src/backend/utils/adt/selfuncs.c | 28 ++++++++++++++--
src/include/access/gin_private.h | 1 +
src/test/regress/expected/gin.out | 31 +++++++++++++++++-
src/test/regress/sql/gin.sql | 15 ++++++++-
8 files changed, 170 insertions(+), 9 deletions(-)
diff --git a/contrib/pg_trgm/expected/pg_trgm.out b/contrib/pg_trgm/expected/pg_trgm.out
index b3e709f..3e5ba9b 100644
--- a/contrib/pg_trgm/expected/pg_trgm.out
+++ b/contrib/pg_trgm/expected/pg_trgm.out
@@ -3498,6 +3498,68 @@ select count(*) from test_trgm where t ~ '[qwerty]{2}-?[qwerty]{2}';
1000
(1 row)
+-- check handling of indexquals that generate no searchable conditions
+explain (costs off)
+select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
+ QUERY PLAN
+-----------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on test_trgm
+ Recheck Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qwerty%'::text))
+ -> Bitmap Index Scan on trgm_idx
+ Index Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qwerty%'::text))
+(5 rows)
+
+select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
+ count
+-------
+ 19
+(1 row)
+
+explain (costs off)
+select count(*) from test_trgm where t like '%99%' and t like '%qw%';
+ QUERY PLAN
+-------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on test_trgm
+ Recheck Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qw%'::text))
+ -> Bitmap Index Scan on trgm_idx
+ Index Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qw%'::text))
+(5 rows)
+
+select count(*) from test_trgm where t like '%99%' and t like '%qw%';
+ count
+-------
+ 19
+(1 row)
+
+-- ensure that pending-list items are handled correctly, too
+create temp table t_test_trgm(t text COLLATE "C");
+create index t_trgm_idx on t_test_trgm using gin (t gin_trgm_ops);
+insert into t_test_trgm values ('qwerty99'), ('qwerty01');
+explain (costs off)
+select count(*) from t_test_trgm where t like '%99%' and t like '%qwerty%';
+ QUERY PLAN
+-----------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on t_test_trgm
+ Recheck Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qwerty%'::text))
+ -> Bitmap Index Scan on t_trgm_idx
+ Index Cond: ((t ~~ '%99%'::text) AND (t ~~ '%qwerty%'::text))
+(5 rows)
+
+select count(*) from t_test_trgm where t like '%99%' and t like '%qwerty%';
+ count
+-------
+ 1
+(1 row)
+
+select count(*) from t_test_trgm where t like '%99%' and t like '%qw%';
+ count
+-------
+ 1
+(1 row)
+
create table test2(t text COLLATE "C");
insert into test2 values ('abcdef');
insert into test2 values ('quark');
diff --git a/contrib/pg_trgm/sql/pg_trgm.sql b/contrib/pg_trgm/sql/pg_trgm.sql
index 08459e6..dcfd3c2 100644
--- a/contrib/pg_trgm/sql/pg_trgm.sql
+++ b/contrib/pg_trgm/sql/pg_trgm.sql
@@ -55,6 +55,22 @@ select t,similarity(t,'gwertyu0988') as sml from test_trgm where t % 'gwertyu098
select t,similarity(t,'gwertyu1988') as sml from test_trgm where t % 'gwertyu1988' order by sml desc, t;
select count(*) from test_trgm where t ~ '[qwerty]{2}-?[qwerty]{2}';
+-- check handling of indexquals that generate no searchable conditions
+explain (costs off)
+select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
+select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
+explain (costs off)
+select count(*) from test_trgm where t like '%99%' and t like '%qw%';
+select count(*) from test_trgm where t like '%99%' and t like '%qw%';
+-- ensure that pending-list items are handled correctly, too
+create temp table t_test_trgm(t text COLLATE "C");
+create index t_trgm_idx on t_test_trgm using gin (t gin_trgm_ops);
+insert into t_test_trgm values ('qwerty99'), ('qwerty01');
+explain (costs off)
+select count(*) from t_test_trgm where t like '%99%' and t like '%qwerty%';
+select count(*) from t_test_trgm where t like '%99%' and t like '%qwerty%';
+select count(*) from t_test_trgm where t like '%99%' and t like '%qw%';
+
create table test2(t text COLLATE "C");
insert into test2 values ('abcdef');
insert into test2 values ('quark');
diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
index b18ae2b..65ed8b2 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -1814,7 +1814,7 @@ scanPendingInsert(IndexScanDesc scan, TIDBitmap *tbm, int64 *ntids)
* consistent functions.
*/
oldCtx = MemoryContextSwitchTo(so->tempCtx);
- recheck = false;
+ recheck = so->forcedRecheck;
match = true;
for (i = 0; i < so->nkeys; i++)
@@ -1888,9 +1888,14 @@ gingetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
{
CHECK_FOR_INTERRUPTS();
+ /* Get next item ... */
if (!scanGetItem(scan, iptr, &iptr, &recheck))
break;
+ /* ... apply forced recheck if required ... */
+ recheck |= so->forcedRecheck;
+
+ /* ... and transfer it into bitmap */
if (ItemPointerIsLossyPage(&iptr))
tbm_add_page(tbm, ItemPointerGetBlockNumber(&iptr));
else
diff --git a/src/backend/access/gin/ginscan.c b/src/backend/access/gin/ginscan.c
index 74d9821..7b8de10 100644
--- a/src/backend/access/gin/ginscan.c
+++ b/src/backend/access/gin/ginscan.c
@@ -286,6 +286,7 @@ ginNewScanKey(IndexScanDesc scan)
palloc(so->allocentries * sizeof(GinScanEntry));
so->isVoidRes = false;
+ so->forcedRecheck = false;
for (i = 0; i < scan->numberOfKeys; i++)
{
@@ -333,16 +334,28 @@ ginNewScanKey(IndexScanDesc scan)
if (searchMode != GIN_SEARCH_MODE_DEFAULT)
hasNullQuery = true;
- /*
- * In default mode, no keys means an unsatisfiable query.
- */
+ /* Special cases for queries that contain no keys */
if (queryValues == NULL || nQueryValues <= 0)
{
if (searchMode == GIN_SEARCH_MODE_DEFAULT)
{
+ /* In default mode, no keys means an unsatisfiable query */
so->isVoidRes = true;
break;
}
+ else if (searchMode == GIN_SEARCH_MODE_ALL)
+ {
+ /*
+ * The query probably matches all non-null items, but rather
+ * than scanning the index in ALL mode, we use forced rechecks
+ * to verify matches of this scankey. This wins if there are
+ * any non-ALL scankeys; otherwise we end up adding an
+ * EVERYTHING scankey below.
+ */
+ so->forcedRecheck = true;
+ continue;
+ }
+
nQueryValues = 0; /* ensure sane value */
}
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 26a2e3b..46fff24 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -6316,10 +6316,24 @@ gincost_pattern(IndexOptInfo *index, int indexcol,
PointerGetDatum(&nullFlags),
PointerGetDatum(&searchMode));
- if (nentries <= 0 && searchMode == GIN_SEARCH_MODE_DEFAULT)
+ /* Special cases for queries that contain no keys */
+ if (nentries <= 0)
{
- /* No match is possible */
- return false;
+ if (searchMode == GIN_SEARCH_MODE_DEFAULT)
+ {
+ /* In default mode, no keys means an unsatisfiable query */
+ return false;
+ }
+ else if (searchMode == GIN_SEARCH_MODE_ALL)
+ {
+ /*
+ * ginNewScanKey() does not emit scankeys for a key-less ALL
+ * query. Instead it will emit an EVERYTHING key, but only if
+ * there are no other regular keys. We don't know that yet, so
+ * postpone setting the haveFullScan flag.
+ */
+ return true;
+ }
}
for (i = 0; i < nentries; i++)
@@ -6481,6 +6495,10 @@ gincost_scalararrayopexpr(PlannerInfo *root,
/* We ignore array elements that are unsatisfiable patterns */
numPossible++;
+ /* If no regular scan keys, assume an EVERYTHING scan is needed */
+ if (elemcounts.searchEntries == 0)
+ elemcounts.haveFullScan = true;
+
if (elemcounts.haveFullScan)
{
/*
@@ -6705,6 +6723,10 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
return;
}
+ /* If no regular scan keys, assume an EVERYTHING scan is needed */
+ if (counts.searchEntries == 0)
+ counts.haveFullScan = true;
+
if (counts.haveFullScan || indexQuals == NIL)
{
/*
diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h
index 78fcd82..9d2ee3a 100644
--- a/src/include/access/gin_private.h
+++ b/src/include/access/gin_private.h
@@ -359,6 +359,7 @@ typedef struct GinScanOpaqueData
MemoryContext keyCtx; /* used to hold key and entry data */
bool isVoidRes; /* true if query is unsatisfiable */
+ bool forcedRecheck; /* must recheck all returned tuples */
} GinScanOpaqueData;
typedef GinScanOpaqueData *GinScanOpaque;
diff --git a/src/test/regress/expected/gin.out b/src/test/regress/expected/gin.out
index a3911a6..5ba96fa 100644
--- a/src/test/regress/expected/gin.out
+++ b/src/test/regress/expected/gin.out
@@ -1,7 +1,7 @@
--
-- Test GIN indexes.
--
--- There are other tests to test different GIN opclassed. This is for testing
+-- There are other tests to test different GIN opclasses. This is for testing
-- GIN itself.
-- Create and populate a test table with a GIN index.
create table gin_test_tbl(i int4[]) with (autovacuum_enabled = off);
@@ -35,3 +35,32 @@ insert into gin_test_tbl select array[1, 2, g] from generate_series(1, 1000) g;
insert into gin_test_tbl select array[1, 3, g] from generate_series(1, 1000) g;
delete from gin_test_tbl where i @> array[2];
vacuum gin_test_tbl;
+-- Test optimization of empty queries
+create temp table t_gin_test_tbl(i int4[], j int4[]);
+create index on t_gin_test_tbl using gin (i, j);
+insert into t_gin_test_tbl select array[100,g], array[200,g]
+from generate_series(1, 10) g;
+insert into t_gin_test_tbl values(array[0,0], null);
+set enable_seqscan = off;
+explain (costs off)
+select * from t_gin_test_tbl where array[0] <@ i;
+ QUERY PLAN
+---------------------------------------------------
+ Bitmap Heap Scan on t_gin_test_tbl
+ Recheck Cond: ('{0}'::integer[] <@ i)
+ -> Bitmap Index Scan on t_gin_test_tbl_i_j_idx
+ Index Cond: (i @> '{0}'::integer[])
+(4 rows)
+
+select * from t_gin_test_tbl where array[0] <@ i;
+ i | j
+-------+---
+ {0,0} |
+(1 row)
+
+select * from t_gin_test_tbl where array[0] <@ i and '{}'::int4[] <@ j;
+ i | j
+---+---
+(0 rows)
+
+reset enable_seqscan;
diff --git a/src/test/regress/sql/gin.sql b/src/test/regress/sql/gin.sql
index c566e9b..f98fb7e 100644
--- a/src/test/regress/sql/gin.sql
+++ b/src/test/regress/sql/gin.sql
@@ -1,7 +1,7 @@
--
-- Test GIN indexes.
--
--- There are other tests to test different GIN opclassed. This is for testing
+-- There are other tests to test different GIN opclasses. This is for testing
-- GIN itself.
-- Create and populate a test table with a GIN index.
@@ -34,3 +34,16 @@ insert into gin_test_tbl select array[1, 3, g] from generate_series(1, 1000) g;
delete from gin_test_tbl where i @> array[2];
vacuum gin_test_tbl;
+
+-- Test optimization of empty queries
+create temp table t_gin_test_tbl(i int4[], j int4[]);
+create index on t_gin_test_tbl using gin (i, j);
+insert into t_gin_test_tbl select array[100,g], array[200,g]
+from generate_series(1, 10) g;
+insert into t_gin_test_tbl values(array[0,0], null);
+set enable_seqscan = off;
+explain (costs off)
+select * from t_gin_test_tbl where array[0] <@ i;
+select * from t_gin_test_tbl where array[0] <@ i;
+select * from t_gin_test_tbl where array[0] <@ i and '{}'::int4[] <@ j;
+reset enable_seqscan;
--
2.7.4
--------------C5A6759166AE2CA1CB41B4D8
Content-Type: text/x-patch;
name="0002-Avoid-GIN-recheck-for-NULLs-using-new-search-mode-v08.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="0002-Avoid-GIN-recheck-for-NULLs-using-new-search-mode-v08.p";
filename*1="atch"
view thread (31+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected]
Subject: Re: [PATCH 1/5] Avoid GIN full scan for empty ALL keys
In-Reply-To: <no-message-id-1883376@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox