Bit packing и Frame of Reference

В прошлом уроке constant encoding и RLE убирали избыточность повторов. Но что делать с колонкой, где значения почти все разные — id, amount, timestamp? Повторов нет, RLE бессилен. И всё же такие колонки прекрасно сжимаются — другим приёмом. Идея в том, что числа часто занимают куда меньше информации, чем выделенный под них тип. Этот урок про две схемы, которые это используют: bit packing срезает лишние биты у целых, а Frame of Reference хранит значения как смещения от опорной точки — и вместе они дают мощное сжатие дат и timestamp.

Сколько бит на самом деле нужно числу

Когда вы объявляете колонку BIGINT, каждое значение получает 64 бита — 8 байт. Это размер типа, и он фиксирован. Но реальные значения почти никогда не используют все 64 бита.

Возьмём колонку age — возраст человека. Тип, скажем, INTEGER, 32 бита на значение. Но возраст — это число от 0 до примерно 120. Чтобы записать любое число до 127, хватает 7 бит. Остальные 25 бит из 32 в каждом значении — нули. Колонка из миллиона возрастов хранит 25 миллионов заведомо нулевых бит. Это чистая избыточность: место занято, информации ноль.

Bit packing убирает эту избыточность. Идея в названии: упаковать значения, отбросив ведущие нулевые биты. Если в сегменте максимальное значение помещается в 7 бит, то каждое значение хранится в 7 битах, а не в 32. Биты значений укладываются плотно, впритык друг к другу, без выравнивания по байтам — отсюда «packing», упаковка.

Декомпрессия — чистая работа с битами. Чтобы достать значение, движок берёт нужные 7 бит из плотного потока битовыми сдвигами и масками. Сдвиг и маска — операции в один такт процессора, идеально векторизуемые. Это ровно та «распаковка почти даром», которую требует lightweight-подход.

Ключевое следствие: bit packing позволяет хранить значение BIGINT в месте, которого хватило бы для INTEGER или даже меньше. Тип объявлен 64-битным, но если фактические значения мелкие — на диске они займут столько бит, сколько реально нужно. Размер типа перестаёт диктовать размер хранения.

Ширина выбирается локально, по 1024 значения

Bit packing должен выбрать ширину — сколько бит отвести каждому значению. Ширину диктует максимальное значение: нужно столько бит, чтобы в них поместился максимум. Но один максимум на весь сегмент — грубовато: если в сегменте 122 880 значений и почти все мелкие, а одно случайно крупное, то крупное значение задрало бы ширину для всех остальных.

Поэтому DuckDB выбирает ширину не на весь сегмент сразу, а маленькими порциями — отслеживая максимум на каждые 1024 значения. Сегмент режется на участки по 1024 значения, и каждый участок упаковывается своей шириной, подобранной под его собственный локальный максимум. Один участок, где значения мелкие, упакуется очень узко; соседний участок с крупными значениями получит ширину побольше — и не испортит первый.

Зачем именно так. Реальные данные неоднородны вдоль колонки: где-то значения мелкие, где-то крупные. Локальный выбор ширины адаптируется к этой неоднородности — каждый кусок жмётся настолько узко, насколько позволяют именно его значения. Глобальная ширина на весь сегмент равнялась бы по самому крупному значению во всём сегменте и упустила бы экономию на мелких участках. Гранулярность 1024 — это адаптивность сжатия к локальным колебаниям величины значений.

Frame of Reference: смещения от опорной точки

Bit packing срезает ведущие нули. Но есть колонки, где ведущих нулей нет, а сжать всё равно хочется. Классический пример — даты и timestamp.

Даты в DuckDB хранятся внутри как целые числа — Unix-смещения, число дней (или микросекунд для timestamp) от опорной точки 1 января 1970 года. Дата из 2026 года — это смещение порядка 20 с лишним тысяч дней от 1970-го. Число большое, ведущих нулей у него почти нет — bit packing напрямую много не отрежет.

Но посмотрим на колонку дат целиком. Аналитическая таблица обычно покрывает узкий диапазон дат — например, события за один год. Сами числа большие (все около 20 000), но разброс между ними маленький (укладывается в 365). Вот эту структуру — «большие числа, но в узком диапазоне» — использует Frame of Reference, FOR.

FOR работает так. По сегменту находится минимальное значение — это «рама», frame, опорная точка. Затем каждое значение хранится не как оно само, а как разность между ним и минимумом — смещение от рамы. Минимум хранится один раз на сегмент.

