SQLite 的虚拟数据库引擎

过时的文档警告： 本文档描述了 SQLite 2.8.0 版中使用的虚拟机。SQLite 3.0 版和 3.1 版中的虚拟机在概念上相似，但现在是基于寄存器而不是基于堆栈的，每个操作码有五个操作数而不是三个，并且具有与下面所示的一组不同的操作码。有关当前的 VDBE 操作码集和 VDBE 如何运行的简要概述，请参阅虚拟机说明文档。这份文件被保留作为历史参考。

如果您想了解 SQLite 库的内部工作原理，您需要首先深入了解虚拟数据库引擎或 VDBE。VDBE 恰好出现在处理流的中间（参见体系结构图），因此它似乎触及了库的大部分部分。即使是不直接与 VDBE 交互的代码部分通常也处于辅助作用。VDBE 确实是 SQLite 的核心。

本文简要介绍了 VDBE 的工作原理，特别是各种 VDBE 指令（记录在此处）如何协同工作以对数据库执行有用的操作。风格是教程，从简单的任务开始，然后努力解决更复杂的问题。在此过程中，我们将访问 SQLite 库中的大多数子模块。完成本教程后，您应该对 SQLite 的工作原理有一个很好的理解，并准备好开始研究实际的源代码。

预赛

VDBE 实现了一个以虚拟机语言运行程序的虚拟计算机。每个程序的目标是查询或更改数据库。为此，VDBE 实现的机器语言专门设计用于搜索、读取和修改数据库。

VDBE 语言的每条指令都包含一个操作码和三个标记为 P1、P2 和 P3 的操作数。操作数 P1 是任意整数。P2 是一个非负整数。P3 是指向数据结构或以零结尾的字符串的指针，可能为空。只有少数 VDBE 指令使用所有三个操作数。许多指令只使用一个或两个操作数。大量指令根本不使用操作数，而是获取它们的数据并将结果存储在执行堆栈中。每条指令的作用及其使用的操作数的详细信息在单独的操作码描述文档中进行了描述。

VDBE 程序从指令 0 开始执行并继续执行后续指令，直到 (1) 遇到致命错误，(2) 执行暂停指令，或 (3) 将程序计数器增加到程序的最后一条指令之后。当 VDBE 完成执行时，关闭所有打开的数据库游标，释放所有内存，并从堆栈中弹出所有内容。所以永远不用担心内存泄漏或未分配的资源。

如果您以前做过任何汇编语言编程或使用过任何类型的抽象机，那么您应该熟悉所有这些细节。因此，让我们直接进入并开始查看一些代码。

将记录插入数据库

我们从一个可以使用只有几条指令长的 VDBE 程序解决的问题开始。假设我们有一个这样创建的 SQL 表：

CREATE TABLE examp(one text, two int);

换句话说，我们有一个名为“examp”的数据库表，它有两列数据，名为“one”和“two”。现在假设我们要向该表中插入一条记录。像这样：

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

我们可以看到 SQLite 用于使用sqlite命令行实用程序实现此 INSERT 的 VDBE 程序。首先在一个新的空数据库上启动sqlite ，然后创建表。接下来，通过输入“.explain”命令，将sqlite的输出格式更改为设计用于 VDBE 程序转储的格式。最后，输入上面显示的 [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

正如您在上面看到的，我们的简单插入语句是用 12 条指令实现的。前 3 条和最后 2 条指令是标准的序言和尾声，因此真正的工作在中间的 7 条指令中完成。没有跳转，所以程序从上到下执行一次。现在让我们详细看看每条指令。

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

交易指令开始交易。当遇到 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，则它是同一整数的字符串表示形式。之后堆栈看起来像这样：

(integer) 0

OpenWrite指令在表“examp”上打开一个新的读/写游标，其句柄为 P1（本例中为 0），其根页为 P2（在此数据库文件中为 3）。游标句柄可以是任何非负整数。但是 VDBE 在数组中分配游标，数组的大小比最大的游标大一。所以为了节省内存，最好使用从零开始并连续向上工作的句柄。这里的 P3（“examp”）是正在打开的表的名称，但它未被使用，只是为了使代码更易于阅读而生成的。该指令从堆栈顶部弹出要使用的数据库编号（0，主数据库），因此堆栈再次为空。

5 NewRecno 0 0

NewRecno指令为游标 P1 指向的表创建一个新的整数记录号。记录号当前未用作表中的键。新的记录号被压入堆栈。之后堆栈看起来像这样：

(integer) new record key

6 字符串 0 0 你好，世界！

String指令将其 P3 操作数压入堆栈。之后堆栈看起来像这样：

(string) "Hello, World!"
(integer) new record key

7 整数 99 0 99

Integer指令将其 P1 操作数 (99) 压入堆栈。之后堆栈看起来像这样：

(integer) 99
(string) "Hello, World!"
(integer) new record key

8 记录 2 0

MakeRecord指令从堆栈中弹出顶部 P1 元素（在本例中为 2 个）并将它们转换为用于将记录存储在数据库文件中的二进制格式。（详见文件格式说明。） MakeRecord 指令生成的新记录被压回堆栈。之后堆栈看起来像这样：

(record) "Hello, World!", 99
(integer) new record key

9 输入键 0 1

PutIntKey指令使用栈顶的 2 个条目向游标 P1 指向的表中写入一个条目。如果新条目不存在或现有条目的数据被覆盖，则会创建一个新条目。记录数据是栈顶条目，键是下一个条目。该指令弹出堆栈两次。因为操作数 P2 为 1，所以行更改计数递增，并且存储 rowid 以供 sqlite_last_insert_rowid() 函数随后返回。如果 P2 为 0，则行更改计数未修改。该指令是插入实际发生的地方。

10 关闭 0 0

Close指令关闭之前作为 P1 打开的游标（0，唯一打开的游标）。如果 P1 当前未打开，则此指令为空操作。

11 提交 0 0

指令Commit使自上次 Transaction 以来对数据库所做的所有修改真正生效。在另一个事务开始之前，不允许进行其他修改。Commit 指令删除日志文件并释放对数据库的写锁。如果仍有游标打开，读锁将继续保持。

12 暂停 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: 前缀。这对你来说没有任何区别，观察者，free()弹出它们以避免内存泄漏。请注意，仅显示字符串值的前 10 个字符，二进制值（例如 MakeRecord 指令的结果）被视为字符串。唯一可以存储在 VDBE 堆栈上的其他数据类型是 NULL，它在没有前缀的情况下显示为简单的“ NULL ”。如果一个整数同时作为整数和字符串被放入栈中，它的前缀是“ si: ”。

简单查询

此时，您应该了解 VDBE 如何写入数据库的基础知识。现在让我们看看它是如何进行查询的。我们将使用以下简单的 SELECT 语句作为示例：

SELECT * FROM examp;

这条SQL语句生成的VDBE程序如下：

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指针。（回调和用户数据最初都作为参数传递给sqlite_exec() API 函数。）VDBE 的工作是为nColumn、azData[]和azColumnName[]提供值。 当然， nColumn是结果中的列数。 azColumnName[]是一个字符串数组，其中每个字符串都是其中一个结果列的名称。 azData[]是一个包含实际数据的字符串数组。

0 列名 0 0 一 1 列名 1 0 二

我们查询的 VDBE 程序中的前两条指令与设置azColumn的值有关。ColumnName指令告诉 VDBE 为azColumnName[] 数组的每个元素填充什么值。对于结果中的每一列，每个查询都以一个 ColumnName 指令开始，并且在查询的后面每个列都有一个匹配的 Column 指令。

2 整数 0 0 3 OpenRead 0 3 示例 4 VerifyCookie 0 81

指令 2 和 3 在要查询的数据库表上打开一个读取游标。这与 INSERT 示例中的 OpenWrite 指令的工作方式相同，只是这次打开游标是为了读取而不是写入。指令 4 验证数据库模式，如 INSERT 示例中所示。

5 倒带 0 10

Rewind指令初始化一个遍历“examp”表的循环。它将光标 P1 倒回到其表中的第一个条目。这是 Column 和 Next 指令所必需的，它们使用游标遍历表。如果表为空，则跳转到 P2（10），这是刚刚通过循环的指令。如果表不为空，则跳转到 6 处的下一条指令，这是循环体的开头。

6 列 0 0 7 列 0 1 8 回调 2 0

指令 6 到 8 构成了循环的主体，该循环将对数据库文件中的每条记录执行一次。地址 6 和 7 处的Column指令分别从第 P1 游标中取出第 P2 列并将其压入堆栈。在此示例中，第一个 Column 指令将“one”列的值压入堆栈，第二个 Column 指令将“two”列的值压入堆栈。地址 8 处的Callback指令调用 callback() 函数。Callback 的 P1 操作数成为nColumn的值。Callback 指令从堆栈中弹出 P1 值并使用它们填充azData[]数组。

9 下一个 0 6

地址 9 处的指令实现了循环的分支部分。它与地址 5 处的 Rewind 一起构成了循环逻辑。这是一个你应该密切关注的关键概念。Next指令将光标 P1 前进到下一条记录。如果游标前进成功，则立即跳转到P2（6，循环体的开头）。如果光标在末尾，则跳转到下一条指令，结束循环。

10 关闭 0 0 11 停止 0 0

程序末尾的 Close 指令关闭指向表“examp”的游标。在这里调用 Close 并不是真正必要的，因为当程序暂停时，所有游标都会被 VDBE 自动关闭。但是我们需要 Rewind 跳转到的指令，所以我们不妨继续并让该指令做一些有用的事情。Halt 指令结束 VDBE 程序。

请注意，此 SELECT 查询的程序不包含 INSERT 示例中使用的事务和提交指令。因为 SELECT 是不改变数据库的读取操作，所以它不需要事务。

稍微复杂一点的查询

The key points of the previous example were the use of the Callback instruction to invoke the callback function, and the use of the Next instruction to implement a loop over all records of the database file. This example attempts to drive home those ideas by demonstrating a slightly more complex query that involves more columns of output, some of which are computed values, and a WHERE clause that limits which records actually make it to the callback function. Consider this query:

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

This query is perhaps a bit contrived, but it does serve to illustrate our points. The result will have three column with names "one", "two", and "both". The first two columns are direct copies of the two columns in the table and the third result column is a string formed by concatenating the first and second columns of the table. Finally, the WHERE clause says that we will only chose rows for the results where the "one" column begins with an "H". Here is what the VDBE program looks like for this query:

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

Except for the WHERE clause, the structure of the program for this example is very much like the prior example, just with an extra column. There are now 3 columns, instead of 2 as before, and there are three ColumnName instructions. A cursor is opened using the OpenRead instruction, just like in the prior example. The Rewind instruction at address 6 and the Next at address 17 form a loop over all records of the table. The Close instruction at the end is there to give the Rewind instruction something to jump to when it is done. All of this is just like in the first query demonstration.

The Callback instruction in this example has to generate data for three result columns instead of two, but is otherwise the same as in the first query. When the Callback instruction is invoked, the left-most column of the result should be the lowest in the stack and the right-most result column should be the top of the stack. We can see the stack being set up this way at addresses 11 through 15. The Column instructions at 11 and 12 push the values for the first two columns in the result. The two Column instructions at 13 and 14 pull in the values needed to compute the third result column and the Concat instruction at 15 joins them together into a single entry on the stack.

The only thing that is really new about the current example is the WHERE clause which is implemented by instructions at addresses 7 through 10. Instructions at address 7 and 8 push onto the stack the value of the "one" column from the table and the literal string "H%". The Function instruction at address 9 pops these two values from the stack and pushes the result of the LIKE() function back onto the stack. The IfNot instruction pops the top stack value and causes an immediate jump forward to the Next instruction if the top value was false (not not like the literal string "H%"). Taking this jump effectively skips the callback, which is the whole point of the WHERE clause. If the result of the comparison is true, the jump is not taken and control falls through to the Callback instruction below.

Notice how the LIKE operator is implemented. It is a user-defined function in SQLite, so the address of its function definition is specified in P3. The operand P1 is the number of function arguments for it to take from the stack. In this case the LIKE() function takes 2 arguments. The arguments are taken off the stack in reverse order (right-to-left), so the pattern to match is the top stack element, and the next element is the data to compare. The return value is pushed onto the stack.

A Template For SELECT Programs

The first two query examples illustrate a kind of template that every SELECT program will follow. Basically, we have:

Initialize the azColumnName[] array for the callback.
Open a cursor into the table to be queried.
For each record in the table, do:
1. If the WHERE clause evaluates to FALSE, then skip the steps that follow and continue to the next record.
2. Compute all columns for the current row of the result.
3. Invoke the callback function for the current row of the result.
Close the cursor.

This template will be expanded considerably as we consider additional complications such as joins, compound selects, using indices to speed the search, sorting, and aggregate functions with and without GROUP BY and HAVING clauses. But the same basic ideas will continue to apply.

UPDATE And DELETE Statements

The UPDATE and DELETE statements are coded using a template that is very similar to the SELECT statement template. The main difference, of course, is that the end action is to modify the database rather than invoke a callback function. Because it modifies the database it will also use transactions. Let's begin by looking at a DELETE statement:

DELETE FROM examp WHERE two<50;

This DELETE statement will remove every record from the "examp" table where the "two" column is less than 50. The code generated to do this is as follows:

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

Here is what the program must do. First it has to locate all of the records in the table "examp" that are to be deleted. This is done using a loop very much like the loop used in the SELECT examples above. Once all records have been located, then we can go back through and delete them one by one. Note that we cannot delete each record as soon as we find it. We have to locate all records first, then go back and delete them. This is because the SQLite database backend might change the scan order after a delete operation. And if the scan order changes in the middle of the scan, some records might be visited more than once and other records might not be visited at all.

So the implementation of DELETE is really in two loops. The first loop (instructions 5 through 11) locates the records that are to be deleted and saves their keys onto a temporary list, and the second loop (instructions 16 through 19) uses the key list to delete the records one by one.

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

Instructions 0 though 4 are as in the INSERT example. They start transactions for the main and temporary databases, verify the database schema for the main database, and open a read cursor on the table "examp". Notice that the cursor is opened for reading, not writing. At this stage of the program we are only going to be scanning the table, not changing it. We will reopen the same table for writing later, at instruction 15.

5 Rewind 0 12

As in the SELECT example, the Rewind instruction rewinds the cursor to the beginning of the table, readying it for use in the loop body.

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

The WHERE clause is implemented by instructions 6 through 8. The job of the where clause is to skip the ListWrite if the WHERE condition is false. To this end, it jumps ahead to the Next instruction if the "two" column (extracted by the Column instruction) is greater than or equal to 50.

As before, the Column instruction uses cursor P1 and pushes the data record in column P2 (1, column "two") onto the stack. The Integer instruction pushes the value 50 onto the top of the stack. After these two instructions the stack looks like:

(integer) 50
(record) current record for column "two"

The Ge operator compares the top two elements on the stack, pops them, and then branches based on the result of the comparison. If the second element is >= the top element, then jump to address P2 (the Next instruction at the end of the loop). Because P1 is true, if either operand is NULL (and thus the result is NULL) then take the jump. If we don't jump, just advance to the next instruction.

9 Recno 0 0 10 ListWrite 0 0

The Recno instruction pushes onto the stack an integer which is the first 4 bytes of the key to the current entry in a sequential scan of the table pointed to by cursor P1. The ListWrite instruction writes the integer on the top of the stack into a temporary storage list and pops the top element. This is the important work of this loop, to store the keys of the records to be deleted so we can delete them in the second loop. After this ListWrite instruction the stack is empty again.

11 Next 0 6 12 Close 0 0

The Next instruction increments the cursor to point to the next element in the table pointed to by cursor P0, and if it was successful branches to P2 (6, the beginning of the loop body). The Close instruction closes cursor P1. It doesn't affect the temporary storage list because it isn't associated with cursor P1; it is instead a global working list (which can be saved with ListPush).

13 ListRewind 0 0

The ListRewind instruction rewinds the temporary storage list to the beginning. This prepares it for use in the second loop.

14 Integer 0 0 15 OpenWrite 0 3

As in the INSERT example, we push the database number P1 (0, the main database) onto the stack and use OpenWrite to open the cursor P1 on table P2 (base page 3, "examp") for modification.

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

This loop does the actual deleting. It is organized differently from the one in the UPDATE example. The ListRead instruction plays the role that the Next did in the INSERT loop, but because it jumps to P2 on failure, and Next jumps on success, we put it at the start of the loop instead of the end. This means that we have to put a Goto at the end of the loop to jump back to the loop test at the beginning. So this loop has the form of a C while(){...} loop, while the loop in the INSERT example had the form of a do{...}while() loop. The Delete instruction fills the role that the callback function did in the preceding examples.

The ListRead instruction reads an element from the temporary storage list and pushes it onto the stack. If this was successful, it continues to the next instruction. If this fails because the list is empty, it branches to P2, which is the instruction just after the loop. Afterwards the stack looks like:

(integer) key for current record

Notice the similarity between the ListRead and Next instructions. Both operations work according to this rule:

Push the next "thing" onto the stack and fall through OR jump to P2, depending on whether or not there is a next "thing" to push.

One difference between Next and ListRead is their idea of a "thing". The "things" for the Next instruction are records in a database file. "Things" for ListRead are integer keys in a list. Another difference is whether to jump or fall through if there is no next "thing". In this case, Next falls through, and ListRead jumps. Later on, we will see other looping instructions (NextIdx and SortNext) that operate using the same principle.

The NotExists instruction pops the top stack element and uses it as an integer key. If a record with that key does not exist in table P1, then jump to P2. If a record does exist, then fall through to the next instruction. In this case P2 takes us to the Goto at the end of the loop, which jumps back to the ListRead at the beginning. This could have been coded to have P2 be 16, the ListRead at the start of the loop, but the SQLite parser which generated this code didn't make that optimization.

The Delete does the work of this loop; it pops an integer key off the stack (placed there by the preceding ListRead) and deletes the record of cursor P1 that has that key. Because P2 is true, the row change counter is incremented.

The Goto jumps back to the beginning of the loop. This is the end of the loop.

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

This block of instruction cleans up the VDBE program. Three of these instructions aren't really required, but are generated by the SQLite parser from its code templates, which are designed to handle more complicated cases.

The ListReset instruction empties the temporary storage list. This list is emptied automatically when the VDBE program terminates, so it isn't necessary in this case. The Close instruction closes the cursor P1. Again, this is done by the VDBE engine when it is finished running this program. The Commit ends the current transaction successfully, and causes all changes that occurred in this transaction to be saved to the database. The final Halt is also unnecessary, since it is added to every VDBE program when it is prepared to run.

UPDATE statements work very much like DELETE statements except that instead of deleting the record they replace it with a new one. Consider this example:

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

Instead of deleting records where the "two" column is less than 50, this statement just puts the "one" column in parentheses The VDBE program to implement this statement follows:

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

This program is essentially the same as the DELETE program except that the body of the second loop has been replace by a sequence of instructions (at addresses 17 through 26) that update the record rather than delete it. Most of this instruction sequence should already be familiar to you, but there are a couple of minor twists so we will go over it briefly. Also note that the order of some of the instructions before and after the 2nd loop has changed. This is just the way the SQLite parser chose to output the code using a different template.

As we enter the interior of the second loop (at instruction 17) the stack contains a single integer which is the key of the record we want to modify. We are going to need to use this key twice: once to fetch the old value of the record and a second time to write back the revised record. So the first instruction is a Dup to make a duplicate of the key on the top of the stack. The Dup instruction will duplicate any element of the stack, not just the top element. You specify which element to duplication using the P1 operand. When P1 is 0, the top of the stack is duplicated. When P1 is 1, the next element down on the stack duplication. And so forth.

After duplicating the key, the next instruction, NotExists, pops the stack once and uses the value popped as a key to check the existence of a record in the database file. If there is no record for this key, it jumps back to the ListRead to get another key.

Instructions 19 through 25 construct a new database record that will be used to replace the existing record. This is the same kind of code that we saw in the description of INSERT and will not be described further. After instruction 25 executes, the stack looks like this:

(record) new data record
(integer) key

The PutIntKey instruction (also described during the discussion about INSERT) writes an entry into the database file whose data is the top of the stack and whose key is the next on the stack, and then pops the stack twice. The PutIntKey instruction will overwrite the data of an existing record with the same key, which is what we want here. Overwriting was not an issue with INSERT because with INSERT the key was generated by the NewRecno instruction which is guaranteed to provide a key that has not been used before.

CREATE and DROP

Using CREATE or DROP to create or destroy a table or index is really the same as doing an INSERT or DELETE from the special "sqlite_master" table, at least from the point of view of the VDBE. The sqlite_master table is a special table that is automatically created for every SQLite database. It looks like this:

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
)

