Привет, Хабр! Меня зовут Георгий Лебедев, я работаю в команде разработки ядра Tarantool. В 2021 году мы впервые участвовали в Google Summer of Code (GSoC): одним из предложенных студентам проектов была миграция SQL с VDBE на JIT-платформу — с неё и начался мой путь в Tarantool.

Имея за плечами год учебных проектов по разработке различных компонент toolchain’а и вооружившись поддержкой менторов (Никиты Петтика, Тимура Сафина и Игоря Мункина), я взялся за этот проект. Создавая летом, фактически с нуля, платформу для JIT- компиляции SQL- запросов в Tarantool, я наступил на некоторые грабли и приобрёл, на мой взгляд, интересный опыт и знания, которыми хочу поделиться. Статья будет, в первую очередь, интересна тем, кто захочет дальше развивать этот проект, а также тем, кто рассматривает возможность внедрения JIT-компиляции в свой собственный SQL.

С чем нужно было работать

Для поддержки языка SQL в Tarantool используется виртуальная машина (ВМ), унаследованная от SQLite, также известного как Virtual Database Engine (VDBE). Схема этого компонента:

На практике одним из самых популярных способов реализации виртуальных машин является оперирование потоком байтовых инструкций — байткода: на таком же принципе основана VDBE. В этой статье нас будет интересовать байткод в качестве промежуточного представления для виртуальной машины и его интерпретация: далее, говоря о байткоде и реализации ВМ SQL в Tarantool, я буду подразумевать именно VDBE.

Байткод-интерпретация представляет из себя цикл for по массиву opcode’ов (читай, байткод-программе, сгенерированной по SQL-запросу) и switch по типу opcode’а:

for(pOp = &aOp[p->pc]; 1; pOp++) {
    switch (pOp->opcode) {
    ...
    }
}

Задача

С точки зрения сервера приложений, в Tarantool уже есть виртуальная машина — LuaJIT. Ещё одна рукописная (то есть без использования фреймворков для построения среды исполнения) ВМ для поддержки SQL выглядит не очень изящно с точки зрения архитектуры, не говоря уже о проблемах с производительностью, которые она вносит.

В проекте предлагалось исследовать несколько возможных альтернатив VDBE:

• переиспользование инфраструктуры LuaJIT;

• использование фреймворка MIR для JIT-компиляции;

• использование фреймворка LLVM ORC.

Результаты, которые хотелось получить:

• проверка идеи миграции VDBE на выбранную JIT-платформу;

• исследование различных сценариев применения JIT-компиляции в контексте SQL;

• измерение производительности JIT-компиляции в различных SQL-бенчмарках.

Поскольку решение задачи в заданные сроки (три летних месяца) представлялась неподъёмной, а в Tarantool уже имелся первый подход к снаряду в виде патча трёхлетней давности на базе LLVM ORC, я решил использовать именно этот фреймворк и развивать идею Никиты Петтика. Кроме того, мы оглядывались на успешный опыт Postgres, уже реализовавших такую платформу на основе этого фреймворка.

И сегодня есть ещё СУБД, ClickHouse, в которой также успешно реализована JIT-платформа для SQL на базе LLVM ORC.

JIT-компиляция SQL

JIT-компиляция не является панацеей: у этого подхода есть свои накладные расходы и он не всегда даёт лучшие результаты по сравнению с байткод-интерпретацией — именно поэтому у JIT-компиляции довольно ограниченный набор сценариев применения.

Основные преимущества подхода:

• уменьшение количества инструкций перехода и локализация нативного кода — лучшее использование branch predictor’а;

• уменьшение количества веток и объёма машинного кода за счёт специализации;

• улучшение производительности горячих участков байткода, которые являютсяузкими местами при обработке процессором;

• лучшее использование кешей процессора;

• генерация инструкций под целевой процессор;

• простор для оптимизации сгенерированного IR.

В контексте SQL можно выделить основной сценарий использования JIT-компиляции: тяжелые аналитические data query language (DQL) запросы, содержащие много выражений и логики.

Такие запросы представляют собой последовательность байткода, многократно исполняемую в цикле: последовательность, которую можно сшить в один opcode, являющийся вызовом функции с нативным кодом — идеальный случай для применения JIT-компиляции.

Здесь можно выделить некоторые сценарии вычислений, представляющие наибольший интерес:

• декодирование кортежей (строк в терминологии Tarantool);

• арифметические и логические выражения разных видов;

• агрегатные функции.

Агрегатные функции представляют особый интерес, поскольку для их вычисления используются отдельные циклы — снова очень подходящие условия для JIT-компиляции.

Некоторые трудности и аспекты работы над проектом, на которых я не хотел бы здесь останавливаться, я осветил в своём финальном отчёте для GSoC.

Далее речь пойдёт о наиболее важных, на мой взгляд, выводах, которые я сделал при работе над проектом.

LLVM ORC

