ALP: адаптивное сжатие float
В Модуле 08, Урок 03 мы видели, как FOR, Delta и BitPacking сжимают целые числа до 2–4 бит на значение. Но все эти кодировки работают с integers. Что делать с float64? В Модуле 08, Урок 05 мы кратко упомянули BYTE_STREAM_SPLIT (Parquet 2.8) — но он даёт лишь ~1.5–2x на типичных float-данных.
ALP (SIGMOD 2024, Afroozeh, Kuffó & Boncz — CWI Amsterdam) решает проблему радикально: превращает float в integers и сжимает их FastLanes FOR-кодировкой. Звучит как трюк, но за ним стоит наблюдение о реальных данных.
Почему IEEE 754 float так плохо сжимается
Число: 10.12 (double precision, 8 байт)
Пример: число 10.12 в IEEE 754 double precision. Человек видит '10.12' — компьютер хранит 64 бита: sign (1 bit) + exponent (11 bits) + mantissa (52 bits).52 бита мантиссы ≈ random noise → FOR, Delta, Dict бесполезны
Проблема: мантисса занимает 52 из 64 бит и выглядит как noise. FOR/Delta бесполезны — нет паттерна в битах. Dictionary — бесполезен при high cardinality (уникальные значения). RLE — бесполезен (нет повторов). Единственный вариант до ALP: generic byte-level compression (Zstd) или BYTE_STREAM_SPLIT.Проблема — не в float как абстракции, а в IEEE 754 encoding. Число 10.12 — простое для человека, но в binary его мантисса — 52 «случайных» бита, потому что 0.12 не имеет точного двоичного представления.
Наблюдение ALP: большинство float — это decimals
ALP начинается с простого наблюдения: в реальных данных большинство float-значений — это decimal числа, записанные в float по привычке:
Вывод: финансовые, сенсорные и геоданные — это decimal числа, хранимые в float64 «по инерции». Если умножить их на 10^n и округлить — получим integers, которые отлично сжимаются FOR/BitPacking.
ALP Mode A: decimal float → integer → FastLanes FOR
Mode A — основной алгоритм ALP. Применяется, когда float-значения в блоке можно losslessly конвертировать в integers:
Блок: 1024 × float64 цен (10.99, $7.50, …)
Блок float64: 1024 значения цен. $3.25, $10.99, $7.50, $15.00, ... Все — 2 десятичных знака. 8 байт × 1024 = 8 KB несжатых данных.~1.4 KB вместо 8 KB. Ratio: ~5.7x. Decode: integer ops only.
Финальный размер: 1408 (offsets) + 8 (base) + 1 (factor) + 0 (exceptions) = ~1.4 KB. Оригинал: 8 KB. Ratio: 8/1.4 ≈ 5.7x. Для сравнения: Zstd на raw float64 даёт ~2x. ALP: 5.7x — и decode быстрее (integer arithmetic, no entropy decoding).Round-trip гарантия
ALP lossless — ни один бит информации не теряется. Гарантия обеспечивается round-trip проверкой для каждого значения:
encode(val, n):
int_val = round(val × 10^n)
check = int_val × 10^(-n)
if check == val: → store int_val (compressed)
else: → store as exception (raw float64)Если хотя бы одно значение не проходит round-trip — оно хранится в exception list (позиция + raw float64). В типичных данных (финансы, сенсоры) exceptions составляют 0–2% блока.
Pseudodecimal encoding в BtrBlocks (Урок 03) — предшественник ALP Mode A. Обе идеи: «float, который на самом деле decimal, конвертируем в integer». Отличие: ALP формализует round-trip проверку, интегрирует FastLanes UTL layout для SIMD decode, и добавляет Mode B для non-decimal floats. BtrBlocks Pseudodecimal работает только с Mode A-подобными данными.
ALP Mode B: left-part dictionary для high-precision
Mode A не работает для научных данных (π = 3.141592653589793…) — умножение на 10^15 переполняет int64. Для таких данных ALP использует Mode B: разбиение float на две части.
Блок: 1024 × float64 high-precision (π, e, …)
Блок float64 с высокой точностью: 3.141592653589793, 3.141592653589794, 2.718281828459045, ... Full 52-bit mantissa. Mode A невозможен — слишком много значащих цифр.Decode: left_dict[idx] | right → original float64. Ratio: 1.5–3x
Decode: load left-part dict + indices, load right-parts. Reconstruct: concat(left[dict[idx]], right). SIMD-friendly: обе части используют FastLanes UTL layout. Ratio: 1.5–3x на scientific data (зависит от реальной энтропии). Хуже чем Mode A на decimal, но лучше чем Zstd на structured float data.Автоматический выбор режима
ALP автоматически определяет, какой режим использовать для каждого блока:
Блок: 1024 × float64 (тип неизвестен)
Блок float64: 1024 значения. ALP не знает заранее, decimal это или high-precision.Порог 90% — это эвристика. ALP оценивает: если Mode A покрывает ≥90% блока, exception overhead (raw float64 per exception) компенсируется сжатием основной массы. Если данные смешанные (часть decimal, часть high-precision) — ALP может выбрать Mode A с exceptions или Mode B без exceptions, в зависимости от того, что даёт меньший размер.
G-ALP: GPU-расширение (DaMoN 2025)
G-ALP (Hepkema, Afroozeh, Felius, Boncz, Manegold — DaMoN 2025) переносит ALP на GPU. Ключевая адаптация: GPU имеют тысячи threads, но каждый thread — слабее CPU-ядра. G-ALP использует ту же двухрежимную стратегию (Mode A / Mode B), но с layout, оптимизированным под GPU warp (32 threads) вместо CPU SIMD lanes.
Итог
ALP превращает «несжимаемые» float64 в хорошо сжимаемые integers — без потери ни одного бита. Ключевые идеи:
- Mode A (decimal floats): умножение на 10^n → integer → FastLanes FOR. Ratio: 4–8x на финансах/сенсорах
- Mode B (high-precision): split на left/right parts → dictionary + bitpack. Ratio: 1.5–3x
- Автовыбор: sample-based probing, порог ~90% lossless для Mode A
- Round-trip гарантия: каждое значение проверяется, non-lossless → exception list
- Интегрировано в DuckDB как internal float compression
- G-ALP (DaMoN 2025): GPU-версия для A100/H100
В следующем уроке — FSST: как CWI решила аналогичную проблему для строковых данных, где dictionary encoding не справляется.