Static Typing Meets Adaptive Optimization: A Unified Approach to Recursive Queries
Anna Herlihy, Anastasia Ailamaki, Martin Odersky · 2025
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.