Compile or Prefilter? Matching LIKE over Compressed Strings

Jul 14, 2026 · by Martin Prammer and Joe Isaacs · 10 min read

This is part two of a two-part series. This post assumes some familiarity with our technique for evaluating LIKE predicates over FSST-compressed strings, introduced in part one, Pattern Matching on Compressed Strings without Decompression, and will read best after the first.

Two research groups independently explored the same question: Can we evaluate SQL LIKE against FSST symbol codes rather than decompressed text? These two groups chose different execution strategies: Vortex runs a prefilter over the code stream, verifying the few surviving positions with an automaton, while TU Munich (TUM), in work presented at DaMoN 2026 and TUMuchData, compiles each pattern's automaton into machine code for faster execution.

Thus, we have an unusually clean opportunity to map a design space. This post explores this space through a large-scale sensitivity study that varies both search predicates and underlying hardware. While the overall results align with general trends in vectorized vs. compiled execution models, the per-predicate results are more nuanced. As we show that both techniques are highly data- and query-sensitive, we look toward a hybrid approach in the future, complementing each with the other.

The shared idea — a DFA over FSST codes — forks two ways: TU Munich compiles each pattern into machine code, while Vortex prefilters candidate positions and runs the DFA only at the survivors.

Our prefilter-based approach

Vortex starts from the same code-space DFA described in the first post. The important choice is what happens at runtime. Stepping that DFA over every code will generate a correct result, but the automaton step is not free; when evaluating a selective pattern, almost every position it inspects never begins a match. Thus, paying the full cost of the automaton everywhere to find a handful of rows is untenable.

We place a SIMD literal prefilter in front of the verifier. Teddy extracts short literal substrings from the LIKE pattern and builds a small fingerprint table for them. As each compressed block arrives, SIMD shuffles test multiple positions at once, producing a candidate mask for the DFA. Because the DFA discards false positives, Teddy is designed to over-report only, enabling the prefilter to optimize for speed.

This shifts the steady-state work from “run the automaton everywhere” to “fingerprint everything, then verify the few survivors.” The trade-off is pattern-dependent: a selective literal makes the mask sparse and the verifier cheap, whereas a dense literal turns the SIMD pass into overhead. Vortex's planner uses a fingerprint-density estimate to choose between the SIMD-based prefilter and direct DFA evaluation paths and can fall back to decompress-and-match if necessary.

TU Munich's compiled automaton

The TUM implementation builds the automaton with an Aho-Corasick-style construction: a trie over the valid symbol sequences, plus failure links so that a mismatch falls back to the longest still-viable state rather than restarting. The escape byte forces a set of pseudo-end states because a trailing 255 cannot be resolved until the escaped byte it introduces arrives. Substring patterns require two further construction phases, namely linking and splitting, to stay deterministic across the partial-match failures that only substrings produce.

Their execution model is what makes their technique unique. TUM emits the automaton's parsing code in three ways: an interpreted walker, C++ source compiled by clang++ into a shared library and loaded at runtime, and LLVM IR that is JIT-compiled directly. The compiled variants bake the transition logic for a specific pattern into machine code. This compilation step yields a fast DFA, which, in turn, is less dependent on a prefiltering step.

On top of that core, TUM applies several optimizations: caching sub-automata that recur across patterns, assigning each state a level (its distance to acceptance) so a scan can reject early when too little input remains, verifying a pattern's unique prefix or suffix up front with integer comparisons, and accelerating the state-0 self-loop (the step that skips bytes that cannot begin a match) with SSE4.2 string instructions. The theoretical payoff is concrete: checking a string of compressed length m drops from O(m) to O(1) for prefix and suffix patterns, and to a worst case of O(min(L+1, m)) for substrings, where L is the level of the automaton's start state, which is small for short patterns.

Against two decompress-first baselines, namely a hybrid SIMD string search and Vectorscan (the open fork of Hyperscan), TUM reports 2.5–17x higher throughput on an Intel i9-7900X. The LLVM variant is the fastest once the data is large enough to justify the compilation cost, which can generally be amortized across many data blocks.

