本文地址：http://blog.csdn.net/mba16c35/article/details/57197962
翻译自：https://www.sqlite.org/queryplanner.html
综述
sql的最好特性就是它是一种描述性的语言，不是一种过程语言。当你用sql编程，你是告诉系统你想计算什么，而不是怎么去计算它。如何计算的任务由sql数据库引擎中的执行计划(Query Planner)子系统完成。
对于任意一句sql语句，都可能有上千种算法实现它。所有这些算法都可以得到正确结果，但是其中一些会比其他运行得更快。执行计划的任务就是尝试找出最快而且最有效的算法。
在大多数时候，执行计划系统都可以做得很好。但是，它需要索引来完成这项工作。索引是由编码者添加的。在很少情况下执行计划会得到一个次优解，这时候，编码者可能想提供额外的提示去帮助执行计划子系统。
这篇文档提供了sqlite执行计划和引擎工作的背景知识。编码者可以用这些信息创建更好的索引，帮助执行计划获得更好的性能。
1.搜索
1.1 带索引的表
大多数sqlite的表都包含了带unique integer key的行（rowid 或者 INTEGER PRIMARY KEY）.这些行在逻辑上按照rowid的递增顺序来存储。举个栗子，本文使用一个叫“FruitsForSale”的表，表中的内容是关联某种水果和该水果在哪个国家培育，以及它的市场价格。
CREATE TABLE FruitsForSale( Fruit TEXT,State TEXT,Price REAL );
插入了一些实例数据之后，这个表在磁盘上可能以这样的逻辑顺序存储：
图1：表“FruitsForSale”
在这个例子里，rowid不是连续的，不过是按序的。sqlite一般从1开始创建rowid，每加一行就加一。但是如果某些行删了，序列中就会出现一些空缺。应用其实也可以控制rowid的赋值，然后这些行就不一定是在底部插入了。但不管怎样，rowid总是唯一而且按升序排列。
假如你想找到peach的价格：
SELECT price FROM fruitsforsale WHERE fruit='Peach';
为了实现这个查询，sqlite从表中读每一行出来，检查“fruit”一列是否为“Peach”，如果是，就打印这行的“price”列。这个过程如图2所示。这种算法叫做full table scan（全表扫描）：表中的所有内容都要读出来并检查，为了找到所需要的行。如果一张表只有7行，全表扫描是可以接受的。但是如果是一张有7百万行的表，那么全表扫描就要读出百万字节的内容，只是为了找出其中的8字节！因此，我们一般要避免full table scan.
图2：full table scan
1.2 按rowid查找
有一种可以避免全表扫描的技术是，按rowid查找（或者是等价的INTEGER PRIMARY KEY）。为了找到peach的价格，可以找到rowid是4的行：
SELECT price FROM fruitsforsale WHERE rowid=4;因为表中的信息时按rowid的顺序存储的，所以sqlite可以用二分法来找到这一行。假设表中有N行，那么二分法的算法复杂度就是O(logN)，全表扫描是O(N)。这就意味着，如果表有1千万行，上面的查询语句只需要大概10次就能找到，比全表扫描快了一百万倍！
1.3 按索引查找
但是你可能根本不关心item 4的价格是什么，你是想找到peach的价格。所以按rowid查找一般情况下没什么用。
为了查找更加有效，我们可以在“fruit”列上增加索引：
CREATE INDEX Idx1 ON fruitsforsale(fruit);一个索引也是用一张表来实现的，其中索引的内容存储在rowid前面，而且按索引排序（本例中就是“fruit”列）。图4展示了Idx1索引的逻辑示意图。fruit列是将表中内容排序的主键；有两行或两行以上的“fruit”相同时，就用rowid来确定不同的行，这就是rowid的作用。在例子中，“Orange”的两行就靠rowid来区分不同行。因为rowid是唯一的，所以”fruit“和“rowid”的组合键也是在索引表中唯一的。
图4：在fruit列上创建索引
然后这个索引就可以用来实现一个更快的查找Peach价格的算法：
SELECT price FROM fruitsforsale WHERE fruit='Peach';首先在索引Idx1上使用二分法查找fruit+‘Peach’，sqlite可以在Idx1索引表上执行二分查找，但是不能再FruitsForSale表上二分查找，因为Idx1的内容是按照“fruit”列来排序的。找到Idx1中fruit=‘Peach’的行之后，数据库引擎就可以提取这一行的rowid。接着数据库引擎就根据这个rowid，在原表上执行第二次二分查找。从FruitsForSale表上的行，sqlite就可以得到price列的数据。这个过程在表5中展示：
图5：按索引查找Peach的价格
按照上述算法，sqlite要执行两次二分查找来找到Peach的价格，但是对于数据流很大的情况，这也比全表扫描要快很多。
1.4 多行查询结果
在上一个查询中fruit='Peach'约束到一行结果。但是如果有多行结果，也是用一样的算法。假设我们现在要找到Orange的价格：
SELECT price FROM fruitsforsale WHERE fruit='Orange'
图6：找到Orange价格的索引查找算法
在这种情况中，sqlite执行二分查找去找到fruit=“Orange”的第一行。然后从索引表中提取rowid，根据这个rowid在原表中执行二分查找，接着从原表中提取价格列。但是这时还没有结束，数据库引擎接着在索引表中移动到下一行，重复同样的过程在原表中找到下一个Orange。在索引表中移动到下一行的操作，比起执行二分查找，成本会小很多，因为下一行一般和当前行一样位于数据的同一页（database page）.实际上，移动到下一行的成本相对二分查找来说基本可以忽略不计。所以这一个查询的总的耗时估计可以认为是3个二分查找。如果输出结果行数是K，表的总行数是N，那么这个查询的成本大约是(K+1)*logN.
1.5 多个And连接WHERE子句项
如果现在我们要查找在Claifornia培育的Orange的价格，这个查询要这样写：
SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA'
图7：Claifornia Orange的索引查找
如图7所示，这个查询的一个实现方法是先用WHERE子句的fruit='Orange'项找到所有的orange，然后根据state列筛选出Claifornia的行。这个方法在大多数情况下都是可行的。但是，对于不符合查找条件的Florida orange这一行，数据库引擎确实要做多一次无用的二分查找，所以这还没有我们希望的高效，虽然对许多应用来说已经足够高效。
如果除了"fruit"列的索引，我们还有一个“state”列的索引
CREATE INDEX Idx2 ON fruitsforsale(state);图8：state列的索引
“state”索引表像“fruit”索引一样，它是一张全新的表，根据state列排序，state列位于rowid列前面。唯一的区别是在Idx2中，第一列是“state”而Idx1中第一列是“fruit”。在我们的样例数据中，在“state”列有更多冗余，更多重复的数据。相同state的问题仍然由rowid来解决。
使用新的Idx2索引，sqlite查找ClaiforniaOrange有了另一种选择：先找到所有来自Claifornia的fruit，然后筛选出不是Orange的行。
图9：ClaiforniaOrange的索引查找
使用Idx2而不是Idx1导致sqlite检查了一些不同的行，但是最后的结果是一样的（这一点很重要，记住索引不会改变查询结果，仅仅是帮组sqlite更快的得到答案），工作量也是一样的。所以Idx2在这个case中并没有提升性能。
最后两个查询耗费的时间是一样的。那sqlite会选择Idx1还是Idx2呢？如果在数据库上运行
ANALYZE命令，sqlite就有机会收集关于可用索引的统计数据，然后sqlite就知道Idx1索引经常可以将搜索缩减到1行（我们的例子fruit='Orange'是这个规则的一个例外），但是Idx2索引一般情况下只会将搜索缩减到2行。因此当其他都一样的情况下，sqlite会选择Idx1，期望可以把搜索限制到更窄的情况。能让sqlite做出这个选择的唯一可能是
ANALYZE提供的统计数据。如果
ANALYZE没有执行过，选择哪个idex是任意的。
1.6 多列索引
为了在WHERE子句中存在多个AND连接项时，获得最好的性能，你需要一个创建一个针对每一个AND连接项的多列索引。在我们的例子中，我们在“fruit”和“state”列创建一个新的索引：
CREATE INDEX Idx3 ON FruitsForSale(fruit,state);图1：两列索引
多列索引的模式和单列索引类似。索引列位于rowid前面。不同的地方就是现在会有多个列。最左边的列是对这些索引行排序的主键。第二列是用来打破最左边列的平局。如果还有第三列，就可以用第三列来打破前两列的平局，如此类推。因为rowid一定唯一，所以即使前两列的所有内容都相同，索引表的每一个仍然是唯一的。
使用新的多列索引Idx3，现在sqlite可以只通过两次二分查找就得到California orange的价格了。
SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA'
图11：2列索引查找
Idx3的两列都由WHERE子句限制了，sqlIte可以只做一次二分查找就找到California orange的rowid，然后在原表中再做一次二分查找就可以找到这一项。现在完全没有多余的二分查找，我们更加高效了。
注意，Idx3包含了Idx1中所有信息。因此有了Idx3之后，我们就不需要Idx1了。查询"price of peaches"在忽略了Idx3的"state"列之后，一样可以通过Idx3实现。
SELECT price FROM fruitsforsale WHERE fruit='Peach'
图12：多列索引上的单列查找
1.7 覆盖索引(covering indices)
CREATE INDEX Idx4 ON FruitsForSale(fruit,state,price);图13：covering index
SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA';
图14：使用covering index的查询
因此，通过在索引最后增加“输出”列，可以避免查询原表，从而将二分查找的数量减少一半。这是性能上的常数级提升（大约两倍速度），不过远非第一次添加索引的巨大性能提升（100万倍速度）。对大多数应用来说，1毫秒和2毫秒的区别基本没法察觉。
1.8 WHERE 子句中的OR连接项
多列索引只有在WHERE子句的子项是由AND连接的时候才有效。所以当搜索条件是oranges而且在California培育时，Idx3和Idx4是有效的。但是如果我们是要找到orange或者再california培育时，这两个索引都起不到作用：
SELECT price FROM FruitsForSale WHERE fruit='Orange' OR state='CA';当遇到WHERE子句的项由OR连接时，sqlite分别检查每项并尝试使用每项的索引去找到rowid。然后取各个rowid集合的并集得到最后结果。
上面的示意图好像是说sqlite先找到所有的rowid，然后用union操作合并这些rowid，最后才到原表中找出这些合并之后的rowid。
实际上，rowid的查找和rowid的计算是并行的。sqlite会记住已经在结果集中的rowid，每次用一个索引去查找rowid时会避开重复。不过这也只是一个实现的细节。上述示意图虽然不是100%准确，然而提供了一个很好的概观给我们。
为了让OR-UNION过程使用索引，WHERE子句中由OR相连的每一项都必须有索引。为什么呢？因为只要有一项没有索引，为了找到这一项的rowid，sqlite就要做一次全表扫描；既然sqlite必须得做一次全表扫描，那就干脆一次全表扫描找到所有的结果，而不是先union再来二分查找。
2.排序(Sorting)
如果没有合适的索引可用，一个带ORDER BY子句的查询，一定要在一个单独的步骤中排序。
图16：没有索引的排序
如果输出的结果行数是K，排序的时间复杂度是O(KlogK)。当k很小时，排序的时间并不是很重要。但是如果想上面那样，K==N，那么排序所需要的时间就会比全表扫描的时间还要多得多。而且，所有的输出都是临时存储（基于编译和运行时的设置，可能存储在内存，也可能在磁盘），那也同时意味着这句查询要消耗很多临时存储空间。
2.1 通过rowid排序
SELECT * FROM fruitsforsale ORDER BY rowid;图17：按rowid排序
你也可以要求逆序排列：
SELECT * FROM fruitsforsale ORDER BY rowid DESC;sqlite仍然会忽略排序这一步。但是为了可以逆序输出，sqlite会从表的底部向头部扫描，而不是像图17那样从头部开始，向底部扫描。
2.2 按索引排序
当然，很少情况下按rowid排序是有用的。一般我们都会想要按照某一列排序。
如果ORDER BY的某一列是创建过索引的，这个索引就可以用于排序。考虑以下按"fruit"排序的查询：
SELECT * FROM fruitsforsale ORDER BY fruit;图17：按索引排序
Idx1从头到尾扫描（如果"ORDER BY fruit DESC"，就是从尾到头），为了找到每项的rowid，并且按fruit排序。每找到一个rowid，就会做一次二分查找并把那个结果输出。通过这种方式，输出能按要求排序，而且不用先收集全部输出，再在一个单独的步骤中排序。
但是这真的能节省时间吗？按照没有索引的方式，步骤的总数和NlogN成比例，因为这就是排序N行所需要的时间。如果我们使用索引Idx1，我们要找N个rowid，对每个rowid二分
查找花费logN的时间，所以总时间还是NlogN! What the hell!
sqlite使用基于成本衡量的执行计划子系统。当有两个或者更多方式来实现同一个查询时，sqlite会尝试估计执行每个执行计划所需的总时间，然后选用花销最小的那个执行计划。成本衡量大部分基于估计的时间，而时间成本可能取决于表的大小，WEHRE子句的哪些限制是可用的，等等。不过一般来说，没有其他原因的情况下，sqlite会选排序查找的方案，因为这样可以不用在排序前，在临时存储中保留完整的结果集，因而消耗了更少临时存储
2.3 通过covering index排序
如果可以使用covering index，rowid的查找是可以避免的，耗费的时间也可以大大减少。
图19：通过covering index排序
3 同时搜索和排序
3.1 使用多列索引搜索和排序
假设我们想找到所有orange的价格，并按state来排序：
图20：使用多列索引搜索和排序
正如前面所说，sqlite在covering index中，从上而下搜索满足WHERE子句条件的行范围。满足WHERE子句的行保证一定相连，，因为WHERE子句是一个"="约束，并且是索引最左边的列。而从上而下搜索匹配的索引行，保证了输出一定按state列排序，因为state列是紧挨着fruit列的下一列。因此，这句查询变得相当高效。
sqlite对ORDER BY降序排列时可以故伎重演：
SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state DESC除了这次是从下往上扫描匹配的索引行，其他都一样，state就能按降序排列。
3.3 使用索引时局部排序（Block Sorting）
有时只有ORDER BY子句中的某部分可以使用索引。考虑以下查询：
有时只有ORDER BY子句中的某部分可以使用索引。考虑以下查询：
SELECT * FROM fruitforsale ORDER BY fruit,price如果这个扫描使用covering index，“fruit”列本身就是排序好的，但是当有两行或者更多行的"fruit"相同是，price可能是不按序的。在这情况下，sqlite会针对每种fruit做许多小排序，而不是进行对全部结果的大排序。
图22：索引局部排序
在这个例子中，并没有对7个结果统一排序，而是通过5次包含1个结果的排序和1个包含2个结果的排序，得到最终结果。
这样做的好处是：
1.多个小的排序归并比一个大的排序使用更少cpu周期。
2.每个小的排序都是独立运行的，意味每次占用更少的临时存储。
3.ORDER BY中由于索引已经排序的列是可以忽略的(fruit列)，进一步减少cpu时间
4.每次小的排序完成之后都可以输出给应用，而不用等到全表扫描完成。
5.如果包含LIMIT子句，可能可以避免扫描整个表。
4 WITHOUT ROWID tables
上述原则既可以应用在普通的rowid table上，也可以应用在WITHOUT ROWID tables。唯一的不同是索引表中的最右边的rowid列被替换成了PRIMARY KEY。
----
终于翻译完了。心好累。
----
