详解SQLite中的查询规划器

 1.0 介绍

查询规划器的任务是找到最好的算法或者说“查询计划”来完成一条sql语句。早在sqlite 3.8.0版本，查询规划器的组成部分已经被重写使它可以运行更快并且生成更好的查询计划。这种重写被称作“下一代查询规划器”或者“ngqp”。

这篇文章重新概括了查询规划的重要性，提出来一些查询规划固有的问题，并且概括了ngqp是如何解决这些问题。

我们知道的是，ngqp（下一代查询规划器）几乎总是比旧版本的查询规划器好。然而，也许有的应用程序在旧版本的查询规划器中已经不知不觉依赖了一些不确定或者不是很好的特性，这时候将查询规划器更新升级到ngqp，这些应用程序可能会导致程序闪退现象。ngqp必须考虑这种风险，提供一系列的检查项来减小风险和解决可能会引起的问题。

在ngop上关注此文档。对于更一般的sqlite查询规划器以及涵盖sqlite整个历史的概述，请参阅：“sqlite查询优化程序概述”。
2.0 背景

对于用简单的几个指数对单个表的查询，通常会有一个明显的最佳的算法选择。但是对于更大更复杂的查询，诸如众多指数与子查询的多路连接，对于计算结果，可能有数百，数千或者数百万的合理算法。如此查询规划的工作是选择一个单一的“最好”的有众多可能性的查询计划。

查询规划器是什么使得sql数据库引擎变得如此惊人的有用与强大。(这是真正的所有的sql数据库引擎，不只是sqlite。)查询规划器使得编程人员从苦差事中选择一个特定的查询计划之中释放出来。从而允许程序员在更高级别的应用问题里和向最终端用户提供更多的价值之上可以关注更多的心理能量。对于简单的查询，查询计划的选择是显而易见的，虽然是方便的，但并不是很重要的。但是作为应用程序，架构与查询将会变得越来越复杂化。一个聪明的查询规划可以大大地加速和简化应用程序开发的工作。它告诉数据库引擎有什么内容需求是有着惊人的力量的，然后，让数据库引擎找出最好的办法检索那些内容。

写一个好的查询规划器是艺术多于科学。查询规划器必须要有不完整的信息。它不能决定将多久采取任何特别的计划，而实际上无需运行此计划。因此，当比较两个或多个计划时，找出哪些是“最好的”，查询规划器会做出一些假设和猜测，那些假设和猜测有时候会出错。一个好的查询计划要求能找到正确的解决方案，而这些问题是程序员很少考虑的。
2.1 sqlite之中的查询规划器

sqlite的计算使用嵌套循环联接，一个循环中每个标的连接(额外的循环可能会在where句子中插入in和or运算符。sqlite认为那些考虑太多啦，但为了简单起见，我们可以在这篇文章之中可以忽略它。)在每次循环时，一个或者更多的指数被使用，并被加速搜索，或者一个循环可能是“全表扫描”读取表中每一行。因此，查询规划分解成两个子任务：

•     采摘的各种循环的嵌套顺序。
•     选择每个循环的良好指数。

采摘嵌套顺序一般是更具挑战性地问题。

一旦建立连接的嵌套顺序，每个循环指数的选择通常是显而易见的。

2.2 sqlite查询规划器稳定性保证

对于给出的任何sql语句，sqlite 通常情况下会选择相同的查询规划假如：

•     数据库的schema没有明显的改变，例如添加或删除索引(indices)，
•     analyze命令没有返回
•     sqlite在编译时没有使用sqlite_enable_stat3或者sqlite_enable_stat4，并且
•     使用相同版本的sqlite

sqlite的稳定性保证意味着你在测试中高效的运行查询操作，并且你的应用没有更改schema，那么sqlite不会突然选择开始使用一个不同的查询规划，那样有可能在你把你的应用发布给用户之后造成性能问题。如果在实验室里你的应用是工作的，那它在部署之后同样可以工作。

企业级的客户端/服务器sql数据库通常不能做这样的保证。在客户端/服务器sql数据库引擎里，服务器跟踪统计表的大小和索引(indices)的数量，查询规划器根据这些统计信息选择最优的规划。一旦在数据库的内容通过增删改改变，统计信息的改变有可能引起对于某些特定的查询，查询规划器使用不同的查询规划。通常新的规划对于更改过的数据结构来说更好。但有时新的查询规划会导致性能的下降。在使用客户端/服务器数据库引擎时，通常会有一个数据库管理员(dba)来处理这些罕见的问题。但是dba们不能在像sqlite这样的嵌入式数据库中修复该问题，所以sqlite需要小心的确保查询规划在部署之后不会被意外的改变。

