Двухпроходный analyze/compress

В предыдущих уроках мы разобрали восемь с лишним схем сжатия — Constant, RLE, bit packing, Frame of Reference, dictionary, FSST, Chimp, Patas, ALP. И каждый раз в примерах pragma_storage_info показывал, что DuckDB выбрал какую-то одну схему для каждого сегмента — RLE для одной колонки, dictionary для другой, ALP для третьей. Но кто и как делает этот выбор? Вы не указываете схему сжатия — движок решает сам, для каждого сегмента отдельно. Этот завершающий урок модуля про сам механизм выбора: двухпроходный алгоритм analyze/compress.

Почему схему нельзя выбрать заранее

Можно было бы потребовать от пользователя: «укажи схему сжатия для каждой колонки». Так не делают, и причина — данные в одной колонке неоднородны.

Вспомните структуру из модуля про storage-формат: таблица режется на row groups, и каждая колонка каждой row group — это отдельный колоночный сегмент. Колонка region в большой таблице — это не один сегмент, а десятки. И эти сегменты могут содержать очень разные данные. В одной row group region оказался отсортированным куском с длинными сериями — идеален для RLE. В другой row group тот же region — перемешанный фрагмент, где RLE бесполезен, а dictionary в самый раз. Третий сегмент region целиком состоит из одного значения — тут лучше всего constant.

Одна и та же колонка, три сегмента, три разные оптимальные схемы. Глобальный выбор «вся колонка region сжимается схемой X» проиграл бы: какую X ни возьми, она не будет лучшей для всех сегментов сразу. Поэтому правильная гранулярность выбора — сегмент, а не колонка и не таблица. А раз выбор посегментный и зависит от фактического содержимого сегмента, сделать его заранее, до того как данные увидены, нельзя. Выбор должен происходить во время записи, по реальным данным.

Два прохода: сначала оценить, потом записать

DuckDB решает задачу выбора двухпроходным алгоритмом. Каждый сегмент при записи проходит обработку дважды: сначала фаза analyze, затем фаза compress.

Фаза analyze — разведка. Движок прогоняет данные сегмента через все схемы-кандидаты, подходящие по типу: для целочисленного сегмента это bit packing, FOR, RLE, constant; для строкового — dictionary, FSST, constant; для float — ALP, Chimp, Patas. Но на этом проходе он не сжимает по-настоящему — он лишь оценивает: «если сжать этот сегмент данной схемой, сколько байт получится?». Каждая схема возвращает прогноз итогового размера. Analyze собирает эти прогнозы и выбирает победителя — схему с наименьшим предсказанным размером.

Фаза compress — собственно сжатие. Теперь, когда схема выбрана, движок проходит данные сегмента второй раз и реально кодирует их выбранной схемой, записывая сжатые данные в блоки файла фиксированного размера.

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

Почему два прохода — это дёшево

Двойной проход по данным звучит как удвоение работы. На деле он почти бесплатен, и причина — в размере сегмента и в иерархии памяти процессора.

Сегмент невелик: это одна колонка одной row group, порядка 122 880 значений. В сжатом или в рабочем виде такой сегмент — десятки, максимум сотни килобайт. А это сопоставимо с объёмом кэшей современного процессора.

Дальше работает свойство кэша. Когда фаза analyze прогоняет сегмент через схемы-кандидаты, данные сегмента подтягиваются в кэш CPU. Когда сразу за ней фаза compress проходит тот же сегмент второй раз — данные с большой вероятностью всё ещё в кэше: их только что читали, вытеснить не успело. Второй проход читает не из медленной оперативной памяти и тем более не с диска, а из быстрого кэша.

Вот почему два прохода дёшевы: дорог не «проход по данным» сам по себе, дорог проход, упирающийся в медленную память. А когда сегмент целиком помещается в кэш, оба прохода идут на скорости кэша, и стоимость второго прохода почти теряется. Размер сегмента в DuckDB — около 122 880 строк — выбран в том числе и с этим расчётом: достаточно мал, чтобы аккуратно лечь в кэш, и двухпроходный выбор схемы окупается.

