PaperlayerView exact revision on arXiv

Source-linked AI summary

Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction

Manuel Rigger, Zhendong Su

arXiv:2007.08292v1cs.SEcs.DB

TL;DR

Incorrect query optimizations can make DBMS return wrong result sets, while obtaining a non-optimizing reference engine is difficult. NoREC rewrites optimized queries into less-optimizable forms and compares their results; testing found 159 true bugs, including 51 optimization bugs.

  • Problem

    DBMS optimizer implementation errors can produce incorrect result sets, but existing controls provide limited, DBMS-specific ways to disable optimizations.

  • Method

    NoREC transforms a query that may be optimized into another query that cannot be effectively optimized, then compares their result sets to detect optimization bugs.

  • Results

    159 true bugs were found, including 51 optimization bugs, while developers fixed 141 of the 159 bugs.

  • Takeaways & Limitations

    NoREC provides a general foundation for DBMS correctness testing, with additional query-translation strategies as a possible extension.

  • Takeaways & Limitations

    Subqueries were disabled because ambiguous subquery results could differ between optimized and unoptimized queries.

Abstract

from arXiv · show

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.

1 INTRODUCTION

NoREC detects DBMS optimization bugs by comparing an optimized query with an automatically rewritten unoptimized query, and its evaluation found 159 previously unknown bugs across four widely-used systems.

  • 1 INTRODUCTION: NoREC rewrites a query’s WHERE predicate into a form evaluated on every table record, creating an unoptimized reference for comparison.A mismatch between the optimized and unoptimized results indicates a DBMS bug.
  • 1 INTRODUCTION: The approach addresses the difficulty of obtaining a non-optimizing DBMS version because optimization controls are limited and adding them retrospectively is impractical.The translation is intended to preserve the original result while making optimizations inapplicable.
  • 1 INTRODUCTION: An SQLite LIKE optimization bug omitted a matching row, while the translated query correctly evaluated the predicate for that row.The example moves the predicate next to SELECT, preventing the optimization from skipping the record.
  • 1 INTRODUCTION: 159 previously unknown bugs were found across SQLite, MariaDB, PostgreSQL, and CockroachDB during an extensive testing campaign.The reported bugs included optimization, crash, assertion-failure, and error bugs.
  • 1 INTRODUCTION: The paper contributes the NoREC test oracle, its SQLancer implementation, and an extensive evaluation uncovering more than 150 new DBMS bugs.These contributions target effective testing with low implementation effort.

2 BACKGROUND

DBMS testing needs effective test oracles because optimization and dialect differences complicate correctness checking; NoREC compares optimized and unoptimized query executions within one DBMS.

  • 2 BACKGROUND: Automatic DBMS testing requires both effective test cases and a test oracle that detects whether execution produced the expected result.Existing database and query generators address test-case creation, while test oracles have received less attention.
  • 2 BACKGROUND: DBMS query optimizers simplify queries and select efficient physical access paths, making optimization a major source of performance and correctness complexity.Optimization gains primarily come from determining how records can be fetched efficiently.
  • 2 BACKGROUND: NoREC instead transforms an optimized query into one that cannot be effectively optimized, enabling within-DBMS result comparison without requiring another SQL engine.The translation cannot guarantee that all optimizations are absent, but it was widely applicable in practice.
  • 2 BACKGROUND: Differential testing compares outputs from multiple systems, but DBMS dialect and semantic differences make it difficult to construct queries that execute identically.CockroachDB developers specifically described PostgreSQL as insufficiently interchangeable as a correctness oracle.
  • 2 BACKGROUND: Disabling DBMS optimizations directly is generally infeasible because most systems provide limited runtime control over their optimizers.This motivates query rewriting as an alternative to optimizer configuration.

3 APPROACH

NoREC transforms an optimized query into an effectively unoptimized query and compares their cardinalities to detect optimization bugs. The approach extends across joins and multiple tables but has documented limitations for ambiguous, nondeterministic, error-sensitive, and multi-record queries.

  • Approach Overview: NoREC detects optimization bugs by comparing an optimized query’s result cardinality with TRUE evaluations from a translated unoptimized query.The translation moves the predicate after SELECT, forcing evaluation on every row; a cardinality mismatch indicates a bug.
  • Translating the Query: The automatic translation replaces a WHERE predicate with a post-SELECT boolean expression, while preserving support for multiple tables and join clauses.Join clauses can be copied during translation, and multiple-table queries apply without modification.
  • Determining the Row Count: NoREC may miss incorrect result sets with correct cardinalities, although the authors report that such bugs were unlikely in their empirical evidence.The method validates cardinalities rather than comparing complete result contents.
  • Corner Cases and Limitations: The approach disables nondeterministic functions and subquery generation to avoid mismatches caused by ambiguous or unstable query behavior.Nondeterministic functions can produce different results between executions, while ambiguous subqueries were especially problematic in testing.
  • Corner Cases and Limitations: NoREC cannot detect optimization bugs involving prevented errors from short-circuit evaluation because SQL does not specify whether AND and OR must short-circuit.The method also does not directly apply to DISTINCT, aggregate, or window-function queries, though the authors suggest extending the translation idea.
  • Corner Cases and Limitations: SQLite-specific handling is required for configuration-setting input columns and ambiguous GROUP BYs, while some corner cases remain unaddressed because they were rare.The dbstat extension required avoiding predicates on a specific column, and ambiguous GROUP BYs in views were not handled in SQLancer.

