Query Planning

1.搜索

1.1.没有索引的表

1.2.通过Rowid查找

1.3.按索引查找

1.4.多个结果行

1.5.多个AND连接的WHERE-clause条款

1.6.多列索引

1.7.覆盖指数

1.8.在WHERE子句中的OR-Connected术语

2.排序

2.1.按Rowid排序

2.2.按索引排序

2.3.按覆盖指数排序

3.同时搜索和排序

3.1.使用多列索引搜索和排序

3.2.用覆盖索引搜索和排序

3.3.部分使用索引排序（aka块排序）

4.无ROWID表

概观

SQL（在其所有实现中，不仅仅是SQLite）的最佳特性是它是一种声明性语言，而不是过程语言。当用SQL编程时，你告诉系统你想要计算什么，而不是如何计算它。确定如何委派给SQL数据库引擎中的查询规划器子系统的任务。

对于任何给定的SQL语句，可能有数百或数千甚至数百万个执行操作的不同算法。所有这些算法都会得到正确的答案，尽管有些算法会比其他算法快。查询规划器是一个AI，它试图为每个SQL语句选择最快和最高效的算法。

大多数时候，SQLite中的查询计划员都做得很好。但是，查询计划员需要使用索引。这些指数通常必须由程序员添加。很少，查询计划人员AI会做出次优算法选择。在这些情况下，程序员可能希望提供额外的提示来帮助查询规划人员做得更好。

本文档提供了有关SQLite查询规划器和查询引擎如何工作的背景信息。程序员可以使用这些信息来帮助创建更好的索引，并在需要时提供帮助查询计划者的提示。

SQLite查询计划器和下一代查询计划器文档中提供了其他信息。

1.1.没有索引的表

SQLite中的大多数表由零个或多个包含唯一整数键（rowid或INTEGER PRIMARY KEY）的行组成，后面跟着内容。（例外是WITHOUT ROWID表。）行按照增加的rowid的顺序在逻辑上存储。例如，本文使用名为“FruitsForSale”的表格，其将各种水果与它们种植的州以及它们的单价在市场上相关联。架构是这样的：

CREATE TABLE FruitsForSale(
  Fruit TEXT,
  State TEXT,
  Price REAL
);

对于一些（任意）数据，这样一个表可能会逻辑地存储在磁盘上，如图1所示：

图1：表“FruitForSale”的逻辑布局

在这个例子中，rowid不是连续的，但它们是有序的。SQLite通常创建从一个开始的rowid，并且每个添加的行增加一个。但是如果行被删除，那么序列中可能会出现空白。如果需要，应用程序可以控制分配的rowid，以便行不一定插入底部。但不管发生了什么，rowid总是唯一且严格按照升序排列。

假设你想查询桃子的价格。该查询将如下所示：

SELECT price FROM fruitsforsale WHERE fruit='Peach';

为了满足这个查询，SQLite从表格中读取每一行，检查“水果”列的值是否为“桃子”，如果是，则输出该行的“价格”列。该过程如下图2所示。这是算法被称为全表扫描，因为必须读取和检查表的全部内容才能找到感兴趣的一行。对于只有7行的表格，全表扫描是可以接受的，但是如果表格包含700万行，则全表扫描可能会读取兆字节的内容以找到单个8字节数字。出于这个原因，通常会试图避免全表扫描。

图2：全表扫描

1.2.通过Rowid查找

避免全表扫描的一种技术是通过rowid（或等价的INTEGER PRIMARY KEY）进行查找。要查询桃子的价格，可以查询rowid为4的条目：

SELECT price FROM fruitsforsale WHERE rowid=4;

由于信息以rowid顺序存储在表中，因此SQLite可以使用二进制搜索来查找正确的行。如果表格包含N元素，查找所需行所需的时间与logN成比例，而不是与全表扫描中的N成比例。如果该表包含1000万个元素，那意味着查询的速度将大约为N/logN或大约一百万倍。

图3：通过Rowid查找

1.3.按索引查找

