Vector-at-a-time против построчной обработки

Любая СУБД исполняет запрос как конвейер операторов: сканирование таблицы, фильтр, агрегация. Вопрос, который определяет всю производительность движка, звучит так: какими порциями данные движутся между операторами этого конвейера? Ответов исторически три, и от выбора зависит, будет движок быстрым или медленным в разы.

DuckDB — векторизованный движок, и это его главное архитектурное решение. Чтобы понять, что такое «векторизация» и почему она быстрая, нужно увидеть две альтернативы, между которыми она стоит: построчную обработку (tuple-at-a-time) и полную материализацию (full materialization). Векторизация — это компромисс между ними, и компромисс на удивление удачный. Этот урок открывает модуль про движок DuckDB и закладывает фундамент: модель vector-at-a-time, на которой держится всё остальное.

Модель первая: построчная обработка (tuple-at-a-time)

Классический подход, придуманный в 1970-х и описанный в архитектуре Volcano, — обрабатывать по одной строке (tuple) за раз. Конвейер операторов работает так: верхний оператор просит у нижнего «дай следующую строку», тот просит у своего нижнего, и так до самого сканирования таблицы. Одна строка проходит весь конвейер сверху донизу, потом следующая.

Модель элегантна и проста. Каждый оператор — это итератор с методом «дай следующую строку». Но у неё есть скрытая, разрушительная цена.

Представьте простую операцию «прибавить 1 к колонке». В построчной модели для каждой строки происходит вызов функции. Миллион строк — миллион вызовов функции сложения. А каждый вызов функции — это не бесплатная операция: настройка стекового фрейма, передача аргументов, переход, возврат. Полезная работа (само сложение) — это один такт процессора. Накладные расходы вокруг неё — десятки тактов. На миллионе строк полезная работа тонет в океане накладных расходов на вызовы.

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

Построчная модель хороша для OLTP-нагрузки: транзакция трогает одну-две строки, накладные расходы на одну строку несущественны. Но аналитический запрос сканирует миллионы строк — и тут построчная модель катастрофически медленна. Именно поэтому OLTP-СУБД вроде SQLite или PostgreSQL, исторически построчные, проигрывают на аналитике.

Модель вторая: полная материализация

Противоположная крайность — полная материализация (full materialization), типичная для ранних колоночных систем вроде классического MonetDB. Здесь каждый оператор обрабатывает всю колонку целиком и материализует (записывает в память) полный результат, прежде чем передать его следующему оператору.

Накладные расходы на вызовы функций исчезают: оператор «прибавить 1» получает всю колонку и проходит её плотным циклом — один вызов на всю колонку, никакой построчной интерпретации. Это очень быстро по части CPU.

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

Полная материализация решила проблему накладных расходов на вызовы, но создала проблему памяти. Это другая крайность того же спектра.

Модель третья: vector-at-a-time

DuckDB выбрал середину — обработку векторами (vector-at-a-time), идею, выросшую из исследований CWI вокруг MonetDB/X100 (он же Vectorwise). Данные движутся по конвейеру не по одной строке и не целыми колонками, а порциями фиксированного размера — векторами. Вектор в DuckDB — это около 2048 значений одной колонки (точное число и его обоснование — тема следующего урока).

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

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

Почему середина выигрывает

Векторизация выигрывает не потому, что она «компромисс», а потому, что она снимает оба узких места одновременно, не создавая новых. Tuple-at-a-time экономит память, но платит за это вызовами. Full materialization экономит вызовы, но платит памятью. Vector-at-a-time экономит и то, и другое: вектор достаточно велик, чтобы амортизировать вызовы (2048 — много), и достаточно мал, чтобы поместиться в кэш (2048 значений — это килобайты, не гигабайты).

Есть и третий, более тонкий выигрыш. Плотный цикл по вектору из 2048 одинаковых значений — это код, который процессор любит. Такой цикл хорошо предсказывается, хорошо конвейеризируется, и компилятор может применить к нему SIMD — векторные инструкции процессора, обрабатывающие несколько значений за один такт. Построчная обработка с её ветвлениями и вызовами этого не позволяет. Векторный цикл превращает аналитику в работу, для которой современный процессор спроектирован.

Эта модель — фундамент всего движка DuckDB. Дальше в модуле мы разберём, почему вектор именно 2048 значений, как устроены Vector и DataChunk, какие бывают физические типы векторов и как push-based исполнение прогоняет векторы через дерево операторов. Но базовая идея уже здесь: данные двигаются порциями, и размер порции выбран так, чтобы одновременно убить накладные расходы и не переполнить кэш.

Попробуй сам

Это концептуальный урок — задания на размышление и наблюдение.

1. Возьмите построчную СУБД (SQLite) и DuckDB. На одинаковом большом CSV-файле (несколько миллионов строк) выполните одинаковый агрегирующий запрос вида SELECT category, count(*), sum(amount) FROM data GROUP BY category. Сравните время. Объясните разницу через модели обработки.
2. Прикиньте арифметику накладных расходов. Если вызов функции стоит условные 20 тактов, а полезная операция — 1 такт, во сколько раз построчная модель медленнее векторной на этой операции? Как меняется ответ, если вектор содержит 2048 значений?
3. Объясните своими словами, почему полная материализация быстра по CPU, но проигрывает на больших данных. Какой ресурс становится узким местом?
4. Подумайте: почему построчная модель (tuple-at-a-time) — разумный выбор для OLTP-СУБД, обслуживающей транзакции по одной-две строки, но плохой для аналитики?