Constant encoding и RLE

В прошлом уроке мы выяснили, почему DuckDB жмёт данные лёгкими схемами: распаковка обязана идти на скорости сканирования. Теперь начинаем разбирать сами схемы — от простейших к сложным. Этот урок про две самые элементарные: constant encoding, которая хранит один-единственный повторённый значение, и RLE (run-length encoding), которая хранит серии одинаковых значений как пары «значение и длина». Обе тривиальны по устройству, обе распаковываются почти даром — и обе дают огромную экономию на правильных данных.

Constant encoding: когда в сегменте всё одинаковое

Самая простая ситуация для сжатия — когда все значения в колоночном сегменте идентичны. Все 122 880 значений сегмента — одно и то же число, одна и та же строка, один и тот же NULL.

Хранить 122 880 копий одинакового значения — чистая трата места. Constant encoding замечает это и хранит ровно одно значение плюс отметку, что весь сегмент состоит из его повторений. Декомпрессия тривиальна: чтобы «распаковать» сегмент, движок берёт это одно значение и тиражирует его на нужное число строк. По сути распаковки и нет — есть просто одно значение, известное на весь сегмент.

Когда это срабатывает на практике. Сегмент сжимается constant encoding не только в очевидном случае «вся колонка — одна константа». Вспомните: сегмент покрывает одну колонку одной row group — примерно 122 880 строк. Достаточно, чтобы значение колонки было одинаковым в пределах этих 122 880 строк, а в других row groups оно может отличаться. Типичные кандидаты: колонка currency, в которой на длинном отрезке записей стоит 'USD'; колонка-флаг is_deleted, почти всегда false; колонка с дефолтным значением, которое в этом куске данных никто не переопределял; колонка, целиком состоящая из NULL на данном отрезке.

Экономия предельная. Вместо сегмента в десятки или сотни килобайт на диске остаётся одно значение и метка — считанные байты. И это связывается с физическими типами вектора: при сканировании такой сегмент разворачивается в CONSTANT_VECTOR — вектор, который физически хранит одно значение, а логически ведёт себя как массив из 2048 одинаковых. Операторы запроса умеют работать с CONSTANT_VECTOR напрямую и часто обрабатывают весь батч одной операцией.

RLE: кодирование длин серий

Constant encoding требует, чтобы весь сегмент был одним значением. Это жёсткое условие. Ослабим его: пусть в сегменте не одно значение, а несколько, но они идут длинными непрерывными сериями одинаковых. Например: сто 'PL' подряд, потом двести 'DE' подряд, потом полтораста 'FR' подряд.

Эту структуру кодирует RLE — run-length encoding, кодирование длин серий. «Run» — это серия, непрерывный участок из одинаковых значений. RLE хранит каждую серию как пару: само значение и длина серии — сколько раз оно повторяется подряд. Сто 'PL' превращаются в одну пару ('PL', 100). Двести 'DE' — в ('DE', 200). Вместо 450 хранимых значений — три пары.

Декомпрессия снова элементарна. Движок читает пару (значение, длина) и тиражирует значение указанное число раз; читает следующую пару — тиражирует следующее. Никакого сложного разбора — цикл копирования, который процессор выполняет на максимальной скорости. Это ровно тот тип «распаковки почти даром», который требует lightweight-подход.

Степень сжатия RLE определяется длиной серий. Чем длиннее серии, тем сильнее сжатие: серия из тысячи одинаковых значений ужимается в одну пару — это сжатие в тысячу раз на этом участке. Чем короче серии, тем хуже: если значения постоянно чередуются и серии в среднем по две-три штуки, RLE почти не выигрывает — пара (значение, длина) сама занимает место, и на коротких сериях накладные расходы съедают экономию. RLE — схема для данных с длинными сериями.

Где RLE блестит: сортировка, партиционирование, NULL

RLE даёт серьёзный выигрыш ровно тогда, когда в данных есть длинные серии одинаковых значений. Есть три типичные ситуации, когда такие серии возникают сами собой.

