Re: Avoid full GIN index scan when possible

Alexander Korotkov <[email protected]> Wed, 8 Jan 2020 19:31:52 +0300

Newsgroups	gmane.comp.db.postgresql.devel.general
Message-ID	<CAPpHfdthhf8S-UjE46hjy+g7pgGhy=hav1-BUmQq6+hKmY13nA@mail.gmail.com>

Hi, Tomas!

Thank you for your feedback!

On Mon, Jan 6, 2020 at 6:22 PM Tomas Vondra <[email protected]>
wrote:

> Yeah, I can confirm those results, although on my system the timings are
> a bit different (I haven't tested v8):
>
>                                         |        Query time, ms
>              WHERE condition            | master |    v9
> ---------------------------------------+--------+---------
>   a @> '{}'                             |    610 |    589
>   a @> '{}' and b @> '{}'               |    185 |    665
>   a @> '{}' and b @> '{}' and c @> '{}' |    185 |    741
>
> So that's something we probably need to address, perhaps by using the
> GIN_CAT_EMPTY_QUERY entries as proposed.
>

Yeah, handling nulls better without regression in some cases is hard.
For now I see at least 3 different ways of nulls handling, assuming there
is another non-excluding scan key:

1) Collect non-null matches by full scan of all non-null entries.
2) Exclude null marches using scan of null entry.
3) Force recheck.

Each method have its own advantages and disadvantages.  We probably
would need some cost-based decision making algorithm based on statistics.
I'm not entirely sure it's OK to do this execution time.  However, it
probably
could be classified as "adaptive query processing", which is considered as
cool trend in DBMS.

Attached version 10 of patch doesn't change null handling in comparison
with master.  It eliminates full index scan only if there is another scan
on the
same column.  So, it never adds null item to the scan key.  I've rerun tests
from Nikita [1].

   |                                        | Query time, ms |
 # |             WHERE condition            | master |   v10 |
---+----------------------------------------+--------+-------+
 1 |  a @> '{}'                             |    223 |   218 |
 2 |  a @> '{}' and b @> '{}'               |    302 |   308 |
 3 |  a @> '{}' and b @> '{}' and c @> '{}' |    405 |   404 |
 4 |  a @> '{}' and a @@ '1'                |     59 |   0.3 |
 5 |  a @> '{}' and a @@ '-1'               |     64 |   2.2 |
 6 |  a @@ '!-1' and a @@ '1'               |     63 |   0.3 |
 7 |  a @@ '!1' and a @@ '-1'               |     62 |   3.0 |

It appears that absolute numbers for master are higher than they were
previous time [2].  I've rechecked multiple times that current numbers are
correct.  So, it might be I didn't turn off sequential scan previous time.

We can see that cases #1, #2, #3, which have quals over multiple attributes
have the same execution time as in master.  That's expected since scanning
strategy is the same.  Cases #4, #5, #6, #7 have about the same improvement
as in v9.

I've also rerun many nulls test from Nikita [3].

                                       | Query time, ms |
            WHERE condition            | master |   v10 |
---------------------------------------+--------+-------+
 a @> '{}'                             |    190 |   192 |
 a @> '{}' and b @> '{}'               |     55 |    57 |
 a @> '{}' and b @> '{}' and c @> '{}' |     60 |    58 |

The results are the same as in master again.

I've also tested this on a database storing mailing lists archives with
> a trigram index, and in that case the performance with short values gets
> much better. The "messages" table has two text fields with a GIN trigram
> index - subject and body, and querying them with short/long values works
> like this:
>
>                     WHERE                    |  master  |    v9
>   --------------------------------------------------------------
>   subject LIKE '%aa%' AND body LIKE '%xx%'   |    4943  |  4052
>   subject LIKE '%aaa%' AND body LIKE '%xx%'  |      10  |    10
>   subject LIKE '%aa%' AND body LIKE '%xxx%'  |     380  |    13
>   subject LIKE '%aaa%' AND BODY LIKE '%xxx%' |       2  |     2
>
> which seems fairly nice. I've done tests with individual columns, and
> that seems to be working fine too.
>

Cool, thanks!

So, I think v10 is a version of patch, which can be committed after
some cleanup.  And we can try doing better nulls handling in a separate
patch.

Links
1.
https://www.postgresql.org/message-id/f2889144-db1d-e3b2-db97-cfc8794cda43%40postgrespro.ru
2.
https://www.postgresql.org/message-id/CAPpHfdvT_t6ShG2pvptEWceDxEnyNRsm2MxmCWWvxBzQ-pbMuw%40mail.gmail.com
3.
https://www.postgresql.org/message-id/b53614eb-6f9f-8c5c-9df8-f703b0b102b6%40postgrespro.ru

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

