woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

SQLite的查询优化

  SQLite是个典型的嵌入式DBMS,它有很多优点,它是轻量级的,在编译之后很小,其中一个原因就是在查询优化方面比较简单,它只是运用索引机制来进行优化的,经过对SQLite的查询优化的分析以及对源代码的研究,我将SQLite的查询优总结如下:

一、影响查询性能的因素:

1 对表中行的检索数目,越小越好

2 排序与否。

3 是否要对一个索引。

4 查询语句的形式

二、几个查询优化的转换

1 对于单个表的单个列而言,如果都有形如T.C=expr这样的子句,并且都是用OR操作符连接起来,形如: x = expr1 OR expr2 = x OR x = expr3 此时由于对于OR,在SQLite中不能利用索引来优化,所以可以将它转换成带有IN操作符的子句:x IN(expr1,expr2,expr3)这样就可以用索引进行优化,效果很明显,但是如果在都没有索引的情况下OR语句执行效率会稍优于IN语句的效率。

2 如果一个子句的操作符是BETWEEN,在SQLite中同样不能用索引进行优化,所以也要进行相应的等价转换: 如:a BETWEEN b AND c可以转换成:(a BETWEEN b AND c) AND (a>=b) AND (a<=c)。 在上面这个子句中, (a>=b) AND (a<=c)将被设为dynamic且是(a BETWEEN b AND c)的子句,那么如果BETWEEN语句已经编码,那么子句就忽略不计,如果存在可利用的index使得子句已经满足条件,那么父句则被忽略。

3 如果一个单元的操作符是LIKE,那么将做下面的转换:x LIKE abc%’,转换成:x>=abc AND x<abd’。因为在SQLite中的LIKE是不能用索引进行优化的,所以如果存在索引的话,则转换后和不转换相差很远,因为对LIKE不起作用,但如果不存在索引,那么LIKE在效率方面也还是比不上转换后的效率的。

三、 几种查询语句的处理(复合查询)
1
.查询语句为:<SelectA> <operator> <selectB> ORDER BY <orderbylist> ORDER BY
    
执行方法: is one of UNION ALL, UNION, EXCEPT, or INTERSECT. 这个语句的执行过程是先将selectAselectB执行并且排序,再对两个结果扫描处理,对上面四种操作是不同的,将执行过程分成七个子过程:

   outA: selectA的结果的一行放到最终结果集中

   outB: selectA的结果的一行放到最终结果集中(只有UNION操作和UNION ALL操作,其它操作都不放入最终结果集中)

    AltB: selectA的当前记录小于selectB的当前记录

    AeqB: selectA的当前记录等于selectB的当前记录

    AgtB: selectA的当前记录大于selectB的当前记录

    EofA: selectA的结果遍历完

    EofB: selectB的结果遍历完

         下面就是四种操作的执行过程:

 执行顺序

UNION ALL

UNION

EXCEPT

INTERSECT

AltB:

outA, nextA

outA, nextA

outA,nextA

nextA

AeqB:

outA, nextA

nextA

nextA

outA, nextA

AgtB:

outB, nextB

outB, nextB

nextB

nextB

EofA:

outB, nextB

outB, nextB

halt

halt

EofB:

outA, nextA

outA, nextA

outA,nextA

halt

     2 如果可能的话,可以把一个用到GROUP BY查询的语句转换成DISTINCT语句来查询,因为GROUP BY有时候可能会用到index,而对于DISTINCT都不会用到索引的 。

四、子查询扁平化 

     例子:SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5

     对这个SQL语句的执行一般默认的方法就是先执行内查询,把结果放到一个临时表中,再对这个表进行外部查询,这就要对数据处理两次,另外这个临时表没有索引,所以对外部查询就不能进行优化了,如果对上面的SQL进行处理后可以得到如下SQL语句:SELECT x+y AS a FROM t1 WHERE z<100 AND a>5,这个结果显然和上面的一样,但此时只需要对

数据进行查询一次就够了,另外如果在表t1上有索引的话就避免了遍历整个表。

运用flatten方法优化SQL的条件:

1.子查询和外查询没有都用集函数

2.子查询没有用集函数或者外查询不是个表的连接

