  Database Management Systems (DBMS) are used ubiquitously. To efficiently
access data, they apply sophisticated optimizations. Incorrect optimizations
can result in logic bugs, which cause a query to compute an incorrect result
set. We propose Non-Optimizing Reference Engine Construction (NoREC), a
fully-automatic approach to detect optimization bugs in DBMS. Conceptually,
this approach aims to evaluate a query by an optimizing and a non-optimizing
version of a DBMS, to then detect differences in their returned result set,
which would indicate a bug in the DBMS. Obtaining a non-optimizing version of a
DBMS is challenging, because DBMS typically provide limited control over
optimizations. Our core insight is that a given, potentially randomly-generated
optimized query can be rewritten to one that the DBMS cannot optimize.
Evaluating this unoptimized query effectively corresponds to a non-optimizing
reference engine executing the original query. We evaluated NoREC in an
extensive testing campaign on four widely-used DBMS, namely PostgreSQL,
MariaDB, SQLite, and CockroachDB. We found 159 previously unknown bugs in the
latest versions of these systems, 141 of which have been fixed by the
developers. Of these, 51 were optimization bugs, while the remaining were error
and crash bugs. Our results suggest that NoREC is effective, general and
requires little implementation effort, which makes the technique widely
applicable in practice.
