Колоночные сегменты и zonemaps

В прошлом уроке таблица распалась на горизонтальные полосы — row groups примерно по 122 880 строк. Теперь спустимся на уровень ниже. Внутри одной row group каждая колонка живёт своей жизнью: хранится отдельным потоком значений, сжимается своей схемой, описывается своей статистикой. Этот уровень — колоночный сегмент. А самая практически важная часть его статистики — zonemap, компактная сводка min/max, которая позволяет движку пропускать целые куски данных, вообще не читая их с диска. Этот урок разбирает оба понятия: как колонка физически разложена и как min/max превращает фильтр запроса в экономию ввода-вывода.

Колоночный сегмент: единица хранения одной колонки

Возьмём таблицу с тремя колонками — id, amount, country. В row group 0 первые 122 880 строк этих колонок хранятся не вперемешку, а раздельно: все значения id идут одним непрерывным потоком, все значения amount — другим, все значения country — третьим. Каждый такой поток в пределах одной row group и есть колоночный сегмент.

Колоночный сегмент — это физическая единица хранения значений одной колонки одной row group.

ClickHouse: гранулы и Marks для пропуска данных У него три ключевых свойства. Во-первых, он содержит значения только одного типа — все BIGINT, или все VARCHAR, и больше ничего; однородность типа — фундамент всего колоночного подхода. Во-вторых, к сегменту применяется сжатие, и схема сжатия выбирается под конкретный сегмент: amount в одном сегменте может сжаться dictionary-кодированием, в другом — bit packing, в зависимости от того, какие значения там лежат (выбор схемы — тема следующего модуля). В-третьих, у сегмента есть собственная статистика — та самая zonemap.

Почему это даёт скорость аналитике. Запрос SELECT avg(amount) FROM orders касается ровно одной колонки. При колоночном хранении движок читает только сегменты amount и не трогает байты id и country — это projection pushdown на уровне физики. Если бы строки лежали построчно, как в OLTP-СУБД, пришлось бы прочитать всю строку целиком, чтобы добраться до одного поля. На таблице в сто колонок разница — два порядка по объёму чтения. Колоночные сегменты — это и есть тот механизм, который превращает «прочитать одну колонку» в «прочитать только её байты».

Zonemap: min и max как фильтр

У каждого колоночного сегмента DuckDB хранит маленькую сводку статистики. Главные её поля — минимальное и максимальное значение в сегменте. Эта пара min/max и называется zonemap (синонимы — min/max index, zone map). «Zone» — это сегмент, «map» — карта диапазона значений в нём.

Идея простая до элегантности. Zonemap занимает считанные байты — два значения на сегмент. Сам сегмент — это десятки или сотни килобайт сжатых данных. Перед тем как читать и распаковывать сегмент, движок может за бесценок заглянуть в его zonemap и спросить: «а могут ли вообще строки, которые ищет запрос, лежать в этом сегменте?»

Разберём на фильтре WHERE amount > 5000. Движок идёт по сегментам колонки amount и для каждого сравнивает фильтр с zonemap:

• Сегмент с zonemap [min=10, max=900]. Максимум 900, а нужно > 5000. Ни одно значение в сегменте не может подойти. Сегмент пропускается целиком — не читается, не распаковывается. Это и есть data skipping.
• Сегмент с zonemap [min=8000, max=9500]. Минимум 8000, и это уже больше 5000. Все значения сегмента заведомо проходят фильтр. Сравнение по строкам можно не делать вовсе — все строки подходят.
• Сегмент с zonemap [min=200, max=12000]. Диапазон пересекает порог 5000. Часть строк может подойти, часть нет. Только этот сегмент нужно реально прочитать и проверить значение за значением.

Выигрыш в том, что решение «пропустить сегмент» принимается по нескольким байтам zonemap, а сэкономленное чтение — это десятки или сотни килобайт I/O плюс работа распаковки. На большой таблице с избирательным фильтром zonemap отбрасывает большинство сегментов, и запрос читает лишь малую долю данных. Это бесплатный пропуск данных — он не требует от вас ни индекса, ни особых усилий: zonemap строится автоматически для каждого сегмента при записи.

Почему zonemap особенно силён на отсортированных данных

Эффективность zonemap прямо зависит от того, как значения распределены по сегментам. Тут есть две крайности.

