Attached 8th version of the patches.
A brief description of the patches and their improvements/overheads:
1. Avoid full scan in "empty-ALL AND regular" case.
One EVERYTHING entry with unconditional recheck is used instead of multiple
ALL entries.
Overhead for rechecking NULLs and "empty-ALL" keys is introduced.
Overhead of merging ALL-lists for multicolumn indexes is eliminated.
2. Fix overhead of rechecking NULLs.
Returned back overhead of merging NOT_NULL-lists for multicolumn indexes.
3. Fix overhead of unnecessary recheck of "empty-ALL" keys using consistentFn().
Performance of "empty-ALL [AND empty-ALL ...]" case now is the same as on
master.
4. Avoid full scan in "non-empty-ALL AND regular" case.
New variant of list-merging logic added to scanGetItem().
On 07.08.2019 23:32, Tom Lane wrote:
Nikita Glukhov <n.glu...@postgrespro.ru> writes:
Attached 6th version of the patches.
I spent a bit of time looking at these. Attached is a proposed revision
of the 0001 patch, with some minor changes:
* I didn't adopt your move of the "Non-default modes require the index
to have placeholders" test to after the stanza handling zero-key cases.
I think that move would be correct for 0001 as it stands, but it's far
less clear that it's still safe after 0002/0003 or whatever variant of
those we end up with. We should leave that code where it is for now,
enforcing the v1-index requirement for all non-default search modes, and
reconsider after the dust settles. (Or if we never do reconsider, it
won't be a big deal --- I doubt many v0 indexes are still out there.)
Ok.
* Rearranged the selfuncs.c logic to match ginNewScanKey better.
* Cleaned up my own sloppiness in the new gin.sql test cases.
I think this would be committable as it stands, except that replacing
an ALL scan with an EVERYTHING scan could be a performance regression
if the index contains many null items. We need to do something about
that before committing.
Yes, such performance regression does exist (see test results at the end).
And it exists not only if there are many NULLs -- recheck overhead is
significant even in the simple cases like "array @> '{}'". This really
makes patch 0001 non-committable.
And the only thing I can here offer to fix this is the patches 0002 and 0003.
Unfortunately I'm not sold on either 0002 or 0003 as they stand;
they seem overly complicated, I'm not convinced they're correct,
and you haven't really provided examples showing that all this
extra complexity is worthwhile.
Yes, they are complicated, but I tried to simplify 0002 a bit, and even
divided it into two separate patches 0002 and 0003. For the performance
improvements, see the test results at the end.
In particular:
* I don't really like the whole business about detecting a constant-true
ALL condition by applying the consistentFn at this stage. That just
feels wrong to me: the consistentFn should be expecting some data about
the index contents and we don't have any to give. If it works, it's
accidental, and probably it's fragile.
If we have no entries, then there is nothing to pass to consistentFn() and it
should always return the same value for a given scankey. The similar
technique is used in startScanKey() where the fake entryRes[] is passed to it.
Moreover, the only gain we'd get from it is maybe not having to set
forcedRecheck, and that doesn't look to me like it would make all that
much difference.
The forced recheck has a non-zero cost, so this makes real sense.
* The code seems to be assuming that a zero-key ALL query is necessarily
precisely equivalent to a NOT NULL condition. This seems flat out wrong.
At the very least it's possible for such a query to be constant-false,
rather than constant-true-for-non-null-items. Admittedly, that would
suggest rather stupid coding of the opclass query-extract function, as
it could have reported a constant-false condition in an optimizable way
rather than an unoptimizable one. But we aren't entitled to assume that
the opclass isn't being dumb; the API says it can do this, so it can.
I think we have to check the scankey regardless, either in the index or
via forcedRecheck.
Yes, empty ALL queries are equivalent to NOT NULL with or without recheck.
Patches 0001 and 0002 use unconditional forcedRecheck. Patch 0003 uses
conditional recheck depending on the result of triConsistentFn() invocation.
I added missing check for GIN_FALSE to eliminate constant-false empty
ALL queries. So, the empty ALL scankey is always checked in the index,
but only once at the initialization stage.
* I really dislike the refcount business in 0003. It's not clear why we
need that or whether it's correct, and I think it would be unmaintainable
even if it were documented (which it isn't).
ISTM we could get where we need to go in a much simpler way. A couple
of alternative ideas:
* During ginNewScanKey, separate out ALL-mode queries and don't add them
to the scankey list immediately. After examining all the keys, if we
found any normal (DEFAULT or INCLUDE_EMPTY) queries, then go ahead and
add in the ALL-mode queries so that we can check them in the index, but
don't cause a full scan. Otherwise, discard all the ALL-mode queries
and emit a NOT_NULL scan key, setting forcedRecheck so that we apply the
filtering that way.
* Or we could just discard ALL-mode queries on sight, setting
forcedRecheck always, and then emit NOT_NULL if we had any
of those and no normal queries.
I completely rewrote this logic in patch 0004, the reference counting is no
longer needed.
Non-empty ALL keys are immediately added to the list, but the initialization
of hidden ALL entries in them is postponed, and these full scan entries added
only if there are no normal keys. But if we have normal keys, then for each
ALL key enabled special list-merging logic in scanGetItem(), so the items
matching normal keys are emitted to the result even if they have no entries
required for ALL scankeys.
For example, the following intarray query
arr @@ '1' AND arr @@ '!2'
produces two 1-entry scankeys:
DEFAULT('1')
ALL('2') (previously there were 2 entries: '2' and ALL)
When the item lists for the entries '1' and '2' are merged, emitted all items
- having '1' and not having '2', without forced recheck (new logic)
- having both '1' and '2', if triConsistentFn(ALL('2')) returns not FALSE
(ordinary logic, each item must have at least one entry of each scankey)
This helps to do as much work as possible in the index, and to avoid a
unnecessary recheck.
I'm not sure that code changes in scanGetItem() are correct (especially due to
the presence of lossy items), and the whole patch 0004 was not carefully tested,
but if the performance results are interesting, I could work further on this
optimization.
The thing that seems hard to predict here is whether it is worth tracking
the presence of additional keys in the index to avoid a recheck in the
heap. It's fairly easy to imagine that for common keys, avoiding the
recheck would be a net loss because it requires more work in the index.
If we had statistics about key counts, which of course we don't, you
could imagine making this decision dynamically depending on whether an
ALL query is asking about common or uncommon keys.
BTW --- any way you slice this, it seems like we'd end up with a situation
where we never execute an ALL query against the index in the way we do
now, meaning that the relevant code in the scanning logic is dead and
could be removed. Given that, we don't really need a new NOT_NULL search
mode; we could just redefine what ALL mode actually does at execution.
This would be good IMO, because it's not obvious what the difference
between ALL and NOT_NULL modes is anyway.
The ALL mode is still used now for non-empty ALL queries without normal queries.
Simple performance test:
create table t (a int[], b int[], c int[]);
-- 1M NULLs
insert into t select NULL, NULL, NULL
from generate_series(0, 999999) i;
-- 1M 1-element arrays
insert into t select array[i], array[i], array[i]
from generate_series(0, 999999) i;
-- 10k 2-element arrays with common element
insert into t select array[-1,i], array[-1,i], array[-1,i]
from generate_series(0, 9999) i;
create extension intarray;
create index on t using gin (a gin__int_ops, b gin__int_ops, c gin__int_ops);
| Query time, ms
WHERE condition | master | patches
| | #1 | #2 | #3 | #4
---------------------------------------+--------+------+------+------+------
a @> '{}' | 272 | 473 | 369 | 271 | 261
a @> '{}' and b @> '{}' | 374 | 548 | 523 | 368 | 353
a @> '{}' and b @> '{}' and c @> '{}' | 479 | 602 | 665 | 461 | 446
a @> '{}' and a @@ '1' | 52.2 | 0.4 | 0.4 | 0.4 | 0.4
a @> '{}' and a @@ '-1' | 56.2 | 4.0 | 4.0 | 2.3 | 2.3
a @@ '!-1' and a @@ '1' | 52.8 | 53.0 | 52.7 | 52.9 | 0.3
a @@ '!1' and a @@ '-1' | 54.9 | 55.2 | 55.1 | 55.3 | 2.4
--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
>From 2628f94b2367bffbb5cfa304a79e7a76608f97c4 Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.glu...@postgrespro.ru>
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
>From 7e6c1cb9fe7468328683fa6d5f68cc5c8743f036 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/5] Avoid GIN recheck for NULLs using new search mode
---
src/backend/access/gin/ginlogic.c | 3 +-
src/backend/access/gin/ginscan.c | 95 ++++++++++++++++++++++++++-------------
src/include/access/gin.h | 1 +
src/test/regress/expected/gin.out | 86 ++++++++++++++++++++++++++++++++---
src/test/regress/sql/gin.sql | 63 ++++++++++++++++++++++++--
5 files changed, 206 insertions(+), 42 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 7b8de10..903891f 100644
--- a/src/backend/access/gin/ginscan.c
+++ b/src/backend/access/gin/ginscan.c
@@ -200,6 +200,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 +270,8 @@ ginNewScanKey(IndexScanDesc scan)
GinScanOpaque so = (GinScanOpaque) scan->opaque;
int i;
bool hasNullQuery = false;
+ bool colNotNull[INDEX_MAX_KEYS] = {0};
+ int numNotNullKeys = 0;
MemoryContext oldCtx;
/*
@@ -298,6 +305,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 +319,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),
@@ -349,10 +357,17 @@ ginNewScanKey(IndexScanDesc scan)
* 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.
+ * any non-ALL scankeys; otherwise we end up adding a NOT_NULL
+ * scankey below.
*/
so->forcedRecheck = true;
+
+ /*
+ * Increment the number of columns with NOT NULL constraints.
+ */
+ colNotNull[colno] = true;
+ numNotNullKeys++;
+
continue;
}
@@ -386,35 +401,53 @@ ginNewScanKey(IndexScanDesc scan)
partial_matches, extra_data);
}
- /*
- * 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 one EVERYTHING or
+ * several NOT_NULL scankeys to drive a full-index scan.
+ */
+ if (so->nkeys == 0)
+ {
+ hasNullQuery = true;
- /*
- * If the index is version 0, it may be missing null and placeholder
- * entries, which would render searches for nulls and full-index scans
- * unreliable. Throw an error if so.
- */
- if (hasNullQuery && !so->isVoidRes)
- {
- GinStatsData ginStats;
-
- ginGetStats(scan->indexRelation, &ginStats);
- if (ginStats.ginVersion < 1)
- ereport(ERROR,
- (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
- errmsg("old GIN indexes do not support whole-index scans nor searches for nulls"),
- errhint("To fix this, do REINDEX INDEX \"%s\".",
- RelationGetRelationName(scan->indexRelation))));
+ /* Initialize EVERYTHING key if there are no non-NULL columns. */
+ if (!numNotNullKeys)
+ {
+ ginFillScanKey(so, FirstOffsetNumber, InvalidStrategy,
+ GIN_SEARCH_MODE_EVERYTHING, (Datum) 0, 0,
+ NULL, NULL, NULL, NULL);
+ }
+ else
+ {
+ /* Initialize NOT_NULL key for each non-NULL column. */
+ for (i = 0; i < scan->indexRelation->rd_att->natts; i++)
+ {
+ if (colNotNull[i])
+ ginFillScanKey(so, i + 1, InvalidStrategy,
+ GIN_SEARCH_MODE_NOT_NULL, (Datum) 0, 0,
+ NULL, NULL, NULL, NULL);
+ }
+ }
+ }
+
+ /*
+ * If the index is version 0, it may be missing null and placeholder
+ * entries, which would render searches for nulls and full-index scans
+ * unreliable. Throw an error if so.
+ */
+ if (hasNullQuery)
+ {
+ GinStatsData ginStats;
+
+ ginGetStats(scan->indexRelation, &ginStats);
+ if (ginStats.ginVersion < 1)
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("old GIN indexes do not support whole-index scans nor searches for nulls"),
+ errhint("To fix this, do REINDEX INDEX \"%s\".",
+ RelationGetRelationName(scan->indexRelation))));
+ }
}
MemoryContextSwitchTo(oldCtx);
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 5ba96fa..12a64eb 100644
--- a/src/test/regress/expected/gin.out
+++ b/src/test/regress/expected/gin.out
@@ -38,9 +38,18 @@ 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 (costs off)
select * from t_gin_test_tbl where array[0] <@ i;
@@ -53,14 +62,77 @@ select * from t_gin_test_tbl where array[0] <@ i;
(4 rows)
select * from t_gin_test_tbl where array[0] <@ i;
- i | j
--------+---
- {0,0} |
-(1 row)
+ i | j
+---+---
+(0 rows)
select * from t_gin_test_tbl where array[0] <@ i and '{}'::int4[] <@ j;
i | j
---+---
(0 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)
+
+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 @> '{}' | 4 | 0 | ("{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 f98fb7e..e0700c3 100644
--- a/src/test/regress/sql/gin.sql
+++ b/src/test/regress/sql/gin.sql
@@ -38,12 +38,69 @@ 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 (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;
+
+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 8ab99c472801eab2bf10dea2c895b7b2716dec06 Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.glu...@postgrespro.ru>
Date: Fri, 22 Nov 2019 03:24:09 +0300
Subject: [PATCH 3/5] Force GIN recheck for empty ALL keys more accurately
---
src/backend/access/gin/ginscan.c | 81 +++++++++++++++++++++++++++++++---------
1 file changed, 64 insertions(+), 17 deletions(-)
diff --git a/src/backend/access/gin/ginscan.c b/src/backend/access/gin/ginscan.c
index 903891f..47beef3 100644
--- a/src/backend/access/gin/ginscan.c
+++ b/src/backend/access/gin/ginscan.c
@@ -129,19 +129,21 @@ 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;
@@ -270,8 +272,14 @@ ginNewScanKey(IndexScanDesc scan)
GinScanOpaque so = (GinScanOpaque) scan->opaque;
int i;
bool hasNullQuery = false;
- bool colNotNull[INDEX_MAX_KEYS] = {0};
- int numNotNullKeys = 0;
+ /*
+ * GIN_FALSE - column has no search keys
+ * GIN_TRUE - NOT NULL is implied by some non-empty search key
+ * GIN_MAYBE - NOT NULL is implied by some empty ALL key
+ */
+ GinTernaryValue colNotNull[INDEX_MAX_KEYS] = {0};
+ /* Number of GIN_MAYBE values in colNotNull[] */
+ int colNotNullCount = 0;
MemoryContext oldCtx;
/*
@@ -360,13 +368,34 @@ ginNewScanKey(IndexScanDesc scan)
* any non-ALL scankeys; otherwise we end up adding a NOT_NULL
* scankey below.
*/
- so->forcedRecheck = true;
+ GinScanKeyData key;
+ GinTernaryValue res;
+
+ /* Check whether unconditional recheck is needed. */
+ ginFillScanKey(so, &key, false, skey->sk_attno,
+ skey->sk_strategy, searchMode,
+ skey->sk_argument, 0,
+ NULL, NULL, NULL, NULL);
+
+ res = key.triConsistentFn(&key);
+
+ if (res == GIN_FALSE)
+ {
+ so->isVoidRes = true; /* unsatisfiable query */
+ break;
+ }
+
+ so->forcedRecheck |= res != GIN_TRUE;
/*
- * Increment the number of columns with NOT NULL constraints.
+ * Increment the number of columns with NOT NULL constraints
+ * if NOT NULL is not yet implied by some non-empty key.
*/
- colNotNull[colno] = true;
- numNotNullKeys++;
+ if (colNotNull[colno] == GIN_FALSE)
+ {
+ colNotNull[colno] = GIN_MAYBE;
+ colNotNullCount++;
+ }
continue;
}
@@ -375,6 +404,16 @@ ginNewScanKey(IndexScanDesc scan)
}
/*
+ * Current non-empty key implies that column is NOT NULL, so decrement
+ * the number of columns with NOT NULL if NOT NULL already is implied by
+ * some empty ALL key.
+ */
+ if (colNotNull[colno] == GIN_MAYBE)
+ colNotNullCount--;
+
+ colNotNull[colno] = GIN_TRUE;
+
+ /*
* Create GinNullCategory representation. If the extractQueryFn
* didn't create a nullFlags array, we assume everything is non-null.
* While at it, detect whether any null keys are present.
@@ -394,7 +433,7 @@ 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,
@@ -412,24 +451,32 @@ ginNewScanKey(IndexScanDesc scan)
hasNullQuery = true;
/* Initialize EVERYTHING key if there are no non-NULL columns. */
- if (!numNotNullKeys)
+ if (!colNotNullCount)
{
- ginFillScanKey(so, FirstOffsetNumber, InvalidStrategy,
- GIN_SEARCH_MODE_EVERYTHING, (Datum) 0, 0,
- NULL, NULL, NULL, NULL);
+ ginFillScanKey(so, NULL, true, FirstOffsetNumber,
+ InvalidStrategy, GIN_SEARCH_MODE_EVERYTHING,
+ (Datum) 0, 0, NULL, NULL, NULL, NULL);
}
else
{
/* Initialize NOT_NULL key for each non-NULL column. */
for (i = 0; i < scan->indexRelation->rd_att->natts; i++)
{
- if (colNotNull[i])
- ginFillScanKey(so, i + 1, InvalidStrategy,
+ if (colNotNull[i] == GIN_MAYBE)
+ ginFillScanKey(so, NULL, true, i + 1, InvalidStrategy,
GIN_SEARCH_MODE_NOT_NULL, (Datum) 0, 0,
NULL, NULL, NULL, NULL);
}
}
}
+ else if (colNotNullCount)
+ {
+ /*
+ * We use recheck instead of adding NOT_NULL entries to eliminate
+ * rows with NULL columns.
+ */
+ so->forcedRecheck = true;
+ }
/*
* If the index is version 0, it may be missing null and placeholder
--
2.7.4
>From 41b1bd04f63e1f546e08b022223a1425fcf2b5b4 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 4/5] Avoid GIN full scan for non-empty ALL keys
---
src/backend/access/gin/ginget.c | 125 ++++++++++++++++---------
src/backend/access/gin/ginscan.c | 168 +++++++++++++++++++++++++++-------
src/backend/utils/adt/selfuncs.c | 46 ++++------
src/include/access/gin_private.h | 6 ++
src/test/regress/expected/tsearch.out | 23 +++++
src/test/regress/sql/tsearch.sql | 7 ++
6 files changed, 267 insertions(+), 108 deletions(-)
diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
index 65ed8b2..a7f5c56 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -1231,11 +1231,12 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key,
*/
static bool
scanGetItem(IndexScanDesc scan, ItemPointerData advancePast,
- ItemPointerData *item, bool *recheck)
+ ItemPointerData *item, bool *recheckp)
{
GinScanOpaque so = (GinScanOpaque) scan->opaque;
uint32 i;
bool match;
+ bool recheck;
/*----------
* Advance the scan keys in lock-step, until we find an item that matches
@@ -1262,6 +1263,8 @@ scanGetItem(IndexScanDesc scan, ItemPointerData advancePast,
{
ItemPointerSetMin(item);
match = true;
+ recheck = false;
+
for (i = 0; i < so->nkeys && match; i++)
{
GinScanKey key = so->keys + i;
@@ -1270,44 +1273,55 @@ scanGetItem(IndexScanDesc scan, ItemPointerData advancePast,
keyGetItem(&so->ginstate, so->tempCtx, key, advancePast,
scan->xs_snapshot);
- if (key->isFinished)
- return false;
-
- /*
- * If it's not a match, we can immediately conclude that nothing
- * <= this item matches, without checking the rest of the keys.
- */
- if (!key->curItemMatches)
+ if (!key->includeNonMatching) /* postpone curItem checks */
{
- advancePast = key->curItem;
- match = false;
- break;
- }
+ if (key->isFinished)
+ return false;
- /*
- * It's a match. We can conclude that nothing < matches, so the
- * other key streams can skip to this item.
- *
- * Beware of lossy pointers, though; from a lossy pointer, we can
- * only conclude that nothing smaller than this *block* matches.
- */
- if (ItemPointerIsLossyPage(&key->curItem))
- {
- if (GinItemPointerGetBlockNumber(&advancePast) <
- GinItemPointerGetBlockNumber(&key->curItem))
+ /*
+ * If it's not a match, we can immediately conclude that
+ * nothing <= this item matches, without checking the rest of
+ * the keys.
+ */
+ if (!key->curItemMatches)
+ {
+ advancePast = key->curItem;
+ match = false;
+ break;
+ }
+
+ /*
+ * We must return recheck = true if any of the keys are marked
+ * recheck.
+ */
+ recheck |= key->recheckCurItem;
+
+ /*
+ * It's a match. We can conclude that nothing < matches, so the
+ * other key streams can skip to this item.
+ *
+ * Beware of lossy pointers, though; from a lossy pointer, we
+ * can only conclude that nothing smaller than this *block*
+ * matches.
+ */
+ if (ItemPointerIsLossyPage(&key->curItem))
+ {
+ if (GinItemPointerGetBlockNumber(&advancePast) <
+ GinItemPointerGetBlockNumber(&key->curItem))
+ {
+ ItemPointerSet(&advancePast,
+ GinItemPointerGetBlockNumber(&key->curItem),
+ InvalidOffsetNumber);
+ }
+ }
+ else
{
+ Assert(GinItemPointerGetOffsetNumber(&key->curItem) > 0);
ItemPointerSet(&advancePast,
GinItemPointerGetBlockNumber(&key->curItem),
- InvalidOffsetNumber);
+ OffsetNumberPrev(GinItemPointerGetOffsetNumber(&key->curItem)));
}
}
- else
- {
- Assert(GinItemPointerGetOffsetNumber(&key->curItem) > 0);
- ItemPointerSet(&advancePast,
- GinItemPointerGetBlockNumber(&key->curItem),
- OffsetNumberPrev(GinItemPointerGetOffsetNumber(&key->curItem)));
- }
/*
* If this is the first key, remember this location as a potential
@@ -1322,9 +1336,18 @@ scanGetItem(IndexScanDesc scan, ItemPointerData advancePast,
if (i == 0)
{
*item = key->curItem;
+ /* The first key must be have includeNonMatching == false. */
+ Assert(key->includeNonMatching);
}
else
{
+ if (key->includeNonMatching && key->isFinished)
+ {
+ /* Accept all non-matching items after key was finished. */
+ recheck |= key->recheckNonMatching;
+ continue;
+ }
+
if (ItemPointerIsLossyPage(&key->curItem) ||
ItemPointerIsLossyPage(item))
{
@@ -1337,6 +1360,30 @@ scanGetItem(IndexScanDesc scan, ItemPointerData advancePast,
Assert(ginCompareItemPointers(&key->curItem, item) >= 0);
match = (ginCompareItemPointers(&key->curItem, item) == 0);
}
+
+ if (key->includeNonMatching)
+ {
+ /*
+ * If the current item matches, then apply ordinary rules,
+ * else force recheck if needed.
+ */
+ if (match)
+ {
+ if (!key->curItemMatches)
+ {
+ advancePast = key->curItem;
+ match = false;
+ break;
+ }
+
+ recheck |= key->recheckCurItem;
+ }
+ else
+ {
+ match = true;
+ recheck |= key->recheckNonMatching;
+ }
+ }
}
}
} while (!match);
@@ -1347,20 +1394,8 @@ scanGetItem(IndexScanDesc scan, ItemPointerData advancePast,
* Now *item contains the first ItemPointer after previous result that
* satisfied all the keys for that exact TID, or a lossy reference to the
* same page.
- *
- * We must return recheck = true if any of the keys are marked recheck.
*/
- *recheck = false;
- for (i = 0; i < so->nkeys; i++)
- {
- GinScanKey key = so->keys + i;
-
- if (key->recheckCurItem)
- {
- *recheck = true;
- break;
- }
- }
+ *recheckp = recheck;
return true;
}
diff --git a/src/backend/access/gin/ginscan.c b/src/backend/access/gin/ginscan.c
index 47beef3..df90b18 100644
--- a/src/backend/access/gin/ginscan.c
+++ b/src/backend/access/gin/ginscan.c
@@ -137,19 +137,29 @@ ginFillScanKey(GinScanOpaque so, GinScanKey key, bool initHiddenEntries,
{
GinState *ginstate = &so->ginstate;
uint32 nUserQueryValues = nQueryValues;
+ uint32 nAllocatedQueryValues = 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 && initHiddenEntries)
- nQueryValues++;
+ /*
+ * Non-default search modes add one "hidden" entry to each key, but this
+ * entry is initialized only if requested by initHiddenEntries flag.
+ */
+ if (searchMode != GIN_SEARCH_MODE_DEFAULT)
+ {
+ nAllocatedQueryValues++;
+
+ if (initHiddenEntries)
+ nQueryValues++;
+ }
+
key->nentries = nQueryValues;
key->nuserentries = nUserQueryValues;
- key->scanEntry = (GinScanEntry *) palloc(sizeof(GinScanEntry) * nQueryValues);
- key->entryRes = (GinTernaryValue *) palloc0(sizeof(GinTernaryValue) * nQueryValues);
+ key->scanEntry = (GinScanEntry *) palloc(sizeof(GinScanEntry) * nAllocatedQueryValues);
+ key->entryRes = (GinTernaryValue *) palloc0(sizeof(GinTernaryValue) * nAllocatedQueryValues);
key->query = query;
key->queryValues = queryValues;
@@ -158,6 +168,8 @@ ginFillScanKey(GinScanOpaque so, GinScanKey key, bool initHiddenEntries,
key->strategy = strategy;
key->searchMode = searchMode;
key->attnum = attnum;
+ key->includeNonMatching = false;
+ key->recheckNonMatching = false;
ItemPointerSetMin(&key->curItem);
key->curItemMatches = false;
@@ -272,6 +284,8 @@ ginNewScanKey(IndexScanDesc scan)
GinScanOpaque so = (GinScanOpaque) scan->opaque;
int i;
bool hasNullQuery = false;
+ bool hasAllQuery = false;
+ bool hasRegularQuery = false;
/*
* GIN_FALSE - column has no search keys
* GIN_TRUE - NOT NULL is implied by some non-empty search key
@@ -359,7 +373,25 @@ ginNewScanKey(IndexScanDesc scan)
so->isVoidRes = true;
break;
}
- else if (searchMode == GIN_SEARCH_MODE_ALL)
+
+ nQueryValues = 0; /* ensure sane value */
+ }
+
+ if (searchMode == GIN_SEARCH_MODE_ALL)
+ {
+ hasAllQuery = true;
+
+ /*
+ * Increment the number of columns with NOT NULL constraints
+ * if NOT NULL is not yet implied by some non-ALL key.
+ */
+ if (colNotNull[colno] == GIN_FALSE)
+ {
+ colNotNull[colno] = GIN_MAYBE;
+ colNotNullCount++;
+ }
+
+ if (!nQueryValues)
{
/*
* The query probably matches all non-null items, but rather
@@ -386,32 +418,22 @@ ginNewScanKey(IndexScanDesc scan)
}
so->forcedRecheck |= res != GIN_TRUE;
-
- /*
- * Increment the number of columns with NOT NULL constraints
- * if NOT NULL is not yet implied by some non-empty key.
- */
- if (colNotNull[colno] == GIN_FALSE)
- {
- colNotNull[colno] = GIN_MAYBE;
- colNotNullCount++;
- }
-
continue;
}
-
- nQueryValues = 0; /* ensure sane value */
}
+ else
+ {
+ hasRegularQuery = true;
- /*
- * Current non-empty key implies that column is NOT NULL, so decrement
- * the number of columns with NOT NULL if NOT NULL already is implied by
- * some empty ALL key.
- */
- if (colNotNull[colno] == GIN_MAYBE)
- colNotNullCount--;
+ /*
+ * Current key implies that column is NOT NULL, so decrement the
+ * number of columns with NOT NULL constraints.
+ */
+ if (colNotNull[colno] == GIN_MAYBE)
+ colNotNullCount--;
- colNotNull[colno] = GIN_TRUE;
+ colNotNull[colno] = GIN_TRUE;
+ }
/*
* Create GinNullCategory representation. If the extractQueryFn
@@ -433,7 +455,10 @@ ginNewScanKey(IndexScanDesc scan)
}
}
- ginFillScanKey(so, NULL, true, skey->sk_attno,
+ ginFillScanKey(so, NULL,
+ /* postpone initialization of hidden ALL entry */
+ searchMode != GIN_SEARCH_MODE_ALL,
+ skey->sk_attno,
skey->sk_strategy, searchMode,
skey->sk_argument, nQueryValues,
queryValues, categories,
@@ -469,13 +494,88 @@ ginNewScanKey(IndexScanDesc scan)
}
}
}
- else if (colNotNullCount)
+ else
{
- /*
- * We use recheck instead of adding NOT_NULL entries to eliminate
- * rows with NULL columns.
- */
- so->forcedRecheck = true;
+ if (hasAllQuery)
+ {
+ GinScanKey nonAllKey = NULL;
+ int nkeys = so->nkeys;
+ int i = 0;
+
+ /*
+ * Finalize non-empty ALL keys: if we have regular keys, enable
+ * includeNonMatching mode in ALL keys, otherwise initialize
+ * previously skipped hidden ALL entries.
+ */
+ for (i = 0; i < nkeys; i++)
+ {
+ GinScanKey key = &so->keys[i];
+
+ if (key->searchMode != GIN_SEARCH_MODE_ALL)
+ {
+ nonAllKey = key;
+ }
+ else if (hasRegularQuery)
+ {
+ memset(key->entryRes, GIN_FALSE, key->nentries);
+
+ switch (key->triConsistentFn(key))
+ {
+ case GIN_TRUE:
+ key->includeNonMatching = true;
+ key->recheckNonMatching = false;
+ break;
+ case GIN_MAYBE:
+ key->includeNonMatching = true;
+ key->recheckNonMatching = true;
+ default:
+ /*
+ * Items with no matching entries are not
+ * accepted, leave the key as is.
+ */
+ break;
+ }
+ }
+ else
+ {
+ /* Initialize missing hidden ALL entry */
+ key->scanEntry[key->nentries++] =
+ ginFillScanEntry(so, key->attnum, key->strategy,
+ GIN_SEARCH_MODE_ALL, (Datum) 0,
+ GIN_CAT_EMPTY_QUERY, false, NULL);
+
+ /*
+ * ALL entry implies NOT NULL, so update the number of
+ * NOT NULL columns.
+ */
+ if (colNotNull[key->attnum - 1] == GIN_MAYBE)
+ {
+ colNotNull[key->attnum - 1] = GIN_TRUE;
+ colNotNullCount--;
+ }
+ }
+ }
+
+ /* Move some non-ALL key to the beginning (see scanGetItem()) */
+ if (so->keys[0].includeNonMatching)
+ {
+ GinScanKeyData tmp = so->keys[0];
+
+ Assert(nonAllKey);
+
+ so->keys[0] = *nonAllKey;
+ *nonAllKey = tmp;
+ }
+ }
+
+ if (colNotNullCount > 0)
+ {
+ /*
+ * We use recheck instead of adding NOT_NULL entries to
+ * eliminate rows with NULL columns.
+ */
+ so->forcedRecheck = true;
+ }
}
/*
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 46fff24..35998ed 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -6240,7 +6240,6 @@ spgcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
typedef struct
{
- bool haveFullScan;
double partialEntries;
double exactEntries;
double searchEntries;
@@ -6317,23 +6316,21 @@ gincost_pattern(IndexOptInfo *index, int indexcol,
PointerGetDatum(&searchMode));
/* Special cases for queries that contain no keys */
- if (nentries <= 0)
+ if (nentries <= 0 && searchMode == GIN_SEARCH_MODE_DEFAULT)
{
- 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;
- }
+ /* In default mode, no keys means an unsatisfiable query */
+ return false;
+ }
+
+ 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++)
@@ -6356,11 +6353,8 @@ gincost_pattern(IndexOptInfo *index, int indexcol,
counts->exactEntries++;
counts->searchEntries++;
}
- else if (searchMode != GIN_SEARCH_MODE_DEFAULT)
- {
- /* It's GIN_SEARCH_MODE_ALL */
- counts->haveFullScan = true;
- }
+
+ Assert(counts->searchEntries > 0);
return true;
}
@@ -6497,9 +6491,6 @@ gincost_scalararrayopexpr(PlannerInfo *root,
/* If no regular scan keys, assume an EVERYTHING scan is needed */
if (elemcounts.searchEntries == 0)
- elemcounts.haveFullScan = true;
-
- if (elemcounts.haveFullScan)
{
/*
* Full index scan will be required. We treat this as if
@@ -6724,10 +6715,7 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
}
/* If no regular scan keys, assume an EVERYTHING scan is needed */
- if (counts.searchEntries == 0)
- counts.haveFullScan = true;
-
- if (counts.haveFullScan || indexQuals == NIL)
+ if (!counts.searchEntries || indexQuals == NIL)
{
/*
* 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 9d2ee3a..2c04496 100644
--- a/src/include/access/gin_private.h
+++ b/src/include/access/gin_private.h
@@ -297,6 +297,12 @@ typedef struct GinScanKeyData
StrategyNumber strategy;
int32 searchMode;
OffsetNumber attnum;
+ /*
+ * Include/recheck items from other scankeys that has no entries of this
+ * scankey. (This is used for execution of ALL keys without a full scan.)
+ */
+ bool includeNonMatching;
+ bool recheckNonMatching;
/*
* Match status data. curItem is the TID most recently tested (could be a
diff --git a/src/test/regress/expected/tsearch.out b/src/test/regress/expected/tsearch.out
index 7af2899..506cd58 100644
--- a/src/test/regress/expected/tsearch.out
+++ b/src/test/regress/expected/tsearch.out
@@ -337,6 +337,29 @@ 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))
+ Heap Blocks: exact=22
+ -> Bitmap Index Scan on wowidx (actual rows=60 loops=1)
+ Index Cond: ((a @@ '''wr'''::tsquery) AND (a @@ '!''qh'''::tsquery))
+(5 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
