SQLite 中的大多数表都包含零个或多个行，这些行具有唯一的整数键（rowid 或 INTEGER PRIMARY KEY），后面跟着内容。（例外是 WITHOUT ROWID 表。）这些行在逻辑上按 rowid 从小到大排序存储。例如，本文使用名为“FruitsForSale”的表，该表将各种水果与其生长状态和市场上的单价相关联。模式如下

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

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

图形 1：表“FruitsForSale”的逻辑布局

在本例中，rowid 不是连续的，但它们是有序的。SQLite 通常从 1 开始创建 rowid，并在添加每行时递增 1。但如果删除了行，序列中就会出现间隙。应用程序可以根据需要控制分配的 rowid，以便行不一定插入到最底部。但无论发生什么情况，rowid 始终是唯一的，并且严格按升序排列。

假设您要查找桃子的价格。查询将如下所示

SELECT price FROM fruitsforsale WHERE fruit='Peach';

为了满足此查询，SQLite 从表中读取每行，检查“fruit”列的值是否为“Peach”，如果是，则输出该行的“price”列。该过程由下图图 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，即大约快 100 万倍。

图形 3：按 Rowid 查找

1.3. 按索引查找

按 rowid 查找的问题是，您可能并不关心“项目 4”的价格是多少 - 您想知道桃子的价格。因此，rowid 查找没有帮助。

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

CREATE INDEX Idx1 ON fruitsforsale(fruit);

索引是另一个表，类似于原始的“fruitsforsale”表，但内容（在本例中为 fruit 列）存储在 rowid 之前，并且所有行都按内容顺序排列。图 4 给出了 Idx1 索引的逻辑视图。“fruit”列是用于对表元素进行排序的主键，“rowid”是用于在两个或多个行具有相同“fruit”时打破平局的辅助键。在本例中，rowid 必须用作“Orange”行的平局决胜者。请注意，由于 rowid 在原始表的全部元素上始终是唯一的，因此“fruit”后跟“rowid”的组合键在索引的全部元素上也将是唯一的。

图形 4：对 Fruit 列的索引

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

SELECT price FROM fruitsforsale WHERE fruit='Peach';

查询从对 Idx1 索引进行二分查找开始，查找 fruit='Peach' 的条目。SQLite 可以对 Idx1 索引进行此二分查找，但不能对原始 FruitsForSale 表进行，因为 Idx1 中的行按“fruit”列排序。在 Idx1 索引中找到了 fruit='Peach' 的行后，数据库引擎可以提取该行的 rowid。然后，数据库引擎对原始 FruitsForSale 表进行第二次二分查找，以找到包含 fruit='Peach' 的原始行。从 FruitsForSale 表中的行，SQLite 然后可以提取 price 列的值。此过程由下图图 5 说明。

图形 5：桃子价格的索引查找

SQLite 必须执行两次二分查找才能使用上述方法找到桃子的价格。但是对于包含大量行的表，这仍然比执行全表扫描快得多。

1.4. 多个结果行

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

SELECT price FROM fruitsforsale WHERE fruit='Orange'

图形 6：橙子价格的索引查找

在这种情况下，SQLite 仍然执行单个二分查找以找到索引中 fruit='Orange' 的第一个条目。然后，它从索引中提取 rowid，并使用该 rowid 通过二分查找查找原始表条目，并输出原始表中的价格。但是，数据库引擎不会退出，而是前进到索引的下一行，以重复下一 fruit='Orange' 条目的过程。前进到索引（或表）的下一行比执行二分查找的成本要低得多，因为下一行通常位于与当前行相同的数据库页面上。实际上，前进到下一行的成本与二分查找相比非常便宜，以至于我们通常忽略它。因此，我们对该查询总成本的估计是 3 次二分查找。如果输出行的数量为 K，表中行的数量为 N，那么一般来说，执行查询的成本与 (K+1)*logN 成正比。

1.5. 多个 AND 连接的 WHERE 子句项

接下来，假设您不仅要查找任何橙子，而是要专门查找加州种植的橙子。相应的查询如下所示

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

图形 7：加州橙子的索引查找

此查询的一种方法是使用 WHERE 子句中的 fruit='Orange' 项找到所有处理橙子的行，然后通过拒绝来自加利福尼亚州以外的州的所有行来过滤这些行。此过程由上图图 7 说明。在大多数情况下，这是一种非常合理的方法。是的，数据库引擎确实必须对后来被拒绝的佛罗里达橙子行执行额外的二分查找，因此效率不如我们希望的那样高，但对于许多应用程序而言，它已经足够高效了。

假设除了“fruit”上的索引外，还有“state”上的索引。

CREATE INDEX Idx2 ON fruitsforsale(state);

图形 8：对 State 列的索引

“state”索引与“fruit”索引的工作原理相同，因为它是一个新的表，在 rowid 之前有一个额外的列，并且按该额外列作为主键排序。唯一的区别是，在 Idx2 中，第一列是“state”，而不是像 Idx1 中那样是“fruit”。在我们的示例数据集中，“state”列中存在更多冗余，因此存在更多重复条目。平局仍然使用 rowid 解决。

使用“state”上的新 Idx2 索引，SQLite 有另一种查找加州橙子价格的选择：它可以查找包含加州水果的所有行，并过滤掉不是橙子的行。

图形 9：加州橙子的索引查找

使用 Idx2 而不是 Idx1 会导致 SQLite 检查不同的行集，但最终会得到相同的结果（这一点非常重要 - 请记住，索引永远不会改变答案，只会帮助 SQLite 更快地获得答案），并且它执行了相同的工作量。因此，在这种情况下，Idx2 索引并没有帮助提高性能。

