Chimp, Patas и ALP для чисел с плавающей точкой

Целые числа упаковывает bit packing, строки — dictionary и FSST. Остался последний и самый трудный класс — числа с плавающей точкой, REAL и DOUBLE. Цены, измерения датчиков, координаты, метрики. Float сжимать тяжело: их внутреннее представление устроено так, что обычные приёмы об него спотыкаются. Этот урок про то, почему так, и про три схемы, которыми DuckDB всё-таки сжимает float — Chimp, Patas и ALP. Корректные имена и их компромиссы здесь важны: запомните их точно.

Почему float не поддаётся обычным схемам

Число DOUBLE — это 64 бита, но устроены они хитро: знак, экспонента, мантисса по стандарту IEEE 754. Из-за этой структуры приёмы для целых об float ломаются.

Bit packing бесполезен. Он срезает ведущие нулевые биты. Но у типичного float ведущих нулевых бит нет — экспонента и мантисса заполняют разряды плотно. Срезать нечего.

Frame of Reference бесполезен. FOR вычитает минимум, чтобы получить маленькие разности. Но вычитание float от float — это операция над дробными числами, и она не уменьшает число хранимых бит так, как уменьшает у целых: разность двух близких double — это снова полноценный double со своей мантиссой.

Главная же беда — точность. Десятичное число 0.1 в двоичном float не представимо точно: оно хранится как ближайшее двоичное приближение с длинным «мусорным хвостом» в мантиссе. Колонка цен 19.99, 5.49, 120.00 — для человека простые числа с двумя знаками, а в битах double — длинные нерегулярные мантиссы. Эта нерегулярность и есть то, обо что спотыкается сжатие: повторов нет, ведущих нулей нет, разности не помогают.

Поэтому для float нужны специальные схемы. Их в DuckDB три, и появились они в таком порядке: сначала Chimp, потом Patas, затем ALP.

Chimp и Patas: XOR соседних чисел

Chimp и Patas разделяют общую идею, унаследованную от более раннего алгоритма Gorilla (он был придуман для сжатия временных рядов метрик). Идея — XOR соседних значений.

Логика такая. В реальной колонке float соседние значения часто похожи: показания датчика температуры идут как 21.34, 21.35, 21.33 — близкие числа. У близких double совпадает большая часть битов: знак, экспонента, старшие разряды мантиссы одинаковы, отличаются только младшие.

Операция XOR между двумя числами даёт нули в тех битах, где числа совпадают, и единицы — где различаются. XOR двух похожих double — это значение, у которого много нулевых бит: нулевые в начале (там, где совпали знак и экспонента) и нулевые в конце (там, где совпали младшие разряды). Ненулевые биты сгруппированы в узкой средней зоне.

Дальше — то, чего обычные схемы добиться не могли. У результата XOR теперь есть ведущие и хвостовые нули, и их можно отбросить. Chimp и Patas хранят не сами числа, а XOR каждого числа с предыдущим, и кодируют этот XOR компактно: сколько нулей в начале, сколько значащих бит в середине, сами эти биты. Хвостовые нули тоже отбрасываются. XOR превратил «непохожие в битах float» в «значения с отбрасываемыми нулями».

В чём разница между Chimp и Patas. Chimp появился первым. Patas — следующий шаг, оптимизированный прежде всего под скорость декомпрессии: его кодирование XOR-результатов устроено так, чтобы распаковка была ещё быстрее и лучше векторизовалась. Patas жертвует небольшой долей степени сжатия ради того, чтобы декомпрессия надёжно шла на скорости сканирования. Это та же логика, что и во всём модуле: для OLAP скорость распаковки часто важнее лишних процентов сжатия.

ALP: вернуть число к десятичному виду

Chimp и Patas работают с битовым представлением float как есть. ALP заходит с другой стороны — и поэтому жмёт сильнее.

ALP — Adaptive Lossless floating-Point compression, «адаптивное сжатие чисел с плавающей точкой без потерь». Ключевое наблюдение, на котором она построена: огромная доля float в реальных данных — это на самом деле десятичные числа. Цена 19.99, измерение 21.3, процент 4.75. Человек ввёл их как десятичные дроби с небольшим числом знаков после запятой, и лишь представление IEEE 754 превратило их в нерегулярные двоичные мантиссы с мусорным хвостом.

ALP пытается обратить это. Для сегмента float она подбирает множитель — степень десяти, — на который если домножить значения, они становятся целыми. Цены 19.99, 5.49, 120.00 при умножении на 100 превращаются в целые 1999, 549, 12000. ALP адаптивно (отсюда «Adaptive») находит для сегмента подходящую степень десяти.

И вот ключевой ход: как только float превратились в целые, к ним применимо всё, что мы знаем про сжатие целых. Целые 1999, 549, 12000 сжимаются Frame of Reference и bit packing — теми самыми лёгкими, быстрыми схемами из урока про целые. ALP, по сути, переводит задачу «сжать float» в задачу «сжать целые», которая уже отлично решена.

