Is it Bigger than a Breadbox: Efficient Cardinality Estimation for Real World Workloads
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914072932384768 |
|---|---|
| author | Yi, Zixuan Abu-el-Haija, Sami Wang, Yawen Vemparala, Teja Chronis, Yannis Gan, Yu Burrows, Michael Binnig, Carsten Perozzi, Bryan Marcus, Ryan Ozcan, Fatma |
| author_facet | Yi, Zixuan Abu-el-Haija, Sami Wang, Yawen Vemparala, Teja Chronis, Yannis Gan, Yu Burrows, Michael Binnig, Carsten Perozzi, Bryan Marcus, Ryan Ozcan, Fatma |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_03386 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Is it Bigger than a Breadbox: Efficient Cardinality Estimation for Real World Workloads Yi, Zixuan Abu-el-Haija, Sami Wang, Yawen Vemparala, Teja Chronis, Yannis Gan, Yu Burrows, Michael Binnig, Carsten Perozzi, Bryan Marcus, Ryan Ozcan, Fatma Databases Machine Learning 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. |
| title | Is it Bigger than a Breadbox: Efficient Cardinality Estimation for Real World Workloads |
| topic | Databases Machine Learning |
| url | https://arxiv.org/abs/2510.03386 |