Cost-Aware Optimization for Agentic Query Execution

Abstract

Classical query optimization searches over algebraically equivalent plans that differ only in cost. This assumption breaks once LLM-backed operators enter the picture: their placement, ordering, and granularity jointly determine both cost and answer quality, and the right choice among the alternatives is often revealed only at runtime. We formalize this setting as agentic query execution, a query execution paradigm in which agent-based planning is interleaved with execution, and agent workflow optimization becomes the analogue of classical query optimization. We then present EnumGRPO, a self-improving optimizer for this setting. During a learning stage, EnumGRPO enumerates query plans over decisions such as execution paradigm, operator type, operator placement, selectivity scope, and projection width, then distills quality-cost feedback into reusable planning heuristics via in-context reinforcement learning. On SWAN, EnumGRPO achieves higher execution accuracy than LOTUS, Palimpzest, and Agentic BlendSQL, while cutting LLM-operator cost by up to 317x. Without retraining, the learned experiences transfer to another LLM family, the SemBench workload, and purely relational Spider and BIRD workloads, improving or preserving quality while reducing LLM-operator use.