Accelerating Regex Filtering in Milvus with FMIndex Candidate Pruning

Regex filtering is a powerful tool for querying complex string patterns, but it can become a performance bottleneck when it requires scanning entire datasets. In Milvus, an open-source vector database, regex filtering on VARCHAR columns used to scan full row bytes even when the regex pattern contained selective literals that could help narrow down candidates. This article dives into a recent enhancement that leverages FMIndex candidate filtering to accelerate regex queries by extracting and utilizing multiple selective literals and their boolean relationships.

The Problem: Inefficient Regex Filtering

Before this change, Milvus’s regex filtering mechanism was suboptimal. It extracted only the longest literal substring from a regex pattern to generate candidate rows for filtering. While this might seem reasonable, it missed opportunities to use other selective literals embedded in the regex, especially when multiple literals were combined with AND/OR operators.

For example, consider a regex pattern like (foo|bar).*baz. The previous approach would extract just the longest literal (e.g., "baz") and ignore "foo" and "bar". This led to scanning all rows containing "baz," even though the presence of "foo" or "bar" could have further pruned candidates. Additionally, the regex filtering path did not integrate with the FMIndex candidate-and-recheck mechanism designed to efficiently filter rows based on indexed substrings.

The consequence was that many regex queries triggered costly full scans over the data, reducing query performance and throughput.

Understanding the Root Cause

The core issue was the simplistic extraction of only the longest literal substring from regex patterns. This approach failed to capture multiple selective literals and their boolean logic (AND/OR combinations) that could be leveraged for more effective candidate pruning.

Moreover, the regex filtering path was disconnected from the FMIndex candidate filtering mechanism, which is capable of generating bitmap candidates based on indexed substrings. Without integrating these two, the system missed the chance to use FMIndex to prefilter rows before applying the expensive regex matching.

The Solution: Integrating Regex Filtering with FMIndex Candidate Filtering

This PR introduces a sophisticated method to route regex filtering on sealed VARCHAR columns through the existing FMIndex candidate-and-recheck path. The key enhancements include:

• Extraction of All Bounded Literals: Instead of just the longest literal, the implementation extracts all bounded literals from the regex pattern while preserving their AND/OR relationships. This means that if the regex contains multiple literals combined with boolean operators, all are considered for candidate generation.

• Counting Distinct Literals per Segment: The system counts distinct literals in each data segment to assess their selectivity and cost.

• Selecting Cheapest Literal Candidates per AND Group: For each AND group in the boolean expression, it chooses the literal candidate with the lowest cost (i.e., the one expected to prune the most rows efficiently).

• Preserving OR Branches: All OR branches are preserved to form combined candidate bitmaps, ensuring that rows matching any of the alternatives are considered.

• Canonical RE2 Regex Matcher for Final Recheck: The RE2 regex matcher is compiled once and stored for reuse as a final recheck filter on candidate rows, ensuring correctness without redundant compilation overhead.

• FilteredRE2 Adapter: A new adapter manages pinned RE2 prefilters with conservative structural checks to safely map literals extracted from regex patterns to FMIndex candidates.

• Thread-Local Cache: To optimize performance, immutable preparations such as compiled regex and literal extraction are cached thread-locally.

• Preserving Input Bitmaps and NULL Validity: The filtering preserves the original input bitmaps and NULL values, maintaining correctness in the presence of nullable data.

• Graceful Fallback: When no usable literal candidates are found or the candidate generation budget is exceeded, the system falls back to scanning, ensuring robustness.

How This Works in Practice

When a regex filter is applied on a sealed VARCHAR column, the system:

1. Parses the regex to identify all bounded literals and their boolean relationships.
2. Uses the FMIndex to generate candidate bitmaps for these literals.
3. Combines these bitmaps according to the AND/OR structure to form a precise candidate set.
4. Applies the compiled RE2 matcher only to these candidates, avoiding full scans.

This approach effectively prunes the search space, reducing the number of rows that require expensive regex matching.

Takeaway: The Power of Preserving Boolean Literal Relationships

This enhancement highlights an important lesson in optimizing regex filtering with index structures: extracting and preserving multiple selective literals and their boolean relationships is crucial. Relying on a single longest literal can miss significant pruning opportunities.

By integrating regex filtering with FMIndex candidate filtering and carefully managing the boolean logic of literals, Milvus achieves more precise candidate pruning and better query performance. This pattern can be applied to other systems where regex filtering and indexed substring search coexist.

---

This article is based on the pull request "feat: accelerate regex filtering with FMIndex candidates" merged into the Milvus repository. Read the full breakdown on nossletter.tech.

---

Originally published on Nossletter.