Магия в том, что происходит с числами. Сами значения большие — около 20 000. Но смещения от минимума маленькие: если все даты в пределах года, смещения лежат в диапазоне 0..365. А маленькие числа — это как раз то, что bit packing упаковывает превосходно: число до 365 помещается в 9 бит вместо 32. FOR превращает «большие числа в узком диапазоне» в «маленькие числа» — и передаёт их bit packing, который их добивает.

Декомпрессия двухшаговая и по-прежнему дешёвая: достать упакованное смещение (битовый сдвиг и маска) и прибавить к нему минимум сегмента (одно сложение). Сдвиг, маска, сложение — три элементарные операции на значение, всё векторизуется.

Почему это особенно мощно для дат и timestamp

Связка FOR плюс bit packing раскрывается именно на временных колонках, и стоит понять почему.

Timestamp в DuckDB — это 64-битное целое, микросекунды от 1970 года. Абсолютное значение колоссально: timestamp 2026 года — это число порядка 1.7 на 10 в 15-й степени микросекунд. Хранить такое в 64 битах напрямую — 8 байт на каждое значение.

Но таблица фактов почти всегда покрывает ограниченное окно времени — год, месяц, иногда один день. Применяем FOR: вычитаем минимальный timestamp сегмента. Если все события сегмента укладываются, скажем, в сутки, то смещения — это микросекунды в пределах суток, число до примерно 86 миллиардов. Это уже помещается не в 64, а в 37 бит. Если события сегмента укладываются в час — смещения ещё меньше, ширина ещё уже. Bit packing упаковывает эти смещения по их фактической ширине, локально, на каждые 1024 значения.

Результат: временная колонка, которая «по типу» весит 8 байт на значение, после FOR плюс bit packing занимает заметно меньше — тем меньше, чем уже временное окно сегмента. А поскольку данные часто загружаются хронологически, внутри одного сегмента timestamp обычно и так лежат в узком окне — FOR срабатывает почти сам собой. Даты, время, timestamp — главная вотчина этой связки, и именно поэтому колоночные базы хранят временные ряды очень компактно.

Посмотрим на реальном примере, что движок выбирает для разных числовых колонок:

duckdb forlab.duckdb

CREATE TABLE events AS
  SELECT range AS id,
         (range % 120)::INTEGER AS age,
         (DATE '2026-01-01' + (range % 365)) AS event_date
  FROM range(1000000);
CHECKPOINT;

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

Вывод:

column_name  compression  segments
age          bitpacking   9
event_date   bitpacking   9
id           bitpacking   9

Все три числовые колонки попали под bit packing. Колонка age — маленькие числа 0..119, упаковываются напрямую в 7 бит. Колонка event_date — даты в пределах года; внутри сегмента их разброс мал, FOR сводит их к смещениям, bit packing добивает узкой шириной. Колонка id — возрастающая последовательность, в пределах сегмента это плотный диапазон, и его смещения тоже упаковываются узко. Имя bitpacking в выводе обозначает упаковку, нередко уже после приведения значений к смещениям — FOR и bit packing работают как единый механизм для целочисленных и временных данных.

Попробуй сам

Проверьте, как ширина значений управляет сжатием.

1. Создайте таблицу с очень узкими по диапазону числами: CREATE TABLE narrow AS SELECT range AS id, (range % 4)::INTEGER AS tiny FROM range(2000000); и CHECKPOINT. Колонка tiny принимает значения 0..3 — сколько бит ей достаточно? Посмотрите её схему в pragma_storage_info.
2. Создайте таблицу с широкими числами: CREATE TABLE wide AS SELECT range AS id, (random() * 1000000000)::BIGINT AS big FROM range(2000000); и CHECKPOINT. Сравните размер файла wide на диске с размером файла narrow. Почему wide заметно крупнее, хотя число строк то же?
3. Создайте таблицу с датами в узком окне: CREATE TABLE d_year AS SELECT range AS id, (DATE '2026-01-01' + (range % 365)) AS d FROM range(2000000); и CHECKPOINT.
4. Создайте таблицу с датами в очень широком окне: CREATE TABLE d_wide AS SELECT range AS id, (DATE '1900-01-01' + (range % 50000)) AS d FROM range(2000000); и CHECKPOINT. Сравните размеры файлов d_year и d_wide. Объясните разницу через FOR: чем шире разброс дат внутри сегмента, тем больше смещения и тем шире упаковка.
5. Создайте таблицу с timestamp в пределах одного дня и в пределах десяти лет, сравните их размеры на диске. Подтвердите гипотезу: узкое временное окно сегмента -> маленькие смещения -> узкая упаковка -> компактный файл.

Этот эксперимент даёт почувствовать ключевую идею модуля: для bit packing и FOR важна не величина чисел сама по себе, а их разброс внутри сегмента.