Module fsst 

FSST, the string encoding.

Fast Static Symbol Table, from the 2020 paper by Boncz, Neumann and Leis. A table of at most 255 symbols of one to eight bytes each, and compression is replacing the longest matching symbol at each position with its one byte code. A byte that no symbol covers is escaped, which costs two bytes, so the table has to be good or the output is larger than the input.

Why this and not a general compressor

spec/06-compression.md section 6.2 is blunt about it. FSST compresses text about 2x, which is worse than what zstd does to the same bytes, and the ratio is not why it is here. Two other properties are.

The first is random access. Every string in a column is compressed independently against a shared table, so reading row 4,000,000 does not mean decompressing the four million before it. A block compressor gives up that property and gets it back by cutting the data into blocks, which means reading one string decompresses a block.

The second is that a substring search can run against the compressed bytes. Compress the needle with the same symbol table and look for the compressed needle in the compressed haystack. That is what turns URL LIKE '%google%' from a decompress and scan into a scan, and section 6.7 says it is worth more on the ClickBench workload than any ratio improvement. It needs care, because the greedy match that compresses a needle standing alone can segment it differently from the way the same bytes were segmented inside a longer string, so a hit is a candidate and a miss is not a proof. The scan that uses it is M3 work and lives with the rest of encoded execution.

Training

The table is built from a sample rather than from the whole column, and the algorithm is the paper’s: start with nothing, so every byte escapes, then repeat five times. Compress the sample with the table you have, count how often each symbol is used and how often each pair of adjacent symbols occurs, and build the next table from the best 255 of the symbols and the concatenations by gain, where gain is how many bytes of input the symbol accounts for. Five generations is what the paper found, and the shape of the thing is that the first generation learns single bytes, the second learns pairs, and the fifth is finding eight byte symbols like https://.

Matching

Three lookups in a fixed order, longest first. A hash table on the first three bytes for symbols of three bytes and up, a flat table indexed by the first two bytes, and a flat table indexed by the first one. The hash table probes eight slots and keeps the longest symbol that matches rather than the first, because several symbols share a three byte prefix and taking the first would make the ratio depend on insertion order.

Structs

SymbolTable

A trained symbol table, and everything needed to compress and decompress against it.

Constants

ESCAPE

The code that means the next byte is a literal. 255 rather than 0 so that the 255 real codes are a contiguous range starting at zero and a code is its own index into the symbol table.

MAX_SYMBOLS

How many real symbols a table can hold.

MAX_SYMBOL_LEN

The longest a symbol can be. Eight, so that a symbol is a u64 and a match is a mask and a compare rather than a loop over bytes.