Multi-Attribute Selectivity Estimation Using Deep Learning

Abstract

Selectivity estimation - the problem of estimating the result size of queries - is a fundamental problem in databases. Accurate estimation of query selectivity involving multiple correlated attributes is especially challenging. Poor cardinality estimates could result in the selection of bad plans by the query optimizer. We investigate the feasibility of using deep learning based approaches for both point and range queries and propose two complementary approaches. Our first approach considers selectivity as an unsupervised deep density estimation problem. We successfully introduce techniques from neural density estimation for this purpose. The key idea is to decompose the joint distribution into a set of tractable conditional probability distributions such that they satisfy the autoregressive property. Our second approach formulates selectivity estimation as a supervised deep learning problem that predicts the selectivity of a given query. We also introduce and address a number of practical challenges arising when adapting deep learning for relational data. These include query/data featurization, incorporating query workload information in a deep learning framework and the dynamic scenario where both data and workload queries could be updated. Our extensive experiments with a special emphasis on queries with a large number of predicates and/or small result sizes demonstrates that our proposed techniques provide fast and accurate selective estimates with minimal space overhead.

References in corpus (6)

• An Empirical Investigation of Catastrophic Forgetting in Gradient-Based Neural Networks
• MADE: Masked Autoencoder for Distribution Estimation
• Deep Reinforcement Learning for Join Order Enumeration
• Learned Cardinalities: Estimating Correlated Joins with Deep Learning
• Deep AutoRegressive Networks
• Learning to Optimize Join Queries With Deep Reinforcement Learning

Cited by in corpus (7)

• An Empirical Analysis of Deep Learning for Cardinality Estimation
• Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach
• DeepDB: Learn from Data, not from Queries!
• Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation
• FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation
• Online Sketch-based Query Optimization
• Estimating Cardinalities with Deep Sketches