From: Nikita Glukhov Date: Fri, 15 Nov 2019 17:15:12 +0300 Subject: [PATCH 1/5] Avoid GIN full scan for empty ALL keys --- 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"