SQLite3源程序分析_v100.doc

SQLite3源程序分析
作者：空转

本文分析的SQLite版本为3.6.18。现在已经变成3.6.20了，但本文中所涉及的内容变化不大。读者最好能下载一个源程序，然后将本文与源程序对照阅读。这样也有利于发现本文的错误，说实话吧，我写的时候是连分析带猜的，错误肯定很多。

参考文献：
1-The Definitive Guide to SQLite . Michael Owens：比较经典的SQLite著作。我边看边翻译了其中的部分内容，但翻得不好，大家还是看原文吧。
2-SQLite文件格式分析_v102 . 空转：我写的，写得特好。现在是v102版，跟前面的版本相比增加了不少背景知识，对文件格式的介绍算是很全面了。看本文之前，应该先浏览一下此参考文献。
1. SQLite3程序分析
1.1. 主程序流程
所谓“主程序”是指SQLite所提供的命令行处理程序（CLP）。通过对它的分析可以对SQLite源程序建立整体概念，比一上来就直接分析单独API的处理过程要容易。CLP的主要程序都在shell.c中。
CLP的执行流程很简单：循环接受用户输入的SQL命令，处理SQL命令。命令的执行都是调用sqlite3_exec()函数完成，也就是采用的是“执行封装的Query”的形式[1]。
程序定义了一个功能比较强大的回叫函数来处理SQL命令执行的返回结果：
static int callback(void *pArg, int nArg, char **azArg, char **azCol);
程序定义了9种回显的形式，通过一个callback_data结构来对回显参数进行配置。
1.1.1. 程序主函数
程序的main()函数在shell.c的尾部，简化后的main()函数的执行过程主要分为5步：
1. 设置回显参数
2. 取数据库文件名
3. 打开数据库
4. 循环处理SQL命令
5. 关闭数据库
如下：
int main(int argc, char **argv){
struct callback_data data; //回显参数
int rc = 0;

Argv0 = argv[0];
main_init(&data); //设置默认的回显形式

//取数据库文件名，如没有，默认为内存数据库
data.zDbFilename = argv[1];

data.out = stdout;

/* 如果数据库文件存在，则打开它。
** 如果不存在，先不打开（现在什么都不做），
** 可以防止用户因错误的输入而创建空文件。
*/
if( access(data.zDbFilename, 0)==0 ){
open_db(&data);
}

printf(
"SQLite version %s\n"
"Enter \".help\" for instructions\n"
"Enter SQL statements terminated with a \";\"\n",
sqlite3_libversion()
);
rc = process_input(&data, 0);

if( db ){ //关闭数据库
if( sqlite3_close(db)!=SQLITE_OK ){
fprintf(stderr,"error closing database: %s\n", sqlite3_errmsg(db));
}
}
return rc;
}
说明：上述函数与源程序相比做了很大的简化，去掉的部分不是不重要的，而是“可以不解释”的。实用程序的流程一般都是复杂的，SQLite也不例外。本文按照自己的主线进行介绍，只求能说明问题（自圆其说），主线之外的东西，不管重不重要，都尽量忽略。后面的函数也存在这样情况，就不再说明了。
回显参数的设置就不再介绍了，参考源程序的callback()函数和callback_data结构，有关回叫函数的使用见参考文献一。下面介绍数据库的打开过程。
1.1.2. 打开数据库
数据库文件的打开过程在SQLite的权威文档中有介绍，过程如下图：

图1-1 数据库文件的打开过程

在CLP中打开数据库，比上图又多了两层，其调用层次如下：
1-main()：
位于shell.c。
从命令行参数中得到数据库名，如果数据库文件存在，则打开它。

2-open_db()：
位于shell.c。
功能：确认数据库是否已经打开。如果已打开，则什么都不做。如果没有，则打开它。如果打开失败，输出一个错误信息。

3-sqlite3_open()：
位于main.c。
功能：打开一个数据库。
该函数中只包含对opendatabase()的调用，但调用的参数与sqlite3_open_v2()所使用的参数不同。

