Keep It Simple: Testing Databases via DifferentialQuery Plans

ABSTRACT

查询优化器执行各种优化，其中许多已被提出用于优化连接。确保这些优化的正确性至关重要，这意味着它们应经过广泛测试。除了手工编写的测试之外，自动化测试方法也得到了广泛采用。这些方法半随机地生成数据库和查询。更重要的是，它们提供了一种所谓的测试预言机，能够推断系统的结果是否正确。最近，研究人员提出了一种名为“转换查询合成”（Transformed Query Synthesis，TQS）的新测试方法，专门用于发现连接优化中的逻辑错误。TQS是一种复杂的方法，它将给定的输入表拆分成多个子表，并通过检索给定表来验证连接这些子表的查询结果。

我们研究了TQS的错误报告，发现15个独特错误中有14个是通过执行相同查询但使用不同查询计划时显示出差异来报告的。因此，在本研究中，我们提出了一种简单的替代TQS的方法。我们的方法强制为同一查询采用不同的查询计划，并验证结果的一致性。我们将这种方法称为“差异查询计划”（Differential Query Plan，DQP）测试。DQP可以复现TQS发现的15个独特错误中的14个，并发现了26个以前未知且独特的错误。这些结果表明，一个具有有限新颖性的简单方法可以与一个复杂且概念上有吸引力的方法同样有效。此外，DQP是发现逻辑错误的其他测试方法的补充。DQP发现的逻辑错误中有81%是NoREC和TLP无法发现的，而DQP忽略了NoREC和TLP发现的86%的错误。我们希望我们方法的实用性——每个系统的实现代码不足100行——将促使其得到广泛采用。

INTRODUCTION

Background

关系数据库管理系统（DBMS）的一个关键特性是使用JOIN在多个表中连接数据。为了优化连接操作，已经提出了各种策略和优化方法。鉴于这些优化的复杂性，查询优化器可能会应用语义上不正确的优化，从而导致产生不正确的结果。这些错误被称为逻辑错误。找到逻辑错误具有挑战性，因为它们会悄无声息地产生不正确的结果——不像崩溃错误，它们会导致进程终止。在列表1中，第8行的第二个查询触发了DBMS中的一个逻辑错误，因为它应该返回一个非零结果，而不是零。

Related work

最近，针对DBMS的自动化测试方法已经广泛采用来发现逻辑错误，因为它们通常可以发现许多手动编写测试所遗漏的错误。重要的是，这些方法提供了所谓的测试预言机机制，以检查DBMS计算结果是否正确。测试预言机通常与半随机数据库和查询生成器或现有基准（如TPC-H或TPC-DS）相结合。TQS是一种自动化测试方法，用于检测查询优化中的逻辑错误。值得注意的是，它是测试连接优化的最先进方法。为了解决测试预言机问题，TQS通过表拆分模拟连接以推导查询的真实结果。具体来说，它通过将给定的表拆分成几个子表，并通过检索给定表来验证连接这些子表的查询结果来验证连接优化的正确性。为了生成更多的测试用例以发现更多的错误，TQS随机向这些子表中注入噪声，如NULL和空值，并将数据库模式建模为图数据模型以评估连接的相似性。通过这种方法，TQS发现了115个错误。

Limitations

然而，TQS存在两个主要挑战。首先，这种方法难以理解和实现。TQS需要拆分和维护与给定表相关的数据模式，并将数据模式建模为图形，以决定两个图形是否同构以评估查询的相似性。其次，测试范围较小。TQS只能应用于等值连接。尽管TQS论文中声称，该方法在概念上可以扩展到非等值连接，但该方法无法测试其他SQL特性，这些特性是通过TQS直接获得结果所必需的。

这个挑战不对吧，难以理解和实现怎么度量； 只能处理等值连接的话好像也没有给出直接的解决方案。image-20240710171737492

empirical study

