一种有趣的测试方法：pivoted query synthesis

故事从前一阵子说起。有一哥们在短时间内，给我们报了大量的 bug。他是用机器人在测试我们的数据库。据说是测试了 SQLite，测试了 MySQL，测试了 PG，还有小强等等友商，小强被他折磨的修 bug 修不过来了，他就跑来我们这边试试。 一个人测试发现 bug 的速度，让一个团队都修复不过来，这还是非常生猛的。为什么这么牛X呢？他写了一篇论文的，使用了一种新的测试方法。

好，现在我们开始讲他的这篇文章了。这篇文章叫 Testing Database Engines via Pivoted Query Synthesis。

在此之前，比较有效的一种测试方法是 Differential testing，当然 fuzz 是大家耳熟能详的。Differential 测试是构造许许多的 fuzz 输入，我们并不知道输入对应的输出结果是什么。不过 SQL 是一个比较通用的语言，对应着许许多多的实现。所以可以把输入发送到不同的实现，再去对比不同系统的输出结果。如果结果不同，就有可能是某个系统的行为有 bug 了。

我最早听说 Differential 这类的测试方法，是在编译器领域的测试里面。我们要测试编译器实现的 bug，用常规的手段是比较难找 bug 的，效率比较低。Differential 测试方法，可以这样搞：随机构造茫茫多的很小的程序片断，用不同的编译器去编译，因为语言是标准的，之后执行编译后的程序，则各程序的输出结果也应该是相同的，不管是用哪一个编译器编译。如果不同编译器编译出来，执行后生成的结果不一致，肯定有其中哪个实现是有问题的。

那篇文章说了一下 Differential 测试方法的缺点。SQL 尽管是一门语言，但是各种数据库的实现都有自己的方言和 feature，导致很多时候并不通用，这样交叉验证的方式局限性很大。另外，SQL 的查询条件的构造，一点点区别可能查询结果特别多，数据集不好控。

所有作者提出了 Pivoted Query 的方式。这个方法不再是构造输入后用不同实现交叉验证输出结果，而是，先挑一个确定的结果，比如说查询结果里面一行包含某一行，这个叫 pivote row，然后某个基础查询会出这个结果，在此之上去派生出其它的查询请求来。最后验证就是不管查询请求是啥，预期在结果里面一定是包含这样一行的。如果没有，就是发现 bug 了。

查询条件的构造过程举个例子，初始数据里面 c1 列有 0 1 2 NULL 这样四行，然后选择一个 pivot row 比如 c0 == NULL，我们确定了一个基本的查询条件 where c0 == NULL，接下来，我们在这基础上去派生出查询条件，c0 IS NOT 1 这个条件，跟 c0 == NULL 做 and 之后仍然是 TRUE 的，所以我们就可以派生出 where c0 == NULL and c0 IS NOT 1 这样的查询。类似的，我们还可以派出来 join 和其它的查询，只要最终生查的查询请求，结果里面会包含 pivot row。

具体的实现它是用表达式的 ast 生成，做一些基础变换，再筛选出结果为 true 的那些，去生成查询表达式。 列一下整体的流程：

• 第一步，创建一些库和表，为每个表随机填一些数据，确保每个表都至少包含一行以上数据
• 第二步，然后随机选出一行，这一行作为 pivot row
• 第三步，根据这个 pivot row 确定一个 test oracle，基于 SQL 语法随机创建许多查询表达式
• 第四步，对这些表达式，基于 pivot row 的对应的值替换表达式的列，确认修改表达式计算结果是 true
• 第五步，在 where 或者 join 的查询条件里面使用这些我们构造的表达式
• 第六步，调用数据库执行请求
• 第七步，确认返回的执行结果里面，包含 pivot row

具体细节可以去看原文了。这篇文章其实 overview 部分已经把整个方法讲得很明白了。后面的内容就是一些实现的细节，然后在各个数据库里面的一些实验结果了。 不管是 SQLite，MySQL 还是 Postgres 都是茫茫多的 bug 的。

感慨一下现在的测试方法真是令人耳目一新。Differential 里面，我不知道什么样的结果是对，什么样的结果是错，可以交叉验证对错，这个过程就可以找 bug 了，而输入请求是可以瞎构造的。

在这篇 pivoted query 里面，确定一条 pivoted 的结果，在此基础上就可以瞎构造输入了。就有点像，把问题换了一个角度观察，攻守互换。

证明一个算法是对的，很难，因为无法枚举所有的情况。证明算法是错的更容易一些，因为我们只要找到一处反例，就可以证明算法是错的了。 直接思考程序哪里有 bug 的思维方式，就好比证明一个算法是对的，这很难。而 pivot row 确定一个约束，再以此约束条件下去构造查询，就好比假设算法是对的了，去寻找反例，只要有不满足约束了，就是找到 bug 了。