Compile or Prefilter?

Jul 10, 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, Matching LIKE in the FSST Domain, 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 independent groups arrived at diverging ideas: Vortex runs a prefilter over the code stream, verifying the few surviving positions with an automaton, while TU Munich, 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 pays a fixed cost per pattern regardless of selectivity, and recoups that cost by making the per-byte automaton step as cheap as the compiler can manage, which is the right bet precisely when the automaton has to run over everything anyway, and 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 115 search predicates, spanning 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 TU Munich's compiled automaton across seven x86 generations, from AMD Rome through Turin to Intel Ice Lake through Emerald Rapids. The 95 substring-shaped (%…%) predicates from that sweep are plotted below.

Results summary

The results substantiate our expectations, though they also contain surprising elements. Thus, before we discuss any specific numbers, we provide an illustrative sketch below to more clearly showcase these observations.

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: one in which each technique wins. While the regimes are split by selectivity, performance on each side is significantly less affected by selectivity than one might expect.
The performance of each selectivity regime is largely determined by the underlying machine.
The point at which one regime 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 vs compile)	`%http%` (compile vs prefilter)
AMD Rome	2.40x faster	9.30x faster
AMD Milan	2.57x faster	8.71x faster
AMD Genoa	2.96x faster	9.01x faster
AMD Turin	4.57x faster	6.71x faster
Intel Ice Lake	1.74x faster	7.36x faster
Intel Sapphire	1.71x faster	6.67x faster
Intel Emerald	1.20x faster	6.54x faster

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. Each AMD generation widens the prefilter's win. This even includes a reduction in the JIT-compiled approach's relative speedup for search predicates with selectivity well above 10%.

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 and selectivity. 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 more performant 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 amounts to running that architecture over FSST codes rather than raw bytes, which is a good engineering result, though not a new matching technique. That recognition is the larger reason this work became a blog post rather than the foundation of a submitted paper.

TU Munich'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 blog, 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 the combination of both techniques a natural successor to both implementations. Teddy would run first, discarding candidate positions at SIMD speed. Then TUM's compiled automaton would replace our interpreted verifier at the surviving positions, where its per-step advantage applies to exactly the work no prefilter can remove. The corridor between 10 and 21 percent selectivity, where neither design wins outright, is precisely the region a combined matcher targets: dense-fingerprint substrings would preserve the compiled path's throughput, selective strings would preserve the prefilter's skipping, and the planner already computes the fingerprint-density estimate that separates them. Neither codebase contains this system today, though between them they contain every part of it.

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.