Виртуальный движок баз данных SQLite

 Obsolete Documentation Warning: This document describes the virtual machine used in SQLite version 2.8.0. The virtual machine in SQLite version 3.0 and 3.1 is similar in concept but is now register-based instead of stack-based, has five operands per opcode instead of three, and has a different set of opcodes from those shown below. See the virtual machine instructions document for the current set of VDBE opcodes and a brief overview of how the VDBE operates. This document is retained as an historical reference.

Если вы хотите узнать, как библиотека SQLite работает внутри, вам необходимо начать с основательного понимания виртуального движка баз данных (Virtual Database Engine, или VDBE). VDBE находится прямо в середине потока обработки (см. диаграмму архитектуры) и поэтому, похоже, затрагивает большинство частей библиотеки. Даже части кода, которые напрямую не взаимодействуют с VDBE, обычно выполняют вспомогательную роль. VDBE действительно является сердцем SQLite.

Эта статья представляет собой краткое введение в работу VDBE и, в частности, в то, как различные инструкции VDBE (описанные здесь) взаимодействуют друг с другом, чтобы выполнять полезные операции с базой данных. Статья написана в учебном стиле: от простых задач мы перейдём к решению более сложных проблем. По пути мы рассмотрим большинство подмодулей библиотеки SQLite. Завершив это руководство, вы получите достаточно хорошее представление о работе SQLite и будете готовы приступить к изучению исходного кода.

Предварительные сведения

VDBE реализует виртуальный компьютер, который выполняет программу на своём языке виртуальной машины. Цель каждой программы — запрашивать или изменять базу данных. Для этого машинный язык, реализованный в VDBE, специально разработан для поиска, чтения и изменения баз данных.

Каждая инструкция языка VDBE содержит код операции и три операнда с метками P1, P2 и P3. Операнд P1 — произвольное целое число. P2 — неотрицательное целое число. P3 — указатель на структуру данных или строку, завершающуюся нулём; он также может быть равен NULL. Лишь несколько инструкций VDBE используют все три операнда. Многие инструкции используют только один или два операнда. Значительное число инструкций вообще не используют операнды, а вместо этого получают данные и сохраняют результаты в стеке выполнения. Подробное описание действий каждой инструкции и используемых ею операндов приведено в отдельном документе с описанием кодов операций.

Выполнение программы VDBE начинается с инструкции 0 и продолжается последовательно, пока программа не (1) встретит критическую ошибку, (2) не выполнит инструкцию Halt или (3) не передвинет счётчик команд за пределы последней инструкции программы. По завершении выполнения VDBE все открытые курсоры базы данных закрываются, вся память освобождается, а все элементы удаляются из стека. Поэтому не нужно беспокоиться об утечках памяти или неосвобождённых ресурсах.

Если вы программировали на языке ассемблера или работали с какой-либо абстрактной машиной, все эти сведения должны быть вам знакомы. Так что давайте сразу перейдём к делу и рассмотрим код.

Вставка записей в базу данных

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

CREATE TABLE examp(one text, two int);

Иными словами, у нас есть таблица базы данных с именем "examp", содержащая два столбца данных с именами "one" и "two". Теперь предположим, что мы хотим вставить в эту таблицу одну запись. Например, такую:

INSERT INTO examp VALUES('Hello, World!',99);

Программу VDBE, которую SQLite использует для выполнения этой команды INSERT, можно увидеть с помощью утилиты командной строки sqlite. Сначала запустите sqlite для новой пустой базы данных, затем создайте таблицу. После этого измените формат вывода sqlite на формат, предназначенный для отображения дампов программ VDBE, введя команду ".explain". Наконец, введите показанную выше инструкцию [INSERT], предварив её специальным ключевым словом [EXPLAIN]. Ключевое слово [EXPLAIN] заставит sqlite вывести программу VDBE вместо её выполнения. Получим следующее:

$ sqlite test_database_1
 sqlite> CREATE TABLE examp(one text, two int);
 sqlite> .explain
 sqlite> EXPLAIN INSERT INTO examp VALUES('Hello, World!',99);
 addr opcode p1 p2 p3 
 ---- ------------ ----- ----- -----------------------------------
 0 Transaction 0 0 
 1 VerifyCookie 0 81 
 2 Transaction 1 0 
 3 Integer 0 0 
 4 OpenWrite 0 3 examp 
 5 NewRecno 0 0 
 6 String 0 0 Hello, World! 
 7 Integer 99 0 99 
 8 MakeRecord 2 0 
 9 PutIntKey 0 1 
 10 Close 0 0 
 11 Commit 0 0 
 12 Halt 0 0

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

0 Transaction 0 0 1 VerifyCookie 0 81 2 Transaction 1 0

Инструкция Transaction начинает транзакцию. Транзакция завершается при встрече кода операции Commit или Rollback. P1 — индекс файла базы данных, для которого начинается транзакция. Индекс 0 соответствует основному файлу базы данных. При начале транзакции для файла базы данных устанавливается блокировка записи. Пока длится транзакция, никакой другой процесс не может читать файл или записывать в него. Начало транзакции также создаёт журнал отката. Прежде чем вносить изменения в базу данных, необходимо начать транзакцию.

Инструкция VerifyCookie проверяет cookie 0 (версию схемы базы данных), чтобы убедиться, что она совпадает с P2 (значением, полученным при последнем чтении схемы базы данных). P1 — номер базы данных (0 для основной базы данных). Это делается для того, чтобы убедиться, что схема базы данных не была изменена другим потоком; в противном случае её необходимо прочитать заново.

Вторая инструкция Transaction начинает транзакцию и запускает журнал отката для базы данных 1 — базы данных, используемой для временных таблиц.

3 Integer 0 0 4 OpenWrite 0 3 examp

Инструкция Integer помещает в стек целочисленное значение P1 (0). Здесь 0 — номер базы данных, которая будет использоваться в следующей инструкции OpenWrite. Если P3 не равен NULL, то он содержит строковое представление того же целого числа. После этого стек выглядит следующим образом:

(целое число) 0

Инструкция OpenWrite открывает новый курсор для чтения и записи с дескриптором P1 (в данном случае 0) для таблицы "examp", корневая страница которой — P2 (3 в этом файле базы данных). Дескрипторы курсоров могут быть любыми неотрицательными целыми числами. Однако VDBE выделяет курсоры в массиве, размер которого на единицу больше наибольшего дескриптора курсора. Поэтому для экономии памяти лучше использовать дескрипторы, начиная с нуля и последовательно увеличивая их. Здесь P3 ("examp") — имя открываемой таблицы, но оно не используется и создаётся только для того, чтобы код было легче читать. Эта инструкция извлекает из вершины стека номер используемой базы данных (0 — основная база данных), поэтому после этого стек снова пуст.

5 NewRecno 0 0

Инструкция NewRecno создаёт новый целочисленный номер записи для таблицы, на которую указывает курсор P1. Этот номер записи ещё не используется в таблице в качестве ключа. Новый номер записи помещается в стек. После этого стек выглядит следующим образом:

(целое число) ключ новой записи

6 String 0 0 Hello, World!

Инструкция String помещает операнд P3 в стек. После этого стек выглядит следующим образом:

(строка) "Hello, World!"

(целое число) ключ новой записи

7 Integer 99 0 99

Инструкция Integer помещает операнд P1 (99) в стек. После этого стек выглядит следующим образом:

(целое число) 99

(строка) "Hello, World!"

(целое число) ключ новой записи

8 MakeRecord 2 0

Инструкция MakeRecord извлекает из вершины стека P1 элементов (в данном случае 2) и преобразует их в двоичный формат, используемый для хранения записей в файле базы данных. (Подробнее см. описание формата файла.) Новая запись, сформированная инструкцией MakeRecord, помещается обратно в стек. После этого стек выглядит следующим образом:

(запись) "Hello, World!", 99

(целое число) ключ новой записи

9 PutIntKey 0 1