通过rowid查询信息的问题是，您可能不在乎“项目4”的价格是什么 - 您想知道桃子的价格。所以rowid查找是没有用的。

为了使原始查询更高效，我们可以在“fruitsforsale”表的“fruit”列中添加索引，如下所示：

CREATE INDEX Idx1 ON fruitsforsale(fruit);

索引是与原始“fruitsforsale”表类似的另一个表，但其内容（本例中为水果列）存储在rowid的前面，并且所有行都按内容顺序排列。图4给出了Idx1索引的逻辑视图。“水果”栏是用于排序表的元素的主键，而“rowid”是用于在两行或更多行具有相同“水果”时打破领带的二级键。在该示例中，rowid必须用作“橙色”行的打破平局。请注意，由于rowid始终在原始表的所有元素上都是唯一的，因此“fruit”后跟“rowid”的组合键在索引的所有元素上都是唯一的。

图4：水果行上的索引

这个新索引可以用来为原始“桃子价格”查询实现更快的算法。

SELECT price FROM fruitsforsale WHERE fruit='Peach';

该查询首先在Idx1索引上对水果=“Peach”的条目执行二进制搜索。SQLite可以在Idx1索引上执行此二进制搜索，但不在原始的FruitsForSale表上执行此二进制搜索，因为Idx1中的行按“水果”列排序。在Idx1索引中找到具有fruit ='Peach'的行后，数据库引擎可以提取该行的rowid。然后数据库引擎在原始FruitsForSale表上进行第二次二分查找，以查找包含fruit ='Peach'的原始行。从FruitForSale表中的行中，SQLite可以提取价格列的值。该过程如图5所示。

图5：桃子价格的索引查询

SQLite必须执行两个二进制搜索以使用上面的方法显示桃子的价格。但是对于具有大量行的表格，这仍然比进行全表扫描要快得多。

1.4.多个结果行

在之前的查询中，fruit ='Peach'约束将结果缩小为单行。但即使获得多行，相同的技术也可以工作。假设我们查询了橙子而不是桃子的价格：

SELECT price FROM fruitsforsale WHERE fruit='Orange'

图6：橘子价格的索引查询

在这种情况下，SQLite仍然执行一个二进制搜索来查找索引的第一个条目，其中fruit ='Orange'。然后它从索引中提取rowid，并使用该rowid通过二进制搜索来查找原始表项，并从原始表中输出价格。但不是退出，数据库引擎然后前进到下一行索引重复下一个水果=“橙色”条目的过程。前进到索引（或表）的下一行比进行二分查找要便宜得多，因为下一行通常与当前行位于同一数据库页面上。事实上，与二分查找相比，前进到下一行的成本非常便宜，而我们通常忽略它。所以我们对这个查询的总成本的估计是3个二进制搜索。

1.5.多个AND连接的WHERE-clause条款

接下来，假设你想查找不仅仅是橙子的价格，而是特别是加利福尼亚种植的橙子的价格。适当的查询将如下所示：

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA'

图7：加州橘子的索引查找

此查询的一种方法是使用WHERE子句的fruit ='Orange'项来查找处理桔子的所有行，然后通过拒绝来自加利福尼亚以外的任何状态来筛选这些行。这个过程如上图7所示。在大多数情况下，这是一个完全合理的方法。是的，数据库引擎不得不为佛罗里达橙色行进行额外的二进制搜索，后来被拒绝了，所以它没有我们所希望的那样高效，尽管对于许多应用程序来说它足够高效。

假设除了“果实”指数外，还有一个关于“国家”的指数。

CREATE INDEX Idx2 ON fruitsforsale（state）;

图8：State列的索引

“State”索引就像“水果”索引一样工作，因为它是一个新表，在rowid前面有一个额外的列，并且按照该主列的顺序排列。唯一的区别是在Idx2中，第一列是“状态”而不是“水果”，就像Idx1一样。在我们的示例数据集中，“状态”列中存在更多冗余，因此它们的重复条目更多。关系仍然使用rowid解决。

