columnar-engine

Учебный колоночный аналитический движок, написанный с нуля на C++20. Проект реализует собственный бинарный формат хранения данных (BRUH), набор кодеков со сжатием и блочное исполнение запросов через дерево операторов. В качестве целевой нагрузки взят ClickBench: все 43 запроса собраны вручную в виде деревьев операторов, а результаты сверены с DuckDB на одном датасете.

SQL-парсера и оптимизатора в движке нет: планы запросов строятся напрямую кодом. Формат проектировался как неизменяемый, поэтому изменения отдельных строк, транзакции и JOIN не поддерживаются — ClickBench работает над одной плоской таблицей.

Что реализовано

• Собственный колоночный формат BRUH, вдохновленный Apache Parquet: разбиение на группы строк фиксированного размера, по одному column chunk на колонку, метаданные со смещениями и статистиками в конце файла.
• Шесть кодеков (Plain, RLE, FOR, Delta, Bit-packing, Dictionary) с авто-выбором по статистическим свойствам колонки, поверх — блочное сжатие LZ4 или Zstd.
• Статистики min/max/null на каждый column chunk и пропуск заведомо неподходящих групп строк при фильтрации.
• Чтение файла через mmap с ленивой подгрузкой страниц и чтением только запрошенных колонок.
• Представление колонок в памяти: плотные и словарно-кодированные строки, битовое сжатие null-масок и булевых данных, дешевая проверка физического вида колонки без RTTI.
• Push-based конвейер операторов (Scan, Filter, Project, TopN, GlobalAggregation, HashAggregation) с батчами фиксированного размера, selection vector и поздней материализацией.
• Хэш-агрегация с таблицами групп, специализированными под характерную форму ключа, ареной строк для строковых ключей и буфером состояний агрегатов в виде структуры массивов.
• Система выражений (константы, ссылки на колонки, арифметика, сравнения, строковые и временные функции, условный оператор, замена по регулярному выражению через RE2).

Архитектура

Система разбита на слои, каждый из которых зависит только от нижележащих:

Слой	Назначение
apps	Приложения: конвертер CSV ⇔ BRUH и запускатель запросов ClickBench
exec	Операторы, выражения, kernels, хэш-агрегация и таблицы групп
core	Иерархия Column, Batch, Schema, кодеки и авто-выбор кодека
bruh / csv	Бинарный формат BRUH и чтение/запись CSV
util	bit_vector, string_arena, mmap, буферизованные файлы, сжатие LZ4/Zstd

Формат хранения. Файл состоит из последовательности групп строк, в конце лежит блок метаданных (схема, число строк, описания всех column chunk со смещениями, размерами, кодеком, типом сжатия и статистикой). Размер метаданных записан в фиксированном месте в конце файла, поэтому весь блок читается одним обращением с конца. Статистики извлекаются лениво и кэшируются.

Исполнение запроса. Источник проталкивает батчи в цепочку приемников; после фильтрации батч несет selection vector, а не уплотненные данные, чтобы избежать лишних копирований. Перед запуском дерево проходит этап планирования, на котором собирается минимальный набор нужных колонок, а фильтр перед сканированием включает пропуск групп строк по статистике.

Хэш-агрегация. Приемник опирается на таблицу групп (GroupKeyTable) и буфер состояний агрегатов (AggStateBuffer). Фабрика выбирает специализацию таблицы под форму ключа: одно целое, строка, пара целых, целое со строкой, пара целых со строкой либо обобщенный составной ключ. В основе лежит absl::flat_hash_map; строковые ключи хранятся как невладеющие ссылки на арену, а для словарных колонок хэши значений предвычисляются.

Результаты

Сравнение с DuckDB на полном датасете ClickBench (~75 ГБ в исходном CSV), одинаковое оборудование и условия запуска. Геометрическое среднее времени по всем 43 запросам:

Режим	columnar-engine	DuckDB
Холодный	14 900 мс	2761 мс
Горячий	2839 мс	884 мс

Сконвертированный файл со сжатием LZ4 занимает ~12.5 ГБ против ~22.1 ГБ у DuckDB, то есть примерно на 44% компактнее за счет специализированных кодеков. На части запросов движок не уступает DuckDB, а на отдельных паттернах оказывается быстрее.

Структура репозитория

include/        публичные заголовки (core, bruh, csv, exec, util)
src/            реализация по тем же модулям
apps/
  converter/        CSV ⇔ BRUH
  clickbench/       запуск запроса ClickBench над файлом BRUH
tests/          тесты на GoogleTest
script/         сборка, конвертация, запуск запросов, схема hits
cmake/          подтягивание зависимостей через FetchContent

Сборка

Нужны CMake ≥ 3.20, компилятор с поддержкой C++20, Ninja и git. Зависимости (Abseil, RE2, LZ4, Zstd, для тестов — GoogleTest) скачиваются автоматически через FetchContent, ставить их вручную не требуется.

Быстрый путь через скрипты:

bash script/setup.sh      # проверяет/доустанавливает тулчейн (нужен apt)
bash script/build.sh      # Release-сборка converter и clickbench_runner в build-release/

Либо напрямую через CMake:

cmake -S . -B build-release -G Ninja -DCMAKE_BUILD_TYPE=Release
cmake --build build-release --target converter clickbench_runner -j

Полезные опции конфигурации:

Опция	По умолчанию	Назначение
COLUMNAR_BUILD_TESTS	ON	Сборка тестов
COLUMNAR_ENABLE_NATIVE	ON	Сборка с -march=native
COLUMNAR_ENABLE_IPO	ON	LTO, если поддерживается тулчейном
COLUMNAR_ALLOCATOR	auto	Подключаемый аллокатор: auto, none, mimalloc, jemalloc

Использование

Конвертация CSV в формат BRUH требует файла схемы вида имя,тип,nullable по строке на колонку. Для датасета ClickBench схема лежит в script/hits.schema.csv.

# CSV -> BRUH
build-release/apps/converter/converter \
  --mode=csv2bruh \
  --schema=script/hits.schema.csv \
  --input=hits.csv \
  --output=hits.bruh

# BRUH -> CSV
build-release/apps/converter/converter \
  --mode=bruh2csv \
  --input=hits.bruh \
  --output=hits.csv

Запуск запроса ClickBench по номеру (0–42); результат пишется в CSV или в stdout:

build-release/apps/clickbench/clickbench_runner \
  --input=hits.bruh \
  --query=33 \
  --output=result.csv

То же самое через скрипты-обертки, которые при необходимости сами собирают проект:

bash script/convert.sh hits.csv hits.bruh
bash script/run_query.sh 33 hits.bruh result.csv run.log

Тесты

cmake -S . -B build-debug -G Ninja -DCMAKE_BUILD_TYPE=Debug -DCOLUMNAR_BUILD_TESTS=ON
cmake --build build-debug -j
ctest --test-dir build-debug --output-on-failure

Тесты покрывают CSV, формат BRUH, кодеки, сжатие, исполнение запросов и утилиты.

Лицензия

MIT.