Инструкция PutIntKey использует два верхних элемента стека, чтобы записать элемент в таблицу, на которую указывает курсор P1. Если такого элемента ещё нет, создаётся новая запись; в противном случае данные существующей записи перезаписываются. Данные записи находятся на вершине стека, а ключ — следующим элементом ниже. Эта инструкция дважды извлекает элемент из стека. Поскольку операнд P2 равен 1, счётчик изменений строк увеличивается, а rowid сохраняется для последующего возврата функцией sqlite_last_insert_rowid(). Если P2 равен 0, счётчик изменений строк не меняется. Именно эта инструкция фактически выполняет вставку.

10 Close 0 0

Инструкция Close закрывает курсор, ранее открытый как P1 (0 — единственный открытый курсор). Если P1 в данный момент не открыт, эта инструкция ничего не делает.

11 Commit 0 0

Инструкция Commit применяет все изменения базы данных, внесённые после последней инструкции Transaction. До начала следующей транзакции дальнейшие изменения не допускаются. Инструкция Commit удаляет файл журнала и снимает блокировку записи с базы данных. Блокировка чтения сохраняется, если ещё остаются открытые курсоры.

12 Halt 0 0

Инструкция Halt немедленно останавливает движок VDBE. Все открытые курсоры, списки, сортировки и т. д. автоматически закрываются. P1 — код результата, возвращаемый функцией sqlite_exec(). При нормальном завершении это должно быть SQLITE_OK (0). При ошибке может возвращаться другое значение. Операнд P2 используется только при ошибке. В конце каждой программы подразумевается инструкция "Halt 0 0 0", которую VDBE добавляет при подготовке программы к выполнению.

Трассировка выполнения программы VDBE

Если библиотека SQLite скомпилирована без макроса препроцессора NDEBUG, то PRAGMA vdbe_trace заставляет VDBE трассировать выполнение программ. Хотя эта возможность изначально предназначалась для тестирования и отладки, она также может быть полезна для изучения работы VDBE. Используйте "PRAGMA vdbe_trace=ON;", чтобы включить трассировку, и "PRAGMA vdbe_trace=OFF", чтобы выключить её. Например:

sqlite> PRAGMA vdbe_trace=ON;
 0 Halt 0 0
 sqlite> INSERT INTO examp VALUES('Hello, World!',99);
 0 Transaction 0 0
 1 VerifyCookie 0 81
 2 Transaction 1 0
 3 Integer 0 0
 Stack: i:0
 4 OpenWrite 0 3 examp
 5 NewRecno 0 0
 Stack: i:2
 6 String 0 0 Hello, World!
 Stack: t[Hello,.World!] i:2
 7 Integer 99 0 99
 Stack: si:99 t[Hello,.World!] i:2
 8 MakeRecord 2 0
 Stack: s[...Hello,.World!.99] i:2
 9 PutIntKey 0 1
 10 Close 0 0
 11 Commit 0 0
 12 Halt 0 0

В режиме трассировки VDBE выводит каждую инструкцию перед её выполнением. После выполнения инструкции отображаются несколько верхних элементов стека. Если стек пуст, его содержимое не выводится.

В выводе стека большинство элементов снабжены префиксом, указывающим тип данных этого элемента. Целые числа начинаются с "i:". Числа с плавающей запятой начинаются с "r:". (Буква "r" означает "вещественное число".) Строки начинаются с одного из префиксов "s:", "t:", "e:" или "z:". Различие между префиксами строк обусловлено способом выделения для них памяти. Строки z: хранятся в памяти, полученной с помощью malloc(). Строки t: размещены статически. Строки e: являются временными. У всех остальных строк префикс s:. Для вас, наблюдателя, это не имеет значения, но для VDBE это крайне важно, поскольку строки z: необходимо передавать в free() при удалении из стека, чтобы избежать утечки памяти. Обратите внимание, что для строковых значений отображаются только первые 10 символов, а двоичные значения (например, результат инструкции MakeRecord) рассматриваются как строки. Единственный другой тип данных, который может храниться в стеке VDBE, — это NULL; он отображается без префикса, просто как "NULL". Если целое число помещено в стек одновременно как целое число и как строка, его префикс — "si:".

Простые запросы

Теперь вы должны понимать основы записи данных в базу данных с помощью VDBE. Давайте посмотрим, как он выполняет запросы. В качестве примера используем следующую простую инструкцию SELECT:

SELECT * FROM examp;

Программа VDBE, сформированная для этой инструкции SQL, выглядит следующим образом:

sqlite> EXPLAIN SELECT * FROM examp;
 addr opcode p1 p2 p3 
 ---- ------------ ----- ----- -----------------------------------
 0 ColumnName 0 0 one 
 1 ColumnName 1 0 two 
 2 Integer 0 0 
 3 OpenRead 0 3 examp 
 4 VerifyCookie 0 81 
 5 Rewind 0 10 
 6 Column 0 0 
 7 Column 0 1 
 8 Callback 2 0 
 9 Next 0 6 
 10 Close 0 0 
 11 Halt 0 0

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

int Callback(void *pUserData, int nColumn, char *azData[], char *azColumnName[]);

Библиотека SQLite передаёт VDBE указатель на функцию обратного вызова и указатель pUserData. (Функция обратного вызова и пользовательские данные изначально передавались в качестве аргументов API-функции sqlite_exec().) Задача VDBE — определить значения для nColumn, azData[] и azColumnName[]. Разумеется, nColumn — это количество столбцов в результатах. azColumnName[] — массив строк, где каждая строка является именем одного из столбцов результата. azData[] — массив строк, содержащих фактические данные.

0 ColumnName 0 0 one 1 ColumnName 1 0 two

Первые две инструкции программы VDBE для нашего запроса предназначены для задания значений azColumn. Инструкции ColumnName сообщают VDBE, какие значения поместить в каждый элемент массива azColumnName[]. Каждый запрос начинается с одной инструкции ColumnName для каждого столбца результата; позднее в запросе для каждой из них будет соответствующая инструкция Column.

2 Integer 0 0 3 OpenRead 0 3 examp 4 VerifyCookie 0 81

Инструкции 2 и 3 открывают курсор для чтения таблицы базы данных, к которой выполняется запрос. Это работает так же, как инструкция OpenWrite в примере с INSERT, за исключением того, что на этот раз курсор открывается для чтения, а не для записи. Инструкция 4 проверяет схему базы данных так же, как в примере с INSERT.

5 Rewind 0 10

Инструкция Rewind инициализирует цикл по таблице "examp". Она перемещает курсор P1 к первой записи таблицы. Это необходимо инструкциям Column и Next, которые используют курсор для перебора таблицы. Если таблица пуста, выполняется переход к P2 (10) — инструкции, следующей сразу за циклом. Если таблица не пуста, выполнение переходит к следующей инструкции 6, с которой начинается тело цикла.

6 Column 0 0 7 Column 0 1 8 Callback 2 0

Инструкции с 6 по 8 образуют тело цикла, которое будет выполняться один раз для каждой записи в файле базы данных. Инструкции Column по адресам 6 и 7 извлекают из курсора P1 столбец с номером P2 и помещают его в стек. В этом примере первая инструкция Column помещает в стек значение столбца "one", а вторая — значение столбца "two". Инструкция Callback по адресу 8 вызывает функцию callback(). Операнд P1 инструкции Callback становится значением nColumn. Инструкция Callback извлекает из стека P1 значений и использует их для заполнения массива azData[].

9 Next 0 6

Инструкция по адресу 9 выполняет переход, необходимый для цикла. Вместе с инструкцией Rewind по адресу 5 она образует логику цикла. Это ключевое понятие, которому следует уделить особое внимание. Инструкция Next перемещает курсор P1 к следующей записи. Если перемещение курсора выполнено успешно, сразу происходит переход к P2 (6 — началу тела цикла). Если курсор находился в конце таблицы, выполнение переходит к следующей инструкции, завершающей цикл.

10 Close 0 0 11 Halt 0 0

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

Обратите внимание, что в программе этого запроса SELECT нет инструкций Transaction и Commit, использованных в примере с INSERT. Поскольку SELECT выполняет чтение и не изменяет базу данных, транзакция ему не требуется.

Немного более сложный запрос

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

