Cardinality Estimation: Is Machine Learning a Silver Bullet? - Li, Beibin; Lu, Yao; Wang, Chi; Kandula, Srikanth (AIDB, 2021)
Cardinality estimation (CE) aims for high accuracy, small storage, fast building and low query answering latency. We analyze the upper error bounds of random uniform sampling for single-table CE and use them as the accuracy target for machine learning (ML)-based CE. Our analysis indicates that ML-based CE exhibits no Pareto advantage over random uniform sampling but provides a tradeoff among the metrics of interest. We outline such tradeoffs and point out the scenarios when ML-based CE can be useful and when sampling can help.