热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

虚拟机_SQLite虚拟机

篇首语:本文由编程笔记#小编为大家整理,主要介绍了SQLite虚拟机相关的知识,希望对你有一定的参考价值。1

篇首语:本文由编程笔记#小编为大家整理,主要介绍了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/

用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);

流程图如下:

SQLite虚拟机
图二

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 SQLiteVDBE指令

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

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

SQLite虚拟机

图三

解释一下上图中每条指令的意义,下面表格中代表运行时执行指令后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对应的寄存器中

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

3.4.2 对比Lua的指令

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

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

lua1.1版本指令

SQLite虚拟机
图四

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 参考文献

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

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

4. Lua各版本源码

5 附录

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

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


推荐阅读
  • 在使用mybatis进行mapper.xml测试的时候发生必须为元素类型“mapper”声明属性“namespace”的错误项目目录结构UserMapper和UserMappe ... [详细]
  • 本文探讨了一个Web工程项目的需求,即允许用户随时添加定时任务,并通过Quartz框架实现这些任务的自动化调度。文章将介绍如何设计任务表以存储任务信息和执行周期,以及如何通过一个定期扫描机制自动识别并加载新任务到调度系统中。 ... [详细]
  • 本文详细介绍了在MyBatis框架中如何通过#和$两种方式来传递SQL查询参数。使用#方式可以提高执行效率,而使用$则有助于在复杂SQL语句中更好地查看日志。此外,文章还探讨了不同场景下的参数传递方法,包括实体对象、基本数据类型以及混合参数的使用。 ... [详细]
  • 本文由公众号【数智物语】(ID: decision_engine)发布,关注获取更多干货。文章探讨了从数据收集到清洗、建模及可视化的全过程,介绍了41款实用工具,旨在帮助数据科学家和分析师提升工作效率。 ... [详细]
  • 将XML数据迁移至Oracle Autonomous Data Warehouse (ADW)
    随着Oracle ADW的推出,数据迁移至ADW成为业界关注的焦点。特别是XML和JSON这类结构化数据的迁移需求日益增长。本文将通过一个实际案例,探讨如何高效地将XML数据迁移至ADW。 ... [详细]
  • 一、使用Microsoft.Office.Interop.Excel.DLL需要安装Office代码如下:2publicstaticboolExportExcel(S ... [详细]
  • 本文分享了作者在使用LaTeX过程中的几点心得,涵盖了从文档编辑、代码高亮、图形绘制到3D模型展示等多个方面的内容。适合希望深入了解LaTeX高级功能的用户。 ... [详细]
  • MVC模式下的电子取证技术初探
    本文探讨了在MVC(模型-视图-控制器)架构下进行电子取证的技术方法,通过实际案例分析,提供了详细的取证步骤和技术要点。 ... [详细]
  • java datarow_DataSet  DataTable DataRow 深入浅出
    本篇文章适合有一定的基础的人去查看,最好学习过一定net编程基础在来查看此文章。1.概念DataSet是ADO.NET的中心概念。可以把DataSet当成内存中的数据 ... [详细]
  • 使用 ModelAttribute 实现页面数据自动填充
    本文介绍了如何利用 Spring MVC 中的 ModelAttribute 注解,在页面跳转后自动填充表单数据。主要探讨了两种实现方法及其背后的原理。 ... [详细]
  • 使用REM和媒体查询实现响应式布局
    本文介绍如何利用REM单位和媒体查询(Media Queries)来创建适应不同屏幕尺寸的网页布局。通过具体示例,展示在不同屏幕宽度下如何调整页面元素的样式。 ... [详细]
  • 本文介绍了一种在 Android 开发中动态修改 strings.xml 文件中字符串值的有效方法。通过使用占位符,开发者可以在运行时根据需要填充具体的值,从而提高应用的灵活性和可维护性。 ... [详细]
  • Java高级工程师学习路径及面试准备指南
    本文基于一位朋友的PDF面试经验整理,涵盖了Java高级工程师所需掌握的核心知识点,包括数据结构与算法、计算机网络、数据库、操作系统等多个方面,并提供了详细的参考资料和学习建议。 ... [详细]
  • 本文详细介绍了如何在PHP中使用Memcached进行数据缓存,包括服务器连接、数据操作、高级功能等。 ... [详细]
  • Hadoop MapReduce 实战案例:手机流量使用统计分析
    本文通过一个具体的Hadoop MapReduce案例,详细介绍了如何利用MapReduce框架来统计和分析手机用户的流量使用情况,包括上行和下行流量的计算以及总流量的汇总。 ... [详细]
author-avatar
书友30905431
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有