Использование стороннего фреймворка для JIT-компиляции, пусть и со своим собственным IR, позволило абстрагироваться от задач генерации, оптимизации и хранения нативного кода, сосредоточившись на генерации LLVM IR и встраивании JIT-компилятора в существующую инфраструктуру SQL.

To inline, or not to inline, that is the question

При встраивании JIT-компиляции в SQL-инфраструктуру возникает вопрос о том, каким образом генерировать LLVM IR, функционально эквивалентный интерпретации opcode’ов на C. Есть два принципиально разных подхода:

• полностью ручная генерация LLVM IR для каждого opcode’а (Postgres);

• автоматическая с помощью clang (Postgres).

В Postgres второй подход используется только для встроенных функций и операторов.

На мой взгляд, первый подход сопоставим с написанием вручную ассемблерного кода: довольно трудозатратен и чреват ошибками. Кроме того, было бы попросту скучно вместо инновационного летнего проекта заниматься механической работой.Я выбрал такую стратегию: обёртывать существующие блоки кода для SQL opcode’ов в callback’и, вызываемые в JIT-компилируемом коде — это также позволяет избавиться от довольно нетривиального дублирования кода при использовании первого подхода.

Здесь возникает резонный вопрос: а как же специализация кода и другие преимущества JIT-компиляции, которых мы, казалось бы, лишаемся, используя такую стратегию? Тут мне на помощь должны были прийти возможности inlining’а, которые предоставляет LLVM: как выяснилось, для используемого мной C API, который является небольшим подмножеством C++ API LLVM, такие возможности вообще отсутствовали и появились лишь в 13 версии LLVM.

Кроме того, даже для применения C++ API необходимо построить целую инфраструктуру, чтобы:

• хранить, индексировать и загружать bitcode, сгенерированный clang;

• искать в bitcode-модулях (единица трансляции в терминологии LLVM) нужные callback’и и переносить их IR между модулями;

• явно inline’ить callback’и.

Хорошим примером того, как можно реализовать такую инфраструктуру на практике, является Postgres.

Патчинг сгенерированного LLVM IR

В JIT-компиляции SQL в Tarantool есть важный нюанс: некоторые opcode’ы VBDE патчатся при генерации байткода. Например, это используется для оптимизации: чтения напрямую из таблицы можно заменить чтением из индекса:

Видно, что у всех opcode’ов Column изменился первый аргумент, соответствующий номеру курсора.

Ещё одно обстоятельство, при котором нужно патчить байткод-инструкции — это корутины, используемые для подзапросов. Байткод, загружающий колонки из таблицы корутины, должен меняться на байткод, копирующий колонки из регистров возвращаемых значений корутины:

Эти же обстоятельства нужно отражать и в генерируемом LLVM IR; с точки зрения IR решение этой проблемы напрашивается само собой: использовать для каждого opcode’а свой базовый блок — это сильно упрощает анализ, поиск и патчинг нужных инструкций. Или даже позволяет выкидывать целые блоки и заменять их на другие. И всё это нелинейно!

LLVM IR выше для запроса select A from DEMO соответствует загрузке колонки в регистр: видно, как поменялось значение аргумента инструкции store в базовом блоке OP_Column_begin:

store i32 1, i32* %tab, align 4

Представленный ниже LLVM IR генерируется для запроса select * from (select A from DEMO), использующего корутину:

SQL-бенчмарки

Заключительной частью проекта было измерение производительности в стандартных SQL-бенчмарках: я взял TPC-H, как наиболее показательный — в нём отражены типичные аналитические SQL-запросы.

При измерениях учитывалось также время анализа и компиляции запросов, тогда как на практике предполагается применять JIT-компиляцию только для prepared-запросов. Если пренебречь этими накладными расходами, то можно считать, что потери производительности при использовании JIT-компиляции отсутствуют.

К сожалению, из-за того, что я не успел сделать JIT-компиляцию арифметических выражений, а большинство запросов в TPC-H содержат их в большом количестве, мало где удалось увидеть её в деле. Выстрелили только Q17, Q19, Q20. Наиболее примечателен Q19: он содержит огромное количество колоночных ссылок и литералов — прирост производительности оказался практически двухкратным!

Результаты

• Патч-сет с платформой для JIT-компиляции SQL на основе 12 версии LLVM ORC.

• JIT-компиляция различных SELECT-выражений: литералов, колоночных ссылок и агрегатных колонок.

• JIT-компиляция агрегатных функций (например, SUM, COUNT, AVG) с некоторыми ограничениями на сложность запроса.

• Бенчмарк TPC-H показал существенный прирост производительности на некоторых типах запросов и не показал заметной деградации производительности на остальных.

Вместо заключения

В 2022 году можно продолжить работу над JIT-компиляцией SQL в Tarantool. Мы запустили собственную программу для студентов, о чём недавно рассказали на Хабре. Также мы участвуем в Summer OSPP и приглашаем всех, кто заинтересовался проектом, попробовать свои силы. Айда JIT-компилировать!

Оставайтесь на связи в нашем Telegram-чате по студенческой программе и Summer OSPP.