3.子查询不是一个左外连接的右操作数

4.子查询没有用DISTINCT或者外查询不是个表的连接

5.子查询没有用DISTINCT或者外查询没有用集函数

6.子查询没有用集函数或者外查询没有用关键字DISTINCT

7.子查询有一个FROM语句

8.子查询没有用LIMIT或者外查询不是表的连接

9.子查询没有用LIMIT或者外查询没有用集函数

10.子查询没有用集函数或者外查询没用LIMIT

11.子查询和外查询不是同时是ORDER BY子句

12.子查询和外查询没有都用LIMIT

13.子查询没有用OFFSET

14.外查询不是一个复合查询的一部分或者子查询没有同时用关键字ORDER BYLIMIT

15.外查询没有用集函数子查询不包含ORDER BY

16.复合子查询的扁平化:子查询不是一个复合查询,或者他是一个UNION ALL复合查询,但他是都由若干个非集函数的查询构成,他的父查询不是一个复合查询的子查询,也没有用集函数或者是DISTINCT查询,并且在FROM语句中没有其它的表或者子查询,父查询和子查询可能会包含WHERE语句,这些都会受到上面111213条件的限制。

例:   SELECT a+1 FROM (

              SELECT x FROM tab

              UNION ALL

              SELECT y FROM tab

               UNION ALL

               SELECT abs(z*2) FROM tab2

           ) WHERE a!=5 ORDER BY 1

转换为:

        SELECT x+1 FROM tab WHERE x+1!=5

           UNION ALL

           SELECT y+1 FROM tab WHERE y+1!=5

           UNION ALL

           SELECT abs(z*2)+1 FROM tab2 WHERE abs(z*2)+1!=5

           ORDER BY 1

17.如果子查询是一个复合查询,那么父查询的所有的ORDER BY语句必须是对子查询的列的简单引用

18.子查询没有用LIMIT或者外查询不具有WHERE语句

子查询扁平化是由专门一个函数实现的,函数为:

static int flattenSubquery(

Parse *pParse,       /* Parsing context */

Select *p,           /* The parent or outer SELECT statement */

int iFrom,           /* Index in p->pSrc->a[] of the inner subquery */

int isAgg,           /* True if outer SELECT uses aggregate functions */

int subqueryIsAgg    /* True if the subquery uses aggregate functions */

)

       它是在Select.c文件中实现的。显然对于一个比较复杂的查询,如果满足上面的条件时对这个查询语句进行扁平化处理后就可以实现对查询的优化。如果正好存在索引的话效果会更好!

 

五、连接查询

       在返回查询结果之前,相关表的每行必须都已经连接起来,在SQLite中,这是用嵌套循环实现的,在早期版本中,最左边的是最外层循环,最右边的是最内层循环,连接两个或者更多的表时,如果有索引则放到内层循环中,也就是放到FROM最后面,因为对于前面选中的每行,找后面与之对应的行时,如果有索引则会很快,如果没有则要遍历整个表,这样效率就很低,但在新版本中,这个优化已经实现。

       优化的方法如下:

       对要查询的每个表,统计这个表上的索引信息,首先将代价赋值为SQLITE_BIG_DBL(一个系统已经定义的常量):

1)    如果没有索引,则找有没有在这个表上对rowid的查询条件:

1.如果有Rowid=EXPR,如果有的话则返回对这个表代价估计,代价计为零,查询得到的记录数为1,并完成对这个表的代价估计,

2.如果没有Rowid=EXPR 但有rowid IN (...),而IN是一个列表,那么记录返回记录数为IN列表中元素的个数,估计代价为NlogN,

3.如果IN不是一个列表而是一个子查询结果,那么由于具体这个子查询不能确定,所以只能估计一个值,返回记录数为100,代价为200

4.如果对rowid是范围的查询,那么就估计所有符合条件的记录是总记录的三分之一,总记录估计为1000000,并且估计代价也为记录数。

5.如果这个查询还要求排序,则再另外加上排序的代价NlogN

6.如果此时得到的代价小于总代价,那么就更新总代价,否则不更新。

2)    如果WHERE子句中存在OR操作符,那么要把这些OR连接的所有子句分开再进行分析。

