NeuroCard: One Cardinality Estimator for All Tables

Abstract

Query optimizers rely on accurate cardinality estimates to produce good execution plans. Despite decades of research, existing cardinality estimators are inaccurate for complex queries, due to making lossy modeling assumptions and not capturing inter-table correlations. In this work, we show that it is possible to learn the correlations across all tables in a database without any independence assumptions. We present NeuroCard, a join cardinality estimator that builds a single neural density estimator over an entire database. Leveraging join sampling and modern deep autoregressive models, NeuroCard makes no inter-table or inter-column independence assumptions in its probabilistic modeling. NeuroCard achieves orders of magnitude higher accuracy than the best prior methods (a new state-of-the-art result of 8.5$\times$ maximum error on JOB-light), scales to dozens of tables, while being compact in space (several MBs) and efficient to construct or update (seconds to minutes).

arXiv commentVLDB 2021

References in corpus (8)

• WaveNet: A Generative Model for Raw Audio
• Neo: A Learned Query Optimizer
• MADE: Masked Autoencoder for Distribution Estimation
• Deep Unsupervised Cardinality Estimation
• Learning to Optimize Join Queries With Deep Reinforcement Learning
• SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning
• On the Expressive Efficiency of Sum Product Networks
• Autoregressive Energy Machines

Cited by in corpus (7)

• Balsa: Learning a Query Optimizer Without Expert Demonstrations
• Towards Dynamic and Safe Configuration Tuning for Cloud Databases
• Electra: Conditional Generative Model based Predicate-Aware Query Approximation
• Flow-Loss: Learning Cardinality Estimates That Matter
• A Unified Transferable Model for ML-Enhanced DBMS
• LMKG: Learned Models for Cardinality Estimation in Knowledge Graphs
• Simpli-Squared: A Very Simple Yet Unexpectedly Powerful Join Ordering Algorithm Without Cardinality Estimates