# A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 111 references that are in the map.
- First posted on arXiv 5 Jan 2021.

## Builds on (most cited first, 17 of 17)

- [Neo: A Learned Query Optimizer](https://mlsanity.com/paper/1904.03711/) (2019)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [An End-to-End Learning-based Cost Estimator](https://mlsanity.com/paper/1906.02560/) (2019)
- [Deep Unsupervised Cardinality Estimation](https://mlsanity.com/paper/1905.04278/) (2019)
- [Learning to Optimize Join Queries With Deep Reinforcement Learning](https://mlsanity.com/paper/1808.03196/) (2018)
- [Deep Reinforcement Learning for Join Order Enumeration](https://mlsanity.com/paper/1803.00055/) (2018)
- [Plan-Structured Deep Neural Network Models for Query Performance Prediction](https://mlsanity.com/paper/1902.00132/) (2019)
- [SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning](https://mlsanity.com/paper/1901.05152/) (2019)
- [Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings](https://mlsanity.com/paper/2002.12393/) (2020)
- [QuickSel: Quick Selectivity Learning with Mixture Models](https://mlsanity.com/paper/1812.10568/) (2018)
- [An Empirical Analysis of Deep Learning for Cardinality Estimation](https://mlsanity.com/paper/1905.06425/) (2019)
- [Join Query Optimization with Deep Reinforcement Learning Algorithms](https://mlsanity.com/paper/1911.11689/) (2019)
- [An Approach Based on Bayesian Networks for Query Selectivity Estimation](https://mlsanity.com/paper/1907.06295/) (2019)
- [Sampling-Based Query Re-Optimization](https://mlsanity.com/paper/1601.05748/) (2016)
- [Estimating Cardinalities with Deep Sketches](https://mlsanity.com/paper/1904.08223/) (2019)
- [Solving the Join Ordering Problem via Mixed Integer Linear Programming](https://mlsanity.com/paper/1511.02071/) (2015)
- [Forecasting the cost of processing multi-join queries via hashing for main-memory databases (Extended version)](https://mlsanity.com/paper/1507.03049/) (2015)

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

- [VolcanoML: Speeding up End-to-End AutoML via Scalable Search Space Decomposition](https://mlsanity.com/paper/2107.08861/) (2021)
- [MMTU: A Massive Multi-Task Table Understanding and Reasoning Benchmark](https://mlsanity.com/paper/2506.05587/) (2025)
- [No DBA? No regret! Multi-armed bandits for index tuning of analytical and HTAP workloads with provable guarantees](https://mlsanity.com/paper/2108.10130/) (2021)
- [A Unified and Efficient Coordinating Framework for Autonomous DBMS Tuning](https://mlsanity.com/paper/2303.05710/) (2023)
- [Rover: An online Spark SQL tuning service via generalized transfer learning](https://mlsanity.com/paper/2302.04046/) (2023)
- [BAP-SQL: Budget-Aware Observation Planning for Agentic Text-to-SQL](https://mlsanity.com/paper/2608.02876/) (2026)
- [Efficient End-to-End AutoML via Scalable Search Space Decomposition](https://mlsanity.com/paper/2206.09423/) (2022)
- [Fast Gumbel-Max Sketch and its Applications](https://mlsanity.com/paper/2302.05176/) (2023)
- [CONCERTO: Complex Query Execution Mechanism-Aware Learned Cost Estimation](https://mlsanity.com/paper/2412.00749/) (2024)
- [ZeroCard: Cardinality Estimation with Zero Dependence on Target Databases -- No Data, No Query, No Retraining](https://mlsanity.com/paper/2510.07983/) (2025)
- [Exqutor: Extended Query Optimizer for Vector-augmented Analytical Queries](https://mlsanity.com/paper/2512.09695/) (2025)
- [CoLSE: A Lightweight and Robust Hybrid Learned Model for Single-Table Cardinality Estimation using Joint CDF](https://mlsanity.com/paper/2512.12624/) (2025)
- [TiCard: Deployable EXPLAIN-only Residual Learning for Cardinality Estimation](https://mlsanity.com/paper/2512.14358/) (2025)
- [RELOAD: A Robust and Efficient Learned Query Optimizer for Database Systems](https://mlsanity.com/paper/2604.14725/) (2026)

## Abstract (arXiv)

Query optimizer is at the heart of the database systems. Cost-based optimizer studied in this paper is adopted in almost all current database systems. A cost-based optimizer introduces a plan enumeration algorithm to find a (sub)plan, and then uses a cost model to obtain the cost of that plan, and selects the plan with the lowest cost. In the cost model, cardinality, the number of tuples through an operator, plays a crucial role. Due to the inaccuracy in cardinality estimation, errors in cost model, and the huge plan space, the optimizer cannot find the optimal execution plan for a complex query in a reasonable time. In this paper, we first deeply study the causes behind the limitations above. Next, we review the techniques used to improve the quality of the three key components in the cost-based optimizer, cardinality estimation, cost model, and plan enumeration. We also provide our insights on the future directions for each of the above aspects.