Every table (except the "sqlite_master" table itself) and every named index in an SQLite database has an entry in the sqlite_master table. You can query this table using a SELECT statement just like any other table. But you are not allowed to directly change the table using UPDATE, INSERT, or DELETE. Changes to sqlite_master have to occur using the CREATE and DROP commands because SQLite also has to update some of its internal data structures when tables and indices are added or destroyed.

But from the point of view of the VDBE, a CREATE works pretty much like an INSERT and a DROP works like a DELETE. When the SQLite library opens to an existing database, the first thing it does is a SELECT to read the "sql" columns from all entries of the sqlite_master table. The "sql" column contains the complete SQL text of the CREATE statement that originally generated the index or table. This text is fed back into the SQLite parser and used to reconstruct the internal data structures describing the index or table.

Using Indexes To Speed Searching

In the example queries above, every row of the table being queried must be loaded off of the disk and examined, even if only a small percentage of the rows end up in the result. This can take a long time on a big table. To speed things up, SQLite can use an index.

An SQLite file associates a key with some data. For an SQLite table, the database file is set up so that the key is an integer and the data is the information for one row of the table. Indices in SQLite reverse this arrangement. The index key is (some of) the information being stored and the index data is an integer. To access a table row that has some particular content, we first look up the content in the index table to find its integer index, then we use that integer to look up the complete record in the table.

