Архитектура SQLite

Введение

Данный документ описывает архитектуру библиотеки SQLite. Эта информация полезна тем, кто хочет понять или изменить внутреннюю работу SQLite.

На соседней диаграмме показаны основные компоненты SQLite и как они взаимодействуют. Текст ниже объясняет роли различных компонентов.

Обзор

SQLite работает путем компиляции текста SQL в байткод, а затем выполняет этот байткод с помощью виртуальной машины.

Интерфейсы sqlite3_prepare_v2() и родственные им действуют как компилятор для преобразования текста SQL в байткод. Объект sqlite3_stmt является контейнером для одной программы байткода, которая реализует одно SQL-выражение. Интерфейс sqlite3_step() передает программу байткода в виртуальную машину и выполняет ее, пока она либо не завершится, либо не сформирует строку результата для возврата, либо не столкнется с критической ошибкой, либо не будет прервана.

Интерфейс

Большая часть интерфейса на языке C находится в файлах исходного кода main.c, legacy.c и vdbeapi.c, хотя некоторые процедуры разбросаны по другим файлам, где они могут получить доступ к структурам данных со сферой файла. Процедура sqlite3_get_table() реализована в table.c. Процедура sqlite3_mprintf() находится в printf.c. Интерфейс sqlite3_complete() находится в complete.c. Интерфейс TCL реализован в tclsqlite.c.

Чтобы избежать столкновений имён, все внешние символы в библиотеке SQLite начинаются с префикса sqlite3. Те символы, которые предназначены для внешнего использования (другими словами, символы, которые образуют API для SQLite) добавляют знак подчёркивания, и, таким образом, начинаются с sqlite3_. В API расширений иногда добавляется имя расширения перед подчёркиванием; например: sqlite3rbu_ или sqlite3session_.

Токенизатор

При оценке строки, содержащей SQL-запросы, она сначала передаётся токенайзеру. Токенайзер разбивает текст SQL на токены и по одному передаёт их парсеру. Токенайзер написан вручную в файле tokenize.c.

Обратите внимание, что в этой конструкции токенайзер вызывает парсер. Ознакомленные с YACC и BISON могут привыкнуть к обратной последовательности — парсер вызывает токенайзер. Однако токенайзер, вызывающий парсер, лучше, так как его можно сделать потокобезопасным и он работает быстрее.

Парсер

Парсер присваивает значение токенам на основе их контекста. Парсер для SQLite генерируется с помощью генератора парсеров Lemon. Lemon выполняет ту же работу, что и YACC/BISON, но использует другой синтаксис входных данных, который менее подвержен ошибкам. Lemon также генерирует рекурсивный и потокобезопасный парсер. И Lemon определяет концепцию деструктора нетерминала, чтобы не было утечки памяти при обнаружении синтаксических ошибок. Файл грамматики, который управляет Lemon и определяет язык SQL, который понимает SQLite, находится в parse.y.

Поскольку Lemon — это программа, которая обычно не встречается на машинах разработчиков, весь исходный код Lemon (всего один файл C) включён в дистрибутив SQLite в подкаталоге "tool".

Генератор кода

После того, как парсер собирает токены в дерево разбора, запускается генератор кода, который анализирует дерево разбора и генерирует байткод, выполняющий работу SQL-запроса. Объект подготовленного запроса является контейнером для этого байткода. Существует много файлов в генераторе кода, включая: attach.c, auth.c, build.c, delete.c, expr.c, insert.c, pragma.c, select.c, trigger.c, update.c, vacuum.c, where.c, wherecode.c и whereexpr.c. В этих файлах происходит большая часть серьёзной магии. expr.c обрабатывает генерацию кода для выражений. where*.c обрабатывает генерацию кода для условий WHERE в запросах SELECT, UPDATE и DELETE. Файлы attach.c, delete.c, insert.c, select.c, trigger.c update.c и vacuum.c обрабатывают генерацию кода для SQL-запросов с такими же именами. (Каждый из этих файлов вызывает необходимые процедуры в expr.c и where.c). Все остальные SQL-запросы кодируются в build.c. Файл auth.c реализует функциональность sqlite3_set_authorizer().