1 如果有子句是由AND连接符构成,那么再把由AND连接的子句再分别分析。

2 如果连接的子句的形式是X<op><expr>,那么就再分析这个子句。

3 接下来就是把整个对OR操作的总代价计算出来。

4 如果这个查询要求排序,则再在上面总代价上再乘上排序代价NlogN

5 如果此时得到的代价小于总代价,那么就更新总代价,否则不更新。

3)    如果有索引,则统计每个表的索引信息,对于每个索引:

1 先找到这个索引对应的列号,再找到对应的能用到(操作符必须为=或者是IN(…))这个索引的WHERE子句,如果没有找到,则退出对每个索引的循环,如果找到,则判断这个子句的操作符是什么,如果是=,那么没有附加的代价,如果是INsub-select),那么估计它附加代价inMultiplier25,如果是INlist),那么附加代价就是NNlist的列数)。

2 再计算总的代价和总的查询结果记录数和代价。

3 nRow = pProbe->aiRowEst[i] * inMultiplier;/*计算行数*/

4 cost = nRow * estLog(inMultiplier);/*统计代价*/

5 如果找不到操作符为=或者是IN(…)的子句,而是范围的查询,那么同样只好估计查询结果记录数为nRow/3,估计代价为cost/3

6 同样,如果此查询要求排序的话,再在上面的总代价上加上NlogN

7 如果此时得到的代价小于总代价,那么就更新总代价,否则不更新。

4)    通过上面的优化过程,可以得到对一个表查询的总代价(就是上面各个代价的总和),再对第二个表进行同样的操作,这样如此直到把FROM子句中所有的表都计算出各自的代价,最后取最小的,这将作为嵌套循环的最内层,依次可以得到整个嵌套循环的嵌套顺序,此时正是最优的,达到了优化的目的。

5)    所以循环的嵌套顺序不一定是与FROM子句中的顺序一致,因为在执行过程中会用索引优化来重新排列顺序。

六、索引

   SQLite中,有以下几种索引:

1)    单列索引

2)    多列索引

3)    唯一性索引

4)    对于声明为:INTEGER PRIMARY KEY的主键来说,这列会按默认方式排序,所以虽然在数据字典中没有对它生成索引,但它的功能就像个索引。所以如果在这个主键上在单独建立索引的话,这样既浪费空间也没有任何好处。

运用索引的注意事项:

1)    对于一个很小的表来说没必要建立索引

2)    在一个表上如果经常做的是插入更新操作,那么就要节制使用索引

3)    也不要在一个表上建立太多的索引,如果建立太多的话那么在查询的时候SQLite可能不会选择最好的来执行查询,一个解决办法就是建立聚蔟索引

索引的运用时机:

1)    操作符:=><IN

2)    操作符BETWEENLIKEOR不能用索引,

       BETWEENSELECT * FROM mytable WHERE myfield BETWEEN 10 and 20;

       这时就应该将其转换成:

       SELECT * FROM mytable WHERE myfield >= 10 AND myfield <= 20;

       此时如果在myfield上有索引的话就可以用了,大大提高速度

 

       再如LIKESELECT * FROM mytable WHERE myfield LIKE 'sql%';

       此时应该将它转换成:

       SELECT * FROM mytable WHERE myfield >= 'sql' AND myfield < 'sqm';

       此时如果在myfield上有索引的话就可以用了,大大提高速度

 

       再如ORSELECT * FROM mytable WHERE myfield = 'abc' OR myfield = 'xyz';

       此时应该将它转换成:

       SELECT * FROM mytable WHERE myfield IN ('abc', 'xyz');

       此时如果在myfield上有索引的话就可以用了,大大提高速度

3)    有些时候索引都是不能用的,这时就应该遍历全表(程序演示)

       SELECT * FROM mytable WHERE myfield % 2 = 1;

       SELECT * FROM mytable WHERE substr(myfield, 0, 1) = 'w';

       SELECT * FROM mytable WHERE length(myfield) < 5;

 