sqlite稳定性保证适用于传统的查询规划和ngqp。

需要注意的很重要的一点是sqlite版本的改变可能引起查询规划的改变。同版本的sqlite通常会选择相同的查询规划，但是如果你把你的应用重新连接到了不同版本的sqlite上，那么查询规划可能会改变。在很罕见的情况下，sqlite版本的改变会引起性能衰减。这是一个你应该考虑把你的应用静态的连接到sqlite而不是使用一个系统范围(system-wide)的sqlite共享库的原因，因为它有可能在你不知情或者不能控制的情况下改变。
3.0 一个棘手的情况

"tpc-h q8"是一个来自于transaction processing performance council的测试查询。查询规划器在3.7.17以及之前版本的sqlite中没有为tpc-h q8选择一个好的规划。并且被认定再怎么调整传统查询规划器也不能修复这个问题。为了给tpc-h q8查询寻找一个好的好的解决方案，并且能够持续的改进sqlite查询规划器的质量，我们有必要重新设计查询规划器。这个部分将解释为什么重新设计是有必要的，ngqp有什么不同和设法解决tpc-h q8问题。

3.1 查询细节

tpc-h q8 是一个8路的join。基于以上所看到的，查询规划器的主要任务是确定这八次循环最好的嵌套顺序，从而将完成join操作的工作量最小化。下图就是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循环内部的查询比s循环位于l循环外部的查询要运行快大约963倍。

从标记为“*”的小圆圈开始的箭头表示单独运行每个循环所消耗的资源。外循环一定消耗的是“*”所消耗资源。内循环可以选择消耗"*"所消耗的资源，或者选择其余项中的一个为外部循环所消耗的资源，无论选择哪个都是为了得到最低的资源消耗。你可以把“*”所消耗的资源看作是图中其他节点中的任意一个到当前节点的多个弧线的简写表示。因此说这样的图是“完整的”，也就是说图中的每一对节点间都有两个方向的弧线（一些是非常明显的，一些则是隐含的）。

寻找最佳查询规划的问题就等同于寻找图中访问每个节点仅仅一次的最小消耗路径。

（附注：tpc-h q8图里的资源消耗的评估是由sqlite 3.7.16里的 查询规划器计算，并使用自然对数转换得来的 。）

3.2 复杂性

上面所展示的查询规划器问题是简化版的。资源的消耗可以估计出来。我们只有实际运行了循环之后才能知道运行这个循环真正的资源消耗是多少 。sqlite是根据where子句的约束和可以使用的索引来估计运行循环的资源消耗的。这样的估计通常都八九不离十，不过有时候估计的结果却脱离现实。使用analyze命令收集数据库的其他统计信息有时候可以让sqlite对消耗的资源的评估更准确。

消耗的资源是由多个数字组成的，而不是像上图一样只是有一个单独的数字组成。sqlite针对每个循环的不同阶段计算出几个不同的评估的消耗的资源。例如 ，“初始化”资源耗费仅仅发生在查询启动的哪个时候。初始化消耗的资源是对没有索引的表进行自动索引所消耗的资源 。接着是运行循环的每一步所消耗的资源。最后评估循环自动生成的行数，行数是评估内循环所消耗资源所必需的信息。如果查询含有order by子句，那么排序所消耗的资源也要考虑。

常用的查询里的依赖并不一定在一个单独的循环上，因此依赖的模型可能无法用图来表示。例如，where子句的约束之一可能是s.a=l.b+p.c，这就隐含地说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之前，sqlite一直使用“最近邻居” 或者“nn"试探法寻找最佳查询规划。nn试探法对图进行一次单独的遍历，总是选择消耗最低的哪个弧线作为下一步。大多数情况下，nn试探法运行的非常地好。而且，nn试探法也很快，因此sqlite即便是达到64个连接的情况下也能够快速的找到很好的规划。与此相反，可以运行更大量搜索的其他数据库引擎在同一连接中表的数目大于10或者15时就会停止不动。

很不幸，nn试探法对tpc-h q8所计算出的查询规划不是最佳的。由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.4 n个最近邻居试探法或者"n3"试探法

