查询规划器（译）

这是一篇 Query Planning 的译文。

目录

1. 查询
   1.1 无索引表查询
   1.2 使用 rowid 查询
   1.3 使用索引查询
   1.4 多行内容查找
   1.5 使用 AND 链接多个 WHERE 条件查询
   1.6 多列查询
   1.7 覆盖索引查询
   1.8 使用 OR 链接多个 WHERE 条件查询

2. 排序
   2.1 使用 rowid 排序
   2.2 使用索引排序
   2.3 覆盖索引排序

3. 查询并排序
   3.1 通过多列索引查询并排序
   3.2 通过覆盖索引查询并排序
   3.3 通过索引进行局部排序

4. 无 rowid 的表

概述

SQL 最主要的特征 （在 _所有_ 使用 SQL 语句的数据库中，不只是 SQLite）在于它是一中 表述式编程语言，而不是一种 过程化语言。在使用 SQL 时，你只需要告诉系统你想要计算什么，不需要描述如何去计算。计算结果的方式取决于 SQL 数据库引擎的内部查询规划器。

对于一条 SQL 语句，可能有成百上千种执行算法。所有的算法都可以计算出正确的结果，但是有的计算的快，有的计算的慢。查询规划器相当于一个 AI，为每条 SQL 语句尽可能规划最快的执行算法。

多数情况下，查询规划器在 SQLite 中表现的十分出色。但是查询规划器需要使用索引进行协助。这些索引需要由开发者在设计数据库时加上。有时候，查询规划器会选择次优算法，而不是最优的。这种情况下，需要开发者进行一些辅助操作来帮助查询规划器更好的工作。

这篇文章主要讲解了 SQLite 查询规划器和查询引擎背后的工作原理。有必要的时候，开发者可以根据这些原理更好地创建索引，帮助查询规划器高效地工作。

更多信息可以查看 SQLite query planner 和 next generation query planner.

1.查询

1.1 无索引表查询

在 SQLite 中，大多数表由一行或者多行组成，每一行都有一个独一无二的 key (rowid 或者 INTEGER PRIMARY KEY)(WITHOUT ROWID 表是一个特例)。这些数据通常会按照递增顺序排列。例如，这篇文章使用的表为 “FruitsForSale”，主要存储了各种各样的水果以及水果的产地和价格信息。表结构如下：

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

写入一些数据之后，这张表将以 figure 1 图中所示的形式存储于磁盘中：

Figure 1: “FruitsForSale” 表结构

在这个表里，rowid 并不是连续，但却是有序排列的。通常情况下，SQLite 创建一条数据时，这条数据的rowid 是在上一条 rowid 基础上加 1。如果某一行被删除，rowid 则会不连贯。如果有必要，创建一条数据时可以指定 rowid 的序号，并不是只能在末尾追加数据。但无论如何添加，每个 rowid 都是唯一的，有序排列的。

当你想查询桃子的价格，查询语句可能像下面这样：

SELECT price FROM fruitsforsale WHERE fruit='Peach';

为了满足这条查询，SQLite 会读取表中每一行数据，首先检索 ‘fruit’ 这一列看是否有一条数据的值为 ‘Peach’，如果有的话，输出这一条数据对应的 ‘price’ 的值。检索过程如图 figure2 所示。这种算法叫做 全表遍历 —— 需要读入整张表并检索。这个表只有 7 条数据，检索起来还好，但如果有 7 百万条数据，为了检索一条 8-byte 的数据需要读入并遍历 1M 的数据。为此，尽量避免全表遍历。

Figure 2: 全表遍历

1.2 使用 rowid 查询

使用 rowid 查询可以避免全表遍历 (等价于通过 INTEGER PRIMARY KEY 查询)。查询桃子的价格，直接检索 rowid 为 4 的数据即可：

SELECT price FROM fruitsforsale WHERE rowid=4;

因为每条数据是以 rowid 为顺序存储在表中的，SQLite 可以对这些数据进行二分查找。如果表中含有 N 条数据，查询一条数据的时间以 logN 为比例系数增长，而不是以 N 为比例系数增长。假如一个表中含有 1 千万条数据，这意味遍历全表操作时快了 N/logN 倍，也就是 1 百万倍的速度。

Figure 3: 通过 rowid 查询

1.3 使用索引查询

使用 rowid 查询固然很快，但当你不知道 rowid 时怎么办？这时使用 rowid 查询就不行了。

