分享
 
 
 

Sqlite虚拟机VDBE原理(1)(翻译自sqlite.org)

王朝mssql·作者佚名  2007-01-21
窄屏简体版  字體: |||超大  

在网上找了很久相关的资料,但是找到的都是只言片语,索性自己翻译,可能相当不通顺~表骂我。。。

后续还有很多关于Sqlite/编程的资料会陆续放上来,翻译也好,转载也罢,原创最好,为的只是留下一点资料以后翻起来方便,谁让我脑子进水记不住东西。。。

------------------------------------------废话和正文的分割线-------------------------------------------------------------

VDBE (virtual database engine)是一个运行他自己的虚拟机语言组成的程序的虚拟机。每条程序都是用来查询或者操作数据库的。出于这个目的,VDBE的机器语言被设计用来进行搜索,读和修改数据库。

每一条VDBE 说明包括一个OPCODE 和3个OPRANDS分别为P1,P2和P3。P1,P2 为整数,P3是一个指向数据结构或者字符串的指针,有可能为空。大多数说明只用到1-2个OPRANDS,只有少数 说明用到了全部3个OPRANDS。有很多非常重要的说明根本没有用到任何OPRANDS但是却能读取数据并且将结果写入运行时栈当中。

一段VDBE代码从说明0开始运行,直到

1。遇到致命错误;

2。执行了停止说明;

3。整段代码运行完毕,所有打开的数据库都已经关闭,所有内存都已经释放,栈为空。

example:

1.建立一个数据表,并且插入一个数据

CREATE TABLE examp(one text,two int);

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

VDBE将这样解释并执行这两条语句

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条VDBE说明,前3条和最后2条是系统的标准步骤,所以真正完成我们的工作的是中间7条说明。这段代码中没有跳转语句,所有整个代码段从上到下执行一遍。

0 Transaction 0 0

1 VerifyCookie 0 81

2 Transaction 1 0

Transaction 开始一项交互活动。直到 遇到Commit 或者Rollback 时停止。P1参数是交互开始的数据库文件的索引。0号索引是主文件,1代表这个文件存放的是临时表。如果P2参数不为0,则开始一个写交互。当交互开始之后,对应的数据库文件获得"write lock"状态。在这项交互进行当中其他进程将无法读取这个文件。一项交互必须在任何对数据文件的修改动作之前进行。如果P2是0这文件将获得一个"read lock"

VerifyCookie 检查数据库0号参数(计划版本)以确保它=P2,P1是数据库编号,0代表主数据库文件,1代表文件拥有临时表,其他更大的数字代表附加数据库。

在建立VerifyCookie之前,必须有一个Transaction已经开始,或者已经建立了一个read lock.

第2个Transaction语句开始一项交互,应用对象是数据库1 (一个临时数据表)。

3 Integer 0 0

4 OpenWrite 0 3 examp

Integer 将整数P1 (0)压入堆栈。0是下面 OpenWrite 所要用到的数据库的编号,如果P3不为0 ,那么它就是一个代表相同整数的字符串,执行这条语句后,堆栈看起来是这样

(integer) 0

OpenWrite 创建一个新的读/写指针,指向P1(0)也就是数据库中的主文件“examp”,他的根页(节点)是P2(3),因为数据库文件第一页是空的,第二页存放的是数据表的索引。从第3页开始存放每个数据表当中的数据。P3("examp")是被打开的表的名字,这个参数是不被使用的,只是使代码更容易阅读而已。这条语句将栈顶元素弹出(0) ,所以之后,堆栈为空。

5 NewRecno 0 0

NewRecno 为指针P1指向的数据表创建一个整型的新的纪录号。这个纪录好并不是一个用在表里的键值。新的纪录号被压入堆栈。这个动作之后,堆栈看起来是这样:

(integer) new record key

6 String 0 0 Hello, World!

String 将它的P3参数压入堆栈,之后,堆栈应该是这样:

(string) "Hello World!"

(integer) new record key

7 Integer 99 0 99

动作之后,堆栈应该是这样:

(integer) 99

(string) "Hello, World!"

(integer) new record key

8 MakeRecord 2 0

MakeRecord 将栈顶的P1个元素取出( 2个),并且将他们转换成二进制,然后再把新生成的结构压回堆栈。之后,堆栈应该是这样:

(record) "Hello, World!", 99

(integer) new record key

9 PutIntKey 0 1

