A Set-Theoretic Approach to Detecting Logic Bugs in DBMS Inner Join Optimizations
Read the paper · doi:10.1109/icde65706.2026.00224 · arXiv:2606.23294
What this paper does with SQLancer
The test case generation is built on SQLancer, which the authors extend so that all generated columns are NOT NULL, and it relies on SQLancer's randomised population of predicates and clauses. TLP is both its closest conceptual relative -- the paper says both rest on set-theoretic principles -- and one of the two approaches it is measured against, with each JoinEquiv bug rewritten into TLP and DQP form to see whether they reproduce it.
JoinEquiv detects logic bugs in INNER JOIN optimisation through set theory. For each test case it generates equivalent queries from the intersection operation together with three semantics-preserving rewrite rules -- symmetric join, asymmetric difference and symmetric difference transformations -- which turn a simple join query into a more complex but equivalent form, and compares the results. Across MySQL, TiDB, DuckDB and Percona it uncovered 29 previously unknown issues, 27 officially confirmed.
How it was classified
uses infrastructure — yes (implementation)
M10 states the test case generation builds on the SQLancer framework for grammar-aware query generation, M11 that they extended it with a NOT NULL precondition, and M12 that they rely on its randomised population of ON predicates, WHERE clauses and SELECT expressions. M26 also takes optimizer hints from SQLancer-DQP.
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.
Such a table permutation, combined with SQLancer’s randomized population of ONpredicates,WHEREclauses, and SELECT list expressions, ensures that the framework explores a diverse range of symmetric and asymmetric execution plans.
extends technique — no
M11 extends the SQLancer tool with a generation precondition, which is reuse of the codebase rather than extension of a technique. The oracle itself, built from intersection and three difference transformations, is presented as new; TLP is described as sharing a conceptual foundation, not as being generalised.
compares with — yes
TLP and DQP are the two approaches JoinEquiv is compared against: all three transformations are applied to every generated query in the same session, and each reported bug is rewritten into TLP and DQP form to test reproducibility.
Ternary Logic Partitioning (TLP)Differential Query Plans (DQP)
Within each thread, for every INNER JOINquery, JoinEquiv, TLP, and DQP are applied sequentially under the same system TABLE IISUMMARY OFLOGICBUGREPORTS ANDVERIFICATIONSTATUS INDIFFERENTRDBMSS RDBMS Reported Verified Fixed Intended Component Severity Identifier MySQL 10 8 1 2 Optimizer (8) Critical (8)Bug#118544, Bug#118684, Bug#118710, Bug#118857, Bug#118858, Bug#118949, Bug#119032, Bug#119059 TiDB 13 13 4 0Planner (11) Execution (2)Critical (3)#62380, #62444, #62456, #62459, #62460, #62644, #62645, #62689, #63596, #63601, #63635, #63636, #63736 Percona 3 3 0 0 Optimizer (3) Critical (3)PS-10124, PS-10127, DISMYSQL-535 DuckDB 3 3 3 0 – –#20483, #20486, #20608 Total29 27 8 2 – Critical (14) – Note:For DuckDB, component and severity were not provided, so they are marked as “–”.
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).
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.
Crucially, for every generated original INNER JOINquery 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.
describes as state of the art — uncertain
A pattern fired on M43, which was not among the mentions read here. M14 calls TLP and DQP representative approaches rather than the state of the art in those words.
Where this differs from the pattern checks
The regular expressions that scan for these relationships are advisory. Where the reading above contradicts one, the reason is recorded.
What could not be determined
- Whether the paper calls SQLancer or its techniques state of the art: the mention a pattern fired on, M43, was outside the set read.
SQLancer publications it cites (6)
Bibliography entries that resolved to a SQLancer publication, or to a paper by one of the project's authors. A sentence citing one of these numbers is a reference to SQLancer even when it never writes the name.
| # | Entry | Matched as |
|---|---|---|
| 19 | M. Rigger and Z. Su, “Testing database engines via pivoted query synthesis,” in14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), 2020, pp. 667–682. | sqlancer publication · PQS |
| 20 | ——, “Finding bugs in database systems via query partitioning,”Proc. ACM Program. Lang., vol. 4, no. OOPSLA, pp. 211:1–211:30, 2020. | sqlancer publication · TLP |
| 22 | M. Rigger and Z. Su, “Detecting optimization bugs in database engines via non-optimizing reference engine construction,” inProceedings of the 28th ACM Joint European Software Engineering Conference and Symposium on th... | sqlancer publication · NOREC |
| 25 | J. Ba and M. Rigger, “Keep it simple: Testing databases via differential query plans,” 2, no. 3, pp. 188:1–188:26, 2024. | sqlancer publication · DQP |
| 27 | M. Rigger, “SQLancer,” https://github.com/sqlancer/sqlancer, 2025, accessed: 2025-10-27. | sqlancer publication |
| 37 | J. Ba and M. Rigger, “CERT: Finding performance issues in database systems through the lens of cardinality estimation,” inProceedings of the 46th IEEE/ACM International Conference on Software Engineering, 2024, pp. 13... | sqlancer publication · CERT |
Every place it refers to SQLancer (43)
43 sentences, each stored verbatim from the extracted text with where it was found and how. “Citation marker” means the sentence names no tool at all and was reached through a reference number that resolved to a SQLancer publication.
| Id | Sentence | Found by | Where |
|---|---|---|---|
| M1 | Another approach is pivoted query synthesis (PQS) [19], which validates query results by constructing auxiliary queries centered on a specific pivot row. |
technique |
I INTRODUCTION page 1 |
| M2 | 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. | technique | I INTRODUCTION page 1 |
| M3 | Recently, metamorphic tests have been increasingly used for DBMS testing [20]–[23]. | citation marker | I INTRODUCTION page 1 |
| M4 | Representative frameworks include ternary logic partitioning (TLP) [20] and non-optimizing reference engine construction (NoREC) [22]. | technique | I INTRODUCTION page 1 |
| M5 | 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. | technique | I INTRODUCTION page 1 |
| M6 | As shown in Table I, PQS, NoREC, DQP, and TQS do not support EXCEPT,INTERSECT, or UNION operations, while TLP supports only UNION(including ALL). | technique | I INTRODUCTION page 2 |
| M7 | ApproachEXCEPT (ALL)INTERSECT (ALL)UNION (ALL) PQS× × × NoREC× × × TLP× × ⃝ DQP× × × TQS× × × JoinEquiv (*)⃝ ⃝ ⃝ To address this issue, we perform an in-depth exploration of set-theoretic equivalences in join queries for test case generation. | technique | I INTRODUCTION page 2 |
| M8 | 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. | citation marker | I INTRODUCTION page 2 |
| M9 | , they cannot be detected by existing metamorphic testing approaches such as TLP and DQP, thus highlighting the unique and complementary value of JoinEquiv. | technique | I INTRODUCTION page 2 |
| M10 | The test case generation builds upon the SQLancer framework, which provides a grammar-aware SQL query generation engine. |
name |
E Database and Query Generation page 6 |
| M11 | We extend SQLancer to satisfy an additional precondition that all columns are NOT NULL. |
name |
E Database and Query Generation page 6 |
| M12 | Such a table permutation, combined with SQLancer’s randomized population of ONpredicates,WHEREclauses, and SELECT list expressions, ensures that the framework explores a diverse range of symmetric and asymmetric execution plans. |
name |
E Database and Query Generation page 6 |
| M13 | Within each thread, for every INNER JOINquery, JoinEquiv, TLP, and DQP are applied sequentially under the same system TABLE IISUMMARY OFLOGICBUGREPORTS ANDVERIFICATIONSTATUS INDIFFERENTRDBMSS RDBMS Reported Verified Fixed Intended Component Severity Identifier MySQL 10 8 1 2 Optimizer (8) Critical (8)Bug#118544, Bug... |
technique |
A Evaluation Setup page 7 |
| M14 | 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). |
technique |
E Comparison to Existing DBMS Testing Approaches page 9 |
| M15 | TLP shares a conceptual foundation withJoinEquiv, 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 uncoveri... |
technique |
E Comparison to Existing DBMS Testing Approaches page 9 |
| M16 | 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. |
technique |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M17 | Crucially, for every generated original INNER JOINquery 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. |
technique |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M18 | Ternary Logic Partitioning (TLP) (specifically, the TLPWHEREvariant) [20] relies on the set-theoretic principle of UNION. |
technique |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M19 | As illustrated in Listing 8, TLP partitions an original query into three sub-queries by injecting predicates into the WHEREclause based on SQL’s ternary logic (TRUE,FALSE, NULL) and validates that their combined result matches the original. |
technique |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M20 | Differential Query Plans (DQP) [25], in contrast, targets join optimizer robustness. |
technique |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M21 | For each bug exposed by JoinEquiv, we manually rewrite the corresponding query into its TLPand DQP-equivalent forms and execute them on the same database. |
technique |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M22 | Example of ternary logic partitioning (TLP) and differential query plans (DQP). |
technique |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M23 | c0; TLP (Where) transformed query SELECT *FROMt0INNER JOINt1ONt0. |
technique |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M24 | c0WHERE TRUEISNULL; DQP transformed query Plan variant 1 (hash join) hint SELECT/ *+ HASH_JOIN(t0, t1) */*FROMt0INNER JOINt1ON t0. |
technique |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M25 | c0; Formally, given an INNER JOINqueryQ origwhose 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 QDQPusing optimizer hints. |
technique |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M26 | We leverage 32 optimizer hints for MySQL and Percona, and 22 for TiDB (sourced from SQLancer-DQP); DQP does not support DuckDB. |
name |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M27 | If the same inconsistency appears, the bug is considered reproducible by TLP or DQP; Otherwise, it is classified as aJoin-specific bug. |
technique |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M28 | TLP transformed query for Listing 3 and Listing 6 --TLP Transformed query for Listing 3 SELECT DISTINCTt0. |
technique |
E Comparison to Existing DBMS Testing Approaches page 10 |
| M29 | c0FROMt1NATURAL JOINt0WHERE TRUEISNULL; -- empty set✓ --TLP Transformed query for Listing 6 SELECTt0. | technique | E Comparison to Existing DBMS Testing Approaches page 10 |
| M30 | 1 WHERE TRUEISNULL; -- {0|1}ὁB During this validation, we observed an interesting phenomenon when applying the TLP strategy. | technique | E Comparison to Existing DBMS Testing Approaches page 10 |
| M31 | We then rewrote the original query following the TLP’s form, partitioning it into its corresponding subqueries (as shown in Listing 9). | technique | E Comparison to Existing DBMS Testing Approaches page 10 |
| M32 | 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. | technique | E Comparison to Existing DBMS Testing Approaches page 10 |
| M33 | TLP cannot address the optimizer’s semantic bias due to structural transformations during join rewriting. | technique | E Comparison to Existing DBMS Testing Approaches page 10 |
| M34 | 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. | technique | E Comparison to Existing DBMS Testing Approaches page 10 |
| M35 | For each original query, all three transformations are applied sequentially, and the results are compared across TABLE IIINUMBER OFBUGS REPORTED IN A12H UNIFIED RUN(DQPRESULTS EXCLUDEDUCKDB) DBMSTLP DQP JoinEquiv TiDB 0 0 7 MySQL 0 1 13 Percona 0 2 3 DuckDB 0 – 13 Total0 3 36 Increment36↑20↑– the same DBMS instance. | technique | E Comparison to Existing DBMS Testing Approaches page 10 |
| M36 | It shows that JoinEquiv found 36 more join-related inconsistencies than TLP and 20 more than DQP (without DuckDB). | technique | E Comparison to Existing DBMS Testing Approaches page 11 |
| M37 | TLP and DQP focus on predicate-level or plan-level consistency. | technique | E Comparison to Existing DBMS Testing Approaches page 11 |
| M38 | Among existing DBMS testing studies, the SQLancer family [27] is the most representative for discovering logic bugs and is the closest to our work. | name | VII RELATEDWORK page 12 |
| M39 | SQLancer targets logic bugs that lead to incorrect query results in DBMSs. | name | VII RELATEDWORK page 12 |
| M40 | Other representative approaches include PQS [19], NoREC [22], TLP [20], DQP [25], and CERT [37]. | technique | VII RELATEDWORK page 12 |
| M41 | PQS and NoREC have been discussed in §I, while TLP and DQP were analyzed in §V-E. | technique | VII RELATEDWORK page 12 |
| M42 | 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. | technique | VII RELATEDWORK page 12 |
| M43 | 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. | technique | VIII CONCLUSION page 12 |