Finding Missed Optimizations in DBMSs through Unbalanced Short-circuit Query Construction

Jinhui Lai, Chi Zhang, Jie Liang, Zihao Zeng, Zhiyong Wu, Jingzhou Fu, Chijin Zhou, Shuai Ma, Yu Jiang, Zichen Xu. 2026. Proceedings of the ACM on Management of Data.

Read the paper · doi:10.1145/3802061

What this paper does with SQLancer

CERT is SCor's most direct comparison, one of five performance-bug detection tools it is measured against and described as tackling performance bugs through cardinality estimation analysis. SCor found 36 more bugs than CERT, and the paper gives a precise account of the difference in reach: CERT cannot detect optimization opportunities that persist despite correct cardinality estimates, which is exactly the class short-circuit construction targets. SQLancer also appears as a data-generation source the paper declines to reimplement, listing it among the existing methods available for producing test data. SCor finds missed optimizations by constructing unbalanced short-circuit queries: a predicate is written so that one branch could be short-circuited away, and if the optimizer fails to exploit that the query does measurably more work than it needs to. Unlike approaches that observe a performance anomaly and leave its cause open, this points at the specific optimization the optimizer missed. It found 69 issues across five DBMSs. Written by claude-opus-5 from the 14 places this paper refers to SQLancer. The quotations below are the paper's own words, stored verbatim when the text was extracted.

How it was classified

uses infrastructure — no

M5 lists SQLancer among existing data generation methods as the reason SCor does not reimplement data generation, but does not say SCor uses it. Which generator supplies its data is left open, so this falls short of a statement of reuse.

extends technique — no

Unbalanced short-circuit construction is a different mechanism from cardinality-estimation restriction, and M11 sets out the class of issues CERT cannot reach as the motivation.

compares with — yes

M6 names CERT among the five tools SCor is compared with, M8 reports SCor finding 36 more bugs than CERT, and M9 gives the per-DBMS table.

Cardinality Estimation Restriction Testing (CERT)

We compared SCor with five state-of-the-art DBMS performance bug detection tools, including: APOLLO [ 18], AMOEBA [ 24], and CERT [ 1], Puppy [ 54], and HULK [ 55]. M6 · 5.4 Comparative Evaluation · page 19

The results show that SCor found 24, 8, 36, 8, and 4 more bugs than APOLLO, AMOEBA, CERT, Puppy, and HULK, respectively. M8 · 5.4 Comparative Evaluation · page 19

DBMSAPOLLO AMOEBA CERT Puppy HULK SCor PostgreSQL 0 0 - 2 2 3 MySQL - - 3 6 10 13 CockroachDB-1 2 - - 6 TiDB - - 4 - - 26 SQLite 0 - - - - 21 Total 0 1 9 8 12 69 Increment 24↑8↑36↑8↑4↑data-sensitive performance anomalies through data changes, while SCor employs unbalanced shortcircuit queries. M9 · 5.4 Comparative Evaluation · page 20

describes as state of the art — yes

M6 describes the five comparison tools, CERT among them, as state-of-the-art DBMS performance bug detection tools.

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
1	Jinsheng Ba and Manuel Rigger. 2024. CERT: Finding Performance Issues in Database Systems Through the Lens of Cardinality Estimation. InProceedings of the IEEE/ACM 46th International Conference on Software Engineering...	sqlancer publication · CERT
42	Manuel Rigger and Zhendong Su. 2020. Detecting optimization bugs in database engines via non-optimizing reference engine construction. InProceedings of the 28th ACM Joint Meeting on European Software Engineering Confe...	sqlancer publication · NOREC
43	Manuel Rigger and Zhendong Su. 2020. Finding bugs in database systems via query partitioning.Proc. ACM Program. Lang.4, OOPSLA, Article 211 (nov 2020), 30 pages. doi:10.1145/3428279	sqlancer publication · TLP
44	Manuel Rigger and Zhendong Su. 2020. Testing Database Engines via Pivoted Query Synthesis. In14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). USENIX Association, 667–682. https:// www.us...	sqlancer publication · PQS

Every place it refers to SQLancer (14)

14 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	Some automated testing approaches have been widely adopted to detect performance issues for DBMSs [ 1,18,23,24,54,55].	citation marker background	1 Introduction page 2
M2	CERT [ 1] focuses on cardinality estimation by deriving restrictive queries to identify estimation errors that may affect optimization.	technique definition	1 Introduction page 2
M3	Detecting these missed optimizations remains challenging, as existing approaches [ 1,18,23,24,54,55] typically observe performance anomalies without revealing where the optimizer fails.	citation marker motivation	2 Background page 4
M4	Metamorphic testing [ 1] addresses this by constructing oracles through relations between inputs and outputs.	citation marker background	2 Background page 4
M5	Finding Missed Optimizations in DBMSs through Unbalanced Short-Circuit Query Construction 184:13 Given the wide array of existing data generation methods—such as testing benchmarks, TPCH [52], automated testing tools like SQLancer [ 42–44], and built-in DBMS functions [ 41]—SCor does not reimplement data generation.	name incidental	4 Implementation page 12
M6	We compared SCor with five state-of-the-art DBMS performance bug detection tools, including: APOLLO [ 18], AMOEBA [ 24], and CERT [ 1], Puppy [ 54], and HULK [ 55].	technique state of the art	5.4 Comparative Evaluation page 19
M7	CERT tackles performance bugs through cardinality estimation analysis.	technique definition	5.4 Comparative Evaluation page 19
M8	The results show that SCor found 24, 8, 36, 8, and 4 more bugs than APOLLO, AMOEBA, CERT, Puppy, and HULK, respectively.	technique result comparison	5.4 Comparative Evaluation page 19
M9	DBMSAPOLLO AMOEBA CERT Puppy HULK SCor PostgreSQL 0 0 - 2 2 3 MySQL - - 3 6 10 13 CockroachDB-1 2 - - 6 TiDB - - 4 - - 26 SQLite 0 - - - - 21 Total 0 1 9 8 12 69 Increment 24↑8↑36↑8↑4↑data-sensitive performance anomalies through data changes, while SCor employs unbalanced shortcircuit queries.	technique result comparison	5.4 Comparative Evaluation page 20
M10	Specifically, APOLLO targets performance regression bugs, AMOEBA focuses on performance differences among semantically equivalent queries, CERT addresses cardinality estimation issues, PUPPY identifies configuration-related problems, and HULK detects data-sensitive anomalies.	technique definition	5.4 Comparative Evaluation page 20
M11	CERT cannot detect opportunities that persist despite correct cardinality estimates.	technique motivation	5.4 Comparative Evaluation page 20
M12	CERT [ 1] tackles performance bugs through cardinality estimation analysis.	technique definition	7 Related Work page 21
M13	The recent application of fuzzing to DBMSs has successfully uncovered hundreds of bugs [ 19,22,42–44,46,56].	citation marker background	7 Related Work page 22
M14	Similarly, SQLancer uses a generation-based approach guided by its test oracles (PQS [ 44], NoREC [ 42], TLP [ 43], and SRS [ 19]) to detect logic bugs.	name definition	7 Related Work page 22

This page is rendered from _data/papers/paper_doi_10_1145_3802061.json, extracted from supplied pdf. 24 pages, 56 references parsed.