DBStorm: Generating Various Effective Workloads for Testing Isolation Levels
Read the paper · doi:10.1145/3650212.3680318
What this paper does with SQLancer
SQLancer supplies DBStorm's SQL. The paper states that because SQLancer targets the relational model it is used to generate syntactically and semantically correct SQL operations, and that since SQLancer mainly produces serially executed operations they revised it to generate parallel ones. It is also one of the tools measured against, and the comparison makes the paper's point precisely: SQLsmith, SQLancer and Squirrel between them reveal 760 bugs of which none is an isolation bug, because they execute transactions sequentially in a single thread and so cannot produce a cycle in the conflict graph at all.
DBStorm generates workloads for testing isolation-level implementations. Its argument is that query-oriented tools only exercise the query engine, while existing transaction-oriented tools execute a few operations serially and so build sparse conflict graphs that never contain a cycle. DBStorm instead constructs workloads targeting chosen non-serializable anomalies, using conflict-graph isomorphism to avoid generating redundant ones. It found 20 isolation bugs and 13 others.
How it was classified
uses infrastructure — yes (generator)
M7 states DBStorm leverages SQLancer to generate syntactically and semantically correct SQL operations, and M8 that they revised it to emit parallel rather than serial operations. SQLancer is the operation generator inside DBStorm, not the framework it is built on -- the workload construction and conflict-graph analysis are the paper's own.
As SQLancer [60] targets for the relational model, we leverage it to generate syntax/semantic correct SQL operations.
Since SQLancer mainly generates serially executed operations, we revise it to generate parallel operations.
extends technique — no
The revision described in M8 is to SQLancer's operation generation so it can emit parallel operations, not to any of its test oracles. DBStorm's oracle is isolation-level checking over conflict graphs.
compares with — yes
M10 introduces SQLancer among the tools evaluated, M12 explains why it cannot produce a conflict-graph cycle, and M14 reports its bug count alongside SQLsmith's and Squirrel's, none of which is an isolation bug.
SQLancer [60] and TQS [67] randomly generate queries and provide a test oracle to identify logical bugs.
SQLancer ,Squrriel and SQLsmith sequentially execute transactions in a single thread, so it is impossible to exist a cycle in the conflict graph and we do not put them in Fig.
SQLsmith /SQLancer /Squirrel reveal 248/449/63 bugs, but none of them is an isolation bug.
describes as state of the art — no
SQLancer is described by what it generates and by the limits of single-threaded execution; no state-of-the-art claim is made.
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 |
|---|---|---|
| 19 | Jinsheng Ba and Manuel Rigger. 2023. Testing database engines via query plan guidance. In ICSE. 2060–2071. https://dl.acm.org/doi/10.1109/ICSE48619.2023. 00174 | sqlancer publication · QPG |
| 41 | Zu-Ming Jiang, Si Liu, Manuel Rigger, and Zhendong Su. 2023. Detecting transactional bugs in database engines via graph-based oracle construction. In OSDI. 397–417. https://www.usenix.org/conference/osdi23/presentatio... | project authored |
| 43 | Matteo Kamm, Manuel Rigger, Chengyu Zhang, and Zhendong Su. 2023. Testing graph database engines via query partitioning. In ISSTA. 140–149. https://dl.acm. org/doi/abs/10.1145/3597926.3598044 | project authored |
| 60 | Manuel Rigger and Zhendong Su. 2020. Testing database engines via pivoted query synthesis. In OSDI. 667–682. https://dl.acm.org/doi/abs/10.1145/2882903. 2882958 | sqlancer publication · PQS |
Every place it refers to SQLancer (17)
17 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 | Specifically, the query-oriented methods [ 60,63,67,78] generate carefully crafted queries to detect the bugs of query engines, thus they only trigger the code of query engine instead of the IL code. |
citation marker |
1 Introduction page 2 |
| M2 | The transactional-oriented methods [ 32,36,41] generate workloads where a small number of operations are serially executed, constructing sparse and small conflict graphs. |
citation marker project authored |
1 Introduction page 2 |
| M3 | Moreover, others [ 32,36,41] support complex SQL operations and predicates but lacks guidance for avoiding redundant or ineffective workloads. |
citation marker project authored |
1 Introduction page 2 |
| M4 | However, customizing non-serializable anomalies is still vacant in existing researches [19, 24, 32, 33, 36, 39, 43, 53, 57, 77]. |
citation marker |
1 Introduction page 2 |
| M5 | , SQLancer ,DT2). |
name |
3 DBStorm Framework page 4 |
| M6 | SQL operation generation has been extensively studied in [ 8,32,36,60,63,78]. |
citation marker |
3 DBStorm Framework page 4 |
| M7 | As SQLancer [60] targets for the relational model, we leverage it to generate syntax/semantic correct SQL operations. |
name |
3 DBStorm Framework page 4 |
| M8 | Since SQLancer mainly generates serially executed operations, we revise it to generate parallel operations. |
name |
3 DBStorm Framework page 4 |
| M9 | Previous studies [ 32,36,41] propose to sequentially execute all operations such that the order of execution can be effectively manifested, but they might overlook some parallelism-related bugs. |
citation marker project authored |
5.1 Conflict Graph Isomorphism Mapping page 7 |
| M10 | SQLancer [60] and TQS [67] randomly generate queries and provide a test oracle to identify logical bugs. |
name |
7 Experiments page 9 |
| M11 | SQLancer ensures queries access at least one record, but it also issues queries in a single-thread way. |
name |
7.1 IL-related Code Coverage page 9 |
| M12 | SQLancer ,Squrriel and SQLsmith sequentially execute transactions in a single thread, so it is impossible to exist a cycle in the conflict graph and we do not put them in Fig. |
name |
7.3 Anomaly-Sensitive Testing page 10 |
| M13 | 764 DBStorm: Generating Various Effective Workloads for Testing Isolation Levels ISSTA ’24, September 16–20, 2024, Vienna, Austria Table 2: Bug Comparison Total/Confirmed/Fixed DBStorm TxCheck Jepsen DT2 Isolation 20/12/6 7/6/0 22/21/13 4/2/1 Non-isolation 13/12/10 49/46/18 33/33/20 12/10/0 Total/Confirmed/Fixed Tro... |
name |
7.4 Bug Result page 10 |
| M14 | SQLsmith /SQLancer /Squirrel reveal 248/449/63 bugs, but none of them is an isolation bug. |
name |
7.4 Bug Result page 11 |
| M15 | TxCheck [41] constructs two semanticallyequivalent transactions with complex SQL queries, and compares their results to find bugs in transaction processing, including those in the query optimizer, query execution engine, and IL implementations. |
citation marker project authored |
8 Discussion page 11 |
| M16 | The bugs that have been discovered can be classified into logical bugs [ 21,49,60,63], performance bugs [ 42,51,58], and crash bugs [ 8,69,78]. |
citation marker |
8 Discussion page 11 |
| M17 | SQLancer [60] creates a query that would fetch a target data to detect logical bug. |
name |
8 Discussion page 11 |