1.0详解查询计划器的任务是找到最好的算法或“查询计划”来完成一条SQL语句。早在sqlite3.8.0版本中，部分查询计划器已被重写，使其运行速度更快并生成更好的查询计划。这种重写被称为“下一代查询规划器”或“ngqp”。本文概括了查询规划的重要性，提出了查询规划中固有的一些问题，并概述了ngqp如何解决这些问题。我们所知道的是ngqp（下一代查询规划器）几乎总是比旧版本的查询规划器更好。但是，某些应用程序可能在不知不觉中依赖了旧版本查询计划器中的一些不确定或不是很好的功能。这时候queryplanner更新为ngqp。这些应用程序可能会造成程序闪退现象。ngqp必须考虑到这个风险，提供一系列检查项来降低风险，解决可能出现的问题。在ngop上关注此文档。有关更一般的SQLite查询规划器的概述并涵盖SQLite的整个历史，请参阅：“SQLite查询优化器概述”。2.0背景对于具有简单的几个索引的单个表的查询，通常有一个明显的最佳算法可供选择。但对于更大、更复杂的查询，例如多个索引与子查询的多路连接，可能有数百、数千或数百万种合理的算法来计算结果。所以查询计划的工作是从许多可能性中选择一个“最佳”查询计划。查询规划器使sql数据库引擎如此有用和强大。（所有sql数据库引擎都是如此，不仅仅是sqlite。）查询计划器将程序员从选择特定查询计划的苦差事中解放出来。这使程序员可以将更多的精力集中在更高级别的应用程序问题上，并为最终用户提供更多价值。对于简单的查询，查询计划的选择是显而易见的、方便的，但不是很重要。但随着应用程序的发展，模式和查询将变得越来越复杂。巧妙的查询计划可以大大加快和简化应用程序开发的工作。告诉数据库引擎那里需要什么内容，然后让数据库引擎找出检索该内容的最佳方式，这是非常强大的。编写一个好的查询规划器与其说是科学，不如说是一门艺术。查询计划器必须具有不完整的信息。如果不实际运行该程序，它无法决定执行任何特定程序的频率。所以当比较两个或多个计划以找出哪个是“最佳”时，查询计划器会做出一些假设和猜测，而这些假设和猜测有时是错误的。一个好的查询计划需要找到正确的解决方案，而这些问题很少被程序员考虑。2.1sqlite中的Queryplannersqlite的计算使用了nestedloopjoins，每个目标连接在一个循环中（额外的循环可能会在where语句中插入inandor运算符。sqlite认为那些考虑太多了，但是为了简单起见，在本文中我们可以忽略它。）在每个循环中，使用一个或多个索引，并加速搜索，或者一个循环可能是“全表扫描”以读取每一行中的表。因此，查询规划分为两个子任务：选择各种循环的嵌套顺序。为每个循环选择一个好的索引。选择嵌套顺序通常是更具挑战性的问题。一旦建立了连接的嵌套顺序，每个循环索引的选择通常是显而易见的。2.2sqlitequeryplanner稳定性保证对于给定的任何sql语句，sqlite通常会选择相同的查询计划如果：数据库的schema没有发生明显的变化，比如增加或删除索引（indices），analyze命令不返回sqlitecompiled没有sqlite_enable_stat3或sqlite_enable_stat4，并且使用相同版本的sqlitesqlite的稳定性保证意味着如果您在测试中高效地运行查询，并且您的应用程序不更改模式，那么sqlite不会突然选择开始使用不同的查询计划，这可能会在您向用户发布应用程序后导致性能问题。如果您的应用程序在实验室中运行，那么它在部署后也将运行。企业级客户端/服务器SQL数据库通常不能做出这样的保证。在客户端/服务器SQL数据库引擎中，服务器跟踪统计表的大小和索引（索引）的数量，查询计划器根据这些统计数据选择最优计划。一旦数据库的内容发生了增删改查，统计信息的变化可能会导致查询计划器对某些查询使用不同的查询计划。通常新计划更适合更改后的数据结构。但有时新的查询计划会导致性能下降。在使用客户端/服务器数据库引擎时，通常会有数据库管理员(dba)来处理这些罕见的问题。但DBA无法在sqlite这样的嵌入式数据库中解决这个问题，因此sqlite需要小心确保在部署后查询计划不会被意外更改。SQLite稳定性保证适用于传统查询计划和ngqp。需要注意的是，sqlite版本的变化可能会导致查询计划发生变化。相同版本的sqlite通常会选择相同的查询计划，但如果您将应用程序重新连接到不同版本的sqlite，则查询计划可能会发生变化。在极少数情况下，sqlite版本的更改会导致性能下降。这是您应该考虑将您的应用程序静态链接到sqlite而不是使用系统范围的sqlite共享库的原因之一，因为它可能会在您不知情或无法控制的情况下发生变化。3.0粘性案例“tpc-hq8”是事务处理性能委员会的测试查询。查询规划器在sqlite3.7.17及更早版本中没有为tpc-hq8选择好的计划。并且确定无论对传统查询计划器进行多少调整都无法解决此问题。为了给tpc-hq8查询找到好的解决方案，不断提高sqlitequeryplanner的质量，需要重新设计queryplanner。本节将解释为什么需要重新设计、ngqp有何不同以及如何解决tpc-hq8问题。3.1查询细节tpc-hq8是一个8路连接。基于我们上面所看到的，查询规划器的主要任务是确定这八个循环的最佳嵌套顺序，从而最大限度地减少完成连接操作的工作量。下图是tpc-hq8示例的简单模型：图中查询语句from子句部分的8张表用一个大圆圈表示，通过from子句的名字来标识：n2、s、l、p、o、c、n1和r。图中的圆弧表示以圆弧起点为计算表外连接的预估成本。比如sinnerjoinl的cost是2.30，souterjoinl的cost是9.17。这里的“资源消耗”是通过对数运算计算出来的。因为循环是嵌套的，所以总资源消耗是成倍增加的，而不是增加的。通常认为图形带来的权重是要累加的，但这里的图形显示的是各种资源消耗的对数值。上图可以看出，位于l里面的s消耗大约少了6.87。转换后，s循环位于l循环内的查询比s循环位于l循环外的查询运行速度大约快963倍。从标有“*”的小圆圈开始的箭头表示单独运行每个循环所消耗的资源。外循环必须消耗“*”消耗的资源。内循环可以选择消耗“*”所消耗的资源，也可以选择剩余的一项作为外循环消耗的资源，无论选择哪一项，都是为了资源消耗最低。您可以将“*”所消耗的资源视为从图中任何其他节点到当前节点的多条弧的简写表示。这样的图因此被称为是“完备的”，也就是说图中每对节点之间在两个方向上都有弧（有的很明显，有的是隐含的）。寻找最优查询计划的问题等同于在图中寻找访问每个节点恰好一次的成本最低的路径。（注：tpc-hq8图中的资源消耗预估由sqlite3.7.16中的queryplanner计算，并使用自然对数进行转换。）3.2Complexity上面展示的queryplanner问题是Simplified版本。可以估计资源消耗。只有真正运行循环后，我们才能知道运行这个循环的真实资源消耗。SQLite根据where子句的约束和可用索引来估计运行循环的资源消耗。这种估计通常接近十，但有时估计的结果与实际情况相去甚远。使用analyze命令收集数据库的其他统计信息，有时可以让sqlite对消耗资源的评估更加准确。消耗的资源是由多个数字组成的，而不是像上图那样只有一个数字。SQLite计算每个循环的不同阶段消耗的几个不同的估计资源。例如，“初始化”资源消耗仅在查询开始时发生。初始化消耗的资源是没有索引的表自动建立索引消耗的资源。然后就是runloop每一步消耗的资源。最后，评估循环自动生成的行数，这是评估内部循环消耗的资源所必需的信息。如果查询包含orderby子句，那么排序消耗的资源也要考虑。普通查询中的依赖关系不一定在单个循环上，因此依赖关系模型可能无法用图来表示。例如，where子句的约束之一可能是s.a=l.b+p.c，这隐含地表示s的循环必须是l和p的内循环。这种依赖关系无法用图来表示，因为无法同时从两个或多个节点开始绘制弧线。如果查询包含orderby子句或groupby子句，或者查询使用了distinct关键字，则行将自动排序以形成图形。选择遍历这个图的路径非常方便，不需要单独排序。自动移除orderby子句会对性能产生巨大的影响，因此它也是完成计划程序的完整实施时需要考虑的因素。在tpc-hq8查询中，所有初始化资源消耗都可以忽略不计，每个节点之前都有依赖关系，没有orderby、groupby或distinct子句。因此，对于TPC-HQ8，上图足以表示计算资源消耗所需的内容。常见的查询可能涉及许多其他复杂的情况。为了弄清楚问题，本文的其余部分忽略了许多使问题复杂化的因素。3.3寻找最佳查询计划在3.8.0版本之前，sqlite使用“最近邻”或“nn”启发式方法寻找最佳查询计划。nn启发式对图进行单次遍历，始终选择成本最低的弧作为下一步。在大多数情况下，nn启发式算法工作得很好。而且nnheuristic也很快，所以sqlite即使达到64个连接也能很快找到好的方案。相比之下，当同一连接中的表数大于10或15时，其他可以运行更大搜索的数据库引擎会停止。不幸的是，nn启发式算法对于tpc-hq8计算的查询计划不是最优的。nn启发式计算出的计划为r-n1-n2-s-c-o-l-p，其资源消耗为36.92。上一句的意思是：r表运行在最外层循环，n1位于下一个内层循环，n2位于第三层循环，依次类推到位于最内层循环的p。遍历此图的最短路径（可穷举搜索得到）为p-l-o-c-n1-r-s-n2，此时资源消耗为27.38。差异可能看起来并不大，但是请记住，消耗的资源是按对数计算的，因此最短路径比nn启发式得出的路径快近750倍。此问题的一种解决方案是更改SQLite以使用穷举搜索最佳路径。然而，穷举搜索所需的时间与k!（k为连接涉及的表数），所以当连接数超过10个时，运行耗时非常大。3.4n最近邻启发式或“n3”启发式下一代查询规划器使用一种新的启发式来寻找遍历图的最佳路径：“n最近邻启发式”（以下称为“n3”）。对于n3，每一步不只是选择最近的邻居。n3算法需要在每一步跟踪n条最佳路径，其中n是一个小整数。假设n=4，那么对于tpc-hq8图，第一步是找到可以访问任意单个节点的4条最短路径：r(cost:3.56)n1(cost:5.52)n2(cost:5.52)p(cost:7.71)第二步从上一步找到的4条最短路径中的一条开始，找到可以访问两个节点的4条最短路径。在这种情况下，两条或更多条路径是可以的（这样的路径具有相同的一组可访问节点，可能顺序不同），只需记住保留第一步的路径和资源消耗最低的路径即可。我们找到以下路径：r-n1(cost:7.03)r-n2(cost:9.08)n2-n1(cost:11.04)r-p{cost:11.27}第三步从可以访问两个节点的四个最短路径开始，找出能访问三个节点的4条最短路径：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-hq8查询有8个节点，所以这个过程一共重复8次。在通常k个连接的情况下，存储需求复杂度为o(n)，计算时间复杂度为o(k*n)，明显比o(2k)方案快很多。但是，选择哪个n值呢？你可以试试n=k。这个时候这个算法的复杂度是o(k2)，其实很快，因为k的最大值是64，k很少超过10。虽然还是不足以解决tpc-hq8的问题。tpc-hq8查询时如果n=8，n3算法得到的查询计划为r-n1-c-o-l-s-n2-p，资源消耗为29.78。这比nn算法有了很大的改进，但仍然不是最优的。当n=10或更大时，n3可以找到最佳的查询计划进行tpc-hq8查询。下一代查询计划的初始实现选择n=1用于简单查询，n=5用于两个连接，n=10用于三个或更多表的连接。后续版本可能会更改n值选择规则。4.0升级到下一代查询规划器的风险对于大多数应用程序，从遗留查询规划器升级到下一代查询规划器几乎不需要考虑或努力。只需将旧的sqlite版本替换为更新的sqlite版本，重新编译并更快地运行应用程序。复杂流程无需更改或修复API。然而，与其他查询器替代品一样，升级到下一代查询规划器确实会带来性能下降的小风险。这个问题不会出现，因为下一代查询规划器不正确，或者有缺陷，或者比旧的查询规划器更糟糕。如果选定索引的信息确定了，那么下一代查询规划器总能选择比以前更好或更好的计划。问题在于某些应用程序可能使用低质量、选择性较低的索引并且无法运行分析。旧的查询规划器会针对每个查询查看许多但比现在更少的可能查询实现，因此如果运气好的话，这样的规划器可能会遇到一个好的计划。另一方面，下一代查询计划器看的是更多的查询计划实现，所以理论上可能会选择另一个性能更好的查询计划，如果此时索引运行良好，但实际性能很差。下降可能是由数据分布引起的。技术要点：下一代查询规划器只要能够访问到sqlitestat1文件中准确的analyze数据，总能找到与之前的查询规划器性能相同或更好的查询规划。只要查询模式不包含超过10或20行的最左边字段具有相同值的索引，下一代查询计划器总能找到一个好的查询计划。并非所有申请都符合上述标准。幸运的是，即使不满足这些条件，下一代查询计划器通常仍然可以找到好的查询计划。但是，性能下降也是可能的（尽管很少见）。4.1实例分析：使用下一代查询调节器升级FossilFossildvcs是一个用于跟踪所有sqlite源代码的版本控制系统。Fossil软件存储库是一个sqlite数据库文件。（作为一个单独的练习，请读者深入思考这种递归应用的查询规划器。）Fossil既是SQLite的版本控制系统，也是SQLite的测试平台。无论何时强化SQLite，Fossil都是首批测试和评估这些强化的应用程序之一。所以fossil率先采用了下一代查询规划器。不幸的是，下一代查询规划器导致化石性能下降。Fossil使用许多报告，其中一个是在单个分支上所做的更改的时间线，它显示了该分支上的所有合并和删除。有关时间线报告的典型示例，请参见http://www.sqlite.org/src/timeline?nd&n=200&r=trunk。通常生成这样的报告只需要几毫秒。但是，升级到下一代查询规划器后，我们发现在仓库的主干分支上生成这样的报告需要将近10秒。用于生成分支时间表的核心查询如下。（我们不希望读者理解这个查询的细节。下面给出了解释。）?
