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

核心提示：查询处理及优化是关系数据库得以流行的根本原因，也是关系数据库系统最核心的技术之一，浅谈SQLite——查询处理及优化，SQLite的查询处理模块非常的精致，而且很容易移植到不支持 SQL的存储引擎，语法分析的主要任务就是对用户输入的SQL语句进行语法检查，然后生成一个包含所有信息的语法树，Berkeley DB最新的版

查询处理及优化是关系数据库得以流行的根本原因，也是关系数据库系统最核心的技术之一。SQLite的查询处理模块非常的精致，而且很容易移植到不支持 SQL的存储引擎，Berkeley DB最新的版本已经将其完整的移植过来。本文将简要的讨论一下SQLite的查询处理及优化。

查询处理一般来说，包括词法分析、语法分析、语义分析、生成执行计划以及计划的执行几个部分。SQLite的词法分析器是手工写的，语法分析器由 Lemon生成，语义分析主要的进行语义方面的一些检查，比如table是否存在等。而执行计划的生成及执行是最核心的两部分，也是相对比较复杂、有点技术含量的东西。SQLite的执行计划采用了虚拟机的思想，实际上，这种基于虚拟机的思想并非SQLite所独有，但是，SQLite将其发挥到了极致，它生成的执行计划非常详细，而且很容易读(在这里，我不得不佩服D. Richard Hipp在编译理论方面的功底)。

1、语法分析——语法树

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

struct　Select　{
　　ExprList　*pEList;　　　　　　/*　The　fields　of　the　result　*/
　　u8　op;　　　　　　　　　　　　　　　　　/*　One　of:　TK_UNION　TK_ALL　TK_INTERSECT　TK_EXCEPT　*/
　　char　affinity;　　　　　　　　　/*　MakeRecord　with　this　affinity　for　SRT_Set　*/
　　u16　selFlags;　　　　　　　　　　/*　Various　SF_*　values　*/
　　SrcList　*pSrc;　　　　　　　　　/*　The　FROM　clause　*/
　　Expr　*pWhere;　　　　　　　　　　/*　The　WHERE　clause　*/
　　ExprList　*pGroupBy;　　　　/*　The　GROUP　BY　clause　*/
　　Expr　*pHaving;　　　　　　　　　/*　The　HAVING　clause　*/
　　ExprList　*pOrderBy;　　　　/*　The　ORDER　BY　clause　*/
　　Select　*pPrior;　　　　　　　　/*　Prior　select　in　a　compound　select　statement　*/
　　Select　*pNext;　　　　　　　　　/*　Next　select　to　the　left　in　a　compound　*/
　　Select　*pRightmost;　　　　/*　Right-most　select　in　a　compound　select　statement　*/
　　Expr　*pLimit;　　　　　　　　　　/*　LIMIT　expression.　NULL　means　not　used.　*/
　　Expr　*pOffset;　　　　　　　　　/*　OFFSET　expression.　NULL　means　not　used.　*/
　　int　iLimit,　iOffset;　　　/*　Memory　registers　holding　LIMIT　&　OFFSET　counters　*/
　　int　addrOpenEphm[3];　　　/*　OP_OpenEphem　opcodes　related　to　this　select　*/
};