PutIntKey 将栈顶的2个元素作为一个entry写入P1所指的表中,如果表中元素不存在,那么将被创建。如果已经存在,则会被覆盖。数据是栈顶元素,键是下面的元素。这条语句当中,进行2次出栈操作。P2参数用来判定是否修改表中当前rowID,P2=1则rowID+1,并且由last_insert_rowID()函数返回,如果rowID=0,则行号不变,仍未当前ID.(这就解释了"表中元素不存在,那么将被创建。如果已经存在,则会被覆盖").这条语句是文件操作上的insert.

10 Close 0 0

Close 关闭之前打开的一个文件指针(0)(对应于前面的OpenWrite), 如果文件指针当前并没有打开,这条语句不被执行。

11 Commit 0 0

Commit 执行所有最后生效的Transaction的对数据库的修改.在另外一个Transaction 发起之前,所有其他的修改都不被允许。Commit删除所有临时文件,释放write lock。但是如果有任何文件指针存在,read lock将一直存在。

12 Halt 0 0

Halt 使VBDE立即退出。所有文件指针将被立即自动释放。P1是执行结果,他被exec()函数返回。如果正常返回,P1应该是0,如果不正常,则会是其他的数值。P2只有出现错误时才会被用到。当P1!=0时,P2用来决定是否ROLLBACK 。P2=OE_Fail ,不ROLLBACK ;当P2=OE_ROLLBACK ,执行ROLLBACK;当P2=OE_Abort then back out all changes that have occurred during this execution of the VDBE, but do not rollback the transaction

2.简单的查询

SELECT * FROM examp;

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

分析如下:

0 ColumnName 0 0 one

1 ColumnName 1 0 two

前两条语句确定结果当中有几列

2 Integer 0 0

3 OpenRead 0 3 examp

4 VerifyCookie 0 81

语句2和3 打开一个指向被查询数据表的读指针。这个过程和前面insert 的例子里面的openwrite语句一样,只不过这里是读而不是写。语句4同前面例子

5 Rewind 0 10

这条语句初始化一个在examp上的循环过程。如果表为空,那么就跳转道P2(10)这条语句,这里是Close ,调处循环。如果不为空,则进入下面的语句6

6 Column 0 0

7 Column 0 1

8 Callback 2 0

这3条语句是循环体。语句6和7分别将P1指针所指的表元素当中的P2列压入栈中。在这个例子当中,6语句将"one"列压入栈中,7语句将"two"列压入栈中。8语句调用回调函数,弹出栈顶的2个元素作为数据。

9 Next 0 6

Next 语句是循环的一部分,和5一起构成了循环的框架。如果循环进行润立,则转到P2所指的语句 (6)。

10 Close 0 0

11 Halt 0 0

这两条语句关闭所有指针,并且退出VDBE .

查询的关键在于语句5,9所组成的循环,以及语句8调用回调函数将查询出的数据当作参数传递给他。

3.复杂的查询

SELECT one, two, one || two AS 'both'

FROM examp

WHERE one LIKE 'H%'

这条查询确实太过于夸张~不过它足以解释VDBE的查询机制。结果将会包含3列,one,tow 和both.前2列直接从表中复制,但是第三列是用第一列和第二列合并而成的。最后,WHERE子句说明我们只需要以"H"开头的'one'列。

解析后的代码如下

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

除了WHERE子句,这段代码的结构和前面的简单查询的例子几乎一样,只是多出来一列。

Callback产生3列,但是大致上和前面的例子类似.当Callback被调用的时候,结果当中最左边的列应该是堆栈最底部的数据,最右边的列应该是堆栈顶部的数据。11,12两条语句将第一列,第二列数据压入堆栈。13,14 两条语句将即将合并为第3列的数据依次压入堆栈。15语句Concat将栈顶2条语句取出,合并为1个数据并且压回堆栈。

从第7条到第10条语句处理的是WHERE子句。第7条和第8条子句将"one"列和String "H%"压入栈。Function 语句 提出栈顶2个数据比较之后将结果(匹配/不匹配)压入栈中,P3指向比较函数的地址。第10条 IfNot 将栈顶元素出栈,如果不匹配,则直接跳到Next语句(17),如果匹配,则继续下面的语句。

PS: 这里的比较函数是一个用户定义的函数

总结:SELECT 模板

1.为Callback初始化一个ColumnName[]数组;

2.建立一个指向检索表的指针;

3.对于数据文件当中的每一条记录

a.如果 WHERE 子句判断为失败,则直接跳转道NEXT 子句,继续判断下一条记录;

b.判断当前纪录所有列;

c.调用CallBack函数纪录结果。

4。关闭指针,结束VDBE。

UPDATE & DELETE

