The Next-Generation Query Planner

1.介绍

2.背景

2.1.SQLite中的查询计划

2.2.SQLite查询计划器稳定性保证

3.一个困难的案例

3.1.查询详情

3.2.并发症

3.3.查找最佳查询计划

3.4.N个最近邻或“N3”启发式

4.升级到NGQP的风险

4.1.案例研究：将化石升级为NGQP

4.2.解决问题

5.检查清单以避免或修复查询计划程序问题

6.总结

“查询计划者”的任务是找出最佳算法或“查询计划”来完成一条SQL语句。从SQLite 版本3.8.0（2013-08-26）开始，查询规划器组件已被重写，以便运行速度更快并生成更好的计划。重写被称为“下一代查询计划者”或“NGQP”。

本文概述了查询计划的重要性，描述了查询计划固有的一些问题，并概述了NGQP如何解决这些问题。

NGQP几乎总是比传统查询规划器更好。但是，可能存在传统应用程序不知不觉地依赖于传统查询规划器中的未定义和/或次优行为，并且在这些传统应用程序上升级到NGQP可能会导致性能下降。考虑这种风险，并提供一份清单，以降低风险并解决出现的任何问题。

本文件重点介绍NGQP。有关包含SQLite整个历史记录的SQLite查询规划器的更一般概述，请参阅“SQLite查询优化器概述”。

对于索引很少的单个表进行简单查询，对于最佳算法通常有明显的选择。但是对于更大和更复杂的查询，如具有许多索引和子查询的多路连接，可能有数百，数千或数百万个用于计算结果的合理算法。查询计划人员的工作是从众多可能性中选择单一的“最佳”查询计划。

查询计划人员使SQL数据库引擎非常实用而且功能强大。（所有SQL数据库引擎都是如此，而不仅仅是SQLite。）查询规划者将程序员从选择特定查询计划的麻烦中解脱出来，从而允许程序员将更多精力投入到更高级别的应用程序问题上，并提供对最终用户更有价值。对于查询计划选择显而易见的简单查询，这很方便，但不是非常重要。但随着应用程序和模式和查询变得越来越复杂，一个聪明的查询计划程序可以大大加速并简化应用程序开发工作。在告诉数据库引擎需要什么内容方面有惊人的力量，然后让数据库引擎找出检索该内容的最佳方式。

撰写一个好的查询计划是比科学更艺术。查询计划员必须使用不完整的信息。如果没有实际执行该计划，它无法确定任何特定计划需要多长时间。因此，在比较两个或更多计划以确定哪一个“最佳”时，查询计划员必须做出一些猜测和假设，这些猜测和假设有时会出错。一个好的查询计划人员经常会发现正确的解决方案，以至于应用程序员很少需要参与。

2.1.SQLite中的查询计划

SQLite使用嵌套循环计算联接，联接中每个表的一个循环。（可能为IN和OR操作符在WHERE子句中插入额外的循环，SQLite也会考虑这些循环，但为简单起见，我们将在本文中忽略它们。）每个循环可以使用一个或多个索引来加速搜索，或者循环可能是一个“全表扫描”，它读取表中的每一行。因此查询计划分解成两个子任务：

1. 选择各种循环的嵌套顺序

1. 为每个循环选择好的索引

选择嵌套顺序通常是更具挑战性的问题。一旦建立了连接的嵌套顺序，每个循环的索引选择通常是显而易见的。

2.2.SQLite查询计划者稳定性保证

当启用查询计划程序稳定性保证（QPSG）时，只要满足以下条件，SQLite将始终为任何给定的SQL语句选择相同的查询计划：

1. 数据库模式不会以显着的方式变化，例如添加或删除索引，

1. ANALYZE命令不会重新运行，

1. 使用相同版本的SQLite。

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问题。

3.1.查询详情

TPC-H Q8是一个八路连接。如上所述，查询规划器的主要任务是找出八个循环的最佳嵌套顺序，以尽量减少完成连接所需的工作。下图显示了TPC-H Q8的这个问题的简化模型：

在该图中，查询的FROM子句中的8个表中的每个表都由具有FROM-clause项的标签的大圆标识：N2，S，L，P，O，C，N1和R.弧在图中表示假设圆弧的原点位于外部循环中时计算每个项的估计成本。例如，将S循环作为内部循环运行到L的成本是2.30，而将S循环作为外部循环运行到L的成本是9.17。

