Boolean, NULL и вложенные кодировки
Три типа данных, которые кажутся тривиальными — boolean, NULL и nested structures — на практике порождают удивительно разные архитектурные решения в каждом формате. Boolean: 1 бит информации, но хранить можно 5 разными способами. NULL: отсутствие данных, но каждый формат тратит разное количество байт на его представление. Nested: вложенные структуры, которые требуют дополнительных метаданных для восстановления иерархии.
В Модуле 02 мы детально разобрали Dremel-алгоритм для Parquet. В Модуле 03 — потоки PRESENT и Byte RLE в ORC. Теперь — кросс-форматное сравнение: какой формат тратит сколько на boolean, NULL и nested, и почему.
Boolean Encoding: 1 бит данных, N способов хранения
Boolean — простейший тип: true/false, 1 бит информации. Но способ кодирования определяет overhead:
Parquet: RLE для boolean
RLE Bit-Packed HybridParquet кодирует boolean через RLE/Bit-Packed Hybrid (тот же алгоритм, что для dictionary indices). Серия true-true-true → RLE run. Смешанные → bit-packed по 8 значений в байт. Для колонки is_active (95% true): один RLE run покрывает тысячи значений.
ORC: Boolean RLE (Byte RLE)
Byte RLE для booleanORC упаковывает 8 boolean в 1 байт (MSB first), затем применяет Byte RLE к результату. Серии одинаковых байтов (0xFF = 8 true, 0x00 = 8 false) кодируются как run. Для is_active (95% true): большинство байтов = 0xFF → длинные RLE runs.
Arrow: Validity Bitmap
Bit vector (no compression)Arrow хранит boolean как bit vector: 1 бит на значение, packed в байты (LSB first). Нет RLE или другой компрессии — in-memory формат оптимизирован для O(1) доступа через bit-адресацию, а не для размера. 1M boolean = 125 KB.
DuckDB: адаптивный
Constant / RLE / BitPackingDuckDB Analyzer выбирает: (1) Constant — если все true или все false (0 байт на данные). (2) RLE — если длинные серии. (3) Uncompressed bitmap — если паттерн случайный. Решение per-segment.
Overhead на 1 миллион boolean значений
Сценарий — распределение true/false в колонке
ParquetParquet RLE/Bit-Packed Hybrid encoding
ORCORC Boolean RLE (Byte RLE на packed bytes)
ArrowArrow bit vector (uncompressed)
DuckDBDuckDB adaptive: Constant / RLE / bitmap
All true1M значений, все = true. Минимальная энтропия: H = 0 бит. Идеальный случай для RLE.
~8 байтОдин RLE run: header (4 bytes) + value (1 bit) + run length. ~8 байт на 1M значений.
~4 байтВсе packed bytes = 0xFF. Один Byte RLE run: control byte + byte value + repeat count. ~4 байта.
125 KB1M бит / 8 = 125,000 байт. Arrow не сжимает — хранит полный bitmap для O(1) доступа.
~8 байтConstant encoding: metadata + одно значение. ~8 байт. Analyzer определяет Constant автоматически.
95% true1M значений, 950K true, 50K false случайно распределены. Низкая энтропия: H ≈ 0.29 бит.
~15 KBRLE runs прерываются false-значениями. ~50K переключений → ~50K коротких runs. Header overhead доминирует. Bit-packed участки между runs.
~20 KBPacked bytes: большинство = 0xFF, некоторые с false-битами. Byte RLE сжимает серии 0xFF, mixed bytes — литеральные. ~20 KB.
125 KBArrow: тот же bitmap, 125 KB. Содержание не влияет — всегда 1 бит/значение.
~15 KBRLE encoding. Runs длинные (в среднем ~20 true подряд), overhead на run headers.
50/50 random1M значений, 50% true, 50% false, случайный порядок. Максимальная энтропия: H = 1 бит. Worst case для RLE.
~125 KBRLE неэффективен: runs длиной 1–2. Bit-packed mode: 1 бит/значение + header overhead. ≈125 KB + overhead.
~125 KBPacked bytes случайные — Byte RLE не может сжать. Литеральные runs: control byte + bytes. ~125 KB + ~15 KB control.
125 KBArrow: 125 KB. Для random boolean — Arrow оказывается оптимальным: нет overhead на RLE headers.
~125 KBDuckDB Analyzer выбирает uncompressed bitmap — RLE хуже из-за overhead. 125 KB.
NOTE
Парадокс Arrow: для random boolean данных отсутствие компрессии оптимально. RLE/Byte RLE добавляют header overhead при коротких runs. Arrow bitmap — ровно 1 бит/значение без overhead. Но для skewed данных (95% true) — Arrow тратит 125 KB, где Parquet/ORC/DuckDB обходятся 15–20 KB.
NULL Handling: три архитектуры
NULL — не значение, а отсутствие значения. Но каждый формат должен как-то записать, что в позиции N данных нет. Три принципиально разных подхода:
Parquet: Definition Levels
Definition LevelДля каждого значения: целое число от 0 до max_definition_level. Для плоской nullable колонки: 0 = NULL, 1 = значение есть. Для вложенных структур: 0 = top-level NULL, 1 = parent NULL, 2 = значение. Кодируется RLE/Bit-Packed.
Data (только non-null)Массив данных содержит только non-null значения. Позиция определяется по definition levels: пропускаем позиции с def_level < max. Экономия: NULL не занимают места в data.
Overhead: 1 бит/значение (RLE для плоских)
ORC: PRESENT Stream
PRESENT streamByte RLE bitmap: 1 = значение есть, 0 = NULL. 8 boolean на байт, затем Byte RLE. Отсутствует для NOT NULL колонок (экономия metadata). Присутствует для каждого nullable столбца — включая вложенные.
DATA stream (только non-null)Только non-null значения. Как в Parquet — NULL не занимают места. PRESENT bitmap + DATA stream работают в паре: scan PRESENT, для каждой 1 — прочитать из DATA.
Overhead: 1 бит/значение (Byte RLE)
Arrow: Validity Buffer
Validity bitmapBit vector: 1 = valid, 0 = null. LSB first, 64-byte aligned. Не сжимается — O(1) bit-адресация. null_count в metadata для быстрой проверки 'есть ли NULL вообще'.
Values buffer (все позиции)В отличие от Parquet/ORC, Arrow хранит значения для ВСЕХ позиций — включая NULL. Значение на NULL-позиции undefined (мусор). Это позволяет O(1) random access: values[i] + validity[i].
Overhead: 1 бит/значение + wasted space на NULL-позициях
Ключевое архитектурное различие
Свойство NULL-представления
Parquet / ORC (sparse)NULL-позиции не занимают места в data stream. Экономия на хранении, но decode требует skip-логики.
Arrow (dense)Все позиции присутствуют в values buffer. NULL-позиции содержат undefined данные. Простой decode: values[i].
Data sizeСколько места занимают данные (без bitmap)
non_null_count × value_sizeХранятся только non-null значения. Для 1M строк с 50% NULL: 500K значений. Экономия 50% на data.
total_count × value_sizeХранятся все значения, включая undefined на NULL-позициях. Для 1M строк с 50% NULL: 1M значений. Нет экономии.
Random accessСтоимость доступа к i-му значению
O(n) — scan bitmap до iЧтобы прочитать значение на позиции i: подсчитать количество единиц в bitmap до i — это индекс в data stream. Можно ускорить с popcount, но всё равно дороже O(1).
O(1) — values[i]Прямой доступ: values[i] + проверка validity[i]. O(1). Именно ради этого Arrow тратит лишнее место.
NOT NULL колонкиОптимизация для колонок без NULL
Bitmap отсутствуетParquet: definition level = 0 (только required fields). ORC: PRESENT stream опускается. Нет overhead вообще.
null_count = 0, bitmap optionalArrow: если null_count = 0, validity buffer может быть null (отсутствовать). Проверка: if (validity != null) check bit, else always valid.
Вложенные NULLNULL на разных уровнях вложенности (list = null vs element = null)
Definition levels (multi-value)Parquet def_level кодирует УРОВЕНЬ, на котором значение стало NULL: 0 = top-level NULL, 1 = list NULL, 2 = element NULL, 3 = значение. Один integer на позицию вместо нескольких bitmap.
Per-level validityArrow: отдельный validity buffer на каждом уровне вложенности. ListArray has validity + child array has its own validity. Более прямолинейно, но больше buffers.
Bytes-per-NULL сравнение
% NULLДоля NULL в колонке из 1M строк
Parquetdef_level (RLE) + only non-null data values
ORCPRESENT (Byte RLE) + only non-null data values
Arrowvalidity bitmap + ALL data values (including undefined at NULL)
AvroAvro union с null: 1 byte per value (union index) + only non-null data
0% NULLВсе значения present. Нет NULL overhead.
8.0 MBdef_level отсутствует (required). 1M × 8 bytes = 8 MB data.
8.0 MBPRESENT stream отсутствует (NOT NULL). 1M × 8 bytes = 8 MB data.
8.0 MBvalidity buffer = null (null_count=0). 1M × 8 bytes = 8 MB.
9.0 MBUnion index: 1 byte per value = 1 MB overhead даже без NULL. 1M × (1 + 8) = 9 MB.
10% NULL100K NULL, 900K non-null values.
7.3 MBdef_level: ~125 KB (RLE-compressed, mostly 1s). Data: 900K × 8 = 7.2 MB. Total: ~7.3 MB.
7.3 MBPRESENT: ~15 KB (Byte RLE, 90% = 0xFF). Data: 900K × 8 = 7.2 MB. Total: ~7.3 MB.
8.1 MBvalidity: 125 KB. values: 1M × 8 = 8 MB (включая undefined на NULL-позициях). Total: 8.125 MB.
8.2 MBUnion: 1 MB. Data: 900K × 8 = 7.2 MB. Total: 8.2 MB.
50% NULL500K NULL, 500K non-null values. Серьёзная экономия на sparse storage.
4.1 MBdef_level: ~125 KB (RLE, 50/50 — similar to random boolean). Data: 500K × 8 = 4 MB. Total: ~4.1 MB.
4.1 MBPRESENT: ~140 KB (Byte RLE, random pattern). Data: 500K × 8 = 4 MB. Total: ~4.1 MB.
8.1 MBvalidity: 125 KB. values: 1M × 8 = 8 MB. Arrow НЕ экономит на NULL — все позиции заняты. 2x vs Parquet/ORC.
5.5 MBUnion: 1 MB. Data: 500K × 8 = 4 MB. Total: 5.0 MB. Union overhead хуже bitmap.
90% NULL900K NULL, 100K non-null. Sparse колонка — big win для skip-based storage.
0.8 MBdef_level: ~15 KB (RLE, mostly 0s — длинные runs). Data: 100K × 8 = 0.8 MB. Total: ~0.8 MB.
0.8 MBPRESENT: ~4 KB (Byte RLE, mostly 0x00 — длинные runs). Data: 100K × 8 = 0.8 MB. Total: ~0.8 MB.
8.1 MBvalidity: 125 KB. values: 1M × 8 = 8 MB. Arrow тратит 10x больше, чем Parquet/ORC на 90%-null колонку.
1.8 MBUnion: 1 MB. Data: 100K × 8 = 0.8 MB. Total: 1.8 MB. Union overhead > bitmap overhead.
WARNING
При 90% NULL: Parquet/ORC хранят 0.8 MB, Arrow — 8.1 MB (10x разница). Для sparse колонок (sensor data с частыми пропусками, optional fields в wide tables) это определяет выбор формата для long-term storage. Arrow оптимизирован для in-memory compute (O(1) access), не для storage efficiency.
Nested Data: Dremel vs Recursive Streams
Вложенные данные — самая сложная часть кодирования. Рассмотрим структуру:
message User {
required string name;
optional group address {
required string city;
optional string zip;
}
repeated group phones {
required string number;
optional string label;
}
}Parquet: Dremel Definition/Repetition Levels
Parquet использует Dremel-алгоритм (Google, 2010), детально разобранный в Модуле 02, Урок 06. Ключевая идея: два дополнительных массива на каждую leaf-колонку — definition level и repetition level:
Definition Level (def)Число от 0 до max_definition_level. Показывает, на каком уровне вложенности значение определено. Для phones.label: def=0 → user=null (невозможно для required), def=1 → address=null, def=2 → phones=null (пустой repeated), def=3 → phones[i] есть, но label=null, def=4 → label есть. Чем выше def — тем глубже определено.
Repetition Level (rep)Число от 0 до max_repetition_level. Показывает, на каком уровне начинается новое повторение. rep=0 → новая запись (User). rep=1 → новый элемент в phones (тот же User). Для плоских (non-repeated) полей: rep всегда 0 — поле не хранится.
Пример: phones.labelUser 0: phones=[{number:'+49',label:'work'}, {number:'+1',label:null}]. User 1: phones=[]. User 2: phones=[{number:'+7',label:'home'}].
ORC: Recursive PRESENT + LENGTH Streams
ORC использует другой подход — рекурсивные потоки без глобальных levels:
STRUCT (optional address)
address PRESENTBitmap для struct-уровня: есть ли address вообще. [1, 0, 1] = User 0 и 2 имеют address, User 1 — нет.
city DATAТолько для записей, где address PRESENT=1. City всегда required внутри address — нет своего PRESENT.
zip PRESENT + DATAzip — optional внутри address. Свой PRESENT bitmap (относительно address, не top-level). Если address=null, zip просто пропускается.
LIST (repeated phones)
phones LENGTHКоличество элементов в каждом phones list. [2, 0, 1] = User 0 имеет 2 телефона, User 1 — 0, User 2 — 1. Кодируется RLEv2.
number DATAFlat array всех phone numbers. Количество определяется суммой LENGTH: 2+0+1 = 3 значения.
label PRESENT + DATAlabel — optional внутри phone. PRESENT bitmap для 3 phone элементов (не 3 users). [1, 0, 1] = first и third phones имеют label.
Dremel vs Recursive: сравнение
Аспект кодирования вложенных данных
Parquet (Dremel)Definition levels + Repetition levels per leaf column
ORC (Recursive)PRESENT + LENGTH streams per nested node
Metadata per valueСколько дополнительной информации хранится на каждое значение
def + rep integersДва integer на значение (плюс для пустых/null — виртуальные записи). Bit-width = ceil(log₂(max_level+1)). Для глубины 3: 2 бита def + 2 бита rep = 4 бита.
1 bit per nullable nodePRESENT bitmap на каждом nullable-уровне. LENGTH integer на каждом list-уровне. Для struct: 1 бит. Для list: 1 integer (кол-во элементов).
Глубокая вложенностьПоведение при глубине вложенности 5+
def/rep растут линейноmax_def = число optional/repeated полей на пути от root до leaf. Глубина 10: def ∈ [0..10] → 4 бита. Но: одна пара (def, rep) на leaf — не на уровень.
Streams растут линейноКаждый nullable уровень добавляет PRESENT stream. Каждый list добавляет LENGTH stream. Глубина 10: 10 PRESENT + N LENGTH streams. Больше I/O.
Пустые listsКак кодируется пустой repeated group (phones = [])
Виртуальная записьDremel создаёт 'виртуальную' запись с def < max и rep = 0. Пустой list = одна запись в leaf column. Overhead: 1 entry per empty list.
LENGTH = 0Просто LENGTH[i] = 0. Нет phantom записей. Дочерние streams не затронуты. Более компактно для sparse lists.
РеконструкцияСложность сборки вложенной структуры обратно
FSM из def/repDremel Assembly Algorithm: конечный автомат, управляемый (def, rep). Компактный, но неинтуитивный. Ошибки реализации — частая причина багов в Parquet-ридерах.
Рекурсивный scanИтерация по LENGTH → для каждого элемента → PRESENT → DATA. Рекурсивно для вложенных уровней. Проще для понимания, но больше random I/O.
Predicate pushdownВозможность фильтрации без полной десериализации
ОграниченPredicate на leaf-уровне: нужно декодировать def/rep, чтобы определить, какие значения к каким записям относятся. Можно пропускать row groups по statistics.
Per-levelМожно проверить PRESENT на высшем уровне и пропустить дочерние streams для NULL-записей. Более гранулярный skip.
Arrow: Nested через Buffer Architecture
Arrow представляет вложенные данные через composition of array types — каждый уровень имеет свои буферы:
ListArray (phones)ListArray: validity buffer (is list present?) + offsets buffer (int32/int64, start/end index в child array) + child array (StructArray of phone records). Offsets: [0, 2, 2, 3] = User 0 has items [0,2), User 1 has [2,2) = empty, User 2 has [2,3).
StructArray (phone record)StructArray: validity buffer + child arrays for each field. 3 records (flat, из offsets ListArray). Validity: [1,1,1] = все 3 phone records valid.
StringArray (label)StringArray: validity buffer + offsets + data buffer. validity: [1, 0, 1] = phone 0 has label, phone 1 no label, phone 2 has label. Data: 'workhome'. offsets: [0, 4, 4, 8].
Преимущество Arrow: каждый уровень — самостоятельный array с O(1) random access через offsets. Нет FSM для реконструкции, нет recursive stream scan. Но: больше буферов, больше allocations, и validity bitmaps на каждом уровне (даже если NULL нет).
Ключевые выводы
- Boolean encoding — RLE оптимален для skewed данных (95/5), uncompressed bitmap — для random. Arrow bitmap проигрывает 6–10x на skewed, но оптимален на random (нет header overhead).
- Parquet/ORC хранят только non-null data (sparse) — экономия пропорциональна % NULL. Arrow хранит все позиции (dense) — O(1) access, но 10x overhead на 90%-null колонках.
- Avro union для nullable — 1 byte per value (union discriminator), хуже bitmap по overhead, но проще для streaming decode.
- Dremel (Parquet) кодирует всю вложенность в два integer-массива per leaf: компактно для глубокой вложенности, но сложный FSM для реконструкции. Phantom entries для пустых lists.
- ORC recursive streams — отдельный PRESENT + LENGTH на каждом уровне. Проще для понимания, гранулярный skip по PRESENT, но больше I/O-потоков при глубокой вложенности.
- Arrow nested = composition of typed arrays — каждый уровень самостоятелен с O(1) access. Максимальная скорость compute, но максимальный overhead на storage.