pg.ddx.io pgsql-bugs@postgresql.org mailing list archive
help / color / mirror / Atom feedFrom: 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, 02 Oct 2026 15:01:07 -0300
Message-ID: <179096406728.463468.10787135519393288680@gmail.com> (raw)
In-Reply-To: <CALfch1_qFgqr24XQY4kB93Gr62Jx+GUqLA0QYTpWsfrEZZ0wWg@mail.gmail.com>
References: <CALfch1_qFgqr24XQY4kB93Gr62Jx+GUqLA0QYTpWsfrEZZ0wWg@mail.gmail.com>
Hi Palak,
> No further comments from me. The patch look good to me.
Thanks for the review.
Before anyone picks it up: cfbot fails v2 on the two Linux tasks
(CF 7382). Those builds use -fsanitize=undefined, and the server aborts
on the new "'' <<% t" query:
runtime error: load of value 126, which is not a valid value for
type 'bool' (calc_word_similarity, trgm_op.c:922)
The bug is not in v2; v2 only reaches it. After its merge loop,
calc_word_similarity() reads found[j] once more. When neither string
has a trigram, found[] has no elements and that read is past its end
(126 is 0x7E, the sentinel byte after a chunk in cassert builds).
Master does the same with "SELECT word_similarity('', '')". The value
never changes the result: with no trigrams in the second string the
similarity is 0 without using it.
v3 attached:
0001 checks len > 0 before that read, with a test for
word_similarity('', '').
0002 is v2, unchanged.
Built with the same sanitizer flags as cfbot, plus --enable-cassert:
master, 0001's test without its fix: aborts
master + v2: aborts on '' <<% t
master + v3: all 4 pg_trgm tests pass
REL_14_STABLE + v3: all 4 pg_trgm tests pass
Regards,
Manu
Attachments:
[text/x-patch] v3-0001-Fix-out-of-bounds-read-in-pg_trgm-word-similarity.patch (2.6K, ../179096406728.463468.10787135519393288680@gmail.com/2-v3-0001-Fix-out-of-bounds-read-in-pg_trgm-word-similarity.patch)
download | inline diff:
From 330c6ff741575b318b6bf00131cbca576d2e2387 Mon Sep 17 00:00:00 2001
From: Manuel Reyes Bravo <manuelreyesbravo@gmail.com>
Date: Fri, 2 Oct 2026 14:44:44 -0300
Subject: [PATCH v3 1/2] Fix out-of-bounds read in pg_trgm word similarity
calc_word_similarity() looks at found[j] once more after its merge
loop. When neither string has a trigram, as in word_similarity('',
''), found[] has no elements and that read is past its end.
The value never affects the result: with no trigrams in the second
string, iterate_word_similarity() returns 0 without using ulen1. But
it is undefined behavior, and builds with -fsanitize=undefined abort
on it. cfbot hit it through a test with stored empty strings in the
fix for bug #19701.
Backpatch-through: 14
Discussion: https://postgr.es/m/19701-c861a62e79bf49ce@postgresql.org
---
contrib/pg_trgm/expected/pg_word_trgm.out | 7 +++++++
contrib/pg_trgm/sql/pg_word_trgm.sql | 3 +++
contrib/pg_trgm/trgm_op.c | 3 ++-
3 files changed, 12 insertions(+), 1 deletion(-)
diff --git a/contrib/pg_trgm/expected/pg_word_trgm.out b/contrib/pg_trgm/expected/pg_word_trgm.out
index c66a67f30ef..17a3831dfe7 100644
--- a/contrib/pg_trgm/expected/pg_word_trgm.out
+++ b/contrib/pg_trgm/expected/pg_word_trgm.out
@@ -1050,3 +1050,10 @@ select * from test_trgm2 where t ~ '.*$x';
---
(0 rows)
+-- No trigrams on either side: must not read past the end of an empty array
+SELECT word_similarity('', ''), strict_word_similarity('', '');
+ word_similarity | strict_word_similarity
+-----------------+------------------------
+ 0 | 0
+(1 row)
+
diff --git a/contrib/pg_trgm/sql/pg_word_trgm.sql b/contrib/pg_trgm/sql/pg_word_trgm.sql
index d2ada49133a..304409728cc 100644
--- a/contrib/pg_trgm/sql/pg_word_trgm.sql
+++ b/contrib/pg_trgm/sql/pg_word_trgm.sql
@@ -46,3 +46,6 @@ select t,word_similarity('Kabankala',t) as sml from test_trgm2 where t %> 'Kaban
-- test unsatisfiable pattern
select * from test_trgm2 where t ~ '.*$x';
+
+-- No trigrams on either side: must not read past the end of an empty array
+SELECT word_similarity('', ''), strict_word_similarity('', '');
diff --git a/contrib/pg_trgm/trgm_op.c b/contrib/pg_trgm/trgm_op.c
index 22bcc3c3361..00cc0e5e63e 100644
--- a/contrib/pg_trgm/trgm_op.c
+++ b/contrib/pg_trgm/trgm_op.c
@@ -919,7 +919,8 @@ calc_word_similarity(char *str1, int slen1, char *str2, int slen2,
found[j] = true;
}
}
- if (found[j])
+ /* With no trigrams at all, found[] is empty and there is no last one */
+ if (len > 0 && found[j])
ulen1++;
/* Run iterative procedure to find maximum similarity with word */
--
2.55.0
[text/x-patch] v3-0002-Don-t-lose-rows-in-pg_trgm-index-scans-with-a-zer.patch (11.0K, ../179096406728.463468.10787135519393288680@gmail.com/3-v3-0002-Don-t-lose-rows-in-pg_trgm-index-scans-with-a-zer.patch)
download | inline diff:
From e63b25f3145b3d6566dbe32fc30d4c3588b85e27 Mon Sep 17 00:00:00 2001
From: Manu <manuelreyesbravo@gmail.com>
Date: Wed, 23 Sep 2026 16:23:12 -0300
Subject: [PATCH v3 2/2] 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
view thread (6+ messages)
Message-ID: <179096406728.463468.10787135519393288680@gmail.com>
Permalink: ../179096406728.463468.10787135519393288680@gmail.com/
Also on: postgresql.org/message-id/179096406728.463468.10787135519393288680@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, chaturvedipalak1911@gmail.com, kehan5800@gmail.com
Subject: Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0
In-Reply-To: <179096406728.463468.10787135519393288680@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