Физические типы вектора: FLAT, CONSTANT, DICTIONARY и другие

В предыдущем уроке мы сказали важную вещь: Vector — это логический интерфейс «массив из N значений колонки», а физически внутри он может быть устроен по-разному. Пора раскрыть это утверждение. У вектора в DuckDB пять физических представлений (physical types), и выбор представления — один из главных приёмов, которыми движок избегает лишней работы.

Идея проста и мощна. Снаружи любой вектор выглядит одинаково — массив значений. Но если все значения вектора одинаковы, хранить 2048 копий бессмысленно — достаточно одной. Если значений мало уникальных — можно хранить словарь и ссылки. Физический тип — это способ хранить вектор экономно, исходя из того, какие в нём данные. Этот урок — про пять физических типов и про то, как они реализуют ленивую материализацию.

FLAT_VECTOR: плотный массив

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

FLAT_VECTOR колонки amount:
позиция:  0    1    2    3    4    5
значение: 120  80   200  150  90   75

FLAT_VECTOR — представление по умолчанию и универсальное: в нём можно представить любые данные, без исключений. Если вектор не подходит ни под одно из специальных представлений, он FLAT. Цена универсальности — память: FLAT_VECTOR всегда занимает полный размер, 2048 значений независимо от того, что в них. Если все 2048 значений равны 100, FLAT_VECTOR всё равно хранит 2048 сотен.

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

CONSTANT_VECTOR: одно значение на всех

CONSTANT_VECTOR применяется, когда все значения вектора одинаковы. Вместо 2048 копий он хранит ровно одно значение — и логически оно «размножено» на все позиции.

CONSTANT_VECTOR: логически [100, 100, 100, ... , 100]  (2048 раз)
физически хранит: 100  (одно значение)

Когда такое возникает? Очень часто. Литерал в запросе (SELECT amount, 'EU' AS region) — колонка region это CONSTANT_VECTOR со значением 'EU'. Результат фильтра, после которого в колонке осталось одно повторяющееся значение. Колонка-параметр. CONSTANT_VECTOR экономит не только память (одно значение вместо 2048), но и время: оператор, получив CONSTANT_VECTOR, может обработать его за одну операцию вместо 2048 — он знает, что значение везде одно.

DICTIONARY_VECTOR: словарь и ссылки

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

DICTIONARY_VECTOR колонки status:
словарь:          ['new', 'paid', 'shipped']
selection vector: [1, 0, 1, 2, 1, 0, 2, 1, ...]
логически:        ['paid','new','paid','shipped','paid','new',...]

Вместо того чтобы хранить 2048 строк (среди которых масса повторов), DICTIONARY_VECTOR хранит три уникальные строки в словаре и 2048 маленьких целочисленных индексов. Это та же идея, что у типа ENUM и у схемы сжатия dictionary encoding (разбирались в других модулях), но здесь — в рантайме, для вектора в памяти.

Но у DICTIONARY_VECTOR есть второе, ещё более важное применение, чем экономия памяти на повторах. Через него реализуется ленивая материализация — приём, на котором держится эффективность всего движка.

SEQUENCE_VECTOR: значения по формуле

SEQUENCE_VECTOR хранит вектор арифметической последовательности — значения, идущие с постоянным шагом, — двумя числами: начальное значение и приращение. Само значение позиции i вычисляется по формуле start + i * increment, в массиве оно не лежит.

SEQUENCE_VECTOR: start = 1000, increment = 1
логически: [1000, 1001, 1002, 1003, 1004, ...]
физически хранит: start=1000, increment=1  (два числа)

Когда возникает последовательность? Типичный случай — номера строк (row id) при сканировании таблицы. DuckDB при чтении присваивает строкам последовательные идентификаторы, и колонка row id — идеальный SEQUENCE_VECTOR: вместо 2048 чисел два числа и формула. Никакой материализации массива.

FSST_VECTOR: сжатые строки

FSST_VECTOR хранит строки в сжатом виде — кодировкой FSST (Fast Static Symbol Table). FSST извлекает часто встречающиеся подстроки в таблицу символов и заменяет их короткими кодами; подробно эта схема разбирается в модуле про компрессию.

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

Ленивая материализация: главный смысл физических типов

Теперь — ключевая идея урока. Зачем движку пять представлений? Не только ради экономии памяти. Главное — ленивая материализация (lazy materialization): возможность выполнять операции, не создавая полные копии данных.

Рассмотрим типичную операцию — LIMIT 5 или взятие среза. Наивно: создать новый вектор и скопировать в него 5 нужных значений из исходного. Это материализация — выделение памяти и физическое копирование.

DuckDB делает иначе. Результат среза — это DICTIONARY_VECTOR, чей selection vector указывает на нужные позиции исходного вектора. Новый вектор не содержит копий значений — он содержит ссылки на исходные данные через selection vector. Срез выполнен без копирования: создан лишь маленький массив индексов.

Тот же принцип работает для фильтра (результат — ссылки на прошедшие строки), для проекции колонок, для многих операторов. Пока возможно, движок передаёт по конвейеру не плотные копии, а компактные представления — DICTIONARY, CONSTANT, SEQUENCE — со ссылками на исходные данные. Полный FLAT_VECTOR материализуется только тогда, когда оператор дальше по конвейеру действительно требует плотные данные. Часто этот момент так и не наступает.

Unified vector format: как операторы справляются с разнообразием

Возникает естественный вопрос. Если вектор может быть пяти разных физических типов, должен ли каждый оператор иметь пять веток кода — отдельную для FLAT, отдельную для CONSTANT, и так далее? Это был бы кошмар поддержки.

Решение — unified vector format. Это канонический «вид» вектора, к которому оператор может привести любой физический тип, чтобы читать его единообразно. Оператор не пишет пять веток: он приводит входной вектор к unified-формату и работает с ним по одному коду. Unified-формат скрывает, был ли вектор FLAT, DICTIONARY или CONSTANT, и даёт оператору единый интерфейс доступа к значениям. Эта структура подробнее разбирается в следующем уроке вместе с selection vector и validity mask.

Итог урока: логический Vector имеет пять физических представлений. FLAT — универсальный плотный массив. CONSTANT — одно значение на всех. DICTIONARY — словарь и ссылки. SEQUENCE — арифметика по формуле. FSST — сжатые строки. Главный смысл этого разнообразия не экономия памяти сама по себе, а ленивая материализация: операции вроде среза и фильтра возвращают компактные представления со ссылками вместо плотных копий, и физическое копирование откладывается до последнего момента. А unified vector format избавляет операторы от необходимости знать про все пять типов — они работают с единым каноническим видом.

Попробуй сам

Задания на размышление и наблюдение.

1. Для каждого из пяти физических типов придумайте конкретный запрос или ситуацию, в которой такой вектор естественно возникает. Например, для CONSTANT_VECTOR — SELECT id, 'active' AS status FROM users.
2. Посчитайте экономию памяти. Вектор из 2048 значений BIGINT (8 байт) как FLAT занимает 16 КБ. Сколько займёт тот же вектор как CONSTANT_VECTOR, если все значения равны? Как SEQUENCE_VECTOR?
3. Объясните своими словами, что такое ленивая материализация и почему DICTIONARY_VECTOR — удобный механизм для её реализации.
4. Операция WHERE amount > 100 оставляет, скажем, 600 строк из 2048. Объясните, как результат можно представить через selection vector без копирования 600 значений.
5. Зачем нужен unified vector format? Что пришлось бы делать каждому оператору, если бы его не было?