ClassiCard: A Classifier Based Approach for Cardinality Estimation in Normalized Tables
摘要
Cardinality estimation is one of the most fundamental problems in database query optimization. Most existing methods for cardinality estimation in multi-table join queries either suffer from significant estimation errors due to the assumption of attribute independence, or face slow inference caused by complex probabilistic computations. In this paper, we propose a classifier based method to implement effective and efficient cardinality estimation in normalized tables. Specifically, we first build a classification model for each normalized table to learn the attribute distribution by generating negative samples. Second, we propose the conditional sampling method to improve the efficiency of cardinality estimation of single-table range queries. Finally, we incorporate the single-table results into an importance sampling-based join framework to estimate the cardinality of multi-table joins. Experimental results demonstrate that our method significantly improves the query planning while achieving faster inferences compared to existing learning based methods.