为了理解TQS的错误发现效果，我们研究了公共问题追踪器中TQS的错误报告。我们识别了15个独特的错误，其中14个是通过展示使用不同查询提示执行相同查询会产生不同结果来报告的，如列表1所示。因此，不需要推导真实结果来发现这些错误。

image-20240710172524808

基于我们的观察，在本文中，我们提出了一种简单易懂的方法，以达到与TQS相同的错误发现效果。我们建议检查同一查询的不同查询计划执行结果的一致性，并将这种方法称为差异查询计划（Differential Query Plan，DQP）测试。更正式地说，给定一个数据库 $D$ 和一个查询 $Q$，DBMS 使用查询计划 $P$ 在 $D$ 上执行 $Q$ 以获得结果 $Q(P, D)$。对于另一个可能的查询计划 $P’$，如果 $Q(P, D) \neq Q(P’, D)$，则表示存在错误。

approach

为了将这种技术实现为一种不需要修改DBMS的黑箱方法，我们建议使用查询提示并设置DBMS已经提供的系统变量来影响生成的查询计划。我们认为这种技术显而易见且简单，但解决了TQS的两个挑战，并且具有与TQS相似的错误发现效果。此外，DQP可以测试更多的查询优化，而不仅仅是连接优化，因为查询提示和系统变量可以影响其他SQL特性的优化。重要的是，该方法易于实现，因为DQP不需要维护数据结构，如图和子表来推导真实结果。

optimizer hing and system variables 这个oracle太简单了吧

example

列表1展示了DQP在MySQL中发现的一个错误的示例。假设我们在一个银行场景中，MySQL将用户信息存储在user表中，将交易记录存储在transaction表中。前几行代码创建了两个表并插入数据。transaction_id列的数据由用户ID和随机生成的交易ID组成。第7行检查用户1的余额，并获得预期结果。如果查询结果使用了低效的查询计划，数据库管理员可能会通过在第8行添加查询提示来强制执行另一种查询计划。这个提示指示DBMS在进行连接时先处理transaction表。然而，这个查询返回了错误的结果。两个查询计划分别在第10至16行展示。这个错误可能会带来严重后果，因为用户1的所有资金都丢失了。

Implement and evaluation

DQP的实现：

  • DQP在每个DBMS上实现的代码不足100行，基于SQLancer框架。
  • 在MySQL、MariaDB和TiDB三个DBMS上评估DQP。

DQP的效果：

  • DQP能复现TQS发现的15个独特错误中的14个，其中包括所有10个与连接优化相关的错误。
  • DQP发现了26个以前未知且独特的错误，其中21个是逻辑错误。
  • 这些逻辑错误中有15个与连接优化相关，6个与其他查询优化相关。

与其他方法的对比：

  • DQP比TQS更简单但同样通用且高效。
  • 与NoREC和TLP方法对比：
    • NoREC和TLP无法找到DQP发现的21个逻辑错误中的17个。
    • DQP无法找到NoREC和TLP发现的40个逻辑错误中的35个。
  • DQP不仅是TQS的简单替代方案，还能补充NoREC和TLP。

贡献：

  • 研究了TQS在连接优化中发现逻辑错误的效果。
  • 证明了简单易懂的DQP测试方法与复杂的TQS具有相同的错误发现效果。
  • 实现并评估了DQP，发现了26个独特且以前未知的错误。
  • DQP的源代码公开可用，并已集成到SQLancer中。

TQS Study

RQ1：与连接相关的错误：

  • TQS报告的错误中有多少与连接优化相关？
  • TQS旨在发现连接优化中的错误，因此研究发现的错误有多少与此相关。

RQ2：错误的理由：

  • TQS报告的错误是如何被解释的？
  • 说服开发人员是DBMS而不是TQS计算了不正确的结果可能具有挑战性。
  • 发现错误的解释不是基于真实结果，这激发了我们提出更简单的测试方法。

2.1 TQS Summary

TQS的目的：检测连接优化中的逻辑错误。

