Почему SQLite использует байткод

1. Введение

Каждый движок SQL-базы данных работает примерно одинаково: сначала он преобразует входной SQL-текст в «предзаготовленный запрос». Затем он «выполняет» предзаготовленный запрос, чтобы сгенерировать результат.

Предзаготовленный запрос — это объект, представляющий шаги, необходимые для выполнения входного SQL. Или, если взглянуть на это по-другому, предзаготовленный запрос — это SQL-запрос, преобразованный в форму, более понятную для компьютера.

В SQLite предзаготовленный запрос является экземпляром объекта sqlite3_stmt. В других системах предзаготовленный запрос обычно представляет собой внутреннюю структуру данных, которая не отображается непосредственно программисту приложения. Разработчики других движков SQL-баз данных не обязательно называют эти объекты «предзаготовленными запросами». Но такие объекты существуют, как бы они ни назывались. В этой статье будет использоваться термин «предзаготовленный запрос».

Существует бесчисленное множество способов реализации предзаготовленного запроса. В этой статье будут рассмотрены два наиболее распространённых метода:

1. Байткод → Входной SQL преобразуется в язык виртуальной машины, который затем выполняется интерпретатором виртуальной машины. Это метод, используемый в SQLite.

2. Дерево объектов → Входной SQL преобразуется в дерево объектов, представляющих обработку, которая должна быть выполнена. SQL выполняется путём обхода этого дерева. Это метод, используемый в MySQL и PostgreSQL.

У каждого из этих представлений предзаготовленного запроса есть свои преимущества и недостатки. Цель этой статьи — описать некоторые из этих преимуществ и недостатков.

1.1. Как предоставить обратную связь

Этот документ написан с точки зрения первоначального автора SQLite. Если вы не согласны с какими-либо мнениями, изложенными в этом документе, вы можете предложить исправления и/или альтернативные взгляды на форуме SQLite Forum. Или вы можете написать автору напрямую.

1.2. Определение «байткода»

Байткод, генерируемый SQLite, может немного отличаться от того, что многие читатели представляют себе под байткодом. Байткод, используемый (например), виртуальной машиной Java или WebAssembly, почти полностью состоит из низкоуровневых операций, аналогичных тем, которые реализуют физические процессоры: базовые математические операторы, сравнения, условные переходы и инструкции по перемещению содержимого между различными областями памяти. Байткод SQLite тоже содержит такие низкоуровневые инструкции. Но байткод SQLite также содержит некоторые высокоуровневые операции, специфичные для потребностей движка базы данных. Вот несколько примеров:

• OP_Column → Извлечь значение из N-го столбца строки базы данных, на которую в данный момент указывает указатель.

• OP_CreateBtree → Выделить место для нового B-дерева в файле базы данных.

• OP_ParseSchema → Перечитать и повторно проанализировать таблицу sqlite_schema полностью или частично и соответствующим образом обновить внутренние таблицы символов.

• OP_SeekGE → Переместить указатель по конкретному B-дереву к первой записи, которая больше или равна заданному ключу.

• OP_Next → Передвинуть указатель по конкретному B-дереву к следующей записи в B-дереве и перейти, или перейти к следующему элементу, если больше нет записей в этом B-дереве.

Другими словами, «байткод», используемый в SQLite, — это не столько набор инструкций процессора, сколько список баз данных, которые должны быть выполнены в определённом порядке.

1.3. Определение «абстрактного синтаксического дерева» или «AST»

«Абстрактное синтаксическое дерево» или AST — это структура данных, описывающая программу или оператор на каком-либо формальном языке. В нашем контексте формальным языком является SQL. AST обычно реализуется как дерево объектов, где каждый объект представляет собой небольшую часть общего SQL-запроса. AST естественным образом возникают из анализаторов формальных языков. Обычно используется LALR(1)-анализатор. С таким анализатором каждый терминальный символ содержит метаданные, которые станут листом AST, а каждый нетерминальный символ содержит метаданные, которые станут подветвью общего AST. По мере того, как правила грамматики «сокращаются» анализатором, новые узлы AST выделяются и подсоединяются к узлам-потомкам. После завершения анализа начальный символ грамматики содержит корень AST.

AST — это дерево объектов. Но AST не подходит для предзаготовленного запроса. После генерации AST необходимо преобразовать различными способами, прежде чем его можно будет выполнить. Символы нужно разрешить. Необходимо проверить правила семантики. Нужно применить оптимизации, которые преобразуют входной SQL-запрос в различные формы, выполняющиеся быстрее. Наконец, AST необходимо преобразовать в альтернативное представление, более подходящее для выполнения.

Некоторые люди называют дерево объектов, используемое в MySQL и PostgreSQL в качестве исполняемой формы, AST. Вероятно, это неправильное использование термина «AST», потому что к моменту готовности дерева объектов к выполнению оно настолько изменилось, что мало напоминает исходный SQL-текст. Недоразумение частично возникает потому, что и конечный объект предзаготовленного запроса, и исходный AST — это деревья объектов. Обычно исходный AST, полученный непосредственно из анализатора, преобразуется понемногу, в несколько проходов, пока в конце он полностью не преобразуется в дерево объектов, которое уже не является строго AST, но может быть вычислено для получения результата. Не обязательно есть ясная точка в этом процессе, когда дерево объектов перестаёт быть AST и становится предзаготовленным запросом вместо него. И поскольку нет чёткой границы между AST и предзаготовленным запросом, люди часто называют предзаготовленный запрос, представленный в виде дерева объектов, «AST», хотя это описание неточно.

1.4. Программирование с потоком данных

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

