Unveiling Logic Bugs in SPJG Query Optimizations within DBMS
Read the paper · doi:10.1145/3764583
What this paper does with SQLancer
SQLancer is the paper's reference point and its baseline: four of SQLancer's methods -- PQS, TLP, NoREC and DQP -- are the four baselines TQS is measured against, and the paper calls SQLancer the state-of-the-art approach for detecting logic bugs while arguing it is not designed for multi-table queries.
TQS targets logic bugs in Select-Project-Join-Group By query optimisation, arguing that existing generation-based tools rely on random testing and under-exercise error-prone areas such as multi-table joins and grouped aggregation. Its Data-guided Schema and Query Generation solves the ground-truth problem for multi-table queries by deriving data from dimensionally aggregated data cubes, mapping it into a wide table, normalising that into a testing schema, and keeping a bitmap index to track expected results. Knowledge-guided Query Space Exploration avoids repeating the same searches. Across four DBMSs it found 226 bugs in 24 hours.
How it was classified
uses infrastructure — no
Nothing shown says TQS is built on SQLancer's codebase; the paper's own generation is derived from data cubes, and SQLancer appears as the thing being measured against.
extends technique — no
TQS presents its own ground-truth construction for multi-table queries rather than generalising PQS, TLP or NoREC.
compares with — yes
M7 states four methods in SQLancer are used as the baselines, and M8 to M11 name them as PQS, TLP, NoREC and DQP.
Pivoted Query Synthesis (PQS)Ternary Logic Partitioning (TLP)Non-optimizing Reference Engine Construction (NoREC)Differential Query Plans (DQP)
We compare TQS with SQLancer,3which is the state-of-the-art approach to detecting logic bugs in databases.
We use four methods in SQLancer as our baselines.
to the compatibility problem, SQLancer implements different approaches on different databases (PQS, TLP and DQP on MySQL and PolarDB; NoRec and DQP on MariaDB; TLP and DQP on TiDB).
describes as state of the art — yes
M5 calls SQLancer the state-of-the-art approach to detecting logic bugs in databases.
We compare TQS with SQLancer,3which is the state-of-the-art approach to detecting logic bugs in databases.
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 |
|---|---|---|
| 4 | Jinsheng Ba and Manuel Rigger. 2024. CERT: Finding performance issues in database systems through the lens of cardinality estimation. In ICSE. 133:1–133:13. | sqlancer publication · CERT |
| 5 | Jinsheng Ba and Manuel Rigger. 2024. Keep it simple: Testing databases via differential query plans. Proc.ACMManag. Data2, 3 (2024), 188. | sqlancer publication · DQP |
| 49 | Manuel Rigger and Zhendong Su. 2020. Detecting optimization bugs in database engines via non-optimizing reference engine construction. In Proceedings of the ACM Joint Meeting on ESEC and FSE. 1140–1152. | sqlancer publication · NOREC |
| 50 | Manuel Rigger and Zhendong Su. 2020. Finding bugs in database systems via query partitioning. Proceedingsofthe ACM on Programming Languages 4, OOPSLA (2020), 1–30. | sqlancer publication · TLP |
| 51 | Manuel Rigger and Zhendong Su. 2020. SQLancer. [EB/OL]. (2020). Retrieved May 2024 from https://github.com/ sqlancer/sqlancer | sqlancer publication |
| 52 | Manuel Rigger and Zhendong Su. 2020. Testing database engines via pivoted query synthesis. In Proceedingsofthe OSDI 20. 667–682. | sqlancer publication · PQS |
Every place it refers to SQLancer (38)
38 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 | SQLancer [ 51] has emerged as a promising tool for detecting logic bugs in DBMS through the generation and execution of random SQL queries, supplemented by differential testing. |
name |
1 Introduction page 2 |
| M2 | 3 Data-guided Schema and Query Generation (DSG) SQLancer [ 51] automatically detects logic bugs in the implementation of DBMS. |
name |
2.2 Scheme Overview page 6 |
| M3 | Using the randomly generated database, it adopts differential testing approaches such as DifferentialQueryPlans (DQP) [5] to detect logic bugs. |
technique |
2.2 Scheme Overview page 6 |
| M4 | Note that SQLancer is originally designed for logic bug detection in random queries, with a particular focus on differential testing of complex expressions in single-table scenarios. |
name |
2.2 Scheme Overview page 6 |
| M5 | We compare TQS with SQLancer,3which is the state-of-the-art approach to detecting logic bugs in databases. |
name |
4.2 Query Generation Space page 18 |
| M6 | SQLancer is not designed to test multi-table queries. |
name |
4.2 Query Generation Space page 18 |
| M7 | We use four methods in SQLancer as our baselines. |
name |
4.2 Query Generation Space page 18 |
| M8 | The first one is PQS [ 52], which constructs queries to fetch a randomly selected tuple from a table. |
technique |
4.2 Query Generation Space page 18 |
| M9 | The second one is TLP [ 52], which decomposes a query into three partitioning queries, each of which computes its result on that tuple. |
technique |
4.2 Query Generation Space page 18 |
| M10 | The third one is NoRec [ 49], which targets logic bugs generated by the optimization process in DBMS. |
technique |
4.2 Query Generation Space page 18 |
| M11 | The fourth one is DQP [ 5], which enforces different query plans for the same query and validates that the results are consistent. |
technique |
4.2 Query Generation Space page 18 |
| M12 | com/sqlancer/sqlancer 4http://embed. |
name |
5.1 Overview and Showcase of Join Bug Reports page 18 |
| M13 | 0 4 8 12 16 20 24 /uni0000004b/uni00000052/uni00000058/uni00000055/uni000000560100200300400/uni00000047/uni0000004c/uni00000059/uni00000048/uni00000055/uni00000056/uni00000048/uni00000003/uni0000004a/uni00000055/uni00000044/uni00000053/uni0000004b/uni00000056/uni00000003/uni00000012/uni00000003/uni0000004e TQSPQS TL... |
technique |
5.3 Comparison with Existing Tools page 28 |
| M14 | to the compatibility problem, SQLancer implements different approaches on different databases (PQS, TLP and DQP on MySQL and PolarDB; NoRec and DQP on MariaDB; TLP and DQP on TiDB). |
name |
5.3 Comparison with Existing Tools page 28 |
| M15 | This is because that (1) SQLancer approaches may generate random joins with empty results which are not usable for testing and (2) TQS adopts the KQE to avoid repeatedly testing the same query structure. | name | 5.3 Comparison with Existing Tools page 28 |
| M16 | This is due to SQLancer occasionally generating random “Group By” clauses, which are often disorganized and invalid, rendering them ineffective for testing. | name | 5.3 Comparison with Existing Tools page 28 |
| M17 | Unique Logic Bugs Reported by TQS and SQLancer [ 5] DatabaseTQS SQLancer all bugs join bugs aggregation bugs all bugs join bugs aggregation bugs MySQL 13 9 4 5 4 0 MariaDB 8 5 3 7 6 0 TiDB 10 5 5 9 5 0 TOTAL 31 19 12 14 15 0 Table 8. | name | 5.3 Comparison with Existing Tools page 29 |
| M18 | Bug Reproduction of Logic Join Bugs Reported by TQS and SQLancer [ 5] DatabaseTQS SQLancer all bugs non-reproduced reproduced reproduced all bugs non-reproduced MySQL 9 7 2 4 2 MariaDB 5 1 4 6 2 TiDB 5 3 2 5 3 TOTAL 19 11 8 15 7 we only show bug types of the first 24 hours. | name | 5.3 Comparison with Existing Tools page 29 |
| M19 | Table7comparesthenumberofuniquebugsdetectedby TQS and SQLancer across three DBMSs: MySQL, MariaDB, and TiDB. | name | 5.3 Comparison with Existing Tools page 29 |
| M20 | As shown, TQS consistently detects more unique bugs than SQLancer. | name | 5.3 Comparison with Existing Tools page 29 |
| M21 | For example, TQS detects 13 unique bugs in MySQL compared to SQLancer’s 5. | name | 5.3 Comparison with Existing Tools page 29 |
| M22 | Notably, TQS also detects aggregation bugs, which SQLancer fails to identify, such as the 4 aggregation bugs in MySQL and 5 in TiDB. | name | 5.3 Comparison with Existing Tools page 29 |
| M23 | Furthermore, we present the comparison of join bugs detected by both TQS and SQLancer in Table8. | name | 5.3 Comparison with Existing Tools page 29 |
| M24 | Among these bugs, some are reproduced by both TQS and SQLancer. | name | 5.3 Comparison with Existing Tools page 29 |
| M25 | However, TQS also identifies several bugs that SQLancer does not reproduce. | name | 5.3 Comparison with Existing Tools page 29 |
| M26 | This comparison highlights that while both tools detect some of the same join bugs, TQS has a broader detection capability and is able to identify unique bugs that SQLancer fails to catch. | name | 5.3 Comparison with Existing Tools page 29 |
| M27 | The Reproduced Join Bug IDs Reported by TQS and SQLancer [ 5] Database BugIDs of SQLancer BugIDs of TQS MySQL112,243 106,715 112,264 109,211 MariaDB32,105 28,215 32,106 28,216 32,108 29,695 32,186 28,214 TiDB46,580 33,039 47,345 33,042 Table 10. | name | 5.3 Comparison with Existing Tools page 30 |
| M28 | 𝐺𝑇isequivalenttoDQP,asoutlinedin[ 5]. | citation marker | 5.4 Ablation Studies page 31 |
| M29 | While DQP claims to have uncovered 26 previously unidentified bugs, our analysis shows that most of these bugs closely resemble those already found by TQS(join). | technique | 5.4 Ablation Studies page 31 |
| M30 | Table8compares the join bugs detected by DQP with those from TQS(join), revealing that only 7 of the bugs are truly distinct. | technique | 5.4 Ablation Studies page 31 |
| M31 | SQLancer [ 51] is a current state-of-the-art tool in testing DBMS for logic bugs and is the most closely related work to ours. | name | 5.4 Ablation Studies page 32 |
| M32 | SQLancer proposes five approaches to detect logic bugs. | name | 5.4 Ablation Studies page 32 |
| M33 | PQS constructs queries to fetch a randomly selected tuple from a table [ 52]. | technique | 5.4 Ablation Studies page 32 |
| M34 | TLP decomposes a query into three partitioning queries, each of which computes its result on a selected tuple [ 50]. | technique | 5.4 Ablation Studies page 32 |
| M35 | NoRec compares the results of randomly-generated optimized queries and rewritten queries that DBMS cannot optimize [ 49]. | technique | 5.4 Ablation Studies page 32 |
| M36 | CERT aims at finding performance issues through unexpected estimated cardinalities, which represent the estimated number of returned rows [4]. | technique | 5.4 Ablation Studies page 32 |
| M37 | DQP aims at finding logic bugs in database systems by checking whether the query plans of the same query perform consistently [ 5]. | technique | 5.4 Ablation Studies page 32 |
| M38 | SQLancer uses differential testing as the core to test the logic bugs of databases. | name | 5.4 Ablation Studies page 32 |