SELECT one, two, one || two AS 'both'
FROM examp
WHERE one LIKE 'H%'

Этот запрос, возможно, несколько искусственный, но он хорошо иллюстрирует рассматриваемые идеи. Результат будет содержать три столбца с именами "one", "two" и "both". Первые два столбца являются копиями двух столбцов таблицы, а третий столбец результата — строка, полученная конкатенацией первого и второго столбцов таблицы. Наконец, предложение WHERE указывает, что в результат попадут только строки, в которых значение столбца "one" начинается с "H". Ниже показана программа VDBE для этого запроса:

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 ColumnName 0 0 one 1 ColumnName 1 0 two 2 ColumnName 2 0 both 3 Integer 0 0 4 OpenRead 0 3 examp 5 VerifyCookie 0 81 6 Rewind 0 18 7 String 0 0 H% 8 Column 0 0 9 Function 2 0 ptr(0x7f1ac0) 10 IfNot 1 17 11 Column 0 0 12 Column 0 1 13 Column 0 0 14 Column 0 1 15 Concat 2 0 16 Callback 3 0 17 Next 0 7 18 Close 0 0 19 Halt 0 0

Если не учитывать предложение WHERE, структура программы в этом примере очень похожа на структуру предыдущего примера, только добавлен ещё один столбец. Теперь столбцов 3 вместо 2, как раньше, и инструкций ColumnName тоже три. Как и в предыдущем примере, курсор открывается с помощью инструкции OpenRead. Инструкции Rewind по адресу 6 и Next по адресу 17 образуют цикл по всем записям таблицы. Инструкция Close в конце нужна, чтобы инструкции Rewind было куда перейти после завершения работы. Всё это устроено так же, как в первом примере запроса.

В этом примере инструкция Callback должна сформировать данные для трёх столбцов результата вместо двух, но в остальном она работает так же, как в первом запросе. При вызове инструкции Callback самый левый столбец результата должен находиться внизу стека, а самый правый — на вершине. По адресам с 11 по 15 видно, как подготавливается стек. Инструкции Column по адресам 11 и 12 помещают в стек значения первых двух столбцов результата. Две инструкции Column по адресам 13 и 14 извлекают значения, необходимые для вычисления третьего столбца результата, а инструкция Concat по адресу 15 объединяет их в один элемент стека.

Единственное действительно новое в этом примере — предложение WHERE, реализованное инструкциями по адресам с 7 по 10. Инструкции по адресам 7 и 8 помещают в стек значение столбца "one" из таблицы и строковый литерал "H%". Инструкция Function по адресу 9 извлекает эти два значения из стека и помещает в него результат функции LIKE(). Инструкция IfNot извлекает верхнее значение стека и немедленно переходит к инструкции Next, если верхнее значение ложно (не соответствует строковому литералу "H%"). Этот переход фактически пропускает вызов обратного вызова — именно этого и добивается предложение WHERE. Если результат сравнения истинен, переход не выполняется, и управление переходит к следующей инструкции Callback.

Обратите внимание на реализацию оператора LIKE. В SQLite это пользовательская функция, поэтому в P3 указывается адрес её определения. Операнд P1 задаёт количество аргументов функции, которые следует извлечь из стека. В данном случае функция LIKE() принимает 2 аргумента. Аргументы извлекаются из стека в обратном порядке (справа налево), поэтому образец для сравнения находится на вершине стека, а следующим элементом идут данные для сравнения. Возвращаемое значение помещается в стек.

Шаблон программ SELECT

Первые два примера запросов демонстрируют шаблон, которому следует каждая программа SELECT. В общем случае он выглядит так:

Инициализировать массив azColumnName[] для функции обратного вызова.
Открыть курсор для таблицы, к которой выполняется запрос.
Для каждой записи в таблице выполнить:
1. Если условие WHERE ложно, пропустить следующие шаги и перейти к следующей записи.
2. Вычислить все столбцы текущей строки результата.
3. Вызвать функцию обратного вызова для текущей строки результата.
Закрыть курсор.

Этот шаблон значительно расширится при рассмотрении дополнительных сложностей, таких как соединения, составные запросы, использование индексов для ускорения поиска, сортировка, а также агрегатные функции с предложениями GROUP BY и HAVING и без них. Но основные идеи останутся прежними.

Инструкции UPDATE и DELETE

Инструкции UPDATE и DELETE кодируются с использованием шаблона, очень похожего на шаблон инструкции SELECT. Главное отличие, разумеется, в том, что конечное действие — изменение базы данных, а не вызов функции обратного вызова. Поскольку база данных изменяется, также используются транзакции. Начнём с рассмотрения инструкции DELETE:

DELETE FROM examp WHERE two<50;

Эта инструкция DELETE удалит все записи из таблицы "examp", в которых значение столбца "two" меньше 50. Для этого генерируется следующий код:

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 Transaction 1 0 1 Transaction 0 0 2 VerifyCookie 0 178 3 Integer 0 0 4 OpenRead 0 3 examp 5 Rewind 0 12 6 Column 0 1 7 Integer 50 0 50 8 Ge 1 11 9 Recno 0 0 10 ListWrite 0 0 11 Next 0 6 12 Close 0 0 13 ListRewind 0 0 14 Integer 0 0 15 OpenWrite 0 3 16 ListRead 0 20 17 NotExists 0 19 18 Delete 0 1 19 Goto 0 16 20 ListReset 0 0 21 Close 0 0 22 Commit 0 0 23 Halt 0 0

Программа должна выполнить следующие действия. Сначала ей нужно найти все записи таблицы "examp", которые следует удалить. Это делается с помощью цикла, очень похожего на цикл из приведённых выше примеров SELECT. После того как все записи найдены, можно вернуться к ним и удалить по одной. Обратите внимание: нельзя удалять каждую запись сразу после её обнаружения. Сначала нужно найти все записи, а затем вернуться и удалить их. Это связано с тем, что серверная часть базы данных SQLite может изменить порядок сканирования после операции удаления. Если порядок сканирования изменится в середине прохода, некоторые записи могут быть просмотрены более одного раза, а другие — не просмотрены вовсе.

Таким образом, реализация DELETE фактически состоит из двух циклов. Первый цикл (инструкции с 5 по 11) находит записи, которые нужно удалить, и сохраняет их ключи во временный список, а второй цикл (инструкции с 16 по 19) использует этот список ключей, чтобы поочерёдно удалять записи.

0 Transaction 1 0 1 Transaction 0 0 2 VerifyCookie 0 178 3 Integer 0 0 4 OpenRead 0 3 examp

Инструкции с 0 по 4 такие же, как в примере с INSERT. Они начинают транзакции для основной и временной баз данных, проверяют схему основной базы данных и открывают курсор для чтения таблицы "examp". Обратите внимание, что курсор открыт для чтения, а не для записи. На этом этапе программы мы только сканируем таблицу, а не изменяем её. Позже, на инструкции 15, мы повторно откроем ту же таблицу для записи.

5 Rewind 0 12

Как и в примере с SELECT, инструкция Rewind перемещает курсор к началу таблицы, подготавливая его к использованию в теле цикла.

6 Column 0 1 7 Integer 50 0 50 8 Ge 1 11

Предложение WHERE реализовано инструкциями с 6 по 8. Задача условия WHERE — пропустить инструкцию ListWrite, если условие WHERE ложно. Для этого при значении столбца "two" (извлечённом инструкцией Column), большем или равном 50, выполняется переход к инструкции Next.

Как и раньше, инструкция Column использует курсор P1 и помещает в стек запись данных из столбца P2 (1 — столбец "two"). Инструкция Integer помещает значение 50 на вершину стека. После этих двух инструкций стек выглядит так:

(целое число) 50

(запись) текущая запись для столбца "two"

Оператор Ge сравнивает два верхних элемента стека, извлекает их, а затем выполняет переход в зависимости от результата сравнения. Если второй элемент больше или равен верхнему, выполняется переход по адресу P2 (к инструкции Next в конце цикла). Поскольку P1 равен true, переход также выполняется, если один из операндов равен NULL (и результат сравнения, соответственно, равен NULL). Если переход не выполняется, программа просто переходит к следующей инструкции.