Что это даёт пользователю

Из двухпроходного посегментного выбора вытекают три практических следствия.

Сжатие работает само. Вы не выбираете схему, не настраиваете параметры, не подсказываете движку. Создали таблицу, вставили данные, прошёл checkpoint — DuckDB сам для каждого сегмента прогнал analyze и выбрал лучшую схему. Сжатие в DuckDB — это поведение по умолчанию, а не опция, которую надо включать.

Выбор адаптивен к реальным данным. Поскольку решение принимается посегментно по фактическому содержимому, разные части одной колонки сжимаются по-разному — каждая своей оптимальной схемой. Отсортированный кусок получит RLE, перемешанный — dictionary, и всё это внутри одной колонки, автоматически. Движок подстраивается под данные, а не навязывает им единую схему.

Физическая раскладка данных напрямую влияет на сжатие. Это самый практичный вывод всего модуля. Раз движок выбирает схему по содержимому сегмента, то, как вы расположите данные, определяет, какие схемы он сможет применить. Загрузили таблицу отсортированной по колонке — её сегменты получат длинные серии, и analyze выберет RLE; в той же колонке без сортировки серий нет, и RLE окажется недоступен. Сортировка при загрузке, которую мы в модуле про storage-формат рекомендовали ради узких zonemap и data skipping, заодно открывает движку доступ к более сильным схемам сжатия. Вы не управляете сжатием напрямую — но управляете данными, а через них и сжатием.

Увидеть результат работы analyze можно всё той же функцией — pragma_storage_info с колонкой compression показывает, какую схему фаза analyze выбрала для каждого сегмента:

duckdb final.duckdb

CREATE TABLE mixed AS
  SELECT range AS id,
         (range / 100000)::INTEGER AS sorted_grp,
         (random() * 1000)::INTEGER AS random_val,
         ['EU','US','APAC'][(range % 3) + 1] AS region
  FROM range(1000000);
CHECKPOINT;

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

Вывод:

column_name  compression  segments
id           bitpacking   9
random_val   bitpacking   9
region       dictionary   9
sorted_grp   rle          9

Четыре колонки — четыре разных выбора фазы analyze, и каждый объясним. sorted_grp — длинные серии (выражение range / 100000), analyze выбрал rle. region — три уникальных значения, низкая кардинальность, выбран dictionary. id и random_val — целые числа без серий и без повторов, выбран bitpacking. Никто эти схемы не задавал — двухпроходный analyze определил их по реальному содержимому каждого сегмента.

Попробуй сам

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

1. Создайте таблицу, где одна и та же по смыслу колонка попадает в сегменты разного характера. Например: CREATE TABLE blocks AS SELECT range AS id, CASE WHEN range < 500000 THEN 1 ELSE (random() * 1000)::INTEGER END AS v FROM range(1000000); — первая половина колонки v константна, вторая случайна. Сделайте CHECKPOINT.
2. Посмотрите SELECT row_group_id, compression FROM pragma_storage_info('blocks') WHERE column_name = 'v' ORDER BY row_group_id;. Разные ли схемы у ранних и поздних сегментов одной колонки? Объясните, почему analyze выбрал для них разное.
3. Создайте таблицу, отсортированную по колонке низкой кардинальности, и её же неотсортированную копию. Сравните, какие схемы analyze выбрал для этой колонки в обоих случаях. Подтвердите: сортировка открывает доступ к RLE.
4. Создайте широкую таблицу с колонками всех типов — целые, float (десятичные), float (случайные), строки низкой кардинальности, строки высокой кардинальности с общим хвостом. Сделайте CHECKPOINT и одним запросом к pragma_storage_info посмотрите выбор analyze для каждой колонки. Сверьте каждый выбор с тем, что вы знаете из уроков модуля.
5. Поразмышляйте: вы не задавали ни одной схемы вручную. Почему такой автоматический посегментный выбор практичнее, чем если бы пользователь указывал схему на колонку?

Этот эксперимент сводит весь модуль воедино: вы видите, как двухпроходный analyze применяет все изученные схемы — и как через раскладку данных вы косвенно управляете его решениями.