下一代查询规划器使用新的试探法查找遍历图的最佳路径："n个最近邻居试探法"(后面就叫"n3")。用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(2 k)方案快多了。

然而，n选择哪个值呢？你可以试试n=k，此时这种算法的复杂度是o(k2) ,实际上仍然非常相当快，由于k的最大值为64，而且k很少超过10。不过这仍然不足以解决tpc-h q8问题。如果tpc-h q8查询进行时n=8，此时n3算法得到的查询规划是r-n1-c-o-l-s-n2-p,此时资源耗费是29.78。这对nn算法进行了很大的改进，不过仍然不是最佳的。当n=10或者更大时，n3才能找到tpc-h q8查询的最佳查询规划。

下一代查询规划的最初实现对简单查询选n=1,两个连接就选n=5，三个或者更多表连接选择n=10。后续的发布版可能要更改n值得选择规则。

4.0 升级到下一代查询规划器的风险

对大多数应用来说，从旧查询规划器升级到下一代查询规划器不需要多想，或者不需要花很多功夫就可以做到。只要简单地把旧的sqlite版本换成较新的sqlite版本，然后重新编译就行，此时运行应用就会快很多。不需要对复杂过程的api进行更改或者修正。

然而，像其他查询器更换一样，升级到下一代查询规划器确实可以引起性能下降这样的小风险。出现这种问题不是因为下一代查询规划器不正确、或者说漏洞多，或者说比旧的查询规划器差。假若选择索引的信息确定，那么下一代查询规划器总能选择一个比以前好的或者说更优秀的规划。存在的问题是某些应用也许使用了低质量的、没有多少选择性的索引，而且无法运行analyze。旧的查询规划器对每个查询都查看了许多但比现在要少的可能的查询实现，因此如果运气好的话，这样的规划器可能就碰到好的规划。而另一方面，下一代查询规划器查看了更多地查询规划实现，所以理论上来讲，它可能选择另一个性能更好的查询规划，如果此时索引运行良好，而实际运行中性能却有所下降，那么可能是数据的分布引起的.

技术要点：

•     只要下一代查询规划器可以访问sqlite stat1文件里准确的analyze数据，那么它总是能找到与以前查询规划器等同的或者性能更好的查询规划。
•     只要查询模式不包含最左边字段具有相同值且有超过10或者20行的索引，那么下一代查询规划器总是能找到一个好的查询规划。

并不是所有的应用都满足上面条件。幸运的是，即便不满足这些条件，下一代查询规划器通常仍然能找到好的查询规划。不过，性能下降这种情况也有可能出现（不过很少）。

4.1范例分析：升级fossil使用下一代查询规器

fossil dvcs是用来追踪全部sqlite源代码的版本控制系统。fossil软件仓库就是一个sqlite数据库文件。（作为单独的练习，我们邀请读者对这种递归式的应用查询规划器进行深入思考。）fossil既是sqlite的版本控制系统，也是sqlite的测试平台。无论什么时候对sqlite进行强化，fossil都是对这些强化进行测试和评估的首批应用之一。所以fossil最早采用下一代查询规划器。

很不幸，下一代查询规划器引起了fossil性能下降。

fossil用到许多报表，其中之一就是单个分支上所做更改的时间表，它显示了这个分支的所有合并和删除。查看 http://www.sqlite.org/src/timeline?nd&n=200&r=trunk就可以看到时间报表的典型例子。通常生成这样的报表只需要几毫秒。然而，升级到下一代查询规划器之后，我们发现对仓库的主干分支生成这样的报表竟然需要近10秒的时间。

用来生成分支时间表的核心查询如下。（我们不期望读者理解这个查询的细节。下面将给出说明。）
 

这个查询不是特别复杂，不过，即便这样，它仍然可以替代上百行，也许是上千行处理过程代码。这个查询的要点是：向下扫描event表，查找满足下列三个条件中任何一个的最新的200条提交记录：

1.     此提交含有"trunk"标签。
2.     此提交有个子提交含有“trunk"标签。
3.     此提交有个父提交含有“trunk"标签。

第一个条件将显示所有主干分支上的提交，第二个和第三个条件包含合并到主干分支，或者由主干分支产生的提交。这三个条件是通过在此查询的where子句中用or连接三个exists语句实现的。使用下一代查询规划器引起的性能下降是由第二个和第三个条件产生的。两个条件里存在的问题是相同的，因此我们只看第二个条件。第二个条件的子查询可以重写为如下语句（把次要的和不重要的进行了简化）：
 

