# Is it Bigger than a Breadbox: Efficient Cardinality Estimation for Real World Workloads

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 3 Oct 2025.

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

- [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)
- [Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation](https://mlsanity.com/paper/2109.05877/) (2021)
- [FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation](https://mlsanity.com/paper/2011.09022/) (2020)
- [Are We Ready For Learned Cardinality Estimation?](https://mlsanity.com/paper/2012.06743/) (2020)
- [Yggdrasil Decision Forests: A Fast and Extensible Decision Forests Library](https://mlsanity.com/paper/2212.02934/) (2022)
- [FactorJoin: A New Cardinality Estimation Framework for Join Queries](https://mlsanity.com/paper/2212.05526/) (2022)
- [PRICE: A Pretrained Model for Cross-Database Cardinality Estimation](https://mlsanity.com/paper/2406.01027/) (2024)
- [CardBench: A Benchmark for Learned Cardinality Estimation in Relational Databases](https://mlsanity.com/paper/2408.16170/) (2024)

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

- [TiCard: Deployable EXPLAIN-only Residual Learning for Cardinality Estimation](https://mlsanity.com/paper/2512.14358/) (2025)

## Abstract (arXiv)

DB engines produce efficient query execution plans by relying on cost models. Practical implementations estimate cardinality of queries using heuristics, with magic numbers tuned to improve average performance on benchmarks. Empirically, estimation error significantly grows with query complexity. Alternatively, learning-based estimators offer improved accuracy, but add operational complexity preventing their adoption in-practice. Recognizing that query workloads contain highly repetitive subquery patterns, we learn many simple regressors online, each localized to a pattern. The regressor corresponding to a pattern can be randomly-accessed using hash of graph structure of the subquery. Our method has negligible overhead and competes with SoTA learning-based approaches on error metrics. Further, amending PostgreSQL with our method achieves notable accuracy and runtime improvements over traditional methods and drastically reduces operational costs compared to other learned cardinality estimators, thereby offering the most practical and efficient solution on the Pareto frontier. Concretely, simulating JOB-lite workload on IMDb speeds-up execution by 7.5 minutes (>30%) while incurring only 37 seconds overhead for online learning.