Learned Cardinalities: Estimating Correlated Joins with Deep Learning

Abstract

We describe a new deep learning approach to cardinality estimation. MSCN is a multi-set convolutional network, tailored to representing relational query plans, that employs set semantics to capture query features and true cardinalities. MSCN builds on sampling-based estimation, addressing its weaknesses when no sampled tuples qualify a predicate, and in capturing join-crossing correlations. Our evaluation of MSCN using a real-world dataset shows that deep learning significantly enhances the quality of cardinality estimation, which is the core problem in query optimization.

CIDR 2019. https://github.com/andreaskipf/learnedcardinalities

References in corpus (7)

• Adam: A Method for Stochastic Optimization
• Overcoming catastrophic forgetting in neural networks
• What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision?
• On Calibration of Modern Neural Networks
• Deep Reinforcement Learning for Join Order Enumeration
• Learning to Optimize Join Queries With Deep Reinforcement Learning
• Sampling-Based Query Re-Optimization

Cited by in corpus (38)

• Neo: A Learned Query Optimizer
• Bao: Learning to Steer Query Optimizers
• Deep Unsupervised Cardinality Estimation
• Balsa: Learning a Query Optimizer Without Expert Demonstrations
• Learning to Optimize Join Queries With Deep Reinforcement Learning
• Towards Dynamic and Safe Configuration Tuning for Cloud Databases
• Correlation Sketches for Approximate Join-Correlation Queries
• FLAML: A Fast and Lightweight AutoML Library
• Opportunistic View Materialization with Deep Reinforcement Learning
• Multi-Attribute Selectivity Estimation Using Deep Learning
• Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach
• Learning to be a Statistician: Learned Estimator for Number of Distinct Values
• Consistent and Flexible Selectivity Estimation for High-Dimensional Data
• Polyjuice: High-Performance Transactions via Learned Concurrency Control
• An End-to-End Learning-based Cost Estimator
• BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation
• Weakly Supervised Clustering by Exploiting Unique Class Count
• DotHash: Estimating Set Similarity Metrics for Link Prediction and Document Deduplication
• How I Learned to Stop Worrying and Love Re-optimization
• LMKG: Learned Models for Cardinality Estimation in Knowledge Graphs
• Machine Learning-based Cardinality Estimation in DBMS on Pre-Aggregated Data
• Joins on Samples: A Theoretical Guide for Practitioners
• A Pluggable Learned Index Method via Sampling and Gap Insertion
• ML-AQP: Query-Driven Approximate Query Processing based on Machine Learning
• Learned Indexes for Dynamic Workloads
• Learning a Partitioning Advisor with Deep Reinforcement Learning
• CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm
• Survive the Schema Changes: Integration of Unmanaged Data Using Deep Learning
• Flexible Operator Embeddings via Deep Learning
• Towards Enhancing Database Education: Natural Language Generation Meets Query Execution Plans
• Efficient Deep Learning Pipelines for Accurate Cost Estimations Over Large Scale Query Workload
• Q-error Bounds of Random Uniform Sampling for Cardinality Estimation
• Uncertainty-aware Cardinality Estimation by Neural Network Gaussian Process
• Privacy-Enhanced Database Synthesis for Benchmark Publishing (Technical Report)
• Online Sketch-based Query Optimization
• A Comparative Exploration of ML Techniques for Tuning Query Degree of Parallelism
• Simpli-Squared: A Very Simple Yet Unexpectedly Powerful Join Ordering Algorithm Without Cardinality Estimates
• EntropyDB: A Probabilistic Approach to Approximate Query Processing