我的位置: 主页 > 学习专区 > 数据库技术 > > 浅谈SQlite 查询处理及优化

浅谈SQlite 查询处理及优化

2013-08-07 17:10北大青鸟锦江天府学院
[导读] 查询处理及优化是关系数据库得以流行的根本原因,也是关系数据库系统最核心的技术之一。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结构体,并根据该结构,进行接下来语义分析及生成执行计划等工作。

 

来看个例子,这个例子贯穿于全文:

代码

 来看看该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的条件。该情况实际上也是对表进行的扫描。可以说,Sqliterowid为聚簇索引。

 

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

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

代码

 

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

复制代码
代码
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虽然简单,但是,它却五脏俱全。通过它,我们能够观察到数据库系统内部的一些东西,而这些东西是有益处的。

热点专题
>>
相关文章推荐
>>
www.028bdqn.com/" title="北大青鸟证书" class="tagc1" target="_blank">北大青鸟证书 北大青鸟学历 华为 集体 班好 凤凰山 一峰 红树 林骑行 成功者 云景 清远北大青鸟 网页制作 文天祥 惠州北大青鸟 河源北大青鸟 梁*伟 秦*政 温*典 许*灿 珠海北大青鸟 林*涛 李*军 罗* 陈*标 雷* 王*轩 张*兴 温*华 苏*胜 廖*军 徐*凝 陈*昌