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

• URL: http://arxiv.org/abs/2510.03386v1
• Date: Fri, 03 Oct 2025 17:43:02 GMT
• Title: Is it Bigger than a Breadbox: Efficient Cardinality Estimation for Real World Workloads
• Authors: Zixuan Yi, Sami Abu-el-Haija, Yawen Wang, Teja Vemparala, Yannis Chronis, Yu Gan, Michael Burrows, Carsten Binnig, Bryan Perozzi, Ryan Marcus, Fatma Ozcan,
• Abstract summary: DB engines produce efficient query execution plans by relying on cost models.<n>We present a practical method to estimate cardinality of queries using implementationss, with magic numbers tuned to improve average performance on benchmarks.<n>Our method has negligible overhead and competes with SoTA learning-based approaches on error metrics.
• Score: 23.75171397684964
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• CoLSE: A Lightweight and Robust Hybrid Learned Model for Single-Table Cardinality Estimation using Joint CDF [7.945011337356916]
  Cardinality estimation is a critical component of query optimization.<n>We propose CoLSE, a hybrid learned approach for single-table cardinality estimation.<n> Experimental results show that CoLSE achieves a favorable trade-off among accuracy, training time, latency, and model size, outperforming existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2025-12-14T10:08:20Z)
• Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptation [54.61034867177997]
  Caching inference responses allows them to be retrieved without another forward pass through the Large Language Models.<n>Traditional exact-match caching overlooks the semantic similarity between queries, leading to unnecessary recomputation.<n>We present a principled, learning-based framework for semantic cache eviction under unknown query and cost distributions.
  arXiv  Detail & Related papers  (2025-08-11T06:53:27Z)
• CardBench: A Benchmark for Learned Cardinality Estimation in Relational Databases [17.46316633654637]
  Cardinality estimation is crucial for enabling high query performance in databases. There is no systematic benchmark or datasets which allows researchers to evaluate the progress made by new learned approaches. We release a benchmark, containing thousands of queries over 20 distinct real-world databases for learned cardinality estimation.
  arXiv  Detail & Related papers  (2024-08-28T23:25:25Z)
• PRICE: A Pretrained Model for Cross-Database Cardinality Estimation [78.30959470441442]
  Cardinality estimation (CardEst) is essential for optimizing query execution plans. Recent ML-based CardEst methods achieve high accuracy but face deployment challenges due to high preparation costs. We propose PRICE, a PRetrained multI-table CardEst model, which addresses these limitations.
  arXiv  Detail & Related papers  (2024-06-03T06:21:53Z)
• JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
  Join order selection (JOS) is the problem of ordering join operations to minimize total query execution cost. We present JoinGym, a query optimization environment for bushy reinforcement learning (RL) Under the hood, JoinGym simulates a query plan's cost by looking up intermediate result cardinalities from a pre-computed dataset.
  arXiv  Detail & Related papers  (2023-07-21T17:00:06Z)
• Kepler: Robust Learning for Faster Parametric Query Optimization [5.6119420695093245]
  We propose an end-to-end learning-based approach to parametric query optimization. Kepler achieves significant improvements in query runtime on multiple datasets.
  arXiv  Detail & Related papers  (2023-06-11T22:39:28Z)
• Lero: A Learning-to-Rank Query Optimizer [49.841082217997354]
  We introduce a learning to rank query, called Lero, which builds on top of the native query and continuously learns to improve query optimization. Rather than building a learned from scratch, Lero is designed to leverage decades of wisdom of databases and improve the native. Lero achieves near optimal performance on several benchmarks.
  arXiv  Detail & Related papers  (2023-02-14T07:31:11Z)
• FactorJoin: A New Cardinality Estimation Framework for Join Queries [35.22928513918166]
  Cardinality estimation is one of the most fundamental and challenging problems in query optimization. We propose a new framework FactorJoin for estimating join queries. In our evaluation, FactorJoin can produce more effective estimates than the previous state-of-the-art learning-based methods.
  arXiv  Detail & Related papers  (2022-12-11T15:51:39Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  We propose a generalized iterative imputation framework for adaptively and automatically configuring column-wise models. We provide a concrete implementation with out-of-the-box learners, simulators, and interfaces.
  arXiv  Detail & Related papers  (2022-06-15T19:10:35Z)
• Efficient Sub-structured Knowledge Distillation [52.5931565465661]
  We propose an approach that is much simpler in its formulation and far more efficient for training than existing approaches. We transfer the knowledge from a teacher model to its student model by locally matching their predictions on all sub-structures, instead of the whole output space.
  arXiv  Detail & Related papers  (2022-03-09T15:56:49Z)
• Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach [22.958342743597044]
  We investigate the possibilities of utilizing deep learning for cardinality estimation of similarity selection. We propose a novel and generic method that can be applied to any data type and distance function.
  arXiv  Detail & Related papers  (2020-02-15T20:22:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.