Как базы данных выполняют выражения?

В этом посте рассматривается, как различные базы данных выполняют выражения на своем языке запросов.

Нашли и перевели для вас интересную статью о том как базы данных выполняют выражения.

Ссылка на оригинал статьи: https://notes.eatonphil.com/2023-09-21-how-do-databases-execute-expressions.html

Базы данных - это весело. Они находятся на стыке тем информатики, которые в противном случае могли бы показаться непрактичными в жизни разработчика. Например, каждая база данных с языком запросов также является реализацией языка программирования определенного уровня. Это, конечно, включает не все базы данных; смотрите: RocksDB, FoundationDB, TigerBeetle и т.д.

Большинство рассмотренных баз данных используют интерпретатор обхода дерева. Некоторые используют виртуальные машины на основе стека или регистра. У пары есть компиляторы "точно в срок". И, косвенно, некоторые из них выполняют векторную интерпретацию.

На протяжении всего этого поста будет использоваться "виртуальная машина" как сокращение для циклов на основе стека или регистра, которые обрабатывают линеаризованный набор инструкций. Я говорю это, поскольку иногда справедливо называть интерпретатор, работающий по дереву, виртуальной машиной. Но это не то, что я имею в виду, когда говорю "виртуальная машина" в этом посте.

Делая шаг назад