在“State”中使用新的Idx2索引时，SQLite还有另外一种查找加利福尼亚橙子价格的选项：它可以查找包含加利福尼亚水果的每一行，并过滤掉那些不是橙子的行。

图9：加州橘子索引查询

使用Idx2而不是Idx1会导致SQLite检查一组不同的行，但最终会得到相同的答案（这非常重要 - 记住索引不应该更改答案，只能帮助SQLite更快地得到答案）而且它的工作量相同。因此，在这种情况下，Idx2指数无助于表现。

在我们的例子中，最后两个查询需要相同的时间。那么SQLite会选择哪个索引Idx1或Idx2？如果ANALYZE命令已在数据库上运行，以便SQLite有机会收集有关可用索引的统计信息，则SQLite将知道Idx1索引通常会将搜索范围缩小为单个项目（我们的示例fruit ='橙色“是这条规则的例外），而Idx2索引通常只会将搜索范围缩小到两行。因此，如果其他条件相同，SQLite将选择Idx1，希望将搜索范围缩小到尽可能少的行数。由于ANALYZE提供的统计数据，这种选择是唯一可能的。如果ANALYZE尚未运行，那么选择使用哪个索引是任意的。

1.6.多列索引

要在WHERE子句中使用多个AND关联术语的查询中获得最大性能，您确实需要一个多列索引，并且每个AND术语都有列。在这种情况下，我们在FruitsForSale的“水果”和“State”列中创建一个新索引：

CREATE INDEX Idx3 ON FruitsForSale(fruit, state);

图1：双列索引

多列索引遵循与单列索引相同的模式; 索引列将被添加到rowid前面。唯一的区别是现在添加了多列。最左边的列是用于对索引中的行进行排序的主键。第二列用于打破最左列中的关系。如果有第三列，它将用于打破前两列的关系。索引中的所有列都是如此。由于rowid保证是唯一的，即使两行的所有内容列都相同，索引的每一行也都是唯一的。这种情况在我们的样本数据中没有发生，但有一种情况（fruit ='Orange'），第一列必须打破第二列的关系。

鉴于新的多列Idx3索引，现在可以使用SQLite仅使用2个二进制搜索来查找加利福尼亚橘子的价格：

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA'

图11：使用双列索引查找

由于受到WHERE子句约束的两列上的Idx3索引，SQLite可以针对Idx3执行一次二进制搜索以查找加利福尼亚橘子的一个rowid，然后执行一次二元搜索以查找原始表中该项目的价格。没有死胡同，也没有浪费二进制搜索。这是一个更有效的查询。

请注意，Idx3包含与原始Idx1相同的所有信息。所以如果我们有Idx3，我们不再需要Idx1了。通过简单地忽略Idx3的“状态”列，使用Idx3可以满足“桃子价格”查询：

SELECT price FROM fruitsforsale WHERE fruit='Peach'

图12：多列索引上的单列查找

因此，一个好的经验法则是，你的数据库模式不应该包含两个索引，其中一个索引是另一个索引的前缀。用较少的列删除索引。SQLite仍然能够使用较长的索引进行高效查找。

1.7.覆盖指数

通过使用双列索引，“加利福尼亚橙子价格”查询变得更高效。但是，对于包含“价格”列的三列索引，SQLite可以做得更好：

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

图13：覆盖指数

此新索引包含查询使用的原始FruitsForSale表的所有列 - 搜索词和输出。我们称之为“覆盖指数”。由于所有需要的信息都在覆盖索引中，因此SQLite无需查阅原始表以查找价格。

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA';

​

图14：使用覆盖索引进行查询

因此，通过在索引末尾添加额外的“输出”列，可以避免引用原始表，从而将查询的二进制搜索次数减半。这是性能的一个常数因素改进（大约是速度的两倍）。但另一方面，它也只是一种改进; 性能提升两倍的表现并不像表格第一次编制时所看到的增长一百万倍。而对于大多数查询，1微秒和2微秒之间的差异不太可能被注意到。