0001-Avoid-GIN-full-scan-for-empty-ALL-keys-v10.patch (application/octet-stream, 27.8 KB)

commit f98292ef246d2d158ce5e32f6baf6267beb55663
Author: Alexander Korotkov <[email protected]>
Date:   Tue Dec 24 23:52:16 2019 +0300

    Avoid GIN full scan

diff --git a/contrib/pg_trgm/expected/pg_trgm.out b/contrib/pg_trgm/expected/pg_trgm.out
index b3e709f4962..3e5ba9bf198 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 08459e64c30..dcfd3c23eb0 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 7ae4ef05c2f..b31b3606453 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -528,8 +528,20 @@ startScanKey(GinState *ginstate, GinScanOpaque so, GinScanKey key)
 	 * order, until the consistent function says that none of the remaining
 	 * entries can form a match, without any items from the required set. The
 	 * rest go to the additional set.
+	 *
+	 * Exclude only scan keys are known to have no required entries.
 	 */
-	if (key->nentries > 1)
+	if (key->excludeOnly)
+	{
+		MemoryContextSwitchTo(so->keyCtx);
+
+		key->nrequired = 0;
+		key->nadditional = key->nentries;
+		key->additionalEntries = palloc(key->nadditional * sizeof(GinScanEntry));
+		for (i = 0; i < key->nadditional; i++)
+			key->additionalEntries[i] = key->scanEntry[i];
+	}
+	else if (key->nentries > 1)
 	{
 		MemoryContextSwitchTo(so->tempCtx);
 
@@ -1008,7 +1020,7 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key,
 			minItem = entry->curItem;
 	}
 
-	if (allFinished)
+	if (allFinished && !key->excludeOnly)
 	{
 		/* all entries are finished */
 		key->isFinished = true;
@@ -1023,22 +1035,32 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key,
 	 * items. However, there might be exact items for the same page among
 	 * additionalEntries, so we mustn't advance past them.
 	 */
-	if (ItemPointerIsLossyPage(&minItem))
+	if (!key->excludeOnly)
 	{
-		if (GinItemPointerGetBlockNumber(&advancePast) <
-			GinItemPointerGetBlockNumber(&minItem))
+		if (ItemPointerIsLossyPage(&minItem))
+		{
+			if (GinItemPointerGetBlockNumber(&advancePast) <
+				GinItemPointerGetBlockNumber(&minItem))
+			{
+				ItemPointerSet(&advancePast,
+							   GinItemPointerGetBlockNumber(&minItem),
+							   InvalidOffsetNumber);
+			}
+		}
+		else
 		{
+			Assert(GinItemPointerGetOffsetNumber(&minItem) > 0);
 			ItemPointerSet(&advancePast,
 						   GinItemPointerGetBlockNumber(&minItem),
-						   InvalidOffsetNumber);
+						   OffsetNumberPrev(GinItemPointerGetOffsetNumber(&minItem)));
 		}
 	}
 	else
 	{
-		Assert(GinItemPointerGetOffsetNumber(&minItem) > 0);
-		ItemPointerSet(&advancePast,
-					   GinItemPointerGetBlockNumber(&minItem),
-					   OffsetNumberPrev(GinItemPointerGetOffsetNumber(&minItem)));
+		Assert(key->nrequired == 0);
+		ItemPointerSet(&minItem,
+					   GinItemPointerGetBlockNumber(&advancePast),
+					   OffsetNumberNext(GinItemPointerGetOffsetNumber(&advancePast)));
 	}
 
 	/*
@@ -1070,7 +1092,7 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key,
 		 */
 		if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
 		{
-			Assert(ItemPointerIsLossyPage(&minItem));
+			Assert(ItemPointerIsLossyPage(&minItem) || key->nrequired == 0);
 			minItem = entry->curItem;
 		}
 	}
@@ -1740,7 +1762,7 @@ collectMatchesForHeapRow(IndexScanDesc scan, pendingPosition *pos)
 	 */
 	for (i = 0; i < so->nkeys; i++)
 	{
-		if (pos->hasMatchKey[i] == false)
+		if (pos->hasMatchKey[i] == false && !so->keys[i].excludeOnly)
 			return false;
 	}
 
diff --git a/src/backend/access/gin/ginscan.c b/src/backend/access/gin/ginscan.c
index c15d06ceba4..dd6e43f9d1e 100644
--- a/src/backend/access/gin/ginscan.c
+++ b/src/backend/access/gin/ginscan.c
@@ -125,6 +125,21 @@ ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,
 	return scanEntry;
 }
 
