Publication
Writing correct and efficient recursive SQL queries is exceptionally challenging because recursive queries risk returning incorrect results, throwing runtime exceptions, or never terminating. Failures in recursive query execution fall into two categories: non-recoverable failures, such as nontermination or database error, which must be identified statically, and recoverable failures, which arise from incorrect assumptions about program behavior - for example, the optimal join order based on input relations may no longer be optimal after execution begins - leading to severe performance degradation. We present CaQL, a unified recursive query framework that statically enforces correctness properties at the type level while supporting runtime query optimization through multi-stage programming. CaQL unifies two existing systems under a shared architecture: TyQL, a statically typed, language-integrated query framework, and Carac, an adaptive recursive query engine that uses runtime metaprogramming to reoptimize queries based on observed behavior. CaQL leverages bidirectional information flow between TyQL and Carac to make static correctness checks more precise and runtime optimizations more aggressive, enabling behavior that neither system achieves independently. We evaluate CaQL on queries drawn from recursive SQL benchmarks, graph analytics, and program analysis, demonstrating the safety and convenience of language-integrated query with performance competitive with or superior to a state-of-the-art Datalog engine.