为提高查询速度，我们可以将 “fruitsforsalt” 表中 “fruit” 这一列设置为索引，像下面这样:

CREATE INDEX Idx1 ON fruitsforsale(fruit);

索引表是与原来的 “fruitsforsale” 表相关联的另外一张表，索引表中包含索引内容(这里指 fruit 这一列)和 rowid 这两列，其中索引内容在前，所有数据按照索引内容排序。Figure 4 中为索引表的结构。”fruit” 这一列作为主键，”rowid” 作为辅助索引，如果多条主键字段值相同，则用辅助索引进行区别。在下面示例中，”Ornage”字段值相同时，使用 rowid 区别。你可能注意到，在原始表中每条数据的 rowid 都是唯一的，所以通过 “fruit” 和 “rowid” 组成的复合键可以为每条数据确定一个唯一索引。

Figure 4: 索引表

使用索引可以更快的查询出 “桃子的价格” :

SELECT price FROM fruitsforsale WHERE fruit='Peach';

执行这条时，SQLLite 先在索引表中进行二分查找，找到 fruit=’Peach’，然后取出这一行的 rowid。使用 rowid 在原始表 ‘FruitForSale’ 中进行第二次二分查找。找到对应行之后，取出 price 字段值。检索过程如图 figure 5 所示。

Figure 5: 通过索引查找桃子的价格

为了查询桃子的价格， SQLite 进行了两次二分查找。对于含有大量数据的表，这种方式仍然要快于全表遍历。

1.4 多行查找

在前面的查询中，通过 fruit=’Peach’ 约束条件查询出了一条数据。但是有时候一个约束条件可能对应多条数据。例如，我们要查询橘子的价格，将会出现如下情况：

SELECT price FROM fruitsforsale WHERE fruit='Orange';

Figure 6: 通过索引查询橘子价格

在这里，SQLite 仍然是先进行一次二分查找，找到索引为 fruit=’Orange’ 的数据。然后取出 rowid，使用这个 rowid 去原始表再进行一次二分查找，找到对应的 price。之后 SQLite 并不会终止查询，而是继续去查询下一条符合条件的数据。使用二分查找，查询下一条数据的消耗远远小于第一次，因为第二条数据和第一条数据一般会在同一页内，就像上图展示的那样。这样第二次查找十分廉价，以致可以忽略不计。所以整个查询大约进行了三次二分查找。如果数据库中有 K 条数据符合条件，整个表总共有 N 条数据，那么一次查询所消耗时间的比例系数大约为 （K+1)*logN.

1.5 使用 AND 链接多个 WHERE 条件查询

接下来，你想要查询 California 生产的橘子的价格。查询条件如下所示：

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

Figure 7: 使用索引查询 California 生产的橘子的价格

一种查询路径是，先通过 fruit=’Orange’ 条件找出所有橘子的数据，然后过滤掉产地不是 California 的数据。查询过程如图 Figure 7 所示。多数情况这是一种合理的途径。但是，数据库需要做一次额外的二分查找来过滤掉产地为 Florida 的数据，并不是想象中那么高效。

既然可以将 “fruit” 这一列设置为索引，也可以考虑将 “state” 这一列设置为索引。

CREATE INDEX Idx2 ON fruitsforsale(state);

Figure 8: 将 State 这一列设置为索引

这个索引表中的 “state” 这一列和 Idx1 中的 “fruit” 类似，”state” 一列作为主键，”rowid” 一列作为辅助索引。在这个 model 中，”state” 这一列也有很多重复项，还是需要使用 “rowid” 来区分。

使用索引表 Idx2，SQLite 有了新的查询方式：先使用索引表找出 California 对应的行，然后过滤掉未生产橘子的行。

Figure 9: 使用索引查询 California 生产的橘子

这里与使用 idx1 查询最终得到的是相同的结果（使用索引是为了提高 SQLite 的查询速度，不应改变查询结果）。这两种索引方式工作量是相同的，所以在查询价格这个 case 上，使用 Idx2 并不能提高性能。

