Page и Block: колоночный формат и векторизация

Весь модуль мы говорили: операторы обрабатывают Page, данные текут по конвейеру Page за Page. Пора вскрыть Page — это самый «железный» уровень курса. Здесь мы доходим до того, как байты данных физически разложены в памяти воркера, почему эта раскладка колоночная и почему именно она делает Trino быстрым.

Этот урок — про Page и Block: структуру колоночного in-memory формата, виды блоков, dictionary-блоки и связь с векторизацией и кэшами процессора.

Page: единица передачи данных

Page — это единица передачи данных между операторами в Trino. Когда оператор отдаёт результат следующему, он отдаёт Page. Driver прогоняет данные через цепочку операторов именно Page-ами.

Но что внутри Page. Логически Page — это набор строк, скажем, до нескольких тысяч. Однако физически Page устроен не построчно. Page — это набор Block-ов, и каждый Block хранит данные одного столбца.

Вот это — суть. Если бы Page был построчным, в памяти лежало бы: строка 1 (orderkey, total, status), строка 2 (orderkey, total, status)… Значения разных столбцов чередовались бы. Trino делает иначе: сначала все orderkey подряд (Block A), потом все total подряд (Block B), потом все status подряд (Block C). Это колоночная раскладка: значения одного столбца лежат в памяти непрерывно. Trino — колоночный движок не только на диске (форматы Parquet, ORC), но и в памяти, во время исполнения.

Block: данные одного столбца

Block — это структура, хранящая значения одного столбца для строк одного Page. Block — кирпичик, из которого сложен Page.

Block хранит не только значения, но и информацию о null. У столбца значение может отсутствовать. Block держит отдельно «полезную нагрузку» (сами значения) и отметки, какие позиции — null. Так оператору не нужно для каждого значения проверять особый «маркер null» внутри данных — есть отдельная компактная структура null-флагов.

Физическая раскладка Block зависит от типа столбца. Для столбца фиксированной ширины (bigint — 8 байт на значение) Block — это, по сути, один непрерывный массив: значение i-й строки лежит по смещению i * 8. Для столбца переменной ширины (varchar) сложнее: один массив хранит все байты строк подряд, второй — смещения, где какая строка начинается. Но идея общая: значения столбца лежат компактно и непрерывно.

Почему колоночность быстра: кэши процессора

Зачем колоночная раскладка в памяти. Ответ — на уровне «до железа», в устройстве процессора.

Процессор читает память не по одному байту. Он читает cache line — блок фиксированного размера, типично 64 байта, — и кладёт его в кэш (L1, L2). Когда программа обращается к адресу в памяти, процессор подтягивает в кэш всю 64-байтную линию вокруг этого адреса. Если следующее нужное значение оказалось в той же линии — оно уже в кэше, доступ мгновенный. Если нет — процессор ждёт новую линию из памяти, а это медленно.

Теперь сравним раскладки на операции «просуммировать столбец total по всем строкам Page».

Построчная раскладка. Значения total разбросаны: между total строки 1 и total строки 2 лежат orderkey и status. Процессор подтягивает cache line ради одного total — а вместе с ним в кэш попадают ненужные сейчас orderkey и status. Кэш забивается мусором, на каждое значение total — почти отдельная линия.

Колоночная раскладка. Все total лежат подряд в Block B. Процессор подтягивает cache line — и в ней сразу 8 значений total (если bigint, 8 байт). Восемь полезных значений за одно чтение памяти. Кэш используется полностью, обращений к памяти в разы меньше.

Векторизация: батчи вместо строк

Колоночная раскладка раскрывает второй механизм скорости — векторизацию.

Trino — векторизованный движок: операторы обрабатывают данные батчами значений, а не по одной строке. Оператор filter не вызывается «для строки 1, потом для строки 2». Он получает Block столбца и прогоняет предикат по массиву значений в тесном цикле.

Почему это быстро. Во-первых, накладные расходы: вызов кода, проверки, ветвления — всё это происходит раз на батч, а не раз на строку. Во-вторых — тесный цикл по непрерывному массиву идеален для процессора: предсказуемый доступ к памяти, и компилятор (а в случае JVM — JIT) может применить SIMD — Single Instruction Multiple Data, инструкции, обрабатывающие несколько значений одной командой процессора.

