Почему векторизация бьёт построчные движки

Это финальный урок модуля про движок DuckDB. Шесть предыдущих уроков разбирали части: модель vector-at-a-time, число 2048, структуры Vector и DataChunk, физические типы, selection vector и validity mask, push-исполнение и конвейер компиляции. Каждая часть имела смысл сама по себе. Теперь соберём их в одну картину и ответим на главный вопрос модуля прямо: почему векторизованный движок на аналитическом запросе обгоняет построчный движок и интерпретируемый SQL — не на проценты, а в разы.

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

Arrow в DataFusion: RecordBatch и compute kernels Этот урок — про эти четыре механизма и про то, как они работают вместе.

Механизм 1: амортизация накладных расходов

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

Векторизация делит накладные расходы на размер вектора. Один вызов функции обрабатывает не строку, а DataChunk примерно из 2048 значений. Интерпретация выражения — «какой оператор, какой тип, какая функция» — происходит один раз на вектор, а затем плотный цикл применяет это решение к 2048 значениям. Стоимость накладных расходов на одно значение падает примерно в 2048 раз и становится пренебрежимой.

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

Механизм 2: дружелюбие к кэшу

Второй механизм — кэш процессора, к которому мы обращались в уроке про число 2048. Напомним порядок величин: доступ к L1-кэшу — несколько тактов, доступ к оперативной памяти — сотни тактов, разрыв примерно в сто раз. Процессор, ждущий данные из RAM, простаивает.

Векторная модель дружелюбна к кэшу по двум причинам. Первая — рабочий набор помещается в кэш: вектор из 2048 значений это килобайты, несколько векторов оператора — десятки килобайт, это влезает в L1/L2. Оператор работает с данными, которые уже в быстрой памяти. Вторая — колоночный доступ линеен: DataChunk хранит колонку плотным вектором, и оператор проходит его последовательно, адрес за адресом. Линейный доступ идеален для процессора — работает аппаратный prefetch: процессор, видя линейный паттерн, заранее подтягивает следующие данные в кэш, пока считает текущие.

Построчный движок проигрывает по обоим пунктам. Строчное хранение разбрасывает значения одной колонки по памяти — между ними лежат другие колонки, доступ к нужной колонке прыгает по адресам, prefetch не срабатывает. И построчная обработка постоянно перескакивает между операторами и структурами, рабочий набор не локализован.

Механизм 3: SIMD-инструкции

Третий механизм — SIMD, к которому мы обращались в уроке про 2048. SIMD (Single Instruction, Multiple Data) — режим процессора, где одна инструкция обрабатывает несколько значений сразу: одно SIMD-сложение складывает, скажем, восемь пар чисел за такт вместо одной.

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

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

Механизм 4: предсказание ветвлений

Четвёртый механизм тоньше остальных и часто недооценивается — предсказание ветвлений (branch prediction).

Современный процессор исполняет инструкции конвейером: пока одна инструкция считается, следующие уже загружаются и начинают исполняться. Но на условном переходе (if) процессор не знает заранее, какая ветка выполнится. Он угадывает — это и есть branch prediction — и спекулятивно исполняет предсказанную ветку. Если угадал — конвейер не прерывается. Если не угадал — случается branch misprediction: спекулятивно начатая работа выбрасывается, конвейер сбрасывается и наполняется заново. Один промах предсказания стоит десятки тактов.

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

Векторный плотный цикл устроен иначе. Решения «какой тип, какая функция» приняты один раз до цикла, а сам цикл — это однообразная арифметика без условных переходов на каждом значении. Здесь предсказателю нечего угадывать: ветвлений в горячем цикле почти нет. А там, где они нужны — например, проверка NULL — векторная модель их минимизирует: validity mask проверяется целиком один раз, и если NULL-ов нет, цикл идёт вообще без проверок (механизм из урока про validity mask). Векторизация превращает код с непредсказуемыми ветвлениями в код почти без ветвлений — а такой код процессор исполняет на полной скорости конвейера.

Почему интерпретируемый построчный SQL — худший случай

Соберём всё против конкретного антипода — построчного движка с интерпретацией выражений, как в классических OLTP-СУБД на аналитической нагрузке.

Это не один проигрыш, а пять, и они перемножаются. Построчный интерпретируемый движок на каждой строке: делает вызовы функций, заново интерпретирует выражение, прыгает по памяти с промахами кэша, не может задействовать SIMD и спотыкается на непредсказуемых ветвлениях. Каждый фактор замедляет в несколько раз, и вместе они дают разрыв в десятки раз на аналитическом запросе. Именно поэтому SQLite или PostgreSQL — отличные СУБД для своей задачи (OLTP, транзакции по нескольку строк) — кратно медленнее DuckDB на сканировании и агрегации миллионов строк. Дело не в качестве кода этих систем, а в архитектуре: построчная модель структурно не способна так использовать процессор.

Итог модуля. Векторизованный движок DuckDB быстр на аналитике не по одной причине, а по четырём, и все четыре упираются в железо. Амортизация: накладные расходы и интерпретация делятся на 2048. Кэш: рабочий набор-вектор живёт в L1/L2, колоночный доступ линеен и подхватывается prefetch. SIMD: плотный массив одного типа позволяет обрабатывать несколько значений за такт. Предсказание ветвлений: горячий цикл почти без условных переходов, конвейер процессора не сбрасывается. Эти механизмы перемножаются и дают кратный отрыв от построчного интерпретируемого движка. А структуры из предыдущих уроков — DataChunk, физические типы, selection vector, validity mask, push-модель — это и есть инженерная конструкция, которая заставляет все четыре механизма работать вместе.

Попробуй сам

Задания на синтез и проверку.

1. Возьмите DuckDB и построчную СУБД (SQLite). На одном большом датасете (миллионы строк) замерьте время аналитического запроса (GROUP BY с агрегатами) и точечного запроса по ключу (WHERE id = ...). На какой задаче разрыв велик, а на какой — нет? Объясните через четыре механизма.
2. Для каждого из четырёх механизмов (амортизация, кэш, SIMD, предсказание ветвлений) объясните своими словами, почему построчная модель не может им воспользоваться.
3. Объясните, почему четыре механизма дают мультипликативный (перемножающийся), а не аддитивный эффект.
4. Branch misprediction стоит десятки тактов. Объясните, почему горячий векторный цикл «прибавить 1 к 2048 значениям» почти не вызывает промахов предсказания, а построчная обработка — вызывает.
5. Сформулируйте, почему DuckDB не делает построчные OLTP-СУБД устаревшими. Для какой нагрузки векторизация не даёт выигрыша и почему?