在本例中，最后这两种查询方式使用时间相同。我们应该使用哪种呢？如果 ANALYZE 命令开启，SQLite 可以收集使用索引表的统计信息。然后 SQLite 就会知道使用 Idx1 进行索引查询，多数情况下只会查询到一行数据（这个表中 fruit=’Orange’ 属于一种特殊情况）；而使用 Idx2 进行所用查询，很多情况会查询到两行数据。所以如果其他查询情况相同，SQLite 会选择 Idx1 进行索引查询，以减少查询到的行数。这种选择是由 ANALYZE 提供的。如果 ANALYZE 没有运行在数据库上，SQLite 选择每种查询方式的概率是一样的。

1.6 多列索引查询

为最大化提高 “AND 链接多个 WHERE 条件查询” 的性能，你需要设置根据 AND 的链接项建立一个多列索引表。在这里我们为 FruitsForSale 表中的 “fruit” 和 “state” 两列创建为一个索引表：

CREATE INDEX Idx3 ON FruitsForSale(fruit, state);

Figure 10: 两列索引

多列索引表的形式和单列索引表的形式相同，都是索引列在前，rowid 列在后。最左一列用来确定要查询的行数，第二列用来过滤不符合要求的行数。如果这里有三列，第三列则用来过滤前两列结果，以此类推。这种情况一般在我们这种简单数据模型中不会出现。但也有特例，如过滤条件为 fruit=’Orange’ 时会有两行数据，需要根据索引表中的第二列来过滤掉脏数据。因为 rowid 是唯一的，所以索引表中的每一行都是唯一的，尽管两行内容一样。

使用新的索引表 Idx3，SQLite 查询 California 生产的橘子的价格只需要两次二分查找：

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

Figure 11: 使用两列索引的索引表查询

在 Idx3 中使用 WHERE 约束进行查询，SQLite 只需要做一次二分查找就可以找出 “California 生产的橘子” 这一行对应的 rowid，然后再从原始的表中进行一次二分查找，找出对应橘子的价格。这是一种非常高效的查询方式。

既然 Idx3 中已经包含了 Idx1 中的所有信息，那么我们就不需要 Idx1 了。如果要查询 “桃子的价格”，可以忽略掉 “state” 字段，直接使用 Idx3 进行查询：

SELECT price FROM fruitsforsale WHERE fruit='Peach';

Figure 12: 使用 Idx3 进行查询

因此，在今后设计数据库时最好遵循这样一个原则：不要让一个索引表包含另外一个索引表。虽然 SQLite 对于较长索引仍然可以进行高效查找，但是在设计时尽可能减少索引表的列数。

1.7 覆盖索引

通过使用索引表 Idx3 查询 “California 生产的橘子的价格” 已经十分高效。但还可以提高：将 “price” 这一列加入索引表，使用含有 3 列选项的索引表：

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

Figure 13: 覆盖索引表

这个索引表中包含了 FruitesForSale 表中的所有字段。我们称这种查询方式为 “覆盖查询”。因为所有的字段信息都被设置为了索引。SQLite 不需要再查询原始表就可以查询出对应水果的价格。

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

Figure 14: 使用覆盖索引查询

将要查询的结果的那一列数据也加入到索引表中，这样就不用再与原始表相关联，也使二分查找次数减半。这种查询虽然使性能有了提升（查询大约速度提升一倍）。但是，这只是细微提升。在性能提升这一方面，提升一倍往往不如提升数百万倍。所以对于大多数查询来说，1 微秒与 2 微秒之间的的差异是微不足道的。

1.8 使用 OR 链接多个 WHERE 条件查询

多列索引表只适用于用 AND 连接的 WHERE 条件的查询。所以当约束条件为 California 生产和橘子 时 Idx3 和 Idx4 两个索引表才有帮助；当约束条件变为 California 生产或橘子 时，这两个索引表将不再有什么帮助。

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

当面对使用 OR 连接 WHERE 条件时，SQLite 会先通过索引表查询出每个条件对应行的 rowid。然后将这些 rowid 做一个并集，再去原始表中去查询。下面是查询过程：

Figure 15: 使用 OR 连接的查询

如上图所示，SQLite 首先查询出符合条件的 rowid，然后先将两部分做并集，再使用这些 rowid 去原始表中查询。这些 rowid 的排列是非常离散的，SQLite 使用索引查询一次 rowid 之后，会记住遍历过的索引，这样可以减少下次查询的计算量。当然，这只是其中一个实现细节。上图中不能表示完整的检索细节，但是展示了一个大概的过程。