Отсортированные данные. Если таблица отсортирована по колонке, то в этой колонке все одинаковые значения собраны вместе в один непрерывный блок — это и есть длинные серии. Колонка region в таблице, отсортированной по region: сначала все строки 'EU' подряд, потом все 'US' подряд. RLE сжимает такую колонку феноменально. Связь с прошлым модулем: сортировка при загрузке мы рекомендовали ради узких zonemap и data skipping — оказывается, та же сортировка ещё и делает колонку идеальной для RLE. Одно решение, два независимых выигрыша.

Партиционированные или сгруппированные данные. Даже без полной сортировки данные часто приходят группами: все события одного дня загружены вместе, все записи одного клиента идут подряд. В колонке event_date при загрузке день за днём естественно образуются серии — все строки одной даты рядом.

Колонки с обилием NULL. Если в колонке много NULL и они идут подряд (например, необязательное поле, заполненное лишь у части записей одного куска данных), длинные серии NULL прекрасно кодируются RLE. Низкая кардинальность — мало различных значений на много строк — тоже располагает к сериям, особенно в сочетании с упорядоченностью.

Как увидеть выбранную схему

DuckDB выбирает схему сжатия для каждого сегмента сам — этот механизм мы разберём в последнем уроке модуля. Но посмотреть, что движок выбрал, можно уже сейчас, через знакомую функцию pragma_storage_info. В её выводе есть колонка compression — имя схемы, применённой к сегменту.

duckdb rle.duckdb

-- Колонка с длинными сериями: значения идут отсортированными группами
CREATE TABLE sales AS
  SELECT range AS id, (range / 50000)::INTEGER AS region
  FROM range(1000000);
CHECKPOINT;

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

Вывод:

column_name  compression  segments
id           bitpacking   9
region       rle          9

Колонка region получила rle: выражение range / 50000 даёт длинные серии одинаковых значений — 50 000 строк подряд с одним значением региона, затем следующие 50 000 со следующим. RLE на таких данных идеален. Колонка id — строго возрастающая последовательность без повторов вообще, и для неё RLE бесполезен (серии длиной один), движок выбрал другую схему — bit packing, к ней мы перейдём в следующем уроке.

Сравним с противоположным случаем — перемешанной колонкой:

CREATE TABLE shuffled AS
  SELECT range AS id, (random() * 5)::INTEGER AS region
  FROM range(1000000);
CHECKPOINT;

SELECT column_name, compression
FROM pragma_storage_info('shuffled')
WHERE column_name = 'region'
GROUP BY column_name, compression;

column_name  compression
region       bitpacking

Та же по смыслу колонка region, но значения раскиданы случайно — серий нет, и DuckDB на RLE её сжимать не стал, выбрал другую схему. Это прямое подтверждение: RLE — про длинные серии, и движок применяет её только там, где серии действительно есть.

Попробуй сам

Понаблюдайте, как структура данных управляет выбором между constant, RLE и прочими схемами.

1. Создайте таблицу с константной колонкой: CREATE TABLE c AS SELECT range AS id, 'USD' AS currency FROM range(500000); и CHECKPOINT. Посмотрите SELECT column_name, compression FROM pragma_storage_info('c') GROUP BY 1,2;. Какую схему получила currency?
2. Создайте таблицу с длинными сериями: CREATE TABLE r AS SELECT range AS id, (range / 100000)::INTEGER AS bucket FROM range(1000000); и CHECKPOINT. Какую схему получила bucket?
3. Создайте таблицу с короткими чередующимися сериями: CREATE TABLE alt AS SELECT range AS id, (range % 2)::INTEGER AS flip FROM range(1000000); и CHECKPOINT. Колонка flip чередует 0 и 1 — серии длиной один. Выбрал ли движок RLE? Почему нет?
4. Создайте таблицу, отсортированную по колонке низкой кардинальности: CREATE TABLE s AS SELECT range AS id, (range % 8)::INTEGER AS grp FROM range(1000000) ORDER BY grp; и CHECKPOINT. После сортировки одинаковые значения grp собрались в серии — какую схему теперь получила grp? Сравните с несортированной версией той же колонки.
5. Сравните размеры файлов баз c, r и alt на диске через ls -lh. Объясните разницу через длину серий в их колонках.

Этот эксперимент показывает живьём: constant и RLE — не абстрактные опции, движок выбирает их строго по структуре данных, и сортировка превращает обычную колонку в идеального кандидата для RLE.