Note that SQLite uses b-trees, which are a sorted data structure, so indices can be used when the WHERE clause of the SELECT statement contains tests for equality or inequality. Queries like the following can use an index if it is available:

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

If there exists an index that maps the "two" column of the "examp" table into integers, then SQLite will use that index to find the integer keys of all rows in examp that have a value of 50 for column two, or all rows that are less than 50, etc. But the following queries cannot use the index:

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

Note that the SQLite parser will not always generate code to use an index, even if it is possible to do so. The following queries will not currently use the index:

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

To understand better how indices work, lets first look at how they are created. Let's go ahead and put an index on the two column of the examp table. We have:

CREATE INDEX examp_idx1 ON examp(two);

The VDBE code generated by the above statement looks like the following:

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

Remember that every table (except sqlite_master) and every named index has an entry in the sqlite_master table. Since we are creating a new index, we have to add a new entry to sqlite_master. This is handled by instructions 3 through 15. Adding an entry to sqlite_master works just like any other INSERT statement so we will not say any more about it here. In this example, we want to focus on populating the new index with valid data, which happens on instructions 16 through 23.

16 Integer 0 0 17 OpenRead 2 3 examp

The first thing that happens is that we open the table being indexed for reading. In order to construct an index for a table, we have to know what is in that table. The index has already been opened for writing using cursor 0 by instructions 3 and 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

