浅谈SQLite查询处理及优化

浅谈SQLite——查询处理及优化查询处理及优化是关系数据库得以流行的根本原因，也是关系数据库系统最核心的技术之一。SQLite的查询处理模块非常的精致，而且很容易移植到不支持SQL的存储引擎，BerkeleyDB最新的版本已经将其完整的移植过来。本文将简要的讨论一下SQLite的查询处理及优化。查询处理一般来说，包括词法分析、语法分析、语义分析、生成执行计划以及计划的执行几个部分。SQLite的词法分析器是手工写的，语法分析器由Lemon生成，语义分析主要的进行语义方面的一些检查，比如table是否存在等。而执行计划的生成及执行是最核心的两部分，也是相对比较复杂、有点技术含量的东西。SQLite的执行计划采用了虚拟机的思想，实际上，这种基于虚拟机的思想并非SQLite所独有，但是，SQLite将其发挥到了极致，它生成的执行计划非常详细，而且很容易读(在这里，我不得不佩服D.RichardHipp在编译理论方面的功底)。1、语法分析——语法树词法分析本身比较简单，这里就不谈了。语法分析的主要任务就是对用户输入的SQL语句进行语法检查，然后生成一个包含所有信息的语法树。对于SELECT语句，这个语法树最终由结构体Select表示：代码structSelect{ExprList*pEList;/*Thefieldsoftheresult*/u8op;/*Oneof:TK_UNIONTK_ALLTK_INTERSECTTK_EXCEPT*/charaffinity;/*MakeRecordwiththisaffinityforSRT_Set*/u16selFlags;/*VariousSF_*values*/SrcList*pSrc;/*TheFROMclause*/Expr*pWhere;/*TheWHEREclause*/ExprList*pGroupBy;/*TheGROUPBYclause*/Expr*pHaving;/*TheHAVINGclause*/ExprList*pOrderBy;/*TheORDERBYclause*/Select*pPrior;/*Priorselectinacompoundselectstatement*/Select*pNext;/*Nextselecttotheleftinacompound*/Select*pRightmost;/*Right-mostselectinacompoundselectstatement*/Expr*pLimit;/*LIMITexpression.NULLmeansnotused.*/Expr*pOffset;/*OFFSETexpression.NULLmeansnotused.*/intiLimit,iOffset;/*MemoryregistersholdingLIMIT&OFFSETcounters*/intaddrOpenEphm[3];/*OP_OpenEphemopcodesrelatedtothisselect*/};该结构体比较简单，但要注意几个字段。pEList输出结果列的语法树；pSrc为FROM子句语法树；pWhere为WHERE部分的语法树。select语法分析在最终在sqlite3SelectNew中完成：Select*sqlite3SelectNew(Parse*pParse,/*Parsingcontext*/ExprList*pEList,/*whichcolumnstoincludeintheresult*/SrcList*pSrc,/*theFROMclause--whichtablestoscan*/Expr*pWhere,/*theWHEREclause*/ExprList*pGroupBy,/*theGROUPBYclause*/Expr*pHaving,/*theHAVINGclause*/ExprList*pOrderBy,/*theORDERBYclause*/intisDistinct,/*trueiftheDISTINCTkeywordispresent*/Expr*pLimit,/*LIMITvalue.NULLmeansnotused*/Expr*pOffset/*OFFSETvalue.NULLmeansnooffset*/){Select*pNew;Selectstandin;sqlite3*db=pParse-db;pNew=sqlite3DbMallocZero(db,sizeof(*pNew));assert(db-mallocFailed||!pOffset||pLimit);/*OFFSETimpliesLIMIT*/if(pNew==0){pNew=&standin;memset(pNew,0,sizeof(*pNew));}if(pEList==0){pEList=sqlite3ExprListAppend(pParse,0,sqlite3Expr(db,TK_ALL,0));}pNew-pEList=pEList;pNew-pSrc=pSrc;pNew-pWhere=pWhere;pNew-pGroupBy=pGroupBy;pNew-pHaving=pHaving;pNew-pOrderBy=pOrderBy;pNew-selFlags=isDistinct?SF_Distinct:0;pNew-op=TK_SELECT;pNew-pLimit=pLimit;pNew-pOffset=pOffset;assert(pOffset==0||pLimit!=0);pNew-addrOpenEphm[0]=-1;pNew-addrOpenEphm[1]=-1;pNew-addrOpenEphm[2]=-1;if(db-mallocFailed){clearSelect(db,pNew);if(pNew!=&standin)sqlite3DbFree(db,pNew);pNew=0;}returnpNew;}它主要就是将之前得到的各个子语法树汇总到Select结构体，并根据该结构，进行接下来语义分析及生成执行计划等工作。来看个例子，这个例子贯穿于全文：代码来看看该SQL语句生成的语法树：FROM部分：第一个表项：表名zName=”stduents”，zAlias=”s”，jointype=0。第二个表项：注意，jointype=1(JT_INNER)。第三个表项：注意，jointype=1(JT_INNER)。WHERE部分(结点类型为Expr的一棵二叉树)：2、生成执行计划(语法树到OPCODE)Select的执行计划在sqlite3Select中完成：intsqlite3Select(Parse*pParse,/*Theparsercontext*/Select*p,/*SELECT语法树*/SelectDest*pDest/*如果处理结果集*/)其实，该函数先对SQL语句进行语义分析，然后再进行优化，最后生成执行计划。对于上面要SQL语句，生成的执行计划(虚拟机opcode)大致分成5部分，前4部分都在sqlite3Select()中生成，它主要调用了以下几个函数：其中(1)、(2)在sqlite3WhereBegin()中生成，(2)即所谓的查询优化处理；(3)在selectInnerLoop中生成；(4)在sqlite3WhereEnd中生成；(5)是sqlite3FinishCoding中完成的。后续章节，我将分别分析每一部分。3、sqlite3WhereBegin该函数是查询处理最为核心的函数，它主要完成where部分的优化及相关opcode的生成。代码WhereInfo*sqlite3WhereBegin(Parse*pParse,/*Theparsercontext*/SrcList*pTabList,/*Alistofalltablestobescanned*/Expr*pWhere,/*TheWHEREclause*/ExprList**ppOrderBy,/*AnORDERBYclause,orNULL*/u16wctrlFlags/*OneoftheWHERE_*flagsdefinedinsqliteInt.h*/)pTabList是由分析器对FROM部分生成的语法树，它包含FROM中表的信息；pWhere是WHERE部分的语法树，它包含WHERE中所有表达式的信息；ppOrderBy对应ORDERBY子句(暂不考虑)。Sqlite的查询优化做得简单又精致。在一个简单的sqlite3WhereBegin函数中，完成所有的优化处理。查询优化的基本理念就是嵌套循环(nestedloop)，select语句的FROM子句的每个表对应一层循环(INSERT和UPDATE对应只有一个表SELECT语句)。例如，SELECT*FROMt1,t2,t3WHERE...;进行如下操作：代码foreachrow1int1do\Codegeneratedforeachrow2int2do|--bysqlite3WhereBegin()foreachrow3int3do/...end\Codegeneratedend|--bysqlite3WhereEnd()end/而对于每一层的优化，基本的理念就是对于该层循环的表，分析WHERE子句中是否有表达式能够使用其索引。Sqlite有三种基本的扫描策略：(1)全表扫描，这种情况通常出现在没有WHERE子句时；(2)基于索引扫描，这种情况通常出现在表有索引，而且WHERE中的表达式又能够使用该索引的情况；(3)基本rowid的扫描，这种情况通常出现在WHERE表达式中含有rowid的条件。该情况实际上也是对表进行的扫描。可以说，Sqlite以rowid为聚簇索引。第一种情况比较简单，第三种情况与第二种情况没有什么本质的差别。所以，这里只对第二种情况进行详细讨论。先来看看sqlite3WhereBegin的代码(去掉了一些无关紧要的代码)：代码优化部分的代码的基本的算法如下：代码foreachlevelinall_levelsbestPlan.rCost=SQLITE_BIG_DBLforeachtableintablesthatnothandled{计算where中表达式能使用其索引的策略及代价rCostIf(sCost.rCostbestPlan.rCost)bestPlan=sCost}level.plan=bestPlan该算法本质上是一个贪婪算法(greedyalgorithm)。bestBtreeIndex是某个表针对where子句中的表达式分析查询策略的核心函数，后面再讨论。对于我们的例子，经过上面的优化处理后，得到的查询策略分3层循环，最外层是students表，全表扫描；中间层是sc表，利用索引sqlite_autoindex_sc_1，即sc的key对应的索引；内层是course表，利用索引sqlite_autoindex_course_1。下面，开始生成(1)、(2)两部分的opcode，其中(1)由以下几行代码生成：代码1//生成打开表的指令2if((pLevel-plan.wsFlags&WHERE_IDX_ONLY)==03&&(wctrlFlags&WHERE_OMIT_OPEN)==0){4//pTabItem-iCursor为表对应的游标下标5intop=pWInfo-okOnePass?OP_OpenWrite:OP_OpenRead;6sqlite3OpenTable(pParse,pTabItem-iCursor,iDb,pTab,op);7}89//生成打开索引的指令10if((pLevel-plan.wsFlags&WHERE_INDEXED)!=0){11Index*pIx=pLevel-plan.u.pIdx;12KeyInfo*