详解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个以上的连接的时候，运行sqlite3_prepare()所耗费的时间丢非常大。
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。旧的查询规划器对每个查询都查看了许多但比现在要少的可能的查询实现，因此如果运气好的话，这样的规划器可能就碰到好的规划。而另一方面，下一代查询规划器查看了更多地查询规划实现，所以理论上来讲，它可能选择另一个性能更好的查询规划，如果此时索引运行良好，而实际运行中性能却有所下降，那么可能是数据的分布引起的.

技术要点：