第9章 SQLite内核

本章是SQLite各主要子系统的一个概览。它的灵感来自一次会议上Richard Hipp对SQLite所做的介绍。即使你没有看过SQLite的源代码,你也会发现这些内容是如此的有趣。即使SQLite还在发展,但本章所介绍的概念一时不会改变。

现在,你应该已经熟悉SQLite的主要组件了。第1章有一个概述,第5章介绍了B-tree和pager,这些概念本章就不再介绍了。本章会从虚拟机入手,它是SQLite的心脏;然后是存储层;最后是编译器,它可能是系统中最复杂的部分。

虚拟数据库引擎(VDBE)

VDBE是SQLite的核心,它的上层模块和下层模块本质上都是为它服务的,它的实现位于vbde.c、vdbe.h、vdbeapi.c、vdbeInt.h和vdbemem.c等几个文件中。如第5章所述,一个语句(statement)会编译为一个完整的VDBE程序,执行一条单独的SQL命令。它通过底层的基础设施B-tree执行由编译器(Compiler)生成的字节代码,这种字节代码程序语言是为了进行查询、读取和修改数据库而专门设计的。

字节代码在内存中被封装成sqlite3_stmt对象(内部叫做Vdbe,见vdbeInt.h),Vdbe(或者说statement)包含执行程序所需要的一切,包括:

  • VDBE程序

  • 程序计数器

  • 结果字段的名称和类型

  • 参数的绑定值

  • 运行栈和固定数量的编号的内在单元

  • 其它的运行时状态信息,如B-tree游标

VDBE是一个虚拟机,它的字节代码指令和汇编程序十分类似,每一条指令由操作码和三个操作数构成:<opcode, P1, P2, P3>。Opcode为一定功能的操作码,为了理解,可以看成一个函数。p1是32位的有符号整数,p2是31位的无符号整数,它通常是跳转(jump)指令的目标地址(destination),当然还有其它用途;p3为一个以null结尾的字符串或者其它结构体的指针。目前SQLite中有128个操作码。和C API不同的是,VDBE操作码经常变化,所以不应该用字节码编写自己的程序。

下面的几个C API直接和VDBE交互:

  • sqlite3_bind_xxx() functions

  • sqlite3_step()

  • sqlite3_reset()

  • sqlite3_column_xxx() functions

  • sqlite3_finalize()

一般情况下,所有的API都是用来执行一个查询并在VDBE相关的结果集中步进操作。它们有一个共同点:都以一个语句句柄做参数。这是因为它们都需要句柄中的VDBE代码或相关资源来完成任务。注意:sqlite3_prepare()工作于开始阶段,用于产生VDBE代码,它不参与执行。

所有SQL命令的VDBE程序都可以通过EXPLAIN命令得到,如:

sqlite> .m col
sqlite> .h on
sqlite> .w 4 15 3 3 15
sqlite> explain select * from episodes;
addr        opcode                  p1    p2    p3
0            Goto                    0     12
1            Integer                 0     0
2            OpenRead             0     2     # episodes
3            SetNumColumns   0     3
4            Rewind                 0     10
5            Recno                   0     0
6            Column                0     1
7            Column                0     2
8            Callback                3     0
9            Next                     0     5
10          Close                    0     0
11          Halt                     0     0
12          Transaction           0     0
13          VerifyCookie         0     10
14          Goto                    0     1
15          Noop                    0     0

上面使用了4条命令,前面的命令用于调试和格式化。另外,我在编译SQLite时使用了SQLITE_DEBUG选项,这个选择可以提供运行栈更多的信息,比如包含在p3里面的表名。

空注:当前版本的SQLite(3.6.18)确实有较大变化,现在执行EXPLAIN命令的结果如下。

addr  opcode           p1   p2   p3     p4          p5    comment
----  ---------------  ---  ---  -----  ----------  ----  ----------
0     Trace            0    0    0                  00
1     Goto             0    11   0                  00
2     OpenRead         0    2    0      3           00
3     Rewind           0    9    0                  00
4     Rowid            0    1    0                  00
5     Column           0    1    2                  00
6     Column           0    2    3                  00
7     ResultRow        1    3    0                  00
8     Next             0    4    0                  01
9     Close            0    0    0                  00
10    Halt             0    0    0                  00
11    Transaction      0    0    0                  00
12    VerifyCookie     0    40   0                  00
13    TableLock        0    2    0      episodes    00
14    Goto             0    2    0                  00