Instructions 18 through 23 implement a loop over every row of the table being indexed. For each table row, we first extract the integer key for that row using Recno in instruction 19, then get the value of the "two" column using Column in instruction 20. The MakeIdxKey instruction at 21 converts data from the "two" column (which is on the top of the stack) into a valid index key. For an index on a single column, this is basically a no-op. But if the P1 operand to MakeIdxKey had been greater than one multiple entries would have been popped from the stack and converted into a single index key. The IdxPut instruction at 22 is what actually creates the index entry. IdxPut pops two elements from the stack. The top of the stack is used as a key to fetch an entry from the index table. Then the integer which was second on stack is added to the set of integers for that index and the new record is written back to the database file. Note that the same index entry can store multiple integers if there are two or more table entries with the same value for the two column.

Now let's look at how this index will be used. Consider the following query:

SELECT * FROM examp WHERE two==50;

SQLite generates the following VDBE code to handle this query:

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

The SELECT begins in a familiar fashion. First the column names are initialized and the table being queried is opened. Things become different beginning with instructions 5 and 6 where the index file is also opened. Instructions 7 and 8 make a key with the value of 50. The MemStore instruction at 9 stores the index key in VDBE memory location 0. The VDBE memory is used to avoid having to fetch a value from deep in the stack, which can be done, but makes the program harder to generate. The following instruction MoveTo at address 10 pops the key off the stack and moves the index cursor to the first row of the index with that key. This initializes the cursor for use in the following loop.

