Adversarial Query Synthesis via Bayesian Optimization

Jeffrey Tao; Yimeng Zeng; Haydn Thomas Jones; Natalie Maus; Osbert Bastani; Jacob R. Gardner; Ryan Marcus

cs.DBMar 2, 2026

Adversarial Query Synthesis via Bayesian Optimization

Authors: Jeffrey Tao, Yimeng Zeng, Haydn Thomas Jones, Natalie Maus, Osbert Bastani, Jacob R. Gardner, Ryan Marcus

Organizations: University of Pennsylvania

Abstract

Benchmark workloads are extremely important to the database management research community, especially as more machine learning components are integrated into database systems. Here, we propose a Bayesian optimization technique to automatically search for difficult benchmark queries, significantly reducing the amount of manual effort usually required. In preliminary experiments, we show that our approach can generate queries with more than double the optimization headroom compared to existing benchmarks.

Figures & tables

Figure 1: CDFs of absolute and relative differences between baseline system (DuckDB) and witness plan for our generated benchmark. Median values at red cross.

Figure 2: Comparison of geometric mean relative headroom for four benchmarks. Values for JOB and JOB-Complex are from [ 25 ] . Values for Stack are approximated from [ 11 ] . Values for “Ours” are computed with respect to the witness plan.

Synthetic Benchmark Generation

Synthetic benchmark generation creates controlled, verifiable evaluation tasks and datasets to test models across diverse settings.

See all 281 papers

RELOAD: A Robust and Efficient Learned Query Optimizer for Database Systems
Apr 16, 2026Seokwon Lee, Jaeyoung Sim, Sihyun Kim +3Learning to Optimize Database Systems
Yonsei University BDAI Lab, Seoul 03722, South Korea · Microsoft Gray Systems Lab, Redmond, USA
Demonstrating GenDB: Instance-Optimized and Customized Query Processing Code Generation via LLM Agents
Jul 22, 2026Jiale Lao, Immanuel TrummerCode Generation Agentic Code Generation
Cornell University
WAter: A Workload-Adaptive Knob Tuning System based on Workload Compression
Mar 28, 2026Yibo Wang, Jiale Lao, Chen Zhang +3Database Systems Relational Databases
Purdue University, West Lafayette, Indiana, USA · Cornell University, Ithaca, New York, USA · Sichuan University, Chengdu, China

Apr 16, 2026J/K move · Enter open · S save

RELOAD: A Robust and Efficient Learned Query Optimizer for Database Systems

Seokwon Lee, Jaeyoung Sim, Sihyun Kim, Yuhsing Li+2

Yonsei University BDAI Lab, Seoul 03722, South Korea · Microsoft Gray Systems Lab, Redmond, USA

Learning to Optimize Database Systems Robust RL Relational Databases

Open paper AskPDF arXiv

Recent advances in query optimization have shifted from traditional rule-based and cost-based techniques towards machine learning-driven approaches. Among these, reinforcement learning (RL) has attracted significant attention due to its ability to optimize long-term performance by learning policies over query planning. However, existing RL-based query optimizers often exhibit unstable performance at the level of individual queries, including severe performance regressions, and require prolonged training to reach the plan quality of expert, cost-based optimizers. These shortcomings make learned query optimizers difficult to deploy in practice and remain a major barrier to their adoption in production database systems. To address these challenges, we present RELOAD, a robust and efficient learned query optimizer for database systems. RELOAD focuses on (i) robustness, by minimizing query-level performance regressions and ensuring consistent optimization behavior across executions, and (ii) efficiency, by accelerating convergence to expert-level plan quality. Through extensive experiments on standard benchmarks, including Join Order Benchmark, TPC-DS, and Star Schema Benchmark, RELOAD demonstrates up to 2.4x higher robustness and 3.1x greater efficiency compared to state-of-the-art RL-based query optimization techniques.

Abstract

Synthetic Benchmark Generation

Explore similar work

RELOAD: A Robust and Efficient Learned Query Optimizer for Database Systems

Demonstrating GenDB: Instance-Optimized and Customized Query Processing Code Generation via LLM Agents

WAter: A Workload-Adaptive Knob Tuning System based on Workload Compression