Stop Handcrafting Your Engine! GenDB-V: Towards AI-Generated and Formally Verified Database Systems

Jiale Lao, Immanuel TrummerarXiv 2026 · arXiv

TL;DR

GenDB-V is a new system that uses AI agents to automatically synthesize database engines that are both highly optimized for specific workloads and formally verified for correctness. By combining LLM-driven optimization with a rigorous formal verification pipeline, it achieves up to 61x speedups over state-of-the-art engines like DuckDB while guaranteeing the absence of "wrong-answer" bugs.

What Problem Does This Paper Address?

For decades, the database community has faced a dual challenge: making engines faster and ensuring they are correct. As hardware (e.g., GPUs, fast SSDs) and workloads evolve, engineers are forced to repeatedly redesign and rebuild database systems—a process that is both time-consuming and error-prone.

Even mature engines like PostgreSQL are not immune to "wrong-answer" bugs, which can survive for years despite extensive testing. While formal verification (mathematically proving code is correct) offers a solution, it has historically required massive human effort—for instance, verifying the seL4 kernel took roughly 20 person-years. GenDB-V aims to automate this entire cycle, letting AI handle the "handcrafting" while a formal verifier ensures the results are bulletproof.

Methods

GenDB-V sits at the intersection of Large Language Models (LLMs) and formal methods. Its architecture relies on several key innovations:

Figure 1: GenDB-V overview.
  1. SQLSpec & Deterministic Targets: The authors developed SQLSpec, a formal library in the Verus verification language that defines the mathematical semantics of SQL (based on PostgreSQL). Before an AI agent starts, GenDB-V programmatically generates fixed "synthesis targets"—mathematical contracts that the agent must satisfy. Because these targets are fixed outside the agent's control, the AI cannot "cheat" by weakening the correctness requirements.
  2. Performance-First Exploration: Writing formal proofs is expensive and slow. GenDB-V allows agents to first prototype and profile candidate designs in an unverified "diagnostic mode." Once the fastest design is found, the agent then focuses on developing the formal proofs for that specific implementation.
  3. Modular Proof Decomposition: To make verification tractable for LLMs, GenDB-V guides agents to break proofs into three layers: storage reader contracts, physical loop invariants, and "bridge lemmas" that connect low-level execution back to high-level SQL semantics.
  4. Storage-Execution Co-Optimization: Agents aren't just writing query code; they can design custom storage layouts (e.g., compressed columns, sorted orders). GenDB-V ensures these are lossless by requiring the agent to prove that the original logical database can be perfectly recovered from the physical storage.
Figure 2: Translating the running example from a SQL template (step 1) to a typed AST (step 2), a SQLSpec query tree 𝑄𝑇(𝑘) (step 3), and its mathematical semantics (step 4).

Datasets

The system was evaluated on two major benchmarks:

  • TPC-H (SF100): The industry-standard benchmark for analytical queries.
  • SEC-EDGAR (SF3): A benchmark based on financial filings, specifically chosen because it is less likely to have been seen by LLMs during training, thus reducing the risk of "data leakage" where the model simply remembers optimized code.

Key Insights and Ideas

  • Specialization Beats Generality: General-purpose engines like DuckDB must handle every possible query. By specializing an engine to a specific SQL template and hardware, GenDB-V can find optimizations (like fused loops or custom indexing) that a general engine would miss.
  • Verification as a Guardrail for AI: The authors found that testing-based AI synthesis (like the prior Bespoke OLAP system) often produces "silent" bugs—code that passes tests but fails on other valid inputs due to assumptions like "shipment dates always follow order dates." Formal verification catches these by requiring a proof for every possible input in the domain.
  • The "Performance-First" Loop: Decoupling performance trials from verification is crucial. It prevents wasting expensive LLM tokens on proving code that ends up being slow.

Key Results

GenDB-V demonstrates that you don't have to sacrifice performance for formal correctness:

  • Massive Speedups: For specialized query templates, GenDB-V achieved geometric-mean speedups of 22.0x to 61.3x over DuckDB and Umbra.
  • General-Purpose Performance: Even when synthesized as a general-purpose engine (not just for one template), it outperformed DuckDB by 1.27x to 3.4x on TPC-H.
  • Superior Correctness: An audit of a leading testing-based synthesis method (Bespoke OLAP) revealed incorrect answers for 16 out of 28 templates. GenDB-V, by contrast, requires proofs that cover the entire input domain, preventing such failures.
  • Cost-Effective: Synthesizing a verified engine cost roughly $1,229 in LLM tokens—a fraction of the cost of hiring expert engineers for months of manual verification work.

Limitations and Future Work

While promising, GenDB-V has some current boundaries:

  • SQL Subset: SQLSpec currently supports a core analytical subset of SQL. Future work is needed to include more complex features like window functions and recursive queries.
  • Synthesis Cost: While cheaper than humans, thousands of dollars in API costs per benchmark is still significant for smaller projects.
  • Trusted Foundation: The system still relies on the correctness of its "trusted foundation," which includes the Verus verifier, the Z3 SMT solver, and the Rust compiler.
  • Parallelism: Current support is limited to fork-join parallelism; extending this to shared mutable structures is a key next step.

Summary updated

Abstract

For over 50 years, the database community has developed a wide range of successful engines to answer two fundamental questions: how can database systems run faster, and how can we ensure their correctness? Experience with these engines shows that performance depends on hardware and workloads. As both change over time, we repeatedly redesign and rebuild database systems, a time-consuming and expensive process. Correctness remains another long-standing challenge: recent studies continue to uncover wrong-answer bugs even in mature database engines, despite years of development and testing. To address these, we present GenDB-V, a system that enables AI agents to synthesize database engines specialized to hardware and workloads for performance, and formally verified for correctness. GenDB-V supports specialized implementations of SQL templates and general-purpose engines that accept any query within a supported SQL subset. First, we develop SQLSpec to formalize SQL semantics and deterministically construct fixed, implementation-agnostic synthesis targets. Second, we enable joint synthesis of fast code and formal proofs through storage--execution co-optimization, performance-first exploration, and three-layer modular proofs that bridge low-level execution to SQLSpec semantics. Third, we verify the synthesized code and proofs against the fixed synthesis targets in an isolated pipeline, proving SQL correctness and program safety. We evaluate GenDB-V on TPC-H and SEC-EDGAR. For verified template implementations, GenDB-V achieves geometric-mean speedups of 22.0-61.3x over DuckDB and Umbra. For a verified general-purpose engine, GenDB-V also achieves speedups of 1.27-3.4x on TPC-H. GenDB-V also achieves better performance than a testing-based LLM synthesis method, while our audit and tests expose incorrect answers in that method's implementations for 16 of 28 templates.
BibTeX
@misc{lao2026stop,
  author = {Jiale Lao and Immanuel Trummer},
  title = {{Stop Handcrafting Your Engine! GenDB-V: Towards AI-Generated and Formally Verified Database Systems}},
  year = {2026},
  eprint = {2611.02779},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.02779},
}
Figure