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

发布时间：2020-12-12 23:57:46 所属栏目：百科来源：网络整理

导读：转载文章出处：http://www.cnblogs.com/hustcat/archive/2010/06/23/1762987.html 技术博客：http://www.cnblogs.com/hustcat/category/175618.html 查询处理及优化是关系数据库得以流行的根本原因，也是关系数据库系统最核心的技术之一。SQLite的查询处理模

转载文章出处：http://www.cnblogs.com/hustcat/archive/2010/06/23/1762987.html

技术博客：http://www.cnblogs.com/hustcat/category/175618.html

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

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

代码 struct Select{
ExprList * pEList; /* Thefieldsoftheresult */
u8op; Oneof:TK_UNIONTK_ALLTK_INTERSECTTK_EXCEPT */
char affinity; 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. int iLimit,iOffset; MemoryregistersholdingLIMIT&OFFSETcounters int addrOpenEphm[ 3 ]; OP_OpenEphemopcodesrelatedtothisselect */
};

该结构体比较简单，但要注意几个字段。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中完成：

int sqlite3Select(
Parse * pParse, /* Theparsercontext */
Select * p,0)">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,0)">Alistofalltablestobescanned */
Expr * pWhere,0)">*/
ExprList ** ppOrderBy,0)">AnORDERBYclause,orNULL */
u16wctrlFlags OneoftheWHERE_*flagsdefinedinsqliteInt.h */
)

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

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

代码 foreach row1 in t1 do Codegenerated
foreach row2 in t2 do |-- bysqlite3WhereBegin()
foreach row3 in t3 do /
...
endCodegenerated
end |-- bysqlite3WhereEnd()
end /

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

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

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

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

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

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

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

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

代码 foreach level in all_levels
bestPlan.rCost = SQLITE_BIG_DBL
foreach table in tablesthatnothandled
{
计算where中表达式能使用其索引的策略及代价rCost
If(sCost.rCost < bestPlan.rCost)
bestPlan = sCost
}
level.plan = bestPlan

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

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

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

代码 1 // 生成打开表的指令
2 if ((pLevel -> plan.wsFlags & WHERE_IDX_ONLY) == 0
3 && (wctrlFlags & WHERE_OMIT_OPEN) == 0 ){
4 pTabItem->iCursor为表对应的游标下标 5 int op = pWInfo -> okOnePass ? OP_OpenWrite:OP_OpenRead;
6 sqlite3OpenTable(pParse,pTabItem -> iCursor,iDb,pTab,op);
7 }
8
9 生成打开索引的指令 10 if ((pLevel -> plan.wsFlags & WHERE_INDEXED) != 11 Index * pIx = pLevel -> plan.u.pIdx;
12 KeyInfo * pKey = sqlite3IndexKeyinfo(pParse,pIx);
13
14 int iIdxCur = pLevel -> iIdxCur; 索引对应的游标下标 15
16 sqlite3VdbeAddOp4(v,OP_OpenRead,iIdxCur,pIx -> tnum,
17 ( char * )pKey,P4_KEYINFO_HANDOFF);
18 VdbeComment((v, " %s " ,pIx -> zName));
19 }
20

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

代码 notReady = ~ (Bitmask) 0 ;
for (i = 0 ;i < nTabList;i ++ ){
核心代码,从最外层向最内层,为每一层循环生成opcode
notReady = codeOneLoopStart(pWInfo,i,wctrlFlags,notReady);
pWInfo -> iContinue = pWInfo -> a[i].addrCont;
}

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

代码 static BitmaskcodeOneLoopStart(
WhereInfo * pWInfo,0)">CompleteinformationabouttheWHEREclause int iLevel,0)">WhichlevelofpWInfo->a[]shouldbecoded */
u16wctrlFlags,0)">*/
BitmasknotReady Whichtablesarecurrentlyavailable codeOneLoopStart针对5种不同的查询策略，生成各自不同的opcode:

代码 if (pLevel -> plan.wsFlags & WHERE_ROWID_EQ){ rowid的等值查询
...
} else if (pLevel -> plan.wsFlags & WHERE_ROWID_RANGE){ rowid的范围查询
...
使用索引的等值/范围查询
} if (pLevel -> plan.wsFlags & (WHERE_COLUMN_RANGE | WHERE_COLUMN_EQ)){
...
} if (pLevel -> plan.wsFlags & WHERE_MULTI_OR){ or else { 全表扫描
...
}

先看全表扫描：

代码 static const u8aStep[] = {OP_Next,OP_Prev};
2 const u8aStart[] = {OP_Rewind,OP_Last};
3 pLevel -> op = aStep[bRev];
4 pLevel -> p1 = iCur;
5 pLevel -> p2 = 1 + sqlite3VdbeAddOp2(v,aStart[bRev],iCur,addrBrk); 生成OP_Rewind/OP_Last指令 6 pLevel -> p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
7

非常简单，对于我们的例子，最外层循环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、是否需要访问索引和原表。

代码 void bestBtreeIndex(
Parse * pParse,0)">Theparsingcontext */
WhereClause * pWC,255)">struct SrcList_item * pSrc,0)">TheFROMclausetermtosearch */
BitmasknotReady,0)">Maskofcursorsthatarenotavailable */
ExprList * pOrderBy,0)">*/
WhereCost * pCost Lowestcostqueryplan 函数的参数注释得已经很详细了，不再多说。该函数的主要工作就是输出pCost，它包含查询策略信息及相应的代价。
核心算法如下：

