Subject: [PATCH 2/3] Force GIN recheck more accurately

From: Nikita Glukhov <[email-masked]>
Date: Thu, 1 Aug 2019 18:45:41 +0300

---
 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

--------------B7A985DD4CDB1298897DF1B4
Content-Type: text/x-patch;
 name="0003-Avoid-GIN-full-scan-for-non-empty-ALL-keys-v06.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
 filename*0="0003-Avoid-GIN-full-scan-for-non-empty-ALL-keys-v06.patch"