BUG #19701: GIN trigram index loses rows at similarity_threshold 0

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

BUG #19701: GIN trigram index loses rows at similarity_threshold 0

От:
PG Bug reporting form <noreply@postgresql.org>
Дата:
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.




Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0

От:
Manu <manuelreyesbravo@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

Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0

От:
Palak Chaturvedi <chaturvedipalak1911@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  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


Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0

От:
Manu <manuelreyesbravo@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

Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0

От:
Palak Chaturvedi <chaturvedipalak1911@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  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


Re: BUG #19701: GIN trigram index loses rows at similarity_threshold 0

От:
Manu <manuelreyesbravo@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
FAQ