+/*
+ * Append hidden scan entry of given category to the scan key.
+ */
+static void
+ginScanKeyAddHiddenEntry(GinScanOpaque so, GinScanKey key,
+						 GinNullCategory queryCategory)
+{
+	int i = key->nentries++;
+
+	key->scanEntry[i] = ginFillScanEntry(so, key->attnum,
+										 InvalidStrategy, key->searchMode,
+										 (Datum) 0, queryCategory,
+										 false, NULL);
+}
+
 /*
  * Initialize the next GinScanKey using the output from the extractQueryFn
  */
@@ -137,17 +152,16 @@ ginFillScanKey(GinScanOpaque so, OffsetNumber attnum,
 {
 	GinScanKey	key = &(so->keys[so->nkeys++]);
 	GinState   *ginstate = &so->ginstate;
-	uint32		nUserQueryValues = nQueryValues;
 	uint32		i;
 
-	/* Non-default search modes add one "hidden" entry to each key */
-	if (searchMode != GIN_SEARCH_MODE_DEFAULT)
-		nQueryValues++;
 	key->nentries = nQueryValues;
-	key->nuserentries = nUserQueryValues;
+	key->nuserentries = nQueryValues;
 
-	key->scanEntry = (GinScanEntry *) palloc(sizeof(GinScanEntry) * nQueryValues);
-	key->entryRes = (GinTernaryValue *) palloc0(sizeof(GinTernaryValue) * nQueryValues);
+	/* Reserve space for possible "hidden" entry */
+	key->scanEntry = (GinScanEntry *) palloc(sizeof(GinScanEntry) *
+											 (nQueryValues + 1));
+	key->entryRes = (GinTernaryValue *) palloc0(sizeof(GinTernaryValue) *
+												(nQueryValues + 1));
 
 	key->query = query;
 	key->queryValues = queryValues;
@@ -166,6 +180,13 @@ ginFillScanKey(GinScanOpaque so, OffsetNumber attnum,
 	key->requiredEntries = NULL;
 	key->additionalEntries = NULL;
 
+	/*
+	 * By default scan keys of GIN_SEARCH_MODE_ALL mode are "exclude only".
+	 * One scan key might be switched back to "include" mode in the second pass
+	 * of ginNewScanKey() function.
+	 */
+	key->excludeOnly = (searchMode == GIN_SEARCH_MODE_ALL);
+
 	ginInitConsistentFunction(ginstate, key);
 
 	for (i = 0; i < nQueryValues; i++)
@@ -175,54 +196,30 @@ ginFillScanKey(GinScanOpaque so, OffsetNumber attnum,
 		bool		isPartialMatch;
 		Pointer		this_extra;
 
-		if (i < nUserQueryValues)
-		{
-			/* set up normal entry using extractQueryFn's outputs */
-			queryKey = queryValues[i];
-			queryCategory = queryCategories[i];
-			isPartialMatch =
-				(ginstate->canPartialMatch[attnum - 1] && partial_matches)
-				? partial_matches[i] : false;
-			this_extra = (extra_data) ? extra_data[i] : NULL;
-		}
-		else
-		{
-			/* set up hidden entry */
-			queryKey = (Datum) 0;
-			switch (searchMode)
-			{
-				case GIN_SEARCH_MODE_INCLUDE_EMPTY:
-					queryCategory = GIN_CAT_EMPTY_ITEM;
-					break;
-				case GIN_SEARCH_MODE_ALL:
-					queryCategory = GIN_CAT_EMPTY_QUERY;
-					break;
-				case GIN_SEARCH_MODE_EVERYTHING:
-					queryCategory = GIN_CAT_EMPTY_QUERY;
-					break;
-				default:
-					elog(ERROR, "unexpected searchMode: %d", searchMode);
-					queryCategory = 0;	/* keep compiler quiet */
-					break;
-			}
-			isPartialMatch = false;
-			this_extra = NULL;
-
-			/*
-			 * We set the strategy to a fixed value so that ginFillScanEntry
-			 * can combine these entries for different scan keys.  This is
-			 * safe because the strategy value in the entry struct is only
-			 * used for partial-match cases.  It's OK to overwrite our local
-			 * variable here because this is the last loop iteration.
-			 */
-			strategy = InvalidStrategy;
-		}
+		/* set up normal entry using extractQueryFn's outputs */
+		queryKey = queryValues[i];
+		queryCategory = queryCategories[i];
+		isPartialMatch =
+			(ginstate->canPartialMatch[attnum - 1] && partial_matches)
+			? partial_matches[i] : false;
+		this_extra = (extra_data) ? extra_data[i] : NULL;
 
 		key->scanEntry[i] = ginFillScanEntry(so, attnum,
 											 strategy, searchMode,
 											 queryKey, queryCategory,
 											 isPartialMatch, this_extra);
 	}
+
+	/*
+	 * We add "hidden" entries for GIN_SEARCH_MODE_INCLUDE_EMPTY and
+	 * GIN_SEARCH_MODE_EVERYTHING search modes immediately.
+	 * GIN_SEARCH_MODE_ALL is handled separately in the second pass of
+	 * ginNewScanKey() function.
+	 */
+	if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
+		ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_ITEM);
+	else if (searchMode == GIN_SEARCH_MODE_EVERYTHING)
+		ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
 }
 
 /*
@@ -265,6 +262,7 @@ ginNewScanKey(IndexScanDesc scan)
 	GinScanOpaque so = (GinScanOpaque) scan->opaque;
 	int			i;
 	bool		hasNullQuery = false;
+	bool		attrHasNormalScan[INDEX_MAX_KEYS] = {false};
 	MemoryContext oldCtx;
 
 	/*
@@ -287,6 +285,15 @@ ginNewScanKey(IndexScanDesc scan)
 
 	so->isVoidRes = false;
 
+	/*
+	 * Processing GIN_SEARCH_MODE_ALL scan keys requires us to make two passes.
+	 * In the first pass we mark each such scan key as excludeOnly and don't
+	 * add hidden entries there.  We are doing so in the hope that each involved
+	 * column would have normal (not excludeOnly) scan key as well.  If column
+	 * keys doesn't have any normal scan keys, the one of its scan keys receives
+	 * GIN_CAT_EMPTY_QUERY hidden entry and is set to normal
+	 * (excludeOnly = false).
+	 */
 	for (i = 0; i < scan->numberOfKeys; i++)
 	{
 		ScanKey		skey = &scankey[i];
@@ -346,6 +353,9 @@ ginNewScanKey(IndexScanDesc scan)
 			nQueryValues = 0;	/* ensure sane value */
 		}
 
+		if (searchMode != GIN_SEARCH_MODE_ALL)
+			attrHasNormalScan[skey->sk_attno - 1] = true;
+
 		/*
 		 * Create GinNullCategory representation.  If the extractQueryFn
 		 * didn't create a nullFlags array, we assume everything is non-null.
@@ -373,6 +383,21 @@ ginNewScanKey(IndexScanDesc scan)
 					   partial_matches, extra_data);
 	}
 
+	for (i = 0; i < so->nkeys; i++)
+	{
+		GinScanKey	key = &so->keys[i];
+
+		if (key->searchMode != GIN_SEARCH_MODE_ALL)
+			continue;
+
+		if (!attrHasNormalScan[key->attnum - 1])
+		{
+			key->excludeOnly = false;
+			ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
+			attrHasNormalScan[key->attnum - 1] = true;
+		}
+	}
+
 	/*
 	 * If there are no regular scan keys, generate an EVERYTHING scankey to
 	 * drive a full-index scan.
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 18d77ac0b77..443b77d5385 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -6356,7 +6356,8 @@ spgcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 
 typedef struct
 {
-	bool		haveFullScan;
+	bool		attHasFullScan[INDEX_MAX_KEYS];
+	bool		attHasNormalScan[INDEX_MAX_KEYS];
 	double		partialEntries;
 	double		exactEntries;
 	double		searchEntries;
@@ -6452,16 +6453,21 @@ gincost_pattern(IndexOptInfo *index, int indexcol,
 		counts->searchEntries++;
 	}
 
+	if (searchMode == GIN_SEARCH_MODE_DEFAULT)
+	{
+		counts->attHasNormalScan[indexcol] = true;
+	}
 	if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
 	{
 		/* Treat "include empty" like an exact-match item */
+		counts->attHasNormalScan[indexcol] = true;
 		counts->exactEntries++;
 		counts->searchEntries++;
 	}
 	else if (searchMode != GIN_SEARCH_MODE_DEFAULT)
 	{
 		/* It's GIN_SEARCH_MODE_ALL */
-		counts->haveFullScan = true;
+		counts->attHasFullScan[indexcol] = true;
 	}
 
 	return true;
