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

核心提示： 函数的参数注释得已经很详细了，不再多说，浅谈SQLite——查询处理及优化(10)，该函数的主要工作就是输出pCost，它包含查询策略信息及相应的代价，通过它，我们能够观察到数据库系统内部的一些东西，核心算法如下：1//遍历其所有索引,找到一个代价最小的索引2for(;pProbe;pIdx=p

函数的参数注释得已经很详细了，不再多说。该函数的主要工作就是输出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虽然简单，但是，它却五脏俱全。通过它，我们能够观察到数据库系统内部的一些东西，而这些东西是有益处的。