Pattern Matching on Compressed Strings without Decompression<br>Request Access
This is part one of a two-part series. It introduces how Vortex evaluates<br>LIKE predicates directly over FSST-compressed strings. We investigate the<br>performance considerations of our design in part two:<br>Compile or Prefilter?
Analytical datasets often include strings. These strings can be very large<br>(hundreds to thousands of characters), so modern analytics engines typically<br>compress them to reduce I/O costs.<br>FSST<br>is a lightweight string codec designed for this use, reducing text size by<br>roughly 2–3x. Unlike heavyweight codecs such as Zstd, FSST lets you decode a<br>single value without decompressing unneeded values. For this reason,<br>Vortex, our<br>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<br>later as part of a query. In many existing data management engines, reading the<br>data back requires decompressing it first. In contrast, as discussed in an<br>earlier post,<br>Vortex lets us perform compute over data while it stays compressed,<br>rather than decompressing it first and working on the result. This earlier work<br>focused on simple predicates, such as equality matching. This post tackles a<br>harder one: evaluating SQL LIKE over compressed strings without decompressing<br>them into a temporary, intermediate form.
Everything below builds on how FSST encodes strings. If the codec is new to<br>you, consider reading our<br>introduction to FSST<br>first, which walks through the theory and our open-source<br>Rust implementation.
In this post, we explore the two components that make this technique work: an<br>automaton that reads FSST symbol codes rather than raw bytes, and a SIMD<br>prefilter that keeps the automaton fast. Part two goes deeper, compares our<br>approach with the current state of the art, and covers what we learned along the<br>way.
The decompress-first baseline
Most query engines treat compressed strings as opaque. To query compressed data,<br>an engine loads the column, decompresses values, and then passes the full<br>strings to a matcher. This workflow is the only option for "heavyweight" codecs<br>such as Zstd, which do not support extracting individual values from compressed<br>data. A random-access encoding like FSST enables a better way to interact with<br>the data: because of the structure of the compressed form, every value is<br>independently readable, enabling search. Our goal was to use this functionality<br>to push the LIKE predicate down onto the compressed data itself, to skip the<br>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<br>eight bytes long, and replaces each occurrence with a single-byte code; in the<br>example above, www. maps to 12. The table also reserves code 255 as an<br>escape, so the pair (255, c) encodes a literal byte c. A compressed string<br>is a sequence of codes, and decompression is the process of performing<br>dictionary lookups and concatenating the symbols represented by those codes.
To search for a particular string in the data (e.g., google) without<br>decompression, we need to search the code-compressed text. Because FSST provides<br>a dictionary, we could start our search by looking for the pattern in the symbol<br>table. However, this only works if the predicate exactly matches the dictionary<br>values. For example, a dictionary might split www.google.com into [www.,<br>goog, le, .com], so we cannot simply check for a single google symbol in<br>the dictionary. In general, a byte-level substring search over codes is both<br>incorrect (a code's numeric value can coincide with a byte of the search string<br>by accident) and incomplete (the search string can straddle a symbol boundary).<br>To make the search sound, we lift the whole problem into code space: we treat<br>FSST symbol codes as the alphabet of a<br>deterministic finite automaton<br>(DFA).
A DFA is a machine built from a fixed set of states, each with a table that<br>maps every possible input to the next state. Feed it a sequence of inputs, and<br>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<br>matches the pattern, then run it directly over the compressed bytes.
Code Icon<br>Rust
// A compressed string is just a slice of FSST symbol codes.<br>// We match a substring pattern by stepping a DFA over those<br>// codes; the bytes are never expanded back into text.<br>fn matches(codes: &[u8], dfa: &SymbolDfa) -> bool {<br>let mut state = dfa.start;<br>for &code in codes {<br>state = dfa.step(state, code); // one table lookup per code<br>if dfa.is_accept(state) {<br>return true;<br>false
In our case, the inputs are the FSST codes themselves rather than the original<br>characters, so matching a compressed string costs one table lookup per<br>compressed byte; no decompression.
Three properties of FSST make it well-suited for DFA-based compute<br>(existing research):
It is a greedy encoding ,...