Deep Unsupervised Cardinality Estimation
  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.
  Like classical synopses, our estimator summarizes the data without
supervision. Unlike previous solutions, we approximate the joint data
distribution without any independence assumptions. Evaluated on real-world
datasets and compared against real systems and dominant families of techniques,
our estimator achieves single-digit multiplicative error at tail, an up to
90$\times$ accuracy improvement over the second best method, and is space- and
runtime-efficient.
