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:
- Symbolic Database Generation: Creating a symbolic representation of databases with a bounded number of tuples.
- Integrity Constraint Encoding: Translating integrity constraints into SMT formulas.
- Query Semantics Encoding: Encoding how each SQL operator transforms symbolic tuples.
- Equivalence Checking: Constructing an SMT formula that asserts the non-equivalence of the two queries, incorporating both query semantics and integrity constraints.
- 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