Learning Platform
Глоссарий Troubleshooting
Урок 09.02 · 35 мин
Продвинутый
Dictionary EncodingParquetORCArrowDuckDBCardinality ThresholdEncoding Fallback

Dictionary Encoding: кросс-форматный анализ

В Модуле 01 мы рассмотрели идею dictionary encoding: замена повторяющихся значений на индексы словаря. В Модуле 02 — как Parquet реализует RLE_DICTIONARY. В Модуле 03 — как ORC использует отсортированный словарь с DICTIONARY_DATA stream.

Теперь вопрос другой: почему эти реализации настолько различны? Один алгоритм — и пять принципиально разных архитектурных решений в Parquet, ORC, Avro, Arrow и DuckDB. Каждое оптимизировано под свой паттерн доступа, и каждое ломается на своих граничных условиях.

Анатомия решений: что выбирает каждый формат

Пять реализаций dictionary encoding: ключевые решения
РешениеАрхитектурный параметр, определяющий поведение dictionary encoding в каждом формате
ParquetApache Parquet — колоночный формат для аналитики. Dictionary encoding: RLE_DICTIONARY (enum 8)
ORCApache ORC — колоночный формат для Hive. Dictionary encoding с сортированным словарём
ArrowApache Arrow — in-memory формат. DictionaryArray как отдельный тип массива
DuckDBDuckDB — аналитическая СУБД. Dictionary encoding как один из вариантов хранения сегментов
AvroApache Avro — строковый формат для сериализации. Нет встроенного dictionary encoding
Область словаряГраницы, в пределах которых словарь уникален. Определяет гранулярность: чем меньше область — тем больше словарей и overhead.
Per-pageКаждая data page (~1 MB) имеет свой словарь в dictionary page. Column chunk может содержать десятки словарей. При fallback — весь column chunk переключается на PLAIN.
Per-stripeОдин словарь на stripe (~256 MB по умолчанию). DICTIONARY_DATA stream хранит уникальные значения, DATA stream — индексы. Большая область = больше уникальных значений.
Per-arrayОдин словарь на весь DictionaryArray. В IPC: dictionary батчи отправляются отдельно, последующие record batch-и ссылаются по id. Delta dictionary для инкрементальных обновлений.
Per-segmentОдин словарь на сегмент хранения (~122K строк по умолчанию). Analyzer выбирает Dictionary, если кардинальность ниже порога.
—Avro не имеет dictionary encoding на уровне формата. Enum-тип в schema — ближайший аналог, но это schema-level решение, не runtime encoding.
Порядок словаряВ каком порядке значения хранятся в словаре. Влияет на возможность predicate pushdown и range-запросов
Insertion orderЗначения в словаре идут в порядке первого появления. Предсказуемо, но не позволяет range-predicate на словаре: WHERE name BETWEEN 'a' AND 'c' требует полного скана.
SortedСловарь отсортирован лексикографически. Позволяет binary search и range predicate pushdown: WHERE name > 'a' → найти индекс 'a' в словаре, фильтровать по индексам. Дополнительная стоимость сортировки при записи.
User-definedПорядок определяется при создании массива. Arrow не навязывает сортировку — это решение пользователя. Можно создать ordered dictionary для range-запросов.
By frequencyDuckDB может сортировать по частоте для оптимального bit-packing: самые частые значения получают наименьшие индексы → меньше бит на индекс.
—Нет словаря — нет порядка. Enum символы в Avro schema хранятся в порядке объявления.
Кодирование индексовКак кодируются ссылки на словарь. Определяет overhead на одно значение
RLE / Bit-PackRLE/Bit-Packing Hybrid (Parquet enum 3): серии одинаковых индексов → RLE, смешанные → bit-packing с минимальной шириной. Гибрид даёт лучшее для обоих паттернов.
RLEv2ORC RLEv2 с 4 подкодировками: Short Repeat (серии), Direct (bit-packed), Patched Base (outliers), Delta (монотонные). Более гибкий, чем Parquet RLE.
Typed indicesТипизированные индексы: Int8, Int16, Int32 в зависимости от размера словаря. Прямые числа без дополнительного кодирования — для O(1) доступа в памяти.
Bit-packedBit-packed с шириной ceil(log₂(dict_size)). DuckDB оптимизирует под SIMD: ширина выровнена до 1/2/4/8/16/32 бит.
——
Fallback-стратегияЧто происходит, когда кардинальность превышает порог и словарь становится слишком большим
PLAIN (весь chunk)Если dictionary page > dictionary_page_size_limit (1 MB по умолчанию), весь column chunk переключается на PLAIN. Атомарное решение: либо dictionary для всех pages, либо PLAIN для всех.
Direct streamПереключение на direct encoding: DATA stream хранит raw UTF-8 байты, LENGTH stream — длины. Решение принимается per-stripe на основе ratio словарь/данные.
Нет fallbackDictionaryArray — это тип, не кодировка. Если создали dictionary — он остаётся. Конвертация в plain array — явная операция. Arrow IPC передаёт dictionary как есть.
Constant / FSSTЕсли все значения одинаковы → Constant encoding. Если кардинальность высокая → FSST (string compression) или Uncompressed. Нет жёсткого fallback — Analyzer перебирает варианты.
——

