Small. Fast. Reliable.
Choose any three.
Choose any three.
SQL的最佳功能（在所有实现中，不仅限于SQLite）是它是说明性语言，而不是过程 语言。当SQL编程，你告诉系统什么要计算，而不是如何计算它。确定如何将其委派给SQL数据库引擎内的查询计划程序子系统的任务。
对于任何给定的SQL语句，执行操作的可能有成百上千或什至数百万种不同的算法。所有这些算法都会得到正确的答案，尽管有些算法的运行速度会比其他算法快。查询计划程序是一种 AI，它会尝试为每个SQL语句选择最快，最高效的算法。
在大多数情况下，SQLite中的查询计划器做得很好。但是，查询计划者需要索引才能使用。这些索引通常必须由程序员添加。很少，查询计划程序AI会选择次优的算法。在这种情况下，程序员可能希望提供其他提示，以帮助查询计划者做得更好。
本文档提供有关SQLite查询计划程序和查询引擎如何工作的背景信息。程序员可以使用此信息来帮助创建更好的索引，并在需要时提供提示以帮助查询计划者。
SQLite查询计划程序和 下一代查询计划程序文档中 提供了其他信息 。
SQLite中的大多数表由零个或多个行组成，带有唯一的整数键（rowid或INTEGER PRIMARY KEY），后跟内容。（例外是WITHOUT ROWID表。）按逻辑上的顺序，以增加rowid的顺序存储行。例如，本文使用名为“ FruitsForSale”的表，该表将各种水果与它们的生长州和市场单价相关。模式是这样的：
创建表FruitsForSale（ 水果TEXT， 状态TEXT， 价格实 ）; |
对于某些（任意）数据，这样的表可能逻辑上存储在磁盘上，如图1所示：
在此示例中，行标识不是连续的，但是它们是有序的。SQLite通常创建的rowid以1开头，每增加一行增加1。但是，如果删除行，则序列中可能会出现空格。并且应用程序可以根据需要控制分配的rowid，从而不必在底部插入行。但是无论发生什么情况，rowid始终都是唯一的，并且严格按升序排列。
假设您要查询桃子的价格。该查询将如下所示：
从Fruitsforsale选择价格，WHERE fruit ='Peach'; |
为了满足此查询，SQLite从表中读取每一行，检查“水果”列是否具有“桃子”值，如果是，则从该行输出“价格”列。下面的图2说明了该过程。这种算法称为全表扫描， 因为必须读取并检查表的整个内容才能找到感兴趣的一行。对于只有7行的表，可以接受全表扫描，但是如果表包含700万行，则全表扫描可能会读取兆字节的内容，以便找到一个8字节的数字。因此，通常会尝试避免进行全表扫描。
避免全表扫描的一种技术是按rowid（或等效的INTEGER PRIMARY KEY）进行查找。要查询桃子的价格，可以查询一个rowid为4的条目：
从Fruitsforsale的WHERE rowid = 4中选择价格； |
由于信息按行ID顺序存储在表中，因此SQLite可以使用二进制搜索找到正确的行。如果表包含N个元素，则查找所需行所需的时间与logN成正比，而不是像在全表扫描中一样与N成正比。如果该表包含1000万个元素，则意味着查询的数量级为N / logN或快一百万倍。
通过rowid查找信息的问题在于，您可能不在乎“项目4”的价格是多少-您想知道桃子的价格。因此，rowid查找无济于事。
为了使原始查询更有效，我们可以在“ fruitsforsale”表的“ fruit”列上添加索引，如下所示：
在fruitforsale（fruit）上创建索引IDx1； |
索引是另一个与原始“ fruitsforsale”表相似的表，但是内容（在这种情况下为“水果”列）存储在rowid的前面，并且所有行均按内容顺序排列。 图4给出了Idx1索引的逻辑视图。“水果”列是用于对表中的元素进行排序的主键，而“行”列是用于在两行或更多行具有相同的“水果”时打破平局的辅助键。在该示例中，该行标识必须用作“橙色”行的平局决胜局。请注意，由于rowid在原始表的所有元素上始终都是唯一的，因此“ fruit”后跟“ rowid”的复合键在索引的所有元素上都是唯一的。
此新索引可用于为原始“桃子价格”查询实现更快的算法。
从Fruitsforsale选择价格，WHERE fruit ='Peach'; |
该查询从对Idx1索引进行二进制搜索开始，以查找具有fruit ='Peach'的条目。SQLite可以在Idx1索引上执行此二进制搜索，但不能在原始FruitsForSale表上执行此二进制搜索，因为Idx1中的行按“水果”列排序。在Idx1索引中找到具有fruit ='Peach'的行后，数据库引擎可以提取该行的rowid。然后，数据库引擎对原始的FruitsForSale表进行第二次二进制搜索，以找到包含fruit ='Peach'的原始行。然后，从FruitsForSale表的行中，SQLite可以提取price列的值。该过程由图5示出。
SQLite必须使用上面显示的方法进行两次二进制搜索才能找到桃子的价格。但是对于具有大量行的表，这仍然比进行全表扫描要快得多。
在上一个查询中，fruit ='Peach'约束将结果缩小为单行。但是，即使获得多行，相同的技术也可以工作。假设我们查找橙子而不是桃子的价格：
从Fruitsforsale那里选择价格WHERE fruit ='Orange' |
在这种情况下，SQLite仍会执行单个二进制搜索来查找索引的第一个条目，其中fruit ='Orange'。然后，它从索引中提取rowid，并使用该rowid通过二进制搜索查找原始表条目，并从原始表中输出价格。但是，数据库引擎没有退出，而是前进到索引的下一行，以对下一个水果=“ Orange”条目重复该过程。前进到索引（或表）的下一行比进行二进制搜索要便宜得多，因为下一行通常与当前行位于同一数据库页面上。实际上，与二进制搜索相比，前进到下一行的成本是如此之低，以至于我们通常会忽略它。因此，我们估计此查询的总费用为3次二进制搜索。
接下来，假设您不仅要查找任何橙子的价格，而且还要查找加利福尼亚州种植的橙子的价格。适当的查询如下：
从fruitsforsale选择价格，其中fruit ='Orange'AND state ='CA' |
此查询的一种方法是使用WHERE子句的fruit ='Orange'术语查找涉及橙子的所有行，然后通过拒绝来自加利福尼亚州以外州的任何行来过滤这些行。上面的图7显示了此过程。在大多数情况下，这是一种完全合理的方法。是的，数据库引擎确实必须对后来被拒绝的佛罗里达橙行进行额外的二进制搜索，因此它的效率不如我们希望的那样，尽管对于许多应用程序来说，它的效率已经足够高。
假设除了“水果”的索引外，还有“状态”的索引。
在fruitforsale（state）上创建索引IDx2； |
“状态”索引的工作方式类似于“水果”索引，因为它是一个新表，在rowid前面有一个额外的列，并按该额外的列作为主键进行排序。唯一的区别是，在Idx2中，第一列是“状态”，而不是Idx1中的“水果”。在我们的示例数据集中，“状态”列中存在更多的冗余，因此它们是重复项。仍然使用rowid解决联系。
使用“ state”上新的Idx2索引，SQLite可以选择另一个查询加州橙子的价格：它可以查询包含加州水果的每一行，并过滤掉那些不是橙子的行。
使用Idx2而不是Idx1会使SQLite检查不同的行集，但最终得到的答案是相同的（这很重要-请记住，索引永远不要更改答案，而只能帮助SQLite更快地找到答案）并且完成相同的工作量。因此，在这种情况下，Idx2索引对性能没有帮助。
在我们的示例中，最后两个查询花费相同的时间。那么，SQLite将选择哪个索引Idx1或Idx2？如果 ANALYZE命令已在数据库上运行，则SQLite有机会收集了有关可用索引的统计信息，则SQLite将知道Idx1索引通常将搜索范围缩小到单个项目（我们的fruit ='示例）。橙色”是该规则的例外），而Idx2索引通常只会将搜索范围缩小到两行。因此，如果其他所有条件都相等，则SQLite将选择Idx1，希望将搜索范围缩小到尽可能少的行数。由于ANALYZE提供的统计信息，因此只能进行此选择。如果分析 尚未运行，则使用哪个索引的选择是任意的。
为了在WHERE子句中使用多个与AND相连的术语来从查询中获得最大性能，您确实想要一个多列索引，其中每个AND术语都带有列。在这种情况下，我们在FruitsForSale的“ fruit”和“ state”列上创建一个新索引：
在FruitsForSale（水果，州）上创建索引IDx3； |
多列索引遵循与单列索引相同的模式；索引列将添加到rowid的前面。唯一的区别是现在添加了多列。最左边的列是用于对索引中的行进行排序的主键。第二列用于打破最左边一列的关系。如果有第三列，则用于断开前两列的联系。对于索引中的所有列，依此类推。因为保证rowid是唯一的，所以即使两行的所有内容列都相同，索引的每一行也将是唯一的。在我们的样本数据中不会发生这种情况，但是在一种情况下（fruit ='Orange'），第一列上有一个平局，第二列必须打破平局。
给定新的多列Idx3索引，SQLite现在可以仅使用2个二进制搜索来找到加利福尼亚橘子的价格：
从fruitsforsale选择价格，其中fruit ='Orange'AND state ='CA' |
借助受WHERE子句约束的两列上的Idx3索引，SQLite可以对Idx3进行一次二进制搜索，以查找加利福尼亚橘子的一个rowid，然后进行一次二进制搜索，以在原始表中查找该商品的价格。没有死角，也没有浪费的二进制搜索。这是一个更有效的查询。
请注意，Idx3包含与原始Idx1相同的所有信息 。因此，如果我们拥有Idx3，我们将不再真正需要Idx1。只需忽略Idx3的“状态”列，就可以使用Idx3满足“桃子的价格”查询：
从Fruitsforsale那里选择价格WHERE fruit ='Peach' |
因此，一个很好的经验法则是您的数据库架构永远不应包含两个索引，其中一个索引是另一个的前缀。用较少的列删除索引。SQLite仍然可以使用更长的索引进行有效的查找。
通过使用两列索引，使“加利福尼亚橘子的价格”查询更加有效。但是SQLite使用三列索引（其中还包含“价格”列）可以做得更好：
在FruitsForSale（水果，州，价格）上创建索引IDx4； |
此新索引包含查询使用的原始FruitsForSale表的所有列-搜索词和输出。我们称其为“覆盖指数”。由于所需的所有信息都在覆盖索引中，因此SQLite无需查询原始表即可查找价格。
从fruitforsale选择价格，其中fruit ='Orange'AND state ='CA'; |
因此，通过在索引的末尾添加额外的“输出”列，可以避免不得不引用原始表，从而将查询的二进制搜索次数减少了一半。这是性能的恒定因素提高（速度大约提高了一倍）。但另一方面，这也只是一种改进。两倍的性能提升远不及表首次建立索引时的百万倍增长那么引人注目。对于大多数查询，不太可能注意到1微秒和2微秒之间的差异。
仅当查询的WHERE子句中的约束项通过AND连接时，多列索引才有效。因此，Idx3和Idx4在搜索既是橙子又是加利福尼亚州的商品时很有帮助，但是如果我们希望所有都是橙子或加利福尼亚州的商品，则两个索引都没有用 。
从FruitsForSale选择价格，其中fruit ='Orange'或state ='CA'; |
当在WHERE子句中遇到与OR相关的术语时，SQLite会分别检查每个OR术语，并尝试使用索引查找与每个术语相关联的rowid。然后，它使用结果行标识符集的并集来查找最终结果。下图说明了此过程：
上图暗示SQLite首先计算所有rowid，然后将它们与联合操作组合在一起，然后再开始在原始表上进行rowid查找。实际上，rowid查找散布着rowid计算。SQLite一次使用一个索引来查找rowid，同时记住它之前曾查看过哪些rowid，以避免重复。不过，这只是一个实现细节。该图虽然不是100％准确，但可以很好地概述正在发生的事情。
为了使上面显示的OR-by-UNION技术有用，必须有一个可用的索引来帮助解析WHERE子句中的每个OR连接项。如果甚至没有为一个或与OR相关的术语建立索引，则必须进行全表扫描才能找到由一个术语生成的行ID，并且如果SQLite必须进行全表扫描，那么它也可能会做并将其放在原始表上，并一次性获得所有结果，而不必弄乱联合操作和后续的二进制搜索。
可以看到，通过使用相交运算符代替并集，还可以利用OR-by-UNION技术在WHERE子句具有由AND连接的条件的查询上使用多个索引。许多SQL数据库引擎都可以做到这一点。但是仅使用单个索引带来的性能提升很小，因此SQLite目前未实现该技术。但是，将来的SQLite版本可能会得到增强，以支持AND-by-INTERSECT。
SQLite（像所有其他SQL数据库引擎一样）除了加快查找速度外，还可以使用索引来满足查询中的ORDER BY子句。换句话说，索引可用于加快排序和搜索速度。
如果没有合适的索引可用，则带有ORDER BY子句的查询必须作为单独的步骤进行排序。考虑以下查询：
选择*从Fruitsforsale订购水果; |
SQLite通过收集所有查询输出，然后通过分类程序运行该输出来处理此问题。
如果输出行数为K，则排序所需的时间与KlogK成比例。如果K小，排序时间通常不是一个因素，但是在诸如K == N的上述查询中，排序所需的时间可能比进行全表扫描所需的时间长得多。此外，整个输出都存储在临时存储（取决于各种编译时和运行时设置，可能存储在主存储器中或磁盘上）中，这意味着需要大量的临时存储才能完成查询。
由于排序可能会很昂贵，因此SQLite会努力将ORDER BY子句转换为无操作。如果SQLite确定输出自然会按照指定的顺序出现，则不会进行排序。因此，例如，如果您以rowid顺序请求输出，则不会进行排序：
SELECT * FROM fruitforsale ORDER BY rowid; |
您还可以请求像这样的逆序排序：
SELECT * FROM fruitforsale ORDER BY rowid DESC; |
SQLite仍将省略排序步骤。但是为了使输出以正确的顺序出现，SQLite将从表的末尾开始到表头开始进行表扫描，而不是如图17所示从表头开始到末尾进行表扫描 。
当然，按rowid排序查询的输出很少有用。通常情况下，您希望按另一列对输出进行排序。
如果索引在ORDER BY列上可用，则该索引可用于排序。考虑对所有按“水果”排序的项目的请求：
选择*从Fruitsforsale订购水果; |
从上到下（如果使用“ ORDER BY fruit DESC”，则从下到上）扫描Idx1索引，以便按水果顺序查找每个项目的行标识符。然后，对于每个rowid，执行二进制搜索以查找并输出该行。这样，输出将按请求的顺序显示，而无需收集整个输出并使用单独的步骤对其进行排序。
但这真的可以节省时间吗？原始无索引排序的步骤数与 NlogN成正比，因为那是对N行进行排序所花费的时间。但是，当我们使用Idx1时（如此处所示），我们必须进行N个rowid查找，每次查找耗时logN，因此NlogN的总时间是相同的！
SQLite使用基于成本的查询计划器。当有两种或两种以上的方法来解决同一查询时，SQLite会尝试估计使用每个计划运行查询所需的总时间，然后使用估计成本最低的计划。成本主要是根据估计的时间来计算的，因此这种情况可以根据表的大小和可用的WHERE子句约束而定，以此类推。但是总的来说，如果没有其他原因，很可能会选择索引排序，因为它不需要在排序之前将整个结果集累积在临时存储区中，因此使用的临时存储区要少得多。
如果可以将覆盖索引用于查询，则可以避免多个rowid查找，并且查询成本会大大降低。
有了覆盖索引，SQLite可以简单地将索引从一端移到另一端，并按正比于N的时间传递输出，而无需分配大缓冲区来保存结果集。
先前的讨论将搜索和排序视为单独的主题。但是在实践中，通常情况下，人们希望同时进行搜索和排序。幸运的是，可以使用单个索引来执行此操作。
假设我们要查找各种橙子的价格，这些橙子的价格按其生长的州排序。查询是这样的：
从Fruitforsale选择价格，WHERE Fruit ='Orange'，按州订购 |
该查询在WHERE子句中包含搜索限制，在ORDER BY子句中包含排序顺序。使用两列索引Idx3可以同时完成搜索和排序。
该查询对索引进行二进制搜索，以找到具有fruit ='Orange'的行的子集。（因为水果列是索引的最左列，并且索引的行是按排序顺序排列的，所以所有这些行都是相邻的。）然后，它从上到下扫描匹配的索引行，以获取索引的行号。原始表格，并针对每个rowid在原始表格上进行二进制搜索以找到价格。
您会注意到，上图中的任何地方都没有“排序”框。查询的ORDER BY子句已成为空操作。此处无需进行排序，因为输出顺序是按状态列进行的，并且状态列也恰好是索引中水果列之后的第一列。因此，如果我们从顶部到底部扫描水果列具有相同值的索引条目，则保证这些索引条目按状态列排序。
一个覆盖索引也可用于在同一时间搜索和整理。考虑以下：
SELECT * FROM fruitforsale WHERE fruit ='Orange'ORDER BY状态 |
和以前一样，SQLite对覆盖索引中满足WHERE子句的行范围进行单个二进制搜索，从上到下进行扫描以获得所需的结果。保证满足WHERE子句的行是相邻的，因为WHERE子句是索引最左列的等式约束。通过从顶部到底部扫描匹配的索引行，可以确保按状态对输出进行排序，因为状态列是水果列右侧的下一个列。因此，结果查询非常有效。
SQLite可以为ORDER BY降序使用类似的技巧：
SELECT * FROM fruitforsale WHERE fruit ='Orange'ORDER BY state DESC |
遵循相同的基本算法，不同的是这次是从下到上而不是从上到下扫描索引的匹配行，因此状态将以降序显示。
有时，使用索引只能满足ORDER BY子句的一部分。例如，考虑以下查询：
选择*从水果出售按水果订购，价格 |
如果使用覆盖索引进行扫描，则“水果”列将自然以正确的顺序出现，但是当两行或多行具有相同的水果时，价格可能会乱序。发生这种情况时，SQLite会执行许多小的排序，一种是针对每种水果的不同值，而不是一种大的排序。下面的图22说明了该概念。
在示例中，对于Fruit =='Orange'的情况，不是每种元素只有7种，而是每种元素有5种单元素和2种元素有1种。
执行许多较小的排序而不是一个较大的排序的优点是：
由于这些优点，SQLite总是尝试使用索引进行部分排序，即使无法通过索引进行完全排序也是如此。
上述基本原理适用于普通rowid表和WITHOUT ROWID表。唯一的区别是，用作表键且在索引中最右边出现的rowid列被PRIMARY KEY取代。