unlock unlimited code runs for $79, limited time →
NOSSLETTER.techLIVE
back to archive

feat: accelerate regex filtering with FMIndex candidates

Language: Go+2826 -138feature
concepts demonstrated
Regular expressionsIndex-based filteringBitmaps for candidate selectionAdapter pattern
The Issue & Context

Before this change, regex filtering scanned entire row bytes even when the pattern contained selective literals, leading to inefficient full scans and missing opportunities to leverage index-based candidate filtering, especially for complex patterns with multiple literals connected by AND/OR.

Root Cause Analysis

The prior approach extracted only the longest literal substring from regex patterns, losing other selective literals needed for effective index candidate generation. This caused the system to skip FMIndex candidate filtering for many regexes, resulting in costly full scans. The regex filtering path did not integrate with the FMIndex candidate-and-recheck mechanism, and lacked logic to handle combined AND/OR literal conditions and their selectivity.

Solution Strategy & Architectural Pattern

This PR routes regex matching on sealed VARCHAR columns through the existing FMIndex candidate-and-recheck path by extracting all bounded literals and preserving their AND/OR relationships. It counts distinct literals per segment, selects the cheapest literal candidate per AND group, and preserves all OR branches to form combined candidate bitmaps. The canonical RE2 regex matcher is compiled once and used as a final recheck filter. A new FilteredRE2 adapter manages pinned RE2 prefilters with conservative structural checks to safely map literals. The implementation includes a thread-local cache for immutable preparation, preserves input bitmaps and NULL validity, and gracefully falls back to scanning when no usable literal candidates exist or budget limits are exceeded.

Key Takeaway for Contributors

When optimizing regex filtering with index structures, it’s crucial to extract and preserve multiple selective literals and their boolean relationships rather than relying on a single longest literal, enabling more precise candidate pruning and better integration with existing index-based filtering mechanisms.