Разработчик базы данных Prela столкнулся с классической проблемой: первая версия работала чисто, но ужасно медленно. Каждый оператор (проекция, фильтр, join) материализовал промежуточные результаты, поэтому цепочка операций порождала кучу лишних временных таблиц.
Стандартное индустриальное решение — итераторная модель, когда операторы передают данные строка за строкой через вызовы Iterator.next(). Но это тоже дорого: каждый вызов — динамическая диспетчеризация, vtable-лукапы и потеря кэша. Есть два серьёзных способа это исправить: векторизация (возврат батчей, как в DuckDB) и компиляция запроса в машинный код без диспетчеризации (как в Umbra). Оба подхода требуют команды очень умных инженеров на годы работы.
В Prela нашли третий путь — continuation-passing style (CPS). Ключевая идея: операторы не делают вещи, а делают вещи. Вместо того, чтобы принимать список и возвращать список, CPS-оператор принимает список и функцию-продолжение k, которая говорит, что делать с каждым элементом после обработки.
Например, оператор inc в CPS не возвращает список с увеличенными числами — он для каждого элемента применяет k(x+1). А оператор dbl делает то же самое с умножением на два. Если определить источник scan, который просто перебирает входной список и вызывает k для каждого элемента, то цепочка dbl(inc(scan(xs)), print) при инлайнинге превращается в один fused-цикл: for x in xs; print((x+1)*2); end. Никаких промежуточных списков, никакой динамической диспетчеризации.
Для реляционного движка этот подход обобщается на операторы compose (композиция бинарных отношений) и product (join по общему ключу). Если взять нормализованную схему (каждое широкое отношение разбито на бинарные таблицы с плотными первичными ключами), запрос SELECT * FROM movie в Prela выглядит как compose(scan_id(n), product(probe(year), probe(title))). После раскрытия всех определений через CPS и инлайнинг получается один простой цикл for i in 0:n; print(i, (year[i], title[i])); end — ровно то, что делает эффективный колоночный движок.
Вся реализация Prela умещается примерно в 1000 строк Julia в одном файле. Она поддерживает select, project, join, groupby, aggregation, CTEs и UDFs, а по производительности догоняет DuckDB на бенчмарках TPCH и Join Order Benchmark. Правда, с оговорками: Prela не заботится о времени компиляции (Julia JIT-ит запросы), а агрессивно использует предположение, что первичные ключи плотные и непрерывные. В реальных данных это может не работать, но проблему можно решить B-деревьями и битмаповыми фильтрами.
Главный плюс CPS-подхода — расширяемость: пользователь может написать свой оператор в пару строк, и он автоматически скомпилируется и сольётся с остальным запросом.