From: Manu <manuelreyesbravo@gmail.com>
To: pgsql-bugs@lists.postgresql.org
Cc: chaturvedipalak1911@gmail.com
Cc: kehan5800@gmail.com
Subject: Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0
Date: Fri, 25 Sep 2026 12:38:08 -0300
Message-ID: <179035068842.432745.14403644565457508812@gmail.com> (raw)
In-Reply-To: <CALfch18RBVgv+hr6rxwzjsHpJcmnL4_9FByY7Z+oxx8eMy4aDg@mail.gmail.com>
References: <CALfch18RBVgv+hr6rxwzjsHpJcmnL4_9FByY7Z+oxx8eMy4aDg@mail.gmail.com>
Hi Palak,
Thanks for the review and for the row-set comparison.
On Fri, 25 Sept 2026, Palak Chaturvedi wrote:
> * Insert rows after creating the GIN index, then test an empty
> query at threshold zero before and after pending-list cleanup.
>
> * Include strict-word similarity (<<%) at zero, with stored empty
> strings and NULLs.
Both are in v2, attached. The new test uses a small table holding
two words, two empty strings and a NULL, inserted after the GIN index
is created. It runs % and <<%, with an empty and a non-empty query,
before and after gin_clean_pending_list(). It then rebuilds the index
as GiST and repeats the <<% queries. I added 1000 rows before the
GiST build: with only five rows the index is a single leaf page, and
leaf pages were already correct.
Without the C changes, each of the eight GIN queries returns 0 or 1
row instead of 4, both before and after the cleanup, and the empty
<<% query on GiST returns 0 instead of 1004. With them, pg_trgm's
tests pass. I checked this on master (45da2c1d756) and on
REL_14_STABLE, where v2 also applies cleanly.
Regards,
Manu
Attachments:v2-0001-Don-t-lose-rows-in-pg_trgm-index-scans-with-a-zer.patch (text/x-patch, 11.0K) download
From e4c025ac90a4af0b703af020b1ff079f21b21662 Mon Sep 17 00:00:00 2001
From: Manu <manuelreyesbravo@gmail.com>
Date: Wed, 23 Sep 2026 16:23:12 -0300
Subject: [PATCH v2] Don't lose rows in pg_trgm index scans with a zero
similarity threshold
The similarity operators (%, <% and <<%) are true when the similarity is
greater than or equal to the threshold, and zero is a valid threshold,
under which every row matches. The indexes did not follow:
- A GIN scan only visits the rows that share a trigram with the query,
so the rows with none were never returned. Ask for a full index scan
when the threshold is zero, as is already done when the query has no
trigrams.
- When the query has no trigrams, both the GIN consistent functions and
the GiST consistent function on internal pages rejected everything,
although the similarity with such a query is zero, which a zero
threshold accepts.
Reported-by: Ke <kehan5800@gmail.com>
Discussion: https://postgr.es/m/19701-c861a62e79bf49ce@postgresql.org
---
contrib/pg_trgm/expected/pg_trgm.out | 175 +++++++++++++++++++++++++++
contrib/pg_trgm/sql/pg_trgm.sql | 51 ++++++++
contrib/pg_trgm/trgm_gin.c | 24 +++-
contrib/pg_trgm/trgm_gist.c | 6 +-
4 files changed, 251 insertions(+), 5 deletions(-)
diff --git a/contrib/pg_trgm/expected/pg_trgm.out b/contrib/pg_trgm/expected/pg_trgm.outindex 612625f1fda..cc30a2e636a 100644--- a/contrib/pg_trgm/expected/pg_trgm.out+++ b/contrib/pg_trgm/expected/pg_trgm.out@@ -5448,3 +5448,178 @@ SELECT DISTINCT city, similarity(city, 'Warsaw'), show_limit()
Warsaw | 1 | 0.5
(1 row)
+-- A threshold of zero is met by every row: by the rows that share no trigram+-- with the query, and by all of them when the query has no trigrams at all.+-- The indexes must not lose any (bug #19701).+SELECT set_limit(0);+ set_limit +-----------+ 0+(1 row)++SET pg_trgm.word_similarity_threshold = 0;+EXPLAIN (COSTS OFF)+SELECT count(*) FROM restaurants WHERE city % 'Warsaw';+ QUERY PLAN +-------------------------------------------------------+ Aggregate+ -> Bitmap Heap Scan on restaurants+ Recheck Cond: (city % 'Warsaw'::text)+ -> Bitmap Index Scan on restaurants_city_idx+ Index Cond: (city % 'Warsaw'::text)+(5 rows)++SELECT count(*) FROM restaurants WHERE city % 'Warsaw';+ count +-------+ 20000+(1 row)++SELECT count(*) FROM restaurants WHERE city % '';+ count +-------+ 20000+(1 row)++SELECT count(*) FROM restaurants WHERE 'Warsaw' <% city;+ count +-------+ 20000+(1 row)++DROP INDEX restaurants_city_idx;+CREATE INDEX ON restaurants USING gin(city gin_trgm_ops);+EXPLAIN (COSTS OFF)+SELECT count(*) FROM restaurants WHERE city % 'Warsaw';+ QUERY PLAN +-------------------------------------------------------+ Aggregate+ -> Bitmap Heap Scan on restaurants+ Recheck Cond: (city % 'Warsaw'::text)+ -> Bitmap Index Scan on restaurants_city_idx+ Index Cond: (city % 'Warsaw'::text)+(5 rows)++SELECT count(*) FROM restaurants WHERE city % 'Warsaw';+ count +-------+ 20000+(1 row)++SELECT count(*) FROM restaurants WHERE city % '';+ count +-------+ 20000+(1 row)++SELECT count(*) FROM restaurants WHERE 'Warsaw' <% city;+ count +-------+ 20000+(1 row)++RESET pg_trgm.word_similarity_threshold;+-- The same for rows that are still in the GIN pending list, and for strict+-- word similarity, with empty strings and NULLs stored. Every non-NULL row+-- must be returned.+SET pg_trgm.strict_word_similarity_threshold = 0;+SET enable_seqscan = off;+CREATE TEMP TABLE trgm_zero (t text);+CREATE INDEX trgm_zero_idx ON trgm_zero+ USING gin (t gin_trgm_ops) WITH (fastupdate = on);+INSERT INTO trgm_zero VALUES ('Warsaw'), ('Szczecin'), (''), (''), (NULL);+EXPLAIN (COSTS OFF)+SELECT count(*) FROM trgm_zero WHERE t % '';+ QUERY PLAN +------------------------------------------------+ Aggregate+ -> Bitmap Heap Scan on trgm_zero+ Recheck Cond: (t % ''::text)+ -> Bitmap Index Scan on trgm_zero_idx+ Index Cond: (t % ''::text)+(5 rows)++SELECT count(*) FROM trgm_zero WHERE t % '';+ count +-------+ 4+(1 row)++SELECT count(*) FROM trgm_zero WHERE t % 'Warsaw';+ count +-------+ 4+(1 row)++SELECT count(*) FROM trgm_zero WHERE '' <<% t;+ count +-------+ 4+(1 row)++SELECT count(*) FROM trgm_zero WHERE 'Warsaw' <<% t;+ count +-------+ 4+(1 row)++SELECT gin_clean_pending_list('trgm_zero_idx') > 0 AS cleaned;+ cleaned +---------+ t+(1 row)++SELECT count(*) FROM trgm_zero WHERE t % '';+ count +-------+ 4+(1 row)++SELECT count(*) FROM trgm_zero WHERE t % 'Warsaw';+ count +-------+ 4+(1 row)++SELECT count(*) FROM trgm_zero WHERE '' <<% t;+ count +-------+ 4+(1 row)++SELECT count(*) FROM trgm_zero WHERE 'Warsaw' <<% t;+ count +-------+ 4+(1 row)++-- Enough rows for the GiST index to have internal pages.+DROP INDEX trgm_zero_idx;+INSERT INTO trgm_zero SELECT 'Warsaw' FROM generate_series(1, 1000);+CREATE INDEX trgm_zero_idx ON trgm_zero USING gist (t gist_trgm_ops);+EXPLAIN (COSTS OFF)+SELECT count(*) FROM trgm_zero WHERE '' <<% t;+ QUERY PLAN +------------------------------------------------+ Aggregate+ -> Bitmap Heap Scan on trgm_zero+ Filter: (''::text <<% t)+ -> Bitmap Index Scan on trgm_zero_idx+ Index Cond: (t %>> ''::text)+(5 rows)++SELECT count(*) FROM trgm_zero WHERE '' <<% t;+ count +-------+ 1004+(1 row)++SELECT count(*) FROM trgm_zero WHERE 'Warsaw' <<% t;+ count +-------+ 1004+(1 row)++DROP TABLE trgm_zero;+RESET enable_seqscan;+RESET pg_trgm.strict_word_similarity_threshold;diff --git a/contrib/pg_trgm/sql/pg_trgm.sql b/contrib/pg_trgm/sql/pg_trgm.sqlindex 49db86caf7d..2514ce5d7f0 100644--- a/contrib/pg_trgm/sql/pg_trgm.sql+++ b/contrib/pg_trgm/sql/pg_trgm.sql@@ -244,3 +244,54 @@ SELECT DISTINCT city, similarity(city, 'Warsaw'), show_limit()
SELECT set_limit(0.5);
SELECT DISTINCT city, similarity(city, 'Warsaw'), show_limit()
FROM restaurants WHERE city % 'Warsaw';
++-- A threshold of zero is met by every row: by the rows that share no trigram+-- with the query, and by all of them when the query has no trigrams at all.+-- The indexes must not lose any (bug #19701).+SELECT set_limit(0);+SET pg_trgm.word_similarity_threshold = 0;+EXPLAIN (COSTS OFF)+SELECT count(*) FROM restaurants WHERE city % 'Warsaw';+SELECT count(*) FROM restaurants WHERE city % 'Warsaw';+SELECT count(*) FROM restaurants WHERE city % '';+SELECT count(*) FROM restaurants WHERE 'Warsaw' <% city;+DROP INDEX restaurants_city_idx;+CREATE INDEX ON restaurants USING gin(city gin_trgm_ops);+EXPLAIN (COSTS OFF)+SELECT count(*) FROM restaurants WHERE city % 'Warsaw';+SELECT count(*) FROM restaurants WHERE city % 'Warsaw';+SELECT count(*) FROM restaurants WHERE city % '';+SELECT count(*) FROM restaurants WHERE 'Warsaw' <% city;+RESET pg_trgm.word_similarity_threshold;++-- The same for rows that are still in the GIN pending list, and for strict+-- word similarity, with empty strings and NULLs stored. Every non-NULL row+-- must be returned.+SET pg_trgm.strict_word_similarity_threshold = 0;+SET enable_seqscan = off;+CREATE TEMP TABLE trgm_zero (t text);+CREATE INDEX trgm_zero_idx ON trgm_zero+ USING gin (t gin_trgm_ops) WITH (fastupdate = on);+INSERT INTO trgm_zero VALUES ('Warsaw'), ('Szczecin'), (''), (''), (NULL);+EXPLAIN (COSTS OFF)+SELECT count(*) FROM trgm_zero WHERE t % '';+SELECT count(*) FROM trgm_zero WHERE t % '';+SELECT count(*) FROM trgm_zero WHERE t % 'Warsaw';+SELECT count(*) FROM trgm_zero WHERE '' <<% t;+SELECT count(*) FROM trgm_zero WHERE 'Warsaw' <<% t;+SELECT gin_clean_pending_list('trgm_zero_idx') > 0 AS cleaned;+SELECT count(*) FROM trgm_zero WHERE t % '';+SELECT count(*) FROM trgm_zero WHERE t % 'Warsaw';+SELECT count(*) FROM trgm_zero WHERE '' <<% t;+SELECT count(*) FROM trgm_zero WHERE 'Warsaw' <<% t;+-- Enough rows for the GiST index to have internal pages.+DROP INDEX trgm_zero_idx;+INSERT INTO trgm_zero SELECT 'Warsaw' FROM generate_series(1, 1000);+CREATE INDEX trgm_zero_idx ON trgm_zero USING gist (t gist_trgm_ops);+EXPLAIN (COSTS OFF)+SELECT count(*) FROM trgm_zero WHERE '' <<% t;+SELECT count(*) FROM trgm_zero WHERE '' <<% t;+SELECT count(*) FROM trgm_zero WHERE 'Warsaw' <<% t;+DROP TABLE trgm_zero;+RESET enable_seqscan;+RESET pg_trgm.strict_word_similarity_threshold;diff --git a/contrib/pg_trgm/trgm_gin.c b/contrib/pg_trgm/trgm_gin.cindex 5766b3e9955..243d5bbeea9 100644--- a/contrib/pg_trgm/trgm_gin.c+++ b/contrib/pg_trgm/trgm_gin.c@@ -165,6 +165,17 @@ gin_extract_query_trgm(PG_FUNCTION_ARGS)
if (trglen == 0)
*searchMode = GIN_SEARCH_MODE_ALL;
+ /*+ * Likewise when the similarity threshold is zero: every row satisfies the+ * operator then, including the rows that share no trigram with the query,+ * which the extracted trigrams alone would never lead to.+ */+ if ((strategy == SimilarityStrategyNumber ||+ strategy == WordSimilarityStrategyNumber ||+ strategy == StrictWordSimilarityStrategyNumber) &&+ index_strategy_get_limit(strategy) <= 0.0)+ *searchMode = GIN_SEARCH_MODE_ALL;+
PG_RETURN_POINTER(entries);
}
@@ -216,8 +227,11 @@ gin_trgm_consistent(PG_FUNCTION_ARGS)
* just by definition and, consequently, upper bound of
* similarity is just c / len1.
* So, independently on DIVUNION the upper bound formula is the same.
+ *+ * A query with no trigrams has a similarity of zero with any+ * value, which only a threshold of zero accepts.
*/
- res = (nkeys == 0) ? false :+ res = (nkeys == 0) ? (nlimit <= 0.0) :
(((((float4) ntrue) / ((float4) nkeys))) >= nlimit);
break;
case ILikeStrategyNumber:
@@ -302,9 +316,11 @@ gin_trgm_triconsistent(PG_FUNCTION_ARGS)
* See comment in gin_trgm_consistent() about * upper bound
* formula
*/
- res = (nkeys == 0)- ? GIN_FALSE : (((((float4) ntrue) / ((float4) nkeys)) >= nlimit)- ? GIN_MAYBE : GIN_FALSE);+ if (nkeys == 0)+ res = (nlimit <= 0.0) ? GIN_MAYBE : GIN_FALSE;+ else+ res = (((((float4) ntrue) / ((float4) nkeys)) >= nlimit)+ ? GIN_MAYBE : GIN_FALSE);
break;
case ILikeStrategyNumber:
#ifndef IGNORECASE
diff --git a/contrib/pg_trgm/trgm_gist.c b/contrib/pg_trgm/trgm_gist.cindex 42d0b7a5d65..0cb68ac757e 100644--- a/contrib/pg_trgm/trgm_gist.c+++ b/contrib/pg_trgm/trgm_gist.c@@ -335,8 +335,12 @@ gtrgm_consistent(PG_FUNCTION_ARGS)
int32 count = cnt_sml_sign_common(qtrg, GETSIGN(key), siglen);
int32 len = ARRNELEM(qtrg);
+ /*+ * A query with no trigrams has a similarity of zero with any+ * value, which only a threshold of zero accepts.+ */
if (len == 0)
- res = false;+ res = (nlimit <= 0.0);
else
res = (((((float8) count) / ((float8) len))) >= nlimit);
}
--
2.55.0
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-bugs@postgresql.org
Cc: manuelreyesbravo@gmail.com, pgsql-bugs@lists.postgresql.org, chaturvedipalak1911@gmail.com, kehan5800@gmail.com
Subject: Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0
In-Reply-To: <179035068842.432745.14403644565457508812@gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox