Matching LIKE in the FSST Domain

Vortex, our open-source columnar format, stores string columns using FSST, a lightweight encoding that compresses 2–3x while still letting you decode any single value without decompressing its neighbors (let alone an entire chunk or segment of data). We wrote about FSST when we open-sourced our Rust implementation.

Of course, compression is only half the story; we store data so we can query it later. A big part of Vortex is being able to filter data without creating a decompressed intermediate. While we've already talked about how certain encodings expose opportunities for filtering without decompression, the applied predicates have generally been on the simple side, such as equality matching. This blog post explores performing a more complex set of predicates over strings (LIKE), without decompressing them into an intermediate, temporary form first.

This post walks through the mechanisms we built to achieve this functionality: an automaton that reads symbol codes instead of bytes, and a SIMD prefilter that makes it fast. Part two dives much deeper into our technique, compares it against the current state of the art, and discusses the lessons we learned by exploring this design space.

Most query engines treat compressed strings as opaque: load the column, decompress it, and hand the raw bytes to a matcher. This workflow is the only option for "heavyweight" codecs such as Zstd, where fully decompressing the data is the only way to recover the text. 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 and skip the decompress-first path entirely.

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. Byte 255 is reserved 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 over the code-compressed text. Because FSST provides a dictionary, an obvious solution to facilitate this search is to see if the search predicate shows up exactly in the dictionary, as is. However, what if, instead of an exact code, the compressed string was stored using escape codes (g, o, o, g, l, e)? Further, what if it were stored using a mix of escape codes and dictionary entries? It could even overlap another code (go, o, gle.com). In general, a byte-level substring search over codes is both wrong (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) that accepts exactly the code sequences whose decompression matches the pattern, then run it directly over the compressed bytes:

// 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
}

A DFA is a small machine for exactly this kind of question. DFAs are built from a fixed set of states, each of which is associated with a table that specifies the next state for every possible input. Feed a DFA a series of inputs, and it steps from state to state; if it ever reaches an accepting state, the answer is yes. Here, the inputs are FSST codes (rather than characters), so matching a compressed string costs one table lookup per compressed byte, with no backtracking and no decompression.

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

A LIKE pattern typically consists of one or more % wildcards. The patterns can be classified into three types: 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 makes each row's parse unique: 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.

We support the literal pattern shapes that cover the bulk of real LIKE usage: prefixes, suffixes, substrings, and ordered multi-segment patterns like %a%b%. For a supported pattern, the code-space result is designed to be exact: identical, bit for bit, to running LIKE on the decompressed text, and we validate every measurement we publish against exactly that decompress-then-match oracle. Anything outside the supported subset falls back to the ordinary decompress-then-match path, so correctness never depends on coverage.

Stepping the generated DFA over every code is a correct baseline; we can do much better. Our speed comes from almost never running the automaton.

The mechanism that allows us to skip running the DFA is a streaming Teddy prefilter, borrowed from Hyperscan (maintained today in Vectorscan). Teddy takes the short literal substrings of the LIKE pattern, builds a small per-nibble fingerprint table, and uses SIMD shuffles to test many input positions at once for whether a match could start there. The answer is a cheap candidate mask, and we run the DFA verifier inline only at the positions it flags:

// 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 cost-model planner selects one of several scan strategies for each pattern based on substring length, expected fingerprint density, and the available instruction set. Additional cases are covered by extending each layer where it is strongest: Hyperscan's wide Fat Teddy variant broadens the prefilter to the larger literal sets that case-insensitive ILIKE and multi-pattern OR produce, while the DFA verifier handles the single-character _ wildcard, and NOT LIKE simply 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.

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 pay for a full filtering pass in addition to the work that a plain scan would already have finished. Our design is built for selective patterns, where almost nothing matches, and the per-position cost stays small and uniform across the scan. Due to this sensitivity, we implement a bail-out heuristic that watches for the dense case; if necessary, our technique will fall back to plain decompress-and-match rather than paying for a filter that cannot filter.

The headline number comes from ClickBench Q20:

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.

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:

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 approach never moved those bytes in the first place.

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 the full space of "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.