# Sampling-Based Query Re-Optimization

arXiv: https://arxiv.org/abs/1601.05748 · HTML: https://mlsanity.com/paper/1601.05748/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2016.

## Built on by (most cited first, 4 of 4)

- [A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration](https://mlsanity.com/paper/2101.01507/) (2021)
- [Kepler: Robust Learning for Faster Parametric Query Optimization](https://mlsanity.com/paper/2306.06798/) (2023)
- [Budget-aware Query Tuning: An AutoML Perspective](https://mlsanity.com/paper/2404.00137/) (2024)
- [Access Paths for Efficient Ordering with Large Language Models](https://mlsanity.com/paper/2509.00303/) (2025)

## Abstract (arXiv)

Despite of decades of work, query optimizers still make mistakes on "difficult" queries because of bad cardinality estimates, often due to the interaction of multiple predicates and correlations in the data. In this paper, we propose a low-cost post-processing step that can take a plan produced by the optimizer, detect when it is likely to have made such a mistake, and take steps to fix it. Specifically, our solution is a sampling-based iterative procedure that requires almost no changes to the original query optimizer or query evaluation mechanism of the system. We show that this indeed imposes low overhead and catches cases where three widely used optimizers (PostgreSQL and two commercial systems) make large errors.