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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

ClassiCard: A Classifier Based Approach for Cardinality Estimation in Normalized Tables

  • Bingbing Xiang,
  • Huashuai Liu,
  • Xinran Wu,
  • Kun Yue

摘要

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.