TQS的两个主要组成部分：

  • 数据引导模式和查询生成（DSG）：

    • 将宽表作为输入表，通过数据库规范化将其拆分成多个子表，以减少数据冗余和依赖。
    • 随机构建查询以连接这些子表，并通过检索宽表推导真实结果。
    • 维护宽表和拆分表之间关系的过程复杂且必要。

  • 知识引导查询空间探索（KQE）：

    • 评估随机生成的查询是否与先前的查询相似，调整随机生成过程以减少生成相似查询的可能性。
    • 通过将数据库模式建模为嵌入式图来评估相似性，其中每个查询是一个子图，KQE检查两个子图是否同构。

  • 作者声称TQS在MySQL、MariaDB、TiDB和PolarDB中发现了115个错误，包括7种、5种和3种错误类型。

2.2 Study Scope

研究目标：选择TQS的公共错误列表作为研究目标。

数据来源：公共错误列表是唯一能够获取以研究TQS的数据来源，除了TQS的论文外。

代码获取情况：

  • 没有使用TQS的源代码，因为源代码不可用。
  • 作者在邮件中表示目前无法提供源代码。
  • 在第6节中解释了尝试获取源代码的过程。

2.3 Data Preprocessing

（无聊的废话）

目标DBMS：

  • 研究了MySQL、MariaDB和TiDB的错误报告。
  • TQS最初在MySQL、MariaDB、TiDB和PolarDB上进行评估，但公共错误列表中没有PolarDB的错误报告。
  • 研究了前三个DBMS的错误报告，TQS发现92个错误，实际公共错误列表中有21个（MySQL 11个，MariaDB 5个，TiDB 5个）。

防止遗漏错误报告：

  • 搜索了主要作者在相关问题追踪器中的提交历史，没有找到其他作者的账户。
  • 排除了被拒绝和非作者报告的错误。

错误类型匹配：

  • 验证92个错误是否对应于引发错误的测试案例，认为这些错误包括许多重复的无效错误。
  • 通过匹配分析和手动检查，确定公共错误列表中的错误与TQS论文中的错误类型相关联。

唯一错误：

  • 研究了20个错误报告的独特性。
  • 仔细检查开发人员的回应以确认错误是否重复。
  • 发现15个错误是独特的（MySQL 1个，TiDB 4个）。

RQ1 :与连接相关的错误：

  • 确认15个独特错误中有10个（67%）与连接优化相关。
  • 确认TQS的核心组件有助于发现这些错误。

RQ2: 错误的合理性：

  • 研究了错误描述和测试案例。
  • 发现15个独特错误中的14个是通过展示不同查询计划执行结果不一致来报告的。
  • 认为大多数错误可以通过检查相同查询的不同查询计划执行结果的不一致性来发现，这比TQS简单得多。
image-20240710174315325

APPROACHS

  • 核心思想：通过比较相同查询在不同查询计划下的结果来发现错误。
  • 与TQS的比较：
    • DQP不需要实现图和表结构来推导真实结果。
    • DQP支持发现各种查询优化中的错误，而不仅仅是等值连接优化中的错误。
  • 步骤：
    1. 数据库状态生成：
      • 生成一个数据库状态$D$。
      • 可以随机生成，也可以手动指定。
    2. 查询生成：
      • 随机生成一个查询$Q$，并自动验证其结果以发现错误。
    3. 查询计划执行：
      • 为$Q$执行查询计划$P$，并强制DBMS为相同查询执行另一查询计划$P’$。
      • 通过使用查询提示和系统变量来改变查询计划，而无需修改DBMS的源代码。
    4. 结果验证：
      • 比较$Q(P, D)$和$Q(P’, D)$的结果。
      • 如果结果不一致（$Q(P, D) \neq Q(P’, D)$），则表示存在潜在错误。
  • 关键贡献：展示了一个简单且易于理解的方法可以达到与复杂方法相同的性能水平。

