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

Sqlite 前端之家
前端之家收集整理的这篇文章主要介绍了浅谈SQLite——查询处理及优化，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

查询处理及优化是关系数据库得以流行的根本原因，也是关系数据库系统最核心的技术之一。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 * sqlite3SelectNew(
Parse * pParse, Parsingcontext */
ExprList * pEList,0)">whichcolumnstoincludeintheresult */
SrcList * pSrc,0)">theFROMclause--whichtablestoscan */
Expr * pWhere,0)">theWHEREclause */
ExprList * pGroupBy,0)">theGROUPBYclause */
Expr * pHaving,0)">theHAVINGclause */
ExprList * pOrderBy,0)">theORDERBYclause int isDistinct,0)">trueiftheDISTINCTkeywordispresent */
Expr * pLimit,0)">LIMITvalue.NULLmeansnotused */
Expr * pOffset OFFSETvalue.NULLmeansnooffset */
){
Select * pNew;
Selectstandin;
sqlite3 * db = pParse -> db;
pNew = sqlite3DbMallocZero(db,255)">sizeof ( * pNew));
assert(db -> mallocFailed || ! pOffset || pLimit); OFFSETimpliesLIMIT if (pNew == 0 ){
pNew = & standin;
memset(pNew, 0 ,255)">sizeof ( * pNew));
}
 if (pEList == 0 ){
pEList = sqlite3ExprListAppend(pParse,sqlite3Expr(db,TK_ALL,128)">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 ] = - 2 ] = - 1 ;
 if (db -> mallocFailed){
clearSelect(db,pNew);
 if (pNew !=& standin)sqlite3DbFree(db,pNew);
pNew = 0 ;
}
 return pNew;
}

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

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

1 explainselects.sname,c.cname,sc.gradefromstudentssjoinscjoincoursecons.sid=sc.sid and sc.cid=c.cid ;
 2 0 |Trace| 0 | 0 || 00 |
 3 1 |Goto| 35 | 4 //////////////////////////( 1 )////////////////////////////
 5 2 |OpenRead| 3 | 2 | 00 |students#打开students表
 6 3 |OpenRead| 1 | 7 | 00 |sc#打开sc表
 7 4 |OpenRead| 8 | 0 |keyinfo( 2 ,BINARY,BINARY)| 00 |sqlite_autoindex_sc_1#sc的索引
 8 5 |OpenRead| 5 | 00 |course#course表
 9 6 |OpenRead| 4 | 6 | 1 ,128)">00 |sqlite_autoindex_course_1#course的索引
 10 //////////////////////////( 2 )//////////////////////////////
 11 7 |Rewind| 29 | 00 |#将游标p0定位到students表的第一条记录
 12 8 |Column| 1 || 00 |students.sid#取出第0列,写到r1
 13 9 |IsNull| 28 | 14 10 |Affinity| 0 |d| 15 11 |SeekGe| 00 |#将游标p3定位到sc索引的>=r1的记录处
 16 12 |IdxGE| 01 |
 17 13 |IdxRowid| 18 14 |Seek| 19 15 |Column| 3 || 00 |sc.cid#读取sc.cid到r3
 20 16 |IsNull| 27 | 21 17 |Affinity| 22 18 |SeekGe| 00 |#将游标p4定位到course索引的>=r3的记录处
 23 19 |IdxGE| 24 20 |IdxRowid| 25 21 |Seek| 26 ///////////////////////////( 3 )//////////////////////////////
 27 22 |Column| 5 || 00 |students.sname#从游标p0取出第1列(sname)
 28 23 |Column| 6 || 00 |course.cname#从游标p2取出第1列(cname)
 29 24 |Column| 7 || 00 |sc.grade#从游标p1取出第2列(grade)
 30 25 |ResultRow| 31 ///////////////////////////( 4 )///////////////////////////////
 32 26 |Next| 19 | 33 27 |Next| 12 | 34 28 |Next| 35 29 |Close| 36 30 |Close| 37 31 |Close| 38 32 |Close| 39 33 |Close| 40 //////////////////////////( 5 )//////////////////////////////////
 41 34 |Halt| 42 35 |Transaction| 43 36 |VerifyCookie| 44 37 |TableLock| 0 |students| 45 38 |TableLock| 0 |sc| 46 39 |TableLock| 0 |course| 47 40 |Goto| 48

来看看该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,0)">Theparsercontext */
SrcList * pTabList,0)">Alistofalltablestobescanned */
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 /
...
end\Codegenerated
end |-- bysqlite3WhereEnd()
end /

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

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

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

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

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

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

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