上次讲到了SQLite的查询优化代码中的具体实现,现在来看一下它的几个实例:

  1 #include "stdio.h"
  2 #include "sqlite3.h"
  3 #include <windows.h>
  4 void query(sqlite3 *db,sqlite3_stmt *stmt,char * sql);
  5 
  6 int main(int argc, char **argv)
  7 {
  8     sqlite3 *db;
  9     char *zErr;
10     int rc;
11     char *sql;
12     sqlite3_stmt *stmt=0;
13     rc = sqlite3_open("memory.db", &db);
14     if(rc) {
15         fprintf(stderr, "Can't open database: %s\n", sqlite3_errmsg(db));
16         sqlite3_close(db);
17     }
18 
19     //
下面是所建的各个表的结构
20     sql="CREATE TABLE t1 (num int,word TEXT NOT NULL)";
21     //sql="CREATE TABLE t4 (num INTEGER NOT NULL,word TEXT NOT NULL)";
22     //sql="CREATE TABLE t3 (num INTEGER NOT NULL,word TEXT NOT NULL)";
23     rc = sqlite3_exec(db, sql, NULL, NULL, &zErr);
24     if(rc != SQLITE_OK) {
25         if (zErr != NULL) {
26             fprintf(stderr, "SQL error: %s\n", zErr);
27             sqlite3_free(zErr);
28         }
29     }
30 
31     //
下面是对所以插入进行手动提交,这样可以加快插入速度
32     //sqlite3_exec(db,"BEGIN",NULL,NULL,&zErr);
33     //
插入1000000条记录
34     //for (int i=0;i<1000000;i++)
35     //{
36     //    sql = sqlite3_mprintf("insert into t1 values(%d,'%s')",i,"goodc");
37     //    rc = sqlite3_exec(db, sql, NULL, NULL, &zErr);
38     //}
39     //sqlite3_exec(db,"COMMIT",NULL,NULL,&zErr);
40    
41     sql="create index t1nwindex on t1(num)";
42     rc=sqlite3_exec(db, sql, NULL, NULL, &zErr);
43     if(rc != SQLITE_OK) {
44         if (zErr != NULL) {
45             fprintf(stderr, "SQL error: %s\n", zErr);
46             sqlite3_free(zErr);
47         }
48     }
49 
50     //sql="drop index t1nwindex";
51     //sql="drop index t3index";
52     //sql="delete from t2";
53     rc=sqlite3_exec(db, sql, NULL, NULL, &zErr);
54     if(rc != SQLITE_OK) {
55         if (zErr != NULL) {
56             fprintf(stderr, "SQL error: %s\n", zErr);
57             sqlite3_free(zErr);
58         }
59     }
60 
61     printf("
查询结果是:\n");
62     //sql="select * from t1 where num=3000 or num=2000";//INTEGER PRIMARY KEY,快
63     //sql="select * from t2 where num=3000 or num=2000";//没有索引,慢
64     //sql="select * from t3 where num=3000 or num=2000";//有索引,快
65    
66     //
这里交换位置了,但是结果用的时间想差比较大的原因是,t1是用索引存储的,但是它不是由create index
67     //而创建的,所以系统还不会把它作为索引处理,所以这两个表就只是无索引的表,在内部优化计算代价只是对它
68     //进行估计,因为源代码中没有捕获到下面的查询条件,所以都是系统最大值(源代码中有),所以就嵌套顺序没
69     //变,所以出现下面的差异。
70     //sql="SELECT count(*) FROM t3, t1 WHERE t1.num = t3.num";//比下面的快,由于内层少
71     //sql="SELECT count(*) FROM t1, t3 WHERE t1.num = t3.num";//比上面的慢,由于内层多
72 
73     //
下面这个已经内部实现优化,所以所用时间是相同的
74     //sql="SELECT * FROM t2, t3 WHERE t2.num = t3.num";//有索引,稍快
75     //sql="SELECT * FROM t3, t2 WHERE t2.num = t3.num";//同上,内部已经优化
76 
77     //sql="select * from t3 where num=8000";//
有索引,快
78     //sql="select * from t1 where num%2=0";//有索引,但不能用,很慢
79     //sql="select * from t1 where num=8000";//没有索引,慢
80    
81     //BETWEEN
的转换优化---内部已经实现优化,如果有索引的话快一点
82     //sql="select count(*) from t2 where word between 'goodl' and 'goodm'";//BETWEEN
83     //sql="select count(*) from t2 where word >='goodl' and word<'goodm'";//BETWEEN
的转换
84 
85     //LIKE
的转换优化---内部已经实现优化
86     //sql="select count(*) from t2 where word like 'goodl%'";//有索引不起作用
87     //sql="select count(*) from t2 where word >='goodl' and word <'goodm'";//如果有索引会更快
88 
89     //IN
的转换优化---内部没有实现优化,但此时如果可以用索引的话就会很好
90     //如果不用索引则在这里体现不出INOR优,而如果有索引则差别很明显
91     //sql="select count(*) from t2 where word in('goodllll','goodkkkk','goodaaaa')";
92     //sql="select count(*) from t2 where word ='goodllll' or word ='goodkkkk' or word='goodaaaa'";
93 
94     int start=GetTickCount();
95     query(db,stmt,sql);
96     printf("the time has pass:%dms\n",GetTickCount()-start);
97     sqlite3_close(db);
98     return 0;   
99 }
100 
101 void query(sqlite3 *db,sqlite3_stmt *stmt,char * sql){
102     int rc,ncols,i;
103     const char *tail;
104     rc = sqlite3_prepare(db, sql, -1, &stmt, &tail);
105     if(rc != SQLITE_OK) {
106         fprintf(stderr, "SQL error: %s\n", sqlite3_errmsg(db));
107     }
108     rc = sqlite3_step(stmt);
109     ncols = sqlite3_column_count(stmt);
110     while(rc == SQLITE_ROW) {   
111         for(i=0; i < ncols; i++) {
112             fprintf(stderr, "'%s' ", sqlite3_column_text(stmt, i));
113         }
114         fprintf(stderr, "\n");
115         rc = sqlite3_step(stmt);
116     }
117 }

Feedback

#1    回复  引用  查看    

2009-03-03 13:53 by aierong     

我也喜欢sqliteclip_image001

#2    回复  引用  查看    

2009-03-03 17:25 by 玉开     

me too

#3 [楼主]   回复  引用  查看    

2009-03-03 17:29 by 上善     

SQLite确实很吸引人啊,很典型的一个嵌入式DBMS,值得好好研究。

#4    回复  引用    

2009-03-03 23:50 by 木头羊 [未注册用户]

我的官方站点就是用这个数据库的,速度挺快的

#5    回复  引用    

2009-03-04 08:29 by @木头羊 [未注册用户]

@木头羊
速度确实快啊,很方便用的;@木头羊

#6    回复  引用    

2009-03-04 08:30 by king2009 [未注册用户]

再如LIKESELECT * FROM mytable WHERE myfield LIKE 'sql%';

此时应该将它转换成:

SELECT * FROM mytable WHERE myfield >= 'sql' AND myfield < 'sqm';

这句什么意思啊?模糊查询也能转换成>= and < ?????????????

#7    回复  引用    

2009-03-04 10:05 by @上善 [未注册用户]

@king2009

如果查询是LIKE 'sql%';,那么说明要查询的字符串格式是前三位必须是sql,后面可以是任意位任何字符,那么 myfield >= 'sql' 的意思就是说明要找的字符串要比'sql'长或者就是'sql',而后面的'sqm'的意思是说要找的字符串的第三个必须要比m小,再加上前面的限制条件,所以只能是'l'了,所以myfield >= 'sql' AND myfield < 'sqm'就找到了LIKE 'sql%'的字符串。

#8    回复  引用    

2009-03-04 11:38 by king2009 [未注册用户]

噢,如果是like 中文的话,那就是没辙了!
LIKE '
张三%'
myfield >= '
张三' AND myfield < '???'

#9 [楼主]   回复  引用  查看    

2009-03-04 13:01 by 上善     

你可真会想,对于中文的话要编码的,看用哪种编码方式了,如果是中文的话现在就不用索引而是用LIKE就行了。

 

posted on 2009-06-20 03:10 肥仔 阅读(4489) 评论(0)  编辑 收藏 引用 所属分类: 数据库


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理