Selection vector, validity mask и unified format

В предыдущих уроках мы дважды упомянули selection vector — как часть DICTIONARY_VECTOR и как механизм ленивой материализации — но не разобрали его устройство. Также мы обещали раскрыть unified vector format. И есть третий механизм, который мы пока обходили: как вектор представляет NULL-значения. Этот урок собирает три низкоуровневые структуры вместе: selection vector, validity mask и unified vector format.

Эти три механизма — то, без чего векторизованная модель не работала бы на практике. Selection vector позволяет фильтровать без копирования. Validity mask отслеживает NULL так, чтобы это не ломало плотные циклы. Unified format избавляет операторы от разбора пяти физических типов. Все три — про то, как сохранить главное достоинство векторизации (плотные быстрые циклы) при наличии фильтров, NULL-ов и разных представлений.

Selection vector: уровень косвенности

Начнём с задачи. Оператор WHERE amount > 100 применён к вектору из 2048 значений. Условию удовлетворили, скажем, 600 строк. Что оператор должен передать дальше по конвейеру?

Наивный ответ — создать новый вектор и скопировать в него 600 прошедших значений. Это материализация: выделение памяти и физическое копирование 600 значений. На каждом фильтре, на каждом чанке.

Selection vector убирает копирование. Это массив целочисленных индексов, который вводит уровень косвенности (indirection) между «логической» позицией и «физической». Вместо «значение по логической позиции i — это physical_array[i]» становится «значение по логической позиции i — это physical_array[selection_vector[i]]». Selection vector говорит: чтобы получить i-е логическое значение, посмотри в физический массив по индексу selection_vector[i].

Для фильтра это работает так. Исходный вектор amount остаётся нетронутым — все 2048 значений на месте. Оператор создаёт selection vector — массив из 600 индексов, перечисляющий позиции прошедших строк: [3, 7, 12, 15, ...]. Логически результат — это вектор из 600 значений, но физически значения не скопированы: «вектор из 600» — это исходный массив плюс selection vector из 600 индексов.

Преимущества selection vector. Первое — нет копирования значений: создаётся только массив индексов, который и сам компактен (целые числа), и часто короче исходных данных. Второе — общий selection vector на весь DataChunk: фильтр по одной колонке порождает один selection vector, и он применяется ко всем колонкам чанка разом — отфильтровать region, amount, qty это применить тот же selection vector. Третье — selection vector-ы композируются: фильтр после фильтра — это не двойное копирование, а комбинация индексов.

Selection vector — это и есть тот механизм, через который DICTIONARY_VECTOR ссылается на словарь, и через который реализуется ленивая материализация из прошлого урока. Косвенность через массив индексов — сквозной приём движка.

Validity mask: NULL как битовая маска

Второй механизм решает проблему NULL. NULL — это «значения нет». Но вектор — это плотный массив, в нём для каждой позиции что-то лежит. Как представить «значения нет» в плотном массиве, не ломая его?

Плохие варианты: хранить специальное «магическое» значение-маркер (но любое значение может оказаться настоящими данными) или делать каждое значение «значение плюс флаг» (раздувает данные и ломает выравнивание). DuckDB использует validity mask — отдельную битовую маску.

Validity mask — это битовый массив, идущий рядом с вектором: один бит на каждое значение. Бит равен 1, если значение в этой позиции валидно (не NULL), и 0, если значение NULL. Для вектора из 2048 значений validity mask — это 2048 бит, то есть всего 256 байт.

Vector amount:   [120,  ?,   200,  150,  ?,   75 ]
validity mask:   [ 1,   0,   1,    1,    0,   1  ]
                          NULL            NULL

Почему битовая маска — хорошее решение. Компактность: 2048 бит это 256 байт — крошечная добавка к вектору. Скорость: проверить, есть ли в векторе вообще хоть один NULL, можно одним взглядом на маску; если вся маска — единицы, оператор обрабатывает вектор плотным циклом вообще без проверок на NULL, на полной скорости. Это важно: данные часто не содержат NULL, и validity mask позволяет в этом частом случае не платить за поддержку NULL ничего. Когда NULL есть — маска проверяется побитно, что всё равно дёшево.

Когда возникает CONSTANT для validity

Маленькая, но изящная деталь: validity mask сама может быть в «константном» состоянии. Если в векторе нет ни одного NULL, маске не нужно хранить 256 байт единиц — достаточно флага «все валидны». Если все значения NULL — флаг «все NULL». Полный битовый массив маски нужен только в смешанном случае. Это тот же принцип CONSTANT_VECTOR, применённый к маске: не хранить то, что одинаково.

Unified vector format: единый вид для оператора

Третий механизм закрывает вопрос, поставленный в прошлом уроке. Вектор может быть пяти физических типов (FLAT, CONSTANT, DICTIONARY, SEQUENCE, FSST) и может иметь selection vector и validity mask. Если бы каждый оператор разбирал все эти случаи, код операторов был бы громоздким и хрупким.

Unified vector format — это канонический интерфейс доступа к вектору, к которому можно привести вектор любого физического типа. Когда оператору нужно прочитать значения вектора единообразно, он приводит вектор к unified-формату и дальше работает по одному коду, не зная и не заботясь, каким был исходный физический тип.

Unified vector format даёт оператору три вещи в едином виде: указатель на массив данных, selection vector (как добраться от логической позиции к физической) и validity mask (какие значения NULL). Через эти три компонента любой вектор — FLAT, CONSTANT или DICTIONARY — читается единообразно: логическое значение i это data[selection.index(i)], валидность — по validity mask.

Здесь есть тонкий баланс. Специализированные операторы DuckDB по горячим путям всё же используют знание физического типа напрямую — например, видя CONSTANT_VECTOR, оператор обрабатывает его за одну операцию вместо 2048, и это важная оптимизация. Unified format — это «общий знаменатель» для случаев, когда такая специализация не нужна или слишком сложна: он гарантирует, что любой вектор можно обработать единообразно, не плодя пять веток. Движок сочетает оба подхода: быстрые спецпути там, где они дают выигрыш, и unified format как универсальный fallback.

Итог урока: три низкоуровневых механизма делают векторизацию практичной. Selection vector вводит косвенность через массив индексов — фильтр и срез не копируют значения, один selection vector применяется ко всем колонкам чанка. Validity mask хранит NULL отдельной битовой маской — это компактно и позволяет вектору без NULL обрабатываться плотным циклом без единой проверки. Unified vector format даёт оператору канонический вид любого вектора — данные, selection, validity — чтобы не писать код под каждый из пяти физических типов. Все три служат одной цели: сохранить плотные быстрые циклы векторной модели при наличии фильтров, NULL-ов и разнообразия представлений.

Попробуй сам

Задания на размышление и расчёт.

1. Фильтр WHERE x > 0 оставил 800 строк из 2048. Опишите словами, что физически создаёт оператор и что остаётся нетронутым. Сколько индексов в selection vector?
2. Посчитайте размер validity mask для вектора из 2048 значений (один бит на значение). Сравните эту добавку с размером самого вектора INTEGER (8 КБ).
3. Объясните, почему вектор без единого NULL обрабатывается быстрее вектора с NULL-ами. Какую роль здесь играет проверка validity mask целиком?
4. У DataChunk несколько колонок. Объясните, почему фильтр по одной колонке порождает один selection vector, применимый ко всем колонкам чанка.
5. Зачем нужен unified vector format, если специализированные операторы и так умеют работать с конкретными физическими типами? В каких случаях unified-формат полезен?