Cardinality Estimation: Is Machine Learning a Silver Bullet?

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.