Виртуальный движок базы данных 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 внутри, вам необходимо начать с глубокого понимания виртуального движка базы данных или VDBE. VDBE находится прямо посередине потока обработки (см. диаграмму архитектуры), и поэтому он, кажется, затрагивает большинство частей библиотеки. Даже части кода, которые не взаимодействуют напрямую с VDBE, обычно выполняют вспомогательную функцию. VDBE действительно является сердцем SQLite.

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

Предварительные замечания

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

Каждая инструкция языка VDBE содержит код операции и три операнда, обозначенные P1, P2 и P3. Операнд P1 — произвольное целое число. P2 — неотрицательное целое число. P3 — указатель на структуру данных или строку с нулевым окончанием, возможно, нулевое значение. Только несколько инструкций 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], показанный выше, но перед [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

Как вы можете видеть выше, наша простая инструкция INSERT реализована в 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 в стек. После этого стек выглядит так:

(строка) «Привет, мир!»

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

7 Integer 99 0 99

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

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

(строка) «Привет, мир!»

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

8 MakeRecord 2 0

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

(запись) «Привет, мир!», 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 заставляет все изменения в базе данных, внесенные с момента последней транзакции, вступить в силу. Никакие дополнительные изменения не допускаются до тех пор, пока не начнется новая транзакция. Инструкция 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 берут P2-й столбец из P1-го курсора и помещают его на стек. В этом примере первая инструкция Column помещает значение для столбца "one" на стек, а вторая инструкция Column помещает значение для столбца "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 принимает значение FALSE, то пропустить следующие шаги и перейти к следующей записи.
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 ложно. С этой целью он переходит к следующей инструкции (Next), если значение столбца «два» (извлеченного инструкцией Column) больше или равно 50.

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

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

(запись) текущая запись для столбца «два»

Оператор Ge сравнивает две верхние элементы в стеке, извлекает их и затем переходит по адресу P2 (следующая инструкция в конце цикла) в зависимости от результата сравнения. Если второй элемент больше или равен верхнему элементу, происходит переход по адресу P2. Если один из операндов равен 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 играет ту же роль, что и Next в цикле INSERT, но так как при неудачном выполнении происходит переход к P2, а Next — при успешном, мы поместили её в начале цикла, а не в конце. Это означает, что нам нужно добавить Goto в конце цикла, чтобы перейти обратно к тесту цикла в начале. Таким образом, этот цикл имеет форму цикла C while(){…}, тогда как цикл в примере INSERT имел форму цикла do{...}while(). Инструкция Delete выполняет роль функции обратного вызова в предыдущих примерах.

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

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

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

Поместить следующий "объект" в стек и продолжить выполнение ИЛИ перейти к P2, в зависимости от того, существует ли следующий "объект", который нужно поместить.

Различие между Next и ListRead заключается в их представлении "объекта". "Объекты" для инструкции Next — это записи в файле базы данных. "Объекты" для ListRead — это целочисленные ключи в списке. Другое отличие — то, переходить ли к P2 или продолжить выполнение, если следующего "объекта" нет. В данном случае Next продолжит выполнение, а ListRead переходит к P2.

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

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

Инструкция 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;

Вместо удаления записей, где столбец «два» меньше 50, эта операция просто помещает столбец «один» в скобки. Программа 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 стек выглядит так:

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

(целое число) ключ

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

CREATE и DROP

Использование CREATE или DROP для создания или удаления таблицы или индекса по сути равносильно выполнению INSERT или DELETE из специальной таблицы «sqlite_master», по крайней мере, с точки зрения VDBE. Таблица 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» содержит полный текст 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);

Если существует индекс, который отображает столбец «два» таблицы «examp» в целые числа, то SQLite будет использовать этот индекс для поиска целочисленных ключей всех строк в таблице examp, у которых значение столбца «два» равно 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;

Чтобы лучше понять, как работают индексы, давайте сначала посмотрим, как они создаются. Давайте создадим индекс для двух столбцов таблицы 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. Инструкция MakeIdxKey в 21-й инструкции преобразует данные из столбца "два" (который находится вверху стека) в действительный ключ индекса. Для индекса по одному столбцу это в основном пустая операция. Но если операнд P1 в MakeIdxKey был больше единицы, несколько элементов извлекались бы из стека и преобразовывались в один ключ индекса. Инструкция IdxPut в 22-й инструкции фактически создаёт запись индекса. IdxPut извлекает два элемента из стека. Верхний элемент стека используется в качестве ключа для извлечения записи из таблицы индексов. Затем целое число, которое было вторым в стеке, добавляется к набору целых чисел для этого индекса, и новая запись записывается обратно в файл базы данных. Обратите внимание, что одна и та же запись индекса может хранить несколько целых чисел, если существует две или более записей таблицы с одинаковым значением для столбца "два".

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

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 извлекает его и перемещает курсор таблицы к этой строке. Следующие 3 инструкции выбирают данные столбца таким же образом, как и в случае без индекса. Инструкции 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-ю. Обратите внимание, что термин "two<50" выражения WHERE включает только столбцы из первой таблицы и может быть вынесен из внутреннего цикла. 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. В этом примере каждое ведро будет содержать 3 слота памяти. Не очевидно, но при внимательном рассмотрении остальной части программы можно понять, для чего предназначен каждый из этих слотов.

Номер слота памяти Предполагаемое использование слота памяти

0 Столбец «три» — ключ ведра

1 Минимальное значение «три+четыре»

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

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

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

После завершения цикла запроса таблица «examp2» закрывается в инструкции 23, чтобы её блокировка была освобождена, и она могла быть использована другими потоками или процессами. Следующим шагом является перебор всех агрегатных ведер и вывод одной строки результата для каждого ведра. Это выполняется циклом с инструкциями 24 по 30. Инструкция AggNext в позиции 24 переводит следующее ведро в фокус или переходит к концу цикла, если все ведра уже были обработаны. 3 столбца результата извлекаются из ведра агрегатора в порядке с инструкциями 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) и сохраняя его результат в частной ячейке памяти. Затем SQLite подставляет значение этой частной ячейки памяти вместо внутреннего оператора SELECT при вычислении внешнего оператора 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, содержащее вложенный select, реализуется инструкциями с 19 по 21. Вы можете видеть, что результат внутреннего select загружается на стек инструкцией 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, означает, что курсор указывает на индекс B-дерева, который не содержит данных, но может иметь произвольный ключ.

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

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

Составные операторы SELECT

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

SELECT two FROM examp
EXCEPT
SELECT four FROM examp2;

Результатом последнего примера должно быть каждое уникальное значение столбца «два» в таблице examp, за исключением любого значения, присутствующего в столбце «четыре» таблицы 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 извлекает значение столбца «два» из «examp», а инструкция 7 преобразует его в строку. Инструкция 8 помещает пустую строку в стек. Наконец, инструкция 9 записывает строку во временную таблицу. Но помните, что оператор PutStrKey использует вершину стека как данные записи и следующий элемент стека как ключ. Для оператора INSERT строка, сгенерированная оператором MakeRecord, является данными записи, а ключ записи — целое число, созданное оператором NewRecno. Но здесь роли меняются, и строка, созданная MakeRecord, является ключом записи, а данные записи — просто пустая строка.

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

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

Заключение

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

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

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

Эта страница была в последний раз изменена 08 января 2022 г. 05:02:57 UTC

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