Testing DBMS Performance with Mutations
Read the paper · arXiv:2105.10016
What this paper does with SQLancer
AMOEBA takes TLP as the closest related effort and argues it does not transfer: its equivalent queries are tailored to logic bugs and are comparatively simple, so they cannot serve as a metamorphic relation for performance. TLP is then one of the sources of equivalent queries AMOEBA is compared against.
AMOEBA detects performance bugs in database systems, a class the authors note has received far less attention than functional bugs despite affecting response time. It constructs pairs of semantically equivalent queries and compares their response times on the same system; a significant difference points to a performance bug. The paper contributes structure and predicate mutation rules for building such pairs, plus feedback mechanisms to improve efficacy. On PostgreSQL and CockroachDB it found 20 previously unknown performance bugs, 14 confirmed.
How it was classified
uses infrastructure — no
Nothing shown says AMOEBA is built on SQLancer; the tools are named as the means by which others find crash and logic bugs.
extends technique — uncertain
AMOEBA applies the equivalent-query idea to performance rather than correctness, which is arguably a generalisation, but the mentions read frame TLP as an approach that does not transfer rather than one being extended.
compares with — yes
M5 states AMOEBA is compared against two other sources of equivalent queries, TLP among them.
Ternary Logic Partitioning (TLP)
We compare AMOEBA against two other sources of equivalent queries that could be used for detecting performance bugs: (1) a manually-written test suite in a widely-used query optimization framework, and (2) the TLP.
describes as state of the art — uncertain
A pattern fired on M25, which was outside the mentions read here.
What could not be determined
- Whether the paper calls SQLancer the state of the art: the mention a pattern fired on, M25, was not among those read.
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 |
|---|---|---|
| 35 | Manuel Rigger and Zhendong Su. 2020. Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction. In FSE. | sqlancer publication · NOREC |
| 36 | Manuel Rigger and Zhendong Su. 2020. Finding Bugs in Database Systems via Query Partitioning. In OOPSLA. | sqlancer publication · TLP |
| 37 | Manuel Rigger and Zhendong Su. 2020. Testing Database Engines via Pivoted Query Synthesis. In OSDI. | sqlancer publication · PQS |
Every place it refers to SQLancer (28)
28 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 | They leverage tools such as SQLSMITH [4] and SQLancer [35– 37] to discover crash-inducing or logic bugs in DBMSs. |
name |
page 1 |
| M2 | Recently, researchers have proposed Ternary Logic Partitioning (TLP), a technique that applies metamorphic testing for detecting logic bugs in the DBMS [ 36]. |
technique |
page 1 |
| M3 | As a result, it is difficult to construct a metamorphic relation that is tailored for detecting performance bugs based on equivalent queries generated by TLP. |
technique |
page 1 |
| M4 | In addition, TLP targets on comparatively simple queries that are tailored for uncovering logic bugs. |
technique |
page 1 |
| M5 | We compare AMOEBA against two other sources of equivalent queries that could be used for detecting performance bugs: (1) a manually-written test suite in a widely-used query optimization framework, and (2) the TLP. |
technique |
page 2 |
| M6 | Query equivalence is a well-studied topic and is used in many applications: (1) testing correctness of DBMS and SQL queries [ 36,38], (2) educating developers [ 25], and (3) automatically grading student assignments [ 14]. |
citation marker |
page 2 |
| M7 | Notably, SQLancer is a system that constructs equivalent queries for discovering logic bugs in DBMSs. | name | page 4 |
| M8 | In particular, it generates equivalent queries using TLP [ 36]. | technique | page 4 |
| M9 | We defer a comparative analysis of AMOEBA against SQLancer to §8. | name | page 4 |
| M10 | We now investigate the efficacy of two techniques for obtaining equivalent query pairs for performance bug detection: (1) using SQLancer, an automated DBMS testing technique, to generate random query pairs (§8. | name | page 10 |
| M11 | 1 Query Pairs from SQLancer SQLancer is the state-ofart tool for discovering logic bugs [ 35–37]. | name | page 10 |
| M12 | A key technique in SQLancer is using TLP to construct equivalent queries based on the observation that any predicate in SQL evaluates to TRUE ,FALSE, or NULL. | name | page 10 |
| M13 | Given a base query, TLP constructs a mutant query that is equivalent to the base query in two steps. | technique | page 10 |
| M14 | TLP constructs the mutant query by concatenating these partition queries with the UNION ALL operator. | technique | page 10 |
| M15 | This human-intensive baseline is challenging because: (1) they coverBase Query Mutant QueryPerformance Bugs Found Cockroach PostgreSQL SQLancer SQLancer 0 0 Calcite Test Calcite Test 4 4 Calcite Test AMOEBA 4 6 AMOEBA AMOEBA 25 14 Table 4: Comparative Analysis of AMOEBA –The results include the number of performance... | name | page 10 |
| M16 | 3 Results As shown in Table 4, we compare AMOEBA against three baselines: (1) We use SQLancer to randomly generate 2000 pairs of equivalent queries. | name | page 10 |
| M17 | The query pairs generated by the SQLancer reveal zero performance bugs. | name | page 10 |
| M18 | SQLancer differs from AMOEBA in that it mutates queries using TLP. | name | page 10 |
| M19 | We find that TLP is not useful for detecting performance bugs. | technique | page 10 |
| M20 | By design, the TLP query is more complex than the corresponding base query, which inevitably leads to a higher execution time. | technique | page 10 |
| M21 | Among these queries, we find that the TLP query always takes more time to execute compared to the base query (with an average slow-down of 17×). | technique | page 10 |
| M22 | The root cause of these performance differences is that the TLP query forces the DBMS to perform additional operations (i. | technique | page 10 |
| M23 | Given this inherent overhead, TLP is not able to find a variety of performance bugs, which are discovered by AMOEBA and Calcite’s test suite. | technique | page 10 |
| M24 | AMOEBA outperforms SQLancer andCalcite for three reasons: (1) AMOEBA differs from SQLancer in that it leverages a variety of optimization rules to mutate the base query, which are more likely to trigger different runtime behaviors that expose performance bugs; (2) Compared with Calcite ,AMOEBA broadly explores the e... | name | page 11 |
| M25 | SQLancer is the state-of-the-art tool for discovering logic bugs in DBMS using metamorphic testing [ 35–37]. | name | page 12 |
| M26 | The key idea behind SQLancer is to construct a metamorphic relation that is used to generate a cross-referencing oracle for detecting logic bugs. | name | page 12 |
| M27 | AMOEBA is similar to SQLancer in that it uses semantics-preserving query mutation rules to establish a metamorphic relation for discovering performance bugs. | name | page 12 |
| M28 | 6, while the metamorphic relation proposed in SQLancer is effective in detecting logic bugs in DBMS, it is not suitable for discovering performance bugs. | name | page 12 |