Regular expressions are common filters in analytical databases, log processors, security scanners, and data-cleaning systems. Simple substring search can often be accelerated with specialized string instructions or first-byte masks, but general regex predicates normally become deterministic finite automata (DFAs). A scalar DFA has a loop-carried dependency: the next transition depends on the current state, which depends on the previous byte. That makes a single string hard to vectorize directly.
SIMD-accelerated regex scanning takes a different route. Instead of trying to process multiple bytes from one string independently, it processes many strings in parallel. Each SIMD lane carries one tuple’s current pointer and DFA state. Gather loads read the next byte for each active string, vector arithmetic computes transition-table offsets, and lanes that reach accept or reject sinks are replaced with fresh strings from the input column.
The key engineering insight is that database regex filters are boolean predicates, not lexers that must consume every byte. Many strings are rejected or accepted early. A lockstep SIMD implementation wastes lanes by marching every string to the same offset, while a lane-refill design keeps the vector full and lets early exits become a performance advantage.
A regular expression can be compiled into a DFA where each state has one transition for every possible input byte. The implementation stores this as a flat states * 256 table. A transition lookup is just dfa[(state << 8) | byte], which is branch-light and predictable if the table stays cache resident.
Regex predicates often have accept or reject sink states. For example, an invalid character in an e-mail address can reject immediately, and a required substring found in a multi-pattern filter can accept without scanning the tail. Encoding those sinks as negative sentinel values lets the vector loop detect completed lanes without a separate accepting-state lookup.
When a SIMD lane finishes a string, the scanner writes the accepted row id if needed and immediately loads the pointer, length, and initial state for the next string. This turns variable-length, early-exit control flow into a steady stream of lane work.
The dependency chain inside one DFA traversal remains scalar. SIMD becomes useful by running many independent traversals at once, so each lane advances a different string and the vector instruction operates on several independent state machines.
The scalar scanner walks one byte at a time until the string ends or a sink state is reached. This is simple and cache friendly, but branch decisions and dependent table lookups keep it from saturating memory bandwidth.
bool regex_match(const uint8_t *s, size_t n,
const int32_t *dfa, int32_t initial,
int32_t reject_states) {
size_t i = 0;
int32_t state = initial;
while (state >= 0 && i != n) {
uint8_t byte = s[i++];
state = dfa[(state << 8) | byte];
}
return (uint32_t)(state + 1) > (uint32_t)reject_states;
}The vector version keeps arrays of lane-local pointers, offsets, lengths, states, and row ids. One iteration gathers the next byte for every active lane, computes transition offsets, gathers next states, increments offsets for unfinished lanes, and marks lanes that need refill.
// Pseudocode for one vector step.
bytes = gather_byte(ptrs + offsets)
table_pos = (states << 8) | bytes
next_state = gather_i32(dfa + table_pos)
done = (next_state < 0) | (offsets + 1 == lengths)
states = select(done, initial_state, next_state)
offsets = select(done, 0, offsets + 1)
emit_matches(done, next_state, row_ids)
refill_done_lanes(done, ptrs, lengths, row_ids)Because each lane can be at a different offset, input loads are not contiguous. The paper’s design amortizes this cost by buffering multiple bytes per string access and using gather-friendly layouts for pointer and length metadata. The result is most valuable when strings fail early or have heterogeneous lengths.
Columnar and in-memory query engines frequently apply regex filters during scans. A vectorized DFA operator can validate URLs, e-mail addresses, identifiers, or structured codes while returning only row ids that pass the predicate.
High-volume log systems often test many records against the same pattern. Compiling the pattern once and scanning many records in parallel is a natural fit for SIMD across inputs.
Rules for secret formats, network indicators, and record validation often include negative cases that fail early. Lane refill lets those early failures increase throughput instead of producing idle vector lanes.
The pattern works best when the same regex is applied to many strings. Compile and minimize the DFA outside the scan loop, store transitions in a dense byte or 32-bit table, and keep the operator focused on row-id production.
struct RegexDFA {
int32_t initial;
int32_t reject_states;
std::vector<int32_t> transition; // states * 256
};
std::vector<uint32_t> scan_column(const RegexDFA& dfa,
Span<StringRef> column) {
LaneState lanes[VECTOR_WIDTH];
refill_all(lanes, column);
while (any_lane_active(lanes)) {
step_vector_dfa(dfa, lanes);
}
return accepted_row_ids();
}The DFA defines correctness; the vector scheduler only decides which strings occupy lanes. Test the scalar DFA and vector DFA against the same pattern corpus so performance work does not change regex semantics.