feat(ngram): add stop-trigram filtering for high-frequency tokens

Summary

N-gram (trigram) indexes in Lance currently index every alphanumeric trigram produced by the tokenizer. Many trigrams—such as those derived from common English stop words (the, and) or frequent suffix fragments (ing, ion)—appear in a large fraction of documents. Their posting lists are huge but provide little selectivity during query-time intersection, increasing index size, build cost, and read I/O without materially improving pruning.

This issue proposes adding stop-trigram filtering to skip indexing (and querying) ultra-high-frequency trigrams.

Motivation

Current N-gram index behavior (rust/lance-index/src/scalar/ngram.rs):

• Fixed trigrams (N=3) after lowercasing, ASCII folding, and alphanumeric-only filtering
• Tokens encoded as u32; posting lists stored as RoaringTreemap
• Query path: slice query into trigrams → load posting lists → intersect → recheck (AtMost)

High-frequency trigrams hurt performance because:

1. Index bloat — posting lists for common trigrams dominate storage
2. Low pruning value — intersecting a near-universal posting list barely narrows candidates
3. Extra I/O — query path loads large posting lists that contribute little to intersection

Similar systems (e.g. PostgreSQL pg_trgm, search engines with n-gram analyzers) commonly omit or down-weight extremely common grams.

Proposed behavior

Build time

When tokenizing documents during index construction, do not insert trigrams that are classified as stop-trigrams into tokens_map / spill files.

Query time

When slicing a query string into trigrams:

• Skip stop-trigrams when collecting posting lists for intersection
• Do not treat a missing stop-trigram as "no results" (today, any missing token sets missing = true and returns an empty exact result)
• If all query trigrams are stop-trigrams (e.g. contains(text, 'the')), fall back to full recheck (AtLeast), same as queries shorter than N=3 today

Correctness

The N-gram index is inexact (AtMost) and always requires recheck. Skipping stop-trigrams at query time remains correct:

Query	Behavior
contains('ramen')	No stop-trigrams → normal intersection + recheck
contains('the')	Only stop-trigram → full recheck
contains('theory')	Skip the; intersect remaining trigrams + recheck

Design options (for discussion)

Approach	Description	Trade-offs
A. Static stop-trigram set	Built-in list of ~30–50 common trigrams (the, and, ing, ion, …), encoded once via existing ngram_to_token	Simple, predictable; does not adapt to corpus
B. Document-frequency threshold	Drop trigrams with DF > X% during build	Adaptive; requires extra statistics pass and tuning
C. Hybrid (recommended)	Static set on by default; optional max_document_frequency later	Best of both; slightly more API surface

Suggested first step: implement A (static set), with room to extend to C.

Candidate static stop-trigrams (initial draft)

• Whole 3-letter stop words: the, and, for, are, but, not, you, all, can, her, was, one, our, out, …
• Low-selectivity suffix fragments: ing, ion, ati, tio, ent, ere, ter, ate, men, est, …

Exact list should be validated against AlphaNumOnlyFilter + ngram_to_token encoding.

Implementation touchpoints

• rust/lance-index/src/scalar/ngram.rs
  • NGramIndexBuilder::process_batch / tokenize_and_partition — skip stop tokens at build
  • NGramIndex::search — skip stop tokens at query; fix missing logic for stop vs. selective trigrams
• Optional: new module ngram_stop_trigrams.rs with LazyLock<HashSet<u32>>
• Future: NGramIndexDetails proto / builder options for custom stop lists or DF threshold
• Tests: build size reduction, query correctness for stop-only / mixed / normal queries, regex/LIKE paths that derive trigram conditions

Non-goals (for initial PR)

• Changing N=3 or tokenizer pipeline
• Reusing FTS StopWordFilter directly (stemming/stop-word tokenization is incompatible with n-gram substring semantics; see comments on NGramIndex::tokenizer)

References

• N-gram index format: docs/src/format/index/scalar/ngram.md

Start with rust/lance-index/src/scalar/ngram.rs, especially NGramIndexBuilder::process_batch, tokenize_and_partition, and NGramIndex::search, then read docs/src/format/index/scalar/ngram.md. Define and validate the static stop-trigram set against the existing tokenizer and encoding, covering build and query behavior. Done means stop-trigrams are skipped without false empty results, stop-only queries recheck fully, and tests cover normal, mixed, stop-only, and regex/LIKE paths.