Towards Robust Query Optimization

Abstract

Database optimizers choose optimal execution plans for a given query based on point estimates of query selectivities; errors in these estimates can sometimes lead to plans that perform catastrophically worse than true optimal ones. This dissertation makes three contributions towards a principled and practical approach to robust query optimization, with the goal of choosing plans whose performance is resilient against estimation errors.The first contribution, PARQO, introduces a general, penalty-based formulation of robustness that evaluates plans by their expected performance loss relative to the true optimal plan under selectivity uncertainty. By learning workload-informed error models and applying principled sensitivity analysis, PARQO enables robust plan selection that is flexible, interpretable, and effective, while remaining compatible with existing optimizers. Building on this foundation, the second contribution, PAR2QO, integrates robustness into parametric query optimization,which simultaneously optimizes for many query instances sharing the same template but differing in parameters, thereby addressing the high optimization overhead associated with robust query optimization. Unlike traditional parametric optimization approaches that cache and reuse individual plans, PAR2QO shares robustness computation across parameter space, enabling scalable, workload-aware robust plan identification, profiling, and reuse. This approach maintains robustness under workload and data shifts while incurring significantly lower training and optimization costs than the state-of-the-art parametric optimization methods.Instead of operating on top of existing optimizers as with the above two contributions, the final contribution, RobDP, integrates robustness directly into an optimizer that uses the popular, Selinger-style dynamic programming approach. By introducing customizable local plan pruning and retention policies during dynamic programming, RobDP preserves the optimizer's structure and efficiency while allowing it to uncover candidate plans whose robustness only becomes evident in later stages of optimization.Together, these three contributions form a principled and practical path toward robust query optimization: from robust plan selection, to robust plan reuse, and finally to robustness-aware plan construction, progressively moving robust query optimization from a stand-alone procedure to an integral capability of database systems.