Instructions 11 through 18 implement a loop over all index records with the key that was fetched by instruction 8. All of the index records with this key will be contiguous in the index table, so we walk through them and fetch the corresponding table key from the index. This table key is then used to move the cursor to that row in the table. The rest of the loop is the same as the loop for the non-indexed SELECT query.

The loop begins with the MemLoad instruction at 11 which pushes a copy of the index key back onto the stack. The instruction IdxGT at 12 compares the key to the key in the current index record pointed to by cursor P1. If the index key at the current cursor location is greater than the index we are looking for, then jump out of the loop.

The instruction IdxRecno at 13 pushes onto the stack the table record number from the index. The following MoveTo pops it and moves the table cursor to that row. The next 3 instructions select the column data the same way as in the non- indexed case. The Column instructions fetch the column data and the callback function is invoked. The final Next instruction advances the index cursor, not the table cursor, to the next row, and then branches back to the start of the loop if there are any index records left.

Since the index is used to look up values in the table, it is important that the index and table be kept consistent. Now that there is an index on the examp table, we will have to update that index whenever data is inserted, deleted, or changed in the examp table. Remember the first example above where we were able to insert a new row into the "examp" table using 12 VDBE instructions. Now that this table is indexed, 19 instructions are required. The SQL statement is this:

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

And the generated code looks like this:

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

At this point, you should understand the VDBE well enough to figure out on your own how the above program works. So we will not discuss it further in this text.

Joins

In a join, two or more tables are combined to generate a single result. The result table consists of every possible combination of rows from the tables being joined. The easiest and most natural way to implement this is with nested loops.

Recall the query template discussed above where there was a single loop that searched through every record of the table. In a join we have basically the same thing except that there are nested loops. For example, to join two tables, the query template might look something like this:

Initialize the azColumnName[] array for the callback.
Open two cursors, one to each of the two tables being queried.
For each record in the first table, do:
1. For each record in the second table do:
  1. If the WHERE clause evaluates to FALSE, then skip the steps that follow and continue to the next record.
  2. Compute all columns for the current row of the result.
  3. Invoke the callback function for the current row of the result.
Close both cursors.

This template will work, but it is likely to be slow since we are now dealing with an O(N²) loop. But it often works out that the WHERE clause can be factored into terms and that one or more of those terms will involve only columns in the first table. When this happens, we can factor part of the WHERE clause test out of the inner loop and gain a lot of efficiency. So a better template would be something like this:

Initialize the azColumnName[] array for the callback.
Open two cursors, one to each of the two tables being queried.
For each record in the first table, do:
1. Evaluate terms of the WHERE clause that only involve columns from the first table. If any term is false (meaning that the whole WHERE clause must be false) then skip the rest of this loop and continue to the next record.
2. For each record in the second table do:
  1. If the WHERE clause evaluates to FALSE, then skip the steps that follow and continue to the next record.
  2. Compute all columns for the current row of the result.
  3. Invoke the callback function for the current row of the result.
Close both cursors.

Additional speed-up can occur if an index can be used to speed the search of either or the two loops.

SQLite always constructs the loops in the same order as the tables appear in the FROM clause of the SELECT statement. The left-most table becomes the outer loop and the right-most table becomes the inner loop. It is possible, in theory, to reorder the loops in some circumstances to speed the evaluation of the join. But SQLite does not attempt this optimization.

You can see how SQLite constructs nested loops in the following example:

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

The outer loop over table examp is implement by instructions 7 through 23. The inner loop is instructions 13 through 22. Notice that the "two<50" term of the WHERE expression involves only columns from the first table and can be factored out of the inner loop. SQLite does this and implements the "two<50" test in instructions 10 through 12. The "four==two" test is implement by instructions 14 through 16 in the inner loop.

SQLite does not impose any arbitrary limits on the tables in a join. It also allows a table to be joined with itself.

The ORDER BY clause

For historical reasons, and for efficiency, all sorting is currently done in memory.

SQLite implements the ORDER BY clause using a special set of instructions to control an object called a sorter. In the inner-most loop of the query, where there would normally be a Callback instruction, instead a record is constructed that contains both callback parameters and a key. This record is added to the sorter (in a linked list). After the query loop finishes, the list of records is sorted and this list is walked. For each record on the list, the callback is invoked. Finally, the sorter is closed and memory is deallocated.

