Pattern Matching on Compressed Strings without Decompression

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

This is part one of a two-part series. It introduces how Vortex evaluates LIKE predicates directly over FSST-compressed strings. We investigate the performance considerations of our design in part two: Compile or Prefilter?

Analytical datasets often include strings. These strings can be very large (hundreds to thousands of characters), so modern analytics engines typically compress them to reduce I/O costs. FSST is a lightweight string codec designed for this use, reducing text size by roughly 2–3x. Unlike heavyweight codecs such as Zstd, FSST lets you decode a single value without decompressing unneeded values. For this reason, Vortex, our open-source columnar format, uses FSST for its string columns.

Compression is only half the story: we compress data so we can read it back later as part of a query. In many existing data management engines, reading the data back requires decompressing it first. In contrast, as discussed in an earlier post, Vortex lets us perform compute over data while it stays compressed, rather than decompressing it first and working on the result. This earlier work focused on simple predicates, such as equality matching. This post tackles a harder one: evaluating SQL LIKE over compressed strings without decompressing them into a temporary, intermediate form.

Everything below builds on how FSST encodes strings. If the codec is new to you, consider reading our introduction to FSST first, which walks through the theory and our open-source Rust implementation.

In this post, we explore the two components that make this technique work: an automaton that reads FSST symbol codes rather than raw bytes, and a SIMD prefilter that keeps the automaton fast. Part two goes deeper, compares our approach with the current state of the art, and covers what we learned along the way.

The decompress-first baseline

Most query engines treat compressed strings as opaque. To query compressed data, an engine loads the column, decompresses values, and then passes the full strings to a matcher. This workflow is the only option for "heavyweight" codecs such as Zstd, which do not support extracting individual values from compressed data. A random-access encoding like FSST enables a better way to interact with the data: because of the structure of the compressed form, every value is independently readable, enabling search. Our goal was to use this functionality to push the LIKE predicate down onto the compressed data itself, to skip the decompress-first path.

A finite automaton that reads FSST symbols

FSST builds a table of up to 255 symbols, each a frequent byte sequence one to eight bytes long, and replaces each occurrence with a single-byte code; in the example above, www. maps to 12. The table also reserves code 255 as an escape, so the pair (255, c) encodes a literal byte c. A compressed string is a sequence of codes, and decompression is the process of performing dictionary lookups and concatenating the symbols represented by those codes.