在我们的示例中，最后两个查询花费了相同的时间。那么，SQLite 会选择哪一个索引，Idx1 还是 Idx2 呢？如果在数据库上运行了 ANALYZE 命令，使 SQLite 有机会收集有关可用索引的统计信息，那么 SQLite 将知道 Idx1 索引通常会将搜索范围缩小到单个项目（我们示例中 fruit='Orange' 是此规则的例外），而 Idx2 索引通常只会将搜索范围缩小到两行。因此，如果其他条件都相同，SQLite 会选择 Idx1，希望能将搜索范围缩小到尽可能少的行数。这种选择只有在 ANALYZE 提供的统计信息的支持下才有可能。如果 ANALYZE 没有运行，那么选择使用哪个索引是任意的。

1.6. 多列索引

要从 WHERE 子句中包含多个 AND 连接项的查询中获得最大性能，您真正需要的是一个多列索引，其中包含每个 AND 项的列。在这种情况下，我们在 FruitsForSale 的 "fruit" 和 "state" 列上创建了一个新索引

CREATE INDEX Idx3 ON FruitsForSale(fruit, state);

图 1：双列索引

多列索引遵循与单列索引相同的模式；索引列被添加到 rowid 的前面。唯一的区别是现在添加了多个列。最左边的列是用于对索引中的行排序的主键。第二列用于打破最左边列的联系。如果存在第三列，则它将用于打破前两列的联系。以此类推，对于索引中的所有列都是如此。因为 rowid 保证是唯一的，所以即使两行的所有内容列都相同，索引的每一行也将是唯一的。这种情况在我们的示例数据中没有发生，但有一个情况 (fruit='Orange') 在第一列上存在联系，必须由第二列来打破。

有了新的多列 Idx3 索引，SQLite 现在可以通过仅执行两次二进制搜索来查找加州橙子的价格

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

图 11：使用双列索引查找

通过在 WHERE 子句约束的两个列上建立 Idx3 索引，SQLite 可以对 Idx3 进行一次二进制搜索，找到加州橙子的一行 rowid，然后对原始表进行一次二进制搜索，找到该项目的价钱。没有死胡同，也没有浪费二进制搜索。这是一种更有效的查询。

请注意，Idx3 包含与原始 Idx1 相同的所有信息。因此，如果我们有 Idx3，就不再真正需要 Idx1。通过简单地忽略 Idx3 的 "state" 列，可以使用 Idx3 满足 "桃子的价格" 查询

SELECT price FROM fruitsforsale WHERE fruit='Peach'

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

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

1.7. 覆盖索引

"加州橙子的价格" 查询通过使用双列索引变得更加高效。但是，SQLite 可以通过一个也包含 "price" 列的三列索引做得更好

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 连接项

多列索引只有在 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，以避免重复。但这只是一个实现细节。图表虽然不完全准确，但提供了一个很好的概述，说明了正在发生的事情。

为了使上面显示的 OR-by-UNION 技术有效，必须有一个索引可以帮助解决 WHERE 子句中的每个 OR 连接项。如果只有一个 OR 连接项没有索引，则必须进行完全表扫描才能找到由一个项生成的 rowid，如果 SQLite 必须进行完全表扫描，它也可以在原始表上进行，并在一次扫描中获得所有结果，而不必处理并集运算和后续的二进制搜索。

可以看到，OR-by-UNION 技术也可以用于使用多个索引来处理 WHERE 子句中包含 AND 连接项的查询，方法是在 union 运算符中使用交集运算符。许多 SQL 数据库引擎会这样做。但与仅使用一个索引相比，性能提升很小，因此 SQLite 目前没有实现这种技术。但是，未来的 SQLite 版本可能会增强以支持 AND-by-INTERSECT。

2. 排序

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 子句转换为无操作。如果 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;

图 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. 同时搜索和排序

之前的讨论将搜索和排序视为单独的主题。但在实践中，人们通常希望同时搜索和排序。幸运的是，可以使用一个索引来实现这一点。

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

假设我们想找到所有品种的橙子的价格，并按种植它们的州排序。查询如下

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

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

图 20：使用多列索引搜索和排序

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

您会注意到，上面的图表中没有任何 "排序" 框。查询的 ORDER BY 子句已成为无操作。这里不需要进行排序，因为输出顺序按 state 列，而 state 列恰好是索引中 fruit 列后的第一列。因此，如果我们从上到下扫描索引中具有相同 fruit 列值的条目，则这些索引条目保证按 state 列排序。

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

覆盖索引也可以用于同时搜索和排序。请考虑以下内容

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. 使用索引进行部分排序（也称为块排序）

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

SELECT * FROM fruitforsale ORDER BY fruit, price

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

图 22：通过索引进行部分排序

在示例中，不是对 7 个元素进行一次排序，而是对每个水果执行 5 次对单个元素的排序，以及对水果=='橙子'的情况进行 1 次对 2 个元素的排序。

与执行一次大型排序相比，执行多次小型排序的优势在于

多个小型排序总共使用的 CPU 周期少于一次大型排序。
每个小型排序独立运行，这意味着在任何时候都需要保存在临时存储中的信息量要少得多。
由于索引已经处于正确顺序的 ORDER BY 的那些列可以从排序键中省略，从而进一步减少存储需求和 CPU 时间。
输出行可以在每个小型排序完成后返回到应用程序，并在表扫描完成之前很久。
如果存在 LIMIT 子句，则可能可以避免扫描整个表。

由于这些优点，即使无法通过索引进行完全排序，SQLite 也会始终尝试使用索引进行部分排序。

4. WITHOUT ROWID 表

上面描述的基本原则适用于普通 rowid 表和 WITHOUT ROWID 表。唯一的区别是，作为表键并且作为索引中最右侧项出现的 rowid 列被 PRIMARY KEY 替换。

此页面最后修改于 2022-10-26 13:30:36 UTC