Learning Platform
Глоссарий Troubleshooting
Урок 10.07 · 30 мин
Продвинутый
Compressed ExecutionPartial DecompressionAnyBloxWebAssemblyLearned EncodingsGPU DecompressionFuture of Encoding

Будущее кодирования: compressed execution и AnyBlox

В предыдущих четырёх уроках мы разобрали cutting-edge кодировки: BtrBlocks (каскады), FastLanes (SIMD-layout), ALP (float→integer), FSST (символьные таблицы). Каждая из них улучшает сжатие — но все предполагают, что данные нужно декомпрессировать перед обработкой.

Этот урок — о следующем шаге: что если вообще не декомпрессировать?

Compressed Execution: работа на сжатых данных

Традиционный pipeline аналитического запроса: читаем сжатые данные с диска → декомпрессируем в память → обрабатываем (filter, aggregate, join) → возвращаем результат. Декомпрессия — обязательный шаг, и он стоит CPU-циклов.

Compressed execution пропускает декомпрессию: операции выполняются прямо на сжатых данных. Не все операции и не на всех кодировках — но для определённых комбинаций это работает.

Traditional vs Compressed Execution pipeline
Traditional pipelineКлассический путь: все данные декомпрессируются перед обработкой. Стоимость: memory bandwidth (сжатые данные расширяются в 3–10x), CPU на декомпрессию, и cache pollution (декомпрессированные данные вытесняют другие данные из L2/L3 cache).

Обрабатываем 100% данных в full size

Каждый шаг pipeline работает с полноразмерными данными. Если колонка сжата 5x — pipeline обрабатывает 5x больше байтов, чем необходимо. Memory-bandwidth bound на modern hardware.
Compressed executionCompressed execution: filter и часть aggregate работают на сжатых данных. Декомпрессия только для финального результата (обычно < 1% строк после фильтрации). Экономия: меньше memory bandwidth, меньше cache pressure, меньше CPU на декомпрессию.

Декомпрессируем только matches (~1%)

Filter работает на сжатых данных → отсеивает 99% строк → декомпрессируем только 1%. Экономия: 99% декомпрессии пропущено.

DuckDB: три типа compressed vectors

DuckDB реализует compressed execution для трёх типов кодировок:

DuckDB compressed vectors: Constant, Dictionary, FSST
Тип вектораТип сжатого вектора в DuckDB
Что хранитсяВнутреннее представление
Операции без декомпрессииКакие операции работают на сжатых данных
ЭкономияВыигрыш от compressed execution
Constant vectorConstant vector: весь столбец (или chunk) содержит одно значение. Хранится одно значение + count. Типично для: partition columns (year=2024), default values, COUNT(*) результаты.
1 значение + countВместо 1024 копий значения '2024' — одно значение и число повторений.
Filter: O(1). Aggregate: O(1). Join: broadcastWHERE year = 2024: сравнение одного значения = O(1). SUM(constant * N) = constant × count. JOIN: constant broadcast — не нужно hash 1024 одинаковых значений.
1024x меньше работыВместо обработки 1024 значений — обработка 1. Линейная экономия по размеру chunk.
Dictionary vectorDictionary vector: массив indices → dictionary. Indices: 1024 × 2 байта. Dictionary: 50 уникальных значений. Операции на indices дешевле, чем на full values.
indices[] + dict[]1024 целочисленных indices + компактный dictionary (50–500 уникальных значений).
Filter: compare indices. GROUP BY: dict-level aggWHERE status = 'active': найти index 'active' в dict (O(dict_size)), затем scan indices на match (integer compare, не string compare). GROUP BY status: 50 dict entries → 50 groups, aggregate по indices без decode строк.
String compare → int compareСравнение строк (переменная длина, branch-heavy) заменяется сравнением 2-byte integers (фиксированная длина, SIMD-friendly). На длинных строках — 10–50x ускорение per comparison.
FSST vectorFSST vector: строки сжаты символьной таблицей FSST. Каждая строка — независимый буфер сжатых байтов + symbol table.
compressed strings + symbol tableСжатые строковые буферы + символьная таблица (256 entries, ~1 KB).
Equality: encode constant → memcmp. LIKE: partial decodeWHERE url = 'example.com': encode 'example.com' через ту же symbol table → memcmp сжатых байтов. WHERE url LIKE '%example%': частичное декодирование для pattern match. Обе операции — без полной декомпрессии всех строк.
~3x меньше memory bandwidthСжатые строки в 3x компактнее → 3x меньше данных читается из RAM → 3x меньше memory bandwidth. На memory-bandwidth-bound workloads — прямое ускорение.
NOTE

Compressed execution не универсален: JOIN по Dictionary vectors требует совместимых словарей, LIKE на FSST — частичного декодирования, а математические операции (SUM, AVG) на Constant vectors — специальной логики. DuckDB реализует compressed paths для самых частых операций и fallback на decompress для остальных.