Parquet: per-page dictionary с атомарным fallback

Parquet принимает решение о dictionary на уровне column chunk (все data pages колонки в одном row group). Процесс:

Parquet dictionary: запись и fallback

Writer начинает column chunk

Writer начинает записывать column chunk. Буфер dictionary page накапливает уникальные значения по мере записи data pages.

Для каждого значения: lookup в словаре → index или insert

Каждое новое значение: если уже в словаре — записываем индекс. Если новое — добавляем в словарь. Словарь растёт по мере записи.

Словарь < 1 MB → Dictionary Page + Data Pages

Словарь поместился в лимит. Записывается dictionary page + data pages с RLE-encoded индексами. Одна dictionary page на весь column chunk.
РезультатФайловая структура: Dictionary Page (PLAIN encoding уникальных значений) → N Data Pages (RLE_DICTIONARY encoding индексов). Dictionary Page записывается первой в column chunk.

Словарь > 1 MB → Fallback на PLAIN

Словарь превысил лимит. Writer отбрасывает весь словарь и перезаписывает ВСЕ data pages в PLAIN. Это происходит в памяти до записи на диск.
РезультатВсе data pages записаны в PLAIN encoding — raw значения без словаря. Потеря: время на построение словаря. Но для высокой кардинальности (UUID) PLAIN и так оптимален.

Критический момент: fallback атомарный. Нельзя часть pages закодировать dictionary, а часть — PLAIN. Весь column chunk использует одну кодировку. Это упрощает reader (не нужно проверять кодировку каждой page), но тратит ресурсы writer на колонках, где dictionary неизбежно провалится.

WARNING

Порог dictionary_page_size_limit (по умолчанию 1 MB в PyArrow) — это размер словаря в байтах, не количество уникальных значений. Для коротких строк ("US", "DE") — до ~500K уникальных значений в 1 MB. Для длинных строк ("United States of America") — ~40K. Реальный порог кардинальности зависит от средней длины значений.

ORC: per-stripe sorted dictionary

ORC принимает решение о dictionary per-stripe (~256 MB данных). Ключевое отличие — словарь отсортирован:

ORC dictionary: sorted словарь с range predicate support

Sorted Dictionary

DICTIONARY_DATA streamУникальные строки, отсортированные лексикографически: apple → banana → cherry. Позволяет binary search за O(log n). Стоимость: O(n log n) при записи.
DATA stream (индексы)Индексы ссылаются на позиции в отсортированном словаре. 0=apple, 1=banana, 2=cherry, 3=date. RLEv2-encoded для компактности.

Range Predicate Pushdown

WHERE fruit BETWEEN ‘b’ AND ‘d’

SQL запрос с range-предикатом на строковой колонке с dictionary encoding.

Binary search: ‘b’ → idx 1, ‘d’ → idx 3

Binary search в отсортированном словаре: 'b' → index 1 (banana), 'd' → index 3 (date). Предикат: index BETWEEN 1 AND 3. Не нужно декодировать строки.

Фильтр: idx BETWEEN 1 AND 3

Фильтрация по числовым индексам вместо строковых сравнений. На 1M строк: 1M integer comparisons вместо 1M string comparisons. ~10x ускорение.

Преимущество ORC: range-predicate pushdown через отсортированный словарь. WHERE name > 'M' превращается в WHERE index > 12 — integer comparison вместо string comparison. Parquet не может этого делать, потому что его словарь не отсортирован.

Недостаток: сортировка словаря при записи стоит O(n log n). Для stripe с 500K уникальных строк — это ощутимо. Но выигрыш при чтении (range queries) обычно перевешивает.

Arrow: DictionaryArray как тип

В Arrow dictionary — не кодировка, а тип данных. DictionaryArray — отдельный тип массива наравне с Int64Array или StringArray:

Arrow DictionaryArray: два буфера в памяти

Структура в памяти

Dictionary buffer (StringArray)Массив уникальных значений — обычный Arrow StringArray. Порядок определяется при создании. Можно сделать sorted для binary search.
indices ссылаются на позиции
Indices buffer (Int32Array)Массив индексов — Int8, Int16 или Int32 в зависимости от размера словаря. Прямой offset в словарь: O(1) lookup по каждому значению.

В IPC (Arrow Flight / Feather)

Msg 1: Dictionary Batch (полный словарь, id=0)

