From: Nikita Glukhov Date: Thu, 1 Aug 2019 18:45:41 +0300 Subject: [PATCH 2/3] Force GIN recheck more accurately --- src/backend/access/gin/ginlogic.c | 3 +- src/backend/access/gin/ginscan.c | 120 ++++++++++++++++++++++++++++++++------ src/include/access/gin.h | 1 + src/test/regress/expected/gin.out | 97 +++++++++++++++++++++++------- src/test/regress/sql/gin.sql | 68 ++++++++++++++++++--- 5 files changed, 241 insertions(+), 48 deletions(-) diff --git a/src/backend/access/gin/ginlogic.c b/src/backend/access/gin/ginlogic.c index 8f85978..7c4805d 100644 --- a/src/backend/access/gin/ginlogic.c +++ b/src/backend/access/gin/ginlogic.c @@ -224,7 +224,8 @@ shimTriConsistentFn(GinScanKey key) void ginInitConsistentFunction(GinState *ginstate, GinScanKey key) { - if (key->searchMode == GIN_SEARCH_MODE_EVERYTHING) + if (key->searchMode == GIN_SEARCH_MODE_EVERYTHING || + key->searchMode == GIN_SEARCH_MODE_NOT_NULL) { key->boolConsistentFn = trueConsistentFn; key->triConsistentFn = trueTriConsistentFn; diff --git a/src/backend/access/gin/ginscan.c b/src/backend/access/gin/ginscan.c index 11e7e8e..f612e55 100644 --- a/src/backend/access/gin/ginscan.c +++ b/src/backend/access/gin/ginscan.c @@ -129,20 +129,23 @@ ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum, * Initialize the next GinScanKey using the output from the extractQueryFn */ static void -ginFillScanKey(GinScanOpaque so, OffsetNumber attnum, - StrategyNumber strategy, int32 searchMode, +ginFillScanKey(GinScanOpaque so, GinScanKey key, bool initHiddenEntries, + OffsetNumber attnum, StrategyNumber strategy, int32 searchMode, Datum query, uint32 nQueryValues, Datum *queryValues, GinNullCategory *queryCategories, bool *partial_matches, Pointer *extra_data) { - GinScanKey key = &(so->keys[so->nkeys++]); GinState *ginstate = &so->ginstate; uint32 nUserQueryValues = nQueryValues; uint32 i; + if (key == NULL) + key = &(so->keys[so->nkeys++]); + /* Non-default search modes add one "hidden" entry to each key */ - if (searchMode != GIN_SEARCH_MODE_DEFAULT) + if (searchMode != GIN_SEARCH_MODE_DEFAULT && initHiddenEntries) nQueryValues++; + key->nentries = nQueryValues; key->nuserentries = nUserQueryValues; @@ -200,6 +203,11 @@ ginFillScanKey(GinScanOpaque so, OffsetNumber attnum, case GIN_SEARCH_MODE_EVERYTHING: queryCategory = GIN_CAT_EMPTY_QUERY; break; + case GIN_SEARCH_MODE_NOT_NULL: + queryCategory = GIN_CAT_EMPTY_QUERY; + /* use GIN_SEARCH_MODE_ALL to skip NULLs */ + searchMode = GIN_SEARCH_MODE_ALL; + break; default: elog(ERROR, "unexpected searchMode: %d", searchMode); queryCategory = 0; /* keep compiler quiet */ @@ -265,6 +273,9 @@ ginNewScanKey(IndexScanDesc scan) GinScanOpaque so = (GinScanOpaque) scan->opaque; int i; bool hasNullQuery = false; + int numColsNeedNotNull = 0; + bool colNeedsNotNull[INDEX_MAX_KEYS] = {0}; + bool colImpliesNotNull[INDEX_MAX_KEYS] = {0}; MemoryContext oldCtx; /* @@ -298,6 +309,7 @@ ginNewScanKey(IndexScanDesc scan) bool *nullFlags = NULL; GinNullCategory *categories; int32 searchMode = GIN_SEARCH_MODE_DEFAULT; + int colno = skey->sk_attno - 1; /* * We assume that GIN-indexable operators are strict, so a null query @@ -311,8 +323,8 @@ ginNewScanKey(IndexScanDesc scan) /* OK to call the extractQueryFn */ queryValues = (Datum *) - DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[skey->sk_attno - 1], - so->ginstate.supportCollation[skey->sk_attno - 1], + DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[colno], + so->ginstate.supportCollation[colno], skey->sk_argument, PointerGetDatum(&nQueryValues), UInt16GetDatum(skey->sk_strategy), @@ -342,7 +354,32 @@ ginNewScanKey(IndexScanDesc scan) } else if (searchMode == GIN_SEARCH_MODE_ALL) { - so->forcedRecheck = true; + /* + * Don't emit ALL key with no entries, check only whether + * unconditional recheck is needed. + */ + if (!so->forcedRecheck) + { + GinScanKeyData key; + + ginFillScanKey(so, &key, false, skey->sk_attno, + skey->sk_strategy, searchMode, + skey->sk_argument, 0, + NULL, NULL, NULL, NULL); + + so->forcedRecheck |= key.triConsistentFn(&key) != GIN_TRUE; + } + + /* + * Increment the number of columns with NOT NULL constraints + * if NOT NULL is not yet implied. + */ + if (!colImpliesNotNull[colno] && !colNeedsNotNull[colno]) + { + colNeedsNotNull[colno] = true; + numColsNeedNotNull++; + } + continue; } @@ -373,24 +410,71 @@ ginNewScanKey(IndexScanDesc scan) } } - ginFillScanKey(so, skey->sk_attno, + ginFillScanKey(so, NULL, true, skey->sk_attno, skey->sk_strategy, searchMode, skey->sk_argument, nQueryValues, queryValues, categories, partial_matches, extra_data); + + /* + * Current key implies that column is NOT NULL, so decrement the number + * of columns with NOT NULL constraints. + */ + colImpliesNotNull[colno] = true; + + if (colNeedsNotNull[colno]) + { + colNeedsNotNull[colno] = false; + numColsNeedNotNull--; + } } - /* - * If there are no regular scan keys, generate an EVERYTHING scankey to - * drive a full-index scan. - */ - if (so->nkeys == 0 && !so->isVoidRes) + if (!so->isVoidRes) { - hasNullQuery = true; - ginFillScanKey(so, FirstOffsetNumber, - InvalidStrategy, GIN_SEARCH_MODE_EVERYTHING, - (Datum) 0, 0, - NULL, NULL, NULL, NULL); + /* + * If there are no regular scan keys, generate an EVERYTHING or + * NOT_NULL scankey to drive a full-index scan. + */ + if (so->nkeys == 0) + { + hasNullQuery = true; + + /* Initialize EVERYTHING key if there are no NOT NULL columns. */ + if (!numColsNeedNotNull) + { + ginFillScanKey(so, NULL, true, FirstOffsetNumber, + InvalidStrategy, GIN_SEARCH_MODE_EVERYTHING, + (Datum) 0, 0, NULL, NULL, NULL, NULL); + } + else + { + /* + * Initialize only one NOT_NULL key for the first found + * NOT NULL column and force recheck if there are more than + * one NOT NULL column. + */ + so->forcedRecheck |= numColsNeedNotNull > 1; + + for (i = 0; i < scan->indexRelation->rd_att->natts; i++) + { + if (colNeedsNotNull[i]) + { + ginFillScanKey(so, NULL, true, i + 1, InvalidStrategy, + GIN_SEARCH_MODE_NOT_NULL, (Datum) 0, 0, + NULL, NULL, NULL, NULL); + break; + } + } + } + } + else if (numColsNeedNotNull > 0) + { + /* + * We use recheck instead of adding NOT_NULL entries to eliminate + * rows with NULL columns. + */ + so->forcedRecheck = true; + } } /* diff --git a/src/include/access/gin.h b/src/include/access/gin.h index a8eef5a..069d249 100644 --- a/src/include/access/gin.h +++ b/src/include/access/gin.h @@ -34,6 +34,7 @@ #define GIN_SEARCH_MODE_INCLUDE_EMPTY 1 #define GIN_SEARCH_MODE_ALL 2 #define GIN_SEARCH_MODE_EVERYTHING 3 /* for internal use only */ +#define GIN_SEARCH_MODE_NOT_NULL 4 /* for internal use only */ /* * GinStatsData represents stats data for planner use diff --git a/src/test/regress/expected/gin.out b/src/test/regress/expected/gin.out index fb0d29c..5b40691 100644 --- a/src/test/regress/expected/gin.out +++ b/src/test/regress/expected/gin.out @@ -38,28 +38,81 @@ vacuum gin_test_tbl; -- Test optimization of empty queries create temp table t_gin_test_tbl(i int4[], j int4[]); create index on t_gin_test_tbl using gin (i, j); -insert into t_gin_test_tbl select array[100,g], array[200,g] -from generate_series(1, 10) g; -insert into t_gin_test_tbl values(array[0,0], null); +insert into t_gin_test_tbl +values + (null, null), + ('{}', null), + ('{1}', null), + ('{1,2}', null), + (null, '{}'), + (null, '{10}'), + ('{1,2}', '{10}'), + ('{2}', '{10}'), + ('{1,3}', '{}'), + ('{1,1}', '{10}'); set enable_seqscan = off; -explain -select * from t_gin_test_tbl where array[0] <@ i; - QUERY PLAN --------------------------------------------------------------------------------------- - Bitmap Heap Scan on t_gin_test_tbl (cost=12.03..20.49 rows=4 width=64) - Recheck Cond: ('{0}'::integer[] <@ i) - -> Bitmap Index Scan on t_gin_test_tbl_i_j_idx (cost=0.00..12.03 rows=4 width=0) - Index Cond: (i @> '{0}'::integer[]) -(4 rows) +explain (analyze, costs off, timing off, summary off) +select * from t_gin_test_tbl where i @> '{}'; + QUERY PLAN +--------------------------------------------------------------------------- + Bitmap Heap Scan on t_gin_test_tbl (actual rows=7 loops=1) + Recheck Cond: (i @> '{}'::integer[]) + Heap Blocks: exact=1 + -> Bitmap Index Scan on t_gin_test_tbl_i_j_idx (actual rows=7 loops=1) + Index Cond: (i @> '{}'::integer[]) +(5 rows) -select * from t_gin_test_tbl where array[0] <@ i; - i | j --------+--- - {0,0} | -(1 row) - -select * from t_gin_test_tbl where array[0] <@ i and '{}'::int4[] <@ j; - i | j ----+--- -(0 rows) +create or replace function explain_query_json(query_sql text) +returns table (explain_line json) +language plpgsql as +$$ +begin + return query execute 'EXPLAIN (ANALYZE, FORMAT json) ' || query_sql; +end; +$$; +create or replace function execute_text_query(query_sql text) +returns setof text +language plpgsql +as +$$ +begin + return query execute query_sql; +end; +$$; +-- check number of rows returned by index and removed by recheck +select + query, + js->0->'Plan'->'Plans'->0->'Actual Rows' as "return by index", + js->0->'Plan'->'Rows Removed by Index Recheck' as "removed by recheck", + res as "result" +from + (values + ($$ i @> '{}' $$), + ($$ j @> '{}' $$), + ($$ i @> '{}' and j @> '{}' $$), + ($$ i @> '{1}' $$), + ($$ i @> '{1}' and j @> '{}' $$), + ($$ i @> '{1}' and i @> '{}' and j @> '{}' $$), + ($$ j @> '{10}' $$), + ($$ j @> '{10}' and i @> '{}' $$), + ($$ j @> '{10}' and j @> '{}' and i @> '{}' $$), + ($$ i @> '{1}' and j @> '{10}' $$) + ) q(query), + lateral explain_query_json($$select * from t_gin_test_tbl where $$ || query) js, + lateral execute_text_query($$select string_agg((i, j)::text, ' ') from t_gin_test_tbl where $$ || query) res; + query | return by index | removed by recheck | result +-------------------------------------------+-----------------+--------------------+------------------------------------------------------------------------------- + i @> '{}' | 7 | 0 | ({},) ({1},) ("{1,2}",) ("{1,2}",{10}) ({2},{10}) ("{1,3}",{}) ("{1,1}",{10}) + j @> '{}' | 6 | 0 | (,{}) (,{10}) ("{1,2}",{10}) ({2},{10}) ("{1,3}",{}) ("{1,1}",{10}) + i @> '{}' and j @> '{}' | 7 | 3 | ("{1,2}",{10}) ({2},{10}) ("{1,3}",{}) ("{1,1}",{10}) + i @> '{1}' | 5 | 0 | ({1},) ("{1,2}",) ("{1,2}",{10}) ("{1,3}",{}) ("{1,1}",{10}) + i @> '{1}' and j @> '{}' | 5 | 2 | ("{1,2}",{10}) ("{1,3}",{}) ("{1,1}",{10}) + i @> '{1}' and i @> '{}' and j @> '{}' | 5 | 2 | ("{1,2}",{10}) ("{1,3}",{}) ("{1,1}",{10}) + j @> '{10}' | 4 | 0 | (,{10}) ("{1,2}",{10}) ({2},{10}) ("{1,1}",{10}) + j @> '{10}' and i @> '{}' | 4 | 1 | ("{1,2}",{10}) ({2},{10}) ("{1,1}",{10}) + j @> '{10}' and j @> '{}' and i @> '{}' | 4 | 1 | ("{1,2}",{10}) ({2},{10}) ("{1,1}",{10}) + i @> '{1}' and j @> '{10}' | 2 | 0 | ("{1,2}",{10}) ("{1,1}",{10}) +(10 rows) +reset enable_seqscan; +drop table t_gin_test_tbl; diff --git a/src/test/regress/sql/gin.sql b/src/test/regress/sql/gin.sql index aaf9c19..57af762 100644 --- a/src/test/regress/sql/gin.sql +++ b/src/test/regress/sql/gin.sql @@ -38,11 +38,65 @@ vacuum gin_test_tbl; -- Test optimization of empty queries create temp table t_gin_test_tbl(i int4[], j int4[]); create index on t_gin_test_tbl using gin (i, j); -insert into t_gin_test_tbl select array[100,g], array[200,g] -from generate_series(1, 10) g; -insert into t_gin_test_tbl values(array[0,0], null); +insert into t_gin_test_tbl +values + (null, null), + ('{}', null), + ('{1}', null), + ('{1,2}', null), + (null, '{}'), + (null, '{10}'), + ('{1,2}', '{10}'), + ('{2}', '{10}'), + ('{1,3}', '{}'), + ('{1,1}', '{10}'); + set enable_seqscan = off; -explain -select * from t_gin_test_tbl where array[0] <@ i; -select * from t_gin_test_tbl where array[0] <@ i; -select * from t_gin_test_tbl where array[0] <@ i and '{}'::int4[] <@ j; + +explain (analyze, costs off, timing off, summary off) +select * from t_gin_test_tbl where i @> '{}'; + +create or replace function explain_query_json(query_sql text) +returns table (explain_line json) +language plpgsql as +$$ +begin + return query execute 'EXPLAIN (ANALYZE, FORMAT json) ' || query_sql; +end; +$$; + +create or replace function execute_text_query(query_sql text) +returns setof text +language plpgsql +as +$$ +begin + return query execute query_sql; +end; +$$; + +-- check number of rows returned by index and removed by recheck +select + query, + js->0->'Plan'->'Plans'->0->'Actual Rows' as "return by index", + js->0->'Plan'->'Rows Removed by Index Recheck' as "removed by recheck", + res as "result" +from + (values + ($$ i @> '{}' $$), + ($$ j @> '{}' $$), + ($$ i @> '{}' and j @> '{}' $$), + ($$ i @> '{1}' $$), + ($$ i @> '{1}' and j @> '{}' $$), + ($$ i @> '{1}' and i @> '{}' and j @> '{}' $$), + ($$ j @> '{10}' $$), + ($$ j @> '{10}' and i @> '{}' $$), + ($$ j @> '{10}' and j @> '{}' and i @> '{}' $$), + ($$ i @> '{1}' and j @> '{10}' $$) + ) q(query), + lateral explain_query_json($$select * from t_gin_test_tbl where $$ || query) js, + lateral execute_text_query($$select string_agg((i, j)::text, ' ') from t_gin_test_tbl where $$ || query) res; + +reset enable_seqscan; + +drop table t_gin_test_tbl; -- 2.7.4 --------------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"