SQLite 查询处理及优化

朴灿烈づ我的快乐病毒、 2022-07-26 12:23 226阅读 0赞

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

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

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

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  \*/   
\};

![复制代码][copycode.gif]

该结构体比较简单，但要注意几个字段。pEList输出结果列的语法树；pSrc为FROM子句语法树；pWhere为WHERE部分的语法树。

select语法分析在最终在sqlite3SelectNew中完成：

![ContractedBlock.gif][] 代码

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

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

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

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列,写到r1  
 13  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到r3  
 20  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

![复制代码][copycode.gif]

来看看该SQL语句生成的语法树：

FROM部分：  
第一个表项：  
![sqlite10-1.JPG][]

表名zName =”stduents”，zAlias=”s”，jointype = 0。  
第二个表项：  
![sqlite10-2.JPG][]

注意，jointype = 1(JT\_INNER)。  
第三个表项：  
![sqlite10-3.JPG][]

注意，jointype = 1(JT\_INNER)。  
WHERE部分(结点类型为Expr的一棵二叉树)：

![sqlite10-4.JPG][]

2、生成执行计划(语法树到OPCODE)

Select的执行计划在sqlite3Select中完成：

int  sqlite3Select(  
Parse  \* pParse,  /\*  The parser context  \*/   
Select  \* p,  /\*  SELECT语法树  \*/   
SelectDest  \* pDest  /\*  如果处理结果集  \*/   
)

其实，该函数先对SQL语句进行语义分析，然后再进行优化，最后生成执行计划。

对于上面要SQL语句，生成的执行计划(虚拟机opcode)大致分成5部分，前4部分都在sqlite3Select()中生成，它主要调用了以下几个函数：

![sqlite10-5.JPG][]

其中(1)、(2)在sqlite3WhereBegin()中生成，(2)即所谓的查询优化处理；(3)在 selectInnerLoop中生成；(4)在sqlite3WhereEnd中生成；(5)是sqlite3FinishCoding中完成的。后续章节，我将分别分析每一部分。

3、sqlite3WhereBegin  
该函数是查询处理最为核心的函数，它主要完成where部分的优化及相关opcode的生成。

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

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  \*/   
)

![复制代码][copycode.gif]

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

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

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

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  /

![复制代码][copycode.gif]

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

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

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

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

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

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

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

![ContractedBlock.gif][] 代码

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

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

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

![复制代码][copycode.gif]

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

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

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

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

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

![复制代码][copycode.gif]

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

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

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

![复制代码][copycode.gif]

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

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

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  \*/   
)

![复制代码][copycode.gif]

codeOneLoopStart针对5种不同的查询策略，生成各自不同的opcode:

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

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 \{  // 全表扫描   
 ...  
\}

![复制代码][copycode.gif]

先看全表扫描：

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

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

![复制代码][copycode.gif]

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

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

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  \*/   
)

![复制代码][copycode.gif]

函数的参数注释得已经很详细了，不再多说。该函数的主要工作就是输出pCost，它包含查询策略信息及相应的代价。  
核心算法如下：

![复制代码][copycode.gif]

![ExpandedBlockStart.gif][] 代码

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

![复制代码][copycode.gif]

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

后记：

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

[copycode.gif]: /images/20220724/d53bf5a228164d5198de0ce7a19a7346.png
[ExpandedBlockStart.gif]: /images/20220724/43cbb10dfce14ee58a53cbbd8bfa10af.png
[ContractedBlock.gif]: /images/20220724/187506a58c014202aba7502164f83b2c.png
[sqlite10-1.JPG]: /images/20220724/fdb2a0aedbfb466986803e69e6b3f9cf.png
[sqlite10-2.JPG]: /images/20220724/34dda9e4e05947b28a79b9836874e44e.png
[sqlite10-3.JPG]: /images/20220724/ed81081526a64b2eb769d073fe07d3f5.png
[sqlite10-4.JPG]: /images/20220724/5a99ebb44e2748f8a00e20749154aecc.png
[sqlite10-5.JPG]: /images/20220724/b879788f145b402e928d935a2d1288b1.png