pg_trgm: GiST index scan misses rows at the default word_similarity_threshold

Поиск
Список
Период
Сортировка
Искать

pg_trgm: GiST index scan misses rows at the default word_similarity_threshold

От:
Eric Laquer <laquereric@gmail.com>
Дата:
Hello,

At the default pg_trgm.word_similarity_threshold, a GiST (gist_trgm_ops) index scan for `<%` returns fewer rows than a sequential scan when a row's similarity is exactly the threshold. Seen on 17.9; the code is the same on master.

The defaults are float4 literals stored in doubles (trgm_op.c: `double word_similarity_threshold = 0.6f;`, so 0.6000000238...). A leaf computes similarity in float4 (CALCSML), 3/5 = 0.6000000238, which passes. gtrgm_consistent's non-leaf branch divides in float8, 3/5 = 0.59999999999999998, which is below the threshold, so the subtree is pruned. With the threshold SET to 0.6 (a double) both sides agree, which is why it only shows at the default. The same applies to the other two thresholds.

Reproduction (17.9, macOS arm64):

-- pg_trgm: a GiST index scan at the default word_similarity_threshold misses rows a scan returns
CREATE EXTENSION IF NOT EXISTS pg_trgm;
DROP TABLE IF EXISTS t;
CREATE TABLE t (id int, s text);
-- words with none of the letters p, r, a, t, so they share no trigram with 'prat'
INSERT INTO t SELECT g, string_agg(substr('bcdefghijklmnosuvwxyz', 1 + (abs(hashint4(g * 7 + i)) % 21), 1), '')
FROM generate_series(1, 20000) g, generate_series(1, 8) i GROUP BY g;
-- 'pram' shares exactly 3 of 'prat''s 5 trigrams: word_similarity('prat', 'pram') = 0.6, the default threshold
INSERT INTO t SELECT 100000 + g, 'pram' FROM generate_series(1, 50000) g;
CREATE INDEX t_trgm ON t USING gist (s gist_trgm_ops);
SELECT word_similarity('prat', 'pram') AS sml, current_setting('pg_trgm.word_similarity_threshold') AS threshold;
SET enable_indexscan = off; SET enable_bitmapscan = off;
SELECT 'seqscan' AS plan, count(*) FROM t WHERE 'prat' <% s;
RESET enable_indexscan; RESET enable_bitmapscan; SET enable_seqscan = off;
SELECT 'gist' AS plan, count(*) FROM t WHERE 'prat' <% s;
SET pg_trgm.word_similarity_threshold = 0.6; -- the same threshold, as a double
SELECT 'gist, threshold set' AS plan, count(*) FROM t WHERE 'prat' <% s;

Result:
sml | threshold
0.6 | 0.6

seqscan 50000
gist 375
gist, threshold set 50000

With the patch below (divide in float4 on non-leaf pages, as the leaf does) the GiST scan returns 50000, and pg_trgm's regression tests pass (4 of 4).

diff --git a/contrib/pg_trgm/trgm_gist.c b/contrib/pg_trgm/trgm_gist.c
index bd9b923..bbe0e14 100644
--- a/contrib/pg_trgm/trgm_gist.c
+++ b/contrib/pg_trgm/trgm_gist.c
@@ -337,7 +337,7 @@ gtrgm_consistent(PG_FUNCTION_ARGS)
if (len == 0)
res = false;
else
- res = (((((float8) count) / ((float8) len))) >= nlimit);
+ res = (((float4) count) / ((float4) len)) >= nlimit;
}
break;
case ILikeStrategyNumber:

An alternative would be double literals for the three defaults; the patch above keeps the inner check consistent with the leaf whatever the threshold is.

Thank you,
Eric Laquer

Re: pg_trgm: GiST index scan misses rows at the default word_similarity_threshold