空注:有关VDBE的最详细参考在vbde.c中,也可以参考SQLite网站提供的文档http://www.sqlite.org/opcode.html。

空注:后面的内容还按原文翻译。

栈(Stack)

一个VDBE程序通常由几个完成特定任务的段(section)构成,每一个段中都有一些操作栈的指令。这么做是因为不同的指令有不同数量的参数,有些指令只有一个参数;有些指令没有参数;有些指令有好几个参数,这时三个操作数就不够了。

考虑到这些情况,指令采用栈来传递参数。而这些指令本身不会做这些工作,所以在它们之前需要其它一些指令的帮助,以取得需要的参数。VDBE把计算的中间结果保存到内存单元(memory cell)中,其实堆栈和内存单元都基于Mem结构(见vdbeInt.h)。

程序体

让我们来看前面打开episodes表的例子。它的第一个段主要包括指令1~3。

第一条指令(Integer)是为第二条指令作准备的,也就是把第二条指令执行需要的参数压入堆栈,OpenRead从堆栈中取出参数值然后执行。

SQLite可以通过ATTACH命令在一个连接中打开多个数据库文件,每当SQLite打开一个数据库,它就为之赋一个索引号(index),主数据库的索引为0,附加的第一个数据库为1,依次类推。Integer指令将数据库索引的值压入栈(本例为0,代表主数据库),而OpenRead从中取出值,并决定操作哪个数据库。它用P2来确定需要打开表的根页(root page)。然后它打开一个指定数据库中指定表的B-tree游标。所有这些在VDBE代码文档中都有解释,例如,OpenRead命令在SQLite文档中的解释如下:

为数据库表打开一个只读游标,这个表的根页在数据库文件的P2处。数据库文件由栈顶的一个整数指定。0表示主数据库,1表示用于存放临时表的数据库。新打开游标的标识符在P1中。P1的值不必是相邻的,但应该是一个小整数。如果其值为负,表示错误。If P2==0 then take the root page number from off of the stack.

只要有游标打开,就会有一个读锁加载到数据库上。如果数据库本来是未加锁的,此命令的部分工作包括获得一个读锁。读锁允许其它进程读数据库,但是禁止任何进程改数据库。读锁在所有游标都关闭时释放。如果此指令在申请读锁时失败,程序结束并返回SQLITE_BUSY错误码。

P3的值是指向一个结构的指针,该结构定义索引的内容和排序序列的关键信息。当不指向索引时,P3的内容为空。

这个关于OpenRead的文档与其它指令的文档一样,可以直接在源程序文件中找到,特别是vdbe.c中。

最终,SetNumColumns指令设置游标需要处理的列的数量,这是由所要处理的表包含的列数决定的。P1为游标的索引(这里为0,是刚刚打开的游标的索引号)。P2为列的数目,episodes表有三列。

继续本例,Rewind指令将游标设置到表的开始,它会检查表是否为空(“空”即没有记录)。如果没有记录,它会导致指令指针跳转到P2指定的指令处。此处P2为10,即Close指令。一旦Rewind设置游标,接下来就会执行下一段(指令5~9)的几条指令。它们的主要功能是遍历结果集,Recno把由游标P1指定的记录的关键字段值压入堆栈。Column指令从由P1指定的游标,P2指定的列取值。5,6,7三条指令分别把id(primary key)、season和name字段(游标0所指明的表episodes的全部3个字段)的值压入栈。接下来,Callback指令从栈中取出三个值(由P1指定),然后形成一个记录数组,存储在内存单元 (memory cell) 中。然后,Callback会挂起VDBE的执行,把控制权交给sqlite3_step(),该函数将返回SQLITE_ROW。

图9-1 VDBE的步骤:Open和Read