@H_404_1459@
1 分析where子句的所有表达式.如果表达式的形式为X<op>Y,则增加一个Y<op>X形式的虚Term,并在后面进行单独分析.
 * 3 exprAnalyzeAll(pTabList,pWC);
 4
5 WHERETRACE(( " ***OptimizerStart***\n " ));
 6 // 优化开始
7 for (i = iFrom = = pWInfo -> a;i < nTabList;i ++ ,pLevel ++ ){
 8 WhereCostbestPlan; Mostefficientplanseensofar 9 Index * pIdx; IndexforFROMtableatpTabItem 10 int j; ForloopingoverFROMtables 11 int bestJ = - 1 ; Thevalueofj 12 Bitmaskm; BitmaskvalueforjorbestJ 13 int isOptimal; Iteratorforoptimal/non-optimalsearch 14
15 memset( & bestPlan,255)">sizeof (bestPlan));
 16 bestPlan.rCost = sqlITE_BIG_DBL;
 17
18 进行两次扫描: 19 如果第一次扫描没有找到优化的扫描策略,此时,isOptimal==0,bestJ==-1,则进行第二次扫描 20 for (isOptimal = 1 ;isOptimal >= 0 && bestJ < 0 ;isOptimal -- ){
 21 第一次扫描的mask==0,表示所有表都已经准备好 22 Bitmaskmask = (isOptimal ? 0 :notReady);
 23 assert((nTabList - iFrom) > 1 || isOptimal);
 24
25 for (j = iFrom,pTabItem =& pTabList -> a[j];j < nTabList;j ++ ,pTabItem ++ ){
 26 int doNotReorder; Trueifthistableshouldnotbereordered 27 WhereCostsCost; Costinformationfrombest[Virtual]Index() 28 ExprList * pOrderBy; ORDERBYclauseforindextooptimize 29
30 对于左连接和交叉连接,不能改变嵌套的顺序 31 doNotReorder = (pTabItem -> jointype & (JT_LEFT | JT_CROSS)) != 0 ;
 32
33 if (j != iFrom && doNotReorder) 如果j==iFrom,仍要进行优化处理(此时,是第一次处理iFrom项) 34 break ;
 35 m = getMask(pMaskSet,pTabItem -> iCursor);
 36 if ((m & notReady) == 0 ){ 如果该pTabItem已经进行处理,则不需要再处理 37 if (j == iFrom)
 38 iFrom ++ ;
 39 continue ;
 40 }
 41 pOrderBy = ((i == 0 && ppOrderBy) ?* ppOrderBy: 0 );
 42
43 {
 44 对一个表(pTabItem),找到它的可用于本次查询的最好的索引,sCost返回对应的代价 45 bestBtreeIndex(pParse,pWC,pTabItem,mask,pOrderBy, & sCost);
 46 }
 47 if ((sCost.used & notReady) == 0
48 && (j == iFrom || sCost.rCost < bestPlan.rCost)
 49 ){
 50 bestPlan = sCost;
 51 bestJ = j; 如果bestJ>=0,表示找到了优化的扫描策略 52 }
 53 if (doNotReorder) 54 } endfor 55 } 56 WHERETRACE(( ***Optimizerselectstable%dforloop%d\n " ,bestJ,
 57 pLevel - pWInfo -> a));
 58
59 if ((bestPlan.plan.wsFlags & WHERE_ORDERBY) != 不需要进行排序操作 60 * ppOrderBy = 61 }
 62 设置该层选用的查询策略 63 andFlags &= bestPlan.plan.wsFlags;
 64 pLevel -> plan = bestPlan.plan;
 65
66 如果可以使用索引,则设置索引对应的游标的下标 67 if (bestPlan.plan.wsFlags & WHERE_INDEXED){
 68 pLevel -> iIdxCur = pParse -> nTab ++ ;
 69 } else {
 70 pLevel -> iIdxCur = - 71 }
 72 notReady &= ~ getMask(pMaskSet,pTabList -> a[bestJ].iCursor);
 73 该层对应的FROM的表项,即该层循环是对哪个表进行的操作. 74 pLevel -> iFrom = (u8)bestJ;
 75
76 }
 77 优化结束 78 ***OptimizerFinished***\n 79

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