1.8.在WHERE子句中的OR-Connected术语

多列索引仅在查询的WHERE子句中的约束条件通过AND连接时才起作用。因此，当搜索既是桔子又是在加利福尼亚州种植的物品时，Idx3和Idx4是有帮助的，但如果我们想要所有橙子或在加利福尼亚种植的物品，那么这两种索引都不会有用。

SELECT price FROM FruitsForSale WHERE fruit='Orange' OR state='CA';

当在WHERE子句中遇到OR连接词时，SQLite会分别检查每个OR词，并尝试使用索引来查找与每个词关联的rowid。然后它将生成的rowid集合组合起来以找到最终结果。下图说明了这个过程：

图15：使用OR约束的查询

上面的图意味着SQLite首先计算所有rowid，然后在开始在原始表上执行rowid查找之前将它们与联合操作结合起来。实际上，rowid查找是散布在rowid计算中的。SQLite一次使用一个索引来查找rowid，同时记住之前看到的rowid，以避免重复。不过，这只是一个实现细节。该图尽管不是100％准确的，但提供了对发生情况的良好概述。

为了使上面显示的OR-by-UNION技术有用，必须有可用的索引来帮助解决WHERE子句中的每个OR关联术语。如果即使是一个OR连接的术语没有被索引，那么为了找到一个术语产生的rowid也必须进行全表扫描，并且如果SQLite必须进行全表扫描，那么最好不要它可以在原始表格上获得所有结果，而无需混淆联合操作和后续二进制搜索。

我们可以看到OR-by-UNION技术如何通过使用相交运算符代替联合来利用OR-by-UNION技术在WHERE子句的AND连接的查询上使用多个索引。许多SQL数据库引擎都可以做到这一点。但是，仅使用单个索引的性能优势很小，因此SQLite目前不实现该技术。但是，未来版本的SQLite可能会增强以支持AND-by-INTERSECT。

除了加速查找之外，SQLite（与所有其他SQL数据库引擎一样）也可以使用索引来满足查询中的ORDER BY子句。换句话说，索引可以用来加快排序和搜索。

如果没有适当的索引可用，则带有ORDER BY子句的查询必须作为单独的步骤排序。考虑这个查询：

SELECT * FROM fruitsforsale ORDER BY fruit;

SQLite通过收集查询的所有输出并通过分拣机运行该输出来处理这个问题。

图16：没有索引的排序

如果输出行数为K，则排序所需的时间与KlogK成比例。如果K很小，排序时间通常不是一个因素，但是在诸如上述K == N的查询中，排序所需的时间可能远大于进行全表扫描所需的时间。此外，整个输出在临时存储器（可能在主内存或磁盘上，取决于各种编译时和运行时设置）中累积，这可能意味着需要大量临时存储才能完成查询。

2.1.按Rowid排序

因为排序可能很昂贵，所以SQLite努力将ORDER BY子句转换为no-ops。如果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列中可用，则可以使用该索引进行排序。考虑按“水果”排序的所有项目的请求：

SELECT * FROM fruitsforsale ORDER BY fruit;

图18：使用索引进行排序

从上到下扫描Idx1索引（如果使用“ORDER BY fruit DESC”，则从下到上扫描）以便按水果顺序查找每个项目的rowid。然后，对于每个rowid，执行二进制搜索以查找并输出该行。这样，输出按请求的顺序出现，无需收集整个输出并使用单独的步骤对其进行分类。

但这真的可以节省时间吗？原始无索引排序中的步数与NlogN成正比，因为对N行进行排序需要多少时间。但是当我们在这里使用Idx1时，我们必须进行N个rowid查找，每个查询需要logN时间，所以NlogN的总时间是一样的！

SQLite使用基于成本的查询计划器。当有两种或多种解决同一查询的方法时，SQLite会尝试估计使用每个计划运行查询所需的总时间，然后使用具有最低估计成本的计划。成本主要是从估计的时间计算出来的，因此这种情况可能会有所不同，具体取决于表大小以及可用的WHERE子句约束等等。但是一般来说，如果没有其他原因，可能会选择索引排序，因为它不需要在整理结果集之前在临时存储中累积，因此使用的临时存储量更少。