一旦VDBE创建了记录结构(该结构同样关联于语句(statement)句柄),程序就可以通过sqlite3_column_xxx() 函数从记录结构内取出字段值。当下次调用sqlite3_step()时,指令指针会指向Next指令。Next指令会把游标移向表的下一行,如果有其它的记录,它会跳到由P2指定的指令,在这里为指令5(Recno指令),创建一个新的记录结构,进入下一次循环。如果已经没有其它记录可读,Next不跳转,而是执行下一条指令,这里是Close指令。Close指令会关闭游标,然后执行Halt指令,结束VDBE程序,并且sqlite3_step()函数会返回SQLITE_DONE。

程序开始与停止

前面介绍了程序的核心部分,现在来看看其余的指令,这些指令与启动和初始化有关,见图9-2。第一条指令是Goto指令,它是一条跳转指令,跳到P2处,本例中是跳到第12条指令。

指令12是Transaction,它开始一个新的事务;然后执行下一条指令VerifyCookie,它的主要功能是确定VDBE程序编译后,数据库schema是否改变(即是否进行过更新操作)。这在SQLite中是一个很重要的概念,在SQL被sqlite3_prepare()编译成VDBE代码至程序调用sqlite3_step()执行字节码的这段时间内,另一个SQL命令可能会改变数据库模式(比如ALTER TABLE、DROP TABLE或CREATE TABLE)。一旦发生这种情况,schema版本就会改变,之前编译的语句(statement)就会变得无效。当前的数据库schema信息记录在数据库文件的根页中。类似地,每个语句都有一份用于比较的在编译时刻该模式的备份,VerifyCookie的功能就是检查它们是否匹配,如果不匹配,就要采取适当的措施。

图9-2 VDBE的步骤:程序开始

语句的版本号由VerifyCookie的P2参数指定,将它与磁盘上的数据库schema版本号进行比较。如果schema没有改变,两个版本号应该一致。如果不一致,则VDBE程序失效。在此情况下,VerifyCookie将会终止程序并返回SQLITE_SCHEMA错误。在此情况下,应用程序需要重新编译SQL语句,基于新的schema版本生成新的VDBE程序。

如果两者匹配,会执行下一条指令Goto;它会跳到程序的主要部分,即第一条指令,打开表读取记录。这里有两点值得注意:

(1)Transaction指令本身不会获取锁。它的功能相当于BEGIN,而共享锁实际是由OpenRead指令获取的。当事务关闭时释放锁,由Halt指令完成,它会进行扫尾工作。

(2) 语句对象(VDBE程序)所需的存储空间在程序执行前就已经确定。这缘于两个重要事实:首先,栈的深度不会比指令的数目还多。其次,内存单元(memory cell)的数量永远不会多于指令的数量(通常少得多)。在执行VDBE程序之前,SQLite可以计算出分配资源所需要的内存。

指令的类型

VDBE同时只会执行一条指令。每条指令都完成一项简单的任务,而且通常和该指令前面、后面的指令有关。大体上来说,指令可分为三类:

(1)处理值:这些指令通常完成算术运算,比如加、减和除;逻辑运算,比如与和或;还有字符串操作。

(2)数据管理:这些指令操作在内存和磁盘上的数据。内存指令进行栈操作或者在内存单元之间传递数据。磁盘操作指令控制B-tree和pager打开或操作游标,开始或结束事务,等等。

(3)流程控制:控制指令主要是有条件地或无条件地移动指令指针。

一旦熟悉了指令集,就不难明白VDBE程序是如何工作的。至少你可以了解如何使用栈来为后面指令的执行做准备。

B-Tree和Pager模型

B-tree使VDBE执行查找、插入和删除的效率达到O(logN),以及在O(1)的效率下双向遍历结果集。它是自平衡的,可自动地执行碎片整理和空间回收。B-tree本身不会直接读写磁盘,它仅仅维护着页(page)之间的关系。当B-tree需要页或者修改页时,它就会调用pager。当修改页时,pager保证原始页首先写入日志文件。当它完成写操作时,pager根据事务状态决定如何做。

数据库文件格式

数据库中所有的页从1开始顺序编号。一个数据库由多个多重B-tree构成——B-tree用于每一个表和索引。每个表和索引的第1个页(地址)称为根页。所有表和索引的根页都存储在sqlite_master表中。

数据库中第一个页(page 1)有点特殊,page 1的前100个字节是一个对数据库文件进行描述的特殊文件头。它包括库的版本、格式的版本、页大小、编码等所有创建数据库时设置的永久性参数。有关这个特殊文件头的文档在btree.c中,page 1也是sqlite_master表的根页。

页重用及回收

SQLite利用一个空闲页链表(free list)完成页的循环使用。当一个页的所有记录都被删除时,就被插入到该链表。当有新信息需要进入数据库时,临近的空闲页先被选中,当没有空闲页时,才创建新的页(会增加文件的大小)。当运行VACUUM命令时,会清空空闲页链表,所以数据库会缩小。本质上它是在新的文件中重新建立数据库,而所正使用的页都被拷贝过去,而空闲页链表不拷,结果就是一个新的,变小了的数据库。当数据库的autovacuum开启时,SQLite不会使用空闲页链表,而且在每一次事务提交时自动压缩数据库。

B-Tree记录

B-tree中的页由B-tree记录组成,也叫做payload(有效载荷)。每一个B-tree记录(或payload)有两个域:关键字域(key field)和数据域(data field)。关键字域就是ROWID的值,也就是每个数据库表都会提供的关键字的值。从B-tree的角度,数据域可以是任何无结构的数据。数据库的记录就保存在这些数据域中。B-tree的任务就是排序和遍历,这仅需要关键字段。Payload的大小是不定的,这与内部的关键字和数据域有关。平均情况下,每个页一般包含多个payload,当然也可能一个payload占用几个页(当一个payload太大不能存在一个页内)。

B+树

B-tree按关键字的顺序存储,在一个B-tree中所有的关键字必须唯一(这一点自动地由ROWID主键字段保证)。表采用B+tree,B+tree的内部结点不包含表数据(数据库记录)。图9-3是一个表的B+tree的示例:

图9-3 B+tree的组织(表)

B+tree中的根页(root page)和内部页(internal page)都是用来导航的,这些页的数据域都是指向下级页的指针,仅仅包含关键字。所有的数据库记录都存储在叶子页(leaf page)内。在叶节点一级,记录和页都是按照关键字的顺序排列的,这使B-tree游标只使用页结点就能正向和反向(水平地)遍历记录,并使遍历的效率(时间复杂度)可能达到O(1)。

记录和字段

数据库记录位于叶子页的数据域,由VDBE管理(前面在介绍Callback命令时介绍过)。数据库记录以二进制的形式存储,但有一定的数据格式,这种格式描述了记录中的所有字段。记录格式是连续的字节流,其组成包括一个逻辑头(logical header)和一个数据区(data segment),逻辑头包括“头大小(可变长的64位整数)”和一个数据类型(也是可变长的64位整数)数组,数据类型用来描述存储在数据区的字段的类型,如图9-4所示。64位整数用Huffman编码实现。

图9-4 记录结构

类型入口的数量与字段数量相等。类型数组与字段数组的元素按下标相对应。一个类型入口表明它对应字段的数据类型和宽度。类型入口的可能取值及其含义在表9-1中列出。

表9-1 字段类型值

类型值 含义 数据宽度
0 NULL 0
N in 1..4 有符号整数 N
5 有符号整数 6
6 有符号整数 8
7 IEEE符点数 8
8-11 未使用 N/A
N>12的偶数 BLOB (N-12)/2
N>13的奇数 TEXT (N-13)/2

例如,取episodes表的第1条记录:

sqlite> SELECT * FROM episodes ORDER BY id LIMIT 1;
id    season     name
0     1            Good News Bad News

这条记录的内部记录格式如图9-5所示。

表9-5 episodes表的第1条记录

记录头长4字节。头的大小反映头内各要素都是单字节编码。第一个类型,对应id字段,是一个1字节有符号整数。第二个类型,对应season字段,也是一个1字节有符号整数。Name字段的类型入口是一个大于13的奇数,表示它是一个text值,该值占(49-13)/2=18个字节。通过这些信息,VDBE可以解析记录的数据段并取出独立的字段值。

层次数据组织

SQLite的层次数据组织模型如图9-6所示。在模型中,每层处理特定的数据单元。从下向上,数据越来越结构化;从上往下,数据越来越无序。C-API处理字段值,VDBE处理记录,B-tree处理健值的数据,pager处理页,OS接口处理二进制的数据和原始存储器。