9 Recno 0 0 10 ListWrite 0 0

Инструкция Recno помещает в стек целое число, представляющее собой первые 4 байта ключа текущей записи при последовательном сканировании таблицы, на которую указывает курсор P1. Инструкция ListWrite записывает целое число с вершины стека во временный список хранения и извлекает верхний элемент. Это важная работа данного цикла: сохранить ключи записей, которые требуется удалить, чтобы во втором цикле удалить сами записи. После этой инструкции ListWrite стек снова пуст.

11 Next 0 6 12 Close 0 0

Инструкция Next перемещает курсор к следующему элементу таблицы, на которую указывает курсор P0, и, если перемещение прошло успешно, выполняет переход к P2 (6 — началу тела цикла). Инструкция Close закрывает курсор P1. Она не влияет на временный список хранения, поскольку он не связан с курсором P1, а является глобальным рабочим списком (который можно сохранить с помощью ListPush).

13 ListRewind 0 0

Инструкция ListRewind перемещает временный список хранения к его началу. Это подготавливает его к использованию во втором цикле.

14 Integer 0 0 15 OpenWrite 0 3

Как и в примере с INSERT, мы помещаем номер базы данных P1 (0 — основная база данных) в стек и используем OpenWrite, чтобы открыть курсор P1 для изменения таблицы P2 (базовая страница 3, "examp").

16 ListRead 0 20 17 NotExists 0 19 18 Delete 0 1 19 Goto 0 16

Этот цикл выполняет фактическое удаление. Он организован иначе, чем цикл в примере с UPDATE. Инструкция ListRead выполняет роль, которую в цикле INSERT выполняла инструкция Next, но, поскольку при неудаче она переходит к P2, а Next выполняет переход при успехе, ListRead помещена в начало цикла, а не в конец. Это означает, что в конце цикла нужно поместить Goto, чтобы вернуться к проверке условия в начале. Таким образом, этот цикл имеет форму цикла C while(){...}, тогда как цикл в примере с INSERT имел форму do{...}while(). Инструкция Delete выполняет роль, которую в предыдущих примерах выполняла функция обратного вызова.

Инструкция ListRead считывает элемент из временного списка хранения и помещает его в стек. Если чтение прошло успешно, выполнение переходит к следующей инструкции. Если список пуст, происходит переход к P2 — инструкции, расположенной сразу за циклом. После этого стек выглядит следующим образом:

(целое число) ключ текущей записи

Обратите внимание на сходство инструкций ListRead и Next. Обе операции работают по одному правилу:

Поместить следующий «элемент» в стек и перейти к следующей инструкции ИЛИ выполнить переход к P2 — в зависимости от того, есть ли следующий «элемент», который можно поместить в стек.

Одно из различий между Next и ListRead — то, что они считают «элементом». Для инструкции Next «элементами» являются записи в файле базы данных. Для ListRead «элементами» являются целочисленные ключи в списке. Ещё одно различие — переходить ли к следующей инструкции или выполнять переход, если следующего «элемента» нет. В данном случае Next переходит к следующей инструкции, а ListRead выполняет переход. Позже мы увидим другие инструкции цикла (NextIdx и SortNext), работающие по тому же принципу.

Инструкция NotExists извлекает верхний элемент стека и использует его как целочисленный ключ. Если в таблице P1 нет записи с таким ключом, выполняется переход к P2. Если запись существует, выполнение переходит к следующей инструкции. В данном случае P2 указывает на Goto в конце цикла, который возвращает выполнение к ListRead в начале. Можно было бы указать для P2 значение 16 — адрес ListRead в начале цикла, — но синтаксический анализатор SQLite, сгенерировавший этот код, не выполнил такую оптимизацию.

Инструкция Delete выполняет основную работу этого цикла: извлекает из стека целочисленный ключ (помещённый туда предыдущей инструкцией ListRead) и удаляет запись с этим ключом из курсора P1. Поскольку P2 равен true, счётчик изменений строк увеличивается.

Инструкция Goto выполняет переход к началу цикла. На этом цикл заканчивается.

20 ListReset 0 0 21 Close 0 0 22 Commit 0 0 23 Halt 0 0

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

Инструкция ListReset очищает временный список хранения. Этот список очищается автоматически при завершении программы VDBE, поэтому в данном случае эта инструкция не нужна. Инструкция Close закрывает курсор P1. Это также делает движок VDBE по завершении выполнения программы. Commit успешно завершает текущую транзакцию и сохраняет в базе данных все изменения, внесённые в ходе этой транзакции. Последняя инструкция Halt тоже не нужна, поскольку она добавляется в каждую программу VDBE при подготовке к выполнению.

Инструкции UPDATE очень похожи на DELETE, за исключением того, что вместо удаления записи они заменяют её новой. Рассмотрим следующий пример:

UPDATE examp SET one= '(' || one || ')' WHERE two < 50;

Вместо удаления записей, в которых значение столбца "two" меньше 50, эта инструкция просто заключает значение столбца "one" в скобки. Программа VDBE для выполнения этой инструкции приведена ниже:

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 Transaction 1 0 1 Transaction 0 0 2 VerifyCookie 0 178 3 Integer 0 0 4 OpenRead 0 3 examp 5 Rewind 0 12 6 Column 0 1 7 Integer 50 0 50 8 Ge 1 11 9 Recno 0 0 10 ListWrite 0 0 11 Next 0 6 12 Close 0 0 13 Integer 0 0 14 OpenWrite 0 3 15 ListRewind 0 0 16 ListRead 0 28 17 Dup 0 0 18 NotExists 0 16 19 String 0 0 ( 20 Column 0 0 21 Concat 2 0 22 String 0 0 ) 23 Concat 2 0 24 Column 0 1 25 MakeRecord 2 0 26 PutIntKey 0 1 27 Goto 0 16 28 ListReset 0 0 29 Close 0 0 30 Commit 0 0 31 Halt 0 0

Эта программа по существу совпадает с программой DELETE, за исключением того, что тело второго цикла заменено последовательностью инструкций (по адресам с 17 по 26), которые обновляют запись, а не удаляют её. Большинство этих инструкций должно быть вам уже знакомо, но есть несколько небольших нюансов, поэтому мы кратко их рассмотрим. Также обратите внимание, что порядок некоторых инструкций до и после второго цикла изменился. Это лишь следствие того, что синтаксический анализатор SQLite выбрал другой шаблон для вывода кода.

При входе в тело второго цикла (на инструкции 17) стек содержит одно целое число — ключ записи, которую мы хотим изменить. Нам нужно использовать этот ключ дважды: сначала, чтобы получить старое значение записи, а затем, чтобы записать изменённую запись. Поэтому первая инструкция — Dup, создающая копию ключа на вершине стека. Инструкция Dup может дублировать любой элемент стека, а не только верхний. Операнд P1 задаёт, какой элемент следует продублировать. Если P1 равен 0, дублируется вершина стека. Если P1 равен 1, дублируется следующий элемент ниже. И так далее.

После дублирования ключа следующая инструкция, NotExists, однократно извлекает элемент стека и использует извлечённое значение как ключ для проверки наличия записи в файле базы данных. Если записи с таким ключом нет, выполняется переход обратно к ListRead, чтобы получить следующий ключ.

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

(record) новая запись данных

(integer) ключ

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

CREATE и DROP

Использование CREATE или DROP для создания или удаления таблицы либо индекса, с точки зрения VDBE, по сути эквивалентно выполнению INSERT или DELETE для специальной таблицы «sqlite_master». Таблица sqlite_master — специальная таблица, которая автоматически создаётся для каждой базы данных SQLite. Она выглядит так:

CREATE TABLE sqlite_master (
  type      TEXT,    -- either "table" or "index"
  name      TEXT,    -- name of this table or index
  tbl_name  TEXT,    -- for indices: name of associated table
  sql       TEXT     -- SQL text of the original CREATE statement
)

