Skip to content

bug: MemWAL LSM fuzzy FTS expands max_expansions per source instead of over the merged vocabulary #9883

Closed

Description

@hamersaw

Problem

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)

  1. 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.
  2. Pass the canonical groups directly to memtable arms.
  3. 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).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions