Строковые кодировки: за пределами словаря
В Уроке 02 мы разобрали, как dictionary encoding работает в пяти форматах — и где он ломается. Когда кардинальность превышает порог (1 MB Parquet page, stripe ratio в ORC), словарь становится бесполезным: overhead на хранение самого словаря превышает экономию на индексах.
Но строки — самый распространённый тип данных в аналитических хранилищах: URL, email, JSON-поля, user_agent, текстовые описания, log messages. Если словарь не работает — что делать? В Модуле 02 мы видели PLAIN и DELTA_BYTE_ARRAY как альтернативы. Теперь разберём всю палитру строковых кодировок и поймём, почему для строк всё ещё не было хорошего решения — до появления FSST.
PLAIN: length-prefixed byte arrays
Самая простая кодировка строк — PLAIN. Каждая строка хранится как пара (length, bytes):
PLAIN — это baseline, не кодировка. Никакого сжатия, никакой трансформации. Форматы используют PLAIN как fallback: Parquet — когда dictionary overflow, ORC — direct encoding для high-cardinality строк.
Prefix Encoding (общий префикс)
Когда строки отсортированы (или почти отсортированы), соседние значения часто делят общий префикс. Prefix encoding (Parquet: DELTA_BYTE_ARRAY) хранит только длину общего префикса и суффикс:
Без prefix encoding
С prefix encoding
Prefix encoding эффективен только для отсортированных данных. Для случайного порядка общий префикс между соседями = 0, и кодировка вырождается в PLAIN с дополнительным overhead.
Parquet DELTA_BYTE_ARRAY (enum 7)
Parquet реализует prefix encoding как DELTA_BYTE_ARRAY:
Отсортированные строки: [s₁, s₂, s₃, …]
Входные строки, обычно отсортированные (после sort_columns или dictionary fallback). Без сортировки — prefix encoding бесполезен.prefix_lengths → DELTA_BINARY_PACKED
Для каждой пары (sᵢ, sᵢ₊₁) вычисляем длину общего префикса. Массив prefix_lengths кодируется DELTA_BINARY_PACKED — дельты между длинами префиксов компактны.suffixes → DELTA_LENGTH_BYTE_ARRAY
Суффиксы (то, что осталось после общего префикса) конкатенируются в один byte array. Их длины — тоже DELTA_BINARY_PACKED (для строк одинаковой длины дельты будут около нуля).Decode: prefix от предыдущей + suffix
Decode: для i-й строки — прочитать prefix_length[i], скопировать первые prefix_length[i] байт из предыдущей строки, добавить suffix[i]. O(1) амортизированно, но зависимость от предыдущей строки.DELTA_BYTE_ARRAY имеет sequential dependency: чтобы декодировать строку N, нужно знать строку N-1 (для копирования префикса). Это не позволяет random access внутри page — нужно декодировать с начала. Для analytics workloads (full column scan) это не проблема, но для point lookups — да.
Delta-Length Encoding (длины отдельно)
Когда строки не отсортированы, но имеют похожую длину (log messages, fixed-format records), выделение длин в отдельный поток даёт выигрыш:
Lengths: [45, 47, 44, 46]
Длины строк (45, 47, 44, 46) кодируются DELTA_BINARY_PACKED. Дельты: [45, +2, -3, +2]. Минимальный bit-width. Для строк одинаковой длины: все дельты = 0.→ DELTA_BINARY_PACKED (12 бит)
DELTA_BINARY_PACKED: base=45, дельты в zigzag → [0, 4, 5, 4] → bit-packed 3 бит. 4 × 3 = 12 бит вместо 4 × 32 = 128 бит.Bytes: конкатенация без разделителей
Байты строк конкатенированы подряд без разделителей. Длины определяют границы. Нет сжатия самих байтов — только устранение length overhead.→ Raw bytes (182 байта)
182 байта контента записаны подряд. Для доступа к i-й строке: сложить lengths[0..i-1] — получить offset. O(n) для random access, O(1) амортизированно при sequential scan.Выигрыш DELTA_LENGTH_BYTE_ARRAY:
- Длины кодируются компактно: если длины похожи, дельты минимальны → несколько бит на строку вместо 32
- Нет 4-byte length prefix на каждую строку: длины вычисляются из delta-encoded массива
- Но: сам контент строк не сжимается. Для URL с высокой кардинальностью — это лучше PLAIN, но далеко от dictionary
ORC: Direct String Encoding
ORC использует другой подход к high-cardinality строкам. Вместо prefix/delta-length, ORC переключается на direct encoding — три отдельных потока:
Dictionary mode (low cardinality)
Direct mode (high cardinality)
Ключевое отличие ORC от Parquet: ORC кодирует длины строк отдельно через RLEv2, что даёт компрессию длин. Parquet PLAIN хранит 4-byte length перед каждой строкой. Для миллиона строк одинаковой длины: ORC LENGTH stream → RLEv2 Short Repeat = десятки байт, Parquet PLAIN → 4 MB length overhead.
Проблема dictionary overflow
Самый болезненный сценарий для строковых колонок — dictionary overflow: колонка начинается с повторяющихся значений, но по мере записи кардинальность растёт и словарь переполняется.
Начало записи: 1000 unique values, dict = 15 KB
Writer начинает запись строковой колонки. Первые 500K строк — 1000 уникальных department names. Словарь: 1000 × ~15 байт = 15 KB. Отлично работает.Рост кардинальности: 500K unique → dict = 10 MB
В середине column chunk появляются user_id-like значения. Кардинальность взрывается: 500K уникальных строк. Словарь растёт: 500K × 20 байт = 10 MB. Parquet dictionary page limit = 1 MB.Parquet: PLAIN для всего chunk. Первые 500K тоже теряют сжатие.
Parquet: весь column chunk переключается на PLAIN. Уже записанные dictionary-encoded pages переписываются. Потеря: CPU на перекодирование + потеря сжатия для первых 500K строк, которые отлично сжимались словарём.ORC: direct mode для stripe. Длины через RLEv2.
ORC: stripe-level решение. Если ratio словарь/данные > порога — direct mode. Но ORC stripes = 256 MB, так что решение принимается раньше, на этапе buffer flush.Mixed cardinality: ни dictionary, ни PLAIN не оптимальны
Результат: для mixed-cardinality данных (часть значений повторяется, часть уникальна) ни dictionary, ни PLAIN не оптимальны. Dictionary теряет на overhead, PLAIN теряет на повторах. Нужен гибрид.DuckDB: multi-variant решение
DuckDB не ограничивается бинарным выбором dictionary/PLAIN. Его Analyzer перебирает варианты:
Кросс-форматное сравнение строковых кодировок
Почему нужен был FSST
Подведём итог проблемы строковых кодировок к 2020 году:
Ключевые выводы
- PLAIN — не кодировка, а baseline. Length-prefixed bytes без сжатия. Используется как fallback, когда ничего лучше не работает.
- Prefix encoding (DELTA_BYTE_ARRAY) эффективен только для отсортированных строк — общий префикс соседей даёт 2–5x. Для случайного порядка — вырождается в PLAIN + overhead.
- DELTA_LENGTH_BYTE_ARRAY отделяет длины от данных и кодирует их delta — экономит на length overhead, но не сжимает контент строк.
- ORC direct encoding выделяет LENGTH stream с RLEv2 — компактнее Parquet PLAIN для строк одинаковой длины.
- Dictionary overflow — главная проблема: колонка, которая начинается с повторов, но потом взрывается уникальными значениями. Parquet теряет сжатие для всего chunk. DuckDB пробует FSST как альтернативу.
- До 2020 года у строк не было хорошего ответа на high-cardinality + random access. FSST (Модуль 09) заполняет этот gap: ~3x сжатие, random access, equality на сжатых данных.