4-opendatabase()：
位于main.c。
功能：这个函数为sqlite3_open()和sqlite3_open16()工作，打开一个数据库。数据库文件名"zFilename"采用UTF-8编码。
先生成各类标志什么的，然后生成默认的排序法。当需要生成数据库后台驱动时，调用sqlite3BtreeFactory()。

在此函数中真正分配sqlite结构的空间：db = sqlite3MallocZero( sizeof(sqlite3) )。
在调用sqlite3BtreeFactory()之前，需要对db的一些域进行设置。

5-sqlite3BtreeFactory()
位于main.c。
功能：本函数创建到数据库BTree驱动的连接。如果zFilename是文件名，则打开并使用它。
如果zFilename是":memory:"，则使用内存数据库（在连接断开时释放）。
如果zFilename为空且数据库是虚拟（virtual）的，则只是暂时使用，在连接断开时被删除。
虚拟数据库可以是磁盘文件或就在内存中，由sqlite3TempInMemory()函数来决定是哪一种情况。

6-sqlite3BtreeOpen()：
位于btree.c。
功能：打开一个数据库文件。
由于在sqlite3BtreeFactory()中已经调用过sqlite3TempInMemory()函数，所以此处逻辑稍简单了一些。
zFilename是数据库文件名。如果zFilename为空，创建一个具有随机文件名的数据库，这个数据库会在调用sqlite3BtreeClose()时被删除。
如果zFilename是":memory:"，创建内存数据库，并在关闭时被释放。
如果此Btree是共享缓冲区的候选者，则尝试寻找一个已存在的BtShared来共享。（参本文后面关于内存数据结构的介绍）
如果不是共享缓冲区的候选者或未找到已存在的BtShared，则调用sqlite3PagerOpen()函数打开文件。
文件打开之后，调用sqlite3PagerReadFileheader()来读文件头中的配置信息。

7-sqlite3PagerOpen()：
位于pager.c。
功能：分配并初始化一个新Pager对象，将其指针放到*ppPager。
该pager会在调用sqlite3PagerClose()时被释放。
zFilename参数是要打开的数据库文件的路径。
如果zFilename为空，创建随机文件名的文件。
如果zFilename为":memory:"，所有信息都放到缓冲区中，不会被写入磁盘。这用来实现内存数据库。
如果pager对象已分配且指定文件打开成功，返回SQLITE_OK并将*ppPager指向新pager对象。
如果有错误发生，*ppPager置空并返回错误代码。
执行过程是：先申请空间，再调用sqlite3OsOpen()打开文件（如果需要），再根据打开的文件设置内存。

8-sqlite3OsOpen()：
位于os.c。
功能：打开一个文件，与具体的操作系统无关。
是一种VFS封装。VFS的意思是"virtual file system"，虚拟文件系统。
本函数只有几条语句，只有一条关键语句：
rc = pVfs->xOpen(pVfs, zPath, pFile, flags & 0x7f1f, pFlagsOut);
对于Win32操作系统，该语句实际调用的是winOpen()函数。

9-winOpen()：
位于os_win.c。
功能：打开一个Windows操作系统文件。
先将文件名转换为操作系统所使用的编码。再设置一系列参数。
最终调用操作系统函数CreateFileA()打开文件。