4 EVALUATION

NoREC was evaluated through a five-month campaign on four widely used DBMS, uncovering 159 previously unknown bugs, including optimization, crash, assertion, and error bugs. The evaluation also examined representative failures and differences across systems and testing oracles.

  • Selected bugs: The campaign exposed concrete optimizer errors, including omitted rows from SQLite index handling, incorrect CockroachDB joins and filters, and MariaDB range-scan and numeric-comparison failures.The examples involve lost records, incorrect fetched records, or an incorrect result from indexed comparisons.
  • Bug overview: 51 bugs were found with the NoREC oracle, alongside 58 unexpected-error bugs, 27 debug assertion failures, and 23 release-build crashes.These categories summarize the principal bug-finding oracles used in the evaluation.
  • Additional clauses: Adding ORDER BY and GROUP BY found only three additional bugs overall, although implementing both clauses required little effort.The evaluation found one logic bug and one crash bug with ORDER BY, plus one error bug with GROUP BY.
  • SQLite: SQLite yielded 110 bugs, including 71 in its core, 13 in RTREE, 24 in FTS, and 2 in DBSTAT.The campaign also found 22 bugs in newly added generated-column support and 26 debug assertion failures.
  • PostgreSQL: PostgreSQL yielded only 8 bugs, none of them optimization bugs, consistent with its restrictive input acceptance and elaborate peer-review process.The passage presents these as believed reasons for the comparatively low count.

5 DISCUSSION

The discussion reports developer reception, bug significance, scope boundaries, and practical considerations for NoREC. It highlights both the severity of optimization bugs and limitations in join handling and evaluation scope.

  • Reception by the DBMS developers: SQLite developers publicly recognized NoREC’s ability to find incorrect answers, including obscure corner cases involving type conversions and unreleased features.The developers described these findings as real bugs whose underlying causes could then be identified and fixed.
  • Bug importance: Many discovered bugs require unlikely combinations of operators or features, but generated queries and middleware can still expose such cases to users.The authors note that root causes are difficult to identify when queries are generated by middleware.
  • Handling of joins: NoREC leaves JOIN clauses unmodified, so translating join predicates—especially for joins other than inner joins—remains future work.For inner joins, combining ON and WHERE predicates is straightforward; other join types require more involved handling.
  • Code coverage and performance: Query-generation and translation overhead is negligible, while runtime is dominated by DBMS processing and communication.The authors also argue that code coverage is not a useful explanation of effectiveness because high coverage can coexist with unfound bugs.
  • Bug importance: 159 true bugs included 51 optimization bugs, which the authors consider especially severe because they may go unnoticed by developers.Crash, assertion, and error bugs often signal malfunction directly, whereas incorrect results can remain silent.
  • Fully automatic approach: NoREC automatically generates and validates test cases, although corner cases require special treatment and reduced cases were manually inspected during evaluation.The authors claim full automation for bug finding, while distinguishing it from subsequent test-case reduction and inspection.

6 RELATED WORK

The related work positions NoREC among differential, oracle-based, random-query, database-generation, and metamorphic testing approaches. Its distinctive role is a low-effort oracle focused primarily on optimization bugs.

  • Differential testing of DBMS: Unlike cross-DBMS differential testing, NoREC compares optimized and unoptimized executions within the same DBMS, avoiding dialect differences that complicate shared queries.Prior differential testing sends SQL to multiple systems, but DBMS-specific extensions and dialect differences make comparisons challenging.
  • Other correctness oracles for testing DBMS: NoREC mainly targets optimization bugs, complementing PQS, which addresses a broader class of DBMS logic bugs but requires higher implementation effort.This lower implementation effort may make NoREC practical for components where implementing PQS would be costly.
  • Random and targeted queries: Existing random-query generators can be paired with NoREC’s oracle to detect logic bugs in addition to crashes and hangs.The cited generators already support bug-finding through randomly generated queries and execution feedback.
  • Random and targeted databases: Database-generation approaches such as QAGen, Reverse Query Processing, and ADUSA construct data or expected results using constraints, symbolic execution, or formal specifications.These methods address the correctness-oracle problem through generated databases or query-aware result construction.
  • Metamorphic testing: NoREC combines query translation and counting to establish a metamorphic relation for detecting incorrect DBMS results.Metamorphic testing generates a new input whose expected result can be inferred from the original input and output.

7 CONCLUSION

The conclusion presents NoREC as a general, effective approach that constructs a test oracle by translating optimized queries into unoptimized queries and comparing their results.

  • 7 CONCLUSION: NoREC translates an optimized query into an unoptimized query, enabling a test oracle that detects optimization bugs by comparing result sets.The conclusion describes this translation-based oracle as the paper’s core insight and a foundation for DBMS correctness testing.
  • 7 CONCLUSION: The paper characterizes NoREC as a general, highly effective approach for detecting bugs in DBMS.
  • 7 CONCLUSION: The authors present NoREC as a foundation for broader correctness testing of DBMS.
Loading 2007.08292v1…