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

(integer) 0

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

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

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

(integer) new rowid

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

(string) "hello1"

(integer) new rowid

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

(integer) 98

(string) "hello1"

(integer) new rowid

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

Ti代表操作数类型,其意义如下:

** 'n' =NUMERIC.

** 'i' =INTEGER.

** 't' =TEXT.

** 'o' =NONE.

(record) "hello1", 98

(integer) new rowid

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)文法介绍

原文发布于微信公众号 - WeMobileDev(WeMobileDev)

原文发表时间:2015-09-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏

C++实现线程安全的单例模式

在某些应用环境下面,一个类只允许有一个实例,这就是著名的单例模式。单例模式分为懒汉模式,跟饿汉模式两种。 首先给出饿汉模式的实现 template <class...

2217
来自专栏腾讯数据库技术

Online DDL过程介绍

4323
来自专栏更流畅、简洁的软件开发方式

其实添加数据也可以这样简单——表单的第一步抽象(针对数据访问层)《怪怪设计论: 抽象无处不在 》有感

更正: 不好意思,昨天晚上思路有点混乱。有几个前提忘记说明了,现在补充一下。 1、缩小范围。按照由简到难的思路,这里先讨论最简单的添加数据的情况。就是单表的添...

2298
来自专栏Java编程技术

受限访问量问题中锁的使用

最近在做网上法庭的一个比较有意思的小需求,就是通过扫二维码方式允许最多30个人同时进入庭审,但是不限制进入的是是不是庭审人员,也就是说只要扫了这个二维码并且当前...

942
来自专栏Java架构沉思录

分布式ID常见解决方案

在分布式系统中,往往需要对大量的数据如订单、账户进行标识,以一个有意义的有序的序列号来作为全局唯一的ID。

6292
来自专栏青玉伏案

iOS开发之SQLite-C语言接口规范(一)——Ready And Open Your SQLite

  为什么要搞一搞SQLite的C语言接口规范呢? 因为在做iOS开发中难免会遇到操作数据库的情况,你可以使用第三方的FMDB等,或者使用CoreData。但我...

2315
来自专栏Danny的专栏

实时错误 '91' :对象变量或with块变量未设置

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

7312
来自专栏我有一个梦想

vc++ 在程序中运行另一个程序的方法

在vc++ 程序中运行另一个程序的方法有三个: WinExec(),ShellExcute()和CreateProcess() 三个SDK函数: WinExec...

4559
来自专栏PingCAP的专栏

TiDB 源码阅读系列文章(十)Chunk 和执行框架简介

Chunk 本质上是 Column 的集合,它负责连续的在内存中存储同一列的数据,接下来我们看看 Column 的实现。

5.7K145
来自专栏黑泽君的专栏

day29_Hibernate学习笔记_01

  Hibernate:是一个数据持久化层的ORM框架。   Object:对象,java对象,此处特指JavaBean。   Relational:关系,二维...

782

扫码关注云+社区

领取腾讯云代金券