Векторное выполнение запросов

Векторное выполнение запросов — это метод обработки данных в системах управления базами данных (СУБД) и аналитических движках, при котором операции выполняются не над одной строкой (кортежем) за раз, а над набором (вектором) данных, часто умещающимся в регистры процессора. Этот подход позволяет эффективно использовать возможности современных центральных процессоров (ЦП), в частности их векторные инструкции (SIMD — Single Instruction, Multiple Data), и минимизировать накладные расходы на интерпретацию и передачу данных.

История и предпосылки

Традиционные СУБД, начиная с 1970-х годов, использовали модель обработки строк за раз (row-at-a-time, или «Volcano model»). В этой модели каждый оператор (например, фильтрация или соединение) получает одну строку, обрабатывает её и передаёт следующему оператору. Такой подход прост в реализации, но приводит к значительным накладным расходам: на каждую строку выполняется вызов функции, проверка состояния и передача управления. С ростом объёмов данных и увеличением разрыва между скоростью процессора и памяти (так называемая «стена памяти») этот метод стал узким местом.

В начале 2000-х годов, с развитием аналитических и колоночных СУБД (например, MonetDB, C-Store), возникла идея обрабатывать данные не построчно, а поблочно. Векторное выполнение стало эволюционным шагом: вместо одной строки за раз обрабатывается пакет (вектор) из десятков или сотен строк. Первые коммерческие реализации появились в СУБД Vectorwise (разработанной в Центре математики и информатики (CWI) в Нидерландах) и позже в Microsoft SQL Server (начиная с версии 2012 года для аналитических нагрузок). В настоящее время векторное выполнение является стандартом для большинства современных аналитических СУБД, включая ClickHouse, DuckDB, Apache Arrow, а также встроено в движки обработки данных в PostgreSQL (через расширения) и MySQL.

Принцип работы

Векторное выполнение основано на идее пакетной обработки. Вместо того чтобы передавать между операторами плана запроса одну строку, каждый оператор оперирует фиксированным блоком данных — вектором. Размер вектора (обычно от 64 до 1024 элементов) выбирается таким образом, чтобы он помещался в кэш-память процессора (L1 или L2) и мог быть обработан за один проход.

Основные этапы

1. Формирование вектора: Данные из таблицы или промежуточного результата считываются блоками. В колоночных СУБД это особенно эффективно, так как каждая колонка хранится отдельно, и вектор может содержать значения только одной колонки.
2. Применение операций: Оператор (например, фильтрация, проекция, агрегация) применяет одну и ту же инструкцию ко всем элементам вектора. Это позволяет использовать SIMD-инструкции процессора, которые выполняют одну операцию над несколькими элементами данных одновременно.
3. Передача результата: Обработанный вектор передаётся следующему оператору в конвейере. Если результат не помещается в один вектор, оператор может повторять цикл, пока не обработает все данные.

Пример: фильтрация

Предположим, есть таблица с колонкой price, и требуется выбрать строки, где price > 100. При построчной обработке процессор для каждой строки выполняет: загрузку значения, сравнение, условный переход. При векторной обработке загружается вектор из 256 значений price, затем одной инструкцией SIMD выполняется сравнение всех 256 значений с константой 100, и формируется маска (битовая карта) строк, удовлетворяющих условию. Далее по этой маске выбираются только нужные значения.

Преимущества

• Повышение производительности: За счёт использования SIMD-инструкций и уменьшения количества вызовов функций (call overhead) скорость обработки может возрастать в 2–10 раз по сравнению с построчной моделью.
• Эффективное использование кэша: Векторы небольшого размера (обычно до 1024 элементов) хорошо помещаются в кэш-память процессора, что снижает количество обращений к оперативной памяти.
• Снижение накладных расходов на интерпретацию: Векторное выполнение позволяет компилировать часто выполняемые операции (например, фильтрацию) в компактный машинный код, который обрабатывает сразу много данных.
• Масштабируемость: Векторные алгоритмы легче распараллеливать на многоядерных процессорах, так как каждый поток может обрабатывать свой вектор независимо.