上图所示的 OR-by-UNION 技术是很适用的，前提索引表中必须有满足条件的数据。如果索引表中没有满足 OR 连接的约束条件的数据，那么 SQLite 会去原始表中进行全表遍历。而不是通过 rowid 集合进行二分查找，这将十分耗费性能。

我们可以看到，OR-by-UNION 这个技术进行多索引查询时，实际上就是先通过索引表查询符合条件的 rowid，再将这些 rowid 进行 并集 操作；类似的，通过 AND 连接的 WHERE 条件的查询，也可以先通过索引表将符合条件的 rowid 查询出来，然后取 交集，很多 SQL 型数据库的原理就是这样的。但是是用单列索引的索引表和 OR-by-INTERSECT 进行 AND 查询，性能会比较差，所以一般都是使用多列索引进行 AND 查询。随着 SQLite 的不断优化，后序可能支持 OR-by-INTERSECT 查询。

2.排序

SQLite (像很多其他 SQL 数据库引擎一样) 可以使用索引进行 ORDER BY 查询，不仅加快查询速度。还可以加速排序速度。

如果没有索引进行辅助，一个 ORDERT BY 查询需要先进行排序。看一下下面这个语句：

SELECT * FROM fruitsforsale ORDER BY fruit;

SQLite 首先检索出所有结果，然后再通过使用一个 sorter 进行排序输出。

Figure 16: 无索引排序

如果要输出的行数为 K 条，那么排序所需时间的比例系数为 KlogK.如果 K 的值比较小，那么排序时间无足轻重。但是像上图所示那样 K==N,排序时间远远大于需要遍历全表的时间。此外，所有的检索结果都需要先放在临时缓存区（可能是运存或者硬盘缓存，依赖于编译时和运行时的设置），这意味着在语句执行完之前需要占据一块很大的缓存。

2.1 使用 rowid 排序

排序操作是十分昂贵的，SQLite 很难将 ORDER BY 转化为一个非耗时操作。如果 SQLite 要输出的数据已经排序好了，这样就不用进行排序了。例如，你如果你按照 rowid 的排序输出结果，就不需要进行排序：

SELECT * FROM fruitsforsale ORDER BY rowid;

Figure 17: 使用 rowid 进行排序检索

你也可以进行倒序检索：

SELECT * FROM fruitsforsale ORDER BY rowid DESC;

这样 SQLite 虽然不会进行排序。但是为了进行倒序输出，SQLite 需要从 table 最后一条开始向前遍历，而不是从前往后遍历。如图 Figure 17 所示。

2.2 使用索引排序

然而，在实际使用中，很少直接通过 rowid 进行有序输出。一般都是通过其他条件进行有序检索。如果一个索引可以适用于进行 ORDER BY 查询，那么这个索引也可以用来进行排序。例如，对 “fruit” 这一列排序进行输出：

SELECT * FROM fruitsforsale ORDER BY fruit;

Figure 18: 使用索引进行排序

首先从上向下遍历 Idx1 索引表（如果查询语句为 “ORDER BY fruit DESC” 则从下向上遍历），按顺序检索出每个 fruit 对应的 rowid。然后通过 rowid 在原始表中进行二分查找并输出对应的数据。因为从索引中检索 rowid 时已经排好顺序，所以直接按照 rowid 的排列顺序在原始表中将数据检索并输出即可，不需要将所有检索结果再次排序。

但是这样做真的节省时间吗？在本节开始时所描述的方式中，先对数据查找再排序，所需要的时间比例系数为 NlogN，因为这需要对 N 条数据进行排序。而通过 Idx 索引表进行有序查找，我们需要对 N 个 rowid 进行二分查找，每个查找时间为 logN，总时间的比例系数同样为 NlogN.

SQLite 的查询规划器遵循 “低成本原则”。当有两种甚至有更多种查询方式时，SQLite 会先对每一种查询方式进行时间预估，然后选择成本最低的那种方式。成本的高低大多数情况下由预估时间决定，所以最终选择哪种方式取决于要查询的表的大小和 WHERE 条件的复杂度。通常情况下，使用索引进行有序查找一般作为首选。主要原因在于，使用索引查找不需要额外的临时存储空间来对数据进行排序，可以减少内存消耗。

2.3 使用覆盖索引排序

如果覆盖索引可以用于查询，那么查询 rowid 这一步则可以省去，这样消耗成本急剧降低。

Figure 19: 使用覆盖索引进行有序查找

