1 Introduction↩︎

Database management systems (DBMSs) constitute the backbone of modern computing infrastructure, enabling efficient storage, management, and retrieval of large-scale data [1]–[4]. Within a DBMS, the query optimizer is a critical component that determines the most efficient execution plan for a given query [5]–[9]. Join optimization, in particular, is central to query processing, as joins often dominate the cost of complex analytical workloads [10], [11]. Optimizing joins is notoriously challenging due to the factorial growth of the join search space and the uncertainty of cost estimation. Consequently, query optimizers employ sophisticated algorithms to determine optimal join orders [12], [13]. While effective, these techniques render DBMS query optimizers highly complex, making bugs inevitable.

Among these bugs, some are relatively easy to detect, while others are not. Specifically, crash bugs cause the system to terminate unexpectedly or become unavailable, often arising from unhandled exceptions, resource conflicts, or internal errors in storage or indexing modules; performance bugs do not compromise correctness but significantly degrade query efficiency, resulting in long execution times, high resource consumption, or reduced throughput. Both types of bugs are relatively easy to detect, as their effects are directly observable. In contrast, logic bugs produce incorrect query results (i.e., violating the intended semantics of the workload) but do not cause the system to fail. They are particularly difficult to detect, as their manifestations are subtle and may arise only under specific data distributions or complex query patterns [14], [15]. While state-of-the-art fuzzers (e.g., SQLsmith [16] and AFL [17]) efficiently uncover crash and performance defects, they generally lack the ability to detect logic bugs.

To address the challenge of detecting logic bugs, several approaches have been proposed. Differential testing, for example, identifies potential bugs by comparing the results of the same query across different DBMSs or versions of the same DBMS. While effective at detecting inconsistencies between implementations, its applicability is often limited to the common core of SQL functionalities [18], as different DBMSs vary in their support for the SQL standard and frequently provide proprietary extensions. Another approach is pivoted query synthesis (PQS) [19], which validates query results by constructing auxiliary queries centered on a specific pivot row. Although PQS can be effective in certain scenarios, it requires substantial engineering effort and is less capable of capturing set-level inconsistencies, such as duplicates or missing tuples.

Recently, metamorphic tests have been increasingly used for DBMS testing [20]–[23]. Representative frameworks include ternary logic partitioning (TLP) [20] and non-optimizing reference engine construction (NoREC) [22]. These approaches transform a query into semantically equivalent variants, either through predicate partitioning or by bypassing the optimizer’s execution path, to check for inconsistencies. Transformed query synthesis (TQS) [24] utilizes optimization hints to verify query results against a ground truth. Recently, differential query planning (DQP) [25] adopts a similar hint-based strategy but focuses on detecting inconsistencies between different physical plans for the same query. We aim to present a metamorphic testing scheme that efficiently and effectively detects logic bugs in DBMS join optimization. Our key insight is that an INNER/NATURAL JOIN) can be semantically expressed as a combination of multiple set intersection operations. Such a theoretical equivalence should be strictly upheld by any standards-compliant DBMS. However, we discovered that this is often not the case. A highly illustrative motivating example is shown in Listing [lst:motivating-example], which depicts a bug we discovered in TiDB [26]. We crafted a simple INNER JOIN query whose ON predicate, (-1.35703815E8 >= t0.c0), is provably FALSE. A fundamental principle of SQL dictates that such a query can produce no joined rows, and thus its final result set must be empty. In blatant contradiction to this principle, TiDB returns a non-empty result \(\{0\}\). As shown in Listing [lst:cross-plan], the root cause became evident upon inspecting the query’s execution plan. Astonishingly, the HashJoin operator was labeled as a CARTESIAN inner join, which signifies a cross product. This provides direct evidence that the query optimizer had completely discarded the essential ON predicate. By erroneously demoting the INNER JOIN to a CROSS JOIN, the optimizer exhibited not a subtle semantic misinterpretation but a catastrophic failure in its core logic.

CREATE TABLE t0(c0 BOOL UNSIGNED NOT NULL);
CREATE TABLE t1 LIKE t0;
INSERT INTO t0(c0) VALUES (true);
INSERT INTO t1(c0) VALUES (false);
-- (*@\colorbox{yellow!65}{\color{codegray}Original Query}@*)
SELECT DISTINCT t1.c0 FROM t1 INNER JOIN t0 ON -1.35703815E8>=t0.c0 WHERE t0.c0; 
-- Expected Result: empty set | Actual Result: {0}. (*@\bugicon@*)
-- (*@\colorbox{yellow!65}{\color{codegray}Equivalent Query}@*)
(SELECT DISTINCT t1.c0 FROM t1 LEFT JOIN t0 ON -1.35703815E8>=t0.c0 WHERE t0.c0)
 INTERSECT
(SELECT DISTINCT t1.c0 FROM t1 RIGHT JOIN t0 ON -1.35703815E8>=t0.c0 WHERE t0.c0); 
-- Expected Result: empty set | Actual Result: empty set.(*@\checkicon@*)

-> HashAgg ... group by: t1.c0 ... (rows=1)
    -> (*@\colorbox{red!30}{{\color{codered}\bfseries HashJoin} ... {\color{codered}\bfseries CARTESIAN inner join} ... ({\color{codered}\bfseries rows}=1)}@*)

The above example reveals that such optimizer-level logic bugs often stem from incorrect handling of algebraic equivalences during query rewriting. Although existing studies have achieved significant results in logic bug detection, our systematic investigation reveals that these methods still exhibit notable deficiencies in supporting equivalent transformations at the relational algebra level. Table 1 compares the feature coverage of typical testing approaches with respect to SQL set operations, including EXCEPT, INTERSECT, UNION, and their ALL variants. As shown in Table 1, PQS, NoREC, DQP, and TQS do not support EXCEPT, INTERSECT, or UNION operations, while TLP supports only UNION (including ALL). These results reveal that existing approaches focus primarily on predicate partitioning or optimizer path validation, resulting in limited testing capability.

To address this issue, we perform an in-depth exploration of set-theoretic equivalences in join queries for test case generation. Leveraging the property that an INNER JOIN (or NATURAL JOIN) is semantically equivalent to a combination of set intersection operations, we design three transformation rules (§3.2, §3.3, and §3.4). These rules enable the construction of semantically equivalent query pairs, whose result sets can be compared to uncover deep logical inconsistencies in query rewriting or execution semantics. Based on this equivalence-driven query generation method, we develop a metamorphic testing framework, JoinEquiv, implemented on top of SQLancer [27] and made publicly available.¹ Compared with existing approaches (see Table 1), JoinEquiv achieves full support for all three set operations and their ALL variants.

To evaluate the effectiveness of our JoinEquiv framework, we conduct extensive tests on four production-grade DBMSs: MySQL, TiDB, DuckDB, and Percona. JoinEquiv reported 29 previously unknown logical inconsistencies. Among these, 27 have already been confirmed by developers, 14 of which involve critical bugs in query optimizer rewrite logic or executor semantic handling. Cross-oracular validation shows that the vast majority of the remaining bugs can only be detected by our intersection-equivalence transformations; i.e., they cannot be detected by existing metamorphic testing approaches such as TLP and DQP, thus highlighting the unique and complementary value of JoinEquiv. We believe that the principled methodology, low implementation effort, and broad applicability of JoinEquiv will lead to its widespread adoption to improve the robustness of DBMSs.

In summary, our main contributions in this paper include:

• We propose a new metamorphic testing paradigm that bridges relational algebra and set theory, mapping INNER JOIN to set-theoretic intersection to build principled logic-level oracles.

• We design a structurally complete set of minimal transformation rules (SJT, ADT, and SDT) that collectively encompass all core SQL set operators. They serve as normal forms for intersection semantics, supported by formal proofs that establish their equivalence and identify their specific validity boundaries across sets and multisets.

• We implement and evaluate JoinEquiv on widely used DBMSs to uncover many previously unknown logic bugs.

2 Background↩︎

2.1 Set and Multiset Semantics in SQL↩︎

Although SQL is rooted in the relational model [28], there is a key semantic divergence between SQL implementations and Codd’s original pure set-based theory: modern DBMSs commonly adopt the bag (or multiset) model, which allows for identical tuples in a data table. To cope with such dual semantics, SQL’s set operators, such as UNION, INTERSECT, and EXCEPT, have evolved two variants: the default DISTINCT mode for working with sets (de-duplication), and the ALL mode for working with bags (preserving duplicates). This semantic complexity extends to join operations. Both INNER JOIN and NATURAL JOIN, in essence, can be viewed as generalized intersection operations since their core goal is to find combinations of tuples that satisfy specific conditions in two relationships.

2.2 Query Optimization and Rewrite Logic↩︎

The query optimizer is a critical component that translates declarative SQL into efficient physical execution plans [29], [30]. This typically involves navigating a combinatorial search space of join orders, physical operators, and access paths [31]. To manage such complexity, optimizers rely heavily on heuristic rewrite rules (e.g., predicate pushdown and join reordering) and on cardinality estimation [32]. However, ensuring the correctness of these equivalent transformations is notoriously difficult. The interplay between complex rewrite logic and diverse SQL features makes the optimizer a frequent source of logic bugs, in which a flawed transformation causes the DBMS to violate query semantics and produce incorrect results.

2.3 Metamorphic Testing↩︎

Metamorphic testing is an effective methodology in software testing [33], [33]–[35] designed to overcome the oracle problem, where the ground truth is difficult to determine. Its core idea is that even if the correct output (i.e., the “ground truth”) of a single execution is unknown, we can use metamorphic relations between multiple inputs to verify whether their corresponding outputs satisfy the expected invariance. If this expected relation is violated, it indicates a flaw in the system [33]. In the context of DBMS testing, this idea is materialized in the construction of semantically equivalent query pairs. The approach rewrites an original query \(Q\) into a logically equivalent query \(Q'\), which may exhibit a different syntactic structure and execution path. In this way, the assertion \(\text{Result}(Q) \equiv \text{Result}(Q')\) itself constitutes an endogenous (self-contained) test adjudicator that requires no external reference. Unlike differential testing, meta-transformation testing circumvents the challenge of SQL dialect differences by shifting the focus of verification from inter-system consistency to intra-system logical consistency.

3 Methodology↩︎

In this section, we present our logical bug detection method, JoinEquiv, based on set-theoretic principles. Our key insight is that the intersection operation of a set can be expressed in a number of different algebraic equations. We apply this insight to DBMSs and find that the behavior of INNER JOIN and NATURAL JOIN operations is highly isomorphic to set intersections in the specific but common scenario where the join columns contain no NULL values.

This finding provides a solid theoretical foundation on which we can build our test determiners. Specifically, we take a simple original query \(Q_{\text{orig}}\) and use set constants to construct a transformed query \(Q_{\text{meta}}\). These two queries are theoretically equivalent in an ideal NOT NULL-constrained environment. Therefore, any inconsistency between their results clearly indicates a logical bug in the DBMS, rather than semantic ambiguity arising from NULL handling.

3.1 Framework Overview↩︎

As illustrated in Fig. 1, JoinEquiv consists of six main steps.

Step generates a database state by creating two tables (t0, t1) and populating them with random data, e.g., inserting \(\{(1,1), (2,2), (3,3)\}\) into t0 and \(\{(1), (3), (4)\}\) into t1.

Step creates an original query \(Q_{\text{orig}}\), “SELECT t0.c0 FROM t0 INNER JOIN t1 ON t0.c0=t1.c0.” Since INNER JOIN is a fundamental and well-optimized operator, we expect the DBMS to choose an efficient execution plan using its native query optimizer. Steps and execute \(Q_{\text{orig}}\) on the DBMS and fetch its result set. In our example, assuming the DBMS behaves correctly, the result of \(Q_{\text{orig}}\) should be \(\text{rs}_{\text{orig}} = \{1, 3\}\), representing the two matching tuples.

Step translates \(Q_{\text{orig}}\) into a transformed query \(Q_{\text{meta}}\). For instance, by applying the symmetric join transformation rule (see Section 3.2), we can rewrite \(Q_{\text{meta}}\) as (SELECT t0.c0 FROM t0 LEFT JOIN t1 ON t0.c0=t1.c0) INTERSECT (SELECT t0.c0 FROM t0 RIGHT JOIN t1 ON t0.c0=t1.c0). Although \(Q_{\text{meta}}\) is semantically equivalent to \(Q_{\text{orig}}\), its more complex structure (involving two outer joins and a set intersection) effectively disables the optimizer’s standard join optimization strategies for a simple inner join. Consequently, the DBMS is forced to adopt an entirely different and typically more complex execution path, such as first computing the intermediate results of both outer joins and then performing the INTERSECT operation on them. Steps and similarly execute \(Q_{\text{meta}}\) on the DBMS and fetch its result set. In a correctly implemented DBMS, the final result should still be \(\text{rs}_{\text{meta}} = \{1, 3\}\). However, due to an incorrect optimization or an executor defect, some tuples may be erroneously omitted. In this example, the buggy result \(\text{rs}_{\text{bug}} = \{1\}\) misses one tuple.

Finally, Step compares their result sets (\(\text{rs}_{\text{orig}}\) vs. \(\text{rs}_{\text{meta}}\) or \(\text{rs}_{\text{bug}}\)). For a correct execution, \(\text{rs}_{\text{orig}} = \{1, 3\}\) and \(\text{rs}_{\text{meta}} = \{1, 3\}\) are identical and the test passes. In the bug case, \(\text{rs}_{\text{bug}} = \{1\}\) indicates that JoinEquiv has successfully detected a logical bug in the query optimizer or executor.

Fundamentally, the effectiveness of our transformation strategy lies in forcing the DBMS to evaluate two fundamentally different execution paths. While the original INNER JOIN is typically executed via a single highly efficient physical operator (e.g., hash join), our proposed rules construct complex, nested structures involving outer joins and set operations. This structural complexity often inhibits the optimizer’s standard simplification strategies, compelling the DBMS to fully materialize intermediate results and perform combinatorial aggregations. Any semantic inconsistency that arises between these two logically equivalent but distinct execution paths will manifest as a discrepancy in the outputs.

Next, we describe the three transformation rules in detail.

3.2 Symmetric Join Transformation↩︎

The symmetric join transformation (SJT) rule is grounded in a fundamental principle of relational algebra: An INNER JOIN or NATURAL JOIN is logically equivalent to the intersection of its corresponding left and right outer joins under the NOT NULL constraint. Formally, this rule is derived from the set-theoretic identity \(A \cap B\), which represents the minimal canonical form required to reconstruct intersection semantics using asymmetric outer joins.

To ensure the correctness of transformations, SJT must accurately handle the two core semantics of sets and multisets inherent in SQL. Using a simple dataset, Figs. 2 (a) and 2 (b) demonstrate the difference between set and multiset semantics:

• Set Semantics: Elements are treated as distinct entities, and duplicate values are automatically removed. For instance, with \(A = \{1,2,3,4\}\) and \(B = \{1,3,4,5\}\), the intersection operation yields \(A \cap B = \{1,3,4\}\).

• Multiset Semantics: Element multiplicities are preserved during set operations. Specifically, the multiplicity of an element in the result is determined by the minimum of its multiplicities in the two input multisets. For instance, with \(A = \{1,2,2,3\}\) and \(B = \{1,2,2,5\}\), the multiset intersection becomes \(A \cap B = \{1,2,2\}\), where the duplicate occurrences of \(2\) are retained.

Algorithm 3 describes the SJT rule. It takes as input the abstract syntax tree (AST) of a query and produces a new AST that is structurally different yet semantically equivalent, from which a logically equivalent query can be generated. First, it verifies whether the input AST contains an INNER JOIN or NATURAL JOIN. If no such operator exists, the transformation is deemed inapplicable (lines 2–3). Next, using the original AST as a template, the algorithm constructs two new AST subtrees: one where the join operator is replaced with a LEFT JOIN (denoted as \(\text{AST}_L\)) and another replaced by a RIGHT JOIN (denoted as \(\text{AST}_R\)) (lines 5–6). To preserve duplicate semantics, it inspects whether the query contains the DISTINCT modifier (line 7). If DISTINCT exists (i.e., using set semantics), duplicate tuples are removed and the transformed query employs the INTERSECT operator. Otherwise (i.e., using multiset semantics), duplicates are preserved and INTERSECT ALL is used to maintain tuple multiplicities. Finally, the algorithm creates a new INTERSECT node as the parent, attaching \(\text{AST}_L\) and \(\text{AST}_R\) as its left and right children, respectively, thus constructing the transformed \(\text{AST}_{\text{out}}\) as output (line 11).

3.3 Asymmetric Difference Transformation↩︎

The asymmetric difference transformation (ADT) rule constructs equivalent queries by leveraging the asymmetric set-difference identity \(A \cap B \equiv A \setminus (A \setminus B)\), implemented via EXCEPT (or EXCEPT ALL). This represents the minimal canonical form to construct an intersection relying solely on the set-difference operator, grounded in the double complement law. Compared to the SJT rule, ADT generates a nested query structure that poses unique challenges to the DBMS optimizer in handling and simplifying complex EXCEPT clauses. To ensure transformation correctness, ADT must be validated under set and multiset semantics. On a simple dataset, Figs. 2 (c) and 2 (d) illustrate how ADT behaves under the two semantics:

• Set Semantics: Let \(A = \{1,2,3,4\}\) and \(B = \{1,3,4,5\}\). The inner difference, \(A \setminus B\), yields \(\{2\}\), and applying the outer expression, \(A \setminus (A \setminus B)\), restores the elements common to both sets, resulting in \(\{1,3,4\}\), which exactly equals the standard intersection \(A \cap B\).

• Multiset Semantics: Let \(A = \{1,2,2,3\}\) and \(B = \{1,2,2,5\}\). Under the multiset (bag) semantics, the first difference, \(A \setminus B\), produces \(\{3\}\), and the subsequent expression, \(A \setminus (A \setminus B)\), yields \(\{1,2,2\}\), which is consistent with the multiset intersection result.

Algorithm 4 describes the ADT rule. Its initialization (lines 1–6) mirrors that of the SJT rule. The subsequent steps diverge: It examines whether the original query contains a DISTINCT modifier, selecting either an EXCEPT (for set semantics) or EXCEPT ALL (for multiset semantics) operator node (excOp) to strictly preserve semantic equivalence (lines 7-10). The core of the ADT transformation lies in a two-stage tree construction. First, excOp combines \(\text{AST}_L\) and \(\text{AST}_R\) to construct a subtree representing the inner difference expression \(A \setminus B\) (\(\text{AST}_\text{inner\_except}\), line 11). Then, EXCEPT is applied again with \(\text{AST}_L\) as the left child and \(\text{AST}_\text{inner\_except}\) as the right child, resulting in the final AST \(\text{AST}_\text{out}\) representing the complete expression \(A \setminus (A \setminus B)\) (line 12).

3.4 Symmetric Difference Transformation↩︎

The symmetric difference transformation (SDT) rule constructs equivalent queries based on the symmetric set-difference identity \(A \cap B \equiv (A \cup B) \setminus ((A \setminus B) \cup (B \setminus A))\). This constitutes the minimal canonical form to derive the intersection via the UNION operator, grounded in the inclusion-exclusion principle. Compared to SJT and ADT, SDT produces a more complex set operation structure, challenging the DBMS optimizer with multiple intermediate computations. To verify transformation correctness, SDT is examined under both set and multiset semantics. Using a simple dataset, Fig. 2 (e) illustrates the behavior of SDT under set semantics:

• Set Semantics: Let \(A = \{1,2,3,4\}\) and \(B = \{1,3,4,5\}\). The symmetric difference \((A \setminus B) \cup (B \setminus A)\) equals \(\{2,5\}\), and subtracting this from the full union \(A \cup B = \{1,2,3,4,5\}\) yields \(\{1,3,4\}\), which is exactly \(A \cap B\). This example demonstrates that SDT correctly preserves intersection semantics through symmetric-difference operations under set semantics.

• Multiset Semantics: Under multiset semantics, however, the same procedure fails to maintain equivalence. We formally prove such a non-equivalence in Section 4.

Algorithm 5 details the SDT transformation. Its initialization (lines 1–6) mirrors that of SJT and ADT. Note that, since SDT does not hold for multisets, we consider only its implementation under set semantics. Then, set operation nodes are created to implement the symmetric difference transformation. Specifically, two EXCEPT nodes compute the differences \(A \setminus B\) and \(B \setminus A\) from the left and right join ASTs (lines 10–11). These different nodes are then combined under a UNION node to form the symmetric difference \((A \setminus B) \cup (B \setminus A)\) (lines 12–13). Finally, another EXCEPT node subtracts this symmetric difference from the full union of the left and right join ASTs (line 14), producing the transformed AST that preserves the intersection semantics.

3.5 Database and Query Generation↩︎

Generating high-quality databases and queries for testing has been extensively studied and is not the primary concern of this work. JoinEquiv is compatible with any database and query generator capable of producing valid SQL queries containing INNER/NATURAL JOIN operators. Here, we provide details of our implementation for reproducibility. The test case generation builds upon the SQLancer framework, which provides a grammar-aware SQL query generation engine. We extend SQLancer to satisfy an additional precondition that all columns are NOT NULL. Specifically, Step  of Fig. 1 randomly generates tables and rows using CREATE TABLE and INSERT statements under NOT NULL constraints. Step  then constructs the original queries, where JoinEquiv randomly selects a subset of tables from the generated schema to participate in the join. The order of table references is also randomized. Across test iterations, the roles of participating tables (e.g., t0 and t1) are permuted by a randomized generation engine. Although the transformation templates use a fixed LEFT/RIGHT JOIN structure, symmetric variants are implicitly instantiated through this randomized table binding. For instance, expressions such as t1 LEFT JOIN t0 naturally arise, which are algebraically equivalent to t0 RIGHT JOIN t1. As a result, symmetric forms of SJT, ADT, and SDT are repeatedly exercised over long-running testing without explicitly enumerating all symmetric variants. Such a table permutation, combined with SQLancer’s randomized population of ON predicates, WHERE clauses, and SELECT list expressions, ensures that the framework explores a diverse range of symmetric and asymmetric execution plans.

4 Theoretical Analysis of Transformation Equivalence↩︎

The correctness of our fuzzing methodology relies on the semantic equivalence of the query transformations we employ. This section provides a theoretical analysis of the equivalence of the three transformation rules: SJT, ADT, and SDT. We rigorously examine their validity under both set semantics (corresponding to SELECT DISTINCT) and multiset semantics (corresponding to standard SELECT).

4.1 Preliminaries↩︎

To ensure the clarity of our proofs, we operate under the assumption that all columns in the involved tables are defined as NOT NULL. This allows us to map SQL operations directly to the classical set and multiset theory without the complexities of three-valued logic. Let \(R\) and \(S\) be two relations (tables). We establish the following mappings from SQL operators to their mathematical counterparts:

This model applies to queries using SELECT DISTINCT or standard set operators (UNION, EXCEPT, INTERSECT), which implicitly perform duplicate elimination.

• R INNER JOIN S maps to the theta-join \(R \bowtie_\theta S\), where \(\theta\) is the join condition.

• R LEFT JOIN S ON\(\theta\) maps to the left outer theta-join, denoted \(R \bowtie_\theta^l S\) := \((R \bowtie_\theta S) \cup R_{\text{unmatched}}\).

• R RIGHT JOIN S ON\(\theta\) maps to the right outer theta-join, denoted \(R \bowtie_\theta^r S\) := \((R \bowtie_\theta S) \cup S_{\text{unmatched}}\).

• UNION, EXCEPT, and INTERSECT (without ALL) map to standard set operators \(\cup\), \(\setminus\), and \(\cap\). Their ALL variants correspond to multiset operations that preserve duplicates.

Let \(A\) and \(B\) be two multisets, and let \(t\) be a tuple. The count of \(t\) in a multiset \(M\) is denoted by \(\mathrm{count}(t, M)\). The multiset semantics for the SQL ALL set operators are defined as follows: \[\begin{align} \mathrm{count}(t, A \cap B) &= \min(\mathrm{count}(t, A), \mathrm{count}(t, B)), \\ \mathrm{count}(t, A \cup B) &= \mathrm{count}(t, A) + \mathrm{count}(t, B), \\ \mathrm{count}(t, A \setminus B) &= \max(0, \mathrm{count}(t, A) - \mathrm{count}(t, B)), \end{align}\] where the operations on the left correspond to INTERSECT ALL, UNION ALL, and EXCEPT ALL, respectively.

4.2 Proofs of Equivalence under Set Semantics↩︎

Under set semantics, all three transformation rules are provably equivalent to an INNER JOIN. The equivalence trivially extends to NATURAL JOIN, as it can be regarded as an INNER JOIN with a specific predicate defined on all common attributes.

4.3 Proofs of Equivalence under Multiset Semantics↩︎

Under multiset semantics, the validity of the transformation rules diverges.

Remark: Finally, we discuss in which cases SDT is valid under multiset semantics. The most direct sufficient condition for SDT’s validity is when the input multisets are duplicate-free, effectively degenerating to set semantics (i.e., for all tuples \(t\), \(\mathrm{count}(t,\cdot)\in\{0,1\}\)). In this case, our proofs based on set algebra apply directly. An equivalent statement is that SDT can be safely applied if the input relations have been explicitly de-duplicated (e.g., via a DISTINCT modifier) or if the context guarantees that the relations are unique on the projection of their join key columns.

5 Experimental Evaluation↩︎

In this section, we evaluate JoinEquiv in terms of its ability to discover new vulnerabilities, as well as its efficiency in exploring the state space of the target DBMSs. Our evaluation aims at answering the following research questions:

• RQ1: Can JoinEquiv find real logic bugs in widely used and extensively tested DBMSs?

• RQ2: How diverse are the logic bugs found?

• RQ3: Can JoinEquiv find logic bugs that are missed by existing approaches?

Note: For DuckDB, component and severity were not provided, so they are marked as “–”. Verified

denotes that the bugs have been officially confirmed and accepted by the developers as valid logic defects.

5.1 Evaluation Setup↩︎

We tested seven widely used and representative RDBMSs using JoinEquiv, namely MySQL, TiDB, Percona, PostgreSQL, CockroachDB, and SQLite. These systems are selected as they collectively represent widely deployed single-node RDBMSs, MySQL-compatible variants, distributed SQL systems, and lightweight embedded databases.

All experiments were conducted on a server running 64-bit Ubuntu 20.04.6 LTS. The machine is equipped with two Intel^® Xeon^® Gold 5218R CPUs (@ 2.10 GHz), each providing 20 physical cores (40 threads per socket), for a total of 80 hardware threads.

To ensure the robustness of results and mitigate the impact of randomness, we adopted a multi-instance parallel testing strategy. For each DBMS, we leverage the testing framework’s multi-threading capability by launching multiple concurrent testing threads. Each thread operates with an independent random state and query generation trajectory. Within each thread, for every INNER JOIN query, JoinEquiv, TLP, and DQP are applied sequentially under the same system configurations and runtime environments. The testing process ran continuously for 12 hours, effectively simulating repeated experiments across diverse random seeds.

5.2 Overall Results for Logic Bug Detection↩︎

We test all the target DBMSs with JoinEquiv. The testing process adheres to a conventional software defect detection pipeline, including fuzzing-based test generation, test case reduction, manual deduplication, cross-DBMS verification, and issue reporting to developers. As a result, 27 previously unknown logic inconsistencies were detected on MySQL, TiDB, Percona, and DuckDB (see Table 2). Interestingly, we did not uncover many bugs in PostgreSQL, CockroachDB, or SQLite. The underlying reasons for this “bug-free” behavior are analyzed in §6.

Among the reported bugs, Table 2 summarizes the results of applying JoinEquiv to different DBMSs. 14 bugs have been verified as critical, and 10 additional bugs in TiDB are still pending official severity classification. Additionally, there are two further test cases identified as intended behavior. Note that different DBMSs adopt different severity levels; for consistency, we use the term critical to unify the meanings of critical and serious in MySQL, critical and major in TiDB, and critical and urgent in Percona. These results demonstrate that JoinEquiv can effectively discover real logic bugs in widely used and extensively tested DBMSs (answering RQ1).

5.3 Diversity of Detected Logic Bugs↩︎

As shown in Fig. 6, the logic bugs detected by JoinEquiv exhibit remarkable diversity across both transformation rules and join types. Specifically, the three transformation rules demonstrate complementary detection capabilities across different DBMSs, collectively uncovering 27 distinct logic bugs in INNER/NATURAL JOIN operations. For example, Listing [lst:MySQL_bug_example] illustrates a bug exposed by SJT, which reveals an inconsistency in NULL semantics handling; Listing [lst:Percona_bug_example] presents a bug triggered by ADT, exposing a logical vulnerability in predicate rewriting within the optimizer; and Listing [lst:TiDB_bug_example] shows an executor-level defect in TiDB discovered by SDT, leading to data representation inconsistencies. Furthermore, the diverse bug distribution across MySQL, TiDB, Percona, and DuckDB indicates that JoinEquiv is independent of system-specific implementation details, as each DBMS exhibits distinct failure modes under different transformation rules. Together, these findings demonstrate that JoinEquiv can uncover a broad, heterogeneous spectrum of logic bugs originating from multiple layers of the system, including the optimizer, executor, and set-operator implementations, thereby effectively answering RQ2.

5.4 Case Analysis for Detected Logic Bugs↩︎

As shown in Listing [lst:MySQL_bug_example], to investigate the root cause of the bug, we manually analyzed the execution process of the transformed query. We first executed its two sub-queries independently to verify their correctness. “SELECT DISTINCT t0.c0 FROM t1 NATURAL LEFT JOIN t0” returned NULL, correctly filling unmatched t1 rows with NULL, while “SELECT DISTINCT t0.c0 FROM t1 NATURAL RIGHT JOIN t0” returned 0, correctly preserving the t0 row.

CREATE TABLE t0(c0 BIGINT NOT NULL, c1 DECIMAL NOT NULL);
CREATE TABLE t1(c0 FLOAT NOT NULL);
INSERT INTO t0(c0, c1) VALUES(0, -1);
INSERT INTO t1(c0) VALUES(0.3);
(*@\colorbox{yellow!65}{\color{codegray}Original query}@*)
SELECT DISTINCT t0.c0 FROM t1 NATURAL JOIN t0;
-- empty set (*@\checkicon@*)
(*@\colorbox{yellow!65}{\color{codegray}Transformed query (SJT rule)}@*)
(SELECT DISTINCT t0.c0 FROM t1 NATURAL LEFT JOIN t0)
 INTERSECT
(SELECT DISTINCT t0.c0 FROM t1 NATURAL RIGHT JOIN t0); 
-- {0} (*@\bugicon@*)

Since both sub-queries return correct results, the error must originate from the final INTERSECT operator. To confirm this, we analyzed the query plan generated by MySQL for \(Q_{\text{meta}}\), as shown in Listing [lst:intersect-plan]. The execution plan shows that the INTERSECT operator receives two single-row inputs (NULL and 0). However, it produces one row (rows=1), which contradicts the standard semantics of INTERSECT. According to the SQL standard, INTERSECT should not treat NULL as equal to any non-NULL value during set matching. Therefore, the correct result of {NULL} INTERSECT {0} should be an empty set. However, MySQL’s executor incorrectly treats NULL as equivalent to 0 during the implementation of the INTERSECT operator, leading to an incorrect result.

-> Table scan on <intersect temporary> (*@\colorbox{red!30}{{(\color{codered}\bfseries rows}=1)}@*)
    -> Intersect materialize with deduplication
        -> (*@{\color{codered}\bfseries Left hash join}@*) (t1.c0 = t0.c0) (rows=1)
            -> ...
        -> (*@{\color{codered}\bfseries Left hash join}@*) (t0.c0 = t1.c0) (rows=1)
            -> ...

This case reveals a logical bug in MySQL’s implementation of set operators: the INTERSECT operator fails to correctly handle the special semantics of NULL under SQL’s three-valued logic. While each individual outer join behaves correctly, the combined set operation introduces a semantic violation, exposing an inconsistency in MySQL’s treatment of NULL during set-based evaluation.

ADT rule successfully revealed a subtle logical bug deep within the query optimizer. In Listing [lst:Percona_bug_example], the original query contained a join predicate t0.c0 < -0.1, which is always false; thus, the theoretically correct result should be an empty set. However, Percona Server incorrectly returned a non-empty result \(\{0, 1\}\). Through an in-depth analysis of the execution plan for the original query, we identified the root cause: The optimizer performed an unsound predicate rewrite. In Listing [lst:except-plan], it erroneously relaxes the filter condition t0.c0 < -0.1 to t0.c0 <= 0. This flawed optimization directly led to the non-empty result.

In contrast, the semantically equivalent complex query generated by the ADT rule successfully inhibited the defective optimization, forcing the DBMS to follow a more conservative and correct execution path and correctly returned an empty set.

CREATE TABLE t0(c0 DECIMAL PRIMARY KEY);
CREATE TABLE t1 LIKE t0;
INSERT INTO t0(c0) VALUES(0.28981613730687783);
INSERT INTO t1(c0) VALUES(0.9690807743979165);
(*@\colorbox{yellow!65}{\color{codegray}Original query}@*)
SELECT t0.c0, t1.c0 FROM t0 INNER JOIN t1 ON t0.c0<-0.1; 
-- {0|1} (*@\bugicon@*)
(*@\colorbox{yellow!65}{\color{codegray}Transformed query(ADT rule)}@*)
(SELECT t0.c0, t1.c0 FROM t0 LEFT JOIN t1 ON t0.c0<-0.1)
 EXCEPT ALL(
    (SELECT t0.c0, t1.c0 FROM t0 LEFT JOIN t1 ON t0.c0<-0.1)
     EXCEPT ALL
    (SELECT t0.c0, t1.c0 FROM t0 RIGHT JOIN t1 ON t0.c0<-0.1));
-- empty set (*@\checkicon@*)

Inner hash join (no condition)  (rows=1)
    -> Covering index scan on t1 using PRIMARY
    -> Hash
        -> Filter:(*@\colorbox{red!30}{(t0.c0 <= 0)}@*)(rows=1)
            -> ..

As shown in Listing [lst:TiDB_bug_example], the SDT rule revealed a severe defect of data representation inconsistency hidden in the TiDB query executor. In this test case, the join predicate² \(\phi\) is a randomly generated but logically tautological expression (always evaluating to TRUE). Therefore, the theoretically correct result of all three semantically equivalent queries should be {’7’ \(|\) ’-’}. However, TiDB returned three mutually inconsistent results for the three equivalent queries: \(Q_{\text{orig}}\) returned {0x37 \(|\) ’-’}, incorrectly printing the character 7 as its hexadecimal byte value; \(Q_{\text{orig}}\) transformed by the SJT rule returned {’7’ \(|\) ’-’}, which happens to be the correct result; \(Q_{\text{orig}}\) transformed by the SDT rule returned {0x37000000 \(|\) ’-’}, showing a typical case of data corruption, where the single-byte representation of ’7’ was erroneously padded with zero bytes.

This phenomenon clearly exposes a severe implementation inconsistency within TiDB when handling CHAR-typed data across different execution paths. By further decomposing the SDT-transformed query, we localized the corruption to the first UNION operation, suggesting that the defect was triggered during the merging of two intermediate result sets from outer joins. This indicates a deep-seated bug in TiDB’s type metadata propagation or memory layout management mechanisms.

5.5 Comparison to Existing DBMS Testing Approaches↩︎

In order to evaluate JoinEquiv’s unique ability to detect logical bugs related to INNER JOIN, we compare it with two representative metamorphic testing approaches: Ternary Logic Partitioning (TLP) and Differential Query Plans (DQP). TLP shares a conceptual foundation with JoinEquiv, as both leverage set-theoretic principles to construct semantically equivalent query variants, whereas DQP evaluates the robustness of query optimizers by executing the same query under different physical plans, a strategy that has proven highly effective in uncovering join-related logical bugs.

CREATE TABLE t0(c0 CHAR NOT NULL);
CREATE TABLE t1 LIKE t0;
INSERT INTO t0(c0) VALUES ('-');
INSERT INTO t1(c0) VALUES ('7');
(*@\colorbox{yellow!65}{\color{codegray}Original query}@*)
(SELECT DISTINCT t1.c0, t0.c0 FROM t1 INNER JOIN t0 ON (*@$\phi$@*));
-- {0x37|'-'} (*@\bugicon@*)
(*@\colorbox{yellow!65}{\color{codegray}Transformed query(ADT rule)}@*)
(SELECT DISTINCT t1.c0, t0.c0 FROM t1 LEFT JOIN t0 ON (*@$\phi$@*)) 
 INTERSECT 
(SELECT DISTINCT t1.c0, t0.c0 FROM t1 RIGHT JOIN t0 ON (*@$\phi$@*));
-- {'7'|'-'} (*@\checkicon@*)
(*@\colorbox{yellow!65}{\color{codegray}Transformed query(SDT rule)}@*)
((SELECT DISTINCT t1.c0 FROM t1 LEFT JOIN t0 ON (*@$\phi$@*))
  UNION
 (SELECT DISTINCT t1.c0 FROM t1 RIGHT JOIN t0 ON (*@$\phi$@*))) 
  EXCEPT(
  ((SELECT DISTINCT t1.c0 FROM t1 LEFT JOIN t0 ON (*@$\phi$@*))
    EXCEPT
   (SELECT DISTINCT t1.c0 FROM t1 RIGHT JOIN t0 ON (*@$\phi$@*)))
    UNION
  ((SELECT DISTINCT t1.c0 FROM t1 RIGHT JOIN t0 ON (*@$\phi$@*))
    EXCEPT
   (SELECT DISTINCT t1.c0 FROM t1 LEFT JOIN t0 ON (*@$\phi$@*))));
-- {0x37000000|'-'} (*@\bugicon@*)

To ensure a fair and systematic comparison, we conduct two complementary experiments. First, we perform a cross-oracular validation based on previously confirmed bugs detected by JoinEquiv. For each reported bug, we reconstruct equivalent test cases following TLP and DQP formulations to examine whether these approaches can reproduce the same erroneous behavior. This validation allows us to assess the orthogonality and uniqueness of JoinEquiv’s detection scope. Second, we carry out a unified cross-oracular evaluation, in which all approaches are executed side by side for 12 hours under identical query generation and database states, to quantitatively compare their bug-finding capabilities. Crucially, for every generated original INNER JOIN query that can be correctly executed, we apply all three transformation strategies (TLP, DQP, and JoinEquiv) within the same iteration, ensuring a fair comparison under an identical execution context.

To evaluate the effectiveness of JoinEquiv, we implemented two representative metamorphic testing approaches as baselines. Ternary Logic Partitioning (TLP) (specifically, the TLP-Where variant) [20] relies on the set-theoretic principle of UNION. As illustrated in Listing [lst:tlp-example], TLP partitions an original query into three sub-queries by injecting predicates into the WHERE clause based on SQL’s ternary logic (TRUE, FALSE, NULL) and validates that their combined result matches the original. Differential Query Plans (DQP) [25], in contrast, targets join optimizer robustness. It forces the DBMS to generate diverse physical plans for the same query (via hints, see Listing [lst:tlp-example]) and checks for discrepancies (\(R_i \neq R_j\)) among the result sets.

To assess the orthogonality of JoinEquiv’s detection scope, we first perform a cross-oracular validation on previously reported bugs. For each bug exposed by JoinEquiv, we manually rewrite the corresponding query into its TLP- and DQP-equivalent forms and execute them on the same database.

[
  style=sqlstyle,language=SQL,
  caption={Example of ternary logic partitioning (TLP)} and differential query plans (DQP).,
  label={lst:tlp-example}]

(*@\colorbox{yellow!65}{\color{codegray}Original query}@*)
SELECT * FROM t0 INNER JOIN t1 ON t0.c0 = t1.c0;
(*@\colorbox{yellow!65}{\color{codegray}TLP (Where) transformed query}@*)
SELECT * FROM t0 INNER JOIN t1 ON t0.c0 = t1.c0 WHERE TRUE
UNION ALL
SELECT * FROM t0 INNER JOIN t1 ON t0.c0 = t1.c0 WHERE FALSE 
UNION ALL
SELECT * FROM t0 INNER JOIN t1 ON t0.c0 = t1.c0 WHERE TRUE IS NULL;
(*@\colorbox{yellow!65}{\color{codegray}DQP transformed query}@*)
(*@\color{codegray}{Plan variant 1 (hash join) hint}@*)
SELECT /*+ HASH_JOIN(t0, t1) */ * FROM t0 INNER JOIN t1 ON t0.c0 = t1.c0;
(*@{\color{codegray}{Plan variant 2 (nested-loop join) hint}@*)
SELECT /*+ NESTED_LOOP_JOIN(t0, t1) */ * FROM t0 INNER JOIN t1 ON t0.c0 = t1.c0;
}

Formally, given an INNER JOIN query \(Q_{\text{orig}}\) whose result differs from one or more of its algebraically equivalent transformed queries, we attempt to construct three predicate-partitioned queries according to TLP’s formulation, and generate multiple physically equivalent variants of queries \(Q_{\text{DQP}}\) using optimizer hints. We leverage 32 optimizer hints for MySQL and Percona, and 22 for TiDB (sourced from SQLancer-DQP); DQP does not support DuckDB. If the same inconsistency appears, the bug is considered reproducible by TLP or DQP; Otherwise, it is classified as a Join-specific bug. Among the 27 bugs originally detected by JoinEquiv, none were reproduced by either baseline, demonstrating that JoinEquiv possesses a fundamental and irreplaceable advantage over existing approaches in the specific domain of INNER JOIN logic bugs.

-- (*@\colorbox{yellow!65}{\color{codegray}TLP Transformed query for Listing 3}@*)
SELECT DISTINCT t0.c0 FROM t1 NATURAL JOIN t0 WHERE TRUE
UNION
SELECT DISTINCT t0.c0 FROM t1 NATURAL JOIN t0 WHERE FALSE
UNION
SELECT DISTINCT t0.c0 FROM t1 NATURAL JOIN t0 WHERE TRUE IS NULL; -- empty set (*@\checkicon@*)
-- (*@\colorbox{yellow!65}{\color{codegray}TLP Transformed query for Listing 6}@*)
SELECT t0.c0, t1.c0 FROM t0 INNER JOIN t1 ON t0.c0<-0.1 WHERE TRUE
UNION ALL
SELECT t0.c0, t1.c0 FROM t0 INNER JOIN t1 ON t0.c0<-0.1 WHERE FALSE
UNION ALL
SELECT t0.c0, t1.c0 FROM t0 INNER JOIN t1 ON t0.c0<-0.1 WHERE TRUE IS NULL; -- {0|1} (*@\bugicon@*)

During this validation, we observed an interesting phenomenon when applying the TLP strategy. As shown in Listing [lst:MySQL_bug_example], the original NATURAL JOIN query correctly returns an empty set, whereas its SJT-transformed counterpart incorrectly produces {0}. We then rewrote the original query following the TLP’s form, partitioning it into its corresponding sub-queries (as shown in Listing [lst:tlp36]). Interestingly, all partitions also correctly return empty sets, and their union remains consistent with the original query result. In contrast, as shown in Listing [lst:Percona_bug_example], the original query incorrectly returns {0\(|\)1}. When rewritten using the TLP approach, the partitioned queries yield the same erroneous result {0 \(|\) 1}, whereas the ADT-transformed query correctly produces an empty set. TLP cannot address the optimizer’s semantic bias due to structural transformations during join rewriting.

To ensure a fair and quantitative comparison between metamorphic testing approaches, we implemented a unified framework that executes JoinEquiv, TLP, and DQP side by side with identical query generation and database states. All three approaches share the same query generator, database state, random seeds, and execution environment, guaranteeing identical experimental conditions. For each original query, all three transformations are applied sequentially, and the results are compared across the same DBMS instance. This setup ensures a fair and controlled environment for large-scale evaluation.

Table 3 summarizes the number of bugs found in the 12-hour run on MySQL, TiDB, Percona, and DuckDB. It shows that JoinEquiv found 36 more join-related inconsistencies than TLP and 20 more than DQP (without DuckDB). TLP and DQP focus on predicate-level or plan-level consistency. In contrast, JoinEquiv operates at the algebraic level of join semantics, leveraging simple yet powerful set-theoretic identities. JoinEquiv systematically verifies the semantic correctness of join rewrites and set-operator interactions, which predicate partitioning or plan variation cannot cover. As a result, JoinEquiv can expose deep semantic inconsistencies arising from incorrect join rewriting, NULL propagation, and set operator evaluation. In summary, JoinEquiv effectively uncovers logic bugs that advanced state-of-the-art approaches fail to detect, thereby answering RQ3.

We measure the code coverage achieved by JoinEquiv on each evaluated DBMS. Over a 12-hour period using 10 threads, it achieves line (statement) coverage of 26.7%, 25.3%, and 19.9% for MySQL, Percona, and TiDB (statement), respectively³. The relatively low code coverage mainly stems from our focus on the query optimization component rather than the full DBMS. It is also worth mentioning that prior work has reported no positive correlation between code coverage and testing effectiveness for DBMSs.

6 Discussion↩︎

JoinEquiv currently restricts all columns to be declared as NOT NULL. This is a deliberate design choice due to the fundamental semantic mismatch between SQL’s three-valued logic (3VL) and set operators. In the SQL standard, equality comparison predicates involving NULL are evaluated to UNKNOWN and therefore excluded from INNER JOIN results, whereas the set operator treats NULL as equal at the set level and preserves them. As a result, certain equivalences that hold under classical relational algebra no longer hold in the presence of NULL. To avoid introducing spurious inconsistencies caused by semantic divergence, we restrict the current implementation to NOT NULL columns. Extending JoinEquiv to explicitly reconcile 3VL with set semantics is an interesting direction for future work.

Ideally, JoinEquiv relies on proven set-theoretic identities and implies that detected discrepancies represent genuine bugs. Nevertheless, false positives can arise from the subtle gap between relational algebra semantics and practical DBMS implementations. For example, we observed representation-level discrepancies such as mixed-type numeric comparisons in MySQL or signed-zero variations (e.g., “-0” vs. “0”) in PostgreSQL, where values are logically equivalent but binary distinct. Similarly, false positives may stem from the loss of non-functional metadata, such as MySQL’s ZEROFILL display attribute being discarded during intermediate set operations. Consequently, these cases reflect the boundary where DBMS implementations prioritize engineering trade-offs or standard compliance over strict bitwise equivalence. Beyond potential false positives, a distinct category of detected logic bugs arises from inconsistent type coercion or memory padding that violates semantic invariance and alters the final result set, as demonstrated by the NULL and CHAR handling defects in Listings 3 and 7.

As mentioned above, we did not discover optimizer logic bugs in PostgreSQL, CockroachDB, or SQLite. For PostgreSQL, only representation-level discrepancies (e.g., “-0” vs. “0”) were observed. This result is consistent with the widely recognized robustness of PostgreSQL and its compatible implementations. Richard Hipp, the primary author of SQLite, has attributed PostgreSQL’s high quality to its “very elaborate peer review process” [36]. We believe that this culture of strict standard compliance also extends to compatible systems such as CockroachDB, thereby reducing the likelihood of optimizer-level logic bugs. For SQLite, JoinEquiv identified several inconsistencies between JOIN and set operations. The developers clarified these as intended behaviors arising from SQLite’s unique type system: while JOIN predicates employ affinity-based comparisons, set operators enforce strict storage-class equality. Although classified as intentional design choices rather than logic bugs, these findings underscore JoinEquiv’s capacity to reveal subtle semantic gaps and implementation-specific variations. For example, MySQL broadly applies implicit type coercion across operators.

Regarding the theoretical scope of JoinEquiv, we prioritize operator-level structural completeness over an exhaustive enumeration of set-theoretic identities. Since identities equivalent to intersection are infinite, making mathematical completeness unattainable, we map intersection to all fundamental SQL set operators. Each rule is designed as a minimal canonical form, reducing unnecessary structural complexity and making the semantic correspondence between the original and transformed queries easier to analyze, thereby facilitating root-cause localization. This design principle leads us to prioritize single-rule transformations over complex rule compositions. Composing multiple rules often results in deeply nested queries that complicate semantic attribution.

Although only 8 out of the 27 confirmed bugs have been fixed so far, the fix rate alone does not directly reflect their severity. Among the reported bugs, the low fix rate stems mainly from the complexity of fixing logic bugs in join optimizers, which often requires modifying core rewrite rules and extensive regression testing to avoid performance regressions. Another important factor is the timing of bug disclosure. As most bugs were reported recently, subsequent releases were developed without awareness of them, making it unlikely that fixes can be incorporated in the short term.

7 Related Work↩︎

Among existing DBMS testing studies, the SQLancer family [27] is the most representative for discovering logic bugs and is the closest to our work. Its key contribution lies in providing a framework for systematically uncovering deep errors inside DBMSs. SQLancer targets logic bugs that lead to incorrect query results in DBMSs. Other representative approaches include PQS [19], NoREC [22], TLP [20], DQP [25], and CERT [37]. PQS and NoREC have been discussed in §1, while TLP and DQP were analyzed in §5.5. CERT [37] aims to identify performance issues caused by unexpected cardinality estimations, that is, the cases where the estimated number of result tuples significantly deviates from the actual number. In contrast, our approach specifically targets the detection of logic bugs in join optimizations, an area that none of the existing SQLancer-based techniques are designed to explore.

A variety of tools have been developed for generating database data [38]–[42] and SQL queries [16], [43]–[48] to automatically construct test cases for DBMS evaluation. However, relatively little attention has been paid to the design of test oracles, which are essential for determining the correctness of query results. Generation-based testing approaches [46], [49]–[53] have been widely adopted for DBMS validation, particularly for bug detection and benchmarking. Among them, SQLSmith [16] is one of the most popular generation-based DBMS testers. It constructs syntactically correct and complex SQL queries from scratch based on the existing database schema, primarily aiming to detect database crashes and internal errors. Recently, TQS [24] introduced data-guided schema generation to derive ground-truth results from wide tables and knowledge-guided query exploration to efficiently traverse the join search space. It then detects bugs by comparing the ground truth with the results of query plans enforced by optimizer hints. Unlike TQS, which relies on specific data synthesis and exploration strategies, JoinEquiv proposes a rigorous metamorphic oracle based on set-theoretic algebra that detects bugs through semantic inconsistencies rather than data lineage.

Mutation-based fuzzers have long been effective in software testing and have discovered numerous bugs [17], [54]–[61]. Early fuzzers such as AFL [17] can be adapted to lightweight DBMS components, but random mutations often fail to produce syntactically valid SQL inputs. Subsequent studies introduced taint analysis [54], [57] and symbolic execution [56], [61] to guide mutation, yet generating test cases that satisfy both syntax and semantics remains challenging. To address these limitations, recent advances have focused on structure-aware and sequence-oriented strategies. SQUIRREL [53] proposed a syntax-preserving mutation strategy on an intermediate representation and a semantics-guided instantiation mechanism to satisfy data dependencies, ensuring a high validity of generated queries. Building on this, LEGO [62] identifies that the order of SQL statements is crucial for triggering deep DBMS states. It utilizes type-affinity analysis to synthesize meaningful SQL sequences rather than isolated queries. Other works also contribute to specific scenarios, such as RATEL [59] for enterprise DBMS feedback, UNICORN [60] for time-series databases, and GRIFFIN [63] for grammar-free mutation. However, mutation-based fuzzers mainly use code coverage feedback (e.g., discovering new execution paths) to trigger crashes or assertion failures. They are not well-suited for detecting logic bugs, where the DBMS returns incorrect results without crashing. In contrast, our work focuses on the semantic correctness of query results. By systematically applying algebraic equivalence rules, we generate test oracles that can identify logical inconsistencies in join optimizations that coverage-guided fuzzers would likely miss.

8 Conclusion↩︎

Building on the basic principles of set theory, this paper introduced JoinEquiv, a novel framework for detecting logic bugs in DBMSs through equivalence-based query transformation. By viewing the join operator as a generalized intersection under set and multiset semantics, we systematically derived three provably equivalent rewriting rules (SJT, ADT, and SDT) and applied them to uncover inconsistencies overlooked by existing state-of-the-art testing approaches such as TLP and DQP. Extensive experiments on four DBMSs detected 27 previously unknown bugs and 14 verified as critical bugs, demonstrating that even simple algebraic equivalences can serve as powerful metamorphic relations for testing complex database systems. Future work will explore the application of equivalence-based testing beyond join operations.

Acknowledgements↩︎

We thank anonymous reviewers for their constructive comments and suggestions, which helped improve this paper. This work was supported in part by Ant Digital Technologies, Ant Group Research Fund. This work was also supported in part by the Shanghai Sailing Program No. 23YF1410600.

AI-Generated Content Acknowledgment↩︎

We claim that large language model (LLM) tools (GPT-4o and Grammarly) were used for text editing, e.g., spelling auto-correction, grammar checks, and sentence rephrasing, in the writing of this paper. We ensure that no AI-generated content was used without human verification or modification. We guarantee that no parts of the scientific content—including research design, data analysis, result generation, and code implementation—were generated or affected by AI systems.

References↩︎