Для каждой таблицы (кроме самой таблицы «sqlite_master») и каждого именованного индекса в базе данных SQLite существует запись в таблице sqlite_master. Эту таблицу можно запрашивать с помощью инструкции SELECT, как и любую другую таблицу. Но напрямую изменять её с помощью UPDATE, INSERT или DELETE нельзя. Изменения sqlite_master должны выполняться командами CREATE и DROP, поскольку SQLite также необходимо обновлять некоторые внутренние структуры данных при добавлении или удалении таблиц и индексов.

Однако с точки зрения VDBE команда CREATE работает почти так же, как INSERT, а DROP — как DELETE. Когда библиотека SQLite открывает существующую базу данных, первым делом она выполняет SELECT, чтобы прочитать столбцы «sql» всех записей таблицы sqlite_master. Столбец «sql» содержит полный текст инструкции CREATE, с помощью которой изначально был создан индекс или таблица. Этот текст передаётся обратно синтаксическому анализатору SQLite и используется для восстановления внутренних структур данных, описывающих индекс или таблицу.

Использование индексов для ускорения поиска

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

Файл SQLite связывает ключ с некоторыми данными. Для таблицы SQLite файл базы данных устроен так, что ключ является целым числом, а данные содержат информацию об одной строке таблицы. В индексах SQLite эта схема обращена: ключ индекса содержит часть сохраняемой информации, а данные индекса представляют собой целое число. Чтобы получить строку таблицы с определённым содержимым, сначала ищут это содержимое в таблице индекса, чтобы найти соответствующий целочисленный индекс, а затем используют это целое число для поиска полной записи в таблице.

Обратите внимание, что SQLite использует B-деревья — упорядоченную структуру данных, поэтому индексы можно использовать, если предложение WHERE инструкции SELECT содержит проверки на равенство или неравенство. В приведённых ниже запросах можно использовать индекс, если он доступен:

SELECT * FROM examp WHERE two==50;
SELECT * FROM examp WHERE two<50;
SELECT * FROM examp WHERE two IN (50, 100);

Если существует индекс, сопоставляющий столбец «two» таблицы «examp» целым числам, SQLite использует его, чтобы найти целочисленные ключи всех строк таблицы examp, в которых значение столбца two равно 50, меньше 50 и так далее. Однако в следующих запросах использовать индекс нельзя:

SELECT * FROM examp WHERE two%50 == 10;
SELECT * FROM examp WHERE two&127 == 3;

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

SELECT * FROM examp WHERE two+10 == 50;
SELECT * FROM examp WHERE two==50 OR two==100;

Чтобы лучше понять, как работают индексы, сначала рассмотрим, как их создают. Давайте создадим индекс для столбца two таблицы examp. Выполним:

CREATE INDEX examp_idx1 ON examp(two);

