  Database Management Systems (DBMSs) process a given query by creating a query
plan, which is subsequently executed, to compute the query's result. Deriving
an efficient query plan is challenging, and both academia and industry have
invested decades into researching query optimization. Despite this, DBMSs are
prone to performance issues, where a DBMS produces an unexpectedly inefficient
query plan that might lead to the slow execution of a query. Finding such
issues is a longstanding problem and inherently difficult, because no ground
truth information on an expected execution time exists. In this work, we
propose Cardinality Estimation Restriction Testing (CERT), a novel technique
that finds performance issues through the lens of cardinality estimation. Given
a query on a database, CERT derives a more restrictive query (e.g., by
replacing a LEFT JOIN with an INNER JOIN), whose estimated number of rows
should not exceed the estimated number of rows for the original query. CERT
tests cardinality estimation specifically, because they were shown to be the
most important part for query optimization; thus, we expect that finding and
fixing such issues might result in the highest performance gains. In addition,
we found that other kinds of query optimization issues can be exposed by
unexpected estimated cardinalities, which can also be found by CERT. CERT is a
black-box technique that does not require access to the source code; DBMSs
expose query plans via the EXPLAIN statement. CERT eschews executing queries,
which is costly and prone to performance fluctuations. We evaluated CERT on
three widely used and mature DBMSs, MySQL, TiDB, and CockroachDB. CERT found 13
unique issues, of which 2 issues were fixed and 9 confirmed by the developers.
We expect that this new angle on finding performance bugs will help DBMS
developers in improving DMBSs' performance.