Языки программирования обычно реализуются путем превращения абстрактного синтаксического дерева (AST) в линейный набор инструкций для виртуальной машины (например, CPython, Java, C #) или собственного кода (например, компилятор C GCC, Go, Rust). Некоторые из предыдущих реализаций также генерируют и запускают скомпилированный точно в срок (JIT) машинный код (например, Java и C #).

В наши дни в языках программирования реализация реже интерпретирует AST или какое-либо другое древовидное промежуточное представление. Этот стиль часто называют "обход дерева".

Языки оболочки иногда выполняют обход по дереву. В противном случае реализации, которые интерпретируют непосредственно из дерева, обычно делают это в качестве краткосрочной меры перед переключением на скомпилированный код виртуальной машины или JIT-ed машинный код (например, некоторые реализации JavaScript, GraalVM, RPython и т.д.)

То есть, хотя некоторые основные реализации языков программирования начинались с интерпретаторов "обхода дерева", в основном они отошли от исключительно "обхода дерева" более десяти лет назад.

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

А базы данных?

Базы данных часто интерпретируют непосредственно из дерева. (Вообще говоря, было бы несправедливо говорить, что они являются интерпретаторами, использующими AST, потому что базы данных обычно преобразуют и оптимизируют не только AST, анализируемый из пользовательского кода.)

Но не все базы данных интерпретируют дерево. У некоторых есть виртуальная машина. А некоторые генерируют и запускают JIT-ed машинный код.

Методология

Если базовая функция (в пути выполнения запроса, которая выполняет что-то вроде арифметики или сравнения) возвращает значение, это признак того, что это интерпретатор обхода дерева. Или, если вы видите код, который оценивает свои аргументы во время выполнения, это также признак интерпретатора, работающего по дереву.

С другой стороны, если функция изменяет внутреннее состояние, например, присваивая значение контексту или перемещая его в стек, это признак того, что это виртуальная машина на основе стека или регистра. Если функция извлекает свои аргументы из памяти и не вычисляет аргументы, это также указывает на то, что это виртуальная машина на основе стека или регистра.

Такой подход может привести к ложноположительным результатам в зависимости от архитектуры интерпретатора. Определяемые пользователем функции (UDFS), вероятно, будут принимать вычисляемые аргументы и возвращать значение независимо от того, как реализован интерпретатор. Поэтому важно найти не просто функции, которые могут быть реализованы подобно UDFs, но и встроенное в ядро поведение. Реализации потока управления такими функциями, как if или case, могут быть отличными местами для поиска.

И тактически я клонирую исходный код и запускаю такие вещи, как git grep -i eval | grep -v test | grep \\.java | grep -i eval или git grep -i expr | grep -v test | grep \\.go | grep -i expr, пока не буду убежден в том, что нахожусь в интересном месте.

Примечание: Говоря о широком спектре проектов, возможно, я неправильно понял один или несколько. Если у вас есть исправление, дайте мне знать! Если есть собственная база данных, над которой вы работаете, где вы можете ссылаться на (публично описанную) стратегию выполнения, не стесняйтесь передавать ее! Или, если мне не хватает вашей базы данных с открытым исходным кодом в этом списке, отправьте мне сообщение!

Cockroach

Судя по таким функциям, как func (e *evaluator) EvalBinaryExpr , которые вычисляют левую часть, а затем вычисляют правую часть и возвращают значение, Cockroach выглядит как интерпретатор, который делает обход по дереву.

Однако это становится немного интереснее, поскольку Cockroach также поддерживает выполнение векторизованных выражений. Векторизация - это причудливый термин, обозначающий действие со многими фрагментами данных одновременно, а не по одному за раз. Это не обязательно подразумевает SIMD. Вот пример векторизованного сложения двух столбцов int64.

ClickHouse

Архитектура ClickHouse немного уникальна, и мне сложно ее прочитать – вероятно, из-за того, что она довольно зрелая, с серьезной оптимизацией. Но они, как правило, хорошо документируют свои заголовочные файлы. Итак, такие файлы, как src/Functions/IFunction.h и src/Interpreters/ExpressionActions.h были полезны.

Они также публично рассказали о своей конвейерной модели выполнения; например, эта презентация и этот выпуск дорожной карты. Но не совсем ясно, насколько конвейерное выполнение (которое шире, чем просто вычисление выражения) связано с вычислением выражения.

Более того, они публично заявили о своей поддержке компиляции JIT для выполнения запросов. Но давайте посмотрим, как работает выполнение, когда JIT не включен. Например, если мы посмотрим как реализован if, мы узнаем, что строки then и else должны быть вычислены условно.

В точке входа среды выполнения executeImpl мы видим вызов функции, executeShortCircuitArguments которая, в свою очередь, вызывает функцию, ColumnFunction::reduce(), которая вычисляет каждый вектор столбца, являющийся аргументом функции, а затем вызывает execute для функции.

Таким образом, из этого мы можем сказать, что выполнение без JIT является перемещением по дереву и что оно выполняется по целым столбцам, то есть векторизованным данным, подобно Cockroach .Однако в ClickHouse выполнение всегда выполняется над векторами столбцов.

DuckDB

Если мы посмотрим, как выполняются выражения функций, мы сможем увидеть, что каждый аргумент в функции вычисляется перед передачей фактической функции. Итак, это похоже на интерпретатор перемещения по дереву.

Как и ClickHouse, выполнение выражений DuckDB всегда выполняется над векторами столбцов. Вы можете прочитать больше об этой архитектуре здесь и здесь.

Influx

У Influx изначально был SQL-подобный язык запросов под названием InfluxQL. Если мы посмотрим, как она вычисляет двоичное выражение, она сначала вычисляет левую часть, а затем правую часть, прежде чем работать со сторонами и возвращать значение. Это интерпретатор, работающий по дереву.

Flux был новым языком запросов для Influx. Хотя в документах Flux предлагается преобразовать их в промежуточное представление, которое выполняется на виртуальной машине, я не вижу ничего похожего на виртуальную машину на основе стека или регистра. Все вычислительные функции вычисляют свои аргументы и возвращают значение. Для меня это выглядит как интерпретатор, идущий по дереву.

Сегодня Influx объявила, что Flux находится в режиме обслуживания, и они снова сосредотачиваются на InfluxQL.

MariaDB / MySQL

Методы потока управления обычно являются хорошим способом увидеть, как реализован интерпретатор. Реализация COALESCE выглядит довольно просто. Мы видим, что это вызывает val_str() объединение каждого аргумента. Но, похоже, я могу найти реализации val_str() только для необработанных значений, а не для выражений. Например, Item_func_coalesce сама по себе не реализует val_str(), что было бы явным признаком обхода дерева. Возможно, она реализует val_str() через наследование.

Это становится немного понятнее, если мы посмотрим на неуправляемые потоковые методы, такие как acos. В этом методе мы видим Item_func_acos саму реализацию val_real(), а также вызываем val_real() все его аргументы. В этом случае очевидно, как будет работать поток управления acos(acos(.5)). Похоже, это указывает на то, что выражения выполняются с помощью интерпретатора перемещения по дереву.

Я также заметил sql/sp_instr.cc. Это пугает (с точки зрения недействительности моего анализа), поскольку он выглядит как виртуальная машина. Но, просмотрев это, я думаю, что эта виртуальная машина соответствует только тому, как выполняются хранимые процедуры, отсюда и sp_ префикс для хранимых программ. В документах MySQL также объясняется, что хранимые процедуры выполняются с помощью виртуальной машины с байт-кодом.

Мне любопытно, почему они не используют эту виртуальную машину для выполнения запросов.

Насколько я могу судить, MySQL и MariaDB не отличаются в этом отношении.

MongoDB

Mongo недавно представила виртуальную машину для выполнения запросов, которая называется Slot Based Execution (SBE). Мы можем найти код SBE в src/mongo/db/exec/sbe/vm/vm.cpp и основную точку входа в виртуальную машину здесь. Выглядит как классическая виртуальная машина на основе стека!

Мне не совсем ясно, всегда ли используется путь SBE или все еще есть случаи, когда он возвращается к их старой модели выполнения. Вы можете прочитать больше о выполнении Mongo здесь и здесь.

PostgreSQL

В верхней части src/backend/executor/execExprInterp.c PostgreSQL четко объясняется, что для выполнения выражения используется виртуальная машина. Вы видите все отличительные признаки: коды операций, цикл над гигантским переключателем и т.д. И если мы посмотрим на то, как выполняются выражения функций, мы увидим еще одну отличительную черту, которая заключается в том, что код выражения функции не оценивает свои аргументы. Они уже были оценены. А код выражения функции просто воздействует на результаты своих аргументов.

PostgreSQL также поддерживает выполнение JIT-выражений. И мы можем найти переключатель между интерпретацией и JIT-компиляцией выражения здесь.

QuestDB

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

Но давайте посмотрим на путь по умолчанию. Например, как AND это реализовано. AndBooleanFunction реализует BooleanFunction, который реализует Function. Выражение может быть вычислено путем вызова getX() метода для типа выражения, который реализует Function. AndBooleanFunction вызовы getBool() в его левой и правой частях. И если мы посмотрим на частичную реализацию BooleanFunction, мы также увидим, что она выполняет getX() определенные преобразования во время вызова getX(). Итак, это интерпретатор, работающий по дереву.

Scylla

Если мы посмотрим на то, как вычисляются функции в Scylla, мы увидим, что сначала выполняется вычисление функции, оценивающей все ее аргументы. И сама функция вычисления функции возвращает cql3::raw_value. Итак, это интерпретатор обхода дерева.

SQLite

Виртуальная машина SQLite является всеобъемлющей и хорошо документированной. Она охватывает не только вычисление выражения, но и выполнение запроса в целом.

Мы можем найти массовый переключатель виртуальной машины в src/vdbe.c.

И если мы посмотрим, например, на то, как AND это реализовано, мы увидим, что оно извлекает свои аргументы из памяти (уже оцененные) и присваивает результат обратно назначенной точке в памяти.

SingleStore

Хотя нет исходного кода для ссылки, SingleStore выступил с докладом в CMU, который сломал их конвейер выполнения запросов. Их документы также охватывают эту тему.

TiDB

Подобно DuckDB и ClickHouse, TiDB реализует векторную интерпретацию. Они публично написали о своем переходе на этот метод.

Давайте посмотрим, как if это реализовано в TiDB. Существует векторизованная и невекторизованная версия if (в expression/control_builtin.go и expression/control_builtin_generated.go соответственно). Так что, возможно, они не полностью перешли на векторизованное выполнение или, возможно, его можно использовать только в некоторых условиях.

Если мы посмотрим на невекторизованную версию if, мы увидим, что условие вычислено. А затем then или else вычисляется в зависимости от результата выполнения условия. Это интерпретатор обхода дерева.

Заключение

Как указывает команда DuckDB, векторизованная интерпретация или JIT-компиляция кажутся будущим для выполнения выражений базы данных. Эти стратегии кажутся особенно важными для аналитики или рабочих нагрузок временных рядов. Но векторная интерпретация, по-видимому, имеет наибольший смысл для систем хранения данных с разбивкой по столбцам. А хранилище с разбивкой по столбцам обычно имеет смысл только для рабочих нагрузок аналитики. Тем не менее, TiDB и Cockroach являются транзакционными базами данных, которые также векторизируют выполнение.

И хотя SQLite и PostgreSQL используют модель виртуальной машины, возможно, базы данных с древовидными интерпретаторами, такими как Scylla и MySQL / MariaDB, решили, что недостаточно значительного выигрыша (для транзакционных рабочих нагрузок), чтобы оправдать сложность перехода к архитектуре компилятор + виртуальная машина.

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

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