2.3.按覆盖指数排序

如果覆盖索引可以用于查询，那么可以避免多个rowid查找，并且查询的成本急剧下降。

图19：使用覆盖索引进行排序

使用覆盖索引，SQLite可以简单地将索引从一端移动到另一端，并在时间上提供与N成比例的输出，而不必分配一个大缓冲区来保存结果集。

前面的讨论将搜索和排序视为单独的主题。但在实践中，人们通常会想要同时进行搜索和排序。幸运的是，可以使用单个索引来完成此操作。

3.1.使用多列索引搜索和排序

假设我们想要找到各种桔子的价格，按照它们种植的状态排序。查询是这样的：

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

该查询同时包含WHERE子句中的搜索限制和ORDER BY子句中的排序顺序。搜索和排序都可以使用两列索引Idx3同时完成。

图20：按多列索引搜索和排序

查询在索引上执行二进制搜索以查找具有水果='橙色'的行的子集。（因为水果列是索引的最左边一列，索引的行按排序顺序排列，所有这样的行将相邻。）然后它从上到下扫描匹配的索引行以获取原始表，并为每个rowid在原始表上执行二进制搜索以查找价格。

您会注意到上图中没有任何“排序”框。查询的ORDER BY子句已成为无操作。由于输出顺序是由状态列和状态列恰好是索引中的水果列之后的第一列，所以这里不需要进行排序。因此，如果我们扫描索引条目的顶部到底部具有相同值的水果列，则这些索引条目保证按状态列排序。

3.2.用覆盖索引搜索和排序

A covering index can also be used to search and sort at the same time. Consider the following:

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

图21：按覆盖索引搜索和排序

和以前一样，SQLite对覆盖索引中满足WHERE子句的行范围进行单一二分搜索，这些扫描范围从上到下，以获得期望的结果。满足WHERE子句的行将保证相邻，因为WHERE子句是索引最左列的等式约束。通过从上到下扫描匹配的索引行，输出保证按状态排序，因为状态列是水果列右侧的下一列。所以生成的查询非常有效。

SQLite可以为降序ORDER BY提供类似的技巧：

SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state DESC

遵循相同的基本算法，除了这次索引的匹配行从底部到顶部而不是从顶部到底部扫描，以便状态以降序出现。

3.3.部分使用索引排序（aka块排序）

有时候只能使用索引来满足ORDER BY子句的一部分。例如，考虑以下查询：

SELECT * FROM fruitforsale ORDER BY fruit, price

如果覆盖索引用于扫描，“水果”栏将按照正确的顺序自然出现，但是当有两列或更多行具有相同水果时，价格可能不合格。发生这种情况时，SQLite会进行很多小的排序，每种排序的值都是一种水果，而不是一种大的排序。下面的图22说明了这个概念。

图22：部分按索引排序

在这个例子中，不是单一的7个元素，而是水果=='橙色'的情况下，有5种单一元素和1种2种元素。

做很多小排序而不是单排排序的好处是：

1. 多种小型排序共同使用比单个大型排序更少的CPU周期。

2. 每个小类都是独立运行的，这意味着任何时候都需要将更少的信息保存在临时存储中。

3. 由于索引而已经按正确顺序排列的那些ORDER BY列可以从排序键中省略，进一步减少了存储需求和CPU时间。

4. 输出行可以在每次小排序完成时返回到应用程序，并在表扫描完成之前完成。

5. 如果存在LIMIT子句，则可能会避免扫描整个表。

由于这些优点，SQLite总是尝试使用索引进行部分排序，即使按索引完成排序是不可能的。

上述基本原则适用于普通rowid表和WITHOUT ROWID表。唯一的区别是用作表的键的rowid列和作为索引中最右项出现的rowid列被PRIMARY KEY所取代。

 SQLite is in the Public Domain.