Small. Fast. Reliable.
Choose any three.
Choose any three.
“查询计划器”的任务是找出最佳算法或“查询计划”以完成一条SQL语句。从SQLite版本3.8.0（2013-08-26）开始，查询计划程序组件已被重写，以使其运行速度更快并生成更好的计划。重写称为“下一代查询计划程序”或“ NGQP”。
本文概述了查询计划的重要性，描述了查询计划固有的一些问题，并概述了NGQP如何解决这些问题。
NGQP几乎总是比旧式查询计划器更好。但是，可能存在遗留应用程序，这些遗留应用程序在不知不觉中依赖于遗留查询计划器中未定义和/或次佳的行为，并且在那些遗留应用程序上升级到NGQP可能会导致性能下降。考虑了此风险，并提供了一份清单以降低风险并解决确实出现的任何问题。
本文档重点介绍NGQP。有关包含SQLite整个历史记录的SQLite查询计划程序的更一般的概述，请参见“ SQLite查询优化器概述”和“索引的工作方式”文档。
对于对索引少的单个表的简单查询，通常最好的算法是显而易见的选择。但是对于较大和更复杂的查询（例如具有许多索引和子查询的多路联接），可能会有成百上千，成千上万或数百万的合理算法来计算结果。查询计划者的工作是从众多可能性中选择单个“最佳”查询计划。
查询计划者是使SQL数据库引擎如此有用和强大的原因。（对于所有SQL数据库引擎，而不仅仅是SQLite，这都是正确的。）查询计划器使程序员摆脱了选择特定查询计划的繁琐工作，从而使程序员可以将更多精力投入到更高级别的应用程序问题上，并提供解决方案。给最终用户更多的价值。对于简单的查询，查询计划的选择是显而易见的，这很方便，但并不是很重要。但是，随着应用程序，模式和查询变得越来越复杂，聪明的查询计划者可以极大地加快和简化应用程序开发的工作。即将告诉数据库引擎所需的内容，然后让数据库引擎找出检索该内容的最佳方法，具有惊人的威力。
编写一个好的查询计划器比科学还重要。查询计划程序必须使用不完整的信息。如果不实际运行某个计划，它将无法确定需要花费多长时间。因此，当比较两个或多个计划以找出哪个是“最佳”时，查询计划者必须做出一些猜测和假设，而这些猜测和假设有时会是错误的。一个好的查询计划者经常会找到正确的解决方案，以至于应用程序程序员很少需要介入。
SQLite使用嵌套循环计算联接，联接中的每个表都有一个循环。（可能在WHERE子句中为IN和OR运算符插入了其他循环。SQLite也考虑了这些循环，但为简单起见，在本文中我们将忽略它们。）在每个循环上可以使用一个或多个索引来加快搜索速度，或者循环可能是读取表中每一行的“全表扫描”。因此，查询计划分解为两个子任务：
通常，选择嵌套顺序是更具挑战性的问题。一旦建立了连接的嵌套顺序，对于每个循环的索引选择通常是显而易见的。
启用查询计划者稳定性保证（QPSG）时，SQLite将始终为任何给定的SQL语句选择相同的查询计划，只要：
默认情况下，禁用QPSG。可以在编译时使用SQLITE_ENABLE_QPSG编译时选项启用它，也可以在运行时通过调用sqlite3_db_config（db，SQLITE_DBCONFIG_ENABLE_QPSG，1,0）启用它。
QPSG意味着，如果您的所有查询在测试期间都能高效运行，并且您的应用程序未更改架构，则在将应用程序发布到以下版本后，SQLite不会突然决定开始使用其他查询计划，这可能会导致性能问题。用户。如果您的应用程序在实验室中可以工作，则部署后它将以相同的方式继续工作。
企业级客户端/服务器SQL数据库引擎通常不提供此保证。在客户端/服务器SQL数据库引擎中，服务器跟踪有关表大小和索引质量的统计信息，而查询计划程序则使用这些统计信息来帮助选择最佳计划。随着数据库中内容的添加，删除或更改，统计信息将不断发展，并可能导致查询计划者开始对某些特定查询使用不同的查询计划。通常，新计划对于不断发展的数据结构会更好。但是有时新的查询计划会导致性能下降。使用客户端/服务器数据库引擎时，通常会有一个数据库管理员（DBA）来处理这些罕见的问题。但是DBA无法解决SQLite等嵌入式数据库中的问题，
重要的是要注意，更改SQLite的版本可能会导致查询计划的更改。相同版本的SQLite始终会选择相同的查询计划，但是如果您重新链接应用程序以使用不同版本的SQLite，则查询计划可能会更改。在极少数情况下，SQLite版本更改可能会导致性能下降。这是您应该考虑将应用程序与SQLite静态链接的原因之一，而不是使用系统范围的SQLite共享库，这可能会在您不知情或无法控制的情况下发生变化。
“ TPC-H Q8”是来自交易处理性能委员会的测试查询 。SQLite 3.7.17和更早版本中的查询计划人员没有为TPC-H Q8选择好的计划。并且已经确定，对遗留查询计划器的任何调整都无法解决该问题。为了找到TPC-H Q8查询的良好解决方案，并继续提高SQLite查询计划器的质量，必须重新设计查询计划器。本节试图解释为什么需要重新设计，以及NGQP有何不同，并解决了TPC-H Q8问题。
TPC-H Q8是八向联接。如上所述，查询计划器的主要任务是找出八个循环的最佳嵌套顺序，以最大程度地减少完成联接所需的工作。下图显示了针对TPC-H Q8的此问题的简化模型：
在该图中，查询的FROM子句中的8个表中的每个表都由一个带有带有FROM子句项标签的大圆圈标识：N2，S，L，P，O，C，N1和R。图中的表示假设圆弧的原点在外循环中，计算每个项的估计成本。例如，将S循环作为L的内部循环运行的成本为2.30，而将S循环作为L的外部循环运行的成本为9.17。
这里的“成本”是对数的。使用嵌套循环时，功是相乘的，而不是相加的。但是习惯上考虑具有加法权重的图，因此该图显示了各种成本的对数。该图显示了S在L内大约6.87的成本优势，但是当S循环在L循环内而不是L循环外时，这意味着查询运行速度快963倍。
小圆圈中标有“ *”的箭头表示无依赖性地运行每个循环的成本。外循环必须使用此*成本。内循环可以选择使用* -cost或使用cost，也可以假设其他条件之一在外循环中，以效果最佳的一个为准。可以将*成本看作是表示多个弧的简写形式，每个弧都来自图中的其他每个节点。因此，该图是“完整的”，这意味着图中的每对节点之间在两个方向上都存在弧（有些弧度是隐含的，有些则是隐含的）。
找到最佳查询计划的问题等同于通过图中的一条成本最低的路径，该路径恰好访问每个节点一次。
（旁注：上面的TPC-H Q8图中的成本估算是由查询计划人员在SQLite 3.7.16中计算的，并使用自然对数进行转换。）
上面查询规划器问题的表示是一种简化。费用是估计数。在实际运行循环之前，我们不知道运行循环的真正成本是多少。SQLite根据在WHERE子句中找到的索引和约束的可用性来猜测运行循环的成本。这些猜测通常是很好的，但有时可能会落空。使用ANALYZE命令收集有关数据库的其他统计信息有时可以使SQLite更好地估算成本。
成本由多个数字组成，而不是如图所示的单个数字。SQLite针对在不同时间应用的每个循环计算几种不同的估计成本。例如，查询开始时仅发生一次“设置”成本。设置成本是为还没有索引的表计算自动索引的成本。然后就有了运行循环每个步骤的成本。最后，对循环产生的行数进行了估算，这是估算内部循环成本所需的信息。如果查询具有ORDER BY子句，则排序成本可能会起作用。
在一般查询中，依赖关系不必位于单个循环上，因此依赖关系矩阵可能无法表示为图形。例如，WHERE子句约束之一可能是Sa = L.b + Pc，这意味着S循环必须是L和P的内部循环。此类依赖关系无法绘制为图形，因为无法使用弧一次在两个或多个节点上起源。
如果查询包含ORDER BY子句或GROUP BY子句，或者查询使用DISTINCT关键字，则在图形中选择一条路径使行自然地以排序顺序出现是有利的，因此不需要单独的排序步骤。自动消除ORDER BY子句可能会产生很大的性能差异，因此这是在完整实现中需要考虑的另一个因素。
在TPC-H Q8查询中，建立成本可以忽略不计，所有依赖关系都在单个节点之间，并且没有ORDER BY，GROUP BY或DISTINCT子句。因此，对于TPC-H Q8，上图是对需要计算的值的合理表示。一般情况涉及很多额外的复杂性，为清楚起见，在本文的其余部分中忽略了这一点。
在版本3.8.0（2013-08-26）之前，SQLite在搜索最佳查询计划时始终使用“最近邻居”或“ NN”启发式方法。NN启发式算法遍历图形，始终选择成本最低的弧作为下一步。在大多数情况下，NN启发式方法的效果出奇地好。而且NN很快，因此SQLite甚至可以为大型64路联接快速找到好的计划。相反，当联接中的表数超过10或15时，其他进行更广泛搜索的SQL数据库引擎往往会陷入困境。
不幸的是，NN为TPC-H Q8计算的查询计划不是最佳的。使用NN计算的计划是R-N1-N2-SCOLP，成本为36.92。前一句中的符号表示R表在外循环中运行，N1在下一个内循环中，N2在第三个循环中，依此类推直到在最内循环中的P。通过图的最短路径（通过穷举搜索找到）是PLOC-N1-RS-N2，成本为27.38。差异似乎不大，但请记住，成本是对数的，因此最短路径比使用NN启发式算法找到的路径快近750倍。
解决此问题的一种方法是更改SQLite，以详尽搜索最佳路径。但是穷举搜索需要与K成正比的时间！（其中K是联接中的表数），因此当您超出10路联接时，运行sqlite3_prepare（）的时间将变得非常大。
NGQP使用一种新的启发式方法来搜索图中的最佳路径：“ N个最近的邻居”（以下称“ N3”）。使用N3时，算法不会为每个步骤仅选择一个最近的邻居，而是针对每个小整数N跟踪每一步的N条最佳路径。
假设N = 4。然后对于TPC-H Q8图，第一步是找到访问该图中任何单个节点的四个最短路径：
R（成本：3.56）
N1（成本：5.52）
N2（成本：5.52）
P（成本：7.71）
第二步找到从上一步的四个路径之一开始访问两个节点的四个最短路径。在两个或更多路径相等的情况下（它们具有相同的访问节点集，尽管顺序可能不同），仅保留第一条路径和成本最低的路径。我们有：
R-N1（费用：7.03）
R-N2（费用：9.08）
N2-N1（费用：11.04）
RP {费用：11.27}
第三步从四个最短的两节点路径开始，找到四个最短的三节点路径：
R-N1-N2（成本：12.55）
R-N1-C（成本：13.43）
R-N1-P（成本：14.74）
R-N2-S（成本：15.08）
依此类推。TPC-H Q8查询中有8个节点，因此此过程总共重复8次。在一般情况下，使用K向联接时，存储要求为O（N），计算时间为O（K * N），这比O（2 K）精确解要快得多。
但是为N选择什么值呢？可以尝试N = K。这使得算法O（K 2）实际上仍然非常有效，因为K的最大值为64，而K很少超过10。但这对于TPC-H Q8问题而言还不够。在TPC-H Q8上N = 8时，N3算法找到成本为29.78的解R-N1-COLS-N2-P。这是对NN的重大改进，但仍不是最佳选择。当N为10或更大时，N3找到TPC-H Q8的最佳解决方案。
NGQP的初始实现为简单查询选择N = 1，为双向联接选择N = 5，为具有三个或更多表的所有联接选择N = 10。在以后的版本中，用于选择N的公式可能会更改。
2018年11月24日更新：当NGQP是新的时，此部分很重要。但是已经过去了五年，NGQP已成功部署到数十亿台设备，并且每个人都进行了升级。升级的危险已消失。本节保留，仅供历史参考。现代读物可以跳到查询计划器清单。
对于大多数应用程序而言，从传统查询计划程序升级到NGQP几乎不需要花力气。只需用较新的SQLite版本替换较旧的SQLite版本并重新编译，应用程序将运行得更快。没有API更改，也没有对编译过程的修改。
但是，与任何查询计划程序更改一样，升级到NGQP确实会带来引入性能退化的小风险。这里的问题不是NGQP不正确，有错误或不如旧查询计划器。给定有关索引选择性的可靠信息，NGQP应该始终选择比以前更好或更好的计划。问题是某些应用程序可能在不运行ANALYZE的情况下使用了低质量和低选择性的索引。较老的查询计划者为每个查询查看的实现方式要少得多，因此，他们可能会因愚蠢的运气而无意中找到了一个好的计划。另一方面，NGQP考虑了更多的查询计划可能性，并且它可能会选择一个在理论上更有效的不同查询计划（假设索引很好），但是由于数据的形状，它实际上会导致性能下降。
关键点：
只要NGQP可以访问SQLITE_STAT1文件中的准确ANALYZE数据，与以前的查询计划者相比，它将始终找到一个相等或更好的查询计划。
NGQP始终会找到一个好的查询计划，只要该架构所包含的索引不超过大约10或20行，并且该索引的最左列中的值相同。
并非所有应用程序都满足这些条件。幸运的是，即使没有这些条件，NGQP仍然通常会找到好的查询计划。但是，确实有（很少）出现性能下降的情况。
所述化石DVCS是用于追踪所有SQLite的源代码的版本控制系统。Fossil存储库是一个SQLite数据库文件。（请读者考虑一下此递归是一项独立的练习。）Fossil既是SQLite的版本控制系统，也是SQLite的测试平台。每当对SQLite进行增强时，Fossil都是测试和评估这些增强的首批应用程序之一。因此，Fossil是NGQP的早期采用者。
不幸的是，NGQP导致Fossil的性能下降。
Fossil提供的众多报告之一是对单个分支进行更改的时间表，其中显示了该分支内外的所有合并。有关 此类报告的典型示例，请参见 http://www.sqlite.org/src/timeline?nd&n=200&r=trunk。生成此类报告通常只需几毫秒。但是在升级到NGQP之后，我们注意到该报告对存储库主干的花费接近10秒。
下面显示了用于生成分支时间轴的核心查询。（不希望读者理解此查询的详细信息。将在后面进行评论。）
选择
blob.rid AS blobRid，
uuid作为uuid，
datetime（event.mtime，'localtime'）AS时间戳，
合并（ecomment，comment）AS评论，
合并（euser，user）AS用户，
blob.rid IN叶AS叶，
bgcolor AS bgColor，
event.type AS eventType，
（选择group_concat（substr（tagname，5），'，'）
FROM标签，tagxref
标记名GLOB'sym- *'
AND tag.tagid = tagxref.tagid
AND tagxref.rid = blob.rid
AND tagxref.tagtype> 0）AS标签，
tagid AS tagid，
简短的AS简短的
event.mtime AS mtime
从事件CROSS JOIN Blob
在哪里blob.rid = event.objid
AND（EXISTS（SELECT 1 from tagxref
在哪里tagid = 11 AND tagtype> 0 AND rid = blob.rid）
或存在（从plink JOIN tagxref ON rid = cid中选择1
在哪里tagid = 11 AND tagtype> 0 AND pid = blob.rid）
或存在（从plink JOIN tagxref ON rid = pid中选择1
在哪里tagid = 11 AND tagtype> 0 AND cid = blob.rid））
ORDER BY event.mtime DESC
限度200；
这个查询并不是特别复杂，但是即使如此，它仍可以替换成百上千行的程序代码。该查询的要旨是：扫描EVENT表以查找满足以下三个条件之一的最新200个签入：
第一种情况导致显示所有后备箱登机手续，第二和第三种情况也包括合并到后备箱或从后备箱中派生的登机手续。这三个条件由查询的WHERE子句中的三个OR连接的EXISTS语句实现。NGQP发生的变慢是由第二种情况和第三种情况引起的。每个问题都是相同的，因此我们将仅研究第二个问题。可以重写第二个条件的子查询（具有次要的和非实质性的简化），如下所示：
选择1 FROM plink加入tagxref ON tagxref.rid = plink.cid WHERE tagxref.tagid = $ trunk AND plink.pid = $ ckid;
PLINK表保存签入之间的父子关系。TAGXREF表将标签映射到签入中。作为参考，此处显示了这两个表的模式的相关部分：
创建表plink（ pid整数参考 cid整数参考 ）; 在plink（pid，cid）上创建唯一索引plink_i1; 创建表tagxref（ tagid INTEGER REFERENCES标签， mtime TIMESTAMP， 除去INTEGER REFERENCE Blob， 唯一（rid，tagid） ）; 创建索引tagxref_i1 ON tagxref（tagid，mtime）;
只有两种合理的方法可以实现此查询。（还有许多其他可能的算法，但是其他算法都不是“最佳”算法的竞争者。）
查找所有签入$ ckid的子级，并测试每个子级是否具有$ trunk标签。
查找所有带有$ trunk标签的签到，并测试每个签到是否为$ ckid的子项。
凭直觉，我们人类知道算法1是最好的。每次签到可能会生几个孩子（最常见的情况是一个孩子），并且每个孩子都可以在对数时间内测试$ trunk标签。实际上，在实践中，算法1是更快的选择。但是NGQP没有直觉。NGQP必须使用硬数学，而算法2在数学上会稍好一些。这是因为，在没有其他信息的情况下，NGQP必须假定索引PLINK_I1和TAGXREF_I1具有相同的质量并且具有同等的选择性。算法2使用TAGXREF_I1索引的一个字段和PLINK_I1索引的两个字段，而算法1仅使用每个索引的第一个字段。由于算法2使用了更多的索引材料，因此NGQP可以正确地判断它是更好的算法。分数很接近，算法2勉强领先于算法1。但是算法2确实是这里的正确选择。
不幸的是，在此应用中，算法2的速度比算法1的慢。
问题在于索引的质量不相等。办理入住手续可能只有一个孩子。因此，PLINK_I1的第一个字段通常会将搜索范围缩小到仅一行。但是有成千上万个带有“ trunk”标签的签入，因此TAGXREF_I1的第一个字段对缩小搜索范围没有帮助。
除非已在数据库上运行ANALYZE，否则NGQP无法知道TAGXREF_I1在此查询中几乎没有用。该ANALYZE上的各种指标和存储这些统计数据的质量命令收集统计SQLITE_STAT1表。NGQP可以访问此统计信息，很容易就选择算法1作为最佳算法。
传统查询计划者为什么不选择算法2？容易：因为NN算法从未考虑过算法2。规划问题的图形如下所示：
在左侧的“无分析”情况下，NN算法选择循环P（PLINK）作为外部循环，因为4.9小于5.2，从而导致路径PT为算法-1。NN只看每一步的最佳选择，因此完全错过了5.2 + 4.4比4.9 + 4.8便宜一些的事实。但是N3算法会跟踪2路连接的5条最佳路径，因此由于总体成本略低，最终选择了路径TP。路径TP是算法2。
请注意，使用ANALYZE可以使成本估算更符合实际情况，并且NN和N3均选择算法1。
（旁注：两个最近的图表中的费用估算是由NGQP使用以2为底的对数和与传统查询计划器相比稍有不同的费用假设计算出来的。因此，后两个图表中的费用估算无法直接比较TPC-H Q8图表中的费用估算值。）
在存储库数据库上运行ANALYZE可立即解决性能问题。但是，我们希望Fossil健壮并始终快速运行，无论是否对其存储库进行了分析。因此，查询被修改为使用CROSS JOIN运算符，而不是普通的JOIN运算符。SQLite不会对CROSS JOIN的表重新排序。这是SQLite的一项长期功能，专门用于允许知识丰富的程序员强制执行特定的循环嵌套顺序。将联接更改为CROSS JOIN（添加单个关键字）后，无论是否使用ANALYZE收集了统计信息，NGQP都被迫选择更快的算法-1。
我们说算法1是“更快”的，但是严格来说并非如此。在通用存储库中，Algorithm-1的运行速度更快，但是可以构建一个存储库，在该存储库中，每个签入均位于不同的唯一命名分支上，并且所有签入都是根签入的子级。在这种情况下，TAGXREF_I1的选择将比PLINK_I1更具选择性，而算法2确实是更快的选择。但是，这样的存储库实际上不太可能出现，因此在这种情况下，使用CROSS JOIN语法对循环嵌套顺序进行硬编码是解决该问题的合理方法。
不要惊慌！ 查询计划者选择劣等计划的情况实际上很少见。您不太可能遇到应用程序中的任何问题。如果您没有性能问题，则无需担心任何这些问题。
创建适当的索引。 大多数SQL性能问题的出现不是由于查询计划程序问题，而是由于缺少适当的索引。确保索引可用于协助所有大型查询。大多数性能问题可以通过一个或两个CREATE INDEX命令解决，而无需更改应用程序代码。
避免创建低质量的索引。。低质量索引（出于此清单的目的）是指表中超过10或20行的索引最左列具有相同值的行。特别是，避免将布尔或“枚举”列用作索引的最左列。
由于在TAGXREF表中有一万个条目，而TAGXREF_I1索引的最左列（TAGID列）的值相同，因此出现了Fossil性能问题。
如果必须使用低质量的索引，请确保运行ANALYZE。 只要查询计划程序知道索引的质量较低，低质量的索引就不会混淆查询计划程序。查询计划者知道这一点的方式是通过ANALYZE命令计算的SQLITE_STAT1表的内容。
当然，只有在数据库中首先有大量内容的情况下，ANALYZE才有效地工作。当创建新数据库时，您希望该数据库会积累大量数据，可以运行命令“ ANALYZE sqlite_schema”来创建SQLITE_STAT1表，然后使用描述普通数据库内容的内容预填充SQLITE_STAT1表（使用普通的INSERT语句）。应用程序-也许是您在实验室中填充良好的模板数据库上运行ANALYZE之后提取的内容。
检测您的代码。 添加可让您快速轻松地了解哪些查询花费过多时间的逻辑。然后处理那些特定的查询。
使用不太可能（）和似然（） SQL函数。 SQLite通常假定索引无法使用的WHERE子句中的术语很有可能为真。如果此假设不正确，则可能导致查询计划不理想。在 不可能的（）和可能性（） SQL函数可用来提供线索约WHERE子句条件，也就是不正确的，从而帮助查询规划中选择最好的规划查询规划。
使用CROSS JOIN语法对可能在未分析的数据库中使用低质量索引的查询强制执行特定的循环嵌套顺序。 SQLite特别对待CROSS JOIN运算符，将左侧的表强制为相对于右侧的表的外循环。
尽可能避免执行此步骤，因为它破坏了整个SQL语言概念的巨大优势之一，特别是应用程序程序员无需参与查询计划。如果您确实使用了CROSS JOIN，请等到开发周期的晚些时候再使用，并仔细注释一下CROSS JOIN的用法，以便以后可以撤消。避免在开发周期的早期使用CROSS JOIN，因为这样做是过早的优化，众所周知这是万恶之源。
使用一元“ +”运算符取消WHERE子句条款的资格。 如果查询计划者在有更高质量的索引可用时坚持为特定查询选择劣质索引，则在WHERE子句中谨慎使用一元“ +”运算符会迫使查询计划者远离劣质索引 指数。尽可能避免使用此技巧，尤其是在应用程序开发周期的早期避免使用此技巧。请注意，如果涉及类型相似性，则在相等表达式中添加一元“ +”运算符可能会更改该表达式的结果 。
使用INDEXED BY语法来强制选择问题查询中的特定索引。 与前面的两个项目符号一样，如果可能，请避免执行此步骤，尤其是避免在开发初期进行此操作，因为这显然是过早的优化。
SQLite中的查询计划器通常会为选择运行SQL语句的快速算法做出出色的工作。对于旧式查询计划程序而言，这是正确的，对于新的NGQP，甚至更是如此。有时可能会由于信息不完整而使查询计划者选择次优计划。与传统查询计划程序相比，使用NGQP发生这种情况的频率更低，但是仍然可能发生。只有在极少数情况下，应用程序开发人员才需要参与并帮助查询计划者做正确的事情。在常见情况下，NGQP只是SQLite的一项新增强功能，它使应用程序运行得更快一些，并且不需要新的开发人员思考或采取任何行动。