IMPLEMENTATION

**4.1 Database and Query Generation **

方法：

  • 采用SQLancer提供的基于语法的随机生成方法，生成语法正确的SQL语句。
  • SQLancer对DBMS的SQL方言进行语法编码，DQP随机遍历相应的语法树以生成SQL语句。

数据库生成：

  • DQP生成非查询语句，如CREATE TABLE和CREATE INDEX。

查询生成：

  • DQP随机遍历语法树以生成查询语句，即SELECT语句。
  • 语法生成方法也用于TQS和SQLSmith。

生成连接查询：

  • SQLancer已为许多DBMS生成连接查询，但缺少对MySQL和MariaDB的支持。
  • 更新了SQLancer以支持为MySQL和MariaDB生成连接子句，参考了TiDB实现的连接代码。

4.2 Query Plan Enforcement

查询提示：

  • 查询提示是查询中的注释，可以影响查询优化器的行为。
  • 被许多流行的DBMS支持，如MySQL、MariaDB和TiDB。
  • 对于需要表或列名作为参数的查询提示，随机生成这些名称。
  • 示例：/*+ JOIN_ORDER(transaction, user)*/ 强制查询优化器以特定顺序连接两个表。

系统变量：

  • 设置影响查询优化器的系统变量。
  • 示例：optimizer_switch 变量影响查询优化。
  • 执行SET语句与查询一起配置系统变量以强制执行不同的查询计划。
  • 示例：在MariaDB中，SET STATEMENT optimizer_switch='index_merge=on' FOR SELECT t0.c0 FROM t0 配置系统变量以控制索引合并优化。

效率考虑：

  • 为测试效率，通过迭代枚举所有可能的查询提示和系统变量值来执行多个查询计划。
  • 观察到查询提示和系统变量值数量有限且较小。
  • 从DBMS文档中提取了不同DBMS的查询提示和系统变量选项数量（例如MySQL中有32个查询提示和26个optimizer_switch变量选项，TiDB中有22个查询提示）。
  • 为简单起见，只展示了$P$和$P’$的执行结果。

4.3 Result Validation

初步观察：

  • 在步骤④中观察到误报。
  • 这些误报源于模糊查询，即结果不保证一致或可预测的查询。

排除误报：

  • 通过检查表中行顺序不同是否影响结果来识别模糊查询。
  • 实施此技术后，没有观察到误报。

迭代过程：

  • 在一个迭代后，DQP继续步骤①或②开始新迭代。
  • 因生成$D$相对较慢，DQP默认返回步骤②。

模糊Ambiguous查询：

  • 模糊查询可能引发误报。
  • 一种模糊查询类型包括在SELECT子句中包含非聚合列。
  • 在TiDB测试中遇到的具体示例显示不同结果，因为查询返回组中的随机行。

模糊查询识别算法：

  • 检查表中行顺序不同是否影响验证结果。
  • 为减少计算复杂度，最小化$Q$和$D$。
  • 多次执行查询以识别模糊查询。
  • 如果验证结果不同，则该查询被视为模糊查询。

算法可扩展性：

  • 认为在实际操作中，算法是可行的，因为最小化后数据库较小。
  • 通过最小化测试用例，循环执行次数成指数级减少。

EVALUATION

评估目标：

  1. 错误再现：DQP能否找到TQS发现的错误？
  2. 新错误：DQP能否发现以前未知的错误？
  3. 错误发现效率：DQP发现错误的效率如何？
  4. 错误发现效果：DQP在发现逻辑错误方面的效果如何，与其他测试预言机相比如何？
  5. 覆盖范围：DQP在多大程度上覆盖查询优化器？

测试的DBMS：

  • 使用了与第2节中相同的DBMS：MySQL、MariaDB和TiDB。
    • MySQL是最流行的关系型DBMS之一。
    • MariaDB是从MySQL分叉出来的另一个流行的DBMS。
    • TiDB是一个流行的企业级DBMS。
  • 由于TQS作者未发布PolarDB的错误报告，未对PolarDB进行测试。
  • 使用了最新的开发版本（MySQL: 8.1.0, MariaDB: 11.1.2, TiDB: 7.4.0）和与TQS相同的版本（MySQL: 8.0.28, MariaDB: 10.8.2, TiDB: 5.4.0）。
  • 所有DBMS均在默认配置下运行。

Q.1 Bug Reproduction

  • 评估目的：确定DQP是否能找到TQS发现的逻辑错误。
  • 方法：
    • 使用TQS公共错误报告中的测试用例作为初始数据库状态和原始查询。
    • 根据DQP步骤③，为查询执行不同的查询计划。
    • 如果原始查询和派生查询的结果不一致，认为DQP能发现该错误。
  • 结果：
    • DQP能识别TQS报告的15个独特错误中的14个。
    • 所有10个与连接相关的错误均能被DQP发现。
    • DQP通过添加no_semi_join查询提示，能够发现TQS作者通过比较执行结果与真实结果不同而发现的错误。
    • 结果表明，DQP可以发现TQS发现的绝大多数错误。

总结：DQP可以检测到14个独特错误中的14个，以及TQS发现的所有10个与连接相关的错误。

Q.2 New Bugs

  • 方法：
    • 运行SQLancer+DQP两次，每次24小时，旨在发现错误。
    • 禁用在第一次运行中导致错误的查询提示和系统变量，减少找到重复错误的可能性。
    • 只报告可能是独特的错误，每个查询提示和系统变量的每个选项最多报告一个错误。
  • 结果概述：
    • 找到26个新的、以前未知的错误，并提交了32个错误报告。
    • 26个错误被确认是独特且以前未知的，1个是重复的，1个等待进一步分析，4个是由于模糊查询引起的误报。
    • 21个新错误是逻辑错误，15个与连接优化相关。
    • 逻辑错误是由于相同查询在不同查询计划下返回的不一致结果导致的。
  • 错误严重性：
    • TiDB：12个发现的错误中有14个被指定为严重或关键。
    • MySQL和MariaDB：错误严重性由用户指定，通常不更新，但提供了TQS报告中的错误严重性作比较。
    • 例子1：通过设置系统变量发现的错误（MySQL中的#112242），指定为严重。
    • 例子2：通过设置查询提示发现的错误（TiDB中的#46580），指定为关键。

总结：SQLancer+DQP发现了26个新的、以前未知的错误，其中21个是逻辑错误，15个与连接优化相关。通过设置系统变量和查询提示，有效发现了严重或关键错误。

image-20240711110304264 image-20240711110443652

Q.3 Bug-finding Efficiency

  • 评估目标：评估DQP在24小时内能找到多少错误。
  • 方法：
    • 使用SQLancer的默认配置运行DQP 24小时，测量导致错误的测试用例数量。
    • 排除导致崩溃或内部错误的错误，因为这些不是直接由DQP发现的。
    • 与TQS进行比较，但由于源代码不可用和实验配置不明确，比较存在挑战。
  • 比较挑战：
    • TQS和DQP都采用基于语法的测试用例生成方法，但实现细节不明确。
    • TQS支持多线程，但未找到使用的线程数量。
    • TQS和DQP在不同机器上评估，影响效率结果的直接可比性。
  • 结果：
    • DQP在MySQL、MariaDB和TiDB中找到216个导致错误的测试用例。
    • 具体数量：MySQL找到24个，MariaDB找到120个，TiDB找到72个。
    • 由于崩溃错误，MySQL和TiDB在约9小时后退出。
    • DQP在错误检测效率上相对于TQS显示出显著进步，尽管两者之间的直接比较具有挑战性。
    • 大量导致错误的测试用例显示SQLancer+DQP在没有复杂技术改进测试用例生成的情况下也能高效运行。

总结：SQLancer+DQP在24小时内在MySQL、MariaDB和TiDB中发现216个导致错误的测试用例，展示了其高效的错误发现能力。

Q.4 Bug-finding Effectiveness

  • 比较对象：
    • 将DQP与两种最先进的逻辑错误测试预言机NoREC和TLP进行比较。
    • NoREC检查DBMS可能优化的谓词的不一致结果。
    • TLP生成多个复杂查询，检查组合分区和原始查询结果是否等效。
    • 未考虑其他测试预言机如PQS，因为其不支持SQLancer中评估的三个DBMS。
  • 方法：
    • 采用与之前研究相同的方法，通过手动和尽力分析识别DQP、NoREC和TLP找到的重叠和独特错误。
    • 仅考虑最小化的测试用例，假定每个测试用例代表一个独特的错误。
    • 收集了从MySQL、MariaDB和TiDB的公共错误列表中获得的41个逻辑错误，确认其中40个可复现。
    • 使用DQP、NoREC和TLP的测试用例交叉验证彼此的错误检测能力。
  • 结果：
    • DQP发现的21个逻辑错误中，有17个NoREC和TLP无法发现。
    • DQP无法复现NoREC发现的4个错误和TLP发现的31个错误中的5个。
    • DQP发现的错误与NoREC和TLP发现的错误很少重叠，表明DQP是NoREC和TLP的补充。
  • 示例：
    • 示例展示了如何通过不同查询重写策略使NoREC和TLP发现错误，但某些情况下需要特定选项（如use_invisible_indexes=on）来暴露错误。

总结：DQP在错误发现方面表现出色，发现了NoREC和TLP无法发现的大多数逻辑错误，显示了DQP在与其他预言机结合使用时的互补性和有效性。

Q.5 Coverage

  • 评估目标：评估DQP对查询优化器的覆盖情况。
  • 指标：
    • 计划覆盖率（Plan Coverage）：衡量DQP覆盖的唯一查询计划比例。
    • 提示和变量覆盖率（Hint and Variable Coverage）：评估查询提示和系统变量对查询优化器的影响程度。
    • 连接覆盖率（Join Coverage）：评估DQP覆盖的连接操作符数量。
    • 代码覆盖率（Code Coverage）：评估系统代码的测试覆盖程度。
  • 计划覆盖率：
    • 计算DQP覆盖的唯一查询计划比例。
    • 使用SQLancer+DQP生成的所有唯一查询计划作为上限。
    • DQP在MySQL、MariaDB和TiDB中的平均计划覆盖率分别为15.42%、18.17%和13.34%。
    • DQP在TiDB中的表现最佳，可能原因是TiDB包含比其他DBMS更丰富的查询元素。
  • 提示和变量覆盖率：
    • 识别三个影响查询优化的类别：Join、Index、Table。
    • MySQL、MariaDB和TiDB分别有42、35和40个相关查询提示或系统变量。
    • SQLancer+DQP在MySQL、MariaDB和TiDB中的提示和变量覆盖率分别为27.22%、22.27%和36.1%。
  • 连接覆盖率：
    • 检查SQLancer+DQP在24小时内覆盖的连接操作符数量。
    • MySQL和MariaDB共有12个连接操作符，TiDB有3个。
    • SQLancer+DQP覆盖了MySQL和MariaDB的7个连接操作符，TiDB的所有3个连接操作符。
  • 代码覆盖率：
    • 使用gcov和cover工具收集MySQL、MariaDB和TiDB的代码覆盖率。
    • SQLancer+DQP的代码覆盖率：MySQL和MariaDB的22.22%、27.17%，TiDB的36.1%。
    • 由于资源限制，仅测量了查询优化代码的覆盖率。

总结：DQP在查询优化器的覆盖率方面表现出色，特别是在计划和连接覆盖率上，但代码覆盖率较低。尽管如此，这表明DQP在覆盖查询优化器方面具有一定的有效性。