Opposite failure modes

First principles indicate that the two designs fail in opposite ways. The prefilter's weakness is the dense pattern, the case our bail-out already watches for: when the fingerprint stops filtering, the SIMD pass becomes pure overhead. This regime is exactly where a prefilter-free design, such as a tightly compiled automaton, comes out ahead. However, when relying on a fast DFA, the weakness lies in the mirror image. The compiled approach runs its automaton over every code regardless of selectivity, and offsets that by driving the per-byte step as cheaply as the compiler can manage. This is the right choice when the automaton has to run over most of the data, but dead weight when a prefilter would have discarded almost every position first.

That is the theory, and it is enough to sketch the curve we should expect:

A soft sketch: several dashed candidate curves descend from prefilter-faster territory through parity into compiled-automaton-faster territory as selectivity grows, agreeing at the ends but disagreeing about where and how sharply they cross, marked with a question mark.

While first principles force the two ends, they say nothing about the shape of the middle. We benchmark both pushdown implementations to explore this unknown region.

Results

Everything below is part of a single experiment. The corpus is the ClickBench URL column: ten million real URLs, FSST-compressed. We evaluate search predicates that span selectivity from a handful of matching rows to essentially all of them. We also group the predicates by length to explore the interaction between predicate length and selectivity. We compare our prefilter with TUM's compiled automaton across seven x86 generations, from AMD Rome through Turin to Intel Ice Lake through Emerald Rapids. We plot 83 substring-shaped (%…%) predicates from that sweep below.

Results summary

The results substantiate our expectations, though they also contain surprising elements. Before we get to specific numbers, here is an illustrative sketch of what they show.

A smooth conceptual crossover: the prefilter is faster at low selectivity, the compiled automaton is faster at high selectivity, and a dark 10-21% corridor marks the region where either can win.

This sketch is intentionally shaped, highlighting the following behaviors:

There are two regimes, split by selectivity, with one technique winning in each. Performance on each side is less affected by selectivity than one might expect.
The performance of each regime is largely determined by the underlying machine.
The point at which one regime (usually) wins out over the other lies between 10% and 21% selectivity. However, within this range, the search predicate itself plays a significant role in determining which regime a particular result belongs to. Thus, rather than a smooth transition from prefiltering-dominated to compiled-automata-dominated results, we find two overlapping sets of predicate-influenced behavior.

With these overarching results in mind, we explore our results in more detail.

Detailed results

Below is a table showing the results at the two ends of the sweep: a highly selective predicate and a nearly unselective one. Each cell gives the named winner's speedup over the other technique on that machine.

Machine	`%google%` (prefilter wins by)	`%http%` (compile wins by)
AMD Rome	2.40x	9.30x
AMD Milan	2.57x	8.71x
AMD Genoa	2.96x	9.01x
AMD Turin	4.57x	6.71x
Intel Ice Lake	1.74x	7.36x
Intel Sapphire	1.71x	6.67x
Intel Emerald	1.20x	6.54x

At the selective end, the prefilter is ahead on every machine, and by a margin that is graded by vendor: on %google%, which matches 646 rows out of ten million, AMD chips run it 2.4x to 4.6x faster than the compiled automaton, while Intel chips run 1.2x to 1.7x faster. At the dense end, the compiled automaton wins everywhere, and by more: 6.5x to 9.3x on %http%, which matches all but a few hundred rows. However, these numbers do not tell the full story.

AMD

machine:

substring length:

All four AMD chips give the prefilter the selective end, and the margins are ordered by launch year: on %google%, Rome (2019) runs it 2.4x faster than the compiled automaton; Milan (2021) 2.6x; Genoa (2022) 3.0x; and Turin (2024) 4.6x. We observe that the prefilter's win grows monotonically across these four AMD launches. At the same time, the JIT-compiled approach's relative speedup for less selective search predicates shrinks as well.

Intel

machine:

substring length:

