Deep Unsupervised Cardinality Estimation

Understand

Cardinality estimation has long been grounded in statistical tools for density estimation.

• To capture the rich multivariate distributions of relational tables, we propose the use of a new type of high-capacity statistical model: deep autoregressive models.
• However, direct application of these models leads to a limited estimator that is prohibitively expensive to evaluate for range or wildcard predicates.
• To produce a truly usable estimator, we develop a Monte Carlo integration scheme on top of autoregressive models that can efficiently handle range queries with dozens of dimensions or more.