The query optimizer is a fundamental component of database management systems that determines the most efficient execution strategy for a given query by evaluating alternative query plans. Among its tasks, join optimization plays a central role, as the order of joins in multi-table queries can significantly affect execution performance. However, due to the inherent complexity of join optimization, logical bugs are inevitable and often difficult to detect. While existing fuzzing tools have shown notable success in uncovering crash- and performance-related errors, effectively identifying logical bugs -- cases in which the system produces incorrect query results -- remains largely unresolved. In this paper, we propose a metamorphic testing approach to detect DBMS bugs related to INNER JOIN optimization through the lens of set theory. For each testing case, equivalent queries are generated based on a basic set operation -- intersection -- and three semantics-preserving transformation rules, i.e., symmetric join transformation, asymmetric difference transformation, and symmetric difference transformation, are introduced. These rules rewrite a simple NATURAL/INNER JOIN query into a more complex, yet semantically equivalent, form. We implement this design in JoinEquiv, which serves as a testing oracle to systematically uncover logical inconsistencies in DBMS query processing by comparing the results of original and transformed queries. Using JoinEquiv, we uncovered 29 previously unknown issues in mainstream DBMSs (MySQL, TiDB, DuckDB, and Percona), and 27 of them were officially confirmed. JoinEquiv reveals deep logical flaws in DBMS optimizers and executors, underscoring its value in enhancing DBMS robustness.

Database Management Systems (DBMS) perform various data operations such as arithmetic calculations and string manipulations when executing SQL queries. These operations are complex due to the wide range of data types and the intricate interactions between different data. Consequently, errors in implementing these data operations can lead to logic bugs, potentially causing issues such as implicit type coercion, overflow, and precision loss. Existing logic bug detection methods primarily focus on issues introduced during query optimization by adapting query-level strategies. However, these methods have limitations when it comes to detecting logic bugs caused by implementation errors in data types and operations. To address this, we propose equivalent data construction (EDC), a novel approach to detect logic bugs in data operation implementations within DBMSs. The core insight is that for data operation expressions in SQL queries, substituting them with precomputed result values should yield identical query outcomes. EDC mainly involves the following steps: first, construct equivalent data for an operation by calculating and storing the results in a derived equivalent table; then, transform the query by replacing the operation expressions with the precomputed results from the equivalent table. Any inconsistencies between the results of the base and transformed queries indicate potential logic bugs. We implemented EDC and evaluated it on six well-tested and widely-used DBMSs(e.g.,MySQL, MariaDB). Our evaluation revealed 52 previously unknown bugs, of which 38 have been confirmed by developers. Developers took these findings seriously. For example, MariaDB developers described our findings as counterintuitive, helping them uncover more issues related to data operations.

Logic bugs can cause DBMSs to silently produce incorrect results for a given query, posing significant threats to software reliability and remaining challenging to detect. Join is a fundamental operation in DBMSs, enabling the combination of data from multiple tables; however, due to its complexity, it is also susceptible to logic bugs. Existing works detect logic bugs in join optimizations by altering query hints and system variables to alter the optimizer's choice of execution plans. However, these approaches struggle to detect logic bugs when query hints or system variables fail to influence the optimizer's behavior, or when the logic bugs reside in join implementation code that is unrelated to optimization. In this paper, we present S et R elation S ynthesis (SRS), a black-box testing approach that detects logic bugs of join implementation in DBMSs by leveraging set relations among different join operations. SRS applies transformations to the original join queries, including modifications to join types, join orders, and join conditions, while ensuring that the outputs of both the original and transformed queries preserve the expected set relations. Violations of these set relations indicate potential logic bugs. We realized SRS and evaluated it on five widely-used and extensively-tested DBMSs: MySQL, MariaDB, TiDB, PostgreSQL, and DuckDB. SRS uncovered 33 previously unknown and unique bugs, all of which have been confirmed, with 12 already fixed. Among these, 33 are logic bugs, demonstrating SRS's effectiveness and practicality in detecting logic bugs in the implementation of join operations within DBMSs.

The SQL specification consists of hundreds of statement types, which leads to difficulties in DBMS fuzzing: state-of-the-art works generally reuse the statements of predefined types; the limited types cannot cover the full input space and test the corresponding logic consequently. In this paper, we propose Lego, a fuzzer to generate SQL sequences with abundant types to improve DBMS fuzzing coverage. The key idea of sequence generation is type-affinity, which indicates the meaningful occurrence of SQL type pairs (e.g., INSERT and SELECT). During each fuzzing iteration, Lego first proactively explores SQL statements of different types and analyzes affinities with coverage feedback. Next, when a new affinity is discovered, Lego synthesizes new SQL sequences containing the types progressively.We evaluate Lego on PostgreSQL, MySQL, MariaDB, and Comdb2 against SQLancer, SQLsmith, and Squirrel. The sequence-oriented fuzzing helps Lego outperform other fuzzers on branch coverage by 44%–198%. More importantly, in the continuous fuzzing, Lego has discovered 102 new vulnerabilities confirmed by the corresponding vendors, including 6 bugs in PostgreSQL, 21 bugs in MySQL, 42 bugs in MariaDB, and 33 bugs in Comdb2. Among them, 22 CVEs have been assigned due to their severe security influences.