Automatic Detection of Performance Bugs in Database Systems using Equivalent Queries
Read the paper · doi:10.1145/3510003.3510093
What this paper does with SQLancer
TLP is one of AMOEBA's three baselines and the paper calls it the state-of-the-art tool for finding logic bugs in DBMSs using metamorphic testing. Because TLP also produces equivalent queries, it can be repurposed as a source of pairs, and the authors built a baseline of 2000 TLP-generated pairs to test that. The finding is a clean negative result about transfer: TLP's mutation rules were not designed for performance, and its mutant queries are on average 17 times slower than their base query, so that inherent overhead swamps the signal a performance oracle depends on. AMOEBA found 25 and 14 bugs against the TLP benchmark's 1 and 1.
AMOEBA finds performance bugs by generating pairs of semantically equivalent queries and reporting when a DBMS executes one far more slowly than the other, since equivalent queries should cost about the same. It applies structural and expression mutation rules designed so the pairs stay comparable in cost. On CockroachDB and PostgreSQL it found substantially more potential performance bugs than either a hand-written optimiser test suite or an equivalence source drawn from TLP.
How it was classified
uses infrastructure — no
TLP's construction is reimplemented to produce a baseline set of equivalent query pairs; the paper does not describe AMOEBA as built on the SQLancer codebase.
extends technique — no
AMOEBA's mutation rules are its own and are designed for cost-comparability, which M10 contrasts with TLP's. Using TLP as one source of equivalent pairs to measure against is comparison, not extension.
compares with — yes
M2 and M5 name TLP as one of the equivalent-query sources AMOEBA is compared against, M9 records the 2000-pair baseline built from it, and M13 reports that AMOEBA found considerably more performance bugs than the TLP-based baseline.
Ternary Logic Partitioning (TLP)
We also compared AMOEBA against two other sources of equivalent queries that could be used for detecting performance bugs: a manually-written test suite in a widely-used query optimization framework, and the Ternary Logic Partitioning (TLP) approach [ 38].
To answer Q4, we compare AMOEBA to three baseline based on two of these existing approaches: Calcite [19, 48] and TLP [38].
Our first baseline consists of 2000 pairs of equivlent queries generated using TLP.
For both DBMSs considered, AMOEBA discovered considerably more PPBs than the baselines based on Calcite and TLP.
describes as state of the art — yes
M14 states that TLP is the state-of-the-art tool for discovering logic bugs in DBMSs using metamorphic testing.
TLP is the state-of-the-art tool for discovering logic bugs in DBMS using metamorphic testing [ 38].
SQLancer publications it cites (3)
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 |
|---|---|---|
| 37 | Manuel Rigger and Zhendong Su. 2020. Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction. In FSE. | sqlancer publication · NOREC |
| 38 | Manuel Rigger and Zhendong Su. 2020. Finding Bugs in Database Systems via Query Partitioning. In OOPSLA. | sqlancer publication · TLP |
| 39 | Manuel Rigger and Zhendong Su. 2020. Testing Database Engines via Pivoted Query Synthesis. In OSDI. | sqlancer publication · PQS |
Every place it refers to SQLancer (15)
15 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 | For instance, they leverage tools such as SQLSMITH [4] and SQLancer [37–39] to discover crash-inducing or logic bugs in DBMSs. |
name |
page 1 |
| M2 | We also compared AMOEBA against two other sources of equivalent queries that could be used for detecting performance bugs: a manually-written test suite in a widely-used query optimization framework, and the Ternary Logic Partitioning (TLP) approach [ 38]. |
technique |
page 2 |
| M3 | Query equivalence is a well-studied topic used in many applications, such as testing DBMSs for correctness [ 38,40], educating developers [ 27], and automatically grading student assignments [ 16]. |
citation marker |
page 3 |
| M4 | BenchmarkPPBs Found Cockroach PostgreSQL Benchmark 1 (TLP) 1 1 Benchmark 2 (Calcite) 4 4 Benchmark 3 (Calcite+AMOEBA )4 6 AMOEBA 25 14 Both structural and expression mutation rules generate queries thatcan reveal PPBs. |
technique |
page 9 |
| M5 | To answer Q4, we compare AMOEBA to three baseline based on two of these existing approaches: Calcite [19, 48] and TLP [38]. |
technique |
page 9 |
| M6 | TLP [ 38] construct equivalent queries to discover logic bugs in DBMSs. |
technique |
page 9 |
| M7 | It is based on the observation that any predicate in SQL evaluates to TRUE, FALSE, or NULL [ 38]. |
citation marker |
page 9 |
| M8 | Accordingly, TLP constructs a mutant query that is equivalent to the base query by (1) dividing the basequery into three partition queries, wherein each predicate is constructed based on the value of the overall base query’s predicate and (2) concatenating these partition queries using the UNION operator. |
technique |
page 9 |
| M9 | Our first baseline consists of 2000 pairs of equivlent queries generated using TLP. |
technique |
page 9 |
| M10 | TLP uses a different set of mutation rules than AMOEBA for generating equivalent queries, which were not designed to detect performance bugs. |
technique |
page 10 |
| M11 | The queries mutated by TLP consistently take longer to execute than their corresponding base query, with an average slow-down of 17 ×. |
technique |
page 10 |
| M12 | Given this inherent overhead, TLP is limited in the kinds and number of PPBs it can find. |
technique |
page 10 |
| M13 | For both DBMSs considered, AMOEBA discovered considerably more PPBs than the baselines based on Calcite and TLP. |
technique |
page 10 |
| M14 | TLP is the state-of-the-art tool for discovering logic bugs in DBMS using metamorphic testing [ 38]. |
technique |
page 11 |
| M15 | 6, TLP is not suitable for discoveringperformance bugs. |
technique |
page 11 |