Detecting Logic Bugs of Join Optimizations in DBMS
Read the paper · doi:10.1145/3588909 · arXiv:2602.21955
What this paper does with SQLancer
SQLancer is the work TQS is built against and the paper says so directly, calling it the current state-of-the-art tool for finding logic bugs in DBMSs and the most closely related work to its own. All three of its oracles serve as baselines -- PQS, TLP and NoREC -- and the paper is careful about the comparison's mechanics, noting that SQLancer supports different oracles on different systems and that its generated joins often return empty results and so cannot be used for testing. The gap TQS identifies is single-table scope: SQLancer is not designed to test multi-table queries, which is exactly where join-optimisation bugs live.
TQS targets logic bugs in join optimisation, which earlier oracles largely miss: PQS is designed for selection over a single table, and 90% of the bugs it reported involve one table only. TQS generates a schema and data together so that the correct result of a multi-table join is known by construction, then uses a knowledge-guided query enumerator to avoid re-testing equivalent query shapes. It found bugs in MySQL, MariaDB, TiDB and others.
How it was classified
uses infrastructure — no
The three oracles are run as baselines. Nothing states that TQS's own schema-and-data generation or its query enumerator is built on the SQLancer codebase.
extends technique — no
TQS constructs the schema and data so a join's correct result is known in advance, which is a different oracle from PQS, TLP or NoREC rather than a generalisation of one. Its relationship to them is that it covers the multi-table case they do not.
compares with — yes
M7 states that three methods in SQLancer are used as baselines, M13 records which oracle was run against which system, and M14 explains a difference in the measured outcome.
Pivoted Query Synthesis (PQS)Ternary Logic Partitioning (TLP)Non-optimizing Reference Engine Construction (NoREC)
We use three methods in SQLancer as our baselines.
Note that due to the compatibility problem, SQLancer implements different approaches on different databases (PQS and TLP on MySQL and X-DB; NoRec on MariaDB; TLP on TiDB).
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.
describes as state of the art — yes
M15 calls SQLancer a current state-of-the-art tool in testing DBMSs for logic bugs and the work most closely related to this one.
SQLancer [ 49] is a current stateof-the-art tool in testing DBMS for logic bugs and is the most closely related work to ours.
SQLancer publications it cites (4)
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 |
|---|---|---|
| 47 | Manuel Rigger and Zhendong Su. 2020. Detecting optimization bugs in database engines via non-optimizing reference engine construction. InACM Joint Meeting on ESEC and FSE. 1140–1152. | sqlancer publication · NOREC |
| 48 | Manuel Rigger and Zhendong Su. 2020. Finding bugs in database systems via query partitioning.Proceedings of the ACM on Programming Languages4, OOPSLA (2020), 1–30. | sqlancer publication · TLP |
| 49 | Manuel Rigger and Zhendong Su. 2020. SQLancer. [EB/OL]. https://github.com/ sqlancer/sqlancer. | sqlancer publication |
| 50 | Manuel Rigger and Zhendong Su. 2020. Testing database engines via pivoted query synthesis. InOSDI 20. 667–682. | sqlancer publication · PQS |
Every place it refers to SQLancer (20)
20 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 | Pivoted Query Synthesis (PQS) has recently emerged as a promising way to detect logic bugs in DBMS [ 50]. |
technique |
1 Introduction page 1 |
| M2 | PQS is mainly designed to support selection queries in a single table and90%of its reported bugs are for queries involving only one table. |
technique |
1 Introduction page 1 |
| M3 | 3 Data-guided Schema and Query Generation (DSG) SQLancer [ 49] is a tool to automatically find logic bugs in the implementation of DBMS. |
name |
2.2 Scheme Overview page 3 |
| M4 | Based on the randomly generated database, it adopts testing approaches such as Pivoted Query Synthesis (PQS) [ 50] to detect logic bugs. |
technique |
2.2 Scheme Overview page 3 |
| M5 | Note that SQLancer Conference acronym ’XX, June 03–05, 2023, Woodstock, NY Xiu Tang, et al. |
name |
2.2 Scheme Overview page 3 |
| M6 | SQLancer is not designed to test multi-table queries. |
name |
3.4 Ground-truth Result Generation page 8 |
| M7 | We use three methods in SQLancer as our baselines. |
name |
3.4 Ground-truth Result Generation page 8 |
| M8 | The first one is PQS [ 50], which constructs queries to fetch a randomly selected tuple from a table. |
technique |
3.4 Ground-truth Result Generation page 8 |
| M9 | The second one is TLP [ 50], which decomposes a query into three partitioning queries, each of which computes its result on that tuple. |
technique |
3.4 Ground-truth Result Generation page 8 |
| M10 | The third one is NoRec [ 47], which targets at logic bugs generated by the optimization process in DBMS. |
technique |
3.4 Ground-truth Result Generation page 8 |
| M11 | com/sqlancer/sqlancer Detecting Logic Bugs of Join Optimizations in DBMS Conference acronym ’XX, June 03–05, 2023, Woodstock, NY Table 3: We tested a diverse set of popular and emerging DBMS. |
name |
5.1 Overview and Showcase of Bug Reports page 8 |
| M12 | The paper sets this passage with letter-spacing, which extraction cannot undo — the sentence is there, but no readable form of it is. |
technique |
5.1.3 Bugs in TiDB.Merge join and join index are the main causes page 10 |
| M13 | Note that due to the compatibility problem, SQLancer implements different approaches on different databases (PQS and TLP on MySQL and X-DB; NoRec on MariaDB; TLP on TiDB). |
name |
5.2 Comparison with Existing Tools page 12 |
| M14 | 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.2 Comparison with Existing Tools page 12 |
| M15 | SQLancer [ 49] is a current stateof-the-art tool in testing DBMS for logic bugs and is the most closely related work to ours. |
name |
5.3 Ablation Studies page 13 |
| M16 | SQLancer proposes three approaches to detect logic bugs. |
name |
5.3 Ablation Studies page 13 |
| M17 | PQS constructs queries to fetch a randomly selected tuple from a table [ 50]. |
technique |
5.3 Ablation Studies page 13 |
| M18 | TLP decomposes a query into three partitioning queries, each of which computes its result on a selected tuple [ 48]. |
technique |
5.3 Ablation Studies page 13 |
| M19 | NoRec compares the results of randomly-generated optimized queries and rewritten queries that DBMS cannot optimize [47]. |
technique |
5.3 Ablation Studies page 13 |
| M20 | SQLancer targets at single table queries and 90. |
name |
5.3 Ablation Studies page 13 |