А что с числами, которые не являются «красивыми» десятичными — результат деления, иррациональная константа, показание с длинным хвостом? ALP не ломается на них: для таких значений у неё есть запасной путь — вариант кодирования (в реализации DuckDB он опирается на близость соседних значений), который обрабатывает float, не сводящиеся к целым. Слово «Adaptive» работает и здесь: ALP смотрит на данные сегмента и выбирает, идти ли путём «домножить до целых» или запасным. Слово «Lossless» — гарантия: при любом пути распаковка восстанавливает исходные биты точно, сжатие без потерь, ни один разряд не теряется.

Цифры: почему ALP выигрывает

Теперь конкретные числа сравнения трёх схем — их стоит запомнить, потому что они объясняют, почему ALP стала схемой по умолчанию для float в DuckDB.

ALP даёт в среднем примерно 4.3x — почти вдвое сильнее, чем Patas с его ~2.1x, и заметно сильнее Chimp с ~2.4x. Разрыв объясняется самим подходом. Chimp и Patas работают с «сырыми» битами IEEE 754 и могут отжать только то, что дал XOR соседей, — а это часто скромно, потому что мусорный хвост мантиссы у соседних чисел совпадает не полностью. ALP убирает причину проблемы: она возвращает числа к десятичному виду, и нерегулярная мантисса просто исчезает — дальше работают мощные целочисленные схемы. Поэтому на типичных данных (цены, измерения, метрики, в массе своей десятичные) ALP выигрывает крупно.

При этом ALP остаётся lightweight: распаковка — это обратный множитель (одно умножение или деление) плюс распаковка целых через FOR и bit packing, всё векторизуемо, всё на скорости сканирования. ALP не платит за высокую степень сжатия медленной декомпрессией — она просто умнее формулирует задачу.

Как увидеть схему на float-колонках

Посмотрим, что DuckDB выбирает для колонок с плавающей точкой:

duckdb floatlab.duckdb

CREATE TABLE measurements AS
  SELECT range AS id,
         ((range % 10000) / 100.0)::DOUBLE AS price,
         (20.0 + (range % 50) / 10.0)::DOUBLE AS sensor
  FROM range(1000000);
CHECKPOINT;

SELECT column_name, compression, count(*) AS segments
FROM pragma_storage_info('measurements')
GROUP BY column_name, compression
ORDER BY column_name;

Вывод:

column_name  compression  segments
id           bitpacking   9
price        alp          9
sensor       alp          9

Обе float-колонки — price и sensor — получили alp. Это и есть схема по умолчанию для чисел с плавающей точкой в современном DuckDB: значения здесь по сути десятичные (price — два знака после запятой, sensor — один), ALP сводит их к целым и сжимает целочисленными схемами. Колонка id целочисленная — для неё float-схемы неприменимы, выбран bitpacking. Если бы в колонке были «некрасивые» float, не сводящиеся к целым, ALP применила бы свой запасной путь — но и тогда в выводе осталось бы имя alp, схема одна, адаптивная.

Попробуй сам

Сравните сжатие float-колонок разного характера.

1. Создайте таблицу с «красивыми» десятичными ценами: CREATE TABLE prices AS SELECT range AS id, ((range % 50000) / 100.0)::DOUBLE AS price FROM range(2000000); и CHECKPOINT. Посмотрите схему колонки price в pragma_storage_info — это должна быть alp.
2. Создайте таблицу с «некрасивыми» float — результатами деления с длинным хвостом: CREATE TABLE ugly AS SELECT range AS id, (random() / 7.0)::DOUBLE AS val FROM range(2000000); и CHECKPOINT. Сравните размер файла ugly на диске с размером файла prices. Почему «красивые» десятичные цены сжимаются заметно сильнее?
3. Создайте таблицу с показаниями датчика, медленно меняющимися (соседние значения очень близки): CREATE TABLE sensor AS SELECT range AS id, (100.0 + sin(range / 1000.0))::DOUBLE AS temp FROM range(2000000); и CHECKPOINT. Посмотрите её размер и схему.
4. Сравните на диске три файла — prices, ugly, sensor. Расположите их по степени сжатия и объясните порядок: десятичные числа с коротким хвостом ALP сводит к целым; медленно меняющиеся близкие значения тоже хорошо предсказуемы; чисто случайные float с длинным хвостом сжимаются хуже всего.
5. Прикиньте по цифрам из урока: если ALP даёт в среднем около 4.3x, а Patas около 2.1x, то насколько меньше был бы файл prices, окажись он сжат ALP, по сравнению с гипотетическим Patas?

Этот эксперимент показывает на практике: float сжимаются по-разному в зависимости от того, насколько они «десятичные» и насколько похожи соседние значения, — и почему ALP, сводящая float к целым, стала схемой по умолчанию.