Первый message содержит dictionary batch с полным словарём и dictionary id. Последующие record batch-и содержат только индексы, ссылаясь на этот id.

Msg 2..N: Record Batch (indices only, dict_id=0)

Record batch содержит только Int32 indices. Reader использует ранее полученный словарь для декодирования. Экономия на передаче: словарь один раз, индексы — для каждого batch.

Опционально: Delta Dictionary (новые записи)

Delta dictionary: если в новом batch появились значения, не входящие в словарь — отправляется DELTA dictionary message с новыми записями. Не нужно пересылать весь словарь.

Критическое отличие Arrow: нет fallback. Если создали DictionaryArray — он навсегда dictionary. Конвертация обратно в plain — явная операция (dictionary_decode()). Это design choice: Arrow — in-memory формат, где тип определяется при создании, а не при записи.

В Arrow IPC формат поддерживает delta dictionaries — инкрементальные обновления словаря. Если в потоке record batch-ей появляется новое значение — отправляется delta dictionary message, добавляющий запись. Не нужно пересылать весь словарь.

DuckDB: analyze-and-pick

DuckDB не привязан к одному формату хранения. Его Analyzer сэмплирует данные и выбирает оптимальную кодировку для каждого сегмента (~122K строк):

DuckDB encoding selection: Analyzer pipeline

Сегмент колонки (~122K строк)

DuckDB разбивает колонку на сегменты по ~122,880 строк (row group size). Для каждого сегмента Analyzer выбирает кодировку независимо.
Analyze

Подсчёт статистик: cardinality, min, max, avg_length

Analyzer считает уникальные значения, min/max, распределение. Для строк: средняя длина, кардинальность. Для чисел: range, delta patterns.
Select encoding
ConstantВсе значения одинаковы (cardinality=1). Хранение: одно значение + count. 0 бит на значение кроме заголовка. Пример: колонка partition key.
DictionaryКардинальность ниже порога (~4096 для строк). Словарь + bit-packed индексы. DuckDB сортирует словарь по частоте: самые частые значения → наименьшие индексы → меньше бит.
FSSTВысокая кардинальность строк, но паттерны в подстроках. FSST (Fast Static Symbol Table) учит 256-символьную таблицу и заменяет частые подстроки. ~3x сжатие с random access.
BitPacking/FORЧисловые данные с узким диапазоном. FOR (Frame of Reference): base + bit-packed offsets. BitPacking: минимальная ширина для max value. Часто комбинируется с Delta.

Ключевое отличие DuckDB: нет жёсткого fallback — есть континуум вариантов. Если dictionary не подходит — Analyzer рассмотрит FSST, BitPacking, FOR, Constant, RLE или Uncompressed. Каждый сегмент может использовать свою кодировку. Это даёт гибкость, которой нет у Parquet (dictionary-or-PLAIN) и ORC (dictionary-or-direct).

Кардинальность: когда dictionary ломается

Главный враг dictionary encoding — высокая кардинальность. Вопрос: при какой кардинальности словарь становится убыточным?

Кардинальность vs compression: точка безубыточности
Формула overheadDictionary encoding экономит, когда: N × avg_len > dict_size + N × ceil(log₂(card)) / 8. Слева — raw размер. Справа — словарь + bit-packed индексы.
Пороги по форматамКаждый формат определяет порог по-разному: Parquet — по размеру словаря (1 MB), ORC — по ratio, DuckDB — по кардинальности (~4096 для строк).
10 уникальных (country)10 строк × ~10 байт = 100 байт словарь. 1M × 4 бита = 500 KB индексы. Raw: 1M × 10 = 10 MB. Экономия: 20x. Dictionary всегда выгоден.
10K уникальных (city)10K × ~12 байт = 120 KB словарь. 1M × 14 бит = 1.75 MB индексы. Raw: 1M × 12 = 12 MB. Экономия: 6x. Dictionary полезен, но словарь уже занимает заметное место.
500K уникальных (email)500K × ~25 байт = 12.5 MB словарь. 1M × 19 бит = 2.4 MB индексы. Raw: 1M × 25 = 25 MB. Итого: 14.9 MB — хуже чем raw! Словарь превышает экономию на индексах.

Практическое правило: dictionary выгоден, когда кардинальность ≪ N (количества строк). Точка безубыточности зависит от средней длины значений:

  • Короткие строки ("US", "DE") — dictionary выгоден до ~100K уникальных
  • Средние строки ("Engineering") — до ~10K–50K уникальных
  • Длинные строки ("https://...") — до ~1K–5K уникальных

Гибридные стратегии и fallback-деревья

В реальности решение «dictionary или нет» — не бинарное. Форматы используют деревья решений:

Дерево выбора: Parquet writer vs DuckDB Analyzer

Parquet Writer

Начать с Dictionary

Writer начинает с dictionary encoding для каждой колонки — это default. Пессимистичный подход: пробуем оптимальное, fallback на простое.

dict_size > limit?

Проверка при записи каждой page: если dictionary page > dictionary_page_size_limit — fallback. Порог настраивается (PyArrow: dictionary_pagesize_limit).
Нет

RLE_DICTIONARY для column chunk

Dictionary encoding для всего column chunk. Dictionary Page записывается первой, затем Data Pages с RLE-encoded индексами.

При overflow → весь chunk → PLAIN

DuckDB Analyzer

Analyze сегмент

Analyzer сэмплирует сегмент: подсчёт уникальных, min/max, распределение, средняя длина. Решение per-segment, не per-column.

card=1 → Constant / card<thresh → Dict / else → FSST/BP

Если все значения одинаковы — Constant (0 бит). Если кардинальность ≤ порога — Dictionary. Иначе — для строк FSST, для чисел BitPacking/FOR.

Кодировка per-segment, может меняться

Каждый сегмент может использовать разную кодировку. Колонка city: первые 122K строк = Dictionary (10 городов), следующие = FSST (1000 городов).

fallback — континуум вариантов

Dictionary overhead: что стоит словарь

Словарь — не бесплатная абстракция. Каждый формат платит свою цену:

Overhead dictionary encoding по форматам
Тип overheadКатегория накладных расходов dictionary encoding
ParquetOverhead dictionary encoding в Apache Parquet
ORCOverhead dictionary encoding в Apache ORC
Arrow IPCOverhead dictionary encoding в Arrow IPC/Feather
Память writerСколько памяти writer тратит на поддержание словаря при записи
dict + hash mapWriter держит dictionary page + hash map для O(1) lookup. Для 100K строк × 20 байт: ~2 MB dict + ~3 MB hash map = ~5 MB. Умножить на число колонок.
sorted treeORC writer использует TreeMap/TreeSet для поддержания отсортированного словаря. Overhead больше, чем hash map: ~8 MB на колонку.
hash + bufferArrow DictionaryBuilder использует hash set + значения. Для 100K строк: ~6 MB. При delta dictionary — только новые записи.
I/O при чтенииДополнительный I/O для загрузки словаря при чтении
1 page readDictionary page — один дополнительный read до data pages. Для column pruning: если колонка не нужна — dictionary page не читается. Для row group pruning: dictionary не участвует в min/max stats.
1 stream readDICTIONARY_DATA stream + LENGTH stream — два дополнительных read. Но ORC footer содержит stream directory, поэтому reader знает exact offset. Sequential read.
1 messageDictionary batch — один дополнительный IPC message в начале потока. При Arrow Flight: один дополнительный gRPC round-trip. При Feather: sequential read.
Decode costCPU-стоимость декодирования каждого значения при чтении
index lookupКаждое значение: RLE/bit-unpack → index → dictionary[index]. Один indirect memory access. На CPU с L1 cache hit: ~1-2 ns. Если словарь не помещается в L1 (~32 KB): cache miss → 5-10 ns.
index lookupRLEv2 decode → index → dictionary lookup. Потенциально дороже, чем Parquet: RLEv2 decode сложнее (4 подкодировки). Но словарь часто в cache.
O(1) directArrow: indices → dictionary[index]. Прямой доступ без decode. Самый дешёвый: массив в памяти, индекс = offset. O(1).

Ключевые выводы

  1. Пять форматов — пять архитектур dictionary. Parquet: per-page, insertion order, атомарный fallback. ORC: per-stripe, sorted, range-predicate pushdown. Arrow: per-array, тип (не кодировка), delta dictionaries. DuckDB: per-segment, frequency-sorted, multi-variant fallback.
  2. Сортировка словаря — трейдофф. ORC: sorted → range predicates за O(log n), но O(n log n) при записи. Parquet: insertion order → нет range pushdown, но O(1) insert.
  3. Fallback-стратегии определяют поведение на граничных данных. Parquet ломается атомарно (весь chunk → PLAIN). DuckDB плавно переключается (Dictionary → FSST → Uncompressed).
  4. Кардинальность — ключевой порог: до ~10K–50K уникальных значений (зависит от длины строк) dictionary выгоден. Выше — словарь занимает больше, чем экономит.
  5. Arrow DictionaryArray — тип, не кодировка. Нет runtime fallback — решение принято при создании. Delta dictionaries поддерживают инкрементальные обновления в streaming-сценариях.
  6. Dictionary overhead реален: 5–8 MB RAM per column при записи, дополнительный I/O при чтении, indirect memory access при decode. На колонках с 1000+ столбцов — суммируется.

Закончили урок?

Отметьте его как пройденный, чтобы отслеживать свой прогресс

Войдите чтобы оценить урок
Вернуться к курсу
Прогресс модуля
0 из 6