Недостатки и ограничения

• Сложность реализации: Разработка векторного движка требует глубокого понимания архитектуры процессора, SIMD-инструкций и управления памятью. Ошибки в оптимизации могут привести к снижению производительности.
• Чувствительность к типу данных: Векторное выполнение наиболее эффективно для однородных данных фиксированной длины (числа, даты). Для строк переменной длины или сложных типов (JSON, массивы) эффективность снижается, так как требуется дополнительная обработка.
• Нагрузка на память: Хотя векторное выполнение уменьшает количество обращений к памяти, оно требует предварительной загрузки больших блоков данных, что может создавать пиковую нагрузку на подсистему памяти.
• Неприменимость для OLTP: Для транзакционных нагрузок (OLTP), где преобладают точечные запросы (поиск одной записи по ключу), векторное выполнение не даёт преимущества, так как накладные расходы на формирование вектора превышают выгоду от его обработки.

Сравнение с другими моделями выполнения

Применение

Векторное выполнение запросов широко используется в:

• Аналитических СУБД (OLAP): ClickHouse, DuckDB, Apache Druid, Greenplum, Amazon Redshift. Эти системы обрабатывают миллиарды строк за секунду при выполнении агрегаций и фильтраций.
• Колоночные хранилища: Apache Parquet, Apache Arrow, где данные хранятся в колоночном формате, что идеально сочетается с векторной обработкой.
• Фреймворки для обработки данных: Apache Spark (начиная с версии 2.0 с Tungsten-движком), Pandas (через библиотеку NumPy), где векторные операции реализованы на уровне массивов.
• СУБД реального времени: TimescaleDB, QuestDB, где требуется высокая скорость вставки и анализа временных рядов.

Реализации в известных СУБД

• ClickHouse: Использует векторное выполнение как основной метод обработки. Размер вектора (по умолчанию 8192 строки) оптимизирован для современных процессоров. Поддерживает SIMD-инструкции SSE4.2, AVX2, AVX-512.
• DuckDB: Векторный движок с размером вектора 2048 строк. Использует JIT-компиляцию для некоторых операций, но основная обработка — векторная.
• Microsoft SQL Server: В аналитическом режиме (columnstore index) использует векторное выполнение с размером вектора 1024 строки. Включено по умолчанию для запросов, затрагивающих большие объёмы данных.
• PostgreSQL: В стандартной поставке не имеет векторного выполнения, но через расширения (например, pgvector для векторного поиска, или Hydra) можно получить частичную поддержку.

Будущее развитие

Векторное выполнение продолжает эволюционировать. Основные направления:

• Адаптивный размер вектора: Автоматический выбор размера вектора в зависимости от типа данных, загрузки процессора и объёма кэша.
• Гибридные модели: Сочетание векторного выполнения с JIT-компиляцией для сложных запросов, где выгода от компиляции перевешивает накладные расходы.
• Поддержка новых типов данных: Оптимизация векторных операций для строк, JSON, геопространственных данных.
• Интеграция с аппаратными ускорителями: Использование GPU, FPGA и специализированных процессоров (например, Intel QAT) для векторной обработки.

Источники

• Boncz, P. A., Zukowski, M., & Nes, N. (2005). MonetDB/X100: Hyper-Pipelining Query Execution. CIDR.
• Abadi, D. J., Boncz, P. A., & Harizopoulos, S. (2009). Column-Oriented Database Systems. VLDB Journal.
• Zukowski, M., & Boncz, P. A. (2012). Vectorwise: A Vectorized Analytical DBMS. IEEE Data Engineering Bulletin.
• Kersten, M. L., et al. (2011). The Researcher’s Guide to the Data Deluge: Query Execution in MonetDB. VLDB.
• Документация ClickHouse: Vectorized Query Execution. ClickHouse, Inc.