查询处理及优化是关系数据库得以流行的根本原因,也是关系数据库系统最核心的技术之一。sqlite的查询处理模块非常的精致,而且很容易移植到不支持sql的存储引擎,Berkeley DB最新的版本已经将其完整的移植过来。本文将简要的讨论一下sqlite的查询处理及优化。
查询处理一般来说,包括词法分析、语法分析、语义分析、生成执行计划以及计划的执行几个部分。sqlite的词法分析器是手工写的,语法分析器由Lemon生成,语义分析主要的进行语义方面的一些检查,比如table是否存在等。而执行计划的生成及执行是最核心的两部分,也是相对比较复杂、有点技术含量的东西。sqlite的执行计划采用了虚拟机的思想,实际上,这种基于虚拟机的思想并非sqlite所独有,但是,sqlite将其发挥到了极致,它生成的执行计划非常详细,而且很容易读(在这里,我不得不佩服D. Richard Hipp在编译理论方面的功底)。
1、语法分析——语法树
词法分析本身比较简单,这里就不谈了。语法分析的主要任务就是对用户输入的SQL语句进行语法检查,然后生成一个包含所有信息的语法树。对于SELECT语句,这个语法树最终由结构体Select表示:
代码
struct
Select{
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)。
第三个表项:
注意,jointype = 1(JT_INNER)。
WHERE部分(结点类型为Expr的一棵二叉树):
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
该函数是查询处理最为核心的函数,它主要完成where部分的优化及相关opcode的生成。
代码
@H_815_1301@
WhereInfo
*
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语句)。例如,
SELECT * FROM t1,t2,t3 WHERE ...;
进行如下操作:
代码
foreach
row1
in
t1
do
\Codegenerated
foreach
row2
in
t2
do
|--
bysqlite3WhereBegin()
foreach
row3
in
t3
do
/
...
end\Codegenerated
end
|--
bysqlite3WhereEnd()
end
/
而对于每一层的优化,基本的理念就是对于该层循环的表,分析WHERE子句中是否有表达式能够使用其索引。
sqlite有三种基本的扫描策略:
(1)全表扫描,这种情况通常出现在没有WHERE子句时;
(2)基于索引扫描,这种情况通常出现在表有索引,而且WHERE中的表达式又能够使用该索引的情况;
(3)基本rowID的扫描,这种情况通常出现在WHERE表达式中含有rowID的条件。该情况实际上也是对表进行的扫描。可以说,sqlite以rowID为聚簇索引。
第一种情况比较简单,第三种情况与第二种情况没有什么本质的差别。所以,这里只对第二种情况进行详细讨论。
先来看看sqlite3WhereBegin的代码(去掉了一些无关紧要的代码):
代码
优化部分的代码的基本的算法如下:
代码
foreach
level
in
all_levels
bestPlan.rCost
=
sqlITE_BIG_DBL
foreach
table
in
tablesthatnothandled
{
计算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
//
生成打开表的指令
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)
!=
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,
17
(
char
*
)pKey,P4_KEYINFO_HANDOFF);
18
VdbeComment((v,0)">"
%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
BitmaskcodeOneLoopStart(
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。
利用索引的等值/范围查询:
这种情况相对来说比较复杂(不过读懂了也很简单),对于我们的例子,中间循环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、是否需要访问索引和原表。
代码
voID
bestBtreeIndex(
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
6
int
rev;
TruetoscaninreverSEOrder
7
int
wsFlags
=
8
Bitmaskused
=
0
;
该表达式使用的表的位码
9
10
int
nEq;
可以使用索引的等值表达式的个数
11
int
bInest
=
如果存在xIN(SELECT...),则设为true
12
int
nInMul
=
1
;
处理IN子句
13
int
nBound
=
100
;
估计需要扫描的表中的元素.100表示需要扫描整个表.范围条件意味着只需要扫描表的某一部分.
14
int
bSort
=
是否需要排序
int
bLookup
=
如果对索引中的每个列,需要对应的表进行查询,则为true
16
17
DeterminethevaluesofnEqandnInMul
18
计算nEq和nInMul值
19
for
(nEq
=
0
;nEq
<
pProbe
->
nColumn;nEq
++
){
20
WhereTerm
*
pTerm;
AsingletermoftheWHEREclause
21
int
j
=
pProbe
->
aiColumn[nEq];
22
pTerm
=
findTerm(pWC,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
=
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
44
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
}
65
66
if
(pOrderBy){
处理orderby
67
68
&&
isSortingIndex(pParse,pWC
->
pMaskSet,pOrderBy,
&
rev)
69
){
70
wsFlags
|=
WHERE_ROWID_RANGE
|
WHERE_ColUMN_RANGE
|
WHERE_ORDERBY;
71
wsFlags
|=
(rev
?
WHERE_REVERSE:
0
);
72
}
else
{
73
bSort
=
74
}
75
}
76
77
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
==
0
){
如果索引包含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
}