http://edu.codepub.com/2010/1125/27429.php
查询处理及优化是关系数据库得以流行的根本原因，也是关系数据库系统最核心的技术之一。SQLite的查询处理模块非常的精致，而且很容易移植到不支持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 */}; 该结构体比较简单，但要注意几个字段。pEList输出结果列的语法树；pSrc为FROM子句语法树；pWhere为WHERE部分的语法树。
select语法分析在最终在sqlite3SelectNew中完成：
代码 Select *sqlite3SelectNew( Parse *pParse, /* Parsing context */ ExprList *pEList, /* which columns to include in the result */ SrcList *pSrc, /* the FROM clause -- which tables to scan */ Expr *pWhere, /* the WHERE clause */ ExprList *pGroupBy, /* the GROUP BY clause */ Expr *pHaving, /* the HAVING clause */ ExprList *pOrderBy, /* the ORDER BY clause */ int isDistinct, /* true if the DISTINCT keyword is present */ Expr *pLimit, /* LIMIT value. NULL means not used */ Expr *pOffset /* OFFSET value. NULL means no offset */){ Select *pNew; Select standin; sqlite3 *db = pParse->db; pNew = sqlite3DbMallocZero(db, sizeof(*pNew) ); assert( db->mallocFailed || !pOffset || pLimit ); /* OFFSET implies LIMIT */ 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; } return pNew;}
它主要就是将之前得到的各个子语法树汇总到Select结构体，并根据该结构，进行接下来语义分析及生成执行计划等工作。
来看个例子，这个例子贯穿于全文：
代码 1 explain select s.sname,c.cname,sc.grade from students s join sc join course c on s.sid=sc.sid and sc.cid = c.cid; 2 0|Trace|0|0|0||00| 3 1|Goto|0|35|0||00| 4 //(1) 5 2|OpenRead|0|3|0|2|00|students #打开students表 6 3|OpenRead|1|7|0|3|00|sc #打开sc表 7 4|OpenRead|3|8|0|keyinfo(2,BINARY,BINARY)|00|sqlite_autoindex_sc_1 #sc的索引 8 5|OpenRead|2|5|0|2|00|course #course表 9 6|OpenRead|4|6|0|keyinfo(1,BINARY)|00|sqlite_autoindex_course_1 #course的索引10 //(2)//11 7|Rewind|0|29|0||00| #将游标p0定位到students表的第一条记录12 8|Column|0|0|1||00|students.sid #取出第0列,写到r113 9|IsNull|1|28|0||00|14 10|Affinity|1|1|0|d|00|15 11|SeekGe|3|28|1|1|00| #将游标p3定位到sc索引的>=r1的记录处16 12|IdxGE|3|28|1|1|01|17 13|IdxRowid|3|2|0||00|18 14|Seek|1|2|0||00|19 15|Column|3|1|3||00|sc.cid #读取sc.cid到r320 16|IsNull|3|27|0||00|21 17|Affinity|3|1|0|d|00|22 18|SeekGe|4|27|3|1|00| #将游标p4定位到course索引的>=r3的记录处23 19|IdxGE|4|27|3|1|01|24 20|IdxRowid|4|4|0||00|25 21|Seek|2|4|0||00|26 ///(3)//27 22|Column|0|1|5||00|students.sname #从游标p0取出第1列 (sname)28 23|Column|2|1|6||00|course.cname #从游标p2取出第1列 (cname)29 24|Column|1|2|7||00|sc.grade #从游标p1取出第2列(grade)30 25|ResultRow|5|3|0||00|31 ///(4)///32 26|Next|4|19|0||00|33 27|Next|3|12|0||00|34 28|Next|0|8|0||01|35 29|Close|0|0|0||00|36 30|Close|1|0|0||00|37 31|Close|3|0|0||00|38 32|Close|2|0|0||00|39 33|Close|4|0|0||00|40 //(5)//41 34|Halt|0|0|0||00|42 35|Transaction|0|0|0||00|43 36|VerifyCookie|0|7|0||00|44 37|TableLock|0|3|0|students|00|45 38|TableLock|0|7|0|sc|00|46 39|TableLock|0|5|0|course|00|47 40|Goto|0|2|0||00|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, /* The parser context */ 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, /* The parser context */ SrcList *pTabList, /* A list of all tables to be scanned */ Expr *pWhere, /* The WHERE clause */ ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */ u16 wctrlFlags /* One of the WHERE_* flags defined in sqliteInt.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 / Code generated foreach row2 in t2 do |-- by sqlite3WhereBegin() foreach row3 in t3 do / ... end / Code generated end |-- by sqlite3WhereEnd()end /
而对于每一层的优化，基本的理念就是对于该层循环的表，分析WHERE子句中是否有表达式能够使用其索引。
Sqlite有三种基本的扫描策略：
(1)全表扫描，这种情况通常出现在没有WHERE子句时；
(2)基于索引扫描，这种情况通常出现在表有索引，而且WHERE中的表达式又能够使用该索引的情况；
(3)基本rowid的扫描，这种情况通常出现在WHERE表达式中含有rowid的条件。该情况实际上也是对表进行的扫描。可以说，Sqlite以rowid为聚簇索引。
第一种情况比较简单，第三种情况与第二种情况没有什么本质的差别。所以，这里只对第二种情况进行详细讨论。
先来看看sqlite3WhereBegin的代码(去掉了一些无关紧要的代码)：
代码 1 /*分析where子句的所有表达式.如果表达式的形式为X <op> Y,则增加一个Y <op> X形式的虚Term,并在后面进行单独分析. 2 * */ 3 exprAnalyzeAll(pTabList, pWC); 4 5 WHERETRACE(("*** Optimizer Start *** ")); 6 //优化开始 7 for(i=iFrom=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){ 8 WhereCost bestPlan; /* Most efficient plan seen so far */ 9 Index *pIdx; /* Index for FROM table at pTabItem */10 int j; /* For looping over FROM tables */11 int bestJ = -1; /* The value of j */12 Bitmask m; /* Bitmask value for j or bestJ */13 int isOptimal; /* Iterator for optimal/non-optimal search */14 15 memset(&bestPlan, 0, 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 Bitmask mask = (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; /* True if this table should not be reordered */27 WhereCost sCost; /* Cost information from best[Virtual]Index() */28 ExprList *pOrderBy; /* ORDER BY clause for index to optimize */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¬Ready)==048 && (j==iFrom || sCost.rCost<bestPlan.rCost) 49 ){50 bestPlan = sCost;51 bestJ = j; //如果bestJ >=0,表示找到了优化的扫描策略52 }53 if( doNotReorder ) break;54 }//end for55 }//end for56 WHERETRACE(("*** Optimizer selects table %d for loop %d ", bestJ,57 pLevel-pWInfo->a));58 59 if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){//不需要进行排序操作60 *ppOrderBy = 0;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 = -1;71 }72 notReady &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);73 //该层对应的FROM的表项,即该层循环是对哪个表进行的操作.74 pLevel->iFrom = (u8)bestJ;75 76 }77 //优化结束78 WHERETRACE(("*** Optimizer Finished *** "));
优化部分的代码的基本的算法如下：
代码 foreach level in all_levels bestPlan.rCost = SQLITE_BIG_DBL foreach table in tables that not handled { 计算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)!=0 ){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, iDb,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 Bitmask codeOneLoopStart( WhereInfo *pWInfo, /* Complete information about the WHERE clause */ int iLevel, /* Which level of pWInfo->a[] should be coded */ u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */ Bitmask notReady /* Which tables are currently available */) codeOneLoopStart针对5种不同的查询策略，生成各自不同的opcode:
代码 if( pLevel->plan.wsFlags & WHERE_ROWID_EQ ){ //rowid的等值查询...}else if( pLevel->plan.wsFlags & WHERE_ROWID_RANGE ){//rowid的范围查询...//使用索引的等值/范围查询}else if( pLevel->plan.wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){...}if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){//or...}else{ //全表扫描...} 先看全表扫描：
代码 1 static const u8 aStep[] = { OP_Next, OP_Prev };2 static const u8 aStart[] = { 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、是否需要访问索引和原表。
代码 static void bestBtreeIndex( Parse *pParse, /* The parsing context */ WhereClause *pWC, /* The WHERE clause */ struct SrcList_item *pSrc, /* The FROM clause term to search */ Bitmask notReady, /* Mask of cursors that are not available */ ExprList *pOrderBy, /* The ORDER BY clause */ WhereCost *pCost /* Lowest cost query plan */) 函数的参数注释得已经很详细了，不再多说。该函数的主要工作就是输出pCost，它包含查询策略信息及相应的代价。核心算法如下：
代码 1 //遍历其所有索引,找到一个代价最小的索引 2 for(; pProbe; pIdx=pProbe=pProbe->pNext){ 3 const unsigned int * const aiRowEst = pProbe->aiRowEst; 4 double cost; /* Cost of using pProbe */ 5 double nRow; /* Estimated number of rows in result set */ 6 int rev; /* True to scan in reverse order */ 7 int wsFlags = 0; 8 Bitmask used = 0; //该表达式使用的表的位码 9 10 int nEq; //可以使用索引的等值表达式的个数 11 int bInEst = 0; //如果存在 x IN (SELECT...),则设为true 12 int nInMul = 1; //处理IN子句 13 int nBound = 100; //估计需要扫描的表中的元素. 100表示需要扫描整个表.范围条件意味着只需要扫描表的某一部分. 14 int bSort = 0; //是否需要排序 15 int bLookup = 0; //如果对索引中的每个列,需要对应的表进行查询,则为true 16 17 /* Determine the values of nEq and nInMul */ 18 //计算nEq和nInMul值 19 for(nEq=0; nEq<pProbe->nColumn; nEq++){ 20 WhereTerm *pTerm; /* A single term of the WHERE clause */ 21 int j = pProbe->aiColumn[nEq]; 22 pTerm = findTerm(pWC, iCur, 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 }else if( pExpr->x.pList ){ 33 nInMul *= pExpr->x.pList->nExpr + 1; 34 } 35 }else 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 int j = pProbe->aiColumn[nEq]; 44 if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){ 45 WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx); 46 WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, 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 }else if( pProbe->onError!=OE_None ){//所有列都能使用索引 61 if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){ 62 wsFlags |= WHERE_UNIQUE; 63 } 64 } 65 66 if( pOrderBy ){//处理order by 67 if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 68 && isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev) 69 ){ 70 wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY; 71 wsFlags |= (rev ? WHERE_REVERSE : 0); 72 }else{ 73 bSort = 1; 74 } 75 } 76 77 if( pIdx && wsFlags ){ 78 Bitmask m = 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 }else{ 89 bLookup = 1;//需要查询原表 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 * (double)nBound) / (double)100;106 107 //加上排序的代价:cost *log (cost)108 if( bSort ){109 cost += cost*estLog(cost);110 }111 112 //如果只查询索引,则代价减半113 if( pIdx && bLookup==0 ){114 cost /= (double)2;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语句存在INDEXED BY,则只考虑该索引129 if( pSrc->pIndex ) break;130 131 /* Reset masks for the next index in the loop */132 wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);133 eqTermMask = idxEqTermMask;134 }135
可见，SQLite的代价模型非常简单。而通用数据库一般是将基于规则的优化和基于代价的优化结合起来，十分复杂。
后记：
查询优化是关系数据库中最复杂的技术之一，这点我深有感触，对于SQLite这样简单的优化处理，我断断续续也差不多看了一个来月。如果你不是做DB内核开发，你会认为这些东西用处也许不会太大。但是，作为一个DBA，或者经常做数据库应用开发的程序员，如果你不理解数据库系统的执行计划，是不合格的，因为你很难写出高效的SQL语句。SQLite虽然简单，但是，它却五脏俱全。通过它，我们能够观察到数据库系统内部的一些东西，而这些东西是有益处的。本篇文章来源于：开发学院 http://edu.codepub.com 原文链接：http://edu.codepub.com/2010/1125/27429_6.php
本篇文章来源于：开发学院 http://edu.codepub.com 原文链接：http://edu.codepub.com/2010/1125/27429_5.php
