You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
bug: MemWAL LSM fuzzy FTS expands max_expansions per source instead of over the merged vocabulary #9883
The MemWAL LSM FTS planner expands a fuzzy Match independently in every source (base table, SSTable generations, frozen and active memtables). Each source spends the leaf's max_expansions budget over its own vocabulary, while a single merged index spends it once over the union of every segment's vocabulary (final_query_tokens). When the cap binds, the same row can match or not depending on which tier it lives in, so results can shift as rows flush or compact.
Example — "alpha beta", fuzziness 1, AND, max_expansions = 2:
Source
Rows
Vocabulary
Result
base
id1 alpha beta, id3 alph beta
alph, alpha, beta
alpha spends both slots, AND fails — id1 excluded
active
id2 alpha beta
alpha, beta
alpha→alpha, beta→beta — id2 matches
A merged index over the union returns no rows. Fuzzy OR on main has the same divergence; #9526 extends it to fuzzy AND and documents it.
A source's vocabulary is a subset of the union, so each source's own expansion is a superset of its share of the canonical set: sources only ever over-match (with LIMIT, an over-matched row can displace a canonical one from the top-k).
Proposed fix (contained in mem_wal)
In the LSM planner, compute each fuzzy leaf's canonical vocabulary: merge every source's own expansion per query position, then spend the budget once in position order, lexicographically. Base/SSTable expansions come from InvertedIndex::expand_fuzzy_tokens; memtable expansions from FtsMemIndex.
Pass the canonical groups directly to memtable arms.
For a base/SSTable arm whose own expansion differs from its share, rewrite the leaf into per-position single-term fuzzy Match leaves under a Boolean (must for AND, should for OR), each with max_expansions set to that position's share. The share is a lexicographic prefix of that arm's candidates, so the arm reselects exactly the canonical terms.
Open questions: score parity of the rewritten Boolean leaf versus a grouped Match, and the added planning latency (expansion becomes a barrier before dispatch; only fuzzy queries pay it).
Activity
docs(mem_wal): note per-source fuzzy expansion in LSM FTS