Testing Database Systems via Differential Query Execution

Testing Database Systems via Differential Query Execution

Basic Information:

• Title: Testing Database Systems via Differential Query Execution (通过差异查询执行测试数据库系统)
• Authors: Jiansen Song, Wensheng Dou, Ziyu Cui, Qianwang Dai, Wei Wang, Jun Wei, Hua Zhong, Tao Huang
• Affiliation: State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences; University of Chinese Academy of Sciences; Nanjing College; Nanjing Institute of Software Technology
• Keywords: Database system, DBMS testing, logic bug
• URLs: Paper, GitHub

论文简要 :

• 本文提出了一种名为差异查询执行（Differential Query Execution，DQE）的新颖通用方法，用于检测数据库管理系统（DBMS）中SELECT、UPDATE和DELETE查询中的逻辑错误。通过在五个生产级DBMS上的实验，发现了50个独特的逻辑错误，并成功修复了其中的11个。

背景信息:

• 论文背景: 数据库管理系统（DBMS）通过结构化查询语言（SQL）提供高效的数据检索和操作。然而，DBMS的错误实现可能导致逻辑错误，从而导致SELECT查询返回错误结果，或者UPDATE和DELETE查询生成错误的数据库状态。现有方法主要集中在检测SELECT查询中的逻辑错误，而UPDATE和DELETE查询中的逻辑错误尚未得到解决。
• 过去方案: 过去的方法主要集中在检测SELECT查询中的逻辑错误，如RAGS、PQS、NoREC和TLP等。然而，这些方法无法检测UPDATE和DELETE查询中的逻辑错误，尽管这些错误可能导致更严重的后果。
• 论文的Motivation: 鉴于现有方法无法解决UPDATE和DELETE查询中的逻辑错误，本文提出了一种新颖的通用方法DQE，通过执行具有相同谓词的SELECT、UPDATE和DELETE查询，并观察它们的执行结果之间的不一致性，来检测这些查询中的逻辑错误。通过在五个生产级DBMS上的实验，验证了DQE的有效性和通用性，并发现了多个未知的逻辑错误。

方法:

• a. 理论背景:
  • 本文提出了一种名为差异查询执行（Differential Query Execution，DQE）的新方法，用于检测数据库管理系统（DBMS）中SELECT、UPDATE和DELETE查询中的逻辑错误。DQE的核心思想是使用相同的谓词执行不同的SQL查询，并观察它们执行结果的不一致性。该方法旨在自动识别DBMS中的逻辑错误，特别是在UPDATE和DELETE查询中，这些错误在现有方法中尚未得到有效解决。DQE通过执行具有相同谓词的查询并比较它们的结果来解决构建有效的测试预言的挑战。作者实现了DQE并在五个广泛使用的DBMS上评估了其有效性，发现了41个以前未知的错误，其中20个出现在UPDATE和DELETE查询中。
• b. 技术路线:
  • 生成数据库和查询三元组的过程：首先通过创建表格和使用INDEX命令和随机选项对其进行修改来生成初始数据库。然后为每个表格添加两个新列rowId和updated，以唯一标识行并跟踪修改。使用基于SQL的抽象语法树（ASTs）的算法随机生成谓词来进行谓词生成。基于生成的谓词生成包含SELECT查询（Qsel）、UPDATE查询（Qup）和DELETE查询（Qdel）的查询三元组。使用谓词中引用的表格来生成Qsel的选择字段和Qup的更新字段。还可以为查询三元组生成可选的子句，如ORDER BY。使用目标DBMS提供的诊断命令获取查询引发的错误。通过将选择字段与rowId列连接并执行修改后的查询来获取SELECT查询访问的行。通过将更新字段与更新列的赋值连接并执行修改后的查询来获取UPDATE查询访问的行。

结果:

• a. 详细的实验设置:
  • 作者在五个广泛使用且生产级别的DBMS上实现和评估了DQE，包括MySQL、MariaDB、TiDB、CockroachDB和SQLite。他们在这些DBMS中检测到了41个以前未知的错误，其中20个出现在UPDATE和DELETE查询中。实验结果表明，DQE在检测DBMS中SELECT、UPDATE和DELETE查询的逻辑错误方面具有有效性。作者已经公开提供了DQE供使用。

ABSTRACT：

这篇论文提出了一种名为差分查询执行（DQE）的新方法，用于检测数据库管理系统（DBMS）中SELECT、UPDATE和DELETE查询的逻辑错误。DQE的核心思想是：具有相同谓词的不同SQL查询通常会访问数据库中的相同行。比如，使用谓词φ的UPDATE查询更新的行，也应该被具有相同谓词φ的SELECT查询获取。如果不是这样，就暴露了目标DBMS中的逻辑错误。研究者在五个生产级别的DBMS上应用了DQE，包括MySQL、MariaDB、TiDB、CockroachDB和SQLite，共检测到50个独特的错误，其中41个已被确认，11个已被修复。这表明DQE的简单性和通用性可以大大提高DBMS的可靠性。