Код VDBE, сгенерированный приведённой выше инструкцией, выглядит так:

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 Transaction 1 0 1 Transaction 0 0 2 VerifyCookie 0 178 3 Integer 0 0 4 OpenWrite 0 2 5 NewRecno 0 0 6 String 0 0 index 7 String 0 0 examp_idx1 8 String 0 0 examp 9 CreateIndex 0 0 ptr(0x791380) 10 Dup 0 0 11 Integer 0 0 12 OpenWrite 1 0 13 String 0 0 CREATE INDEX examp_idx1 ON examp(tw 14 MakeRecord 5 0 15 PutIntKey 0 0 16 Integer 0 0 17 OpenRead 2 3 examp 18 Rewind 2 24 19 Recno 2 0 20 Column 2 1 21 MakeIdxKey 1 0 n 22 IdxPut 1 0 indexed columns are not unique 23 Next 2 19 24 Close 2 0 25 Close 1 0 26 Integer 333 0 27 SetCookie 0 0 28 Close 0 0 29 Commit 0 0 30 Halt 0 0

Помните, что для каждой таблицы (кроме sqlite_master) и каждого именованного индекса существует запись в таблице sqlite_master. Поскольку мы создаём новый индекс, необходимо добавить новую запись в sqlite_master. Это выполняют инструкции с 3-й по 15-ю. Добавление записи в sqlite_master работает так же, как любая другая инструкция INSERT, поэтому мы не будем останавливаться на этом подробнее. В данном примере нас интересует заполнение нового индекса допустимыми данными, которое выполняется инструкциями с 16-й по 23-ю.

16 Integer 0 0 17 OpenRead 2 3 examp

Сначала индексируемая таблица открывается для чтения. Чтобы создать индекс для таблицы, необходимо знать, какие данные она содержит. Индекс уже был открыт для записи с помощью курсора 0 инструкциями 3 и 4.

18 Rewind 2 24 19 Recno 2 0 20 Column 2 1 21 MakeIdxKey 1 0 n 22 IdxPut 1 0 indexed columns are not unique 23 Next 2 19

Инструкции с 18-й по 23-ю реализуют цикл по каждой строке индексируемой таблицы. Для каждой строки таблицы сначала с помощью Recno в инструкции 19 извлекается целочисленный ключ этой строки, а затем с помощью Column в инструкции 20 получается значение столбца «two». Инструкция MakeIdxKey в позиции 21 преобразует данные столбца «two» (находящиеся на вершине стека) в допустимый ключ индекса. Для индекса по одному столбцу это, по сути, пустая операция. Но если бы операнд P1 инструкции MakeIdxKey был больше единицы, со стека было бы снято несколько элементов и преобразовано в один ключ индекса. Инструкция IdxPut в позиции 22 фактически создаёт запись индекса. IdxPut снимает со стека два элемента. Элемент на вершине стека используется как ключ для поиска записи в таблице индекса. Затем целое число, находившееся вторым на стеке, добавляется в набор целых чисел для этого индекса, а новая запись сохраняется обратно в файл базы данных. Обратите внимание, что одна запись индекса может содержать несколько целых чисел, если две или более записи таблицы имеют одинаковое значение столбца two.

Теперь посмотрим, как будет использоваться этот индекс. Рассмотрим следующий запрос:

SELECT * FROM examp WHERE two==50;

Для обработки этого запроса SQLite генерирует следующий код VDBE:

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 ColumnName 0 0 one 1 ColumnName 1 0 two 2 Integer 0 0 3 OpenRead 0 3 examp 4 VerifyCookie 0 256 5 Integer 0 0 6 OpenRead 1 4 examp_idx1 7 Integer 50 0 50 8 MakeKey 1 0 n 9 MemStore 0 0 10 MoveTo 1 19 11 MemLoad 0 0 12 IdxGT 1 19 13 IdxRecno 1 0 14 MoveTo 0 0 15 Column 0 0 16 Column 0 1 17 Callback 2 0 18 Next 1 11 19 Close 0 0 20 Close 1 0 21 Halt 0 0

Инструкция SELECT начинается привычным образом. Сначала инициализируются имена столбцов и открывается запрашиваемая таблица. Начиная с инструкций 5 и 6 появляются отличия: также открывается файл индекса. Инструкции 7 и 8 создают ключ со значением 50. Инструкция MemStore в позиции 9 сохраняет ключ индекса в ячейке памяти VDBE с номером 0. Память VDBE используется, чтобы не извлекать значение из глубины стека: это возможно, но усложняет генерацию программы. Следующая инструкция, MoveTo по адресу 10, снимает ключ со стека и перемещает курсор индекса к первой строке индекса с этим ключом. Так курсор подготавливается к использованию в следующем цикле.

Инструкции с 11-й по 18-ю реализуют цикл по всем записям индекса с ключом, полученным инструкцией 8. Все записи индекса с этим ключом расположены в таблице индекса подряд, поэтому мы перебираем их и извлекаем соответствующий ключ таблицы. Затем этот ключ таблицы используется для перемещения курсора к нужной строке таблицы. Остальная часть цикла совпадает с циклом для запроса SELECT без индекса.

Цикл начинается с инструкции MemLoad в позиции 11, которая помещает копию ключа индекса обратно на стек. Инструкция IdxGT в позиции 12 сравнивает этот ключ с ключом текущей записи индекса, на которую указывает курсор P1. Если ключ индекса в текущей позиции курсора больше искомого индекса, цикл завершается.

Инструкция IdxRecno в позиции 13 помещает на стек номер записи таблицы из индекса. Следующая инструкция MoveTo снимает его со стека и перемещает курсор таблицы к этой строке. Следующие три инструкции выбирают данные столбцов так же, как и в случае без индекса. Инструкции Column извлекают данные столбцов и вызывается функция обратного вызова. Последняя инструкция Next перемещает курсор индекса, а не таблицы, к следующей строке и затем возвращает выполнение в начало цикла, если в индексе ещё остались записи.

Поскольку индекс используется для поиска значений в таблице, важно поддерживать согласованность индекса и таблицы. Теперь, когда у таблицы examp есть индекс, его необходимо обновлять при каждой вставке, удалении или изменении данных в таблице examp. Помните первый пример выше, где для добавления новой строки в таблицу «examp» понадобилось 12 инструкций VDBE. Теперь, когда у таблицы есть индекс, требуется 19 инструкций. Вот инструкция SQL:

INSERT INTO examp VALUES('Hello, World!',99);

А вот сгенерированный код:

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 Transaction 1 0 1 Transaction 0 0 2 VerifyCookie 0 256 3 Integer 0 0 4 OpenWrite 0 3 examp 5 Integer 0 0 6 OpenWrite 1 4 examp_idx1 7 NewRecno 0 0 8 String 0 0 Hello, World! 9 Integer 99 0 99 10 Dup 2 1 11 Dup 1 1 12 MakeIdxKey 1 0 n 13 IdxPut 1 0 14 MakeRecord 2 0 15 PutIntKey 0 1 16 Close 0 0 17 Close 1 0 18 Commit 0 0 19 Halt 0 0

К этому моменту вы должны достаточно хорошо понимать VDBE, чтобы самостоятельно разобраться в работе приведённой выше программы. Поэтому мы не будем рассматривать её подробнее.

Соединения

При соединении две или более таблицы объединяются для формирования единого результата. Итоговая таблица состоит из всех возможных сочетаний строк соединяемых таблиц. Самый простой и естественный способ реализации — вложенные циклы.

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

Инициализировать массив azColumnName[] для функции обратного вызова.
Открыть два курсора — по одному для каждой из двух запрашиваемых таблиц.
Для каждой записи первой таблицы выполнить следующее:
1. Для каждой записи второй таблицы выполнить следующее:
  1. Если условие WHERE имеет значение FALSE, пропустить следующие шаги и перейти к следующей записи.
  2. Вычислить все столбцы текущей строки результата.
  3. Вызвать функцию обратного вызова для текущей строки результата.
Закрыть оба курсора.

Этот шаблон будет работать, но, скорее всего, медленно, поскольку теперь мы имеем дело с циклом сложности O(N²). Однако часто условие WHERE можно разложить на части, и одна или несколько из них будут зависеть только от столбцов первой таблицы. В таком случае часть проверки WHERE можно вынести из внутреннего цикла и существенно повысить эффективность. Поэтому более удачный шаблон будет выглядеть примерно так:

Инициализировать массив azColumnName[] для функции обратного вызова.
Открыть два курсора — по одному для каждой из двух запрашиваемых таблиц.
Для каждой записи первой таблицы выполнить следующее:
1. Вычислить части условия WHERE, которые зависят только от столбцов первой таблицы. Если хотя бы одна из них ложна (то есть всё условие WHERE обязательно ложно), пропустить оставшуюся часть этого цикла и перейти к следующей записи.
2. Для каждой записи второй таблицы выполнить следующее:
  1. Если условие WHERE имеет значение FALSE, пропустить следующие шаги и перейти к следующей записи.
  2. Вычислить все столбцы текущей строки результата.
  3. Вызвать функцию обратного вызова для текущей строки результата.
Закрыть оба курсора.

Дополнительно ускорить поиск в одном или обоих циклах можно с помощью индекса.

SQLite всегда строит циклы в том же порядке, в котором таблицы указаны в предложении FROM инструкции SELECT. Самая левая таблица становится внешним циклом, а самая правая — внутренним. Теоретически в некоторых случаях циклы можно переставить, чтобы ускорить выполнение соединения. Однако SQLite не пытается выполнять такую оптимизацию.

Посмотреть, как SQLite строит вложенные циклы, можно на следующем примере:

CREATE TABLE examp2(three int, four int);
SELECT * FROM examp, examp2 WHERE two<50 AND four==two;

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 ColumnName 0 0 examp.one 1 ColumnName 1 0 examp.two 2 ColumnName 2 0 examp2.three 3 ColumnName 3 0 examp2.four 4 Integer 0 0 5 OpenRead 0 3 examp 6 VerifyCookie 0 909 7 Integer 0 0 8 OpenRead 1 5 examp2 9 Rewind 0 24 10 Column 0 1 11 Integer 50 0 50 12 Ge 1 23 13 Rewind 1 23 14 Column 1 1 15 Column 0 1 16 Ne 1 22 17 Column 0 0 18 Column 0 1 19 Column 1 0 20 Column 1 1 21 Callback 4 0 22 Next 1 14 23 Next 0 10 24 Close 0 0 25 Close 1 0 26 Halt 0 0

Внешний цикл по таблице examp реализован инструкциями с 7-й по 23-ю. Внутренний цикл — инструкциями с 13-й по 22-ю. Обратите внимание: часть выражения WHERE «two<50» зависит только от столбцов первой таблицы, поэтому её можно вынести из внутреннего цикла. SQLite так и делает: проверка «two<50» реализована инструкциями с 10-й по 12-ю. Проверка «four==two» реализована инструкциями с 14-й по 16-ю во внутреннем цикле.

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

Предложение ORDER BY

По историческим причинам и для повышения эффективности вся сортировка в настоящее время выполняется в памяти.

SQLite реализует предложение ORDER BY с помощью специального набора инструкций для управления объектом, называемым сортировщиком. Во внутреннем цикле запроса, где обычно находилась бы инструкция Callback, вместо неё формируется запись, содержащая параметры обратного вызова и ключ. Эта запись добавляется в сортировщик (связный список). После завершения цикла запроса список записей сортируется, а затем обходится. Для каждой записи в списке вызывается функция обратного вызова. В конце сортировщик закрывается, а память освобождается.

Рассмотрим, как это работает, на следующем запросе:

SELECT * FROM examp ORDER BY one DESC, two;

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 ColumnName 0 0 one 1 ColumnName 1 0 two 2 Integer 0 0 3 OpenRead 0 3 examp 4 VerifyCookie 0 909 5 Rewind 0 14 6 Column 0 0 7 Column 0 1 8 SortMakeRec 2 0 9 Column 0 0 10 Column 0 1 11 SortMakeKey 2 0 D+ 12 SortPut 0 0 13 Next 0 6 14 Close 0 0 15 Sort 0 0 16 SortNext 0 19 17 SortCallback 2 0 18 Goto 0 16 19 SortReset 0 0 20 Halt 0 0

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

Цикл запроса состоит из инструкций с 5-й по 13-ю. Инструкции с 6-й по 8-ю формируют запись со значениями azData[] для одного вызова функции обратного вызова. Инструкции с 9-й по 11-ю создают ключ сортировки. Инструкция 12 объединяет запись вызова и ключ сортировки в одну запись и добавляет её в список сортировки.

Особый интерес представляет аргумент P3 инструкции 11. Ключ сортировки формируется так: перед каждой строкой добавляется один символ из P3, после чего все строки объединяются. Функция сравнения при сортировке использует этот символ, чтобы определить направление сортировки — по возрастанию или убыванию, а также тип сортировки — строковый или числовой. В этом примере первый столбец должен сортироваться как строка по убыванию, поэтому его префикс — «D», а второй столбец должен сортироваться численно по возрастанию, поэтому его префикс — «+». Для строковой сортировки по возрастанию используется «A», а для числовой сортировки по убыванию — «-».

После завершения цикла запроса на инструкции 14 закрывается запрашиваемая таблица. Это делается заранее, чтобы при необходимости другие процессы или потоки могли получить к ней доступ. Список записей, сформированный в цикле запроса, сортируется инструкцией 15. Инструкции с 16-й по 18-ю обходят список записей (теперь уже отсортированный) и вызывают функцию обратного вызова для каждой записи. Наконец, на инструкции 19 закрывается сортировщик.

Агрегатные функции и предложения GROUP BY и HAVING

Для вычисления агрегатных функций VDBE реализует специальную структуру данных и инструкции для управления ею. Структура данных представляет собой неупорядоченный набор корзин, каждая из которых содержит ключ и одну или несколько ячеек памяти. В цикле запроса предложение GROUP BY используется для формирования ключа, после чего в фокус помещается корзина с этим ключом. Если такой корзины ещё нет, создаётся новая. После этого ячейки памяти корзины используются для накопления значений различных агрегатных функций. Когда цикл запроса завершается, каждая корзина посещается один раз, чтобы сформировать одну строку результата.

Разобраться в этой концепции поможет пример. Рассмотрим следующий запрос:

SELECT three, min(three+four)+avg(four) 
FROM examp2
GROUP BY three;

Для этого запроса генерируется следующий код VDBE:

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 ColumnName 0 0 three 1 ColumnName 1 0 min(three+four)+avg(four) 2 AggReset 0 3 3 AggInit 0 1 ptr(0x7903a0) 4 AggInit 0 2 ptr(0x790700) 5 Integer 0 0 6 OpenRead 0 5 examp2 7 VerifyCookie 0 909 8 Rewind 0 23 9 Column 0 0 10 MakeKey 1 0 n 11 AggFocus 0 14 12 Column 0 0 13 AggSet 0 0 14 Column 0 0 15 Column 0 1 16 Add 0 0 17 Integer 1 0 18 AggFunc 0 1 ptr(0x7903a0) 19 Column 0 1 20 Integer 2 0 21 AggFunc 0 1 ptr(0x790700) 22 Next 0 9 23 Close 0 0 24 AggNext 0 31 25 AggGet 0 0 26 AggGet 0 1 27 AggGet 0 2 28 Add 0 0 29 Callback 2 0 30 Goto 0 24 31 Noop 0 0 32 Halt 0 0

Первая заслуживающая внимания инструкция — AggReset в позиции 2. Инструкция AggReset инициализирует набор пустых корзин и задаёт в P2 количество ячеек памяти, доступных в каждой корзине. В этом примере в каждой корзине будет по три ячейки памяти. Это не сразу очевидно, но, если внимательно изучить остальную часть программы, можно понять, для чего предназначена каждая ячейка.

Ячейка памяти Назначение ячейки памяти

0 Столбец «three» — ключ корзины

1 Минимальное значение «three+four»

2 Сумма всех значений «four». Используется для вычисления «avg(four)».

Ячейка памяти	Назначение ячейки памяти
0	Столбец «three» — ключ корзины
1	Минимальное значение «three+four»
2	Сумма всех значений «four». Используется для вычисления «avg(four)».

Цикл запроса реализован инструкциями с 8-й по 22-ю. Ключ агрегирования, заданный предложением GROUP BY, вычисляется инструкциями 9 и 10. Инструкция 11 помещает нужную корзину в фокус. Если корзины с заданным ключом ещё нет, создаётся новая, и выполнение переходит к инструкциям 12 и 13, которые инициализируют корзину. Если корзина уже существует, выполняется переход к инструкции 14. Значения агрегатных функций обновляются инструкциями с 11-й по 21-ю. Инструкции с 14-й по 18-ю обновляют ячейку памяти 1, чтобы в ней находилось следующее значение «min(three+four)». Затем инструкции с 19-й по 21-ю обновляют сумму столбца «four».

После завершения цикла запроса на инструкции 23 закрывается таблица «examp2», чтобы освободить её блокировку и позволить другим потокам или процессам использовать таблицу. Следующий шаг — пройти по всем агрегатным корзинам и вывести по одной строке результата для каждой из них. Это выполняет цикл инструкций с 24-й по 30-ю. Инструкция AggNext в позиции 24 помещает в фокус следующую корзину или переходит в конец цикла, если все корзины уже просмотрены. Столбцы результата по порядку извлекаются из корзины агрегатора инструкциями с 25-й по 27-ю. Наконец, на инструкции 29 вызывается функция обратного вызова.

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

Если понять, что агрегатный запрос на самом деле состоит из двух последовательных циклов, становится гораздо проще разобраться в различии между предложениями WHERE и HAVING в инструкции SQL-запроса. Предложение WHERE ограничивает первый цикл, а предложение HAVING — второй. Это можно увидеть, добавив в наш пример запроса оба предложения — WHERE и HAVING:

SELECT three, min(three+four)+avg(four) 
FROM examp2
WHERE three>four
GROUP BY three
HAVING avg(four)<10;

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 ColumnName 0 0 three 1 ColumnName 1 0 min(three+four)+avg(four) 2 AggReset 0 3 3 AggInit 0 1 ptr(0x7903a0) 4 AggInit 0 2 ptr(0x790700) 5 Integer 0 0 6 OpenRead 0 5 examp2 7 VerifyCookie 0 909 8 Rewind 0 26 9 Column 0 0 10 Column 0 1 11 Le 1 25 12 Column 0 0 13 MakeKey 1 0 n 14 AggFocus 0 17 15 Column 0 0 16 AggSet 0 0 17 Column 0 0 18 Column 0 1 19 Add 0 0 20 Integer 1 0 21 AggFunc 0 1 ptr(0x7903a0) 22 Column 0 1 23 Integer 2 0 24 AggFunc 0 1 ptr(0x790700) 25 Next 0 9 26 Close 0 0 27 AggNext 0 37 28 AggGet 0 2 29 Integer 10 0 10 30 Ge 1 27 31 AggGet 0 0 32 AggGet 0 1 33 AggGet 0 2 34 Add 0 0 35 Callback 2 0 36 Goto 0 27 37 Noop 0 0 38 Halt 0 0

Код, сгенерированный в последнем примере, совпадает с предыдущим, за исключением двух условных переходов, добавленных для реализации новых предложений WHERE и HAVING. Предложение WHERE реализовано инструкциями с 9-й по 11-ю в цикле запроса. Предложение HAVING реализовано инструкциями с 28-й по 30-ю в цикле вывода.

Использование инструкций SELECT в качестве членов выражения

Само название «язык структурированных запросов» указывает на то, что SQL должен поддерживать вложенные запросы. И действительно, поддерживаются два разных вида вложенности. Любую инструкцию SELECT, возвращающую результат из одной строки и одного столбца, можно использовать как член выражения другой инструкции SELECT. Кроме того, инструкцию SELECT, возвращающую результат из одного столбца и нескольких строк, можно использовать в качестве правого операнда операторов IN и NOT IN. Начнём этот раздел с примера первого вида вложенности, когда инструкция SELECT с одной строкой и одним столбцом используется как член выражения другой инструкции SELECT. Вот наш пример:

SELECT * FROM examp
WHERE two!=(SELECT three FROM examp2
            WHERE four=5);

SQLite сначала выполняет внутреннюю инструкцию SELECT (ту, которая обращается к examp2) и сохраняет результат в отдельной ячейке памяти. Затем при вычислении внешней инструкции SELECT SQLite подставляет значение из этой ячейки вместо внутренней инструкции SELECT. Код выглядит так:

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 String 0 0 1 MemStore 0 1 2 Integer 0 0 3 OpenRead 1 5 examp2 4 VerifyCookie 0 909 5 Rewind 1 13 6 Column 1 1 7 Integer 5 0 5 8 Ne 1 12 9 Column 1 0 10 MemStore 0 1 11 Goto 0 13 12 Next 1 6 13 Close 1 0 14 ColumnName 0 0 one 15 ColumnName 1 0 two 16 Integer 0 0 17 OpenRead 0 3 examp 18 Rewind 0 26 19 Column 0 1 20 MemLoad 0 0 21 Eq 1 25 22 Column 0 0 23 Column 0 1 24 Callback 2 0 25 Next 0 19 26 Close 0 0 27 Halt 0 0

Первые две инструкции инициализируют отдельную ячейку памяти значением NULL. Инструкции со 2-й по 13-ю реализуют внутреннюю инструкцию SELECT для таблицы examp2. Обратите внимание: вместо передачи результата функции обратного вызова или его сохранения в сортировщике результат запроса помещается в ячейку памяти инструкцией 10, а цикл прерывается переходом на инструкции 11. Переход на инструкции 11 — это устаревший код, который никогда не выполняется.

Внешняя инструкция SELECT реализована инструкциями с 14-й по 25-ю. В частности, предложение WHERE с вложенным запросом реализовано инструкциями с 19-й по 21-ю. Видно, что результат внутреннего запроса помещается на стек инструкцией 20 и используется условным переходом на инструкции 21.

Если результат подзапроса является скалярным значением, можно использовать одну отдельную ячейку памяти, как в предыдущем примере. Но если результат подзапроса представляет собой вектор, например когда подзапрос является правым операндом IN или NOT IN, требуется другой подход. В этом случае результат подзапроса сохраняется во временной таблице, а её содержимое проверяется с помощью операторов Found или NotFound. Рассмотрим пример:

SELECT * FROM examp
WHERE two IN (SELECT three FROM examp2);

Код, сгенерированный для реализации этого запроса, выглядит так:

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 OpenTemp 1 1 1 Integer 0 0 2 OpenRead 2 5 examp2 3 VerifyCookie 0 909 4 Rewind 2 10 5 Column 2 0 6 IsNull -1 9 7 String 0 0 8 PutStrKey 1 0 9 Next 2 5 10 Close 2 0 11 ColumnName 0 0 one 12 ColumnName 1 0 two 13 Integer 0 0 14 OpenRead 0 3 examp 15 Rewind 0 25 16 Column 0 1 17 NotNull -1 20 18 Pop 1 0 19 Goto 0 24 20 NotFound 1 24 21 Column 0 0 22 Column 0 1 23 Callback 2 0 24 Next 0 16 25 Close 0 0 26 Halt 0 0

Временная таблица для хранения результатов внутренней инструкции SELECT создаётся инструкцией OpenTemp в позиции 0. Этот код операции используется для таблиц, существующих только в течение выполнения одной инструкции SQL. Временный курсор всегда открывается для чтения и записи, даже если основная база данных доступна только для чтения. Временная таблица автоматически удаляется при закрытии курсора. Значение P2, равное 1, означает, что курсор указывает на индекс BTree, у которого нет данных, но может быть произвольный ключ.

Внутренняя инструкция SELECT реализована инструкциями с 1-й по 10-ю. Этот код лишь создаёт запись во временной таблице для каждой строки таблицы examp2, в которой столбец «three» имеет значение, отличное от NULL. Ключом каждой записи временной таблицы является столбец «three» таблицы examp2, а данными — пустая строка, поскольку они никогда не используются.

Внешняя инструкция SELECT реализована инструкциями с 11-й по 25-ю. В частности, предложение WHERE с оператором IN реализовано инструкциями 16, 17 и 20. Инструкция 16 помещает значение столбца «two» текущей строки на стек, а инструкция 17 проверяет, что это значение не NULL. Если проверка пройдена, выполнение переходит к инструкции 20, где проверяется, совпадает ли элемент на вершине стека с каким-либо ключом во временной таблице. Остальной код совпадает с тем, что мы уже видели.

Составные инструкции SELECT

SQLite также позволяет объединять две или более инструкции SELECT на равных правах с помощью операторов UNION, UNION ALL, INTERSECT и EXCEPT. Такие составные инструкции SELECT реализуются с использованием временных таблиц. Реализация немного отличается для каждого оператора, но основные принципы одинаковы. В качестве примера рассмотрим оператор EXCEPT.

SELECT two FROM examp
EXCEPT
SELECT four FROM examp2;

Результатом последнего примера должны стать все уникальные значения столбца «two» таблицы examp, за исключением тех, которые встречаются в столбце «four» таблицы examp2. Запрос реализуется следующим кодом:

addr opcode p1 p2 p3 ---- ------------ ----- ----- ----------------------------------- 0 OpenTemp 0 1 1 KeyAsData 0 1 2 Integer 0 0 3 OpenRead 1 3 examp 4 VerifyCookie 0 909 5 Rewind 1 11 6 Column 1 1 7 MakeRecord 1 0 8 String 0 0 9 PutStrKey 0 0 10 Next 1 6 11 Close 1 0 12 Integer 0 0 13 OpenRead 2 5 examp2 14 Rewind 2 20 15 Column 2 1 16 MakeRecord 1 0 17 NotFound 0 19 18 Delete 0 0 19 Next 2 15 20 Close 2 0 21 ColumnName 0 0 four 22 Rewind 0 26 23 Column 0 0 24 Callback 1 0 25 Next 0 23 26 Close 0 0 27 Halt 0 0

Временная таблица, в которой формируется результат, создаётся инструкцией 0. Затем следуют три цикла. Цикл инструкций с 5-й по 10-ю реализует первую инструкцию SELECT. Вторая инструкция SELECT реализована циклом инструкций с 14-й по 19-ю. Наконец, цикл инструкций с 22-й по 25-ю считывает временную таблицу и один раз вызывает функцию обратного вызова для каждой строки результата.

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

Вот что произойдёт. Первая инструкция SELECT сформирует строки результата и сохранит каждую строку в качестве ключа записи временной таблицы. Данные каждой записи временной таблицы никогда не используются, поэтому мы записываем туда пустую строку. Вторая инструкция SELECT также формирует строки, но строки, созданные второй инструкцией SELECT, удаляются из временной таблицы. Поэтому строки должны храниться в ключе файла SQLite, а не в данных: так их проще найти и удалить.

Рассмотрим подробнее, что здесь происходит. Первая инструкция SELECT реализована циклом инструкций с 5-й по 10-ю. Инструкция 5 начинает цикл, перематывая курсор в начало. Инструкция 6 извлекает значение столбца «two» из «examp», а инструкция 7 преобразует его в запись. Инструкция 8 помещает на стек пустую строку. Наконец, инструкция 9 записывает строку во временную таблицу. Но помните: код операции PutStrKey использует верхний элемент стека как данные записи, а следующий элемент — как ключ. Для инструкции INSERT запись, созданная кодом операции MakeRecord, является данными записи, а ключ записи — целое число, созданное кодом операции NewRecno. Но здесь роли поменялись местами: строка, созданная MakeRecord, становится ключом записи, а данные записи — просто пустой строкой.

Вторая инструкция SELECT реализована инструкциями с 14-й по 19-ю. Инструкция 14 начинает цикл, перематывая курсор в начало. Инструкции 15 и 16 создают новую строку результата из столбца «four» таблицы «examp2». Но вместо того, чтобы использовать PutStrKey для записи этой новой строки во временную таблицу, мы вызываем Delete, чтобы удалить её из временной таблицы, если она там есть.

Результат составной инструкции SELECT передаётся функции обратного вызова циклом инструкций с 22-й по 25-ю. В этом цикле нет ничего нового или примечательного, кроме того, что инструкция Column в позиции 23 извлекает столбец из ключа записи, а не из её данных.

Итоги

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

Чтобы узнать больше о работе библиотеки SQLite, обратитесь непосредственно к исходному коду SQLite. Если вы поняли материал этой статьи, изучение исходников не должно вызвать больших затруднений. Тем, кто серьёзно интересуется внутренним устройством SQLite, вероятно, также будет полезно внимательно изучить коды операций VDBE, описанные здесь. Большая часть документации по кодам операций извлекается из комментариев в исходном коде с помощью скрипта, поэтому сведения о различных кодах операций можно также найти непосредственно в исходном файле vdbe.c. Если вы дочитали до этого места, разобраться в остальном вам будет нетрудно.

Если вы обнаружите ошибки в документации или коде, смело исправляйте их и/или связывайтесь с автором по адресу drh@hwaci.com. Исправления ошибок и предложения всегда приветствуются.

SQLite is in the Public Domain.
https://sqlite.org/vdbe.html