plink表保存着各个提交之间的父子关系。tagxref表把标签映射到提交上。作为参考，对这两个表进行查询的模式的相关部分显示如下：
 

实现这样的查询只有两个方法值得考虑。（当然可能还有许多其他算法，不过它们中的任何一个都不是“最佳”算法的竞争者。

•     查找提交$ckid的所有子提交，然后对每一个进行测试，看看是否有子提交包含$trunk标签
•     查找所有包含$trunk标签的提交，然后对每个这样的提交进行测试，看看是否有$ckid提交的子提交。

仅凭直觉，我们人类认为第一个算法是最佳选择。每个提交可能有几个子提交（其中有一个提交是我们最常用到的。），然后对每个子提交进行测试，用对数运算计算出查找到$trunk标签的时间。实际上，算法1确实较快。然而下一代查询规划器却没有使用人们直觉上的最佳选择。下一代查询规划器一定是选择了很难得算法，算法2在数学上相对稍微难些。这是因为：在没有其他信息的情况下下一代查询规划器一定假设plink_i1和tagxref_i1索引具有同等的质量和同等的可选择性。算法2使用了tagxref_i1索引的一个字段，plink_i1索引的两个字段，而算法1只是使用了这两个索引的第一个字段。正是由于算法2使用了多个字段的索引，所以下一代查询规划器才会以自己的标准正确地确定它作为两种算法中性能较好的算法。两个算法所花费的时间非常接近，算法2 只是勉强稍稍领先算法1。不过，这种情况下，选择算法2确实是正确的。

很不幸，在实际的应用中算法2比算法1要慢些。

出现这样的问题是因为索引并不是具有同等质量。一个提交有可能只有一个子提交。这样plink_i1索引的第一个字段通常缩减值对一行进行搜索。不过由于成千上万的提交都包含有"trunk"标签，所以tagxref_i1的第一个字段对缩减搜索不会有多大帮助。

下一代查询规划器是没有办法知道tagxref_i1在这样的查询中几乎没有什么用处，除非在数据库上运行analyze。analyze命令 收集了各个索引的质量统计信息，并把 这些统计信息存储到sqlite_stat1表里。如果下一代查询规划器能够访问这些统计信息 ，那么在很大程度上它就会非常容易地选择算法1作为最佳算法。

难道旧查询规划器没有选择算法2？很简单：因为nn算法甚至从来都没有考虑到算法2。这类规划问题的图示如下：

在如左图那样“没有运行analyze“的情况下，nn算法选择循环p9plink)作为外循环，因为4.9比5.2要小，结果就是选择p-t路径，即算法1。nn算法只是在每一步查找一个最佳选择路径，因此它完全忽略了这样一个事实：5.2+4.4是比4.9+4.8性能稍稍有些好的规划。然而n3算法对着两个连接追踪了5个最佳路径，因此它最终选择了t-p路径，因为这条路径的总体资源消耗要少一些。路径t-p就是算法2。

注意： 如果运行了analyze，那么对资源消耗的评估就更加接近于现实，这样nn和n3都选择算法1。

（附注：最新的两图中对资源消耗的评估是下一代查询规划器使用以2为底的对数算法计算得出来的，而且与旧查询规划器相比假设的资源消耗稍微有些不同。因此，最后两个图中的资源消耗评估不能与tpc-h q8图里的资源消耗评估进行比较。）

4.2 问题修正

对资源仓库数据库运行analyze可立即修复这类性能问题。然而，无论是否对资源仓库是否进行分析，我们都要求fossil十分强壮，而且总是能够快速地运行。基于这个原因，我们修改查询使用cross join操作符而不使用常用的join操作符。sqlite将不会对cross join连接的表重新排序。这个功能是sqlite中长期都有的一个功能，做这么特别的设计就是允许具有丰富经验的开发人员能够强制sqlite执行特定的嵌套循环顺序。一旦某个连接更改为（增加了一个关键字的）cross join这样的连接，下一代查询规划器就不管是否使用analyze收集统计统计信息都强制选择稍稍快一点的算法1。

