A Lightweight Learned Cardinality Estimation Model

Abstract

Cardinality estimation is a fundamental task in database management systems, aiming to predict query results accurately without executing the queries. However, existing techniques either achieve low estimation accuracy or incur high inference latency. Simultaneously achieving high speed and accuracy becomes critical for the cardinality estimation problem. In this paper, we propose a novel data-driven approach called CoDe (Covering with Decompositions) to address this problem. CoDe employs the concept of covering design, which divides the table into multiple smaller, overlapping segments. For each segment, CoDe utilizes tensor decomposition to accurately model its data distribution. Moreover, CoDe introduces innovative algorithms to select the best-fitting distributions for each query, combining them to estimate the final result. By employing multiple models to approximate distributions, CoDe excels in effectively modeling discrete distributions and ensuring computational efficiency. Notably, experimental results show that our method represents a significant advancement in cardinality estimation, achieving state-of-the-art levels of both estimation accuracy and inference efficiency. Across various datasets, CoDe achieves absolute accuracy in estimating more than half of the queries.

IEEE Transactions on Knowledge and Data Engineering (TKDE), 2025

References in corpus (6)

• XGBoost: A Scalable Tree Boosting System
• Deep Unsupervised Cardinality Estimation
• A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation
• QuickSel: Quick Selectivity Learning with Mixture Models
• ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads (Extended)
• An Approach Based on Bayesian Networks for Query Selectivity Estimation