Deep Unsupervised Cardinality Estimation

Abstract

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.

arXiv commentVLDB 2020. Updates since version 1: new title and new/revised content

References in corpus (12)

• Adam: A Method for Stochastic Optimization
• WaveNet: A Generative Model for Raw Audio
• Conditional Image Generation with PixelCNN Decoders
• Neo: A Learned Query Optimizer
• MADE: Masked Autoencoder for Distribution Estimation
• Deep Reinforcement Learning for Join Order Enumeration
• Learned Cardinalities: Estimating Correlated Joins with Deep Learning
• A Deep and Tractable Density Estimator
• Learning to Optimize Join Queries With Deep Reinforcement Learning
• PixelCNN++: Improving the PixelCNN with Discretized Logistic Mixture Likelihood and Other Modifications
• Autoregressive Energy Machines
• How I Learned to Stop Worrying and Love Re-optimization

Cited by in corpus (34)

• Bao: Learning to Steer Query Optimizers
• Database Meets Deep Learning: Challenges and Opportunities
• Are We Ready For Learned Cardinality Estimation?
• Balsa: Learning a Query Optimizer Without Expert Demonstrations
• Qd-tree: Learning Data Layouts for Big Data Analytics
• Towards Dynamic and Safe Configuration Tuning for Cloud Databases
• Correlation Sketches for Approximate Join-Correlation Queries
• ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads (Extended)
• Spitz: A Verifiable Database System
• RadixSpline: A Single-Pass Learned Index
• NeuroCard: One Cardinality Estimator for All Tables
• Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation
• CERT: Finding Performance Issues in Database Systems Through the Lens of Cardinality Estimation
• FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation
• Electra: Conditional Generative Model based Predicate-Aware Query Approximation
• Consistent and Flexible Selectivity Estimation for High-Dimensional Data
• PRICE: A Pretrained Model for Cross-Database Cardinality Estimation
• Fine-Grained Modeling and Optimization for Intelligent Resource Management in Big Data Processing
• Efficient Query Re-optimization with Judicious Subquery Selections
• Flow-Loss: Learning Cardinality Estimates That Matter
• BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation
• How Good are Learned Cost Models, Really? Insights from Query Optimization Tasks
• RelJoin: Relative-cost-based Selection of Distributed Join Methods for Query Plan Optimization
• A Unified Transferable Model for ML-Enhanced DBMS
• LMKG: Learned Models for Cardinality Estimation in Knowledge Graphs
• Updatable Learned Index with Precise Positions
• A General Cardinality Estimation Framework for Subgraph Matching in Property Graphs
• Low Rank Learning for Offline Query Optimization
• One Model to Rule them All: Towards Zero-Shot Learning for Databases
• Q-error Bounds of Random Uniform Sampling for Cardinality Estimation
• Uncertainty-aware Cardinality Estimation by Neural Network Gaussian Process
• Experience-Enhanced Learning: One Size Still does not Fit All in Automatic Database
• A Lightweight Learned Cardinality Estimation Model
• Patterns Count-Based Labels for Datasets