10-CreateFileA()：
位于WINBASE.H。
功能：
打开文件名所指定的文件。如果文件不存在，则创建。
1.1.3. 循环处理SQL命令
SQL命令的处理是由process_input()函数完成的。该函数还完成”.”命令的处理，这我们就不管了。简化后的process_input()函数如下：
static int process_input(struct callback_data *p, FILE *in){
while( 1 ){
zLine = one_input_line(zSql, in);
if( zLine && zLine[0]=='.' && nSql==0 ){
rc = do_meta_command(zLine, p);
continue;
}
rc = sqlite3_exec(p->db, zSql, callback, p, &zErrMsg);
if( rc || zErrMsg ){
处理出错信息;
}
}
return errCnt;
}
这么简化应该就不用解释了。
1.2. SQL命令编译与执行的过程
1.2.1. sqlite3_exec()函数
函数sqlite3_exec()位于文件legacy.c的尾部，其函数头为：
int sqlite3_exec(
sqlite3 *db, /* 一个打开的数据库连接 */
const char *zSql, /* 要执行的SQL语句 */
sqlite3_callback xCallback, /* 回叫函数 */
void *pArg, /* 传递给xCallback()的第一个参数 */
char **pzErrMsg /* 将错误信息写到*pzErrMsg中 */
)
sqlite3_exec()函数一次可以执行多条SQL命令。执行完成后返回一个SQLITE_ success/failure代码，还会将错误信息写到*pzErrMsg中。如果SQL是查询，查询结果中的每一行都会调用xCallback()函数。pArg为传递给xCallback()的第一个参数。如果xCallback==NULL，即使对查询命令也没有回叫调用。
sqlite3_exec()函数的实现体现了一个典型的、实用的SQL语句处理过程，我认为对应用程序的开发很有借鉴意义，所以就不过多简化了，去掉一些测试代码，增加一些注释，源程序基本如下：
int sqlite3_exec(
sqlite3 *db, /* 一个打开的数据库连接 */
const char *zSql, /* 要执行的SQL语句 */
sqlite3_callback xCallback, /* 回叫函数 */
void *pArg, /* 传递给xCallback()的第一个参数 */
char **pzErrMsg /* 将错误信息写到*pzErrMsg中 */
){
int rc = SQLITE_OK; /* 返回码 */
const char *zLeftover; /* 未处理的SQL串尾部。zSql中可能包含多个SQL
语句，一次处理一个，此变量为剩下的还未处理的
语句。 */
sqlite3_stmt *pStmt = 0; /* 当前SQL语句（对象） */
char **azCols = 0; /* 结果字段(s)的名称 */
int nRetry = 0; /* 重试的次数 */
int callbackIsInit; /* 如果初始化了回叫函数，为true */

if( zSql==0 ) zSql = "";

sqlite3Error(db, SQLITE_OK, 0); /* 清除db中的错误信息 */
while( (rc==SQLITE_OK || (rc==SQLITE_SCHEMA && (++nRetry)<2)) && zSql[0] ){
int nCol;
char **azVals = 0;

pStmt = 0;
rc = sqlite3_prepare(db, zSql, -1, &pStmt, &zLeftover);/* 编译一条语句 */
if( rc!=SQLITE_OK ){
continue;
}
if( !pStmt ){
/* 遇到注释时会执行此分支 */
zSql = zLeftover;
continue;
}

callbackIsInit = 0;
nCol = sqlite3_column_count(pStmt); /* 取字段数 */

while( 1 ){
int i;
rc = sqlite3_step(pStmt); /* 执行语句 */

/* 如果有回叫函数并且需要，则调用回叫函数 */
if( xCallback && (SQLITE_ROW==rc ||
(SQLITE_DONE==rc && !callbackIsInit
&& db->flags&SQLITE_NullCallback)) ){
/* 1-如果回叫函数未初始化，则初始化之 */
if( !callbackIsInit ){
/* 此分支只执行一次 */
azCols = sqlite3DbMallocZero(db, 2*nCol*sizeof(const char*) + 1);
if( azCols==0 ){
goto exec_out;
}
for(i=0; i<nCol; i++){
/* 取各字段的名称 */
azCols[i] = (char *)sqlite3_column_name(pStmt, i);
}
callbackIsInit = 1;
}
/* 2-如果返回的是记录 */
if( rc==SQLITE_ROW ){
azVals = &azCols[nCol];
for(i=0; i<nCol; i++){
/* 取各字段的值 */
azVals[i] = (char *)sqlite3_column_text(pStmt, i);
if( !azVals[i] && sqlite3_column_type(pStmt, i)!=SQLITE_NULL ){
db->mallocFailed = 1;
goto exec_out;
}
}
}
/* 3-调用回叫函数对返回的记录进行处理 */
if( xCallback(pArg, nCol, azVals, azCols) ){
rc = SQLITE_ABORT;
sqlite3VdbeFinalize((Vdbe *)pStmt);
pStmt = 0;
sqlite3Error(db, SQLITE_ABORT, 0);
goto exec_out;
}
}

/*
如果返回的不是记录，有两种情况：一种是到达结果记录集的结尾，
第二种是执行create table一类的不返回记录集的命令。
无论哪种情况，此处都需要“定案”。
*/
if( rc!=SQLITE_ROW ){
rc = sqlite3VdbeFinalize((Vdbe *)pStmt);
pStmt = 0;
if( rc!=SQLITE_SCHEMA ){
nRetry = 0;
zSql = zLeftover;
while( sqlite3Isspace(zSql[0]) ) zSql++;
}
break;
}
}

sqlite3DbFree(db, azCols);
azCols = 0;
}

exec_out:
if( pStmt ) sqlite3VdbeFinalize((Vdbe *)pStmt);
sqlite3DbFree(db, azCols);

rc = sqlite3ApiExit(db, rc);
/* 对出错信息进行处理 */
if( rc!=SQLITE_OK && ALWAYS(rc==sqlite3_errcode(db)) && pzErrMsg ){
int nErrMsg = 1 + sqlite3Strlen30(sqlite3_errmsg(db));
*pzErrMsg = sqlite3Malloc(nErrMsg);
if( *pzErrMsg ){
memcpy(*pzErrMsg, sqlite3_errmsg(db), nErrMsg);
}else{
rc = SQLITE_NOMEM;
sqlite3Error(db, SQLITE_NOMEM, 0);
}
}else if( pzErrMsg ){
*pzErrMsg = 0;
}

return rc;
}
1.2.2. SQL语句编译的调用层次
当调用sqlite3_prepare()函数时，编译一条SQL语句。编译过程的调用层次如下：
1- sqlite3_prepare()
在prepare.c中。
SQLite现在提供两个版本的编译API函数：遗留的和现在使用的。
在遗留版本中，原始SQL文本没有保存在编译后的语句（sqlite3_stmt结构）中，因此，如果schema发生改变，sqlite3_step()会返回SQLITE_SCHEMA。在新版本中，编译后的语句中保存原始SQL文本，当遇到schema改变时自动重新编译。
sqlite3_prepare()函数中其实只包含一条对sqlite3LockAndPrepare（）的调用语句：
rc = sqlite3LockAndPrepare(db,zSql,nBytes,0,ppStmt,pzTail);
其中第4个参数为0，表示不将SQL文本复制到ppStmt中。
空注：源程序中紧跟此函数的sqlite3_prepare_v2()函数中在调用sqlite3LockAndPrepare（）时第4个参数为1，不知与上述解释是否矛盾。

