浅谈SQLite——查询处理及优化

查询处理及优化是关系数据库得以流行的根本原因，也是关系数据库系统最核心的技术之一。SQLite的查询处理模块非常的精致，而且很容易移植到不支持SQL的存储引擎，Berkeley DB最新的版本已经将其完整的移植过来。本文将简要的讨论一下SQLite的查询处理及优化。
查询处理一般来说，包括词法分析、语法分析、语义分析、生成执行计划以及计划的执行几个部分。SQLite的词法分析器是手工写的，语法分析器由Lemon生成，语义分析主要的进行语义方面的一些检查，比如table是否存在等。而执行计划的生成及执行是最核心的两部分，也是相对比较复杂、有点技术含量的东西。SQLite的执行计划采用了虚拟机的思想，实际上，这种基于虚拟机的思想并非SQLite所独有，但是，SQLite将其发挥到了极致，它生成的执行计划非常详细，而且很容易读(在这里，我不得不佩服D. Richard Hipp在编译理论方面的功底)。

1、语法分析——语法树
词法分析本身比较简单，这里就不谈了。语法分析的主要任务就是对用户输入的SQL语句进行语法检查，然后生成一个包含所有信息的语法树。对于SELECT语句，这个语法树最终由结构体Select表示：

该结构体比较简单，但要注意几个字段。pEList输出结果列的语法树；pSrc为FROM子句语法树；pWhere为WHERE部分的语法树。

select语法分析在最终在sqlite3SelectNew中完成：

它主要就是将之前得到的各个子语法树汇总到Select结构体，并根据该结构，进行接下来语义分析及生成执行计划等工作。

来看个例子，这个例子贯穿于全文：

来看看该SQL语句生成的语法树：

FROM部分：
第一个表项：

表名zName =”stduents”，zAlias=”s”，jointype = 0。
第二个表项：

注意，jointype = 1(JT_INNER)。
第三个表项：

注意，jointype = 1(JT_INNER)。
WHERE部分(结点类型为Expr的一棵二叉树)：

2、生成执行计划(语法树到OPCODE)

Select的执行计划在sqlite3Select中完成：

其实，该函数先对SQL语句进行语义分析，然后再进行优化，最后生成执行计划。

对于上面要SQL语句，生成的执行计划(虚拟机opcode)大致分成5部分，前4部分都在sqlite3Select()中生成，它主要调用了以下几个函数：

其中(1)、(2)在sqlite3WhereBegin()中生成，(2)即所谓的查询优化处理；(3)在 selectInnerLoop中生成；(4)在sqlite3WhereEnd中生成；(5)是sqlite3FinishCoding中完成的。后续章节，我将分别分析每一部分。

3、sqlite3WhereBegin
该函数是查询处理最为核心的函数，它主要完成where部分的优化及相关opcode的生成。

pTabList是由分析器对FROM部分生成的语法树，它包含FROM中表的信息；pWhere是WHERE部分的语法树，它包含WHERE中所有表达式的信息；ppOrderBy 对应ORDER BY子句(暂不考虑)。

Sqlite的查询优化做得简单又精致。在一个简单的sqlite3WhereBegin函数中，完成所有的优化处理。查询优化的基本理念就是嵌套循环(nested loop)，select语句的FROM子句的每个表对应一层循环(INSERT和UPDATE对应只有一个表SELECT语句)。例如，
SELECT * FROM t1,t2,t3 WHERE ...;
进行如下操作：

而对于每一层的优化，基本的理念就是对于该层循环的表，分析WHERE子句中是否有表达式能够使用其索引。

Sqlite有三种基本的扫描策略：

(1)全表扫描，这种情况通常出现在没有WHERE子句时；

(2)基于索引扫描，这种情况通常出现在表有索引，而且WHERE中的表达式又能够使用该索引的情况；

(3)基本rowid的扫描，这种情况通常出现在WHERE表达式中含有rowid的条件。该情况实际上也是对表进行的扫描。可以说，Sqlite以rowid为聚簇索引。

第一种情况比较简单，第三种情况与第二种情况没有什么本质的差别。所以，这里只对第二种情况进行详细讨论。

先来看看sqlite3WhereBegin的代码(去掉了一些无关紧要的代码)：

优化部分的代码的基本的算法如下：

该算法本质上是一个贪婪算法(greedy algorithm)。
bestBtreeIndex是某个表针对where子句中的表达式分析查询策略的核心函数，后面再讨论。

对于我们的例子，经过上面的优化处理后，得到的查询策略分3层循环，最外层是students表，全表扫描；中间层是sc表，利用索引sqlite_autoindex_sc_1，即sc的key对应的索引；内层是course表，利用索引sqlite_autoindex_course_1。

下面，开始生成(1)、(2)两部分的opcode，其中(1)由以下几行代码生成：

而(2)中的opcode在以下几行代码完成：

4、codeOneLoopStart
该函数根据优化分析得到的结果生成每层循环的opcode。

先看全表扫描：

非常简单，对于我们的例子，最外层循环students是全表扫描，生成指令7。

利用索引的等值/范围查询：
这种情况相对来说比较复杂(不过读懂了也很简单)，对于我们的例子，中间循环sc表，用到索引，指令8~14是对应的opcode。内层循环course表也用到索引，指令15~21是对应的opcode。(具体的含义见其注释，其生成算法见源码)。
这里不得不提到一点。在通用数据库中，连接操作会生成所谓的结果集(用临时表存储)。而sqlite不会生成中间结果集，例如，对这里的例子，它会分别对students、sc和course各分配一个游标，每次调用接口sqlite3_step时，游标根据where条件分别定位到各自的记录，然后取出查询输出列的数据，放到用于存放结果的寄存器中(见(3)中的opcode)。所以，sqlite中，必须不断调用sqlite3_step才能读取所有记录。

4、selectInnerLoop
该函数主要生成输出结果列的opcode，见(3)，比较简单。

5、sqlite3WhereEnd
主要完成嵌套循环的收尾工作的opcode生成，为每层循环生成OP_Next/OP_Prev，以及关闭表和索引游标的OP_Close，也比较简单。

6、SQLite的代价模型
最后，来看看bestBtreeIndex，在这个函数中，完成查询代价的计算以及查询策略的确定。
SQLite采用基于代价的优化。根据处理查询时CPU和磁盘I/O的代价，主要考虑以下一些因素：
A、查询读取的记录数；
B、结果是否排序(这可能会导致使用临时表)；
C、是否需要访问索引和原表。

可见，SQLite的代价模型非常简单。而通用数据库一般是将基于规则的优化和基于代价的优化结合起来，十分复杂。

后记：

查询优化是关系数据库中最复杂的技术之一，这点我深有感触，对于SQLite这样简单的优化处理，我断断续续也差不多看了一个来月。如果你不是做DB内核开发，你会认为这些东西用处也许不会太大。但是，作为一个DBA，或者经常做数据库应用开发的程序员，如果你不理解数据库系统的执行计划，是不合格的，因为你很难写出高效的SQL语句。SQLite虽然简单，但是，它却五脏俱全。通过它，我们能够观察到数据库系统内部的一些东西，而这些东西是有益处的。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!