agora inbox for pgsql-bugs@postgresql.org
help / color / mirror / Atom feedFrom: Manu <manuelreyesbravo@gmail.com>
To: pgsql-bugs@lists.postgresql.org
Cc: kehan5800@gmail.com
Subject: Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0
Date: Wed, 23 Sep 2026 16:26:42 -0300
Message-ID: <179019160285.4009503.14265883830439530659@gmail.com> (raw)
In-Reply-To: <19701-c861a62e79bf49ce@postgresql.org>
References: <19701-c861a62e79bf49ce@postgresql.org>
Hi,
I can reproduce this on master (374522aa63a), and it is wider than the
report. With the thresholds at 0, on 5002 rows (100 of them empty
strings), a sequential scan returns all 5002 rows for each of these
queries. The indexes return:
- v % 'apple', 'apple' <% v, 'apple' <<% v: GIN 315, GiST 5002
- v % '', v % '#' (no trigrams): GIN 0, GiST 0
So all three similarity operators are affected in GIN, and GiST is
affected too, when the query has no trigrams. There are two causes:
1. gin_extract_query_trgm() returns the query's trigrams, so a GIN scan
only visits rows that share one of them. At a threshold of 0 every
row matches, including the ones that share none. The fix asks for
GIN_SEARCH_MODE_ALL when the threshold is 0, as the function already
does when the query has no trigrams.
2. When the query has no trigrams, gin_trgm_consistent() and
gin_trgm_triconsistent() return false outright, and so does
gtrgm_consistent() on GiST internal pages. The similarity with
such a query is 0, which a threshold of 0 accepts. GiST leaf pages
already get this right, which is why the report's three-row table
(a single leaf page) shows GiST as correct.
The attached patch fixes both and adds a test to the existing threshold
test on the restaurants table, for GiST and GIN. Without the C changes
the new test fails (GiST returns 0 for the empty query, GIN returns
10000 and 0 instead of 20000); with them, pg_trgm's tests pass. With
the default thresholds, all the queries above return the same as
before.
It applies cleanly to REL_14_STABLE through REL_19_STABLE; I built and
ran the pg_trgm tests on REL_18_STABLE as well.
Regards,
Manu
Attachments:
[text/x-patch] 0001-Don-t-lose-rows-in-pg_trgm-index-scans-with-a-zero-s.patch (7.1K, ../179019160285.4009503.14265883830439530659@gmail.com/2-0001-Don-t-lose-rows-in-pg_trgm-index-scans-with-a-zero-s.patch)
download | inline diff:
From ed8ae0f099f118e0bb5fcee5b0ccdf15b792e16a Mon Sep 17 00:00:00 2001
From: Manu <manuelreyesbravo@gmail.com>
Date: Wed, 23 Sep 2026 16:23:12 -0300
Subject: [PATCH] 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 | 71 ++++++++++++++++++++++++++++
contrib/pg_trgm/sql/pg_trgm.sql | 19 ++++++++
contrib/pg_trgm/trgm_gin.c | 24 ++++++++--
contrib/pg_trgm/trgm_gist.c | 6 ++-
4 files changed, 115 insertions(+), 5 deletions(-)
diff --git a/contrib/pg_trgm/expected/pg_trgm.out b/contrib/pg_trgm/expected/pg_trgm.out
index 612625f1fda..5f3bf1976fa 100644
--- a/contrib/pg_trgm/expected/pg_trgm.out
+++ b/contrib/pg_trgm/expected/pg_trgm.out
@@ -5448,3 +5448,74 @@ 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;
diff --git a/contrib/pg_trgm/sql/pg_trgm.sql b/contrib/pg_trgm/sql/pg_trgm.sql
index 49db86caf7d..091628a2bf9 100644
--- a/contrib/pg_trgm/sql/pg_trgm.sql
+++ b/contrib/pg_trgm/sql/pg_trgm.sql
@@ -244,3 +244,22 @@ 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;
diff --git a/contrib/pg_trgm/trgm_gin.c b/contrib/pg_trgm/trgm_gin.c
index 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.c
index 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
view thread (6+ messages) latest in thread
Message-ID: <179019160285.4009503.14265883830439530659@gmail.com>
Permalink: ../179019160285.4009503.14265883830439530659@gmail.com/
Also on: postgresql.org/message-id/179019160285.4009503.14265883830439530659@gmail.com
reply
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, kehan5800@gmail.com
Subject: Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0
In-Reply-To: <179019160285.4009503.14265883830439530659@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 agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox