BtrBlocks: каскадное кодирование
В Модуле 08, Урок 06 мы увидели, как разные системы выбирают кодировки: Parquet — probe-and-fallback, ORC — statistics-driven, DuckDB — sample-based. Каждая из них выбирает одну кодировку на блок.
BtrBlocks (SIGMOD 2023, Kuschewski, Sauerwein, Alhomssi, Leis — TU Munich) задаёт вопрос: а что если применить несколько кодировок подряд? Выход одной кодировки становится входом другой — каскад. Dictionary сначала заменяет строки на индексы, затем FOR сжимает индексы, затем BitPacking упаковывает результат. Каждый уровень каскада добавляет сжатие, потому что работает с данными, уже упрощёнными предыдущим уровнем.
Идея: sampling + cascade
Вместо выбора одной “лучшей” кодировки BtrBlocks:
- Берёт sample (1–5%) данных из блока
- Пробует каждую из 8 кодировок на sample
- Выбирает лучшую → применяет к полным данным
- На выход первой кодировки — снова пробует все кодировки из пула
- Повторяет, пока cascade не перестаёт улучшать ratio
Блок: 65K строк, 12 unique departments
Блок данных: 65 536 строковых значений (department names). Кардинальность: 12 уникальных значений. Распределение: 'Engineering' = 40%, 'Sales' = 20%, остальные 10 отделов по 4%.Sample 1–5% → evaluate 8 candidates
Level 0: evaluate на sampleBtrBlocks берёт ~1000 случайных значений и пробует все 8 кодировок. Результаты: OneValue — не подходит (12 unique). Dictionary — подходит (12 unique → 4-bit indices). RLE — средне (runs короткие, данные не sorted). FSST — подходит (строки ~10 символов). Frequency — подходит (2 значения = 60%). Победитель: Dictionary (наибольшее сжатие на sample).
Победитель Level 0: Dictionary
Level 0 → Dictionary: строки → индексы 0–11Dictionary encoding: 12 строк в словарь (суммарно ~120 байт). 65K значений → 65K индексов 0–11. Каждый индекс — 4 бита (ceil(log₂(12)) = 4). Но BtrBlocks пока НЕ пакует биты — он передаёт массив integer индексов [0–11] на следующий уровень cascade.
Выход Dictionary → вход для Level 1
Level 1: evaluate индексы [0–11] на sampleТеперь данные — массив integers 0–11. Пробуем снова: OneValue: − (12 unique). FOR: 1/5 (range 0–11, base=0, 4 bits). RLE: ~ (короткие runs). Dictionary на integers: бесполезно (уже indices). Победитель: FOR (base=0, offset width=4 bits).
Победитель Level 1: FOR
Level 1 → FOR: indices → base + 4-bit offsetsFOR encoding: base = 0 (min), max offset = 11. Bit width = 4. 65K × 4 bits = 32.5 KB. Это уже packed данные — дальнейший cascade не улучшит (bit-packed integers = максимальная плотность для этих данных).
Level 2: evaluate → no improvement → stop
Chain: Dictionary → FOR. Total: ~33 KB. Ratio: ~23.6x
Финальная chain: Dictionary → FOR. Размер: 32.5 KB (offsets) + 120 B (dictionary) + metadata ≈ 33 KB. Original: 65K × ~12 bytes = ~780 KB. Ratio: 780/33 ≈ 23.6x. Для сравнения: single Dictionary без cascade = 65K × 4 bits = 32.5 KB (то же самое — FOR не добавил в этом случае, потому что indices уже компактны). Cascade выигрывает на более сложных данных.Когда cascade реально помогает
Cascade даёт выигрыш, когда выход первой кодировки имеет другую структуру, чем вход:
ДанныеТип входных данных
Single encodingЛучшая одиночная кодировка
Cascade chainЦепочка кодировок BtrBlocks
ВыигрышДополнительное сжатие от cascade
Low-card strings (sorted)Строки с низкой кардинальностью, отсортированные. Runs длинные.
Dictionary: 20xDictionary сжимает хорошо. Но indices — sorted integers с длинными runs (0,0,0,...,1,1,1,...). RLE на indices ещё лучше.
Dict → RLE → FOR: 50xDictionary: strings → indices. RLE: sorted indices с runs → (value, run_length) pairs. FOR: run_lengths в узком диапазоне → packed. Трёхуровневый cascade.
+2.5xCascade добавил 2.5x сверху. RLE на sorted dictionary indices — паттерн, который single encoding не ловит.
Float monetary ($3.25)Doubles, которые на самом деле decimal: $3.25 = 3.25 (double). Типичные 2 десятичных знака.
Uncompressed: 1xДля doubles единственная стандартная опция — не кодировать (или BYTE_STREAM_SPLIT). Dictionary бесполезен при high cardinality prices.
Pseudodecimal → FOR: 8xPseudodecimal: $3.25 (8 bytes double) → 325 (2 bytes integer) + exponent 2. FOR: integers 325 в narrow range → bit-packed. 8 bytes → 1 byte.
+8xБез Pseudodecimal — doubles несжимаемы (high entropy). С Pseudodecimal — трансформация в integers, дальше стандартные integer encodings.
Zipf-distributed integersIntegers с power-law распределением: 10 значений = 90% данных, длинный хвост. Типично для user_id, product_id.
Dictionary: 5xDictionary: все 10K unique → 14-bit indices. Высокая кардинальность → большой словарь.
Freq → Dict → FOR: 12xFrequency: top-10 значений (90% данных) → 4-bit codes. Остальные → exception list. Dict на exceptions (10K unique in 10% data). FOR на Frequency output.
+2.4xFrequency encoding выделяет hot values в compact representation. Остальное — в exception list с собственной кодировкой. Двухуровневая стратегия.
NOTE
Cascade не всегда улучшает результат. На данных с максимальной энтропией (random bytes, encrypted) или уже оптимально закодированных (constant column) — cascade останавливается на Level 0. Стоимость cascade: O(sample_size × pool_size × levels) — но sample маленький (1–5%), pool фиксирован (8), levels обычно 2–3.
Пул кодировок: 8 encodings
BtrBlocks использует фиксированный пул из 8 кодировок. Каждая имеет свою роль в cascade:
EncodingКодировка из пула BtrBlocks
ТрансформацияЧто кодировка делает с данными
Типы данныхК каким типам применяется
Cascade рольГде в cascade эта кодировка обычно стоит
Выход → следующий уровеньЧто получается на выходе и может ли быть входом для следующего уровня
UncompressedДанные записываются как есть. Raw bytes. Baseline для cascade evaluation. Используется, когда ни одна кодировка не сжимает лучше, чем raw.
Passthrough (без изменений)Нет трансформации. Данные копируются 1:1. Overhead: только block header (~8 bytes).
ВсеПрименяется к любым данным — это fallback.
Terminal (fallback)Всегда последний вариант. Если cascade дошёл до Uncompressed — дальше каскадировать нечего.
Raw bytes → cascade stopВыход = вход. Cascade останавливается.
OneValueВсе значения в блоке одинаковы. Хранится 1 значение + count. 0 бит на данные. Аналог DuckDB Constant.
N × value → 1 × value + countОдин экземпляр значения + количество. Для блока из 65K одинаковых: 65K × 8 bytes → 8 bytes + 4 bytes = 12 bytes. Ratio: ~43000x.
ВсеРаботает для любого типа: int, string, double. Проверка: all_same(block).
TerminalЕсли все одинаково — лучше не бывает. Cascade не нужен.
12 bytes → cascade stopМинимальный возможный размер. Дальше сжимать нечего.
DictionaryСтроит словарь уникальных значений. Заменяет каждое значение на integer index. Словарь хранится отдельно.
values → dict + int indicesВход: N values с K unique. Выход: K-entry dictionary + N integer indices [0..K-1]. Индексы — integers, которые можно каскадировать.
ВсеДля strings: основная кодировка при low/medium cardinality. Для integers: если есть повторы. Для doubles: если discrete values.
First (обычно)Типичный первый шаг cascade. Выход (integer indices) подаётся на FOR, RLE, или BitPacking.
int[] → FOR / RLE / BPМассив integer индексов: идеальный вход для FOR (narrow range), RLE (sorted data), BitPacking.
RLERun-Length Encoding: серии одинаковых значений → (value, run_length) пары. Эффективно для sorted или clustered данных.
runs → (val, len) pairsСерия [A,A,A,B,B] → [(A,3), (B,2)]. Два массива: values и lengths. Оба — integers, оба каскадируемы.
int, strДля integers: sorted данные. Для строк: sorted или clustered. Для doubles: редко (continuous values = no runs).
First / InnerПервый шаг на sorted данных. Inner: RLE на dictionary indices (если indices имеют runs после sort).
values[] + lengths[] → FOR eachДва массива integers. Каждый каскадируется отдельно: FOR на values, FOR на lengths.
FrequencyУникальная BtrBlocks кодировка. Выделяет TOP-K частых значений. Hot values кодируются компактно. Cold values — в exception list с собственной кодировкой.
hot top-K compact + cold exceptionsTop-K значений: bitmap + K-way code (ceil(log₂(K)) бит). Exceptions: позиции + значения в отдельном блоке. Для zipf-distributed данных: 90% данных в K bits, 10% в exception list.
int, strДля integers с power-law: user_ids, product_ids. Для строк: URLs с популярными доменами. Не для doubles (continuous = no hot values).
FirstВсегда первый шаг: разделить горячие и холодные данные. Холодные — каскадируются отдельно.
codes[] + exceptions[] → cascade eachДва потока: hot codes (small integers → FOR/BP) и cold exceptions (каскад по типу данных).
FORFrame-of-Reference: base + offsets. Вычитает минимум из каждого значения. Offsets в узком диапазоне → меньше бит.
values → base + narrow offsetsbase = min(block). offsets = values - base. Bit width = ceil(log₂(max_offset + 1)). Автоматически pack в минимальное число бит.
intТолько integers. FOR не работает для строк или doubles (нет определённой 'base' для arbitrary bytes).
Inner / TerminalОбычно второй шаг: на dictionary indices, на RLE lengths, на Frequency codes. Выход — bit-packed, дальше каскад не нужен.
packed bits → cascade stop (usually)Bit-packed данные — уже оптимальная плотность для integers в fixed range. Дальнейший cascade не улучшает.
PseudodecimalУникальная BtrBlocks кодировка для doubles, которые на самом деле decimal. Определяет: можно ли double представить как integer × 10^(-n)? Если да — хранить integer + exponent.
double → integer × 10^(-n)$3.25 (double, 8 bytes) → 325 (integer, 2 bytes) + exponent 2 (shared per block). Проверка: round(value × 10^n) == value × 10^n для n=0,1,2,...,18. Если да — lossless conversion.
doubleТолько doubles. Ключевое наблюдение: значительная доля 'float' колонок в production — на самом деле decimal ($3.25, 20.5°C, 99.99). Pseudodecimal ловит этот паттерн.
First (doubles)Первый шаг для doubles. Трансформирует doubles в integers — после чего доступен весь integer cascade pool (Dict, FOR, RLE).
int[] → Dict / FOR / RLE cascadeВыход: массив integers. Передаётся на Level 1 как integer данные. Вся мощь integer cascading теперь доступна для бывших doubles.
FSSTFast Static Symbol Table — string compression. Строит таблицу 256 символов (1–8 байт каждый) из training sample. Каждая строка: замена частых подстрок на 1-byte коды. Подробно в Уроке 06 этого модуля.
strings → 1-byte symbol codesSymbol table: 256 entries × 1–8 bytes. Каждая строка сканируется слева направо: если подстрока совпадает с символом — заменяется на 1-byte код. ~3x compression на text.
stringТолько строки. Для high-cardinality длинных строк, где Dictionary бесполезен. URLs, JSON, log messages.
Terminal (strings)Выход — compressed bytes. Дальнейший cascade на byte stream обычно не даёт улучшения (данные уже компактны).
compressed bytes → cascade stopFSST выход: byte stream с ~3x compression. Дополнительное кодирование не помогает — нет структуры для integer encodings.
Pseudodecimal Encoding: инновация для doubles
Pseudodecimal — наиболее неожиданная кодировка в пуле BtrBlocks. Наблюдение авторов: значительная часть double-колонок в реальных данных — это decimal числа (цены, проценты, температуры), хранимые как IEEE 754 double из-за отсутствия native decimal типа в большинстве систем.
Колонка: [3.25, 10.99, 7.50, 99.95, …] (double, 8 bytes each)
Колонка цен: $3.25, $10.99, $7.50, $99.95, ... Хранится как double (8 bytes each). IEEE 754: 3.25 = 0x4008000000000000. Высокая entropy — integer encodings не работают напрямую.Шаг 1: определить exponent
Проверка: round(value × 10^n) == value × 10^n ?Для n = 0, 1, 2, ..., 18: проверить, можно ли value точно представить как integer × 10^(-n). Для 3.25: n=2 → 3.25 × 100 = 325.0 → round(325.0) = 325 → 325.0 == 325.0 +. Exponent = 2. Для всего блока: найти минимальный n, работающий для ВСЕХ значений.
Шаг 2: convert double → integer
Трансформация: int_value = round(double_value × 10^n)Каждый double → integer. Трансформация lossless (проверено на шаге 1). Размер integer зависит от range: prices $0.01–$999.99 → integers 1–99999 → 17 бит. Вместо 64 бит (double) → 17 бит (integer).
Шаг 3: cascade integer encodings
Integer cascade: FOR → BitPackingТеперь массив integers [325, 1099, 750, 9995, ...]. FOR: base = 1 (min price $0.01), offsets = [324, 1098, 749, 9994, ...]. Bit width = ceil(log₂(99999)) = 17 бит. 65K × 17 bits = 138 KB. Для сравнения: original doubles = 65K × 8 bytes = 520 KB.
Результат: 520 KB → 138 KB. Ratio: 3.8x (vs ~1.0x без Pseudodecimal)
Финальный результат: 65K × 17 bits = 138 KB + metadata (exponent=2, base=1, dict=none). Original: 65K × 64 bits = 520 KB. Ratio: 3.8x. Без Pseudodecimal: ratio ~1.0x (doubles несжимаемы стандартными integer encodings). Cascade chain: Pseudodecimal → FOR → BitPacking.Pseudodecimal vs ALP
АспектСравнение двух подходов к компрессии float-as-double
Pseudodecimal (BtrBlocks, 2023)BtrBlocks SIGMOD 2023: Pseudodecimal Encoding в cascade framework
ALP (DuckDB, 2024)ALP (Adaptive Lossless Floating-Point): SIGMOD 2024, интегрирован в DuckDB
ИдеяОсновная идея кодировки
double → integer × 10^(-n)Умножить на 10^n, округлить — если совпадает, хранить integer. Один exponent на блок.
double → integer × 10^(-n) + exception handlingТо же умножение, но с двумя режимами: (1) decimal floats → integer, (2) high-precision → left-part dictionary. Обработка exceptions встроена.
ExceptionsЧто делать с doubles, которые не конвертируются в integer
Весь блок fallbackЕсли не все значения в блоке convertible — Pseudodecimal не применяется к блоку. Fallback на Uncompressed. Не может обработать mix decimal/non-decimal.
Per-value exception listALP кодирует конвертируемые значения как integers, не-конвертируемые — в exception list. Работает даже если 10% значений — outliers (NaN, Inf, high-precision).
High-precision floatsDoubles с 15+ значащих цифр (scientific data)
Не поддерживаетPseudodecimal работает только для decimal doubles (1–18 знаков после запятой). Scientific doubles (π = 3.141592653589793) → не конвертируются → Uncompressed.
Mode 2: left-part dictionaryALP Mode 2: для high-precision floats. Разбивает double на left-part + right-part. Left-part (exponent + high mantissa bits) кодируется dictionary. Right-part — bit-packed. Работает для любых doubles.
ИнтеграцияГде используется
BtrBlocks (research prototype)Часть BtrBlocks cascade framework. C++ prototype на GitHub. Не интегрирован в production системы.
DuckDB (production)Интегрирован в DuckDB storage engine. Используется для всех float/double колонок в .duckdb файлах. Production-grade.
ВлияниеИсторическое значение
Предшественник ALPPseudodecimal (2023) — первая публикация идеи 'decimal floats → integers'. ALP (2024) — развитие идеи с exception handling и Mode 2 для non-decimal floats.
Развитие Pseudodecimal + новые режимыALP цитирует BtrBlocks. Авторы (Afroozeh, Boncz — CWI) добавили exception handling и high-precision mode. Результат: ALP работает для ВСЕХ doubles, не только decimal.
TIP
Pseudodecimal в BtrBlocks и ALP в DuckDB — это одна и та же идея (decimal floats → integers) с разным уровнем зрелости. BtrBlocks первым опубликовал (SIGMOD 2023). ALP (SIGMOD 2024) добавил exception handling и second mode для non-decimal floats, и интегрирован в production DuckDB. Подробно ALP рассмотрим в Уроке 05.
Evaluation: Public BI Benchmark
BtrBlocks оценивался на Public BI Benchmark — коллекции реальных бизнес-данных из Tableau Public (73 таблицы, 5.7 млрд строк, ~860 GB raw):
ФорматФормат хранения и алгоритм компрессии
Compression Ratio (vs raw)Во сколько раз меньше raw данных. Больше = лучше.
Decompress SpeedСкорость декомпрессии (GB/s). Больше = лучше.
Ключевое преимуществоПочему такой результат
Parquet + SnappyApache Parquet с Snappy compression. Default для многих Spark deployments.
3.6x3.6x сжатие. Dictionary encoding + Snappy. Хороший baseline.
~1.5 GB/sSnappy декомпрессия быстрая. Bottleneck: dictionary decoding для строк.
Широко поддерживается, fast decodeParquet + Snappy — industry default. Поддерживается всеми движками.
Parquet + ZstdApache Parquet с Zstd compression. Лучше сжатие, чем Snappy.
5.5x5.5x сжатие. Dictionary + Zstd (ANS phase добавляет ~40% сверх Snappy).
~1.0 GB/sZstd декомпрессия медленнее Snappy, но всё ещё быстрая.
Лучше ratio за счёт ANSZstd ANS фаза сжимает выход LZ77 эффективнее, чем чистый LZ77 Snappy.
BtrBlocksBtrBlocks cascade encoding framework. Без внешней компрессии (LZ77/Zstd) — только lightweight encodings.
7.5x7.5x сжатие — лучше, чем Parquet+Zstd. За счёт: cascade encodings (Dict→FOR→BP), Pseudodecimal для doubles, Frequency для zipf-данных, FSST для строк.
~2.0 GB/sБыстрее Parquet+Snappy! Lightweight encodings (bit operations, memcpy) быстрее LZ77 (hash table lookups). No general-purpose compression overhead.
Cascade + type-aware encodingsBtrBlocks использует знание о типах данных (Pseudodecimal для doubles, FSST для строк) + cascade. Parquet применяет generic LZ77/Zstd ко всем типам одинаково.
Почему BtrBlocks выигрывает
Причина 1: type-aware encoding poolBtrBlocks знает тип данных и применяет type-specific кодировки. Pseudodecimal для doubles, FSST для строк, Frequency для zipf. Zstd/Snappy не знают тип — они видят только байты.
Причина 2: cascade вместо single encodingSingle encoding (Dict OR FOR OR RLE) выбирает одну трансформацию. Cascade (Dict → FOR → BP) применяет последовательность, каждая из которых сжимает то, что предыдущая не могла.
Причина 3: lightweight decode = fasterBtrBlocks decode: bit operations + memcpy + simple arithmetic. Нет LZ77 (hash table, sliding window). Нет ANS (state machine, table lookups). Lightweight operations = better CPU cache utilization = higher throughput.
WARNING
BtrBlocks — исследовательский прототип, не production-ready формат. Нет экосистемы (Spark, Trino, DuckDB не читают BtrBlocks файлы), нет спецификации формата, нет governance. Ценность BtrBlocks — идеи: cascade encoding и Pseudodecimal уже влияют на DuckDB (ALP), и могут повлиять на будущие версии Parquet. GitHub: maxi-k/btrblocks, C++, MIT license.
BtrBlocks: архитектура формата
BtrBlocks File
BtrBlocks файл: columnar layout. Данные разбиты на блоки (chunks) по ~65K значений на колонку. Каждый chunk — независимая единица cascade encoding.File HeaderMetadata: количество колонок, типы, количество chunks, offsets к каждому chunk. Позволяет random access к любому chunk без чтения остальных.
Column 0, Chunk 0Один chunk одной колонки. Header: cascade chain descriptor (e.g., Dict→FOR). Body: encoded data. Footer: dictionary (если используется). Каждый chunk полностью самодостаточен — декодируется независимо.
Column 0, Chunk 1Другой chunk той же колонки. Может иметь ДРУГУЮ cascade chain — данные изменились. Пример: Chunk 0 = Dict→FOR (low cardinality region), Chunk 1 = FSST (high cardinality region).
Decode: chain в обратном порядке. Per-chunk parallel.
Decode: прочитать chain descriptor → применить decode в обратном порядке. Dict→FOR: un-FOR (add base to offsets) → un-Dictionary (lookup indices in dict). Per-chunk decode: полная параллелизация.Ключевые выводы
- BtrBlocks (SIGMOD 2023, TU Munich) — cascade encoding framework: выход одной кодировки → вход другой. 2–3 уровня cascade.
- Sampling-based selection: 1–5% sample → evaluate все 8 кодировок → лучшая → cascade → repeat. Быстро (sample маленький), эффективно (пробует все варианты).
- Пул из 8 кодировок: Uncompressed, OneValue, Dictionary, RLE, Frequency, Pseudodecimal, FOR, FSST. Каждая имеет роль в cascade (first / inner / terminal).
- Pseudodecimal Encoding: doubles с decimal значениями ($3.25) → integers (325). Делает doubles доступными для integer cascade. Предшественник ALP (SIGMOD 2024).
- Результаты: 7.5x compression (vs Parquet+Zstd 5.5x) при 2.0 GB/s decode (vs 1.0 GB/s). Лучше сжимает и быстрее декодирует.
- Причина: type-aware encodings + cascade + lightweight decode (bit operations вместо LZ77/ANS). Знание типа данных > brute-force general-purpose compression.
- Статус: research prototype (C++, MIT license). Идеи влияют на DuckDB (ALP, FSST). Не production format.