INTRODUCTION：

背景：

DBMS（例如MySQL、MariaDB、TiDB、CockroachDB和SQLite）使用结构化查询语言（SQL）来高效检索和操作数据库中的数据，并在许多业务关键应用中发挥着不可或缺的作用。DBMS可能遇到的不同类型的错误，特别是逻辑错误，这些错误可能导致SELECT查询返回错误结果，或者UPDATE和DELETE查询产生错误的数据库状态。这些逻辑错误通常不会导致DBMS崩溃，因此开发者可能不容易注意到它们。本研究的重点是检测DBMS中的这类逻辑错误。

相关工作以及局限性：

数据库管理系统（DBMS）中检测逻辑错误的几种方法，特别是针对 SELECT 查询的方法。提到的方法包括 RAGS（通过在多个DBMS上运行相同的SELECT查询来检测结果差异），PQS（生成特定行的SELECT查询来检测DBMS是否能正确检索这行），NoREC（通过重写SELECT查询为一个DBMS无法优化的等效查询来检测结果差异），以及TLP（将SELECT查询分解为三个部分查询，然后将这些部分的结果合并，预期与原始查询结果相同）。

然而，这些方法主要关注于SELECT查询中的逻辑错误，而对于可能导致更严重后果的UPDATE和DELETE查询中的逻辑错误，尚未有有效的检测方法。自动检测这些错误是一个挑战，因为需要构建一个有效的测试预言机（test oracle）来判断给定查询的DBMS行为是否正确。

文章还讨论了SELECT、UPDATE和DELETE查询中的谓词（WHERE子句）使用问题。理想情况下，DBMS应该对这三种查询中的谓词评估采用相同的实现方式。但由于优化选择的多样性，DBMS通常采用不同的实现方式来评估这些查询中的谓词，导致使用相同谓词的SELECT、UPDATE和DELETE查询可能会访问不同的行。1https://bugs.mysql.com/bug.php?id=106420

(这里使用bug report的引用来说明SELECT UPDATE和DELETE的实现逻辑不同，是不是有点牵强?）

Key insight以及面临的挑战：

本文提出了一种差异查询执行（Differential Query Execution, DQE）的新方法，用于检测SELECT、UPDATE和DELETE查询中的逻辑错误。DQE通过执行具有相同谓词φ的SELECT、UPDATE和DELETE查询，并观察它们执行结果之间的不一致性来解决测试预言机问题。例如，如果一个UPDATE查询更新的行在具有相同谓词φ的SELECT查询结果中没有出现，这表明目标数据库管理系统（DBMS）存在逻辑错误。

DQE面临的主要挑战是如何自动获取给定SELECT、UPDATE或DELETE查询所访问的行。为了解决这个挑战，DQE方法在数据库中的每个表格中添加两个额外的列，一个用于唯一标识每一行，另一个用于跟踪行是否被修改。此外，DQE还重新编写SELECT和UPDATE查询，以便识别它们所访问的行。

Motivation example:

这个错误涉及UPDATE和DELETE查询，它们意外地改变了数据库状态。具体来说，有一个表t1，包含一个INT类型的行，其值为1。使用的谓词φ是一个空字符串。在处理这三种查询时（SELECT、UPDATE和DELETE），TiDB尝试将φ转换为布尔值。

对于SELECT查询，TiDB首先将φ截断为DOUBLE类型的值0，然后将其转换为布尔值FALSE。因此，SELECT查询得到一个空的查询结果，并引发一个警告。而对于UPDATE和DELETE查询，TiDB错误地将φ评估为TRUE，导致数据库状态发生了意外的变化。这个错误在报告给TiDB开发者后得到了确认和修复。现有的检测方法无法发现这个错误，因为它仅发生在UPDATE和DELETE查询中。

评估：

为了评估差异查询执行（DQE）的有效性和通用性，研究者们实施了DQE，并在五个广泛使用的、生产级别的数据库管理系统（DBMS）上进行了实验。这些系统包括MySQL、MariaDB、TiDB、CockroachDB和SQLite。通过这些实验，共检测到了50个独特的错误，在这些DBMS中，其中41个被确认为新的错误，并且已有11个错误得到修复。在这41个确认的错误中，20个发生在UPDATE和DELETE查询中。他们检测到的错误无法被现有的方法（如PQS、NoREC和TLP）检测到。实验结果表明，DQE在检测DBMS中的SELECT、UPDATE和DELETE查询的逻辑错误方面是有效的。DQE的代码已经在GitHub上公开。

(是指20个发生在UPDATE和DELETE的错误没法被现有工具检测到还是全部？)

limitations:

DQE虽然在目标数据库管理系统（DBMS）的SELECT、UPDATE和DELETE查询中检测到了许多错误，但仍存在一些限制。首先，DQE受到与差异测试相同的问题的影响，即当相同的错误同时出现在SELECT、UPDATE和DELETE查询中时，DQE无法检测到这个错误。其次，DQE只支持SELECT、UPDATE和DELETE查询中的常见操作和函数，如JOIN、ORDER BY和LIMIT。它不支持只在一种查询中使用的操作和函数，例如只在SELECT查询中使用的DISTINCT、子查询、基于聚合的函数、窗口函数和GROUP BY。对于这些特性，DQE无法比较它们在SELECT、UPDATE和DELETE查询中的执行结果。第三，DQE不支持非确定性函数，例如RAND函数，这种函数在不同查询中返回不同的值。

贡献：

1. 提出DQE方法：这是一种新颖且通用的方法，用于检测数据库管理系统（DBMS）中SELECT、UPDATE和DELETE查询的逻辑错误。据作者所知，DQE是首个能够检测出UPDATE和DELETE查询中逻辑错误的方法。
2. 在五个广泛使用的DBMS上实施和评估DQE：通过在这些DBMS上的实现和评估，DQE检测到了41个以前未知的错误，其中20个错误发生在UPDATE和DELETE查询中。这表明DQE在检测这类错误方面具有有效性。

PRELIMINARIES

A. Database Management Systems and SQL

1. 数据库管理系统（DBMS）的广泛应用：DBMS在许多应用程序中被广泛使用，以实现有效的数据检索和操作。主流的DBMS（例如MySQL、MariaDB、TiDB、CockroachDB和SQLite）采用关系数据模型，这种模型将数据组织成关系表，因此这些系统被称为关系型数据库管理系统。
2. 结构化查询语言（SQL）：关系型DBMS通常采用SQL作为查询语言。在SQL中，SELECT、UPDATE和DELETE查询通过谓词（即WHERE子句）来确定要检索、更新或删除的行。DBMS通常采用复杂的优化技术来提高查询评估的性能。
3. 优化过程的差异：尽管对于相同的谓词，DBMS可以在SELECT、UPDATE和DELETE查询中应用不同的优化，但无论应用何种优化，具有相同谓词φ的SELECT、UPDATE和DELETE查询理应访问相同的行。例如，MySQL开发人员指出，虽然所有的数据操纵语言（DML）语句都必须经过优化阶段，但SELECT和UPDATE查询不会经过相同的优化过程。

B. Target DBMSs

这段文字讨论了研究所关注的五个生产级别且广泛使用的数据库管理系统（DBMS）：MySQL、MariaDB、TiDB、CockroachDB和SQLite。选择这些DBMS的依据是它们的流行度和数据库类型。

1. 流行度和排名：根据DB-Engines Ranking，MySQL、SQLite和MariaDB是最受欢迎的DBMS之一，在全球排名分别为第2、第9和第13位。
2. DBMS的类型和特点：
   • MySQL和MariaDB是传统的DBMS，已经开发了数十年。
   • SQLite是一个嵌入式DBMS，是最广泛部署的DBMS。
   • 根据GitHub Database Topic，TiDB和CockroachDB是最受欢迎的关系型DBMS（分别拥有33.3K和26.5K星）。
   • CockroachDB和TiDB是具有高可扩展性的分布式NewSQL DBMS。

C. Query Execution Strategy

不同数据库管理系统（DBMS）在SELECT、UPDATE和DELETE查询中的SQL查询执行策略，尤其关注它们如何处理语法和语义错误，这对于DQE（差异查询执行）分析查询执行情况至关重要。

1. MySQL、MariaDB和TiDB的策略：这三个DBMS采用相同的查询执行策略。当查询评估中出现语法或语义错误时，这些系统会根据错误的严重性引发警告或错误。例如，使用无效值时会引发警告，而语法上无效的谓词会引发错误。如果评估查询时出现警告，DBMS可以继续执行查询；但如果出现错误，则会中止并回滚查询。这三个DBMS在不同的SQL模式下执行查询，影响查询执行策略。在严格模式下，对于UPDATE和DELETE查询会采用严格的验证检查。如果SELECT查询中的谓词引发警告，在UPDATE和DELETE查询中会将其视为错误。

   STRICT_ALL_TABLES和STRICT_TRANS_TABLES是两种SQL模式设置，它们用于定义如何处理数据验证和错误。

   1. STRICT_ALL_TABLES：当这个模式被激活时，DBMS对所有表执行严格的数据验证。这意味着如果插入或更新的数据行违反了列定义（例如，超出指定的长度或类型），DBMS将拒绝这个操作并显示错误。这个模式有助于确保数据的完整性和一致性，因为它阻止了无效数据的输入。
   2. STRICT_TRANS_TABLES：这个模式与STRICT_ALL_TABLES相似，但它主要适用于具有事务支持的表。在这个模式下，如果在事务处理过程中的任何点上违反数据完整性，则整个事务都会被回滚，确保数据库状态的一致性。

   假设我们有一个名为users的表，其中有一个名为age的列，其数据类型为整数（INT），并且这个列不允许为空（NOT NULL）。

   1. STRICT_ALL_TABLES模式：
      • 在这种模式下，如果你尝试插入一条新的记录到users表中，但没有提供age字段的值，数据库将拒绝这个插入操作并显示一个错误。这是因为age字段被定义为NOT NULL，而在STRICT模式下，任何违反列定义的操作都会被阻止。
      • 示例命令：INSERT INTO users (name) VALUES ('Alice');
      • 结果：由于age字段缺失，操作将失败并显示错误。
   2. STRICT_TRANS_TABLES模式：
      • 假设users表是一个事务支持的表（例如，在InnoDB引擎中）。在STRICT_TRANS_TABLES模式下，如果你在一个事务中执行多个操作，其中一个操作违反了数据完整性，那么整个事务都会被回滚。
      • 示例：
        • 开始一个事务：START TRANSACTION;
        • 正确插入：INSERT INTO users (name, age) VALUES ('Bob', 25);
        • 错误插入：INSERT INTO users (name) VALUES ('Charlie');（由于缺少age，这将失败）
        • 提交事务：COMMIT;
      • 结果：第二个插入操作将失败，并且由于是在STRICT_TRANS_TABLES模式下，整个事务（包括第一个成功的插入）都会被回滚，数据库中不会添加任何新记录。

   这两种模式通过增加严格性来提高数据的完整性，确保只有符合定义的数据才能被存储到数据库中。

2. CockroachDB和SQLite的策略：这两个DBMS采用较为简单的查询执行策略。在这两个系统中，SELECT、UPDATE和DELETE查询在评估谓词时出现语法或语义错误只会引发错误，不会引发警告。如果UPDATE或DELETE查询引发错误，将会被回滚，并撤销所有由该查询所做的更改。然而，如果SELECT查询引发错误，它将返回在错误发生之前匹配其谓词的所有行，这意味着SELECT查询即使在引发错误时也可能返回非空的查询结果。

这个例子描述了SQL查询在不同SQL模式下如何处理针对特定谓词φ的警告和错误。

1. 严格模式（Strict Mode）：在严格模式下，DBMS对UPDATE和DELETE查询采用严格的验证检查。特别是，如果一个带有谓词φ的SELECT查询引发了一个警告，在相同谓词φ的UPDATE和DELETE查询中，这个警告会被当作错误处理（并带有相同的错误消息）。
2. 非严格模式（Non-Strict Mode）：在非严格模式下，如果一个带有谓词φ的SELECT查询引发了警告，带有相同谓词φ的UPDATE和DELETE查询也会引发相同的警告。值得注意的是，如果带有谓词φ的SELECT查询引发了错误，在严格模式和非严格模式下，相同谓词φ的UPDATE和DELETE查询也会引发相同的错误。

这个例子说明了在不同的SQL模式下，DBMS如何根据SELECT查询的警告或错误来调整UPDATE和DELETE查询的行为。在严格模式下，警告被升级为错误，而在非严格模式下，相同的警告被保留。在任何模式下，如果SELECT查询引发错误，UPDATE和DELETE查询也会引发同样的错误。

APPROACH

A. DQE Overview

它的工作流程如下：

1. 生成随机数据库（步骤1）：创建包含一个或多个表（如t1、t2）的数据库，每个表包含一些随机列和数据（例如，表t1有一个值为’a’和’b’的列c1）。
2. 生成随机谓词φ（步骤2）：随机生成一个谓词，例如NOT c1。
3. 生成查询三元组< Qsel, Qup, Qdel >（步骤3）：基于谓词φ生成一组查询，包括SELECT查询（Qsel）、UPDATE查询（Qup）和DELETE查询（Qdel）。这三个查询都使用相同的谓词φ。
4. 执行查询三元组（步骤4）：在相同的数据库状态下执行Qsel、Qup和Qdel，并分析它们的执行结果。
5. 分析执行结果（步骤5）：分析SELECT查询的结果集rs、执行UPDATE查询后修改的表tu以及执行DELETE查询后修改的表td。特别关注这些查询访问的行和引发的错误。
6. 检测逻辑错误（步骤6）：如果查询三元组中的三个查询的执行结果不一致（例如，访问了不同的行），则表明目标DBMS中可能存在潜在的逻辑错误。

接下来的部分分别描述了数据库生成（第III-B节）、SQL查询生成策略（第III-C节）、获取查询三元组执行结果的方法（第III-D节）以及如何通过比较三个查询的执行结果来检测逻辑错误（第III-E节）。

B. Database Generation

数据库生成的过程，主要采用了SQLancer的方法，用于实验中的数据库准备。这个过程不是研究的主要贡献，但为了完整性而被提及。

1. 创建表格：使用CREATE TABLE命令创建最多maxTable个表格。每个表格包含最多maxCol个列。为每个列随机分配一个列类型（如INT或TEXT）和一些列约束（如PRIMARY KEY和UNIQUE）。
2. 填充数据：通过执行INSERT命令向每个表中填充随机数据。每个表包含最多maxInsert行数据。
3. 修改表格结构：执行最多maxAlter个ALTER TABLE和CREATE INDEX命令来修改每个初始表格，例如添加新列或在现有列上建立索引。还配置每个表格的随机选项，比如设置自增列的起始编号（例如AUTO_INCREMENT=5）。
4. 参数配置：maxTable、maxCol、maxInsert、maxAlter都是可配置的参数。在实验中，默认设置分别为5、3、10、3。
5. 增加特殊列：在生成的数据库中，每个表格被修改以添加rowId和updated列。rowId列用于唯一标识每行，通常为TEXT类型，填充唯一值（如UUID）。updated列用于跟踪每行的修改情况，通常为INT类型，默认值为0。这两个新增加的列用于后续部分中获取查询访问的行，但不用于查询三元组生成。
6. 针对不同DBMS的特定生成：数据库生成过程针对不同的DBMS进行了特定的调整。不同的DBMS支持不同的列类型、列约束和表选项。例如，CockroachDB支持INTERVAL列类型，而MySQL则不支持。

C. Query Triple Generation

这段文字描述了查询三元组< Qsel, Qup, Qdel >的生成过程，其中Qsel、Qup和Qdel使用相同的谓词φ。整个过程包括谓词的生成和基于谓词生成三种查询（SELECT、UPDATE、DELETE）。

1. 谓词生成：使用一种算法，基于SQL的抽象语法树（AST）随机生成谓词。随机选择节点类型（CONST、COLUMN或操作符），如果是CONST，则生成一个常量值；如果是COLUMN，则随机返回数据库中表的列引用；如果是操作符，则迭代生成其操作数。当AST达到最大深度（maxDepth，实验中默认设为3）时，只生成常量或列引用，不再扩展AST。
2. 查询三元组生成：基于谓词φ，随机生成Qsel、Qup和Qdel。首先提取谓词φ中引用的表，这些表将用于Qsel、Qup和Qdel。然后为Qsel生成选择字段，为Qup生成更新字段。Qsel的选择字段是列引用列表，Qup的更新字段是赋值列表。最后，生成通用支持的可选子句（如ORDER BY）。
3. 查询生成的支持和限制：DQE支持SELECT、UPDATE和DELETE查询中的常见操作和函数，但不支持仅在一种查询中使用的操作和函数，如仅在SELECT查询中使用的DISTINCT、基于聚合的函数、窗口函数和GROUP BY。DQE也不支持非确定性函数，如返回随机值的RAND函数。查询生成过程针对不同DBMS进行了特定的调整。

举例，可以生成如下查询三元组：

• 

1. 聚合函数：聚合函数对一组值进行计算，并返回单个值。它们通常用于统计分析，例如计算总和、平均值、最大值、最小值等。聚合函数对整个数据集或分组的数据集进行操作。常见的聚合函数包括：

   • SUM()：计算数值列的总和。
   • AVG()：计算数值列的平均值。
   • COUNT()：计算数据集中的项数。
   • MAX()：找出列中的最大值。
   • MIN()：找出列中的最小值。

   使用聚合函数时，通常会结合GROUP BY子句来对数据进行分组，然后对每个组应用聚合函数。

2. 窗口函数：窗口函数对数据集的一部分（称为“窗口”）执行计算，这部分数据与查询结果中的当前行相关。与聚合函数不同，窗口函数不会将行组合成单个输出行 — 它们会为每个输入行返回一个值。因此，窗口函数可以用来执行更复杂的计算，如累积总和、移动平均等。常见的窗口函数包括：

   • ROW_NUMBER()：为每个窗口内的行分配一个唯一的序号。
   • RANK() 和 DENSE_RANK()：为窗口内的行提供排名。
   • LEAD() 和 LAG()：访问窗口内的后续行或前置行的数据。
   • SUM()、AVG() 等聚合函数也可以用作窗口函数。

   窗口函数通常与OVER子句一起使用，以定义窗口的范围和排序。

（和PINOLO的生成方式很像啊）

D. Obtaining Execution Results

这段文字描述了如何获取生成的查询三元组< Qsel, Qup, Qdel >的执行结果。这个过程包括两个主要部分：获取由查询引发的错误和自动获取查询访问的行。

1. 获取查询引发的错误：
   • 当SELECT、UPDATE和DELETE查询评估时出现语法或语义错误，它们可能引发错误（在MySQL、MariaDB和TiDB中有时是警告）。
   • 特别是，UPDATE查询（Qup）可能违反表约束（如NOT NULL和UNIQUE）并在更新引用表时引发特定于UPDATE的错误。类似地，DELETE查询（Qdel）可能违反表约束（如FOREIGN KEY）并在删除引用表中的数据时引发特定于DELETE的错误。
   • 为了获取查询引发的错误，使用目标DBMS提供的诊断命令，如MySQL、MariaDB和TiDB中的SHOW WARNINGS命令。CockroachDB和SQLite没有这样的诊断命令，因此在这两个DBMS中使用Java中的SQLException来获取引发的错误。
   • 
2. 获取SELECT查询（Qsel）访问的行：
   • 为了获取SELECT查询返回的行，将Qsel的选择字段与其引用表的rowId列一起附加，形成一个新的SELECT查询Q’ sel。
   • 执行Q’ sel后，从其结果集中提取rowId列的值。
   • 
3. 获取UPDATE查询（Qup）访问的行：
   • 为了获取UPDATE查询更新的行，将Qup的更新字段与其引用表的updated列的赋值列表一起附加，形成一个新的UPDATE查询Q’ up。
   • 执行Q’ up后，从每个引用表中提取updated列值等于1的rowId列的值。
   • 
4. 获取DELETE查询（Qdel）访问的行：
   • 为了获取DELETE查询删除的行，比较执行Qdel之前后每个引用表中rowId列的值。
   • 执行Qdel后，查看被删除的rowId列的值。
   • 

E. Comparing Execution Results

这段文字讲述了如何比较和分析在不同数据库管理系统（DBMS）中SELECT、UPDATE和DELETE查询（即Qsel、Qup和Qdel）的执行结果，以检测目标DBMS中是否存在逻辑错误。这一过程涉及到对查询访问的行集合（分别标记为rowsel、rowup和rowdel）的比较。

1. 针对MySQL、MariaDB和TiDB的比较规则：这些系统中，如果Qup和Qdel分别引发了特定于UPDATE和DELETE的错误，则不会与Qsel的执行结果进行比较。在不违反以下规则的情况下，如果任何规则被违反，DQE将报告一个错误：
   • 如果Qsel引发错误，则Qup和Qdel也应引发相同的错误，此时rowsel、rowup和rowdel应为空。
   • 在严格模式下，如果Qsel引发警告，则Qup和Qdel应引发错误，且警告和错误应具有相同的错误代码和消息（除了错误级别不同）。此时rowup和rowdel应为空。
   • 在非严格模式下，如果Qsel引发警告，则Qup和Qdel也应引发相同的警告，此时rowsel、rowup和rowdel应相同。
   • 如果Qsel没有引发警告或错误，则Qup和Qdel也不应引发警告或错误，此时rowsel、rowup和rowdel应相同。
2. 针对CockroachDB和SQLite的比较规则：在这些系统中，规则略有不同：
   • 如果Qsel引发错误，则Qup和Qdel也应引发相同的错误。但与MySQL、MariaDB和TiDB不同，此时rowsel可能不为空，而rowup和rowdel应为空。
   • 如果Qsel没有引发警告或错误，则Qup和Qdel也不应引发警告或错误，此时rowsel、rowup和rowdel应相同。

EVALUATION

DQE是基于SQLancer（一个用Java实现的工具）开发的，并对其进行了以下改进：

1. 改进点：
   • 首先，为目标数据库管理系统（DBMS）添加了UPDATE和DELETE查询的生成能力，例如MySQL、TiDB和SQLite。
   • 其次，为了确保在相同的数据库状态下执行查询三元组（Qsel, Qup, Qdel），在MySQL、MariaDB和TiDB中使用ROLLBACK事务来回滚由UPDATE和DELETE查询所做的所有更改。在CockroachDB和SQLite中，则通过记录查询执行前的表内容并在查询执行后用相同的内容填充表来维护数据库状态。
   • 为了在五个目标DBMS上实现DQE，编写了大约2600行代码。
2. 评估效果：
   • 研究团队通过回答两个研究问题来评估DQE的有效性：
     • RQ1: DQE可以检测到现实世界DBMS中的哪些逻辑错误？
     • RQ2: DQE检测到的错误中有多少是现有方法可以发现的？

A. Experimental Methodology

1. 实验设置：
   • DQE在五个广泛使用的数据库管理系统（DBMS）上进行评估：MySQL、MariaDB、TiDB、CockroachDB和SQLite。这些DBMS的详细信息在文中的第II-B节中介绍。
   • 实验使用的是这些DBMS的最新发布版本：MySQL 8.0.28、MariaDB 10.8.2、TiDB 5.2.0、CockroachDB 21.2.6和SQLite 3.39.2。对于TiDB，实验还包括在其5.3.0和5.4.0版本发布后的测试。
   • 实验在一台配有8个CPU核心和32GB RAM的CentOS机器上进行。每个DBMS根据其自身部署要求进行部署。
2. 实验过程：
   • DQE运行以在目标DBMS中找到错误。实验没有设置超时，直到DQE找到错误为止。整个实验持续了大约一个月。
   • 当DQE报告潜在错误时，通过目标DBMS的交互式终端手动执行以确认是否能复现这个错误。
   • 成功复现报告的错误后，手动将测试用例减少到更小的规模，包括移除未使用的列、可选的列约束、数据表中的数据，并随机移除部分谓词子句。
   • 在报告错误之前，检查目标DBMS的错误跟踪系统以避免提交重复的错误。报告错误后，等待开发者的反馈。
   • 手动精简，至于怎么去重的没细说
3. 实验重点：
   • 开发者的响应时间决定了在测试一个DBMS上花费的努力。TiDB的开发者提供了更快速的确认，这极大地增强了继续测试的信心。因此，实验主要集中在TiDB上，并保持其最新状态。

B. Overall Detection Results

1. 检测结果概况：

   • DQE报告了122个错误，经过手动复现和最小化测试用例，最终确认了50个独特的错误。

   • 怎么去重？精简后的结果是相同的，则说明是重复的bug。

     We manually reproduce and minimize the test cases of these 122 reported bugs. If the minimized test cases of some bugs are the same, we only keep one, and consider others as duplicate bugs.

   • 这些错误被提交给相应的DBMS开发者：MySQL（7个）、MariaDB（4个）、TiDB（37个）、CockroachDB（1个）和SQLite（1个）。

   • 其中，41个错误被确认为新的错误，11个已被修复。

   • 

2. 错误的状态和分类：

   • 在这41个确认的错误中，22个被评定为重大或中等严重级别。
   • 触发错误的查询类型包括SELECT（21个）、UPDATE（18个）和DELETE（20个）查询。一个错误可以由多个类型的查询触发，因此触发查询的总数超过已确认的错误总数。

3. 错误的后果：

   • 大多数SELECT查询导致了不正确的警告，例如重复警告、意外警告和错误的警告信息。
   • 所有UPDATE查询和大多数DELETE查询导致了不正确的数据库状态。
   • 其他错误包括意外的警告、不正确的警告信息和导致SHOW WARNINGS命令执行失败的错误。
   • 

4. 错误分布：

   • 大部分导致不正确数据库状态的错误发生在TiDB（34个）和MySQL（2个）。（逻辑错误，查询结果不符合）

   • 导致重复警告和意外警告的错误主要出现在TiDB和MariaDB。

     • 重复警告（Duplicate Warnings）：这类警告发生在系统对同一问题或条件生成多次警告的情况下。例如，如果数据库在处理单个查询时针对相同的问题重复生成警告，那么这些警告就被视为重复警告。这种情况可能是由于数据库内部逻辑的问题，导致它在处理特定情况时过度反应。
     • 意外警告（Unexpected Warnings）：意外警告是指在执行数据库操作时出现的不预期或不适当的警告消息。这种警告通常表明数据库以某种方式对操作作出了反应，但这种反应与操作的性质或上下文不相符。例如，如果一个简单且正确的查询操作触发了性能相关的警告，尽管查询本身并没有表现出任何性能问题，这样的警告就可以被认为是意外的。（比如向一个表中插入一行新数据。这个操作相对简单，不应该触发任何警告。）

   • 导致不正确警告信息和SHOW WARNINGS命令执行失败的错误仅出现在TiDB。

   • 发生在SQLite的一个错误导致了意外的错误。

C. Comparing with Existing Approaches

这段文字讨论了为回答研究问题RQ2所进行的与现有方法的比较。目的是评估DQE在检测数据库管理系统（DBMS）中逻辑错误方面的相对效果。

1. 与现有方法的比较：
   • 现有的方法（PQS、NoREC和TLP）主要构建预言机（oracles）来检测单个SELECT查询中的逻辑错误。
   • 这些方法无法检测在UPDATE和DELETE查询中的20个逻辑错误。
   • 它们也不考虑SELECT查询可能意外引发的正常错误（如警告）作为逻辑错误。
   • 因此，这些方法不能检测与这类错误相关的SELECT查询中的18个逻辑错误。
2. 现有方法的局限性：
   • 分析剩余的3个SELECT查询中的逻辑错误，发现这些错误也不能被现有方法的预言机捕获或触发。
   • 理论上，所有报告的错误都无法被这些方法检测到。
3. 与其他DBMS测试方法的比较：
   • 其他DBMS测试方法（如SQLsmith、APOLLO、AMOEBA、RAGS和SparkFuzz）无法构建预言机来检测逻辑错误，或者由于差异测试需要多个DBMS，所以无法在单个DBMS中检测逻辑错误。
   • 因此，DQE没有与这些方法进行比较。

D. Other Experimental Statistics

1. 测试效率：
   • DQE报告了122个错误，但经过过滤重复错误后，最终确认了50个独特的错误，重复率为41%。
   • 在发现这50个独特错误的过程中，DQE生成了约17.76亿个查询三元组。
2. 查询生成效率：
   • DQE在不同DBMS上的查询生成效率不同。例如，在MySQL中，每秒生成2,885个查询，成功率为88%；而在SQLite中，每秒生成12,313个查询，成功率为97%。
   • DQE生成的查询可能由于语义约束而在不同的DBMS中变得无效，例如插入重复值到唯一列中。
3. 代码覆盖率：
   • 与现有工作（PQS、NoREC和TLP）比较，DQE在MySQL和MariaDB中的代码覆盖率与这些工作相似，分别为15%和21%。
   • 这一覆盖率较低，是因为DQE主要关注于DBMS的查询处理，而不包括其他功能，如用户管理、配置和容错。
4. 参数选择：
   • 实验使用了一些默认参数（如maxTable=5、maxCol=10、maxDept=3）来生成数据库和查询。
   • 这些参数可能影响错误检测的有效性，但由于DBMS中的逻辑错误通常符合小范围假设，影响可能较低。例如，所有50个提交的错误都可以在单表上检测到，其中47个错误可以通过一行数据检测到。

E. Selected Bugs

Incorrect database state.

Duplicate warning.

Unexpected warning.

Unexpected error.

Incorrect warning message.

Others.

F. Not A Bug

这段文字描述了MySQL中的一个错误（编号MySQL#10640712），涉及在索引列r1上多次出现相同的警告或错误的情况。错误的具体情况如下：

1. 数据库和查询设置：
   • 数据库表t1包含一个FLOAT类型的行，其值为0，且在列c1上建立了索引。
   • 使用的谓词φ是('a' | 1) BETWEEN 0 AND c1。在SELECT查询中，MySQL将'a'转换为INT值0，然后执行与1的按位或操作，结果为1，最后检查这个结果是否在0和列c1的值之间的范围内。
   • 由于列c1的值为1，谓词φ被评估为TRUE，因此SELECT查询返回行r1，但同时引发了三个相同的警告。
2. 错误表现：
   • UPDATE和DELETE查询分别引发一个警告和一个错误（警告代码和消息相同）。
   • 由于只有一行数据，作者认为不应该出现重复的警告或错误。
3. 开发者的回应：
   • 当向MySQL开发者报告这个问题时，他们确认了这个问题的存在，但解释说“重复的警告，即使完全相同，也不构成一个错误”。

RELATED WORK

相关的工作主要集中在三个方面：DBMS的差异测试、数据库和SQL查询生成、以及DBMS的测试预言机。

1. DBMS的差异测试：
   • 差异测试是测试DBMS的有效方法，它通过将相同的输入提供给多个功能上相似的系统并比较它们的输出来检测错误。
   • 例如，RAGS在不同的DBMS上执行相同的SELECT查询并观察查询结果的差异；APOLLO在同一DBMS的不同版本上执行SELECT查询以检测性能错误；SparkFuzz通过参考DBMS（如PostgreSQL）或不同版本的Spark来验证查询结果。
   • 本文提出了一种新的差异测试方法，即在一个DBMS中执行带有相同谓词的SELECT、UPDATE和DELETE查询来检测逻辑错误。
2. 数据库和SQL查询生成：
   • 自动输入生成是自动测试的关键组成部分，数据库和SQL查询生成已被广泛研究。
   • 如SQLsmith是一个开源的随机SQL查询生成器；Go-randgen可以基于输入的SQL语法生成各种SQL查询；SQLRight是一个基于变异的SQL查询生成器。
3. DBMS的测试预言机：
   • 测试预言机是揭示DBMS错误的关键。
   • 例如，ADUSA使用Alloy语言和分析器来分析给定SELECT查询的预期查询结果；PQS合成一个SELECT查询来获取随机选择的支点行，并检查这行是否包含在其查询结果中；NoREC重写SELECT查询为DBMS无法优化的等效查询，并比较它们的结果。
   • 本文提出了一种新的测试预言机方法，对DBMS测试提供了补充。

CONCLUSION

在UPDATE和DELETE查询中的逻辑错误可能导致更严重的后果，例如不正确的数据库状态，并且现有方法尚未解决这些问题。在本文中，我们提出了一种新颖且通用的方法DQE，用于有效检测SELECT、UPDATE和DELETE查询中的逻辑错误。我们在五个广泛使用的数据库管理系统上评估了DQE，即MySQL、MariaDB、TiDB、CockroachDB和SQLite。总共，我们在这些DBMS中检测到了41个以前未知的逻辑错误。我们期望DQE的通用性能够帮助提高数据库管理系统的可靠性。