我们说算法1"快一些“，不过，严格来说这么说不准确。对一个常见的存储仓库运行算法1是快一些，不过，可能构建这样一种资源仓库：对资源仓库的每一次提交都是提交给不同的名字唯一的分支上，而且所有的提交都是根提交的子提交。这种情况下，tagxref_i1与plink_i1相比就具有更多的可选项了，此时算法2才真正快一些。然而实际中这样的资源仓库极不可能出现，所以使用cross join语法硬编码嵌套循环的顺序是解决这种情形下存在问题的适合方案。

5.0 避免或者修正查询规划器问题的方法一览表

    不要惊慌！查询规划器选择差的规划这种情况实际上是非常罕见的。你未必会在应用中碰到这样的问题。如果你没有性能方面问题，那么你就不必为此而担心。

    创建正确的索引。大多数sql性能问题不是因为查询规划器问题而引起的，而是因为缺少合适的索引。确保索引可以促进所有大型的查询。大多数性能问题都可以使用一个或者两个create index命令来解决，而不需要对应用代码进行修改。

    避免创建低质量的索引。（用于解决查询规划器问题而创建的）低质量索引是这样的索引：表里的索引最左一个字段具有相同值的行超过10行或者20行。特别注意，避免使用布尔字段或或者“枚举类型”字段作为索引的最左一字段。

    这篇文章的前一段所说的fossil性能问题是因为tagxref表的tagxref_i1索引的最左一子段(tagid字段）具有相同值得项超过1万。

    如果你一定要使用低质量的索引，那么请一定要运行analyze。只要查询规划器知道那个索引时低质量的，那么低质量的索引就不会让它迷惑。查询规划器知晓低质量索引的方法是通过sqlite_stat1表的内容来实现的，这个表示有analyze命令计算得来的。

    当然，analyze只有在数据库一开始就拥有非常大量的内容的情况下才能够高效地运行。当你希望创建一个数据库并累积了大量数据的时候，你可以运行命令"analyze sqlite_master"创建sqlite_stat1表，然后（使用常用的insert语句）向sqlite_stat1表中填入用来说明这样的数据库正适合你的应用的内容-也许这样的内容是你在对实验室的某个填写的非常完美的模板数据库运行analyze命令后所获得的。

    编写你自己的代码。增加可以让你快速且非常容易就能知道哪些查询需要很多时间，这样就只运行哪些特别不需要花太长时间的查询。

    如果查询可能使用没有运行分析的数据库上的低质量索引，那么请使用cross join语法，强制使用特定的嵌套循环顺序。sqlite对cross join操作符进行特殊的处理，它强制左表为右表的外部循环。

    如果有其他方法实现，那么就避免这么做，因为它与任何一个sql语言理念里的强大的优点相抵触，特别是应用开发人不需要了解查询规划。如果你使用了cross join，那么直到开发周期的后期你也要这么做，而且要在注释里仔细地说明cross join是如何使用的，这样以后才有可能把它去掉。在开发周期的早期就避免使用cross join,因为这么做是不成熟的优化措施，也就是众所周知的万恶之源。

    使用单目运算符"+",取消where子句某些限制条件。当对某个具体的查询有更高质量的索引可以使用的时候，如果查询规划器仍然坚持选择差质量的索引，那么请在where子句中谨慎地使用单目运算符"+",这样做就可以强制查询规划器不使用差质量的索引。如果可能的话，就尽量小心地添加这个这个运算符，而且尤其避免在应用开发的周期的早期就使用。特别要注意：给一个与类型密切相关的等号表达式增加单目运算符"+"可能更改这个表达式的结果。

    使用indexed by语法，强制有问题的查询选择特定的索引。同前两个标题一样，如果可能的话，尽量避免使用这个方法，尤其避免在开发的早期这么做，因为很清楚，它是一个不成熟的优化措施。

6.0 结论

sqlite的查询规划器做这样的工作做得非常好：为正在运行的sql语句选择快速算法。对旧查询规划器来说，这是事实，对新的下一代查询规划器来说更是这样。也许偶然会出现这样的情况：由于信息不完整，查询规划器选择了稍差的查询规划。 与使用旧查询规划器相比，使用下一代查询规划器这种情形就会更少出现了，不过仍然有可能出现。即便出现了这种极少出现的情况，应用开发人员需要做的是了解和帮助查询规划器做正确的事情。通常情况下，下一代查询规划器只是对sqlite做了一个新的增强，这种增强可以让应用运行的更快些，而且不需要开发人员做更多的思考或者动作。