Линия MonetDB -> X100/Vectorwise: откуда взялась векторизация

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

Понять историю векторизации важно не ради дат. Каждый шаг этой эволюции был ответом на конкретную проблему производительности предыдущего шага. Пройдя её, вы поймёте, почему векторизованный движок устроен именно так, а не просто запомните, что он «быстрый». Это фундамент для модуля про векторизованный движок, где мы спустимся до уровня кэшей процессора и регистров — а без сегодняшнего контекста те детали повисли бы в воздухе.

В этом уроке — три остановки: классический построчный движок и его беда, MonetDB и его противоположная беда, и X100/Vectorwise, нашедший баланс, который и достался DuckDB. Каждая остановка — это конкретная инженерная проблема и попытка её решить; вместе они складываются в логичную историю, в конце которой стоит векторизованный движок DuckDB. Пройдём её по порядку, шаг за шагом.

Отправная точка: построчный движок и его проблема

Классические СУБД (PostgreSQL, MySQL, SQLite) исполняют запросы по модели Volcano — её также называют итераторной или tuple-at-a-time моделью.

Идея проста. План запроса — это дерево операторов: scan, filter, join, aggregate. У каждого оператора есть метод next(), возвращающий одну строку. Корневой оператор вызывает next() у дочернего, тот — у своего дочернего, и так до листьев. Строки «протягиваются» через дерево по одной.

Модель элегантна: операторы единообразны, легко комбинируются, и добавить новый тип оператора просто — достаточно реализовать next(). Именно за элегантность и простоту Volcano-модель стала классической и десятилетиями применялась в большинстве СУБД. Для своего времени и для транзакционных нагрузок она была удачным выбором. Но у неё есть фундаментальная проблема производительности — накладные расходы на каждую строку — и эта проблема становится критичной именно на аналитических нагрузках, которые в эпоху создания Volcano ещё не были массовыми.

Чтобы обработать одну строку, движок делает массу служебной работы: вызов виртуального метода next() (а это непрямой вызов через указатель — процессору трудно его предсказать), интерпретацию выражений (для каждой строки заново разбирается, что price * quantity — это умножение), проверку типов. Полезная работа — собственно умножение двух чисел — занимает наносекунды. Служебная обвязка вокруг неё — в разы больше.

На OLTP это незаметно: транзакция трогает несколько строк. На OLAP это катастрофа: запрос сканирует 100 миллионов строк, и служебная обвязка умножается на 100 миллионов. Движок тратит большую часть времени не на вычисления, а на интерпретацию и вызовы. Иными словами, проблема Volcano-модели не была «ошибкой» — она была невидима, пока аналитические нагрузки оставались редкими. Когда аналитика данных стала массовой, та же модель из элегантного решения превратилась в узкое место, и понадобился другой подход. Эволюция, которую мы разбираем, — это история о том, как изменившиеся нагрузки потребовали изменить движок.

Первая крайность: MonetDB и column-at-a-time

MonetDB — колоночная аналитическая СУБД, разработанная в CWI (предшественник DuckDB по той же линии). MonetDB атаковал проблему Volcano радикально: он отказался от обработки по строке и стал обрабатывать целую колонку за раз (column-at-a-time, full materialization).

Логика такая. Раз накладные расходы платятся за каждую единицу обработки — сделаем единицу максимально большой. Не строка, а вся колонка целиком. Оператор фильтра получает на вход весь массив колонки price (все 100 миллионов значений) и за один проход, плотным циклом без виртуальных вызовов, обрабатывает его полностью. Результат — тоже целый массив — передаётся следующему оператору.

Это убило накладные расходы на строку. Плотный цикл по массиву — то, что процессор исполняет максимально эффективно: предсказуемо, конвейерно, с SIMD. На вычислительной части MonetDB был очень быстр и доказал: колоночная обработка массивами — правильное направление.

Но возникла противоположная проблема — материализация. Каждый оператор должен полностью построить свой результирующий массив в памяти, прежде чем отдать его дальше. Промежуточные результаты — это полноразмерные колонки.

Представьте цепочку из нескольких операторов над колонкой в 100 миллионов значений. Каждый оператор материализует свой полный промежуточный массив в RAM. Память расходуется огромными объёмами на промежуточные данные. И, что ещё хуже для скорости, эти массивы не помещаются в кэш процессора — они живут в основной памяти. Каждый оператор пишет свой результат в RAM, следующий читает его из RAM обратно. Данные постоянно ходят между процессором и памятью, а память по сравнению с кэшем медленная.

Итог: MonetDB решил проблему накладных расходов на строку, но создал проблему материализации и нагрузки на память. Volcano был слишком мелкозернистым; MonetDB — слишком крупнозернистым.

Здесь стоит обратить внимание на одну деталь, важную для понимания всего курса: разрыв в скорости между кэшем процессора и основной памятью огромен. Доступ к данным в кэше — это единицы тактов процессора; доступ к данным в основной памяти, если их нет в кэше, — в десятки, а то и сотни раз дольше. Процессор, ожидающий данные из памяти, простаивает. Поэтому, когда MonetDB гоняет полноразмерные промежуточные массивы через основную память, проблема не в самих операциях записи и чтения как таковых — проблема в том, что процессор бо́льшую часть времени ждёт память, вместо того чтобы вычислять. Любой движок, который хочет быть по-настоящему быстрым на современном железе, должен удерживать активные данные в кэше — и именно эту цель преследует выбор размера единицы обработки.

Баланс: X100 / Vectorwise и векторизация