图9-6 模型和各层所对应的数据

Each module takes part in managing its own specific portion of the data in the database, and relies on the layer below it to supply it with a more crude form from which to extract its respective pieces.

溢出页

如前所述,B-tree记录具有可变的大小,而页的大小是固定的。这就有可能一个B-tree记录比一个单独的页还要大。这时,超大的B-tree记录就溢出到由溢出页组成的链表上,如图9-7所示。

在图中,第4个页太大,B-tree模块就创建一个溢出页来容纳它。如果一个溢出页还不够,就再链接第2个。这实际上也是二进制大对象的处理方法。请记住:当你使用大的BLOB时,它实际上是存储在页链表中的。如果BLOB实在太大,链表就会很长,操作就会很低效。这种情况下,将BLOB存储在一个外部文件中而在数据库中只保存其文件名也许更好一些。

图9-7 溢出页

B-Tree API

B-Tree模块有它自己的API,它可以独立于C API使用。也就是说,如果你愿意,你可以把它当作一个独立的运行库来使用,或在SQLite中直接存取库表。SQLite B-tree模块的另一个好处就是它本身支持事务。由pager处理的事务、锁和日志都是为B-tree服务的。根据功能,可将B-Tree API分为以下几类:

访问和事务函数

包括:

  • sqlite3BtreeOpen: 打开一个新的数据库文件,返回一个B-tree对象。

  • sqlite3BtreeClose: 关闭一个数据库。

  • sqlite3BtreeBeginTrans: 开始一个新的事务。

  • sqlite3BtreeCommit: 提交当前事务。

  • sqlite3BtreeRollback: 回卷当前事务。

  • sqlite3BtreeBeginStmt: 开始一个statement事务。

  • sqlite3BtreeCommitStmt: 提交一个statement事务。

  • sqlite3BtreeRollbackStmt: 回卷一个statement事务。

表函数

包括:

  • sqlite3BtreeCreateTable: 在数据库文件中创建一个新的、空的B-tree。其参数决定是采用表格式(B+tree)还是索引格式(B-tree)。

  • sqlite3BtreeDropTable: 从数据库中删除一个B-tree。

  • sqlite3BtreeClearTable: 从B-tree中删除所有数据,但保持B-tree的结构。

游标函数

包括:

  • sqlite3BtreeCursor: Creates a new cursor pointing to a particular B-tree. Cursors can be either a read cursor or a write cursor. Read and write cursors may not exist in the same B-tree at the same time.

  • sqlite3BtreeCloseCursor: Closes the B-tree cursor.

  • sqlite3BtreeFirst: Moves the cursor to the first element in a B-tree.

  • sqlite3BtreeLast: Moves the cursor to the last element in a B-tree.

  • sqlite3BtreeNext: Moves the cursor to the next element after the one it is currently pointing to.

  • sqlite3BtreePrevious: Moves the cursor to the previous element before the one it is currently pointing to.

  • sqlite3BtreeMoveto: Moves the cursor to an element that matches the key value passed in as a parameter. If there is no match, leaves the cursor pointing to an element that would be on either side of the matching element, had it existed.

记录函数

包括:

  • sqlite3BtreeDelete: Deletes the record that the cursor is pointing to.

  • sqlite3BtreeInsert: Inserts a new element in the appropriate place of the B-tree.

  • sqlite3BtreeKeySize: Returns the number of bytes in the key of the record that the cursor is pointing to.

  • sqlite3BtreeKey: Returns the key of the record the cursor is currently pointing to.

  • sqlite3BtreeDataSize: Returns the number of bytes in the data record that the cursor is currently pointing to.

  • sqlite3BtreeData: Returns the data in the record the cursor is currently pointing to.

配置函数