We can see the process in action in the following query:

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

There is only one sorter object, so there are no instructions to open or close it. It is opened automatically when needed, and it is closed when the VDBE program halts.

The query loop is built from instructions 5 through 13. Instructions 6 through 8 build a record that contains the azData[] values for a single invocation of the callback. A sort key is generated by instructions 9 through 11. Instruction 12 combines the invocation record and the sort key into a single entry and puts that entry on the sort list.

The P3 argument of instruction 11 is of particular interest. The sort key is formed by prepending one character from P3 to each string and concatenating all the strings. The sort comparison function will look at this character to determine whether the sort order is ascending or descending, and whether to sort as a string or number. In this example, the first column should be sorted as a string in descending order so its prefix is "D" and the second column should sorted numerically in ascending order so its prefix is "+". Ascending string sorting uses "A", and descending numeric sorting uses "-".

After the query loop ends, the table being queried is closed at instruction 14. This is done early in order to allow other processes or threads to access that table, if desired. The list of records that was built up inside the query loop is sorted by the instruction at 15. Instructions 16 through 18 walk through the record list (which is now in sorted order) and invoke the callback once for each record. Finally, the sorter is closed at instruction 19.

Aggregate Functions And The GROUP BY and HAVING Clauses

To compute aggregate functions, the VDBE implements a special data structure and instructions for controlling that data structure. The data structure is an unordered set of buckets, where each bucket has a key and one or more memory locations. Within the query loop, the GROUP BY clause is used to construct a key and the bucket with that key is brought into focus. A new bucket is created with the key if one did not previously exist. Once the bucket is in focus, the memory locations of the bucket are used to accumulate the values of the various aggregate functions. After the query loop terminates, each bucket is visited once to generate a single row of the results.

An example will help to clarify this concept. Consider the following query:

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

The VDBE code generated for this query is as follows:

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

The first instruction of interest is the AggReset at 2. The AggReset instruction initializes the set of buckets to be the empty set and specifies the number of memory slots available in each bucket as P2. In this example, each bucket will hold 3 memory slots. It is not obvious, but if you look closely at the rest of the program you can figure out what each of these slots is intended for.

Memory Slot Intended Use Of This Memory Slot

0 The "three" column -- the key to the bucket

1 The minimum "three+four" value

2 The sum of all "four" values. This is used to compute "avg(four)".

Memory Slot	Intended Use Of This Memory Slot
0	The "three" column -- the key to the bucket
1	The minimum "three+four" value
2	The sum of all "four" values. This is used to compute "avg(four)".

The query loop is implemented by instructions 8 through 22. The aggregate key specified by the GROUP BY clause is computed by instructions 9 and 10. Instruction 11 causes the appropriate bucket to come into focus. If a bucket with the given key does not already exists, a new bucket is created and control falls through to instructions 12 and 13 which initialize the bucket. If the bucket does already exist, then a jump is made to instruction 14. The values of aggregate functions are updated by the instructions between 11 and 21. Instructions 14 through 18 update memory slot 1 to hold the next value "min(three+four)". Then the sum of the "four" column is updated by instructions 19 through 21.

After the query loop is finished, the table "examp2" is closed at instruction 23 so that its lock will be released and it can be used by other threads or processes. The next step is to loop over all aggregate buckets and output one row of the result for each bucket. This is done by the loop at instructions 24 through 30. The AggNext instruction at 24 brings the next bucket into focus, or jumps to the end of the loop if all buckets have been examined already. The 3 columns of the result are fetched from the aggregator bucket in order at instructions 25 through 27. Finally, the callback is invoked at instruction 29.

In summary then, any query with aggregate functions is implemented by two loops. The first loop scans the input table and computes aggregate information into buckets and the second loop scans through all the buckets to compute the final result.

The realization that an aggregate query is really two consecutive loops makes it much easier to understand the difference between a WHERE clause and a HAVING clause in SQL query statement. The WHERE clause is a restriction on the first loop and the HAVING clause is a restriction on the second loop. You can see this by adding both a WHERE and a HAVING clause to our example query:

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

The code generated in this last example is the same as the previous except for the addition of two conditional jumps used to implement the extra WHERE and HAVING clauses. The WHERE clause is implemented by instructions 9 through 11 in the query loop. The HAVING clause is implemented by instruction 28 through 30 in the output loop.

Using SELECT Statements As Terms In An Expression

The very name "Structured Query Language" tells us that SQL should support nested queries. And, in fact, two different kinds of nesting are supported. Any SELECT statement that returns a single-row, single-column result can be used as a term in an expression of another SELECT statement. And, a SELECT statement that returns a single-column, multi-row result can be used as the right-hand operand of the IN and NOT IN operators. We will begin this section with an example of the first kind of nesting, where a single-row, single-column SELECT is used as a term in an expression of another SELECT. Here is our example:

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

