Attached 6th version of the patches.
On 01.08.2019 22:28, Tom Lane wrote:
Alexander Korotkov <a.korot...@postgrespro.ru> writes:
On Thu, Aug 1, 2019 at 9:59 PM Tom Lane <t...@sss.pgh.pa.us> wrote:
While I've not attempted to fix that here, I wonder whether we shouldn't
fix it by just forcing forcedRecheck to true in any case where we discard
an ALL qualifier.
+1 for setting forcedRecheck in any case we discard ALL qualifier.
ISTM, real life number of cases we can skip recheck here is
negligible. And it doesn't justify complexity.
Yeah, that was pretty much what I was thinking --- by the time we got
it fully right considering nulls and multicolumn indexes, the cases
where not rechecking could actually do something useful would be
pretty narrow. And a bitmap heap scan is always going to have to
visit the heap, IIRC, so how much could skipping the recheck really
save?
I have simplified patch #1 setting forcedRecheck for all discarded ALL quals.
(This solution is very close to the earliest unpublished version of the patch.)
More accurate recheck-forcing logic was moved into patch #2 (multicolumn
indexes were fixed). This patch also contains ginFillScanKey() refactoring
and new internal mode GIN_SEARCH_MODE_NOT_NULL that is used only for
GinScanKey.xxxConsistentFn initialization and transformed into
GIN_SEARCH_MODE_ALL before GinScanEntry initialization.
The cost estimation seems to be correct for both patch #1 and patch #2 and
left untouched since v05.
BTW, it's not particularly the fault of this patch, but: what does it
even mean to specify GIN_SEARCH_MODE_ALL with a nonzero number of keys?
It might mean we would like to see all the results, which don't
contain given key.
Ah, right, I forgot that the consistent-fn might look at the match
results.
Also I decided to go further and tried to optimize (patch #3) the case for
GIN_SEARCH_MODE_ALL with a nonzero number of keys.
Full GIN scan can be avoided in queries like this contrib/intarray query:
"arr @@ '1' AND arr @@ '!2'" (search arrays containing 1 and not containing 2).
Here we have two keys:
- key '1' with GIN_SEARCH_MODE_DEFAULT
- key '2' with GIN_SEARCH_MODE_ALL
Key '2' requires full scan that can be avoided with the forced recheck.
This query is equivalent to single-qual query "a @@ '1 & !2'" which
emits only one GIN key '1' with recheck.
Below is example for contrib/intarray operator @@:
=# CREATE EXTENSION intarray;
=# CREATE TABLE t (a int[]);
=# INSERT INTO t SELECT ARRAY[i] FROM generate_series(1, 1000000) i;
=# CREATE INDEX ON t USING gin (a gin__int_ops);
=# SET enable_seqscan = OFF;
-- master
=# EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM t WHERE a @@ '1' AND a @@ '!2';
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on t (cost=16000095.45..16007168.16 rows=5019 width=24)
(actual time=66.955..66.956 rows=1 loops=1)
Recheck Cond: ((a @@ '1'::query_int) AND (a @@ '!2'::query_int))
Heap Blocks: exact=1
Buffers: shared hit=6816
-> Bitmap Index Scan on t_a_idx (cost=0.00..16000094.19 rows=5019 width=0)
(actual time=66.950..66.950 rows=1 loops=1)
Index Cond: ((a @@ '1'::query_int) AND (a @@ '!2'::query_int))
Buffers: shared hit=6815
Planning Time: 0.086 ms
Execution Time: 67.076 ms
(9 rows)
-- equivalent single-qual query
=# EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM t WHERE a @@ '1 & !2';
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on t (cost=78.94..7141.57 rows=5025 width=24) (actual
time=0.019..0.019 rows=1 loops=1)
Recheck Cond: (a @@ '1 & !2'::query_int)
Heap Blocks: exact=1
Buffers: shared hit=8
-> Bitmap Index Scan on t_a_idx (cost=0.00..77.68 rows=5025 width=0)
(actual time=0.014..0.014 rows=1 loops=1)
Index Cond: (a @@ '1 & !2'::query_int)
Buffers: shared hit=7
Planning Time: 0.056 ms
Execution Time: 0.039 ms
(9 rows)
-- with patch #3
=# EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM t WHERE a @@ '1' AND a @@ '!2';
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on t (cost=75.45..7148.16 rows=5019 width=24) (actual
time=0.019..0.020 rows=1 loops=1)
Recheck Cond: ((a @@ '1'::query_int) AND (a @@ '!2'::query_int))
Heap Blocks: exact=1
Buffers: shared hit=6
-> Bitmap Index Scan on t_a_idx (cost=0.00..74.19 rows=5019 width=0)
(actual time=0.011..0.012 rows=1 loops=1)
Index Cond: ((a @@ '1'::query_int) AND (a @@ '!2'::query_int))
Buffers: shared hit=5
Planning Time: 0.059 ms
Execution Time: 0.040 ms
(9 rows)
Patch #3 again contains a similar ugly solution -- we have to remove already
initialized GinScanKeys with theirs GinScanEntries. GinScanEntries can be
shared, so the reference counting was added.
Also modifications of cost estimation in patch #3 are questionable.
GinQualCounts are simply not incremented when haveFullScan flag is set,
because the counters anyway will be overwritten by the caller.
--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
>From fd93922e7b2b9f64cc26767590ca610d3af117fa Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.glu...@postgrespro.ru>
Date: Thu, 1 Aug 2019 22:59:38 +0300
Subject: [PATCH 1/3] 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 | 15 ++++++---
src/backend/utils/adt/selfuncs.c | 12 ++++++-
src/include/access/gin_private.h | 1 +
src/test/regress/expected/gin.out | 30 ++++++++++++++++-
src/test/regress/sql/gin.sql | 14 +++++++-
8 files changed, 149 insertions(+), 8 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..11e7e8e 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++)
{
@@ -329,10 +330,6 @@ ginNewScanKey(IndexScanDesc scan)
searchMode > GIN_SEARCH_MODE_ALL)
searchMode = GIN_SEARCH_MODE_ALL;
- /* Non-default modes require the index to have placeholders */
- if (searchMode != GIN_SEARCH_MODE_DEFAULT)
- hasNullQuery = true;
-
/*
* In default mode, no keys means an unsatisfiable query.
*/
@@ -343,9 +340,19 @@ ginNewScanKey(IndexScanDesc scan)
so->isVoidRes = true;
break;
}
+ else if (searchMode == GIN_SEARCH_MODE_ALL)
+ {
+ so->forcedRecheck = true;
+ continue;
+ }
+
nQueryValues = 0; /* ensure sane value */
}
+ /* Non-default modes require the index to have placeholders */
+ if (searchMode != GIN_SEARCH_MODE_DEFAULT)
+ hasNullQuery = true;
+
/*
* Create GinNullCategory representation. If the extractQueryFn
* didn't create a nullFlags array, we assume everything is non-null.
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 7eba59e..1a9d76d 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -6326,6 +6326,16 @@ gincost_pattern(IndexOptInfo *index, int indexcol,
return false;
}
+ if (nentries <= 0 && searchMode == GIN_SEARCH_MODE_ALL)
+ {
+ /*
+ * GIN does not emit scan entries for empty GIN_SEARCH_MODE_ALL keys,
+ * and it can avoid full index scan if there are entries from other
+ * keys, so we can skip setting of 'haveFullScan' flag.
+ */
+ return true;
+ }
+
for (i = 0; i < nentries; i++)
{
/*
@@ -6709,7 +6719,7 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
return;
}
- if (counts.haveFullScan || indexQuals == NIL)
+ if (counts.haveFullScan || indexQuals == NIL || counts.searchEntries <= 0)
{
/*
* Full index scan will be required. We treat this as if every key in
diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h
index afb3e15..b0251f7 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..fb0d29c 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,31 @@ 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
+select * from t_gin_test_tbl where array[0] <@ i;
+ QUERY PLAN
+--------------------------------------------------------------------------------------
+ Bitmap Heap Scan on t_gin_test_tbl (cost=12.03..20.49 rows=4 width=64)
+ Recheck Cond: ('{0}'::integer[] <@ i)
+ -> Bitmap Index Scan on t_gin_test_tbl_i_j_idx (cost=0.00..12.03 rows=4 width=0)
+ 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)
+
diff --git a/src/test/regress/sql/gin.sql b/src/test/regress/sql/gin.sql
index c566e9b..aaf9c19 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,15 @@ 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
+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;
--
2.7.4
>From 6af6e2ffd5460e59d1bfd054acee427bde2ab7e9 Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.glu...@postgrespro.ru>
Date: Thu, 1 Aug 2019 18:45:41 +0300
Subject: [PATCH 2/3] Force GIN recheck more accurately
---
src/backend/access/gin/ginlogic.c | 3 +-
src/backend/access/gin/ginscan.c | 120 ++++++++++++++++++++++++++++++++------
src/include/access/gin.h | 1 +
src/test/regress/expected/gin.out | 97 +++++++++++++++++++++++-------
src/test/regress/sql/gin.sql | 68 ++++++++++++++++++---
5 files changed, 241 insertions(+), 48 deletions(-)
diff --git a/src/backend/access/gin/ginlogic.c b/src/backend/access/gin/ginlogic.c
index 8f85978..7c4805d 100644
--- a/src/backend/access/gin/ginlogic.c
+++ b/src/backend/access/gin/ginlogic.c
@@ -224,7 +224,8 @@ shimTriConsistentFn(GinScanKey key)
void
ginInitConsistentFunction(GinState *ginstate, GinScanKey key)
{
- if (key->searchMode == GIN_SEARCH_MODE_EVERYTHING)
+ if (key->searchMode == GIN_SEARCH_MODE_EVERYTHING ||
+ key->searchMode == GIN_SEARCH_MODE_NOT_NULL)
{
key->boolConsistentFn = trueConsistentFn;
key->triConsistentFn = trueTriConsistentFn;
diff --git a/src/backend/access/gin/ginscan.c b/src/backend/access/gin/ginscan.c
index 11e7e8e..f612e55 100644
--- a/src/backend/access/gin/ginscan.c
+++ b/src/backend/access/gin/ginscan.c
@@ -129,20 +129,23 @@ ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,
* Initialize the next GinScanKey using the output from the extractQueryFn
*/
static void
-ginFillScanKey(GinScanOpaque so, OffsetNumber attnum,
- StrategyNumber strategy, int32 searchMode,
+ginFillScanKey(GinScanOpaque so, GinScanKey key, bool initHiddenEntries,
+ OffsetNumber attnum, StrategyNumber strategy, int32 searchMode,
Datum query, uint32 nQueryValues,
Datum *queryValues, GinNullCategory *queryCategories,
bool *partial_matches, Pointer *extra_data)
{
- GinScanKey key = &(so->keys[so->nkeys++]);
GinState *ginstate = &so->ginstate;
uint32 nUserQueryValues = nQueryValues;
uint32 i;
+ if (key == NULL)
+ key = &(so->keys[so->nkeys++]);
+
/* Non-default search modes add one "hidden" entry to each key */
- if (searchMode != GIN_SEARCH_MODE_DEFAULT)
+ if (searchMode != GIN_SEARCH_MODE_DEFAULT && initHiddenEntries)
nQueryValues++;
+
key->nentries = nQueryValues;
key->nuserentries = nUserQueryValues;
@@ -200,6 +203,11 @@ ginFillScanKey(GinScanOpaque so, OffsetNumber attnum,
case GIN_SEARCH_MODE_EVERYTHING:
queryCategory = GIN_CAT_EMPTY_QUERY;
break;
+ case GIN_SEARCH_MODE_NOT_NULL:
+ queryCategory = GIN_CAT_EMPTY_QUERY;
+ /* use GIN_SEARCH_MODE_ALL to skip NULLs */
+ searchMode = GIN_SEARCH_MODE_ALL;
+ break;
default:
elog(ERROR, "unexpected searchMode: %d", searchMode);
queryCategory = 0; /* keep compiler quiet */
@@ -265,6 +273,9 @@ ginNewScanKey(IndexScanDesc scan)
GinScanOpaque so = (GinScanOpaque) scan->opaque;
int i;
bool hasNullQuery = false;
+ int numColsNeedNotNull = 0;
+ bool colNeedsNotNull[INDEX_MAX_KEYS] = {0};
+ bool colImpliesNotNull[INDEX_MAX_KEYS] = {0};
MemoryContext oldCtx;
/*
@@ -298,6 +309,7 @@ ginNewScanKey(IndexScanDesc scan)
bool *nullFlags = NULL;
GinNullCategory *categories;
int32 searchMode = GIN_SEARCH_MODE_DEFAULT;
+ int colno = skey->sk_attno - 1;
/*
* We assume that GIN-indexable operators are strict, so a null query
@@ -311,8 +323,8 @@ ginNewScanKey(IndexScanDesc scan)
/* OK to call the extractQueryFn */
queryValues = (Datum *)
- DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[skey->sk_attno - 1],
- so->ginstate.supportCollation[skey->sk_attno - 1],
+ DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[colno],
+ so->ginstate.supportCollation[colno],
skey->sk_argument,
PointerGetDatum(&nQueryValues),
UInt16GetDatum(skey->sk_strategy),
@@ -342,7 +354,32 @@ ginNewScanKey(IndexScanDesc scan)
}
else if (searchMode == GIN_SEARCH_MODE_ALL)
{
- so->forcedRecheck = true;
+ /*
+ * Don't emit ALL key with no entries, check only whether
+ * unconditional recheck is needed.
+ */
+ if (!so->forcedRecheck)
+ {
+ GinScanKeyData key;
+
+ ginFillScanKey(so, &key, false, skey->sk_attno,
+ skey->sk_strategy, searchMode,
+ skey->sk_argument, 0,
+ NULL, NULL, NULL, NULL);
+
+ so->forcedRecheck |= key.triConsistentFn(&key) != GIN_TRUE;
+ }
+
+ /*
+ * Increment the number of columns with NOT NULL constraints
+ * if NOT NULL is not yet implied.
+ */
+ if (!colImpliesNotNull[colno] && !colNeedsNotNull[colno])
+ {
+ colNeedsNotNull[colno] = true;
+ numColsNeedNotNull++;
+ }
+
continue;
}
@@ -373,24 +410,71 @@ ginNewScanKey(IndexScanDesc scan)
}
}
- ginFillScanKey(so, skey->sk_attno,
+ ginFillScanKey(so, NULL, true, skey->sk_attno,
skey->sk_strategy, searchMode,
skey->sk_argument, nQueryValues,
queryValues, categories,
partial_matches, extra_data);
+
+ /*
+ * Current key implies that column is NOT NULL, so decrement the number
+ * of columns with NOT NULL constraints.
+ */
+ colImpliesNotNull[colno] = true;
+
+ if (colNeedsNotNull[colno])
+ {
+ colNeedsNotNull[colno] = false;
+ numColsNeedNotNull--;
+ }
}
- /*
- * If there are no regular scan keys, generate an EVERYTHING scankey to
- * drive a full-index scan.
- */
- if (so->nkeys == 0 && !so->isVoidRes)
+ if (!so->isVoidRes)
{
- hasNullQuery = true;
- ginFillScanKey(so, FirstOffsetNumber,
- InvalidStrategy, GIN_SEARCH_MODE_EVERYTHING,
- (Datum) 0, 0,
- NULL, NULL, NULL, NULL);
+ /*
+ * If there are no regular scan keys, generate an EVERYTHING or
+ * NOT_NULL scankey to drive a full-index scan.
+ */
+ if (so->nkeys == 0)
+ {
+ hasNullQuery = true;
+
+ /* Initialize EVERYTHING key if there are no NOT NULL columns. */
+ if (!numColsNeedNotNull)
+ {
+ ginFillScanKey(so, NULL, true, FirstOffsetNumber,
+ InvalidStrategy, GIN_SEARCH_MODE_EVERYTHING,
+ (Datum) 0, 0, NULL, NULL, NULL, NULL);
+ }
+ else
+ {
+ /*
+ * Initialize only one NOT_NULL key for the first found
+ * NOT NULL column and force recheck if there are more than
+ * one NOT NULL column.
+ */
+ so->forcedRecheck |= numColsNeedNotNull > 1;
+
+ for (i = 0; i < scan->indexRelation->rd_att->natts; i++)
+ {
+ if (colNeedsNotNull[i])
+ {
+ ginFillScanKey(so, NULL, true, i + 1, InvalidStrategy,
+ GIN_SEARCH_MODE_NOT_NULL, (Datum) 0, 0,
+ NULL, NULL, NULL, NULL);
+ break;
+ }
+ }
+ }
+ }
+ else if (numColsNeedNotNull > 0)
+ {
+ /*
+ * We use recheck instead of adding NOT_NULL entries to eliminate
+ * rows with NULL columns.
+ */
+ so->forcedRecheck = true;
+ }
}
/*
diff --git a/src/include/access/gin.h b/src/include/access/gin.h
index a8eef5a..069d249 100644
--- a/src/include/access/gin.h
+++ b/src/include/access/gin.h
@@ -34,6 +34,7 @@
#define GIN_SEARCH_MODE_INCLUDE_EMPTY 1
#define GIN_SEARCH_MODE_ALL 2
#define GIN_SEARCH_MODE_EVERYTHING 3 /* for internal use only */
+#define GIN_SEARCH_MODE_NOT_NULL 4 /* for internal use only */
/*
* GinStatsData represents stats data for planner use
diff --git a/src/test/regress/expected/gin.out b/src/test/regress/expected/gin.out
index fb0d29c..5b40691 100644
--- a/src/test/regress/expected/gin.out
+++ b/src/test/regress/expected/gin.out
@@ -38,28 +38,81 @@ 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);
+insert into t_gin_test_tbl
+values
+ (null, null),
+ ('{}', null),
+ ('{1}', null),
+ ('{1,2}', null),
+ (null, '{}'),
+ (null, '{10}'),
+ ('{1,2}', '{10}'),
+ ('{2}', '{10}'),
+ ('{1,3}', '{}'),
+ ('{1,1}', '{10}');
set enable_seqscan = off;
-explain
-select * from t_gin_test_tbl where array[0] <@ i;
- QUERY PLAN
---------------------------------------------------------------------------------------
- Bitmap Heap Scan on t_gin_test_tbl (cost=12.03..20.49 rows=4 width=64)
- Recheck Cond: ('{0}'::integer[] <@ i)
- -> Bitmap Index Scan on t_gin_test_tbl_i_j_idx (cost=0.00..12.03 rows=4 width=0)
- Index Cond: (i @> '{0}'::integer[])
-(4 rows)
+explain (analyze, costs off, timing off, summary off)
+select * from t_gin_test_tbl where i @> '{}';
+ QUERY PLAN
+---------------------------------------------------------------------------
+ Bitmap Heap Scan on t_gin_test_tbl (actual rows=7 loops=1)
+ Recheck Cond: (i @> '{}'::integer[])
+ Heap Blocks: exact=1
+ -> Bitmap Index Scan on t_gin_test_tbl_i_j_idx (actual rows=7 loops=1)
+ Index Cond: (i @> '{}'::integer[])
+(5 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)
+create or replace function explain_query_json(query_sql text)
+returns table (explain_line json)
+language plpgsql as
+$$
+begin
+ return query execute 'EXPLAIN (ANALYZE, FORMAT json) ' || query_sql;
+end;
+$$;
+create or replace function execute_text_query(query_sql text)
+returns setof text
+language plpgsql
+as
+$$
+begin
+ return query execute query_sql;
+end;
+$$;
+-- check number of rows returned by index and removed by recheck
+select
+ query,
+ js->0->'Plan'->'Plans'->0->'Actual Rows' as "return by index",
+ js->0->'Plan'->'Rows Removed by Index Recheck' as "removed by recheck",
+ res as "result"
+from
+ (values
+ ($$ i @> '{}' $$),
+ ($$ j @> '{}' $$),
+ ($$ i @> '{}' and j @> '{}' $$),
+ ($$ i @> '{1}' $$),
+ ($$ i @> '{1}' and j @> '{}' $$),
+ ($$ i @> '{1}' and i @> '{}' and j @> '{}' $$),
+ ($$ j @> '{10}' $$),
+ ($$ j @> '{10}' and i @> '{}' $$),
+ ($$ j @> '{10}' and j @> '{}' and i @> '{}' $$),
+ ($$ i @> '{1}' and j @> '{10}' $$)
+ ) q(query),
+ lateral explain_query_json($$select * from t_gin_test_tbl where $$ || query) js,
+ lateral execute_text_query($$select string_agg((i, j)::text, ' ') from t_gin_test_tbl where $$ || query) res;
+ query | return by index | removed by recheck | result
+-------------------------------------------+-----------------+--------------------+-------------------------------------------------------------------------------
+ i @> '{}' | 7 | 0 | ({},) ({1},) ("{1,2}",) ("{1,2}",{10}) ({2},{10}) ("{1,3}",{}) ("{1,1}",{10})
+ j @> '{}' | 6 | 0 | (,{}) (,{10}) ("{1,2}",{10}) ({2},{10}) ("{1,3}",{}) ("{1,1}",{10})
+ i @> '{}' and j @> '{}' | 7 | 3 | ("{1,2}",{10}) ({2},{10}) ("{1,3}",{}) ("{1,1}",{10})
+ i @> '{1}' | 5 | 0 | ({1},) ("{1,2}",) ("{1,2}",{10}) ("{1,3}",{}) ("{1,1}",{10})
+ i @> '{1}' and j @> '{}' | 5 | 2 | ("{1,2}",{10}) ("{1,3}",{}) ("{1,1}",{10})
+ i @> '{1}' and i @> '{}' and j @> '{}' | 5 | 2 | ("{1,2}",{10}) ("{1,3}",{}) ("{1,1}",{10})
+ j @> '{10}' | 4 | 0 | (,{10}) ("{1,2}",{10}) ({2},{10}) ("{1,1}",{10})
+ j @> '{10}' and i @> '{}' | 4 | 1 | ("{1,2}",{10}) ({2},{10}) ("{1,1}",{10})
+ j @> '{10}' and j @> '{}' and i @> '{}' | 4 | 1 | ("{1,2}",{10}) ({2},{10}) ("{1,1}",{10})
+ i @> '{1}' and j @> '{10}' | 2 | 0 | ("{1,2}",{10}) ("{1,1}",{10})
+(10 rows)
+reset enable_seqscan;
+drop table t_gin_test_tbl;
diff --git a/src/test/regress/sql/gin.sql b/src/test/regress/sql/gin.sql
index aaf9c19..57af762 100644
--- a/src/test/regress/sql/gin.sql
+++ b/src/test/regress/sql/gin.sql
@@ -38,11 +38,65 @@ 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);
+insert into t_gin_test_tbl
+values
+ (null, null),
+ ('{}', null),
+ ('{1}', null),
+ ('{1,2}', null),
+ (null, '{}'),
+ (null, '{10}'),
+ ('{1,2}', '{10}'),
+ ('{2}', '{10}'),
+ ('{1,3}', '{}'),
+ ('{1,1}', '{10}');
+
set enable_seqscan = off;
-explain
-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;
+
+explain (analyze, costs off, timing off, summary off)
+select * from t_gin_test_tbl where i @> '{}';
+
+create or replace function explain_query_json(query_sql text)
+returns table (explain_line json)
+language plpgsql as
+$$
+begin
+ return query execute 'EXPLAIN (ANALYZE, FORMAT json) ' || query_sql;
+end;
+$$;
+
+create or replace function execute_text_query(query_sql text)
+returns setof text
+language plpgsql
+as
+$$
+begin
+ return query execute query_sql;
+end;
+$$;
+
+-- check number of rows returned by index and removed by recheck
+select
+ query,
+ js->0->'Plan'->'Plans'->0->'Actual Rows' as "return by index",
+ js->0->'Plan'->'Rows Removed by Index Recheck' as "removed by recheck",
+ res as "result"
+from
+ (values
+ ($$ i @> '{}' $$),
+ ($$ j @> '{}' $$),
+ ($$ i @> '{}' and j @> '{}' $$),
+ ($$ i @> '{1}' $$),
+ ($$ i @> '{1}' and j @> '{}' $$),
+ ($$ i @> '{1}' and i @> '{}' and j @> '{}' $$),
+ ($$ j @> '{10}' $$),
+ ($$ j @> '{10}' and i @> '{}' $$),
+ ($$ j @> '{10}' and j @> '{}' and i @> '{}' $$),
+ ($$ i @> '{1}' and j @> '{10}' $$)
+ ) q(query),
+ lateral explain_query_json($$select * from t_gin_test_tbl where $$ || query) js,
+ lateral execute_text_query($$select string_agg((i, j)::text, ' ') from t_gin_test_tbl where $$ || query) res;
+
+reset enable_seqscan;
+
+drop table t_gin_test_tbl;
--
2.7.4
>From c679bb2fe98aa4a093a73d225b77a114d554a71b Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.glu...@postgrespro.ru>
Date: Sat, 3 Aug 2019 01:59:57 +0300
Subject: [PATCH 3/3] Avoid GIN full scan for non-empty ALL keys
---
src/backend/access/gin/ginget.c | 3 +-
src/backend/access/gin/ginscan.c | 56 ++++++++++++++++++++++++++++++++---
src/backend/utils/adt/selfuncs.c | 54 +++++++++++++++++----------------
src/include/access/gin_private.h | 2 ++
src/test/regress/expected/tsearch.out | 24 +++++++++++++++
src/test/regress/sql/tsearch.sql | 7 +++++
6 files changed, 116 insertions(+), 30 deletions(-)
diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
index 65ed8b2..acc43c1 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -588,7 +588,8 @@ startScan(IndexScanDesc scan)
uint32 i;
for (i = 0; i < so->totalentries; i++)
- startScanEntry(ginstate, so->entries[i], scan->xs_snapshot);
+ if (so->entries[i]->nrefs > 0)
+ startScanEntry(ginstate, so->entries[i], scan->xs_snapshot);
if (GinFuzzySearchLimit > 0)
{
diff --git a/src/backend/access/gin/ginscan.c b/src/backend/access/gin/ginscan.c
index f612e55..605cc5f 100644
--- a/src/backend/access/gin/ginscan.c
+++ b/src/backend/access/gin/ginscan.c
@@ -87,6 +87,7 @@ ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,
queryCategory) == 0)
{
/* Successful match */
+ prevEntry->nrefs++;
return prevEntry;
}
}
@@ -94,6 +95,9 @@ ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,
/* Nope, create a new entry */
scanEntry = (GinScanEntry) palloc(sizeof(GinScanEntryData));
+
+ scanEntry->nrefs = 1;
+
scanEntry->queryKey = queryKey;
scanEntry->queryCategory = queryCategory;
scanEntry->isPartialMatch = isPartialMatch;
@@ -273,6 +277,8 @@ ginNewScanKey(IndexScanDesc scan)
GinScanOpaque so = (GinScanOpaque) scan->opaque;
int i;
bool hasNullQuery = false;
+ bool hasAllQuery = false;
+ bool hasNormalQuery = false;
int numColsNeedNotNull = 0;
bool colNeedsNotNull[INDEX_MAX_KEYS] = {0};
bool colImpliesNotNull[INDEX_MAX_KEYS] = {0};
@@ -390,6 +396,11 @@ ginNewScanKey(IndexScanDesc scan)
if (searchMode != GIN_SEARCH_MODE_DEFAULT)
hasNullQuery = true;
+ if (searchMode == GIN_SEARCH_MODE_ALL)
+ hasAllQuery = true;
+ else
+ hasNormalQuery = true;
+
/*
* Create GinNullCategory representation. If the extractQueryFn
* didn't create a nullFlags array, we assume everything is non-null.
@@ -467,13 +478,50 @@ ginNewScanKey(IndexScanDesc scan)
}
}
}
- else if (numColsNeedNotNull > 0)
+ else
{
+ if (numColsNeedNotNull > 0)
+ {
+ /*
+ * We use recheck instead of adding NOT_NULL entries to eliminate
+ * rows with NULL columns.
+ */
+ so->forcedRecheck = true;
+ }
+
/*
- * We use recheck instead of adding NOT_NULL entries to eliminate
- * rows with NULL columns.
+ * If we have both ALL and normal keys, then remove ALL keys and
+ * force recheck.
*/
- so->forcedRecheck = true;
+ if (hasAllQuery && hasNormalQuery)
+ {
+ int nkeys = so->nkeys;
+ int j = 0;
+
+ for (i = 0; i < nkeys; i++)
+ {
+ GinScanKey key = &so->keys[i];
+
+ if (key->searchMode == GIN_SEARCH_MODE_ALL)
+ {
+ /* Derefence key's entries */
+ for (int e = 0; e < key->nentries; e++)
+ key->scanEntry[e]->nrefs--;
+
+ so->nkeys--;
+ }
+ else
+ {
+ /* Move key */
+ if (i != j)
+ so->keys[j] = so->keys[i];
+
+ j++;
+ }
+ }
+
+ so->forcedRecheck = true;
+ }
}
}
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 1a9d76d..dcdd636 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -6245,6 +6245,7 @@ spgcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
typedef struct
{
bool haveFullScan;
+ bool haveNormalScan;
double partialEntries;
double exactEntries;
double searchEntries;
@@ -6326,40 +6327,42 @@ gincost_pattern(IndexOptInfo *index, int indexcol,
return false;
}
- if (nentries <= 0 && searchMode == GIN_SEARCH_MODE_ALL)
+ if (searchMode == GIN_SEARCH_MODE_ALL)
{
/*
* GIN does not emit scan entries for empty GIN_SEARCH_MODE_ALL keys,
* and it can avoid full index scan if there are entries from other
* keys, so we can skip setting of 'haveFullScan' flag.
*/
- return true;
- }
+ if (nentries <= 0)
+ return true;
- for (i = 0; i < nentries; i++)
+ counts->haveFullScan = true;
+ }
+ else
{
- /*
- * For partial match we haven't any information to estimate number of
- * matched entries in index, so, we just estimate it as 100
- */
- if (partial_matches && partial_matches[i])
- counts->partialEntries += 100;
- else
- counts->exactEntries++;
+ counts->haveNormalScan = true;
- counts->searchEntries++;
- }
+ for (i = 0; i < nentries; i++)
+ {
+ /*
+ * For partial match we haven't any information to estimate number of
+ * matched entries in index, so, we just estimate it as 100
+ */
+ if (partial_matches && partial_matches[i])
+ counts->partialEntries += 100;
+ else
+ counts->exactEntries++;
- if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
- {
- /* Treat "include empty" like an exact-match item */
- counts->exactEntries++;
- counts->searchEntries++;
- }
- else if (searchMode != GIN_SEARCH_MODE_DEFAULT)
- {
- /* It's GIN_SEARCH_MODE_ALL */
- counts->haveFullScan = true;
+ counts->searchEntries++;
+ }
+
+ if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
+ {
+ /* Treat "include empty" like an exact-match item */
+ counts->exactEntries++;
+ counts->searchEntries++;
+ }
}
return true;
@@ -6719,7 +6722,8 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
return;
}
- if (counts.haveFullScan || indexQuals == NIL || counts.searchEntries <= 0)
+ if ((counts.haveFullScan && !counts.haveNormalScan) ||
+ indexQuals == NIL || counts.searchEntries <= 0)
{
/*
* Full index scan will be required. We treat this as if every key in
diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h
index b0251f7..af05964 100644
--- a/src/include/access/gin_private.h
+++ b/src/include/access/gin_private.h
@@ -313,6 +313,8 @@ typedef struct GinScanKeyData
typedef struct GinScanEntryData
{
+ /* Number of references from GinScanKeys */
+ int nrefs;
/* query key and other information from extractQueryFn */
Datum queryKey;
GinNullCategory queryCategory;
diff --git a/src/test/regress/expected/tsearch.out b/src/test/regress/expected/tsearch.out
index 7af2899..3f19620 100644
--- a/src/test/regress/expected/tsearch.out
+++ b/src/test/regress/expected/tsearch.out
@@ -337,6 +337,30 @@ SELECT count(*) FROM test_tsvector WHERE a @@ '!no_such_lexeme';
508
(1 row)
+-- Test optimization of non-empty GIN_SEARCH_MODE_ALL queries
+EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
+SELECT * FROM test_tsvector WHERE a @@ '!qh';
+ QUERY PLAN
+-------------------------------------------------------------
+ Bitmap Heap Scan on test_tsvector (actual rows=410 loops=1)
+ Recheck Cond: (a @@ '!''qh'''::tsquery)
+ Heap Blocks: exact=25
+ -> Bitmap Index Scan on wowidx (actual rows=410 loops=1)
+ Index Cond: (a @@ '!''qh'''::tsquery)
+(5 rows)
+
+EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
+SELECT * FROM test_tsvector WHERE a @@ 'wr' AND a @@ '!qh';
+ QUERY PLAN
+------------------------------------------------------------------------------
+ Bitmap Heap Scan on test_tsvector (actual rows=60 loops=1)
+ Recheck Cond: ((a @@ '''wr'''::tsquery) AND (a @@ '!''qh'''::tsquery))
+ Rows Removed by Index Recheck: 17
+ Heap Blocks: exact=24
+ -> Bitmap Index Scan on wowidx (actual rows=77 loops=1)
+ Index Cond: ((a @@ '''wr'''::tsquery) AND (a @@ '!''qh'''::tsquery))
+(6 rows)
+
RESET enable_seqscan;
INSERT INTO test_tsvector VALUES ('???', 'DFG:1A,2B,6C,10 FGH');
SELECT * FROM ts_stat('SELECT a FROM test_tsvector') ORDER BY ndoc DESC, nentry DESC, word LIMIT 10;
diff --git a/src/test/regress/sql/tsearch.sql b/src/test/regress/sql/tsearch.sql
index ece80b9..54a5eef 100644
--- a/src/test/regress/sql/tsearch.sql
+++ b/src/test/regress/sql/tsearch.sql
@@ -111,6 +111,13 @@ SELECT count(*) FROM test_tsvector WHERE a @@ any ('{wr,qh}');
SELECT count(*) FROM test_tsvector WHERE a @@ 'no_such_lexeme';
SELECT count(*) FROM test_tsvector WHERE a @@ '!no_such_lexeme';
+-- Test optimization of non-empty GIN_SEARCH_MODE_ALL queries
+EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
+SELECT * FROM test_tsvector WHERE a @@ '!qh';
+
+EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
+SELECT * FROM test_tsvector WHERE a @@ 'wr' AND a @@ '!qh';
+
RESET enable_seqscan;
INSERT INTO test_tsvector VALUES ('???', 'DFG:1A,2B,6C,10 FGH');
--
2.7.4
