FSST: сжатие строк таблицей символов
В Модуле 08, Урок 04 мы видели проблему строковых кодировок: dictionary работает только при низкой кардинальности. Когда словарь переполняется (>1M unique строк), Parquet падает на PLAIN, ORC — на DIRECT stream. Строки занимают 60–80% размера типичных аналитических таблиц.
FSST (VLDB 2020, Boncz, Neumann & Leis) решает проблему иначе: вместо замены целых строк на индексы (dictionary) — замена частей строк на однобайтовые коды через обучаемую таблицу символов. Ключевое отличие от LZ-семейства: FSST сохраняет random access к отдельным строкам без декомпрессии блока.
Символьная таблица: 256 символов × 1–8 байт
FSST строит таблицу из 256 «символов» — частых подстрок длиной 1–8 байт. Каждый символ кодируется одним байтом (0x00–0xFF). 256 кодов — это всё пространство одного байта.
Обучающая выборка: 1000+ строк из блока
Обучающая выборка: 1000–5000 строк из блока. FSST анализирует частотность подстрок длиной 1–8 байт и выбирает 256, дающих максимальное суммарное сжатие.Overhead: ~1–2 KB на блок. Для 10 MB данных: < 0.02%
Overhead символьной таблицы: ~1–2 KB на блок. Для блока из 65K строк (10+ MB) — overhead < 0.02%. Таблица хранится один раз в начале блока. Декодер читает таблицу, затем поточно декодирует строки.Алгоритм обучения таблицы
FSST обучает таблицу за 5 итераций greedy-алгоритма:
5 итераций → таблица готова. Время обучения: < 1 мс
5 итераций — фиксированное число, не зависит от данных. Время обучения: O(sample_size × 5 × 256). На практике: < 1 мс на 5000 строк. Результат: таблица из 256 символов, оптимизированная для конкретного блока данных.Кодирование и декодирование
Кодирование — замена подстрок на коды. Декодирование — замена кодов на подстроки. Обе операции — поточные: один проход слева направо, без lookback.
Вход: ‘http://www.example.com/api/users’ (33 байта)
Входная строка: 'http://www.example.com/api/users' — 33 байта.Выход: ‘http://www.example.com/api/users’ (33 байта, lossless)
Восстановленная строка: 'http://www.example.com/api/users' — побайтово идентична оригиналу. Throughput декодирования: 1–3 GB/s (сравнимо с LZ4).Random access: ключевое отличие от LZ
FSST сохраняет random access к отдельным строкам — свойство, которого нет ни у LZ4, ни у Zstd, ни у GZIP:
Late decompression (сравнение в сжатом виде) — одно из ключевых преимуществ FSST для аналитических query engines. DuckDB использует это: WHERE url LIKE '%example%' может выполняться на FSST-сжатых строках, декомпрессируя только финальные match’и для вывода. Предикат = работает через encode-and-compare; LIKE — через частичное декодирование.
FSST12: 4096 символов для JSON/XML
Стандартный FSST использует 8-bit коды (256 символов). Для данных с широким алфавитом (JSON, XML, HTML — теги, атрибуты, namespaces) 256 символов может не хватить. FSST12 расширяет коды до 12 бит:
Adoption: кто использует FSST
FSST — одна из самых широко адаптированных CWI-кодировок. Три крупных аналитических движка интегрировали её:
FSST, ALP и FastLanes — три кодировки от одной группы (CWI Amsterdam), решающие три разных типа данных: FastLanes — integers (SIMD-оптимизация), ALP — floats (decimal→integer трансформация), FSST — strings (символьные таблицы). Все три интегрированы в DuckDB. Вместе они покрывают ~95% типов данных в аналитических workloads.
Итог
FSST — string compression через обучаемую символьную таблицу. Ключевые свойства:
- 256 символов × 1–8 байт — таблица обучается за 5 итераций greedy selection (менее 1 мс)
- Random access — каждая строка декодируется независимо, без декомпрессии блока
- Late decompression — предикаты (
=,LIKE) работают на сжатых строках - ~3x на текстовых данных при throughput 1–3 GB/s (сравнимо с LZ4)
- FSST12 — 12-bit коды (4096 символов) для JSON/XML с широким алфавитом
- Adopted: DuckDB, Hyrise, Velox, реализации на C++/Rust/Go
В следующем уроке — как все эти техники складываются в будущее кодирования: compressed execution, partial decompression, AnyBlox, и куда движутся исследования.