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

Started by PG Bug reporting form1 day ago1 messagesbugs

noreply@postgresql.org

1 day ago

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;

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.