От:
Kirill Reshke <reshkekirill@gmail.com>
Дата:
On Wed, 28 Oct 2026 at 14:17, Eric Laquer  wrote:
>
> Hello,
>
> At the default pg_trgm.word_similarity_threshold, a GiST (gist_trgm_ops) index scan for `<%` returns fewer rows than a sequential scan when a row's similarity is exactly the threshold. Seen on 17.9; the code is the same on master.
>
> The defaults are float4 literals stored in doubles (trgm_op.c: `double word_similarity_threshold = 0.6f;`, so 0.6000000238...). A leaf computes similarity in float4 (CALCSML), 3/5 = 0.6000000238, which passes. gtrgm_consistent's non-leaf branch divides in float8, 3/5 = 0.59999999999999998, which is below the threshold, so the subtree is pruned. With the threshold SET to 0.6 (a double) both sides agree, which is why it only shows at the default. The same applies to the other two thresholds.
>
> Reproduction (17.9, macOS arm64):
>
> -- pg_trgm: a GiST index scan at the default word_similarity_threshold misses rows a scan returns
> CREATE EXTENSION IF NOT EXISTS pg_trgm;
> DROP TABLE IF EXISTS t;
> CREATE TABLE t (id int, s text);
> -- words with none of the letters p, r, a, t, so they share no trigram with 'prat'
> INSERT INTO t SELECT g, string_agg(substr('bcdefghijklmnosuvwxyz', 1 + (abs(hashint4(g * 7 + i)) % 21), 1), '')
> FROM generate_series(1, 20000) g, generate_series(1, 8) i GROUP BY g;
> -- 'pram' shares exactly 3 of 'prat''s 5 trigrams: word_similarity('prat', 'pram') = 0.6, the default threshold
> INSERT INTO t SELECT 100000 + g, 'pram' FROM generate_series(1, 50000) g;
> CREATE INDEX t_trgm ON t USING gist (s gist_trgm_ops);
> SELECT word_similarity('prat', 'pram') AS sml, current_setting('pg_trgm.word_similarity_threshold') AS threshold;
> SET enable_indexscan = off; SET enable_bitmapscan = off;
> SELECT 'seqscan' AS plan, count(*) FROM t WHERE 'prat' <% s;
> RESET enable_indexscan; RESET enable_bitmapscan; SET enable_seqscan = off;
> SELECT 'gist' AS plan, count(*) FROM t WHERE 'prat' <% s;
> SET pg_trgm.word_similarity_threshold = 0.6; -- the same threshold, as a double
> SELECT 'gist, threshold set' AS plan, count(*) FROM t WHERE 'prat' <% s;
>
> Result:
> sml | threshold
> 0.6 | 0.6
>
> seqscan 50000
> gist 375
> gist, threshold set 50000
>
> With the patch below (divide in float4 on non-leaf pages, as the leaf does) the GiST scan returns 50000, and pg_trgm's regression tests pass (4 of 4).
>
> diff --git a/contrib/pg_trgm/trgm_gist.c b/contrib/pg_trgm/trgm_gist.c
> index bd9b923..bbe0e14 100644
> --- a/contrib/pg_trgm/trgm_gist.c
> +++ b/contrib/pg_trgm/trgm_gist.c
> @@ -337,7 +337,7 @@ gtrgm_consistent(PG_FUNCTION_ARGS)
> if (len == 0)
> res = false;
> else
> - res = (((((float8) count) / ((float8) len))) >= nlimit);
> + res = (((float4) count) / ((float4) len)) >= nlimit;
> }
> break;
> case ILikeStrategyNumber:
>
> An alternative would be double literals for the three defaults; the patch above keeps the inner check consistent with the leaf whatever the threshold is.
>
> Thank you,
> Eric Laquer

Is that distinct from BUG #19701 ?

-- 
Best regards,
Kirill Reshke


Re: Re: pg_trgm: GiST index scan misses rows at the default word_similarity_threshold

От:
Eric Laquer <laquereric@gmail.com>
Дата:
Hi Kirill,

Thanks for looking. I believe it is distinct from BUG #19701, though the two patches touch neighbouring lines of gtrgm_consistent.

#19701 is a zero threshold. GIN loses rows there (the default search mode only fetches rows sharing a query trigram, and nkeys == 0 rejects everything), and the report says GiST agrees with a seqscan. Manu's v3-0002 changes gtrgm_consistent only in the len == 0 branch (res = (nlimit <= 0.0)) and keeps the float8 division.

This report is GiST at the default threshold, on rows whose similarity equals the threshold exactly, with a non-empty query (len = 5 in the reproduction, so the len == 0 branch is never taken). The cause is the float8 division on internal pages against the float4 similarity on leaves, with the default stored as 0.6f. v3-0002 leaves that line as it is, so it would not change this result. GIN is not affected, since gin_trgm_consistent already divides in float4.

If v3-0002 goes in first, the change applies on top of it as:

--- a/contrib/pg_trgm/trgm_gist.c
+++ b/contrib/pg_trgm/trgm_gist.c
@@ gtrgm_consistent(PG_FUNCTION_ARGS)
if (len == 0)
res = (nlimit <= 0.0);
else
- res = (((((float8) count) / ((float8) len))) >= nlimit);
+ res = (((float4) count) / ((float4) len)) >= nlimit;

Thank you,
Eric Laquer

On Wed, Oct 28, 2026 06:56 AM, Kirill Reshke <reshkekirill@gmail.com> wrote:
On Wed, 28 Oct 2026 at 14:17, Eric Laquer <laquereric@gmail.com> wrote:
>
> Hello,
>
> At the default pg_trgm.word_similarity_threshold, a GiST (gist_trgm_ops) index scan for `<%` returns fewer rows than a sequential scan when a row's similarity is exactly the threshold. Seen on 17.9; the code is the same on master.
>
> The defaults are float4 literals stored in doubles (trgm_op.c: `double word_similarity_threshold = 0.6f;`, so 0.6000000238...). A leaf computes similarity in float4 (CALCSML), 3/5 = 0.6000000238, which passes. gtrgm_consistent's non-leaf branch divides in float8, 3/5 = 0.59999999999999998, which is below the threshold, so the subtree is pruned. With the threshold SET to 0.6 (a double) both sides agree, which is why it only shows at the default. The same applies to the other two thresholds.
>
> Reproduction (17.9, macOS arm64):
>
> -- pg_trgm: a GiST index scan at the default word_similarity_threshold misses rows a scan returns
> CREATE EXTENSION IF NOT EXISTS pg_trgm;
> DROP TABLE IF EXISTS t;
> CREATE TABLE t (id int, s text);
> -- words with none of the letters p, r, a, t, so they share no trigram with 'prat'
> INSERT INTO t SELECT g, string_agg(substr('bcdefghijklmnosuvwxyz', 1 + (abs(hashint4(g * 7 + i)) % 21), 1), '')
> FROM generate_series(1, 20000) g, generate_series(1, 8) i GROUP BY g;
> -- 'pram' shares exactly 3 of 'prat''s 5 trigrams: word_similarity('prat', 'pram') = 0.6, the default threshold
> INSERT INTO t SELECT 100000 + g, 'pram' FROM generate_series(1, 50000) g;
> CREATE INDEX t_trgm ON t USING gist (s gist_trgm_ops);
> SELECT word_similarity('prat', 'pram') AS sml, current_setting('pg_trgm.word_similarity_threshold') AS threshold;
> SET enable_indexscan = off; SET enable_bitmapscan = off;
> SELECT 'seqscan' AS plan, count(*) FROM t WHERE 'prat' <% s;
> RESET enable_indexscan; RESET enable_bitmapscan; SET enable_seqscan = off;
> SELECT 'gist' AS plan, count(*) FROM t WHERE 'prat' <% s;
> SET pg_trgm.word_similarity_threshold = 0.6; -- the same threshold, as a double
> SELECT 'gist, threshold set' AS plan, count(*) FROM t WHERE 'prat' <% s;
>
> Result:
> sml | threshold
> 0.6 | 0.6
>
> seqscan 50000
> gist 375
> gist, threshold set 50000
>
> With the patch below (divide in float4 on non-leaf pages, as the leaf does) the GiST scan returns 50000, and pg_trgm's regression tests pass (4 of 4).
>
> diff --git a/contrib/pg_trgm/trgm_gist.c b/contrib/pg_trgm/trgm_gist.c
> index bd9b923..bbe0e14 100644
> --- a/contrib/pg_trgm/trgm_gist.c
> +++ b/contrib/pg_trgm/trgm_gist.c
> @@ -337,7 +337,7 @@ gtrgm_consistent(PG_FUNCTION_ARGS)
> if (len == 0)
> res = false;
> else
> - res = (((((float8) count) / ((float8) len))) >= nlimit);
> + res = (((float4) count) / ((float4) len)) >= nlimit;
> }
> break;
> case ILikeStrategyNumber:
>
> An alternative would be double literals for the three defaults; the patch above keeps the inner check consistent with the leaf whatever the threshold is.
>
> Thank you,
> Eric Laquer

Is that distinct from BUG #19701 ?

--
Best regards,
Kirill Reshke
FAQ