SQLite虚拟机

1 前言

本文主要介绍SQLite虚拟机VDBE，为了更好地了解SQLite虚拟机，文中也加入了一些Lua虚拟机内容来对比学习，更好地了解不同虚拟机之间的异同。

1.1 预备知识

虚拟机设计需要编译原理相关理论基础，这里先简单温习下编译原理中的一些知识。

1.1.1 文法

(1) LR文法

1965年，D.knuth 首先提出了LR(K)文法及LR(K)分析技术。括号中的K 表示向右查看输入串符号的个数。对于大多数用无二义性上下文无关文法描述的语言都可以用相应的LR 分析器进行识别，而且这种方法还具有分析速度快，能准确、及时地指出出错位置。

(2) LR(0)，SLR(1)，LR(1)，LALR(1)

LR(0)：分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，不适用绝大多数高级语言的语法分析器，但它是构造其它LR 类分析器的基础。

SLR(1)：简单LR(1)分析法

SLR(1)方法简单地把非终极符的后继符集做为可归约的依据，较容易产生文法冲突。

LR(1)：针对不同产生式上的非终极符，分别定义其后继符集，减少了移入/归约冲突。

LALR(1):Look-AheadLR(1)：

是LR(1)的优化版,LR(1)文法产生的项目较多，带来的实际问题是系统资源消耗大。由于许多LR(1)产生式具有同心状态，合并这些同心状态后没有冲突的文法即符合LALR文法。

LALR分析法因减少了系统内存消耗而得到广泛的使用

(3)YACC

目前对于真正实用的编译程序，所采用的LR分析器基本都是借助于美国贝尔实验室1974年推出的"一个编译器的编译器-YACC"来实现的。它能接受一个用BNF(巴科斯范式)描述的LALR(1)文法并构造LALR(1)语法分析器。简单来说就是YACC这个工具可以编译一个符合LALR（1）文法的语法文件，输出一个该文法文件对应的语法解析文件，这个输出文件一般是C或C++文件。

SQLite中的文法文件是parse.y

(4)Lemon

SQLite中的文法文件并不是使用YACC编译的，而是用Lemon编译。Lemon是SQLite作者维护的一个开源项目。Lemon的源文件在SQLite包里tool目录下，只包含两个C文件：lemon.c和lempar.c，其中lempar.c是模板文件，在编译parse.y时使用。Lemon.c则用于生成lemon可执行程序。

Lemon与YACC没有本质上的不同，都是LALR(1)文法编译器。但lemon有一些改进，主要有：

(1)语法更易读和理解，变量不易弄错。

YACC语法示例： expr -> expr PLUS expr { $$ = $1 + $3; };

Lemon语法示例： expr(A) ::= expr(B) PLUS expr(C). { A = B+C; }

(2)Lemon不使用全局变量，YACC在分析器与分词器间使用全局变量。

(3)Lemon是可重入的，允许多个分析器同时运行。YACC不支持重入。

Lemon简介:

http://www.hwaci.com/sw/lemon/

http://www.hwaci.com/sw/lemon/lemon.html

用Lemon编译parse.y文件后生成的文件是parse.c文件，它包含在SQLite源文件包里。这个文件是解释SQL语句生成可执行指令的编译程序，其入口是函数sqlite3Parser。

Lua在3.1版本以前使用LALR(1)文法文件，并使用YACC生成该文法文件生成编译引擎。但从3.1版本开始为了实现更高的编译效率，使用手写的自顶向下的编译器。

2 虚拟机的组成要素

1．语言和文法

SQLite虚拟机的语言是SQL语句，类似insert into … 这种SQL语句。Lua的语言就是我们在lua脚本中写程序用的语句。

文法是解释语言用的规则，许多虚拟机会采用文法文件，SQLite中是parse.y文件，Lua早期版本是lua.stx文件。

2．文法编译器

编译文法文件的工具。SQLite用的Lemon，Lua早期版本用Yacc。编译器编译文法文件，生成语法分析程序。SQLite中生成的文件是parse.c。Lua1.1版本生成的是y.tab.c。

3．指令和程序

虚拟机中执行的程序体，程序由指令串构成。指令常会变化比较大，以适应各种不同的需求或性能改进等。SQLite和Lua的指令都经历过比较大变化。

4．执行器和运行期环境

在SQLite中入口是sqlite3VdbeExec，Lua执行入口是lua_execute。运行期需要维护的主要是程序运行栈、程序计数器PC、寄存器等。

3 SQLite虚拟机

3.1 SQLite架构

图一

上图取自SQLite官网，在《SQLite文件分析》中，主要介绍了B-Tree这部分内容（图中左下角框图）。本文则主要介绍上面两个框图部分。

3.2 SQL语句执行流程图

本文中的SQL语句Demo采用下面的例子:

create table examp(one text, two int);

insert into examp values ('hello', 98);

流程图如下：

图二

3.3 SQL语句编译

编译的目的是将SQL语句生成能够在SQLite虚拟机VDBE(Virtual Database Engine)中可以执行的指令序列（可以理解为VDBE的执行程序）。SQLite的SQL语句编译引擎在parse.c文件中，由工具Lemon编译文法文件parse.y而来，引擎的入口函数是sqlite3Parser。所有的SQL语句都将通过sqlite3Parser编译成指令才会在虚拟机VDBE中执行

我们用下面SQL语句作为Demo来演示SQL语句的编译。

insert into examp values ('hello1', 98 );

//Insert Demo 1

insert into examp( one,tow ) values('hello', 98 );

//Insert Demo 2，与1等价

Parse.y中对应的inert文法有两条

////// The INSERTcommand //////////

cmd ::= insert_cmd(R) INTO fullname(X)inscollist_opt(F)

VALUES LP itemlist(Y) RP.

{sqlite3Insert(pParse,X, Y, 0, F, R);}

//前面两个insert例子会匹配上面的文法项。其中参数F是可选的，demo1的F为空，demo2的F为表列的List。

cmd ::= insert_cmd(R) INTO fullname(X)inscollist_opt(F) select(S).

{sqlite3Insert(pParse, X, 0, S, F, R);}

//对于形如下面的insert语句会匹配第二条insert文法项

INSERT INTO first_table_name [(column1,column2, ... columnN)]

SELECT column1,column2, ...columnN

FROMsecond_table_name [WHERE condition];

上面例子中的Insert语句会调用sqlite3Insert函数生成insert语句相关的指令序列。

3.4 SQLite的VDBE指令

VDBE每条指令都包括一个操作码和三个操作数，P1，P2，P3(注：VDBE指令随版本不同会有较大变化，但大体指令的模式仍是想通的，SQLite近期的版本采用5个操作数)。P1是一个任意整数，P2是一个非负整数，P3是一个结构体指针（可能为空）或者非空的字符串。很少的指令使用全部三个操作数。大多数指令仅仅使用一个或者两个操作数。也有一些指令没有操作数，而是操作在执行栈上的数据。

仍然用前面的insert语句来看看生成的指令序列，如下图所示：

图三

解释一下上图中每条指令的意义，下面表格中代表运行时执行指令后VDBE栈的变化

0|Goto|0|11| 跳转到第11条指令

1|Integer|0|0| 将要操作的数据库ID入栈，数据库ID这里是0

2|OpenWrite|0|5| OpenWrite指令打开一个可写游标。P1=0 table id， P2=5 table所在的根页号，P3没有被使用

3|SetNumColumns|0|2| 设置列数目

4|NewRowid|0|0| 为新插入的纪录分配rowid，同时rowid入栈

5|String8|0|0|hello 将字符串”hello”入栈

6|Integer|98|0| 将整数98入栈

7|MakeRecord|2|0|ti 将栈中P1=2个元素弹出，转换成二进制（用于写入db），压入栈

Ti代表操作数类型，其意义如下：

** 'n' =NUMERIC.

** 'i' =INTEGER.

** 't' =TEXT.

** 'o' =NONE.

8|Insert|0|3| 执行插入记录到数据库，栈清空

9|Close|0|0| 关闭游标

10|Halt|0|0| 同步脏Page到文件，结束

11|Transaction|0|1| 事务开始。事务开始会获得一个写锁，当这个事务在执行时其他程序不能读或者写这个文件。开始事务会创建一个回滚日志，在对数据库改变前必须启动一个事务。

12|VerifyCookie|0|4| 检查cookie 0（数据库schema版本）以确保它等于P2（数据库schema最后读出的值）。P1是数据库号（0代表主数据库）。这是确保数据库schema没有被其他线程改写而导致它必须被重新读入

13|Goto|0|1| 跳转到第1条指令

14|Noop|0|0|

3.4.1 栈和寄存器

根据指令获取操作数方式的不同，可以把虚拟机的实现分为基于栈和基于寄存器两类，两种实现方法同样会导致指令有比较大差异。

基于栈的虚拟机

对于大多数的虚拟机，比如JVM，Python，都采用传统基于栈的。VDBE同样基于栈。

基于栈的虚拟机指令一般都是在当前栈中获取和保存操作数。比如一个简单的加法赋值运算:a=b+c，一般会被转化成如下的指令:

1.push b; // 将变量b的值压入stack

2.push c; // 将变量c的值压入stack

3.add; // 将stack顶部的两个值弹出后相加，将结果压入stack

4.mov a; // 将stack顶部结果放到a中

由于基于栈的指令是通过当前栈来查找操作数的，这意味着所有操作数的存储位置是在运行期才决定。因为不需要在编译阶段决定在哪里存储操作数，所以基于栈的编译器实现起来相对比较容易。

基于栈的缺点在于：对于一个简单的运算，也需要使用较多的指令组合才能完成，这样增加了整体指令集的长度。虚拟机也需要同样多的迭代次数来执行这些指令，这对于效率来说会有比较大的影响。并且，由于操作数都要放到栈上，使得移动这些操作数的内存复制增加，这也会影响效率。

基于寄存器的虚拟机

基于寄存器的指令都是在已经分配好的寄存器中存取操作数。对于上面的运算，一般会使用如下的指令:

add a b c; //将b与c对应的寄存器的值相加，将结果保存在a对应的寄存器中

基于寄存器的指令可以直接对应标准的3地址指令，用一条指令完成了上面多条指令的计算工作，并且有效地减少了内存复制操作。这样的指令系统对于效率有很大的帮助。不过，在编译器设计上，就要在代码生成阶段对寄存器进行分配，增加了实现的复杂度。并且每条指令的复杂度增加。

Lua 在5.0版本以前采用栈方式，5.0以后采用寄存器方式。

3.4.2 对比Lua的指令

让我们看看Lua早期版本的指令和5.0后的指令对比。用一个简单的算术运算来查看指令。

Demo： a=11;b=2;c=a+b;

lua1.1版本指令

图四

1.1版本是基于栈的，ADDOP前进行了操作数压栈。

lua5.2版本指令

Lua5.2的指令使用32bit的unsigned integer表示。所有指令的定义都在lopcodes.h文件中，总共有40种指令(id从0到39)。根据指令参数的不同，可以将所有指令分为4类:

图五

从上图可以看到lua5.2的指令高度精炼，lua可以把脚本编译成lua可执行文件随宿主程序一起发布，其指令的精炼可以使生成的可执行文件很小，执行起来速度也更快。

图六

5.2版本基于寄存器，ADD指令包含了操作数寄存器，寄存器id从0开始。

对比Lua早前版本和现在的版本，可以看到Lua在性能优化方面做了很多努力。

3.5 VDBE(Virtual Database Engine)

SQL语句编译成指令序列后，接下里会在虚拟机中执行这些指令。VDBE引擎的入口是sqlite3VdbeExec，很好理解这个函数一定包含一个循环和所有指令的Case分支，引擎执行编译好的指令序列。每条指令对应一个case OP_xxxx。下面是截取sqlite3VdbeExec的一个片段。

/*从这里开始执行指令

**pc为程序计数器(int)

*/

for(pc=p->pc; rc==SQLITE_OK; pc++){

//取得操作码

pOp = &p->aOp[pc];

switch( pOp->opcode ){

case OP_Goto:{ /*jump */

CHECK_FOR_INTERRUPT;

pc =pOp->p2 - 1;

break;

}

… …

}

}

VDBE主要工作如下：

1.保存编译好的SQL语句对应指令集，即程序体。

2.执行指令相应的动作

3.维护运行时栈的状态。VDBE的栈是局部的，Lua1.1版时还比较简陋，使用的是全局栈，3.1版本后引入了闭包（closure）

4.维护指令计数器PC

4 参考文献

1.《程序设计语言编译原理》 作者：陈火旺等。

2.《lex与yacc》 JobnR.Levine等。

3. SQLite源码，主要用的3.2.8版本

4. Lua各版本源码

5 附录

这部分附件下载自网络，作者不详。

5.1 LR(0),SLR(1),LR(1),LYLR(1)文法介绍