代码
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)由以下几行代码生成：

代码
生成打开表的指令 if ((pLevel -> plan.wsFlags & WHERE_IDX_ONLY) == 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,128)">17 ( char * )pKey,P4_KEYINFO_HANDOFF);
 18 VdbeComment((v,0)">%s -> zName));
 19 }
 20

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

代码
notReady = ~ (Bitmask) 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 */
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 int rev; TruetoscaninreverSEOrder 7 int wsFlags = 8 Bitmaskused = 0 ; 该表达式使用的表的位码 9 int nEq; 可以使用索引的等值表达式的个数 11 int bInEst = 如果存在xIN(SELECT...),则设为true 12 int nInMul = 处理IN子句 13 int nBound = 100 ; 估计需要扫描的表中的元素.100表示需要扫描整个表.范围条件意味着只需要扫描表的某一部分. 14 int bSort = 是否需要排序 int bLookup = 如果对索引中的每个列,需要对应的表进行查询,则为true 16 17 DeterminethevaluesofnEqandnInMul 计算nEq和nInMul值 19 for (nEq = 0 ;nEq < pProbe -> nColumn;nEq ++ ){
 20 WhereTerm * pTerm; AsingletermoftheWHEREclause int j = pProbe -> aiColumn[nEq];
 22 pTerm = findTerm(pWC,j,notReady,eqTermMask,pIdx);
 23 if (pTerm == 0 ) 如果该条件在索引中找不到,则break. 24 25 wsFlags |= (WHERE_COLUMN_EQ | WHERE_ROWID_EQ);
 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 = 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 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 }
 if (pOrderBy){ 处理orderby 68 && isSortingIndex(pParse,pWC -> pMaskSet, & rev)
 69 ){
 70 wsFlags |= WHERE_ROWID_RANGE | WHERE_COLUMN_RANGE | WHERE_ORDERBY;
 71 wsFlags |= (rev ? WHERE_REVERSE: 72 } 73 bSort = 74 }
 75 }
 76
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 == 如果索引包含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虽然简单，但是，它却五脏俱全。通过它，我们能够观察到数据库系统内部的一些东西，而这些东西是有益处的。

猜你在找的Sqlite相关文章

SQLite学习笔记
安装 在Windows上安装SQLite。 访问官网下载下Precompliled Binaries for Windows的两个压...
windows上如何安装Sqlite
一、安装 下载地址：http://www.sqlite.org/download.html 将Precompiled Binaries for Wi...
【Android数据存储】SQLite使用实例(附源码)
实例: 会员信息管理 功能：1.查看数据库 2.清空数据库 3.增加会员 4.删除会员 5.更新会员 ...
SQLite数据库管理
SQLite3常用命令
加密你的SQLite
关于SQLite SQLite是一个轻量的、跨平台的、开源的数据库引擎，它的在读写效率、消耗总量、...
SQLite这么娇小可爱，不多了解点都不行啊
在我眼里，MySQL和Oracle是这样的 而SQLite在是这样的 所以这么萌的数据库，我真的应该多了...
SQLite这么娇小可爱，不多了解点都不行啊
在我眼里，MySQL和Oracle是这样的 而SQLite在是这样的 所以这么萌的数据库，我真的应该多了...
SQLite 这么娇小可爱，不多了解点都不行啊
（点击上方蓝字，快速关注我们) 作者：空之境界 网址：http://supermao.cn/sqlitezhe-yao-...
SQLITE3 使用总结
SQLITE3 使用总结 投稿：hebedich 字体：[ 增加  减小] 类型：转载 时间：2014-08-19 Sql...
MySQLMsSQLOracleSqlitePostgre SQLMariadbMongoDBNoSQLHBaseJDBC
undo日志persistent-cmysql-error-postal-codesql-match-almysql-5.6mysql-8.0database-tri安装路径系统错误data_dir丢失文件主从同步sql_mode数据库目录匿名用户character_seID归零数据库位置查询表重复字段查询字段截断日志SUSPECT7391Remote ServeLinked Serve玄学问题登录不上开启远程访问