使用覆盖索引，SQLite 可以简单的对所有数据进行遍历，然后将结果输出，所需时间比例系数问 N。而且不需要额外开辟临时缓存区对数据进行排序。

3.同时进行查询和排序

前面针对查询和排序两个主题分别作了讲解。但是在实际使用中，开发者需要将查找和排序同时进行。幸运的是，通过单个索引就可以完成这个操作。

3.1 通过多列索引进行同时查找和排序操作

假如我们有这样一个需求：我们想要查询所有橘子的价格，并且按照橘子产地进行排序输出。查询语句如下：

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

这条查询语句中，既包含了查询，又包含了排序。使用索引表 Idx3 中的两列索引，可以将满足这两个条件的数据查询出来.

Figure 20: 使用多行索引进行查找并排序

查询过程中，SQLite 先进行一次二分查找，找到 fruit=’Orange’ 对应的 rowid。（因为 fruit 是最左端的一列，所以整个索引表就是按照 furit 的拼写顺序进行排序的，因此两个相同的 fruit 在表中也是相邻的。）然后使用 rowid 在原始表中进行二分查找，找出对应的水果的价格。

你可能注意到，这里没有任何排序过程。没有特意过程去执行 ORDER BY 操作。没有排序过程，是因为在 index 表中查出数据的时候就已经按照 state 排好顺序了。在一个索引表中，如果第一列的值相同（例如上图中的 ‘Orange’)，那么其对应的第二列的值也会像第一列那样按照顺序进行排列。所以，如果我们在一个索引表中遍历 fruit 值相同的两行，那么这两行数据的 state 列一定是按照顺序排列的。

3.2 使用覆盖索引进行查找和排序

覆盖索引也可以用来查找和排序，例如下面这样：

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

Figure 21: 使用覆盖索引进行查找并排序

按照之前说的，为满足 WHERE 条件约束，SQLite 会进行一次二分查找，从上向下遍历索引表，以找到符合条件的数据。如果 WHERE 条件所约束的值在索引表中有多条数据，那么这些条数据一定是相邻排列的。遍历时是按照从上向下顺序遍历的。因为 fruit 这一列后面一列就是 state，所以当 fruit 值相等时就会按照 state 这一列进行排列，以此类推。根据这个原理，查找出来的数据直接就是已经排好顺序的，十分高效。

SQLite 同样也可以进行降序查询：

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

基本原理是类似的，只不过这次是从下向上遍历，这样查询出来的数据也是降序排列的。

3.3 使用索引进行局部排序

有些情况下，索引表只能满足部分属性的排序。例如下面这个查询：

SELECT * FROM fruitforsale ORDER BY fruit, price;

如果使用覆盖索引表进行遍历，fruit 这一列肯定是按照顺序排列的，但是如果表中有多条 fruit 字段值相同的数据，它们的 price 字段值就不一定按照顺序排列了。当出现这种状况时，SQLite 会进行很多局部排序操作，每次只针对某个 fruit 进行排序，而不是针对整个表排序。Figure 22 展示了这一过程：

Figure 22: 使用索引进行局部排序

在这个示例中，并不是对 7 条数据进行整体排序，而是进行了 5 次单条排序（其实不用排）和 1 次两条排序（fruit=’Orange’ 这两条数据）。

进行多次局部排序，而不是进行整体排序的优点在于：

1. 相对于一次整体排序，多个局部排序同时进行可以减少 CPU 的时钟周期。
2. 每个局部排序可以很快运行完毕，这意味着不用将大量信息暂存到内存缓存中，减少内存的占用。
3. 有些 sort key 已经在索引表中排好顺序了，写 SQL 的可以省略，这样可以减少内存占用和 CPU 执行时间。
4. 每当一次局部排序完成，便会将数据返回给应用；整体查询需要遍历完整表才会将数据返回。前者更好。
5. 如果使用了 LIMIT 条件，还可以避免遍历整个表。

因为这些优点，SQLite 经常使用索引进行局部排序，而不是进行整体排序。

4.无 rowid 的表

以上描述的这些基本原则，同时适用于含有 rowid 的表和无 rowid 的表。唯一的不同就是，有 rowid 的表，rowid 这一列一般会作为一个表的键。创建索引表之后，rowid 会在所以表中最右端用来关联索引表和原始表，在索引表中它的位置会被主键代替。

参考文献

• https://www.sqlite.org/queryplanner.html