2- sqlite3LockAndPrepare()
在prepare.c中。结合注释，很简单，也很清晰。
static int sqlite3LockAndPrepare(
sqlite3 *db, /* 数据库句柄 */
const char *zSql, /* UTF-8编码的SQL语句 */
int nBytes, /* zSql的字节数 */
int saveSqlFlag, /* 如果为True，将SQL文本复制到sqlite3_stmt中。 */
sqlite3_stmt **ppStmt, /* OUT: 指向语句句柄 */
const char **pzTail /* OUT: 未处理的SQL串 */
){
int rc;
*ppStmt = 0;
if( !sqlite3SafetyCheckOk(db) ){ /* 确定db指针的合法性。 */
return SQLITE_MISUSE;
}

/* 将UTF-8编码的SQL语句zSql编译成。 */
rc = sqlite3Prepare(db, zSql, nBytes, saveSqlFlag, ppStmt, pzTail);
if( rc==SQLITE_SCHEMA ){ /* 如果遇到SCHEMA改变，定案，再编译 */
sqlite3_finalize(*ppStmt);
rc = sqlite3Prepare(db, zSql, nBytes, saveSqlFlag, ppStmt, pzTail);
}

return rc;
}

3- sqlite3Prepare()
在prepare.c中。
很长的函数，在其中调用sqlite3RunParser()函数，在给定的SQL字符串上执行分析器。
函数中，先创建Parse结构、加锁什么的，到调用sqlite3RunParser()函数时参数反而很简单了：
sqlite3RunParser(pParse, zSql, &zErrMsg);
此处zSql是一个完整的SQL语句串。
调用返回后还要做一系列处理，略。

