RedditPP Mascot

RedditPP

r/vectordatabase • … • u/Cautious_Bit_8521

I'm not convinced regex indexing helps unless selectivity is high

I've been looking at native regex filtering as a two-stage retrieval problem. My current view is that vector similarity finds the general neighborhood, then a structural constraint narrows the result by error-code format, version pattern, term order, or route shape. The interesting part is probably not adding a regex operator. It is deciding when an index can reduce work without changing the result.

This pattern is described for vector databases such as Milvus: RE2 keeps matching cost predictable, regex remains a heavy predicate, and cheaper scalar conditions run first. An NGRAM index does not decide the match. It extracts required literals, builds a candidate set, then verifies the original strings with exact regex evaluation. If the planner cannot prove that candidate reduction is safe, it falls back to the raw path.

The benchmark makes the selectivity tradeoff unusually clear. It used 10 million sealed log rows and warm-cache measurements. For a literal-rich pattern, candidate reduction of 99.99% produced a 3.26x p50 speedup. At 50% candidate reduction, the gain fell to 1.17x. An anchored pattern became slower at high candidate rates, while weak-literal, alternation, and case-insensitive patterns stayed close to raw-scan cost.

So "regex index enabled" is probably not a useful performance claim by itself. I would want candidate ratio, raw versus indexed latency, CPU per query, selectivity distribution, cold behavior, and the percentage of patterns that fall back. I would also separate regex cost from ANN and compound-filter cost.

I'm curious how others decide whether an NGRAM-style index is worth its storage and build cost. Would love to hear your thoughts.

— 0