mlsanityData to 7 Oct 2026

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

arXiv 2101.01507 ↗First posted 5 Jan 2021cs.DB cs.AIcited by 14

Not on the map. Why?

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.

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

Builds on

17 of 111 references.

References · 17

  1. 2019Neo: A Learned Query Optimizercited by 80
  2. 2018Learned Cardinalities: Estimating Correlated Joins with Deep Learningcited by 64
  3. 2019An End-to-End Learning-based Cost Estimatorcited by 43
  4. 2019Deep Unsupervised Cardinality Estimationcited by 36
  5. 2018Learning to Optimize Join Queries With Deep Reinforcement Learningcited by 32
  6. 2018Deep Reinforcement Learning for Join Order Enumerationcited by 25
  7. 2019Plan-Structured Deep Neural Network Models for Query Performance Predictioncited by 24
  8. 2019SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learningcited by 17
  9. 2020Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findingscited by 16
  10. 2018QuickSel: Quick Selectivity Learning with Mixture Modelscited by 12
  11. 2019An Empirical Analysis of Deep Learning for Cardinality Estimationcited by 8
  12. 2019Join Query Optimization with Deep Reinforcement Learning Algorithmscited by 7
5 more
  1. 2019An Approach Based on Bayesian Networks for Query Selectivity Estimationcited by 6
  2. 2016Sampling-Based Query Re-Optimizationcited by 4
  3. 2019Estimating Cardinalities with Deep Sketchescited by 4
  4. 2015Solving the Join Ordering Problem via Mixed Integer Linear Programmingcited by 3
  5. 2015Forecasting the cost of processing multi-join queries via hashing for main-memory databases (Extended version)cited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 1; 2023: 3; 2024: 1; 2025: 5; 2026: 2.

14 papers.

Sort:

By area:

  1. 2021VolcanoML: Speeding up End-to-End AutoML via Scalable Search Space Decompositioncited by 25
  2. 2025MMTU: A Massive Multi-Task Table Understanding and Reasoning Benchmarkcited by 13
  3. 2021No DBA? No regret! Multi-armed bandits for index tuning of analytical and HTAP workloads with provable guaranteescited by 4
  4. 2023A Unified and Efficient Coordinating Framework for Autonomous DBMS Tuningcited by 4
  5. 2023Rover: An online Spark SQL tuning service via generalized transfer learningcited by 3
  6. 2026BAP-SQL: Budget-Aware Observation Planning for Agentic Text-to-SQLcited by 1
  7. 2022Efficient End-to-End AutoML via Scalable Search Space Decompositioncited by 0
  8. 2023Fast Gumbel-Max Sketch and its Applicationscited by 0
  9. 2024CONCERTO: Complex Query Execution Mechanism-Aware Learned Cost Estimationcited by 0
  10. 2025ZeroCard: Cardinality Estimation with Zero Dependence on Target Databases -- No Data, No Query, No Retrainingcited by 0
  11. 2025Exqutor: Extended Query Optimizer for Vector-augmented Analytical Queriescited by 0
  12. 2025CoLSE: A Lightweight and Robust Hybrid Learned Model for Single-Table Cardinality Estimation using Joint CDFcited by 0
2 more
  1. 2025TiCard: Deployable EXPLAIN-only Residual Learning for Cardinality Estimationcited by 0
  2. 2026RELOAD: A Robust and Efficient Learned Query Optimizer for Database Systemscited by 0