Решение нашли в CWI же, в проекте X100 (научная работа Peter Boncz и коллег, около 2005 года). X100 позже стал коммерческим продуктом под названием Vectorwise. Это и есть рождение векторизованного исполнения в современном виде.

Идея X100 — компромисс между двумя крайностями. Не строка (слишком мелко, как Volcano). Не вся колонка (слишком крупно, как MonetDB). А vector — небольшой блок значений одной колонки фиксированного размера: например, около двух тысяч значений.

Операторы обмениваются не строками и не полными колонками, а векторами. Filter получает вектор из ~2000 значений price, обрабатывает его плотным циклом, отдаёт следующему оператору вектор-результат.

Обратите внимание: дерево операторов при этом сохраняется — то самое дерево из Volcano-модели, с теми же scan, filter, join, aggregate. X100 не выбросил структуру Volcano, он изменил только одно: что именно течёт между операторами. Была строка — стал вектор. Это важная мысль: векторизация — не отказ от модели операторов, а смена гранулярности обмена внутри неё. Поэтому векторизованный движок сохраняет элегантность и комбинируемость Volcano (операторы по-прежнему единообразны и легко соединяются в дерево), но избавляется от её главной беды — платы за каждую строку. Лучшее от обеих сторон: структура от Volcano, гранулярность от колоночной обработки.

Почему этот размер — золотая середина? Два соображения, оба про железо.

Накладные расходы амортизируются. Виртуальный вызов и накладная обвязка платятся один раз на вектор, а не на строку. ~2000 значений за один вызов — служебная стоимость размазывается на тысячи значений и становится пренебрежимой. Проблема Volcano решена.

Вектор помещается в кэш процессора. Это ключевое отличие от MonetDB. Блок из ~2000 значений достаточно мал, чтобы целиком лежать в кэше процессора (L1/L2). Конвейер операторов работает так: оператор обработал вектор — вектор всё ещё в кэше — следующий оператор берёт его прямо из кэша, не обращаясь к медленной основной памяти. Промежуточные данные не материализуются полноразмерными массивами в RAM. Проблема MonetDB решена.

Внутри обработки одного вектора по-прежнему плотный цикл по массиву — а значит, доступны SIMD-инструкции (одна инструкция процессора обрабатывает сразу несколько значений). Векторизация совмещает скорость колоночной обработки MonetDB с компактностью, которая удерживает данные в кэше.

Где в этой линии DuckDB

DuckDB — прямой наследник линии MonetDB -> X100/Vectorwise. Он создан в той же группе CWI людьми, выросшими в этой исследовательской традиции, и его движок исполнения — векторизованный, ровно по принципу X100. То есть DuckDB — не сторонняя реализация чужой идеи, а продолжение исследовательской линии теми же людьми и в том же институте, где эта линия и развивалась.

DuckDB не скопировал X100 буквально — он добавил многое своё: push-based исполнение вместо pull, morsel-driven параллелизм, современные схемы сжатия. Но фундамент исполнителя — векторизация — это наследие X100. В DuckDB размер вектора зафиксирован константой STANDARD_VECTOR_SIZE со значением 2048. Почему именно 2048, как устроены Vector и DataChunk, какие бывают физические типы векторов — это содержание модуля 05. Сейчас важно другое: вы знаете, откуда взялась векторизация и какие две проблемы она решает одновременно. С этим контекстом модуль про векторизованный движок будет не набором фактов, а понятной инженерной историей.

Почему важно знать эту эволюцию

Можно было бы просто сказать «DuckDB — векторизованный движок, и поэтому быстрый», и идти дальше. Но без истории это утверждение остаётся заклинанием. Пройдя эволюцию, вы получаете кое-что более ценное, чем факт.

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

Во-вторых, история показывает важный общий принцип проектирования высокопроизводительных систем: производительность определяется гранулярностью. Volcano и MonetDB различаются не алгоритмами, а размером единицы обработки — строка против колонки. Этот же вопрос «какого размера порция работы» возникнет в курсе ещё не раз: в morsel-driven параллелизме (какого размера morsel), в storage-формате (какого размера row group и блок). Эволюция векторизации — первый и самый наглядный пример того, как выбор гранулярности решает производительность.

В-третьих, вы видите, что DuckDB — не изолированное изобретение, а звено непрерывной линии исследований CWI. MonetDB научил, что колоночная обработка массивами — правильно. X100 нашёл правильную гранулярность. DuckDB взял этот фундамент и добавил современные слои. Понимая линию, вы понимаете и то, почему остальным внутренностям DuckDB можно доверять: за ними стоят два десятилетия итераций, а не одна догадка.

Попробуй сам

Закрепите логику эволюции, рассуждая количественно.

Возьмите запрос, сканирующий таблицу на 100 миллионов строк с простым фильтром по одной колонке. Прикиньте на бумаге для каждой из трёх моделей:

1. Volcano: сколько раз будет вызван метод next() для прохода через один оператор? (Подсказка: единица — строка.)
2. Column-at-a-time (MonetDB): сколько вызовов на оператор, и какого размера промежуточный массив каждый оператор материализует в памяти?
3. Vector-at-a-time (DuckDB): при размере вектора 2048 — сколько векторов составят 100 миллионов строк, и, значит, сколько вызовов на оператор?

Сравните три числа вызовов и подумайте: в модели DuckDB накладные расходы вызова делятся на 2048 значений, а промежуточный вектор при этом помещается в кэш процессора. Запишите, какую проблему Volcano и какую проблему MonetDB это решает. Этот расчёт — мостик к модулю 05, где мы разберём, почему выбрана именно константа 2048.