Данные отсортированы (или хотя бы скоррелированы с порядком вставки). Тогда у соседних сегментов диапазоны min/max узкие и почти не пересекаются: сегмент 0 держит, скажем, [0, 5000], сегмент 1 — [5001, 10000], сегмент 2 — [10001, 15000]. Фильтр WHERE x BETWEEN 10001 AND 10100 мгновенно отбрасывает сегменты 0 и 1 по zonemap — их диапазоны не пересекают искомый — и читает только сегмент 2. Пропуск данных работает в полную силу.

Данные перемешаны случайно. Тогда в каждом сегменте встречаются и маленькие, и большие значения, и zonemap каждого сегмента — это широкий диапазон вроде [0, 999999]. Такой диапазон пересекается с почти любым фильтром, и движку приходится читать почти все сегменты. Zonemap всё ещё хранится, но отбрасывает мало или ничего.

Отсюда мощный практический рычаг. Если в таблице есть колонка, по которой часто фильтруют запросы — дата, идентификатор клиента, регион, — стоит загрузить данные в эту таблицу отсортированными по этой колонке. Сортировка при загрузке делает zonemap по этой колонке узкими и непересекающимися, и все последующие фильтрующие запросы получают мощный data skipping даром. Это одна из немногих оптимизаций физической раскладки, доступных в DuckDB: индексов в привычном OLTP-смысле здесь нет, и физический порядок данных плюс zonemap — основной инструмент ускорения избирательных фильтров.

Zonemap, projection pushdown и filter pushdown

Колоночные сегменты и zonemap вместе дают два разных механизма пропуска данных, и их полезно не путать.

Projection pushdown — пропуск ненужных колонок. Запрос SELECT avg(amount) FROM orders называет только amount. Благодаря колоночным сегментам движок читает байты только сегментов amount и полностью игнорирует сегменты id и country. Это вертикальное усечение: меньше колонок — меньше чтения.

Filter pushdown — пропуск ненужных строк. Запрос с WHERE amount > 5000 благодаря zonemap пропускает целые сегменты, чьи диапазоны не пересекают условие. Это горизонтальное усечение: меньше строк — меньше сегментов читается.

Реальный аналитический запрос обычно получает оба. SELECT avg(amount) FROM orders WHERE country = 'PL' читает только сегменты amount и country (projection pushdown отрезал id и прочие колонки) и только те row groups, чьи zonemap по country пропускают значение 'PL' (filter pushdown отрезал не подходящие группы). Два механизма перемножаются: запрос касается лишь небольшого прямоугольника данных вместо всей таблицы.

Увидеть, что движок действительно делает pushdown, можно через EXPLAIN. В физическом плане у оператора сканирования отображаются и список проецируемых колонок, и применённые к скану фильтры:

EXPLAIN SELECT avg(amount) FROM orders WHERE country = 'PL';

Фрагмент вывода:

PHYSICAL_PLAN
  PROJECTION (avg(amount))
    HASH_GROUP_BY
      TABLE_SCAN
        Table: orders
        Projections: amount, country
        Filters: country='PL'

В блоке TABLE_SCAN строка Projections: amount, country показывает, что движок читает только две колонки из всей таблицы — это projection pushdown. Строка Filters: country='PL' показывает, что фильтр опущен прямо в сканирование, где он и сработает против zonemap, отбрасывая не подходящие row groups. План — это прямое доказательство, что сегменты и zonemap делают свою работу.

Попробуй сам

Проверьте data skipping на отсортированных и перемешанных данных.

1. Создайте отсортированную таблицу: CREATE TABLE sorted AS SELECT range AS k, range % 1000 AS v FROM range(2000000) ORDER BY k; и CHECKPOINT.
2. Создайте перемешанную таблицу с тем же содержимым: CREATE TABLE shuffled AS SELECT range AS k, range % 1000 AS v FROM range(2000000) ORDER BY random(); и CHECKPOINT.
3. Выполните EXPLAIN ANALYZE SELECT count(*) FROM sorted WHERE k BETWEEN 1500000 AND 1500100;. Посмотрите в выводе число строк, реально прочитанных оператором сканирования.
4. Выполните тот же EXPLAIN ANALYZE для таблицы shuffled с фильтром по k в том же диапазоне. Сравните, сколько строк прочитал скан в каждом случае.
5. Объясните разницу через zonemap: в отсортированной таблице сегменты по k имеют узкие непересекающиеся диапазоны, и фильтр отбрасывает почти все сегменты; в перемешанной таблице сегменты по k имеют широкие диапазоны и почти не отбрасываются.
6. Загляните в pragma_storage_info('sorted') и найдите колонки со статистикой сегментов. Сравните диапазоны min/max сегментов колонки k для отсортированной и перемешанной таблиц.

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