代码遍历其所有索引,找到一个代价最小的索引 for (;pProbe;pIdx = pProbe = pProbe -> pNext){
3 const unsigned int * const aiRowEst = pProbe -> aiRowEst;
double cost; CostofusingpProbe 5 double nRow; Estimatednumberofrowsinresultset 6 int rev; TruetoscaninreverSEOrder 7 int wsFlags = 8 Bitmaskused = 0 ; 该表达式使用的表的位码 9 10 int nEq; 可以使用索引的等值表达式的个数 11 int bInEst = 如果存在xIN(SELECT...),则设为true 12 int nInMul = 1 ; 处理IN子句 13 int nBound = 100 ; 估计需要扫描的表中的元素.100表示需要扫描整个表.范围条件意味着只需要扫描表的某一部分. 14 int bSort = 是否需要排序 int bLookup = 如果对索引中的每个列,需要对应的表进行查询,则为true 16 17 DeterminethevaluesofnEqandnInMul 18 计算nEq和nInMul值 19 for (nEq = 0 ;nEq < pProbe -> nColumn;nEq ++ ){
20 WhereTerm * pTerm; AsingletermoftheWHEREclause 21 int j = pProbe -> aiColumn[nEq];
22 pTerm = findTerm(pWC,j,notReady,eqTermMask,pIdx);
23 if (pTerm == 0 ) 如果该条件在索引中找不到,则break. 24 break ;
25 wsFlags |= (WHERE_COLUMN_EQ | WHERE_ROWID_EQ);
26 if (pTerm -> eOperator & WO_IN){
27 Expr * pExpr = pTerm -> pExpr;
28 wsFlags |= WHERE_COLUMN_IN;
29 if (ExprHasProperty(pExpr,EP_xIsSelect)){ IN(SELECT...) 30 nInMul *= 25 ;
31 bInEst = 1 ;
32 } if (pExpr -> x.pList){
33 nInMul *= pExpr -> x.pList -> nExpr + 34 }
35 } if (pTerm -> eOperator & WO_ISNULL){
36 wsFlags |= WHERE_COLUMN_NULL;
37 }
38 used |= pTerm -> prereqRight; 设置该表达式使用的表的位码 39 }
40
41 计算nBound值 42 if (nEq < pProbe -> nColumn){ 考虑不能使用索引的列 43 44 if (findTerm(pWC,WO_LT | WO_LE | WO_GT | WO_GE,pIdx)){
45 WhereTerm * pTop = findTerm(pWC,WO_LT | WO_LE,128)">46 WhereTerm * pBtm = findTerm(pWC,WO_GT | WO_GE,pIdx); >=
47 48 估计范围条件的代价 49 whereRangeScanEst(pParse,pProbe,nEq,pBtm,pTop, & nBound);
50 if (pTop){
51 wsFlags |= WHERE_TOP_LIMIT;
52 used |= pTop -> prereqRight;
53 }
54 if (pBtm){
55 wsFlags |= WHERE_BTM_LIMIT;
56 used |= pBtm -> prereqRight;
57 }
58 wsFlags |= (WHERE_COLUMN_RANGE | WHERE_ROWID_RANGE);
59 }
60 } if (pProbe -> onError != OE_None){ 所有列都能使用索引 61 if ((wsFlags & (WHERE_COLUMN_IN | WHERE_COLUMN_NULL)) == 62 wsFlags |= WHERE_UNIQUE;
63 }
64 }
65
66 if (pOrderBy){ 处理orderby 67 68 && isSortingIndex(pParse,pWC -> pMaskSet,pOrderBy, & rev)
69 ){
70 wsFlags |= WHERE_ROWID_RANGE | WHERE_COLUMN_RANGE | WHERE_ORDERBY;
71 wsFlags |= (rev ? WHERE_REVERSE: 0 );
72 } else {
73 bSort = 74 }
75 }
76
77 if (pIdx && wsFlags){
78 Bitmaskm = pSrc -> colUsed; m为src使用的列的位图 79 int j;
80 for (j = 0 ;j < pIdx -> nColumn;j ++ ){
81 int x = pIdx -> aiColumn[j];
82 if (x < BMS - 1 ){
83 m &= ~ (((Bitmask) 1 ) << x); 将索引中列对应的位清0 84 85 }
86 if (m == 0 ){ 如果索引包含src中的所有列,则只需要查询索引即可. 87 wsFlags |= WHERE_IDX_ONLY;
88 } 89 bLookup = 需要查询原表 90 91 }
92
93 估计输出行数,同时考虑IN运算 94 nRow = ( double )(aiRowEst[nEq] * nInMul);
95 if (bInEst && nRow * 2 > aiRowEst[ 0 ]){
96 nRow = aiRowEst[ 0 ] / 2 ;
97 nInMul = ( int )(nRow / aiRowEst[nEq]);
98 }
99
100 代价为输出的行数+二分查找的代价 101 cost = nRow + nInMul * estLog(aiRowEst[ 0 ]);
102
103 考虑范围条件影响 104 nRow = (nRow * ( double )nBound) / ( double ) 100 ;
105 cost = (cost * ( 106
107 加上排序的代价:cost*log(cost) 108 if (bSort){
109 cost += cost * estLog(cost);
110 }
111
112 如果只查询索引,则代价减半 113 if (pIdx && bLookup == 114 cost /= ( 115 }
116
117 如果当前的代价更小 118 if (( ! pIdx || wsFlags) && cost < pCost -> rCost){
119 pCost -> rCost = cost; 代价 120 pCost -> nRow = nRow; 估计扫描的元组数 121 pCost -> used = used; 表达式使用的表的位图 122 pCost -> plan.wsFlags = (wsFlags & wsFlagMask); 查询策略标志(全表扫描,使用索引进行扫描) 123 pCost -> plan.nEq = nEq; 查询策略使用等值表达式个数 124 pCost -> plan.u.pIdx = pIdx; 查询策略使用的索引(全表扫描则为NULL) 125 126
127
128 如果SQL语句存在INDEXEDBY,则只考虑该索引 129 if (pSrc -> pIndex) 130
131 Resetmasksforthenextindexintheloop 132 wsFlagMask = ~ (WHERE_ROWID_EQ | WHERE_ROWID_RANGE);
133 eqTermMask = idxEqTermMask;
134 }
135

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

后记：

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

（编辑：李大同）

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