While the overall shape of the Intel-based results is the same as AMD's, its year trend runs the other way: Ice Lake (2021) gives the prefilter 1.7x on %google%, while Emerald Rapids (2023), the newest Intel chip in the fleet, thins that win to 1.2x. For less-selective queries, there does not seem to be a pattern similar to what was observed in the AMD results.

For ease of comparison, we present a single, combined results view below.

Both

machine:

substring length:

While the winner (almost) never changes across different hardware, the gap itself shifts dramatically; compare Emerald Rapids, where the prefilter's selective-end win thins to 1.2x, to Turin, where it stretches past 4.5x.

Further, these results underscore the importance of the exact search predicate. First, we note the case of %=%, a predicate with about 67.7% selectivity that falls into neither regime. Its winner depends on the machine: the prefilter wins on Turin, while the compiled automaton wins everywhere else. Likewise, %yandex%, six bytes in 13.4% of rows, shows that the prefilter is faster on every chip, contributing a unique point to the region ill-defined by selectivity. Finally, %php%, three bytes at 13.6%, shows the compiled automaton as the more effective approach on every chip. Note that php is built from some of the most common byte patterns in a URL column, leading to the fingerprint flagging candidates everywhere, filtering almost nothing; a failure mode that the Vortex "bail-out" exists to handle.

Deeper insights and future work

Setting the two implementations side by side taught us as much about our own design as it did about the comparison.

Mostly Hyperscan

The most useful thing this exploration turned up is where our own branch sits in the design space. Strip away the FSST framing, and the execution side of our approach is Hyperscan. We did not set out to clone it; the candidate-then-verify shape is simply where our design landed, and once the resemblance was obvious, we brought in Hyperscan's actual prefilter rather than reinvent it. The Teddy pass is Hyperscan's Teddy, the multi-pattern path is its Fat Teddy, and the surrounding pipeline is the literal-prefilter-plus-automaton architecture that Hyperscan popularized. Our execution-side contribution is running that architecture over FSST codes rather than raw bytes: a solid engineering result, and an integration rather than a new matching technique.

TUM's branch sits in a quite different place. Their implementation contains no literal prefilter at all, neither Teddy nor FDR, Hyperscan's two literal-matching engines, so the single most Hyperscan-shaped component is absent. They run the automaton over the entire compressed stream and rely on code generation to make it fast, which Hyperscan does not do, since Hyperscan compiles a pattern into a bytecode database that its fixed engines interpret rather than into machine code. Their one point of contact with Hyperscan's toolbox is the self-loop accelerator, which is shufti-flavored (find the next interesting byte) rather than the full prefilter-and-verify pipeline. Thus, their execution story is genuinely not "just Hyperscan," while ours, on the execution side, mostly is. For those interested, we highly recommend their DaMoN 2026 paper; it's worth the read.

Final thoughts

In this series, we explored two independent implementations of the same idea. When set side by side, they clearly demonstrate the split behavior underpinning the overall design space: the prefilter wins when the fingerprint discards most positions, while the compiled automaton wins when there is less to discard. The same map shows that the designs are complementary rather than competing. Our implementation uses Hyperscan's prefilter, whereas TUM's approach relies solely on a compiled engine.

One could consider a combination of both techniques a natural successor to both implementations. The planner already computes the fingerprint-density estimate that separates the two regimes, and that estimate can route each pattern to the right engine: when density is low, run Teddy and verify the few survivors; when it is high, bypass the prefilter and run a compiled automaton directly, exactly where Teddy would have earned nothing. Placing a compiled automaton as the verifier behind Teddy could also help the middle of the corridor, between 10 and 21 percent selectivity, though our measurements do not yet show whether that extra complexity pays off. Neither codebase contains this system today, but between them they hold the pieces.

We leave the exploration of this idea as future work.

The matcher described here is open source, and the Teddy prefilter and planner are on their way upstream to Vortex. Vortex has repeatedly benefited from implementing ideas from research groups around the world; we look forward to seeing where the future work of our research team and TUM's database group will go.