To search for a particular string in the data (e.g., google) without decompression, we need to search the code-compressed text. Because FSST provides a dictionary, we could start our search by looking for the pattern in the symbol table. However, this only works if the predicate exactly matches the dictionary values. For example, a dictionary might split www.google.com into [www., goog, le, .com], so we cannot simply check for a single google symbol in the dictionary. In general, a byte-level substring search over codes is both incorrect (a code's numeric value can coincide with a byte of the search string by accident) and incomplete (the search string can straddle a symbol boundary). To make the search sound, we lift the whole problem into code space: we treat FSST symbol codes as the alphabet of a deterministic finite automaton (DFA).

A DFA is a machine built from a fixed set of states, each with a table that maps every possible input to the next state. Feed it a sequence of inputs, and it steps through states; if it reaches a match state, the input matches.

We build a DFA that accepts exactly the code sequences whose decompression matches the pattern, then run it directly over the compressed bytes.

Rust

// A compressed string is just a slice of FSST symbol codes.
// We match a substring pattern by stepping a DFA over those
// codes; the bytes are never expanded back into text.
fn matches(codes: &[u8], dfa: &SymbolDfa) -> bool {
    let mut state = dfa.start;
    for &code in codes {
        state = dfa.step(state, code); // one table lookup per code
        if dfa.is_accept(state) {
            return true;
        }
    }
    false
}

In our case, the inputs are the FSST codes themselves rather than the original characters, so matching a compressed string costs one table lookup per compressed byte; no decompression.

Three properties of FSST make it well-suited for DFA-based compute (existing research):

It is a greedy encoding, which means that a string is compressed by repeatedly taking the longest symbol that matches at the cursor, so a whole string, parsed from its start, has exactly one encoding.
No two symbols share the same three-byte prefix, resulting in unique prefixes. This uniqueness bounds the number of ways a pattern's first bytes can be carved into symbols.
The last byte of the i-th symbol differs from i itself (index-suffix divergence), which keeps code values from masquerading as the text they encode.

The LIKE patterns we optimize are built from literal segments separated by % wildcards. They fall into three shapes: prefixes (abc%), suffixes (%abc), and substrings (%abc%), each of which builds its own automaton. Note that the shapes are not equally easy. For example, a prefix is anchored at the start of the string, exactly where greedy encoding ensures that each row's parse is unique. In this case, the automaton only has to accept the handful of code runs that spell out the prefix, including the case where the row's final matching symbol runs past the prefix's end. In contrast, a substring floats to any offset, where the same search-string bytes can be carved into codes more than one way depending on what precedes them, so its automaton has to accept every such carving rather than just the string's own greedy encoding. Full patterns are stitched together from those pieces.

A compressed string as a row of FSST codes, the symbol table those codes index, and a DFA whose edges are codes — accepting the code sequences that decompress to a match. Simplified to one accepting path for %google%; the real automaton also covers the other ways the substring can be carved into codes.

Beyond those single-segment shapes, we also handle ordered multi-segment patterns like %a%b%. Anything outside the supported subset falls back to the ordinary decompress-then-match path, so correctness never depends on coverage.

Prefilter, then verify

While stepping the generated DFA over every code is a correct baseline, we can do much better by leveraging prefiltering. The speed of our implementation comes from almost never running the automaton outside of the positions where a match could begin.

The mechanism that allows us to skip running the DFA is a streaming Teddy prefilter, borrowed from Hyperscan (maintained today in Vectorscan).

The prefilter examines short literal substrings to determine whether a match could start at a given position in the string. Importantly, our prefilter builds a small fingerprint table and then uses data-parallel (SIMD) shuffles to test many positions at once. The result is a cheap candidate mask, computed block by block. Our prefilter is one-sided: it may flag positions that do not pan out, but it never rules out a real match, so the DFA runs afterward at the flagged positions to decide.

Thus, Teddy answers "could a match start here?" for an entire block of encoded data at once, and we run the DFA verifier inline only at the positions it flags.

Rust

// Teddy answers "could a match start here?" for a whole block at once.
// The DFA only runs at the few positions that survive.
for (base, block) in all_bytes.chunks(BLOCK).enumerate() {
    let candidates = teddy.fingerprint(block); // one mask per block
    for pos in candidates.iter_ones() {
        if dfa.matches_at(block, pos) {         // verify survivors
            out.set(base * BLOCK + pos);
        }
    }
}

On a selective pattern, the mask discards almost every position for a few instructions per block, so the automaton barely runs. Consider the google search predicate we've been using; it's actually part of ClickBench's Q20, which scans a large URL column. Using the 10-million-row version of the dataset, the 865 MB of URL text compresses to 537 MB of FSST codes (1.61x). A naive scan for google stops at every g in the dataset; about ten million stops, or roughly once every 86 bytes of text. Teddy, running over the compressed codes, flags 44,158 candidates across the entire column, resulting in a 200x reduction in stops, averaging one stop every 12 KB of compressed data. This reduction is critical to our performance, as the DFA verifier confirms only 646 candidates as true matches.

Around that prefiltering core sits the rest of the machinery. A planner selects one of several scan strategies for each pattern based on substring length, expected fingerprint density, and the available instruction set. Additional cases extend the same core: case-insensitive ILIKE folds letters in the matcher, and NOT LIKE negates the final match mask. The SIMD pass has an AVX-512 path, an AVX2 path, and a scalar fallback, so the same matcher can run on the vast majority of x86 machines.

Teddy fingerprints a whole block of codes with a SIMD nibble-shuffle, producing a sparse candidate mask; the DFA verifier runs only at the few surviving positions.

However, the prefilter is an additional preprocessing step, performed under the assumption that the pattern is uncommon. When a pattern is so common that the fingerprint flags nearly every position, the candidate mask stops filtering, and we would incur the cost of a full filtering pass in addition to the work already done by a plain scan. Our design is built for selective patterns, where almost nothing matches, and the per-position cost remains small and uniform across the scan. Due to this sensitivity, we implement a bail-out heuristic that detects the dense case; if necessary, our technique will fall back to plain decompress-and-match rather than pay for an ineffective filter.

How fast is it?

The headline number comes from ClickBench Q20:

SELECT COUNT(*) FROM hits WHERE "URL" LIKE '%google%';

This query is run over roughly a hundred million rows, using Vortex-backed DuckDB and toggling pushdown. The table shows the median time at one thread across the seven x86 generations we measured.

Machine	With pushdown (ms)	Without pushdown (ms)	Speedup
AMD Rome	1,068.6	3,721.3	3.48x
AMD Milan	947.3	3,411.4	3.60x
AMD Genoa	989.8	3,161.0	3.19x
AMD Turin	600.9	2,095.1	3.49x
Intel Ice Lake	1,679.5	4,293.4	2.56x
Intel Sapphire Rapids	1,515.7	3,635.2	2.40x
Intel Emerald Rapids	990.5	2,610.7	2.64x

We then use the Milan and Sapphire Rapids machines to explore the impact of thread-parallelism; add additional compute, and the decompress-first path begins to catch up:

Speedup at threads	1	8	16	32	64	full width
EPYC Milan (56t)	3.60x	3.05x	2.42x	1.76x	—	1.54x
Xeon Sapphire (88t)	2.40x	1.98x	1.57x	1.59x	1.44x	1.42x

Decompression has a real per-byte compute cost, which is exactly what extra cores enable; thus, the path that does more compute gains more from the additional threads. On the widest box we tested, an 88-thread Sapphire Rapids server, the win settles at 1.42x. Eventually, both paths read the same compressed column from the same saturated memory bus; the only remaining advantage is that the pushdown path never expands those codes into text in the first place.

Many more measurements are in the companion post.

The same idea, twice

While we were building this, TU Munich's database group developed a mechanism for the same goal, which was presented at DaMoN 2026. Instead of using a prefilter, they compile each pattern's automaton into machine code, making each step cheap, whereas our prefiltering approach minimizes the impact of our DFA. Having two independently developed implementations of the same idea, with opposite failure modes, gives us a rare chance to explore the LIKE pushdown design space. Using a wider set of experiments across the tested machines, we explored this space in the second part of this blog series: "Compile or Prefilter?"

Code-space LIKE pushdown ships today as part of the FSST encoding in Vortex. The Teddy prefilter and planner described here are on their way upstream from our research branch. We build in the open; if you'd benefit from not having to decompress your data before analyzing it, come find us on GitHub or reach out to us directly.