4- sqlite3RunParser()
在tokenize.c中。
功能：在给定的SQL字符串上执行分析器。传入一个parser结构。返回一个SQLITE_状态码。如果有错误发生，将错误信息写入*pzErrMsg。
本函数内部是一个循环语句，每次循环处理一个词，根据词的类型做出不同的处理。如果是正经的词（不是空格什么的），都会调用sqlite3Parser()函数对其进行分析。

5- sqlite3Parser()
在parse.c中。
本函数为分析器主程序。
parse.c中的程序好象都是自动生成的，我反正是看不懂，也就不想看了。摘一段与兄弟们共享：
if( yypParser->yyidx < 0 || yymajor==0 ){
yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion);
yy_parse_failed(yypParser);
yymajor = YYNOCODE;
}else if( yymx!=YYERRORSYMBOL ){
YYMINORTYPE u2;
u2.YYERRSYMDT = 0;
yy_shift(yypParser,yyact,YYERRORSYMBOL,&u2);
}
1.2.3. 查询的执行过程
前一小节介绍的编译调用层次看起来还是很清晰的，但实际执行时情况要复杂得多。
比如Oracle一类的数据库，以服务器的形式供客户端访问。在服务器启动的过程中可以完成所有必要的初始化工作，在解析SQL语句时逻辑可能反而简单一些。（Oracle好像也有一些东西在第一次调用时才加载，比如Java虚拟机什么的）。
SQLite这样的数据库主要是提供API供应用程序调用，这就要求在一次单独的调用中要完成所有相关工作。另外，SQLite好像更倾向于将工作留到不得不做时再做（即使不一定非得这样），所以在SQLite中经常会看到“如果还没创建，则创建”或“如果还没打开，则打开”一类的代码。这样，程序的旁枝就会比较多，有时读起来会有一定困难。比如，在SQLite启动后第1次执行select语句时，在编译该语句的过程中需要完成schema信息内存初始化的全部工作。
下面我们就跟踪一条最简单的select语句的执行过程，从中可以了解SQLite的运行机制。首先要准备数据库。
创建一个新的数据库，创建一个表：
create table d (
id integer primary key,
name text,
loca text );
向表中插入4条记录：
insert into d (name,loca) values ('accounting','Beijing');
insert into d (name,loca) values ('research','Nanjing');
insert into d (name,loca) values ('marketing','Xining');
insert into d (name,loca) values ('operation','Baoding');
执行下列命令：
.m col
.h on
.w 4 15 3 3 3 20 3
explain select * from d;
返回结果如下：
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 2 0 00
13 TableLock 0 2 0 d 00
14 Goto 0 2 0 00
上面显示了一条select语句经编译后所生成的VDBE程序。有关VDBE程序的介绍请参考《SQLite权威指南》[1]。其中相关介绍好像有些过时，主要是由于这部分程序变化比较快，但还是很有参考价值的，反正我看了那部分内容之后，上面的程序就能看懂个大概意思了。