这里的“成本”是对数的。使用嵌套循环，工作成倍增加，而不是增加。但习惯上考虑具有加性权重的图，因此图表显示了各种成本的对数。该图显示了S在L内的成本优势约为6.87，但是这意味着当S循环位于L循环内部而不是在其外部时，该查询运行速度提高约963倍。

标有“*”的小圆圈中的箭头表示运行每个循环的成本，没有依赖关系。外部循环必须使用这个* -cost。内循环可以选择使用* -cost或成本，假设其他条件之一在外循环中，无论哪个给出最佳结果。可以将*成本看作是表示多个弧的简短符号，其中一个来自图中的每个其他节点。该图因此是“完整的”，这意味着在图的每对节点之间在两个方向上都存在弧（一些显式的和一些暗示的）。

找到最佳查询计划的问题等同于通过图表找到一个最小成本路径，该路径恰好访问每个节点一次。

（注意：上面的TPC-H Q8图表中的成本估计是由查询规划器在SQLite 3.7.16中计算出来的，并使用自然对数进行转换。）

3.2.并发症

上面的查询计划问题的表述是一种简化。成本是估计值。在我们实际运行循环之前，我们无法知道运行循环的真正成本。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.3.查找最佳查询计划

在版本3.8.0（2013-08-26）之前，当搜索最佳查询计划时，SQLite始终使用“最近邻居”或“NN”启发式。NN启发式算法对图进行单遍历，总是选择成本最低的弧作为下一步。NN启发式在大多数情况下工作得非常好。NN很快，所以SQLite能够快速找到适用于大型64路连接的良好计划。相比之下，执行更广泛搜索的其他SQL数据库引擎往往会在连接中的表数量超过10或15时停滞不前。

不幸的是，由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（）的时间会变得非常大。

3.4.N个最近邻或“N3”启发式

NGQP使用一种新的启发式方法通过图表寻找最佳路径：“N个最近邻居”（以下简称“N3”）。对于N3，算法不是每个步骤只选择一个最近邻居，而是针对某个小整数N在每个步骤追踪N个最佳路径。

假设N=4。然后对于TPC-H Q8图，第一步找到四条最短路径来访问图中的任何单个节点：

R (cost: 3.56) N1 (cost: 5.52) N2 (cost: 5.52) P (cost: 7.71)

第二步找到四条最短路径，从上一步的四条路径之一开始访问两个节点。在两个或更多路径相同的情况下（它们具有相同的访问节点集合，但可能以不同的顺序），只保留第一条和成本最低的路径。我们有：

R-N1 (cost: 7.03) R-N2 (cost: 9.08) N2-N1 (cost: 11.04) R-P {cost: 11.27}

第三步从四个最短的双节点路径开始，找到四个最短的三节点路径：

R-N1-N2 (cost: 12.55) R-N1-C (cost: 13.43) R-N1-P (cost: 14.74) R-N2-S (cost: 15.08)

等等。TPC-H Q8查询中有8个节点，因此该过程总共重复8次。在K路连接的一般情况下，存储需求为O（N），计算时间为O（K * N），这比O（2K）精确解明显快得多。

但是选择N值有什么价值？有人可能会尝试N = K。这使得算法O（K2）实际上仍然非常有效，因为K的最大值是64并且K很少超过10.但是这对于TPC-H Q8问题是不够的。在TPC-H Q8上N = 8时，N3算法找到解决方案R-N1-COLS-N2-P，成本为29.78。这对NN来说是一个很大的改进，但它仍然不是最优的。当N为10或更大时，N3找到TPC-H Q8的最佳解决方案。

对于简单查询，NGQP的初始实施选择N = 1，对于双向连接N = 5，对于具有三个或更多个表的所有连接，N = 10。此选择N的公式可能会在后续版本中更改。

对于大多数应用程序，从传统查询规划人员升级到NGQP需要很少的思考或努力。只需将较旧的SQLite版本替换为较新版本的SQLite并重新编译，应用程序运行速度就会更快。没有API更改或编辑过程的修改。

但是，如同任何查询计划者的变更一样，升级到NGQP确实带来了引入绩效回归的小风险。这里的问题并不是NGQP不正确或者错误或者比传统查询规划器差。给出有关指数选择性的可靠信息，NGQP应该总是选择一个与以前一样好或更好的计划。问题在于某些应用程序可能使用低质量和低选择性的索引而未运行ANALYZE。较早的查询计划人员针对每个查询查看的可能实现数量较少，因此他们可能因愚蠢的运气而绊倒了一个好计划。另一方面，NGQP着眼于更多的查询计划可能性，并且可以选择理论上更好的不同查询计划，假设索引良好，但在实践中给出了性能回归，