Partial Decompression: декодирование одного значения

FastLanes (Урок 04) открывает другую возможность: partial decompression. Благодаря UTL layout, можно декодировать одно значение из блока в 1024, не трогая остальные 1023.

Partial Decompression: full block vs single value
Full block decompressionКлассический подход: чтобы прочитать value[500] из блока 1024 значений, нужно декомпрессировать все 1024. Причина: в традиционном bit-packing биты value[500] переплетены с битами соседних значений.

Decode 1024 значений ради одного. O(block_size)

Стоимость: O(block_size). Для 1024 × 4-byte values = decode 4 KB, даже если нужно 4 байта.
FastLanes partial decodeFastLanes UTL: биты value[500] находятся в конкретном lane (определяется UTL permutation). Чтобы decode value[500]: (1) определить lane, (2) прочитать только биты этого lane, (3) unpack одно значение. Остальные 1023 значения — не тронуты.

Decode 1 значение. O(1)

Стоимость: O(1). Один lane lookup + один bit-unpack. Полезно для: point queries (WHERE id = 500), index lookups, late materialization (декодируем только колонки, которые прошли filter).

Partial decompression полезна для late materialization: сначала filter на сжатых данных → получаем позиции match’ей → декодируем только нужные значения из нужных колонок. Комбинация compressed execution (filter без decode) + partial decompression (decode только matches) минимизирует объём декомпрессии.

AnyBlox: WebAssembly-декодеры внутри данных

Все форматы (Parquet, ORC, Arrow) имеют одну проблему: формат задаёт набор кодировок. Parquet поддерживает PLAIN, RLE_DICTIONARY, DELTA_BINARY_PACKED и ещё 6 типов — и всё. Новая кодировка (например, ALP) требует изменения спецификации, обновления всех reader-библиотек (pyarrow, spark, polars, duckdb, …), и ожидания adoption. Процесс занимает годы.

AnyBlox предлагает радикальное решение: вместо фиксированного набора кодировок — положить декодер рядом с данными.

AnyBlox: архитектура — данные + WebAssembly декодер

Проблема: writer знает ALP, reader не знает ALP → data unreadable

Традиционная проблема: writer хочет использовать новую кодировку (ALP, FSST, FastLanes cascade). Но reader не поддерживает её — data loss. Format version lock-in.
Решение AnyBlox
Data blockСжатые данные — закодированные любой кодировкой. ALP, FSST, FastLanes, кастомная proprietary кодировка, экспериментальная learned encoding. Формат данных — произвольный.
Wasm decoderWebAssembly модуль: скомпилированный декодер для этой конкретной кодировки. ~10–100 KB. Sandboxed execution: Wasm не может обратиться к файловой системе, сети, или памяти за пределами своего буфера. Reader загружает Wasm модуль, передаёт блок данных, получает декодированные значения.
Reader: любой, без обновления
AnyBlox Reader (generic)Reader не знает, какая кодировка использована. Он знает только: (1) загрузить Wasm модуль из файла, (2) передать data block в Wasm, (3) получить decoded values. Один generic reader — для ВСЕХ кодировок, существующих и будущих. Reader не обновляется при появлении новой кодировки.

Writer: любая кодировка. Reader: всегда прочитает.

Результат: формат данных отвязан от набора кодировок. Writer может использовать ЛЮБУЮ кодировку — experimental, proprietary, bleeding-edge — и reader всегда прочитает, потому что декодер поставляется вместе с данными.

Почему WebAssembly?

Почему именно WebAssembly для AnyBlox
ТребованиеЧто нужно от формата декодера
АльтернативыДругие подходы и почему не подходят
WebAssemblyКак Wasm решает требование
БезопасностьДекодер из неизвестного источника — не должен иметь доступ к системе
Native code (DLL/SO): full system accessShared library (.so/.dll) — полный доступ к ОС. Декодер от злоумышленника = arbitrary code execution. Неприемлемо.
Memory sandbox: линейная память, нет syscallsWasm module видит только свой линейный буфер памяти. Нет доступа к файлам, сети, другим процессам. Sandbox на уровне спецификации — не зависит от ОС.
ПроизводительностьДекодирование на скорости, близкой к native
JIT interpreted (Lua/Python): 10–100x slowdownИнтерпретируемый декодер — слишком медленный для data-intensive workloads. Декомпрессия гигабайтов — нужна native скорость.
AOT/JIT compile: ~0.8–0.95x native speedWasm компилируется в native code через AOT (Ahead-of-Time) или JIT. Wasmtime, Wasmer — production Wasm runtimes. Overhead vs native C: 5–20%.
ПортируемостьДекодер работает на всех платформах без перекомпиляции
Native binary: per-platform buildNative binary (.so) компилируется под конкретную платформу (x86/ARM, Linux/macOS/Windows). Нужно 6+ вариантов.
One .wasm binary → все платформыОдин .wasm файл работает на x86, ARM, RISC-V, в браузере, на сервере, на embedded. Compile once, run anywhere.
WARNING