«Программа с потоком данных» — это, возможно, более подходящее описание, чем «AST», для дерева объектов, которое движок SQL-базы данных использует в качестве предзаготовленного запроса.

2. Преимущества компиляции в байткод

SQLite компилируется в байткод, и разработчики SQLite очень довольны этим подходом. Вот почему:

2.1. Байткод проще для понимания

Плоский список кодов операций можно легко распечатать, чтобы увидеть, как реализуется SQL-запрос. Это происходит в SQLite, когда вы предваряете SQL-запрос словом «EXPLAIN»: вместо фактического выполнения SQL результатом является список байткода, который был бы использован для реализации этого SQL.

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

Представление в виде дерева объектов сложнее опубликовать в читаемом человеком виде. Объекты, составляющие дерево, часто очень разные, и поэтому сложно разработать согласованное и простое представление таблицы для отображения объектов. Любое такое табличное представление, которое вы разработаете, практически наверняка будет иметь более чем шесть столбцов, вероятно, гораздо больше. Проблема отображения дерева объектов в виде таблицы достаточно сложна, что никто этого не делает, насколько мне известно. Таким образом, ни один движок базы данных с деревом объектов не предоставляет такой уровень детализации в выводе «EXPLAIN», как SQLite.

2.2. Байткод проще отлаживать

Байткод обеспечивает чёткое разделение между парсингом и анализом на клиентском конце и вычислением SQL-запроса на серверном конце. При возникновении проблем (неверные ответы и/или плохая производительность) разработчики могут изучить байткод, чтобы быстро определить, является ли источником проблемы либо клиентский анализ, либо часть базы данных.

В отладочных сборках SQLite команда PRAGMA vdbe_trace=ON; выведет трассировку выполнения байткода в консоли.

2.3. Байткод можно выполнять поэтапно

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

Это сложнее реализовать в структуре данных «дерево объектов». Когда предзаготовленный запрос представляет собой дерево объектов, выполнение обычно происходит путём обхода дерева. Прерывание запроса в середине вычисления означает возвращение стека к вызывающей стороне, сохраняя при этом достаточно состояния, чтобы возобновить оценку с того места, где она остановилась. Это не невозможно, но достаточно сложно, чтобы я никогда не видел этого на практике.

Большинство движков SQL-баз данных не нуждаются в инкрементальном выполнении подготовленных запросов, поскольку большинство SQL-движков являются клиентско-серверными. В клиентско-серверных движках единственное SQL-определение отправляется на сервер, а затем весь ответ возвращается сразу. Таким образом, каждый запрос выполняется до завершения за один раз. Но SQLite не является клиентско-серверным. SQLite — это библиотека, которая выполняется в том же адресном пространстве и используя ту же стековую память, что и приложение. Возможность лёгкого и надёжного инкрементального выполнения SQL-запроса важна для SQLite.

2.4. Байт-код меньше по размеру

Байт-код, сгенерированный SQLite, обычно меньше, чем соответствующее абстрактное синтаксическое дерево (AST), полученное из парсера. Во время начальной обработки SQL-текста (во время вызова sqlite3_prepare() и аналогичных функций) и AST, и байт-код существуют в памяти одновременно, поэтому используется больше памяти. Но это временное состояние. AST быстро отбрасывается, и его память освобождается, даже до возврата вызова sqlite3_prepare(), поэтому результирующий подготовленный запрос в итоге потребляет меньше памяти в своем представлении в виде байт-кода, чем в виде AST. Это важно, потому что вызовы sqlite3_prepare() временные, но подготовленные запросы часто кэшируются для возможного повторного использования и сохраняются в памяти в течение длительного времени.

2.5. Байт-код быстрее

Я полагаю, что представление подготовленного запроса в виде байт-кода работает быстрее, потому что для каждого шага вычисления требуется меньше решений. Подчёркиваю «полагаю» в предыдущем предложении → трудно проверить это утверждение экспериментально, так как никто не тратил несколько лет на создание эквивалентных представлений байт-кода и дерева объектов подготовленного запроса, чтобы увидеть, какой вариант работает быстрее. Мы знаем, что SQLite очень быстрый, но у нас нет хороших сравнений «бок о бок» с другими SQL-базами данных, поскольку другие базы данных тратят много времени на обработку сообщений клиент/сервер, и трудно отделить накладные расходы на обмен сообщениями от реального времени обработки.

3. Преимущества компиляции в дерево объектов

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

3.1. Решение по планированию запросов может быть отложено до времени выполнения

Когда подготовленный запрос представляет собой байт-код, после генерации байт-кода алгоритм фиксируется и не может быть изменён впоследствии без полной перекомпиляции байт-кода. Это не относится к подготовленному запросу в виде дерева объектов. Дерево объектов легче изменять на лету. План запроса изменяем и может быть изменён во время выполнения, на основе прогресса выполнения запроса. Таким образом, запрос может динамически самонастраиваться.

3.2. Программы потока данных легко распараллелить

В программе потока данных каждый узел обработки может быть назначен разному потоку. Необходимо какое-то механизм очереди с поддержкой многопоточности для передачи промежуточных результатов от одного узла к другому. Однако, как правило, в каждом узле программы не нужны синхронизирующие примитивы. Планирование работы узла тривиально: узел становится готовым к выполнению, когда у него есть доступные данные и есть место в его выходной очереди.

Это важный момент для движков баз данных, которые предназначены для выполнения больших аналитических запросов (OLAP) на больших многоядерных серверах. Основной фокус SQLite — обработка транзакций (OLTP) в Интернете вещей, поэтому меньше необходимости представлять подготовленные запросы как программы потока данных в SQLite.

Эта страница была в последний раз изменена 2024-05-09 17:38:03 UTC