Finding Bugs in Database Systems via Query Partitioning
Reviewed by Greg Wilson / 2021-10-07
Keywords: Databases, Debugging
Rigger2020 describes one of the coolest practical innovations I've seen in a long time. Starting from an original query, they automatically generate several more complex queries, each of which is guaranteed to produce a disjoint subset of the original's output. They then compare the union of those subsets with the original query's result; if they differ, there's a bug in the database's query processor.
As a concrete example, they use the fact that boolean conditions in SQL can produce true, false, or null. The result? "…we found 175 bugs in widely-used DBMSs such as MySQL, TiDB, SQLite, and CockroachDB, 125 of which have been fixed. Notably, 77 of these were logic bugs, while the remaining were error and crash bugs." I would really like to see someone replicate this work for pipelines written in the tidyverse and Pandas; any takers?
Rigger2020 Manuel Rigger and Zhendong Su: "Finding bugs in database systems via query partitioning". Proceedings of the ACM on Programming Languages, 4, 2020, 10.1145/3428279.
Logic bugs in Database Management Systems (DBMSs) are bugs that cause an incorrect result for a given query, for example, by omitting a row that should be fetched. These bugs are critical, since they are likely to go unnoticed by users. We propose Query Partitioning, a general and effective approach for finding logic bugs in DBMSs. The core idea of Query Partitioning is to, starting from a given original query, derive multiple, more complex queries (called partitioning queries), each of which computes a partition of the result. The individual partitions are then composed to compute a result set that must be equivalent to the original query's result set. A bug in the DBMS is detected when these result sets differ. Our intuition is that due to the increased complexity, the partitioning queries are more likely to stress the DBMS and trigger a logic bug than the original query. As a concrete instance of a partitioning strategy, we propose Ternary Logic Partitioning (TLP), which is based on the observation that a boolean predicate p can either evaluate to TRUE, FALSE, or NULL. Accordingly, a query can be decomposed into three partitioning queries, each of which computes its result on rows or intermediate results for which p, NOT p, and p IS NULL hold. This technique is versatile, and can be used to test WHERE, GROUP BY, as well as HAVING clauses, aggregate functions, and DISTINCT queries. As part of an extensive testing campaign, we found 175 bugs in widely-used DBMSs such as MySQL, TiDB, SQLite, and CockroachDB, 125 of which have been fixed. Notably, 77 of these were logic bugs, while the remaining were error and crash bugs. We expect that the effectiveness and wide applicability of Query Partitioning will lead to its broad adoption in practice, and the formulation of additional partitioning strategies.