包括:

  • sqlite3BtreeSetCacheSize: Controls the page cache size as well as the synchronous writes (as defined in the synchronous pragma).

  • sqlite3BtreeSetSafetyLevel: Changes the way data is synced to disk in order to increase or decrease how well the database resists damage due to OS crashes and power failures. Level 1 is the same as asynchronous (no syncs() occur and there is a high probability of damage). This is the equivalent to pragma synchronous=OFF. Level 2 is the default. There is a very low but non-zero probability of damage. This is the equivalent to pragma synchronous=NORMAL. Level 3 reduces the probability of damage to near zero but with a write performance reduction. This is the equivalent to pragma synchronous=FULL.

  • sqlite3BtreeSetPageSize: Sets the database page size.

  • sqlite3BtreeGetPageSize: Returns the database page size.

  • sqlite3BtreeSetAutoVacuum: Sets the autovacuum property of the database.

  • sqlite3BtreeGetAutoVacuum: Returns whether the database uses autovacuum.

  • sqlite3BtreeSetBusyHandler: Sets the busy handler.

还有其它的函数,所有这些函数在btree.h和btree.c中都有很完备的文档,但上面列出的函数可以使你建立一个总体印象。

编译器

前面已经介绍了VDBE以下直到OS层的各层次。下面介绍VDBE程序是怎么来的。编译器的输入是一个单独的SQL命令,输出是最终经过优化的VDBE程序,这些工作在3个阶段上完成:分词器(Tokenizer)、分析器(Parser)和代码生成器(Code Generator)。

分词器(Tokenizer)

编译的第一步是对SQL命令分词。分词器将一个命令分解成一串单独的词汇(token)。词可以是有特定含义的一个字符或一个字符序列。每个词都有其关联的词类(token class),词类是一个数字标识,表明这个词是什么。例如左括号的词类是TK_LP,保留字SELECT的词类是TK_SELECT。所有词类在parse.h中定义。例如下面的SQL语句:

SELECT rowid FROM foo where name='bar' LIMIT 1 ORDER BY rowid;

经分词器处理之后的部分结果在表9-2中给出。

表9-2 一个分词后SELECT语句

文本 词类 动作
SELECT TK_SELECT 发给分析器
" " TK_SPACE 丢弃
Rowid TK_ID 发给分析器
" " TK_SPACE 丢弃
FROM TK_FROM 发给分析器
" " TK_SPACE 丢弃
foo TK_ID 发给分析器
" " TK_SPACE 丢弃
WHERE TK_WHERE 发给分析器
" " TK_SPACE 丢弃
name TK_ID 发给分析器
= TK_EQ 发给分析器

总之,分词器按照SQL的词法定义把它切分为一个一个的词,并传递给分析器(Parser)进行语法分析(忽略空格)。

保留字

分词器是手工编写的(hand-coded),主要在Tokenize.c中实现。因为是手工代码,不是用自动生成的代码来对SQL保留字分类。保留字在keywordhash.h文件中定义。这个文件是一个最优化的、将所有SQL保留字压缩到可能最小的缓冲区,方法是公共的字符序列重叠存放。SQLite使用指明了每个保留字偏移量和大小的数组来识别保留字入口。这种方法是一种空间优化的方法,有利于内嵌式的应用程序。一个生成了的缓冲区的例子如下:

static int keywordCode(const char *z, int n){
static const char zText[537] =
"ABORTABLEFTEMPORARYADDATABASELECTHENDEFAULTRANSACTIONATURALTER"
"AISEACHECKEYAFTEREFERENCESCAPELSEXCEPTRIGGEREGEXPLAINITIALLYANALYZE"
"XCLUSIVEXISTSTATEMENTANDEFERRABLEATTACHAVINGLOBEFOREIGNOREINDEX"
"AUTOINCREMENTBEGINNERENAMEBETWEENOTNULLIKEBYCASCADEFERREDELETE"
"CASECASTCOLLATECOLUMNCOMMITCONFLICTCONSTRAINTERSECTCREATECROSS"
"CURRENT_DATECURRENT_TIMESTAMPLANDESCDETACHDISTINCTDROPRAGMATCH"
"FAILIMITFROMFULLGROUPDATEIFIMMEDIATEINSERTINSTEADINTOFFSETISNULL"
"JOINORDEREPLACEOUTERESTRICTPRIMARYQUERYRIGHTROLLBACKROWHENUNION"
"UNIQUEUSINGVACUUMVALUESVIEWHERE";

The keywordhash.h file includes a routine sqlite3KeywordCode(), which allows the tokenizer to quickly match the keyword with its appropriate token class with minimal space. So, the tokenizer first tries to match a token with what it knows, and failing that, it resorts to sqlite3KeywordCode(), which will return either a keyword token class or a generic TK_ID.

The tokenizer and parser work hand in hand, one token at a time. As the tokenizer resolves each token, it passes the token to the parser. The parser takes the tokens and builds a parse tree, which is a hierarchical representation of the statement.

分析器(Parser)

SQLite的语法分析器是用Lemon生成的(Lemon是一个开源的LALR(1)语法分析器的生成器,SQLite在使用时进行了定制)。该分析器用parse.c内定义的语法规则将一串词组织成层次结构的分析树(parse tree)。

The parse tree is primarily composed of expressions and lists of expressions. An expression itself is a recursive structure that can contain subexpressions under it. For example, the WHERE clause in a SELECT parse tree is represented by a single expression. The SELECT clause, on the other hand, is represented as a list of expressions; each expression is a column that will be returned in the result set. 例如,如下简单的SQL语句:

SELECT rowid, name, season FROM episodes WHERE rowid=1 LIMIT 1

可以组织成如图9-8所示的分析树。

图9-8 简化了的分析树

一旦语句经过分词和分析,分析树作为一种结果会传送给代码生成器。

代码生成器(Code Generator)

代码生成器是SQLite中最庞大、最复杂的部分。与其它模块不同,代码生成器没有定义明确的接口,但它与分析器关系紧密。代码生成器由多个源文件组成,这些源文件大多针对特定的SQL操作。例如,生成SELECT语句的代码在select.c中,其它的源文件包括update.c、insert.c、delete.c和trigger.c等等。

代码生成器根据语法分析树生成VDBE程序。树的每一部分生成一个VDBE指令序列来完成特定的任务。The values for the operands are taken from the data structures associated with the parse tree. 例如,下面是一个读操作中打开表的代码的生成实现:

/* Generate code that will open a table for reading.*/
void sqlite3OpenTableForReading(
  Vdbe *v,        /* Generate code into this VDBE */
  int iCur,       /* The cursor number of the table */
  Table *pTab     /* The table to be opened */
){
  sqlite3VdbeAddOp(v, OP_Integer, pTab->iDb, 0);
  sqlite3VdbeAddOp(v, OP_OpenRead, iCur, pTab->tnum);
  VdbeComment((v, "# %s", pTab->zName));
  sqlite3VdbeAddOp(v, OP_SetNumColumns, iCur, pTab->nCol);
}

Sqlite3vdbeAddOp函数有三个参数:(1)VDBE实例(它将添加指令),(2)操作码(一条指令),(3)两个操作数。它增加一条指令到VDBE程序。上例中,sqlite3OpenTableForReading增加了3条指令,即图9-1中的指令1~3,功能是打开一个表的B-tree用于读。为方便起见,将图9-1中的指令序列重列于此:

sqlite> explain select * from episodes;
addr        opcode                  p1    p2    p3
0            Goto                    0     12
1            Integer                 0     0
2            OpenRead             0     2     # episodes
3            SetNumColumns   0     3
4            Rewind                 0     10
5            Recno                   0     0
6            Column                0     1
7            Column                0     2
8            Callback                3     0
9            Next                     0     5
10          Close                    0     0
11          Halt                     0     0
12          Transaction           0     0
13          VerifyCookie         0     10
14          Goto                    0     1
15          Noop                    0     0

优化

代码生成器不仅负责生成代码,也负责进行查询优化。优化是代码生成的一部分,主要的实现位于where.c中。生成的WHERE子句通常被其它模块共享,比如select.c、update.c和delete.c。这些模块调用sqlite3WhereBegin()开始WHERE语句块的指令生成,然后将返回的代码加入到它们自己的VDBE代码中,最后调用sqlite3WhereEnd(),生成结束WHERE子句代码的VDBE指令。程序的一般结构如图9-9所示:

图9-9 WHERE子句的VDBE代码的生成 优化发生在sqlite3WhereBegin()阶段。 它在已完成工作的基础上,寻找可以使用的索引,寻找可以重写的表达式,等等。 为了能对优化先有一个感觉, 我们从一个不含WHERE子句的简单SELECT语句开始,如图9-10所示:

图9-10 一个不含WHERE子句的SELECT语句

powered by Gitbook该教程制作时间: 2016-05-17 19:45:32