关键点：

• 只要能够访问SQLITE_STAT1文件中的精确ANALYZE数据，NGQP将始终找到与以前的查询计划相比相同或更好的查询计划。

• 只要模式不包含索引最左列中具有相同值的约10或20行以上的索引，NGQP将始终找到一个好的查询计划。

并非所有应用都符合这些条件。幸运的是，即使没有这些条件，NGQP通常仍会找到好的查询计划。但是，在可能发生性能衰退的情况下（很少）会出现这种情况。

4.1.案例研究：将化石升级为NGQP

所述Fossil DVCS是用于追踪所有SQLite的源代码的版本控制系统。Fossil存储库是一个SQLite数据库文件。（请读者作为独立练习来思考这种递归。）Fossil既是SQLite的版本控制系统，也是SQLite的测试平台。无论何时对SQLite进行增强，Fossil都是首批测试和评估这些增强功能的应用程序之一。所以Fossil是NGQP的早期采用者。

不幸的是，NGQP导致化石业绩回落。

Fossil提供的许多报告之一是对单个分支进行更改的时间表，显示该分支内外的所有合并。有关此类报告的典型示例，请参阅http://www.sqlite.org/src/timeline?nd&n=200&r=trunk。生成这样的报告通常只需要几毫秒。但是在升级到NGQP后，我们注意到这个报告对于存储库的主干来说接近10秒。

下面显示了用于生成分支时间轴的核心查询。（读者不需要了解这个查询的详细信息，评论会随之而来。）

这个查询并不是特别复杂，但即使如此，它也可以取代数百甚至数千行程序代码。查询的要点是：查看EVENT表，查找满足以下三个条件中的任何一个的最近200次签入：

1. check-in 有一个“trunk”标签。

2. check-in 有一个有“trunk”标签的孩子。

3. check-in 有一个有“trunk”标签父母。

第一种情况导致显示所有的干线检入，并且还包括合并到干线或从干线分叉的第二和第三原因检入。这三个条件是由查询的WHERE子句中的三个OR连接的EXISTS语句实现的。NGQP发生的放缓是由第二和第三个条件造成的。每个问题都是一样的，所以我们只考察第二个问题。第二个条件的子查询可以重写（具有较小的和非实质性的简化），如下所示：

PLINK表包含签入之间的父子关系。TAGXREF表将标签映射到签入。作为参考，这里显示了这两个表的模式的相关部分：

只有两种合理的方式来实现这个查询。（还有很多其他可能的算法，但其他算法都不是“最佳”算法的竞争者。）

1. 查找所有入住$ ckid的孩子并测试每一个孩子是否有$ trunk标签。

2. 使用$ 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。规划问题的图形如下所示：

在左侧的“without ANALYZE”情况下，NN算法选择环路P（PLINK）作为外环，因为4.9小于5.2，导致路径PT为算法-1。神经网络只考虑每一步的单一最佳选择，因此它完全忽略了5.2 + 4.4比4.9 + 4.8稍微便宜一些的事实。但是N3算法跟踪2路加入的5条最佳路径，所以它最终选择了路径TP，因为它的总体成本稍低。路径TP是算法2。

请注意，使用ANALYZE，成本估算与实际情况更好地一致，算法-1由NN和N3选择。

（注：最近两个图表中的成本估算是由NGQP使用基于2的对数计算的，并且与传统查询规划器相比略有不同的成本假设计算出来，因此后两个图表中的成本估算不是直接可比的到TPC-H Q8图表中的成本估算。）

4.2。解决问题

在存储库数据库上运行ANALYZE可立即解决性能问题。然而，我们希望化石能够健壮并且始终快速工作，而不管其储存库是否已经被分析。由于这个原因，查询被修改为使用CROSS JOIN运算符而不是普通的JOIN运算符。SQLite不会重新排列CROSS JOIN的表。这是SQLite的一个长期特性，专门设计用于让知识丰富的程序员执行特定的循环嵌套顺序。一旦连接变为CROSS JOIN（添加单个关键字），NGQP就不得不选择更快的算法-1，而不管是否使用ANALYZE收集统计信息。