Генератор кода, и особенно логика в where*.c и select.c, иногда называется планировщиком запросов. Для любого конкретного SQL-запроса может быть сотни, тысячи или миллионы различных алгоритмов вычисления ответа. Планировщик запросов — это ИИ, который стремится выбрать лучший алгоритм из этих миллионов вариантов.

Двигатель байткода

Байткод-программа, созданная генератором кода, выполняется виртуальной машиной.

Сама виртуальная машина полностью содержится в одном исходном файле vdbe.c. Заголовочный файл vdbe.h определяет интерфейс между виртуальной машиной и остальной частью библиотеки SQLite, а vdbeInt.h — структуры и интерфейсы, которые являются частными для самой виртуальной машины. Различные другие файлы vdbe*.c являются вспомогательными для виртуальной машины. Файл vdbeaux.c содержит утилиты, используемые виртуальной машиной, и интерфейсные модули, используемые остальной частью библиотеки для построения программ ВМ. Файл vdbeapi.c содержит внешние интерфейсы виртуальной машины, такие как sqlite3_bind_int() и sqlite3_step(). Отдельные значения (строки, целые числа, числа с плавающей точкой и BLOB) хранятся во внутреннем объекте "Mem", реализованном в vdbemem.c.

SQLite реализует SQL-функции с помощью обратных вызовов C-языковым процедурам. Таким же образом реализуются и встроенные SQL-функции. Большинство встроенных SQL-функций (например, abs(), count(), substr() и т. д.) можно найти в файле исходного кода func.c. Функции преобразования дат и времени находятся в файле date.c. Некоторые функции, такие как coalesce() и typeof(), реализованы как байткод непосредственно генератором кода.

B-дерево

База данных SQLite поддерживается на диске с помощью реализации B-дерева, которая находится в файле исходного кода btree.c. Отдельные B-деревья используются для каждой таблицы и каждого индекса в базе данных. Все B-деревья хранятся в одном файле диска. Подробности формата файла стабильны и хорошо определены, и гарантируется их совместимость в дальнейшем.

Интерфейс к подсистеме B-дерева и остальной части библиотеки SQLite определяется заголовочным файлом btree.h.

Кэш страниц

Модуль B-дерева запрашивает информацию с диска в страницах фиксированного размера. По умолчанию размер страницы составляет 4096 байт, но может быть любым целой степенью двойки от 512 до 65536 байт. Кэш страниц отвечает за чтение, запись и кэширование этих страниц. Кэш страниц также обеспечивает абстракцию отката и атомарной фиксации и занимается блокировкой файла базы данных. Драйвер B-дерева запрашивает определённые страницы у кэша страниц и уведомляет его, когда необходимо изменить страницы или зафиксировать/отменить изменения. Кэш страниц обрабатывает все сложные детали, гарантирующие быстрое, безопасное и эффективное выполнение запросов.

Основная реализация кэша страниц находится в файле pager.c. Логика режима WAL находится в отдельном файле wal.c. Кэширование в оперативной памяти реализовано в файлах pcache.c и pcache1.c. Интерфейс между подсистемой кэша страниц и остальной частью SQLite определяется заголовочным файлом pager.h.

Интерфейс ОС

Для обеспечения переносимости между операционными системами SQLite использует абстрактный объект, называемый VFS. Каждый VFS предоставляет методы для открытия, чтения, записи и закрытия файлов на диске и для других задач, специфичных для ОС, таких как определение текущего времени или получение случайных чисел для инициализации встроенного генератора псевдослучайных чисел. В настоящее время SQLite предоставляет VFS для Unix (в файле os_unix.c) и Windows (в файле os_win.c).

Утилиты

Выделение памяти, функции сравнения строк без учёта регистра, переносимые функции преобразования текста в число и другие утилиты находятся в файле util.c. Таблицы символов, используемые парсером, поддерживаются хеш-таблицами, которые находятся в файле hash.c. Файл исходного кода utf.c содержит подпрограммы преобразования Юникода. SQLite имеет собственную реализацию printf() (с некоторыми расширениями) в файле printf.c и собственный генератор псевдослучайных чисел (PRNG) в файле random.c.

Тестовый код

Файлы в папке "src/" дерева исходного кода, имена которых начинаются с test, предназначены только для тестирования и не включаются в стандартную сборку библиотеки.