The way SQLite deals with this is to first run the inner SELECT (the one against examp2) and store its result in a private memory cell. SQLite then substitutes the value of this private memory cell for the inner SELECT when it evaluates the outer SELECT. The code looks like this:

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

The private memory cell is initialized to NULL by the first two instructions. Instructions 2 through 13 implement the inner SELECT statement against the examp2 table. Notice that instead of sending the result to a callback or storing the result on a sorter, the result of the query is pushed into the memory cell by instruction 10 and the loop is abandoned by the jump at instruction 11. The jump at instruction at 11 is vestigial and never executes.

The outer SELECT is implemented by instructions 14 through 25. In particular, the WHERE clause that contains the nested select is implemented by instructions 19 through 21. You can see that the result of the inner select is loaded onto the stack by instruction 20 and used by the conditional jump at 21.

When the result of a sub-select is a scalar, a single private memory cell can be used, as shown in the previous example. But when the result of a sub-select is a vector, such as when the sub-select is the right-hand operand of IN or NOT IN, a different approach is needed. In this case, the result of the sub-select is stored in a transient table and the contents of that table are tested using the Found or NotFound operators. Consider this example:

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

The code generated to implement this last query is as follows:

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

The transient table in which the results of the inner SELECT are stored is created by the OpenTemp instruction at 0. This opcode is used for tables that exist for the duration of a single SQL statement only. The transient cursor is always opened read/write even if the main database is read-only. The transient table is deleted automatically when the cursor is closed. The P2 value of 1 means the cursor points to a BTree index, which has no data but can have an arbitrary key.

The inner SELECT statement is implemented by instructions 1 through 10. All this code does is make an entry in the temporary table for each row of the examp2 table with a non-NULL value for the "three" column. The key for each temporary table entry is the "three" column of examp2 and the data is an empty string since it is never used.

The outer SELECT is implemented by instructions 11 through 25. In particular, the WHERE clause containing the IN operator is implemented by instructions at 16, 17, and 20. Instruction 16 pushes the value of the "two" column for the current row onto the stack and instruction 17 checks to see that it is non-NULL. If this is successful, execution jumps to 20, where it tests to see if top of the stack matches any key in the temporary table. The rest of the code is the same as what has been shown before.

Compound SELECT Statements

SQLite also allows two or more SELECT statements to be joined as peers using operators UNION, UNION ALL, INTERSECT, and EXCEPT. These compound select statements are implemented using transient tables. The implementation is slightly different for each operator, but the basic ideas are the same. For an example we will use the EXCEPT operator.

SELECT two FROM examp
EXCEPT
SELECT four FROM examp2;

The result of this last example should be every unique value of the "two" column in the examp table, except any value that is in the "four" column of examp2 is removed. The code to implement this query is as follows:

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 删除 0 0 19 下一个 2 15 20 关闭 2 0 21 ColumnName 0 0 四 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”中提取“two”列的值，指令 7 将其转换为一行。指令 8 将空字符串压入堆栈。最后，指令 9 将行写入临时表。但请记住，PutStrKey 操作码使用堆栈顶部作为记录数据，并将堆栈中的下一个用作键。对于 INSERT 语句，由 MakeRecord 操作码生成的行是记录数据，记录键是由 NewRecno 操作码创建的整数。但是这里角色颠倒了，MakeRecord 创建的行是记录键，记录数据只是一个空字符串。

第二个 SELECT 由指令 14 到 19 实现。指令 14 通过倒回其游标来初始化循环。指令 15 和 16 从表“examp2”的“四”列创建了一个新的结果行。但是我们没有使用 PutStrKey 将这个新行写入临时表，而是调用 Delete 将其从临时表中删除，如果它存在。

复合选择的结果通过指令 22 到 25 处的循环发送到回调例程。除了在 23 处的 Column 指令将从记录中提取列之外，这个循环没有什么新的或值得注意的密钥而不是记录数据。

概括

本文回顾了 SQLite 的 VDBE 用于实现 SQL 语句的所有主要技术。尚未显示的是，这些技术中的大多数可以组合使用来为适当复杂的查询语句生成代码。例如，我们展示了如何在简单查询中完成排序，我们展示了如何实现复合查询。但是我们没有给出复合查询中排序的例子。这是因为对复合查询进行排序不会引入任何新概念：它只是在同一个 VDBE 程序中结合了以前的两个想法（排序和复合）。

有关 SQLite 库如何运行的更多信息，请读者直接查看 SQLite 源代码。如果您理解本文中的材料，那么您应该不会有太大的困难来理解这些来源。认真研究 SQLite 内部结构的学生可能还想仔细研究此处记录的 VDBE 操作码。大多数操作码文档是使用脚本从源代码中的注释中提取的，因此您还可以直接从vdbe.c源文件中获取有关各种操作码的信息。如果你已经成功阅读到这里，你应该不难理解其余部分。

如果您在文档或代码中发现错误，请随时修复它们和/或通过 [email protected]联系作者。随时欢迎您的错误修复或建议。