VeriEQL: Bounded Equivalence Verification for Complex SQL Queries with Integrity Constraints

Yang He, P. Zhao, Xinyu Wang, Yuepeng Wang

TL;DR

This paper introduces VeriEQL, a novel SMT-based approach for verifying bounded equivalence of complex SQL queries, even when integrity constraints are present. VeriEQL significantly outperforms existing methods, proving or disproving equivalence for over 70% of a large, diverse benchmark suite and generating valuable counterexamples for debugging.

What Problem Does This Paper Address?

Ensuring that two SQL queries produce the same results is crucial for tasks like query rewriting and automated grading. However, current tools struggle with real-world SQL queries that often include complex features like sorting, case statements, and, importantly, integrity constraints (e.g., primary keys, foreign keys, NOT NULL). Existing techniques are limited in their ability to handle these complexities, supporting only a small fraction of typical queries. This gap hinders the practical application of formal verification in database systems.

Methods

VeriEQL employs a Satisfiability Modulo Theories (SMT) approach. The core innovation lies in a new logical encoding that models SQL query semantics over symbolic tuples within the theory of integers and uninterpreted functions. This encoding is designed to precisely handle complex SQL features and rich integrity constraints without relying on overly complex theories. The process involves:

  1. Symbolic Database Generation: Creating a symbolic representation of databases with a bounded number of tuples.
  2. Integrity Constraint Encoding: Translating integrity constraints into SMT formulas.
  3. Query Semantics Encoding: Encoding how each SQL operator transforms symbolic tuples.
  4. Equivalence Checking: Constructing an SMT formula that asserts the non-equivalence of the two queries, incorporating both query semantics and integrity constraints.
  5. SMT Solving: Using an SMT solver (Z3) to determine satisfiability. If satisfiable, a counterexample database is generated; otherwise, equivalence is proven.

Datasets

The evaluation uses a comprehensive set of benchmarks from three sources:

  • LeetCode: A newly curated dataset of 23,994 query pairs from LeetCode, paired with manually written "ground-truth" queries. This dataset is valuable for its diversity and real-world query patterns.
  • Calcite: 397 query pairs derived from the Apache Calcite optimization rules test suite, representing a standard workload.
  • Literature: 64 query pairs from existing research on query equivalence.

Key Insights and Ideas

  • Integrity Constraints are Crucial: The paper strongly emphasizes that supporting rich integrity constraints is not just a feature but a necessity for accurate equivalence checking. Ignoring them leads to a high rate of spurious counterexamples.
  • Symbolic Tuples for Practicality: The use of symbolic tuples, combined with an SMT encoding based on integers and uninterpreted functions, provides a practical yet powerful way to model complex SQL features and integrity constraints without excessive complexity.
  • Bounded Equivalence is Sufficient: The approach focuses on bounded equivalence, which is often sufficient for practical applications and allows for more efficient verification than full, unbounded equivalence.
  • Counterexamples Drive Debugging: VeriEQL's ability to generate concrete counterexamples is highlighted as a key enabler for finding bugs in real-world systems like MySQL and Apache Calcite, and for improving test suites.

Key Results

  • High Coverage: VeriEQL supports over 75% of the benchmarks across all workloads, significantly outperforming baselines in terms of query complexity handled.
  • Superior Performance: VeriEQL proves or disproves equivalence for over 70% of benchmarks within a 10-minute timeout, outperforming state-of-the-art techniques by more than an order of magnitude.
  • Effective Disproving: VeriEQL generates counterexamples for 14.9% of LeetCode benchmarks, a capability lacking in most bounded verification baselines.
  • Bug Discovery: VeriEQL identified serious bugs in MySQL and Calcite, leading to confirmed fixes and improvements in these projects.
  • Scalability: VeriEQL can verify equivalence for a significant number of benchmarks with input bounds up to 5, and even up to 100 for some cases, demonstrating reasonable scalability.

Limitations and Future Work

  • Correlated Subqueries and Window Functions: VeriEQL currently does not support correlated subqueries or window functions, though the authors suggest these could be incorporated by leveraging existing techniques.
  • Large Counterexamples: For a small number of benchmarks, disproving equivalence requires very large input databases (over 1000 tuples), which may exceed the practical time limits of VeriEQL.
  • Formal Semantics Comparison: Further work could explore the formal differences between VeriEQL's semantics and other state-of-the-art proposals.

Summary updated

Abstract

The task of SQL query equivalence checking is important in various real-world applications (including query rewriting and automated grading) that involve complex queries with integrity constraints; yet, state-of-the-art techniques are very limited in their capability of reasoning about complex features (e.g., those that involve sorting, case statement, rich integrity constraints, etc.) in real-life queries. To the best of our knowledge, we propose the first SMT-based approach and its implementation, VeriEQL, capable of proving and disproving bounded equivalence of complex SQL queries. VeriEQL is based on a new logical encoding that models query semantics over symbolic tuples using the theory of integers with uninterpreted functions. It is simple yet highly practical -- our comprehensive evaluation on over 20,000 benchmarks shows that VeriEQL outperforms all state-of-the-art techniques by more than one order of magnitude in terms of the number of benchmarks that can be proved or disproved. VeriEQL can also generate counterexamples that facilitate many downstream tasks (such as finding serious bugs in systems like MySQL and Apache Calcite).
BibTeX
@inproceedings{he2024verieql,
  author = {Yang He and P. Zhao and Xinyu Wang and Yuepeng Wang},
  title = {{VeriEQL: Bounded Equivalence Verification for Complex SQL Queries with Integrity Constraints}},
  booktitle = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  doi = {10.1145/3649849},
}
Figure