下面，我们就在此数据库基础上跟踪查询语句select * from d的处理过程。主要是罗列在处理过程所执行过的函数。每次调用的相关说明并不多，有的只说明关键变量的值，有的简单说明执行过程。主要是调用的太多了，实在没法对每次调用都详细说明。读者最好按上面的方法创建示例数据库，然后边看边跟踪执行。
注意：函数前面的数字表示调用的层次，而不是序号。

1-sqlite3_exec:
zSql="select * from d;"

2-sqlite3Prepare:
zSql="select * from d;"
调用sqlite3RunParser。

3-sqlite3RunParser：
每处理一个单词，调用一次sqlite3Parser。
当语句处理完毕，语句串变为""，最后一次调用sqlite3Parser。
在sqlite3Parser中，后部有一个do while循环。循环了好多遍，下面一句也执行了好多遍：
yy_reduce(yypParser,yyact-YYNSTATE);
yy_reduce中有一个大的switch语句，每次调用执行的分支不同。终于有一遍中调用了sqlite3Select。
sqlite3Select是select语句的处理主程序，在其中又经过如下调用层次（太多，这些层次就没编号了）：
sqlite3Select(在select.c中)
↓
sqlite3SelectPrep(在select.c中)
↓
sqlite3SelectExpand(在select.c中)
↓
sqlite3WalkSelect(在walker.c中)
↓
selectExpander(在select.c中)
↓
sqlite3LocateTable(在build.c中)
↓
sqlite3ReadSchema(在prepare.c中)
↓
sqlite3Init(在prepare.c中)。

4-sqlite3Init：
功能：
初始化所有数据库文件——主数据库、临时数据库和所有附加的数据库。返回成功码。如果有错误发生，将错误信息写入*pzErrMsg。
执行：
进入第一个循环语句。在循环语句中调用sqlite3InitOne。
需要注意的是程序中有一小句很重要：
db->init.busy = 1;
当db->init.busy被设为1时，就不会再有VDBE代码生成或执行。后面就可以在回叫函数中通过执行系统表中的create语句的方式为对象创建内部数据结构而又不会实际地执行这些创建语句。

5-sqlite3InitOne：
(在prepare.c中)
功能：
读入一个单独数据库文件的schema，并初始化内部的数据结构。
执行：
调用回叫函数sqlite3InitCallback，执行系统表的创建语句，为系统表创建内部数据结构。

6-sqlite3InitCallback：
(在prepare.c中)
功能：
本函数是初始化数据库时的回叫程序。
执行：
调用sqlite3_exec。

7-sqlite3_exec:
zSql=CREATE TABLE sqlite_master(
type text,
name text,
tbl_name text,
rootpage integer,
sql text
)

8-sqlite3Prepare:
zSql=CREATE TABLE sqlite_master(
type text,
name text,
tbl_name text,
rootpage integer,
sql text
)

7-sqlite3_exec:
从sqlite3Prepare返回后，执行到sqlite3_step一句。

8-sqlite3_step：
sqlite3_step是顶层函数，它调用sqlite3Step完成主要工作。

9-sqlite3Step：
此函数中调用了sqlite3VdbeExec。

10-sqlite3VdbeExec:
p->zSql=""
p->nOp=2
p->aOp:
0 21 OP_Trace
1 40 OP_Halt
可见，不执行实际的创建功能，直接返回。

9-sqlite3Step：
回到sqlite3Step后，发现sqlite3VdbeExec调用的返回结果为101。
rc又与另一个数“与”操作后，值为21，返回。

8-sqlite3_step：
rc值在其后的运算中变为101，返回。

7-sqlite3_exec:
rc!=SQLITE_ROW，不回显，退出循环。返回。

6-sqlite3InitCallback：
返回。

5-sqlite3InitOne：
继续执行，很多语句之后，遇到调用sqlite3_exec，查询系统表的内容。

6-sqlite3_exec:
zSql=SELECT name, rootpage, sql FROM 'main'.sqlite_master

7-sqlite3Prepare:
zSql=SELECT name, rootpage, sql FROM 'main'.sql