fsst · shipping · also Fast Static Symbol Table, FSST8

FSST

FSST compresses strings with a shared static table of byte-sequence symbols so individual strings can be decoded independently.

Mechanism: FSST8 replaces sequences of 1-8 bytes with single-byte codes. Code 255 escapes the following literal byte, allowing a fixed table to represent unseen input. FSST12 is a different variant. [1] [3]

Access: The decoder needs the selected string's encoded bytes and the matching symbol table, not preceding strings. The caller still supplies its location and encoded length. This is string-level access, not arbitrary character indexing or a disk-read guarantee. [1] [2]

Comparison: Equality on compressed values requires a common table and compatible encoding. Equal code bytes from different tables can decode differently. Whole-value dictionary coding removes repeated complete strings; FSST can additionally compress the dictionary's distinct strings. [1] [4]

Output capacity: In the pinned binary-mode decoder, bytes 00 ff 21 yield ram! with a constructed table. With two output bytes available, only ra is stored while the returned decoded length remains 4. A caller must check that length against capacity before consuming the result. Rebinding code 0 to rom changes the same stream to rom!. [2] [4]

Relations

related
Compression dictionary, Lossless compression, SSTable restart point

Advantages

  • A read-only decoder table can be shared across decoding threads. [2]

Limitations

  • Encoded payload size excludes the shared table and string-location metadata; savings must include those costs. [1, 2]
  • The published API controls cover valid streams only and do not establish rejection of malformed or adversarial input. [4]

Citations

  1. Boncz, Neumann and Leis (2020): FSST: Fast Random Access String Compression, PVLDB 13(11), sections 2-6 (accessed 2026-11-17)
  2. FSST pinned API: symbol table, binary mode, independent decoding and output truncation (accessed 2026-11-17)
  3. FSST project README at e638d4c: byte codes and FSST12 distinction (accessed 2026-11-17)
  4. Hesela: pinned FSST decoder controls, source, observations and replay (accessed 2026-11-17)
Sources & caveats
  • Source synthesis of the 2020 paper and a pinned author-maintained implementation; no paper throughput or compression-ratio result is claimed for another workload.
  • Ten constructed valid-stream cases run at two compiler optimization levels on one machine. Tables are manually populated, not trained; the experiment does not exercise table serialization or malformed input.

JSON: /data/terms/fsst.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. FSST. Hesela. 2026-11-17. https://hesela.dev/terms/fsst/