Learned Cardinalities: Estimating Correlated Joins with Deep Learning
By Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, Alfons Kemper. Conference on Innovative Data Systems Research, 2018
483 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing
View Paper: https://www.semanticscholar.org/paper/287050dc91b146768c9d4435e5582fc9975ba84c
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Sanjay Krishnan
- Ken Goldberg
- Tim Kraska
- Ion Stoica
- Hongzi Mao
- Mohammad Alizadeh
- Johannes Gehrke
- Donald Kossmann
In Computer Networks and Communications
- Johannes Gehrke
- Joseph M Hellerstein
- Sanjay Krishnan
- Ion Stoica
- Ken Goldberg
- Mohammad Alizadeh
- Tim Kraska
- Hongzi Mao
In Signal Processing
- Sanjay Krishnan
- Ken Goldberg
- Johannes Gehrke
- Joseph M Hellerstein
- Tim Kraska
- Ion Stoica
- M. Franklin
- Donald Kossmann
Citations in the corpus
- Learning to Optimize Join Queries With Deep Reinforcement Learning (2018, background): “Liu [31] and Kipf [25] use DNNs to learn cardinality estimates.”
- Neo: A Learned Query Optimizer (2019, background): “Other approaches demonstrate how machine learning can be used to achieve better cardinality estimates [20, 43, 44].”
- ALEX: An Updatable Adaptive Learned Index (2019, methodology): “ML in other DB components: Machine learning has been used to improve cardinality estimation [10, 16], query optimization [26], workload forecasting [24], multi-dimensional indexing [27], and data partitioning [35].”
- FLAML: A Fast and Lightweight AutoML Library (2019, background): “, 2019), cardinality and selectivity estimation (Kipf et al., 2019; Dutt et al., 2019), query performance prediction (Marcus & Papaemmanouil, 2019), workload forecasting (Ma et al.”
- Bao: Making Learned Query Optimization Practical (2020, background): “Several works have applied machine learning techniques to these stubborn problems [27, 29, 33, 39, 41, 47, 60, 61, 64].”