@@ -6597,7 +6603,8 @@ gincost_scalararrayopexpr(PlannerInfo *root,
 			/* We ignore array elements that are unsatisfiable patterns */
 			numPossible++;
 
-			if (elemcounts.haveFullScan)
+			if (elemcounts.attHasFullScan[indexcol] &&
+				!elemcounts.attHasNormalScan[indexcol])
 			{
 				/*
 				 * Full index scan will be required.  We treat this as if
@@ -6608,6 +6615,7 @@ gincost_scalararrayopexpr(PlannerInfo *root,
 				elemcounts.exactEntries = numIndexEntries;
 				elemcounts.searchEntries = numIndexEntries;
 			}
+
 			arraycounts.partialEntries += elemcounts.partialEntries;
 			arraycounts.exactEntries += elemcounts.exactEntries;
 			arraycounts.searchEntries += elemcounts.searchEntries;
@@ -6628,6 +6636,8 @@ gincost_scalararrayopexpr(PlannerInfo *root,
 	counts->partialEntries += arraycounts.partialEntries / numPossible;
 	counts->exactEntries += arraycounts.exactEntries / numPossible;
 	counts->searchEntries += arraycounts.searchEntries / numPossible;
+	counts->attHasNormalScan[indexcol] |= arraycounts.attHasNormalScan[indexcol];
+	counts->attHasFullScan[indexcol] |= arraycounts.attHasFullScan[indexcol];
 
 	counts->arrayScans *= numPossible;
 
@@ -6654,6 +6664,7 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 				numEntries;
 	GinQualCounts counts;
 	bool		matchPossible;
+	bool		fullIndexScan;
 	double		partialScale;
 	double		entryPagesFetched,
 				dataPagesFetched,
@@ -6665,6 +6676,7 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 	Relation	indexRel;
 	GinStatsData ginStats;
 	ListCell   *lc;
+	int			i;
 
 	/*
 	 * Obtain statistical information from the meta page, if possible.  Else
@@ -6821,7 +6833,23 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 		return;
 	}
 
-	if (counts.haveFullScan || indexQuals == NIL)
+	/*
+	 * If attribute has a full scan and at the same time doesn't have normal
+	 * scan, then we have to scan all non-null the entries of that attribute.
+	 * Currently, we don't have per-attribute statistics for GIN.  Thus, we
+	 * if assume the whole GIN index has to be scanned in this case.
+	 */
+	fullIndexScan = false;
+	for (i = 0; i < index->nkeycolumns; i++)
+	{
+		if (counts.attHasFullScan[i] && !counts.attHasNormalScan[i])
+		{
+			fullIndexScan = true;
+			break;
+		}
+	}
+
+	if (fullIndexScan || 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 a136f7f9186..ef63e1087ae 100644
--- a/src/include/access/gin_private.h
+++ b/src/include/access/gin_private.h
@@ -303,6 +303,14 @@ typedef struct GinScanKeyData
 	int32		searchMode;
 	OffsetNumber attnum;
 
+	/*
+	 * "Exclude only" scan key is not capable to enumerate all matching tids.
+	 * Instead it's only useful to check tids returned by other scan keys.
+	 * That is such scan key can only exclude.  GIN search should contain at
+	 * least one normal "include" scankey.
+	 */
+	bool		excludeOnly;
+
 	/*
 	 * Match status data.  curItem is the TID most recently tested (could be a
 	 * lossy-page pointer).  curItemMatches is true if it passes the
diff --git a/src/test/regress/expected/gin.out b/src/test/regress/expected/gin.out
index a3911a6c6c9..5d0271cf92e 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,104 @@ 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
+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;
+                    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 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 @> '{}'                  | 7               | 0                  | ({},) ({1},) ("{1,2}",) ("{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               | 0                  | ({1},) ("{1,2}",) ("{1,2}",{10}) ("{1,3}",{}) ("{1,1}",{10})
+  i @> '{1}' and i @> '{}' and j @> '{}'   | 5               | 0                  | ({1},) ("{1,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               | 0                  | (,{10}) ("{1,2}",{10}) ({2},{10}) ("{1,1}",{10})
+  j @> '{10}' and j @> '{}' and i @> '{}'  | 4               | 0                  | (,{10}) ("{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/expected/tsearch.out b/src/test/regress/expected/tsearch.out
index 7af289927cc..506cd5863dc 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/gin.sql b/src/test/regress/sql/gin.sql
index c566e9b58c8..e0700c31741 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,73 @@ 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
+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;
diff --git a/src/test/regress/sql/tsearch.sql b/src/test/regress/sql/tsearch.sql
index ece80b983c5..54a5eef9ead 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');