UPDATE和DELETE 语句使用和SELECT 类似的模板。主要的不同在于,最后需要的操作不是调用CallBack函数而是修改数据库。既然是需要修改数据库那么就需要用到transaction子句。

4.DELETE

DELETE FROM examp WHERE two<50;

这条SQL语句会从examp文件里删除所有"two"列小于50的数据。

产生的VDBE数据如下

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

这段代码必须做到:

1.必须定位所有需要删除的数据,可以用一个非常类似于SELECT的循环来完成。

2.当所有该删除的数据都找出来以后,就可以挨个删除。

注意:我们不能找出一条删掉一条,而必须一起删除。因为数据库文件使用的是B-树存储,一旦在遍历过程当中有数据被删除,那么树的结构就会变化,从而遍历顺序会发生变化,导致有的数据被访问很多次,而有的数据根本没有被访问到。

所以DELETE实际上是2个循环过程:第一个循环(5-11)找到那些即将要被删除的纪录并且将他们的键值父指导一个临时的表里,然后第2个循环(16-19)根据这张表删除纪录。

0 Transaction 1 0

1 Transaction 0 0

2 VerifyCookie 0 178

3 Integer 0 0

4 OpenRead 0 3 examp

这4条语句和Insert例子里面的基本相同,打开同主数据库和临时表之间的互动通道。更改Cookie,创建一个指向主数据库的指针。注意这里打开的是读指针而不是写指针。因为这里只需要找出要符合要求的纪录,删除工作将在第15条语句后执行。

5 Rewind 0 12

开始一个循环,并且规定跳出位置

6 Column 0 1

7 Integer 50 0 50

8 Ge 1 11

第6条语句将examp表的一个元素的第二列压入堆栈

第7条语句将一个整数50 压入堆栈

第8条语句比较栈顶部两个元素的大小,如果是栈顶〉=次栈顶,则转向P2所指的语句(11),否则执行下一条语句

9 Recno 0 0

10 ListWrite 0 0

第9条语句将当前行的前4个BYTES(就是该条记录的键值)作为一个整数压入堆栈,

第10条语句将这个整数放入临时的表中并且将其出栈。

这两条语句进行的是整个循环当中最重要的工作:将符合要求的数据的键值写入临时表当中。在执行万前10条语句之后,堆栈应该是空的。

11 Next 0 6

12 Close 0 0

检索完整个数据表之后关闭连接。

13 ListRewind 0 0

第13条语句整理临时表,使指针回到表头,准备进行第2次循环。

14 Integer 0 0

15 OpenWrite 0 3

这个不用解释了

16 ListRead 0 20

17 NotExists 0 19

18 Delete 0 1

19 Goto 0 16

这个循环过程执行真正的删除。他和之前的例子的循环有所不同。

第16条语句 ListRead 在失败时跳转至P2所指的语句(20),而Next 在判断成功是跳转,所以把ListRead放在循环的开始而Next放在循环的末尾。有点类似于 while(){},和do{}while()的区别。ListRead从临时表当中读出一个元素并且把它压入堆栈。如果这项操作是成功的,则继续执行下面的语句,如果不成功则跳转至P2(20,循环之后的第一条语句)。

第17条语句NotExists将栈顶元素取出并且转换成整型数。如果一个以这个数为键值得数据项在P1所指的数据表当中不存在,则跳转到 P2.如果数据项存在,则执行下一条语句,这中情况下,开始新的循环。至于为什么P2是循环的结束而不是循环的开始,parser的作者解释说是因为它没有做到最大优化.

第18条语句是删除工作的执行者,他将刚才压入堆栈的键值取出并且删除对应的纪录。

第19条语句开始新的循环。

20 ListReset 0 0

21 Close 0 0

22 Commit 0 0

23 Halt 0 0

这个代码块负责关闭VDBE。

第20条语句清空临时表。

21-23不用多说。

索引

在数据检索当中,如果所有的数据都被检索一遍,要面对大量的数据和I/O操作,为的只是很少的结果。这样的查询可能花费大量的时间。为了加速查询,就要用到索引。

CREATE INDEX examp_idx1 ON examp(two);

VDBE解析后的代码如下

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

注意每个数据库都有一个主表,主表存放各个数据表的地指和对应的指针。创建索引时,我们必须向主表当中添加新的元素。这项操作在语句3-15当中解决。这个过程类似于INSERT 语句的过程,不再多说。我们关心的问题是如何将新建的索引和数据建立连接。这个问题在豫剧16-23当中解决。

16 Integer 0 0

17 OpenRead 2 3 examp

首先,我们打开即将要被添加索引的表,为了给这个表创建索引,我们必须知道表里有些什么。这里

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有