我们说算法-1是“更快”的，但这不是严格的。算法-1在通用存储库中速度更快，但可以构建一个存储库，其中每个检入位于不同的唯一命名分支上，并且所有检入都是根检入的子项。在这种情况下，TAGXREF_I1会比PLINK_I1更具有选择性，算法2真的是更快的选择。然而，这样的存储库在实践中不太可能出现，因此使用CROSS JOIN语法对循环嵌套顺序进行硬编码对于这种情况下的问题是合理的解决方案。

1. 不要惊慌！查询计划人员选择劣质计划的情况实际上非常罕见。您不太可能在应用程序中遇到任何问题。如果你没有性能问题，你不需要担心这一点。

2. 创建适当的索引。大多数SQL性能问题不是由于查询规划问题而是因为缺乏适当的索引。确保索引可用于协助所有大型查询。大多数性能问题可以通过一个或两个CREATE INDEX命令来解决，而且不会更改应用程序代码。

3. 避免创建低质量的索引。。低质量索引（就本清单而言）是表中超过10或20行的索引最左列具有相同值的索引。特别是，避免使用布尔值或“枚举”列作为索引的最左列。本文前面部分描述的化石性能问题的产生是因为TAGXREF表中有超过一万个条目，TAGXREF_I1索引的最左列（TAGID列）的值相同。

4. 如果您必须使用低质量索引，请务必运行 ANALYZE。只要查询计划员知道索引质量低，低质量索引就不会混淆查询计划者。查询计划人员知道这一点的方式是由ANALYZE命令计算的SQLITE_STAT1表的内容。

当然，如果您首先在数据库中拥有大量内容，则ANALYZE只能有效地工作。当创建一个你希望积累大量数据的新数据库时，你可以运行命令“ANALYZE sqlite_master”来创建SQLITE_STAT1表，然后预填充SQLITE_STAT1表（使用普通的INSERT语句），其内容描述了一个典型的数据库应用程序 - 可能是在实验室中的模拟数据库上运行ANALYZE后提取的内容。

1. 仪器你的代码。添加逻辑可以让您快速而轻松地了解哪些查询需要花费太多时间。然后处理那些特定的查询。

2. 使用 不可能（） 和 可能性（） SQL函数。SQLite通常假设WHERE子句中不能被索引使用的条件具有很强的可能性。如果这种假设不正确，可能会导致不理想的查询计划。可能性（）和可能性（）SQL函数可用于向查询规划器提供有关WHERE子句条款的提示，这些条款可能不是真实的，从而有助于查询规划者选择最佳计划。

3. 使用 CROSS JOIN 语法对可能在未分析的数据库中使用低质量索引的查询实施特定的循环嵌套顺序。SQLite专门处理CROSS JOIN运算符，强制将表格向左移动，使其成为相对于右侧表格的外部循环。

如果可能，避免这一步，因为它击败了整个SQL语言概念的巨大优势之一，特别是应用程序员不需要参与查询计划。如果您确实使用了CROSS JOIN，那么请等到开发周期的后期才这样做，并仔细评论CROSS JOIN的使用情况，以便稍后尽可能将其取出。在开发周期的早期避免使用CROSS JOIN，因为这样做是过早的优化，这是众所周知的万恶之源。

1. 使用一元“+”运算符来取消WHERE子句的条件。如果查询计划人员在质量更高的索引可用时坚持为特定查询选择质量不佳的索引，那么仔细使用WHERE子句中的一元“+”运算符可能会强制查询计划员远离质量较差的问题指数。尽可能避免使用这种技巧，特别是在应用程序开发周期早期避免使用这种技巧。请注意，如果涉及类型关联，向等式表达式添加一元“+”运算符可能会更改该表达式的结果。

2. 使用 INDEXED BY 语法强制选择问题查询中的特定索引。和前两个子弹一样，如果可能的话避免这个步骤，特别是避免在开发早期进行，因为这显然是一个不成熟的优化。

SQLite中的查询规划器通常会为选择运行SQL语句的快速算法做出非常出色的工作。传统的查询计划者的确如此，对于新的NGQP更是如此。由于信息不完整，查询计划人员可能会选择不理想的计划，这可能会偶尔出现。对于NGQP，这种情况发生的频率要低于传统的查询规划器，但这种情况可能仍会发生。只有在极少数情况下，应用程序开发人员才需要参与并帮助查询规划人员做正确的事情。在通常情况下，NGQP只是SQLite的一项新增功能，使应用程序运行速度更快，并且不需要新的开发人员思考或操作。