AnyBlox — исследовательский проект, не production-ready формат. Открытые вопросы: стандартизация metadata (как reader находит Wasm модуль в файле?), доверие к декодерам (Wasm sandbox не предотвращает denial of service — бесконечный цикл), и производительность Wasm для SIMD-intensive декодеров (Wasm SIMD proposal всё ещё созревает).

Направления исследований

Encoding research — одна из самых активных областей в data systems. Несколько направлений:

Куда движутся исследования кодирования
Learned EncodingsИдея: вместо ручного дизайна кодировок — обучить модель (neural network или decision tree) выбирать оптимальную кодировку для конкретных данных. BtrBlocks' sampling — примитивная версия этой идеи (rule-based). Следующий шаг: модель, обученная на тысячах колонок, предсказывающая лучшую chain для unseen данных. Проблема: overhead обучения vs экономия сжатия.
Hardware-Aware CompressionFastLanes уже адаптирует layout под SIMD. Следующий шаг: кодировки, оптимизированные под конкретные hardware features: Intel IAA (In-memory Analytics Accelerator), AMD XDNA, CXL memory pooling. IAA может делать Zstd decode в hardware — нужны форматы, оптимизированные для аппаратных декодеров.
GPU DecompressionG-ALP (DaMoN 2025) — первый шаг: ALP для GPU. Направление: все lightweight encodings (FOR, Delta, BitPack, Dictionary) адаптированы под GPU warp-level parallelism. GPU memory bandwidth (3+ TB/s на H100) >> CPU bandwidth (50–100 GB/s) → decompression на GPU может быть в 30x быстрее. Проблема: data transfer CPU→GPU — PCIe bottleneck.
Format-Independent CompressionAnyBlox + FastLanes Expression Encoding → формат, где кодировки не зашиты в спецификацию. Writer описывает chain (FOR → Delta → BitPack) как expression или поставляет Wasm decoder. Reader — generic. Это противоположность текущей ситуации, где Parquet/ORC фиксируют enum кодировок.

Таймлайн: от классических кодировок к compressed execution

Таймлайн: эволюция encoding research (2010–2025)
2010–2015Эра колоночных форматов. Parquet (2013) и ORC (2013) определяют фиксированные наборы кодировок: Dictionary, RLE, Delta, Plain. Кодировки простые, проверенные, ориентированы на Hadoop MapReduce.
2017–2020FSST (2020): string compression с random access. Byte Stream Split (Parquet 2.8, 2021): первая попытка float-compression в Parquet. DuckDB начинает внедрять lightweight compression в native format.
2021–2023BtrBlocks (SIGMOD 2023): каскадная компрессия, Pseudodecimal. FastLanes (VLDB 2023): SIMD-optimized layout. DuckDB FSST integration (2022, PR #4366). Compressed execution становится практикой.
2024–2025ALP (SIGMOD 2024): float compression через decimal→integer. FastLanes File Format (VLDB 2025): expression encoding, MCC. G-ALP (DaMoN 2025): GPU extension. AnyBlox: WebAssembly decoders.

Итог модуля

Модули 08 и 09 прошли полный путь — от информационной теории и классических кодировок через кросс-форматный анализ до cutting-edge исследований:

  • Encoding ≠ compression: кодирование трансформирует данные (Dictionary, FOR, Delta, FSST, ALP), compression сжимает байты (LZ4, Zstd). Максимальный эффект — кодирование перед компрессией (BtrBlocks cascade).
  • SIMD — бесплатно: FastLanes UTL layout даёт автовекторизацию без платформенных intrinsics. >100 млрд int/sec на scalar коде.
  • Float — сжимаем: ALP превращает «несжимаемые» float64 в integers. 4–8x на финансах/сенсорах.
  • Строки — random access: FSST даёт ~3x без потери random access. Late decompression: предикаты на сжатых строках.
  • Декомпрессия — не обязательна: compressed execution (DuckDB vectors), partial decompression (FastLanes), late decompression (FSST) — три способа обойти полную декомпрессию.
  • Форматы эволюционируют: от фиксированных enum кодировок (Parquet/ORC) к expression encoding (FastLanes FF) и WebAssembly-декодерам (AnyBlox).

Все ключевые техники (FastLanes, ALP, FSST) интегрированы в DuckDB — открытый аналитический движок, ставший playground для encoding research из CWI Amsterdam.

Проверьте понимание

Результат: 0 из 0
Прикладной
Вопрос 1 из 4. DuckDB constant vector: если все 2048 значений в сегменте одинаковы, хранит одно значение + count. Как это взаимодействует с vectorized execution?

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

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

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