浅谈SQLite——查询处理及优化
查询处理及优化是关系数据库得以流行的根本原因,也是关系数据库系统最核心的技术之一。SQLite的查询处理模块非常的精致,而且很容易移植到不支持SQL的存储引擎,Berkeley DB最新的版本已经将其完整的移植过来。本文将简要的讨论一下SQLite的查询处理及优化。 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)。 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 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语句)。例如, foreach row2 in t2 do |-- bysqlite3WhereBegin() foreach row3 in t3 do / ... endCodegenerated end |-- bysqlite3WhereEnd() end / 而对于每一层的优化,基本的理念就是对于该层循环的表,分析WHERE子句中是否有表达式能够使用其索引。 Sqlite有三种基本的扫描策略: (1)全表扫描,这种情况通常出现在没有WHERE子句时; (2)基于索引扫描,这种情况通常出现在表有索引,而且WHERE中的表达式又能够使用该索引的情况; (3)基本rowid的扫描,这种情况通常出现在WHERE表达式中含有rowid的条件。该情况实际上也是对表进行的扫描。可以说,Sqlite以rowid为聚簇索引。 第一种情况比较简单,第三种情况与第二种情况没有什么本质的差别。所以,这里只对第二种情况进行详细讨论。 先来看看sqlite3WhereBegin的代码(去掉了一些无关紧要的代码): 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%dn " ,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_levelsbestPlan.rCost = SQLITE_BIG_DBL foreach table in tablesthatnothandled { 计算where中表达式能使用其索引的策略及代价rCost If(sCost.rCost < bestPlan.rCost) bestPlan = sCost } level.plan = bestPlan 该算法本质上是一个贪婪算法(greedy algorithm)。 对于我们的例子,经过上面的优化处理后,得到的查询策略分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 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。 利用索引的等值/范围查询: 4、selectInnerLoop 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虽然简单,但是,它却五脏俱全。通过它,我们能够观察到数据库系统内部的一些东西,而这些东西是有益处的。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |