agora inbox for pgsql-bugs@postgresql.org
help / color / mirror / Atom feedBUG #19701: GIN trigram index loses rows at similarity_threshold 0
5+ messages / 3 participants
[nested] [flat]
* BUG #19701: GIN trigram index loses rows at similarity_threshold 0
@ 2026-09-19 05:17 PG Bug reporting form <noreply@postgresql.org>
2026-09-23 19:26 ` Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0 Manu <manuelreyesbravo@gmail.com>
0 siblings, 1 reply; 5+ messages in thread
From: PG Bug reporting form @ 2026-09-19 05:17 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org; +Cc: kehan5800@gmail.com
The following bug has been logged on the website:
Bug reference: 19701
Logged by: Ke
Email address: kehan5800@gmail.com
PostgreSQL version: 18.6
Operating system: Ubuntu 22.04.5 LTS x86_64, gcc 11.4.0, source buil
Description:
With pg_trgm.similarity_threshold set to 0 -- a legal value; it is the
declared
minimum of the GUC, and pg_settings reports min_val 0 -- a gin_trgm_ops
index
changes the result of a query that uses the % operator. The sequential scan
returns every row, because the operator is implemented as
similarity(a, b) >= pg_trgm.similarity_threshold
and every similarity is >= 0. The GIN scan returns only the rows that share
at
least one trigram with the query string. There is no error and no warning;
rows
are simply missing. A gist_trgm_ops index over the same data is correct, so
the
two index implementations of one operator disagree, and at most one of them
can
be right.
What I did
----------
CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE TABLE m (v text);
INSERT INTO m VALUES ('apple'), ('xyzzy');
CREATE INDEX m_gin ON m USING gin (v gin_trgm_ops);
SET pg_trgm.similarity_threshold = 0;
SELECT v, similarity(v, 'apple'), v % 'apple' FROM m;
v | similarity | ?column?
------+------------+----------
apple| 1 | t
xyzzy| 0 | t <-- the operator says this row matches
SET enable_seqscan = on; SET enable_indexscan = off; SET
enable_bitmapscan = off;
SELECT * FROM m WHERE v % 'apple'; -- apple, xyzzy
SET enable_seqscan = off; SET enable_indexscan = on; SET
enable_bitmapscan = on;
SELECT * FROM m WHERE v % 'apple'; -- apple
EXPLAIN (COSTS OFF) SELECT * FROM m WHERE v % 'apple';
Bitmap Heap Scan on m
Recheck Cond: (v % 'apple'::text)
-> Bitmap Index Scan on m_gin
Index Cond: (v % 'apple'::text)
What I expected
---------------
The same rows either way. An index must not change the answer.
What happened
-------------
The row 'xyzzy' is returned by the sequential scan and not by the index
scan,
although 'xyzzy' % 'apple' evaluates to true.
The enable_* settings above are only there to pin the two plans on a two-row
table. The defect does not need them. With a realistic table the planner
picks
the index scan by itself and the answer it produces is wrong:
CREATE TABLE z (t text);
INSERT INTO z SELECT md5(g::text) FROM generate_series(1, 200000) g;
INSERT INTO z VALUES ('apple');
CREATE INDEX zi ON z USING gin (t gin_trgm_ops);
ANALYZE z;
SET pg_trgm.similarity_threshold = 0;
-- all planner settings at their defaults:
EXPLAIN (COSTS OFF) SELECT count(*) FROM z WHERE t % 'apple' AND t =
md5('7');
Aggregate
-> Bitmap Heap Scan on z
Recheck Cond: ((t % 'apple'::text) AND (t =
'8f14e45f...'::text))
-> Bitmap Index Scan on zi
Index Cond: ((t % 'apple'::text) AND (t =
'8f14e45f...'::text))
SELECT count(*) FROM z WHERE t % 'apple' AND t = md5('7'); -- 0
-- with enable_indexscan/enable_bitmapscan off: -- 1
SELECT similarity(md5('7'), 'apple'); -- 0
That row exists, and md5('7') % 'apple' is true at this threshold, but the
planner's own choice of plan does not return it.
Scale, on the same 200 001-row table:
threshold | seq scan | gin index | rows lost
----------+----------+-----------+-----------
0 | 200001 | 12410 | 187591 <-- 94% of the table
1e-300 | 12410 | 12410 | 0
1e-45 | 12410 | 12410 | 0
1e-10 | 12410 | 12410 | 0
0.01 | 12410 | 12410 | 0
0.3 | 1 | 1 | 0
The boundary is exact: 0 is affected, 1e-300 is not. Five consecutive runs
give
the same numbers. set_limit(0), the documented function form of the same
setting, behaves identically (set_limit returns 0, show_limit returns 0, the
indexed count is still 12410).
All six similarity operators are affected, and GiST is correct for all six
----------------------------------------------------------------------------
Table ('apple'), ('banana'), ('zebra'), ('quick brown fox'), (''), with
pg_trgm.similarity_threshold, pg_trgm.word_similarity_threshold and
pg_trgm.strict_word_similarity_threshold all set to 0. Predicates are
written in
the indexable order -- 't <% ''apple''' is not an indexable form, it falls
back to
a sequential scan and so looks correct for the wrong reason; its commutator
is
the one that reaches the index. Every line below was confirmed from EXPLAIN
to
be a real index scan.
GIN gin_trgm_ops GiST gist_trgm_ops
predicate seq index seq index
-------------- ---- ---------------- ---- -----
t % 'apple' 5 1 wrong 5 5 ok
'apple' % t 5 1 wrong 5 5 ok
'apple' <% t 5 1 wrong 5 5 ok
'apple' <<% t 5 1 wrong 5 5 ok
t %> 'apple' 5 1 wrong 5 5 ok
t %>> 'apple' 5 1 wrong 5 5 ok
t % '' 5 0 wrong 5 5 ok
The last line is the extreme case: a query string with no trigrams at all
(show_trgm('') is {}) returns zero rows from the GIN index and the whole
table
from a sequential scan.
Suspected cause
---------------
Two separate places, both in contrib/pg_trgm/trgm_gin.c.
1. gin_extract_query_trgm() leaves *searchMode at GIN_SEARCH_MODE_DEFAULT
for
SimilarityStrategyNumber, WordSimilarityStrategyNumber and
StrictWordSimilarityStrategyNumber whenever at least one trigram was
extracted. DEFAULT means "the heap tuple must contain at least one of
the
extracted query trigrams", so a row sharing no trigram with the query
string
is never fetched and never offered to the consistent function. The
recheck
can only remove candidates, never restore them. At any threshold above 0
that is a sound optimisation, because sharing no trigram implies
similarity 0
implies a similarity below the threshold. At exactly 0 the implication
fails:
similarity 0 passes a threshold of 0.
2. gin_trgm_consistent() and gin_trgm_triconsistent() return false /
GIN_FALSE
unconditionally when nkeys == 0. That is the '' case: extract_query does
set
GIN_SEARCH_MODE_ALL when no trigram could be extracted, so the scan does
visit
the index, but every candidate is then rejected, and the query returns
zero
rows.
The GIN consistent function's own similarity test is not at fault: with
nlimit = 0 the test ntrue / nkeys >= nlimit is true for any candidate it is
given.
The loss is entirely upstream of it.
GiST has no equivalent shortcut -- gtrgm_consistent admits the whole key
space at
nlimit 0 -- so the GiST scan still visits every row, which is why it is
correct.
Which behaviour is correct is, unfortunately, ambiguous -- and that is a
second,
smaller defect
------------------------------------------------------------------------------
The documentation for %, <% and <<% says each returns true when the
similarity is
"greater than" the threshold (doc/src/sgml/pgtrgm.sgml, unchanged on
master).
The implementation is >= (trgm_op.c, the PG_RETURN_BOOL lines in
trgm_similarity_op,
word_similarity_op and friends; and >= in both consistent functions). At
any
threshold above 0 the difference is invisible, because no pair of strings
has a
similarity exactly equal to a typical threshold. At exactly 0 it is the
whole
question:
- under the documented "greater than", rows of similarity 0 should not
match,
so the sequential scan and GiST are wrong and GIN is accidentally right;
- under the implemented >=, they should match, so GIN is wrong.
Either way two of the three paths disagree with the third, which is the
report.
But a fix has to settle the documented semantics first. For what it is
worth,
>= has been the implemented meaning since at least 2016, when BUG #14202 was
fixed by replacing gtrgm_consistent's bit-pattern comparison with a plain
res = tmpsml >= nlimit; and set_limit() has accepted 0 (its check has always
been
nlimit < 0 || nlimit > 1.0) since the module was added. So the simplest
reading
is that the code is right, the docs should say "greater than or equal to",
and
GIN is the path that needs fixing.
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0
2026-09-19 05:17 BUG #19701: GIN trigram index loses rows at similarity_threshold 0 PG Bug reporting form <noreply@postgresql.org>
@ 2026-09-23 19:26 ` Manu <manuelreyesbravo@gmail.com>
2026-09-25 09:09 ` Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0 Palak Chaturvedi <chaturvedipalak1911@gmail.com>
0 siblings, 1 reply; 5+ messages in thread
From: Manu @ 2026-09-23 19:26 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org; +Cc: kehan5800@gmail.com
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
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0
2026-09-19 05:17 BUG #19701: GIN trigram index loses rows at similarity_threshold 0 PG Bug reporting form <noreply@postgresql.org>
2026-09-23 19:26 ` Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0 Manu <manuelreyesbravo@gmail.com>
@ 2026-09-25 09:09 ` Palak Chaturvedi <chaturvedipalak1911@gmail.com>
2026-09-25 15:38 ` Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0 Manu <manuelreyesbravo@gmail.com>
0 siblings, 1 reply; 5+ messages in thread
From: Palak Chaturvedi @ 2026-09-25 09:09 UTC (permalink / raw)
To: Manu <manuelreyesbravo@gmail.com>; +Cc: pgsql-bugs@lists.postgresql.org; kehan5800@gmail.com
Hi Manu,
Thanks for your patch, I reviewed your patch and tested it on master
at 4545cee303c with
assertions enabled. All four pg_trgm regression tests pass.
Without the C changes, the new tests fail as expected.
I also compared exact row sets from sequential and GIN/GiST index
scans for all six operator forms at zero and positive thresholds.
These covered ordinary, empty and punctuation-only queries, with
empty strings and NULLs among the stored values.
Without the patch, sequential and index scans returned different
rows only when the relevant similarity threshold was zero.
With the patch, their results matched in every case tested.
I did not find a correctness issue. Could you add coverage for
these cases to the regression tests?
* 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.
The suggestions are to preserve that coverage in the regression suite.
Thanks,
Palak
On Thu, 24 Sept 2026 at 00:56, Manu <manuelreyesbravo@gmail.com> wrote:
>
> 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
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0
2026-09-19 05:17 BUG #19701: GIN trigram index loses rows at similarity_threshold 0 PG Bug reporting form <noreply@postgresql.org>
2026-09-23 19:26 ` Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0 Manu <manuelreyesbravo@gmail.com>
2026-09-25 09:09 ` Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0 Palak Chaturvedi <chaturvedipalak1911@gmail.com>
@ 2026-09-25 15:38 ` Manu <manuelreyesbravo@gmail.com>
2026-09-27 15:08 ` Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0 Palak Chaturvedi <chaturvedipalak1911@gmail.com>
0 siblings, 1 reply; 5+ messages in thread
From: Manu @ 2026-09-25 15:38 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org; +Cc: chaturvedipalak1911@gmail.com; kehan5800@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:
[text/x-patch] v2-0001-Don-t-lose-rows-in-pg_trgm-index-scans-with-a-zer.patch (11.0K, ../../179035068842.432745.14403644565457508812@gmail.com/2-v2-0001-Don-t-lose-rows-in-pg_trgm-index-scans-with-a-zer.patch)
download | inline diff:
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.out
index 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.sql
index 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.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
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0
2026-09-19 05:17 BUG #19701: GIN trigram index loses rows at similarity_threshold 0 PG Bug reporting form <noreply@postgresql.org>
2026-09-23 19:26 ` Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0 Manu <manuelreyesbravo@gmail.com>
2026-09-25 09:09 ` Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0 Palak Chaturvedi <chaturvedipalak1911@gmail.com>
2026-09-25 15:38 ` Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0 Manu <manuelreyesbravo@gmail.com>
@ 2026-09-27 15:08 ` Palak Chaturvedi <chaturvedipalak1911@gmail.com>
0 siblings, 0 replies; 5+ messages in thread
From: Palak Chaturvedi @ 2026-09-27 15:08 UTC (permalink / raw)
To: Manu <manuelreyesbravo@gmail.com>; +Cc: pgsql-bugs@lists.postgresql.org; kehan5800@gmail.com
Hi Manu,
Thanks for v2. Both suggestions are covered. All four pg_trgm
regression tests pass on an assertion-enabled master build, and
the new cases fail without the fix.
No further comments from me. The patch look good to me.
Regards,
Palak
On Fri, 25 Sept 2026 at 21:08, Manu <manuelreyesbravo@gmail.com> wrote:
>
> 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
^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2026-09-27 15:08 UTC | newest]
Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-09-19 05:17 BUG #19701: GIN trigram index loses rows at similarity_threshold 0 PG Bug reporting form <noreply@postgresql.org>
2026-09-23 19:26 ` Manu <manuelreyesbravo@gmail.com>
2026-09-25 09:09 ` Palak Chaturvedi <chaturvedipalak1911@gmail.com>
2026-09-25 15:38 ` Manu <manuelreyesbravo@gmail.com>
2026-09-27 15:08 ` Palak Chaturvedi <chaturvedipalak1911@gmail.com>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox