SRS: Detecting Logic Bugs of Join Implementation in DBMSs via Set Relation Synthesis
Read the paper · doi:10.1145/3769828
What this paper does with SQLancer
SRS is implemented on SQLancer, generating its database state with SQLancer's syntax-rule-based random generation and keeping SQLancer's query generation strategy for features outside the join. SQLancer's oracles are then also its baselines: PQS, NoREC, TLP and DQP are four of the six approaches it is measured against, and it reports finding 9 to 12 more bugs than each.
SRS detects logic bugs in how a DBMS implements joins rather than in how it optimises them. The authors argue that existing work perturbs query hints and system variables to change the optimizer's plan choice, which fails when those knobs do not influence the optimizer or when the fault lies in join implementation code unrelated to optimisation. SRS instead transforms a join query -- changing join types, orders and conditions -- so the original and transformed results must stand in a known set relation, and treats a violation as a bug. Across five extensively tested DBMSs it found 33 previously unknown bugs, all confirmed.
How it was classified
uses infrastructure — yes (implementation)
M7 states SRS applies SQLancer's automated random generation for the database state and M9 that its query generation follows SQLancer's strategy for other language features; M23 describes SRS itself as one of the test oracles implemented on SQLancer, alongside PQS, NoREC, TLP and DQP.
SRS applies the automated, syntax-rule-based random generation approach of SQLancer to ensure that the database state exhibits sufficient diversity, thereby enabling thorough and effective bug detection.
For the generation of other language features, aside from considering the tables involved in joins, our approach remains consistent with SQLancer’s query generation strategy for NoREC test oracle [23].
We compared the code coverage achieved by these approaches, and the results showed that the test oracles implemented on SQLancer— PQS, NoREC, TLP, DQP, and SRS—achieved similar code coverage.
extends technique — no
Set Relation Synthesis is presented as its own oracle over join transformations. TLP is discussed as a related set-based approach whose transformation targets differ, not as something SRS generalises.
compares with — yes
Four of the six baselines are SQLancer oracles, all run for 24 hours on the same systems, with bug counts and line coverage reported for each.
Pivoted Query Synthesis (PQS)Non-optimizing Reference Engine Construction (NoREC)Ternary Logic Partitioning (TLP)Differential Query Plans (DQP)
We selected six state-of-the-art approaches for comparison: PQS [ 25], TLP [ 24], NoREC [ 23], Pinolo [ 11], EET [ 13], and DQP [ 3].
As such, we include a comparison with NoREC in our evaluation.
Table 5 shows that SRS found 12, 9, 10, 20, 17, and 13 more bugs than PQS, NoREC, TLP, DQP, Pinolo, and EET, respectively.
For instance, when testing MySQL for 24 hours, PQS, TLP, DQP, and SRS achieved line coverage rates of 23.
describes as state of the art — yes
M12 calls the six approaches, PQS, NoREC and TLP among them, state-of-the-art; M1 says the same of DQP for join optimisation.
TQS [ 28] and DQP [ 3] are two state-of-the-art testing approaches that target logic bugs in the optimization of join operations.
We selected six state-of-the-art approaches for comparison: PQS [ 25], TLP [ 24], NoREC [ 23], Pinolo [ 11], EET [ 13], and DQP [ 3].
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 |
|---|---|---|
| 2 | Jinsheng Ba and Manuel Rigger. 2024. CERT: Finding Performance Issues in Database Systems Through the Lens of Cardinality Estimation. InProceedings of the IEEE/ACM 46th International Conference on Software Engineering... | sqlancer publication · CERT |
| 3 | Jinsheng Ba and Manuel Rigger. 2024. Keep It Simple: Testing Databases via Differential Query Plans. doi:10.1145/3654991 | sqlancer publication · DQP |
| 23 | Manuel Rigger and Zhendong Su. 2020. Detecting optimization bugs in database engines via non-optimizing reference engine construction. InProceedings of the 28th ACM Joint Meeting on European Software Engineering Confe... | sqlancer publication · NOREC |
| 24 | Manuel Rigger and Zhendong Su. 2020. Finding bugs in database systems via query partitioning.Proc. ACM Program. Lang.4, OOPSLA, Article 211 (nov 2020), 30 pages. doi:10.1145/3428279 | sqlancer publication · TLP |
| 25 | Manuel Rigger and Zhendong Su. 2020. Testing Database Engines via Pivoted Query Synthesis. In14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). USENIX Association, 667–682. https://www. us... | sqlancer publication · PQS |
| 32 | Chi Zhang and Manuel Rigger. 2025. Constant Optimization Driven Database System Testing. 2025), 24 pages. doi:10.1145/3709674 | sqlancer publication · CODDTEST |
Every place it refers to SQLancer (59)
59 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 | TQS [ 28] and DQP [ 3] are two state-of-the-art testing approaches that target logic bugs in the optimization of join operations. |
technique |
1 Introduction page 2 |
| M2 | To detect the logic bug shown in Figure 1, we applied all query plan transformation techniques from both TQS and DQP to the bug-inducing query, i. |
technique |
1 Introduction page 2 |
| M3 | In step 1, we randomly generate the database state with syntax-rule-based generators, which is a common practice in existing works [ 23–25]. | citation marker | 3.1 Overview page 6 |
| M4 | Additionally, the influence of NULLvalues must be carefully considered, as addressed in TLP[24]. |
technique |
3.3 Set Relation-driven Join Transformation page 9 |
| M5 | 4 Implementation We implemented SRS on top of SQLancer1, a DBMS testing framework designed for the random generation of database states and SQL queries, which also supports multiple test oracles [ 23,24]. | citation marker | 3.4 Results Checking page 11 |
| M6 | Following the standard pipeline in popular DBMS testing tools like SQLancer, we generate the database state first to improve semantic correctness by generating stateconforming queries. |
name |
4 Implementation page 11 |
| M7 | SRS applies the automated, syntax-rule-based random generation approach of SQLancer to ensure that the database state exhibits sufficient diversity, thereby enabling thorough and effective bug detection. |
name |
4 Implementation page 11 |
| M8 | com/sqlancer/sqlancer 3, No. |
name |
4 Implementation page 11 |
| M9 | For the generation of other language features, aside from considering the tables involved in joins, our approach remains consistent with SQLancer’s query generation strategy for NoREC test oracle [23]. |
name |
4 Implementation page 12 |
| M10 | These DBMSs are also commonly used in the evaluation of previous works [ 3,23–25]. | citation marker | 5.1 Testing Setup page 13 |
| M11 | This aligns with observations from previous works [ 3,24], which limited our reporting of additional potential bugs to avoid duplication. | citation marker | 5.2 New Bugs page 15 |
| M12 | We selected six state-of-the-art approaches for comparison: PQS [ 25], TLP [ 24], NoREC [ 23], Pinolo [ 11], EET [ 13], and DQP [ 3]. |
technique |
5.4 Comparison With the State-of-the-Art page 17 |
| M13 | Both DQP and TQS [ 28] are approaches designed to detect logic bugs in join operations by leveraging the equivalence among different query plans for a given query. |
technique |
5.4 Comparison With the State-of-the-Art page 17 |
| M14 | DQP is a simpler alternative to TQS and has specifically studied TQS, concluding that it offers the same level of bug-finding effectiveness [ 13] as TQS. |
technique |
5.4 Comparison With the State-of-the-Art page 17 |
| M15 | Therefore, we assume that comparing with DQP effectively represents a comparison with this class of approaches. |
technique |
5.4 Comparison With the State-of-the-Art page 17 |
| M16 | PQS generates queries based on the database state such that the result is guaranteed to include specific rows from the database. |
technique |
5.4 Comparison With the State-of-the-Art page 17 |
| M17 | Both TLP and Pionlo leverage set-based relationships to detect logic bugs, but their transformation targets are expressions within query clauses. |
technique |
5.4 Comparison With the State-of-the-Art page 17 |
| M18 | NoREC generates equivalent queries by exploiting the equivalence between the WHERE and SELECT clauses. |
technique |
5.4 Comparison With the State-of-the-Art page 17 |
| M19 | While NoREC is not designed to specifically test join operations, it has previously detected join-related bugs. |
technique |
5.4 Comparison With the State-of-the-Art page 17 |
| M20 | As such, we include a comparison with NoREC in our evaluation. |
technique |
5.4 Comparison With the State-of-the-Art page 17 |
| M21 | Table 5 shows that SRS found 12, 9, 10, 20, 17, and 13 more bugs than PQS, NoREC, TLP, DQP, Pinolo, and EET, respectively. |
technique |
5.4 Comparison With the State-of-the-Art page 17 |
| M22 | DBMSPQS NoREC TLPDQP Pinolo EETSRS MySQL 0 - 4 0 2 310 MariaDB-0 - 0 1 -6 TiDB - - 2 0 0 04 PostgreSQL 0 0 0 - - 02 DuckDB-01- - -1 Total 0 0 7 0 3 323 Increment 12↑9↑10↑20↑17↑13↑“-” indicates that the tool does not support the DBMS. |
technique |
5.4 Comparison With the State-of-the-Art page 18 |
| M23 | We compared the code coverage achieved by these approaches, and the results showed that the test oracles implemented on SQLancer— PQS, NoREC, TLP, DQP, and SRS—achieved similar code coverage. |
name |
5.4 Comparison With the State-of-the-Art page 18 |
| M24 | For instance, when testing MySQL for 24 hours, PQS, TLP, DQP, and SRS achieved line coverage rates of 23. |
technique |
5.4 Comparison With the State-of-the-Art page 18 |
| M25 | And this is a widely used method for comparing different test oracles [ 23]. | citation marker | 5.4 Comparison With the State-of-the-Art page 18 |
| M26 | In this experiment, to determine whether the bugs detected by SRS could be identified by other approaches’ oracle, we selected TQS/DQP, TLP, and NoREC for comparison because their fixed transformation patterns allow for reliable manual validation. | technique | 5.4 Comparison With the State-of-the-Art page 18 |
| M27 | We excluded EET, Pinolo, and PQS due to their vast transformation spaces, 3, No. | technique | 5.4 Comparison With the State-of-the-Art page 18 |
| M28 | SRS: Detecting Logic Bugs of Join Implementation in DBMSs via Set Relation Synthesis 363:19 15 2 11 1 TQS/DQP ’s oracle TLP ’s oracle NoREC ’s oracle Logic bugs found by SRS 33 Fig. | technique | 5.4 Comparison With the State-of-the-Art page 18 |
| M29 | Similarly, Pinolo and PQS were excluded due to scalability issues: in Pinolo, the space of approximate queries is prohibitively large, and in PQS, there can be infinitely many possible pivoted queries for a given row. | technique | 5.4 Comparison With the State-of-the-Art page 19 |
| M30 | Out of the 33 logic bugs detected by SRS, 16 can be detected by TQS/DQP’s oracle; 4 can be detected by TLP’s oracle; 2 can be detected by NoREC’s oracle; and 13 are uniquely detected by SRS. | technique | 5.4 Comparison With the State-of-the-Art page 19 |
| M31 | For TQS/DQP’s oracle, we incorporated query hints and relevant system variables on the buginducing test cases. | technique | 5.4 Comparison With the State-of-the-Art page 19 |
| M32 | The result shows that 17 bugs are undetectable by TQS/DQP’s oracle. | technique | 5.4 Comparison With the State-of-the-Art page 19 |
| M33 | When TQS/DQP fail to influence the optimizer’s behavior, or when the logic bugs lie in the join implementation unrelated to optimization, TQS/DQP is unable to detect certain issues. | technique | 5.4 Comparison With the State-of-the-Art page 19 |
| M34 | Although the analysis shows that 16 out of the 33 logic bugs detected by SRS could theoretically be detected by DQP’s oracle, the tool of DQP failed to uncover any of them during 24 hours, as shown in Table 5. | technique | 5.4 Comparison With the State-of-the-Art page 19 |
| M35 | To determine why a gap exists between theoretical (Figure 6) and practical (Table 5) bug detection in DQP, we checked the join queries generated by DQP’s tool, and found it supports limited join operations (i. | technique | 5.4 Comparison With the State-of-the-Art page 19 |
| M36 | For TLP’s oracle, we manually constructed three follow-up join queries based on the condition in the bug-inducing query, corresponding to the forms p,NOT p, and p IS NULL. | technique | 5.4 Comparison With the State-of-the-Art page 19 |
| M37 | Our analysis shows that four of the bugs detected by SRS can also be identified by TLP’s oracle, whereas the remaining logic bugs cannot be detected by it. | technique | 5.4 Comparison With the State-of-the-Art page 19 |
| M38 | For NoREC’s oracle, we manually constructed two equivalent queries by leveraging the equivalence between the WHERE and SELECT clauses in the bug-inducing query. | technique | 5.4 Comparison With the State-of-the-Art page 19 |
| M39 | Our analysis shows that two of the bugs detected by SRS can also be identified by NoREC’s oracle, while the remaining logic bugs cannot be detected by it. | technique | 5.4 Comparison With the State-of-the-Art page 19 |
| M40 | Given that neither NoREC nor TLP’s oracle is designed to test the implementation of join operations, it is unsurprising that they fail to detect most of these logic bugs. | technique | 5.4 Comparison With the State-of-the-Art page 19 |
| M41 | Example of applying the SRS oracle to a join-related bug from other tools’ bug list -- A bug-inducing case from PQS's bug list: https://www. | technique | 5.4 Comparison With the State-of-the-Art page 20 |
| M42 | at/dbms-bugs/ CREATE TABLEt0(c0INT); CREATE TABLEt1(c0INT) ENGINE = MEMORY; INSERT INTOt0(c0)VALUES(0); INSERT INTOt1(c0)VALUES(-1); -- PQS's oracle: expected: row is fetched, actual: no row is fetched SELECT*FROMt0, t1WHERE(CAST(t1. | technique | 5.4 Comparison With the State-of-the-Art page 20 |
| M43 | We then applied the SRS’s oracle to these bug-inducing cases and successfully reproduced 69 of them, including 16 out of 18 in TQS, 14 out of 15 in DQP, 5 out of 6 in PQS, all 5 in NoREC, 16 out of 17 in TLP, 7 out of 8 in Pinolo, and all 6 in EET. | technique | 5.4 Comparison With the State-of-the-Art page 20 |
| M44 | Listing 5 demonstrates the SRS oracle applied to a join-related bug from PQS’s bug list. | technique | 5.4 Comparison With the State-of-the-Art page 20 |
| M45 | The implementation beyond SQLancer. | name | 6 Discussion page 21 |
| M46 | We made several modifications to SQLancer to enhance the diversity and effectiveness of the generated test cases. | name | 6 Discussion page 21 |
| M47 | Specifically, we adjusted SQLancer to produce schemas with a wider range of data types (e. | name | 6 Discussion page 21 |
| M48 | Non-optimizing Reference Engine (NoREC) [ 23] assumes that a predicate should evaluate to the same value in both the WHERE and SELECT clauses, and leverages this assumption to construct a non-optimizable form of the query. | technique | 7 Related Work page 21 |
| M49 | Differential Query Execution (DQE) [ 27] adopts a similar idea to NoREC, assuming that a predicate should yield consistent results, regardless of whether it appears in a SELECT ,UPDATE, or DELETE statement. | technique | 7 Related Work page 21 |
| M50 | CODDTest [ 32] leverages constant folding and propagation on expressions to produce equivalent queries. | technique | 7 Related Work page 21 |
| M51 | Ternary Logic Partitioning (TLP) [ 24] assumes that a predicate pcan evaluate to TRUE,FALSE, or NULL. | technique | 7 Related Work page 21 |
| M52 | Although both TLP and SRS use the UNION 3, No. | technique | 7 Related Work page 21 |
| M53 | set relation as their test oracle, TLP and SRS differ in target and methodology: (1) SRS focuses on issues related to the implementation bugs of join operations, while TLP targets bugs in predicate handling code via query decomposition. | technique | 7 Related Work page 22 |
| M54 | TLP decomposes a query into 3 based on predicates with TRUE/FALSE/NULLresults. | technique | 7 Related Work page 22 |
| M55 | Transformed Query Synthesis (TQS) [ 28] and Differential Query Plan (DQP) [ 3] target logic bugs in join optimizations and leverage equivalence relationships among different query plans generated for the same query. | technique | 7 Related Work page 22 |
| M56 | SRS is orthogonal to TQS and DQP in targets and methods: (1) TQS and DQP target join optimization bugs, while SRS focuses on join implementation bugs. | technique | 7 Related Work page 22 |
| M57 | (2) TQS and DQP construct test oracles by using query hints to execute different plans, while SRS generates test oracles by transforming the order, type, and conditions of join operations to synthesize set relations. | technique | 7 Related Work page 22 |
| M58 | Cardinality Estimation Restriction Testing (CERT) [ 2] is designed to detect performance issues from the perspective of cardinality estimation. | technique | 7 Related Work page 22 |
| M59 | Given a query, CERT generates a more restrictive variant under the assumption that the cardinality estimator should predict a lower number of rows returned compared to the original query. | technique | 7 Related Work page 22 |