Колоночность и векторизация работают в паре: вектор для обработки — это и есть Block, непрерывный массив значений столбца. Построчная модель такой батч-обработки не позволяет в принципе — там значения столбца не лежат подряд.

Trino написан на Java, и это накладывает рамки: JVM-векторизация ограничена тем, что умеет JIT-компилятор. В свежих релизах Trino добавляет и более явную векторизацию: например, движок детектит поддержку набора инструкций AVX-512 у процессора и использует его для ускорения сериализации блоков и подавления null. Но базовый принцип — обработка Block-ами в тесных циклах — работает независимо от этого.

Dictionary blocks: экономия памяти и CPU

Не все Block-и — простые массивы. Один из важных видов — dictionary block (словарный блок).

Идея — для столбца с малым числом уникальных значений при большом числе строк. Пример: столбец country на миллион строк, а уникальных стран — 50. Хранить миллион строковых значений 'Germany', 'France'… — расточительно: одни и те же строки повторяются тысячи раз.

Dictionary block хранит данные иначе, в двух частях:

1. Словарь (dictionary) — компактный список уникальных значений: 50 названий стран, каждое один раз.
2. Массив индексов (ids) — для каждой из миллиона строк маленькое целое число: индекс её значения в словаре.

Вместо миллиона строк — словарь из 50 строк плюс миллион маленьких целых. Экономия памяти кратная. Но выигрыш не только в памяти — он и в CPU. Оператор может работать прямо по словарю: чтобы применить функцию к столбцу, достаточно применить её к 50 значениям словаря, а не к миллиону строк. Один и тот же 'Germany' не пересчитывается тысячи раз.

Родственный механизм — RLE, run-length encoding: если в блоке подряд идёт много одинаковых значений, хранится значение и число повторов. Частный, но яркий случай — блок, где все значения одинаковы: хранится одно значение и счётчик. Dictionary-блоки и RLE особенно полезны в операциях вроде UNNEST и в join-ах, где данные естественно содержат повторы. Trino создаёт такие блоки автоматически, когда это выгодно, — отдельно их включать не нужно.

Page и Block в общей картине

Соберём весь модуль воедино через Page. Distributed planning дал дерево стадий. Стадии разворачиваются в задачи на воркерах. Задачи — в драйверы, цепочки операторов. Операторы передают друг другу данные Page-ами. И вот теперь мы знаем, что такое Page изнутри: набор Block-ов, по одному на столбец, в колоночной раскладке. Колоночность даёт эффективное использование cache line процессора; векторизация — обработку Block-ов батчами с возможным SIMD; dictionary-блоки — экономию памяти и CPU на повторяющихся значениях. Между стадиями Page-и сериализуются и идут через exchange.

Page и Block — это фундамент, на котором стоит вся скорость Trino. MPP-распределённость раздаёт работу по кластеру; pipeline-исполнение гонит данные потоком; а колоночный формат Page с векторизованными операторами выжимает максимум из каждого ядра процессора. Вот теперь таксономия пройдена до самого железа.

Попробуй сам

Эффекты колоночного формата косвенно видны в EXPLAIN ANALYZE:

1. Выполните EXPLAIN ANALYZE SELECT sum(totalprice) FROM tpch.sf10.orders. Запрос трогает один столбец из многих. Подумайте, как колоночность Block помогает: читается и обрабатывается только нужный столбец.
2. Сравните SELECT sum(totalprice) FROM tpch.sf10.orders и SELECT * FROM tpch.sf10.orders LIMIT 1000000. Первый трогает один столбец, второй — все. Сопоставьте объёмы обработанных данных.
3. Выполните агрегацию по столбцу малой кардинальности — SELECT orderstatus, count(*) FROM tpch.sf10.orders GROUP BY orderstatus (у orderstatus всего несколько значений). Это сценарий, где уместно словарное кодирование.
4. Сформулируйте письменно: почему построчная раскладка хуже использует cache line процессора, чем колоночная, и как dictionary block экономит и память, и CPU.