SQLite执行计划(Query Planning)---数据库索引篇，sqlite执行计划

和通数据库htsjk.Com2019-09-12 23:10 来源:未知阅读:13504 评论 245 热度2

标签：

SQLite执行计划(Query Planning)---数据库索引篇，sqlite执行计划

本文地址：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次就能找到，比全表扫描快了一百万倍！
图4：按rowid查找
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查找Claifornia Orange有了另一种选择：先找到所有来自Claifornia的fruit，然后筛选出不是Orange的行。
图9：Claifornia Orange的索引查找
使用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：多列索引上的单列查找
因此，一个好的做法是你的数据库schema中，不应该存在一个index是另外一个index前缀的情况。删除那个更少列的index，SQLite仍然可以利用那个更长的index实现高效的查找。
1.7 覆盖索引(covering indices) “price of California oranges”查询可以通过两列索引变得更加高效。但是SQLite还可以更加高效：通过包含"price"列的三列索引

CREATE INDEX Idx4 ON FruitsForSale(fruit, state, price);

图13：covering index
这个索引包含了查询语句中的搜索项和结果项的列，我们称之为"covering index"。因为所有需要的信息都在covering index中，SQLite不再需要查询原表来找到价格。

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集合的并集得到最后结果。图15：OR约束的查询

上面的示意图好像是说SQLite先找到所有的rowid，然后用union操作合并这些rowid，最后才到原表中找出这些合并之后的rowid。实际上，rowid的查找和rowid的计算是并行的。SQLite会记住已经在结果集中的rowid，每次用一个索引去查找rowid时会避开重复。不过这也只是一个实现的细节。上述示意图虽然不是100%准确，然而提供了一个很好的概观给我们。
为了让OR-UNION过程使用索引，WHERE子句中由OR相连的每一项都必须有索引。为什么呢？因为只要有一项没有索引，为了找到这一项的rowid，SQLite就要做一次全表扫描；既然SQLite必须得做一次全表扫描，那就干脆一次全表扫描找到所有的结果，而不是先union再来二分查找。
2.排序(Sorting) SQLite（像其他数据库一样）可以使用索引实现ORDER BY子句。索引也可以像加快搜索一样，加快排序的过程。如果没有合适的索引可用，一个带ORDER BY子句的查询，一定要在一个单独的步骤中排序。

SELECT * FROM fruitsforsale ORDER BY fruit;

处理这个SQL，SQLite会先获取查询的所有结果，然后对结果运行sorter：图16：没有索引的排序
如果输出的结果行数是K，排序的时间复杂度是O(KlogK)。当k很小时，排序的时间并不是很重要。但是如果想上面那样，K==N，那么排序所需要的时间就会比全表扫描的时间还要多得多。而且，所有的输出都是临时存储（基于编译和运行时的设置，可能存储在内存，也可能在磁盘），那也同时意味着这句查询要消耗很多临时存储空间。
2.1 通过rowid排序因为排序的成本很高，SQLite尽力去省略这一步操作。如果SQLite能确定输出结果自然而然就能按序排列，排序步骤是可以跳过的。例如，如果你要求按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排序

使用covering index，SQLite可以遍历索引就得到输出结果，这个过程复杂度是O(N)，而且不用分配大量内存来存储结果集。
3 同时搜索和排序前面的讨论把搜索和排序分成不同的话题。但实际中，经常会在搜索的同时需要排序。幸运的是，这个过程可以用同一个索引完成。
3.1 使用多列索引搜索和排序
假设我们想找到所有orange的价格，并按state来排序：

SELECT price FROM fruitforsale WHERE fruit='Orange' ORDER BY state

搜索和排序都可以用两列索引Idx3来同时完成：

图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子句中的某部分可以使用索引。考虑以下查询：

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子句，可能可以避免扫描整个表。

由于上述原因，SQLite总是尝试进去局部搜索。
4 WITHOUT ROWID tables 上述原则既可以应用在普通的rowid table上，也可以应用在WITHOUT ROWID tables。唯一的不同是索引表中的最右边的rowid列被替换成了PRIMARY KEY。

---- 终于翻译完了。心好累。 ----