Synonym matching fires on unrelated queries when two synonym terms share a prefix longer than MAX_PREFIX_LEN (8 bytes) #3029

Description

When a synonym set contains two terms where one is a prefix of the other and the shared prefix is longer than MAX_PREFIX_LEN (8 bytes), synonym matching starts firing for unrelated queries. Any query token that differs from the synonym term only after the 8th byte is treated as an exact match, so the synonym expands and floods the result set.

This is not typo tolerance: it reproduces with num_typos=0, synonym_num_typos=0 and synonym_prefix=false. None of those parameters have any effect on it.

The impact is much larger for languages whose characters take multiple bytes in UTF-8. A Thai character is 3 bytes, so a 3-character Thai word already exceeds the 8-byte limit and virtually every Thai synonym is affected. We hit this in production: the synonym set ["กระดาษ", "กระดาษถ่ายเอกสาร", "กระดาษA4"] (paper / copier paper / paper A4) made the unrelated queries กระดาน (whiteboard), กระบอก (cylinder), กระดูก (bone), กระติก (flask) and กรรไกร (scissors) all return the ~640 paper products instead of their own results — a query for "whiteboard" returned nothing but paper.

The repro below uses ASCII only, so no multi-byte handling is needed to see it.

Steps to reproduce

Typesense v30.2 (also present in v30 and v31 source).

export TS="http://localhost:8108"
export KEY="xyz"

# 1. collection with a plain string field (default locale)
curl -s "$TS/collections" -X POST \
  -H "X-TYPESENSE-API-KEY: $KEY" -H 'Content-Type: application/json' -d '{
    "name": "prefix_bug",
    "fields": [{"name": "name", "type": "string"}]
  }'

# 2. documents
curl -s "$TS/collections/prefix_bug/documents/import?action=create" -X POST \
  -H "X-TYPESENSE-API-KEY: $KEY" --data-binary '{"name":"bookkeeping"}
{"name":"bookkeepinh"}
{"name":"bookkeepingx"}
{"name":"book"}
{"name":"bool"}'

# 3. synonym set: the two terms share an 11-byte prefix ("bookkeeping")
curl -s "$TS/synonym_sets/pfx" -X PUT \
  -H "X-TYPESENSE-API-KEY: $KEY" -H 'Content-Type: application/json' -d '{
    "items": [{"id": "d", "root": "", "synonyms": ["bookkeeping", "bookkeepingx"]}]
  }'

curl -s "$TS/collections/prefix_bug" -X PATCH \
  -H "X-TYPESENSE-API-KEY: $KEY" -H 'Content-Type: application/json' \
  -d '{"synonym_sets": ["pfx"]}'

# 4. search for a word that differs from "bookkeeping" at byte 11 only
curl -s "$TS/collections/prefix_bug/documents/search?q=bookkeepinh&query_by=name&num_typos=0&prefix=false&synonym_num_typos=0&synonym_prefix=false"

Expected: 1 hit — bookkeepinh.

Actual: 3 hits — bookkeepinh, bookkeeping, bookkeepingx. The synonym fired even though bookkeepinh is not in the synonym set and all typo settings are 0/false.

Control cases that behave correctly:

The 8-byte boundary is exactly where the behaviour flips: differences at byte ≤ 8 are detected, differences at byte ≥ 9 are invisible.

Note: the field's locale and the synonym's locale must match for synonyms to apply at all (synonym_reduction skips definitions whose locale differs), but the bug itself is locale-independent — it reproduces with both unset, and with both set to th.

Root cause

synonym_node_t::get_matching_children() in src/synonym_index.cpp falls back to a fuzzy lookup when the query token is not an exact child:

auto it = children.find(token);
if(it != children.end()) {
    return {it->second};
}

// do fuzzy search if the token is not found
art_fuzzy_search((art_tree*) children_tree, (unsigned char*)token.c_str(), term_len, 0, num_typos, ...);

The ART node stores at most MAX_PREFIX_LEN bytes of its compressed prefix (include/art.h:23, currently 8). In art_fuzzy_recurse (src/art.cpp, around line 1718) the part of the prefix that was truncated is walked like this:

// Some intermediate path may have been left out if partial_len is truncated: progress the levenshtein matrix
while(partial_len < n->partial_len && depth < term_len) {
    c = term[depth];        // <-- byte taken from the *search term*, not from the key
    levenshtein_dist(depth, p, c, term, term_len, rows[i], rows[j], rows[k]);
    ...
}

Because c is read from term and then compared against term, every byte past the truncation point scores a match by construction. The Levenshtein distance for that stretch is always 0, so any key that shares the first 8 bytes is reported as a distance-0 hit regardless of what follows.

An inner node with a long compressed prefix only exists when at least two keys share that prefix, which is why a single synonym term never triggers it and why the second, longer term is required.

Suggested fixes

1. In src/art.cpp — do not assume the truncated portion matches. The node's full key is reachable via its minimum leaf; comparing against that instead of term[depth] would score the skipped bytes correctly. This is the real fix but touches the fuzzy path used by all searches, so it needs careful benchmarking.

2. In src/synonym_index.cpp (smaller blast radius) — verify the candidates returned by art_fuzzy_search before accepting them, e.g. compute the actual edit distance between token and leaf->key and drop anything beyond num_typos. This keeps ART untouched and fixes the synonym symptom.

We are happy to test a patch against our dataset if that helps.

Environment

• Typesense 30.2 (self-hosted)
• Reproduced on a fresh collection with default settings
• Related: Synonyms with locale: "th" never match when the synonym term contains SARA AM (U+0E33) at a token boundary #3025 (another Thai synonym issue we reported), though the root cause is different