Source-linked AI summary
Learned Cardinalities: Estimating Correlated Joins with Deep Learning
Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, Alfons Kemper
TL;DR
Cardinality estimation is difficult because optimizers depend on estimates that can fail on correlations and selective predicates. The paper introduces MSCN, a set-based supervised deep-learning estimator, and finds robust IMDb performance with a small footprint, while generalization and complex predicates remain limited.
Problem
Cardinality estimation remains inaccurate because existing methods struggle with join-crossing correlations and cases where no sampled tuples qualify.
Method
MSCN represents tables, joins, and predicates as sets, processes their elements with shared neural networks, and incorporates sample-derived features.
Results
On IMDb, MSCN is more robust than sampling-based techniques and competitive in their favorable regime, using about 3 MiB.
Takeaways & Limitations
MSCN provides a first step toward reliable machine-learning cardinality estimation and can extend to complex predicates, uncertainty estimation, and updatability.
Takeaways & Limitations
Generalization remains challenging for queries far from the training data, and complex predicate types unseen during training are unsupported.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Cardinality estimation is central to query optimization but remains unreliable, especially for join-crossing correlations and selective predicates. The paper proposes MSCN to learn these correlations and reports robust performance on IMDb.
- Cardinality estimates guide query-plan selection, yet widely used systems can be wrong by orders of magnitude.
- Join-crossing correlations, such as relationships between actor nationality and movie genre, are the biggest estimation challenge.
- Sampling methods can fail when selective predicates yield no qualifying samples or suitable indexes are unavailable.
- MSCN uses supervised deep learning to predict query cardinalities and learn join-crossing correlations without changing join enumeration or cost modeling.
- On the real-world IMDb dataset, MSCN is more robust than sampling methods and competitive where those methods perform best.The model achieves this with a configurable footprint of about 3 MiB.
2 RELATED WORK
Prior work applies machine learning to database systems and cardinality estimation, while sampling-based estimators remain limited in handling join-crossing correlations and zero-tuple cases.
- This work uses supervised learning for cardinality estimation rather than reinforcement learning for join ordering.
- The focus isolates cardinality estimation because modern enumeration algorithms can optimize join orders for queries with dozens of relations.
- Earlier neural and regression approaches did not use deep learning or statistics-derived features such as sample-based bitmaps.
- Sampling proposals work well for single-table queries but do not capture join-crossing correlations and remain vulnerable to the 0-tuple problem.
3 LEARNED CARDINALITIES
The paper represents relational queries as sets of tables, joins, and predicates, then applies permutation-invariant neural processing to predict cardinalities. Training combines generated queries with sample-derived features.
- Set-Based Query Representation: A query is represented as three sets: participating tables, joins, and predicates.
- Set-Based Query Representation: Tables and joins use one-hot encodings, while predicates encode columns, operators, and normalized values.
- Enriching the Training Data: The model augments query features with qualifying-sample counts or bitmaps so it can learn patterns associated with join partners.
- Model: MSCN applies shared per-element neural networks to each set, averages transformed elements, concatenates set representations, and feeds them to an output network.
- Model: Averaging set elements preserves permutation invariance and eases generalization to sets with different numbers of elements.
- Training: Target cardinalities are logarithmized and normalized, while training minimizes mean q-error using Adam.
- Generating Training Data: To address cold start, training queries are generated from schema information and literals drawn from actual database values.
- Limitations: Changing data can require complete retraining when the training-set minimum or maximum values change.
4 EVALUATION
Evaluation uses the correlated IMDb dataset and multiple synthetic and benchmark workloads to assess estimation errors and generalization. Comparisons include PostgreSQL, random sampling, and index-based join sampling.
- Dataset: IMDb contains more than 2.5 M movie titles, 234,997 companies, and over 4 M actors across 133 years.
- Workloads: The evaluation includes a 5,000-query synthetic workload, a 500-query workload for more joins, and a 70-query JOB-light workload.
- Experimental Setup: The workloads and experiments examine estimation behavior across varying join counts and query settings.
- Error Analysis: Figure 3 summarizes synthetic-workload q-errors using box boundaries at the 25th and 75th percentiles and whiskers at the 95th percentile.
- Baselines: Competitors are PostgreSQL, Random Sampling, and Index-Based Join Sampling.
4.1 Estimation Quality
MSCN is competitive with established estimators and more robust to empty samples and extreme errors. Its strongest advantage appears in the tail of the error distribution, while IBJS retains the best median estimates.
- MSCN is competitive with IBJS at the median while being significantly more robust to empty base-table samples.IBJS performs extremely well at the median and 75th percentile but suffers when base-table samples are empty.
- Up to two orders of magnitude: MSCN outperforms competing estimators at the end of the q-error distribution.IBJS provides the best median estimates, but MSCN performs better in the distribution tail.
- 376 queries, or 22% of the synthetic workload’s 1,636 base-table queries, have empty samples.The experiment compares MSCN with Random Sampling and PostgreSQL on this subset.
- MSCN addresses the weak spot of purely sampling-based techniques and would complement them well in empty-sample situations.Random Sampling must fall back to an educated guess when no qualifying samples exist, whereas MSCN can use individual query-feature signals.
4.3 Removing Model Features
Removing runtime sampling features leaves MSCN with reasonable estimates, while adding sample cardinalities and then bitmaps progressively improves prediction quality, especially for joins.
- Model variants: MSCN without samples achieves an overall 95th percentile q-error of 25.3 using only inexpensive query features.This variant removes runtime sampling features from the model.
- Model variants: Adding sample cardinalities reduces 95th percentile q-errors by 1.72× for base tables, 3.60× for one join, and 3.61× for two joins.The model uses one qualifying-sample cardinality per base table.
- Model variants: Replacing cardinalities with bitmaps further improves 95th percentile q-errors by 1.47× for base tables, 1.35× for one join, and 1.04× for two joins.The full bitmap model uses one bitmap per base table.
- Model variants: Bitmap patterns provide information that the model can use to produce better cardinality estimates.The bitmaps encode which sampled tuples qualify and can reveal patterns associated with many join partners.
4.4 Generalizing to More Joins
MSCN generalizes beyond its training range to queries with more joins and to workloads with different predicate distributions, although error increases for larger unseen queries and outliers beyond training cardinalities matter.
- More joins: Breaking larger queries into subqueries requires assuming independence between subqueries, which can produce poor estimates on IMDb.This motivates evaluating MSCN directly on queries with more joins.
- More joins: MSCN was trained on queries with zero to two joins but evaluated on scale-workload queries with up to four joins.The experiment tests generalization to three- and four-join queries without training on such queries.
- More joins: 38.6: MSCN’s 95th percentile q-error rises from 7.66 for two joins to 38.6 for three joins, versus PostgreSQL’s 78.0.With four joins, MSCN reaches 2,397 versus PostgreSQL’s 4,077.
- More joins: 58 of 500 queries exceed the maximum cardinality seen during training, including 12 three-join and 46 four-join queries.Excluding these outliers reduces the three- and four-join 95th percentile q-errors to 23.8 and 175.
- JOB-light: MSCN generalizes to JOB-light despite predicate distributions differing from the training data.JOB-light includes mostly equality predicates and closed production_year ranges, while training used a uniform mix of equality and open-range predicates.
4.6 Hyperparameter Tuning
The authors tune epochs, batch size, hidden units, and learning rate, finding a robust default configuration while observing overfitting with longer training.
- The authors varied epochs, batch sizes, hidden units, and learning rates across 72 configurations, training each configuration three times.They used 90,000 training samples and evaluated on 10,000 validation samples.
- The best validation configuration used 100 epochs, batch size 1024, and 256 hidden units, with learning rate fixed at 0.001.
- Across many settings, 100 epochs outperformed 200 because longer training caused overfitting that reduced prediction quality.
- The mean q-error varied by only 1% among the best 10 configurations but by 21% between the best and worst configurations.
- The default configuration is 100 epochs, batch size 1024, 256 hidden units, and learning rate 0.001.
4.7 Model Costs
MSCN converges quickly enough for practical training, offers millisecond-scale prediction, and has a small serialized model footprint; directly optimizing mean q-error is most reliable.
- Fewer than 75 training passes reduce mean q-error to around 3 on 10,000 validation queries.An average 100-epoch training run takes almost 39 minutes.
- Prediction takes a few milliseconds, including PyTorch overhead.The authors expect optimized implementations to achieve very low prediction latencies using GPU-accelerated matrix multiplication.
- Serialized model sizes are 1.6 MiB for MSCN without samples, 1.6 MiB with sample counts, and 2.6 MiB with bitmaps.
- Optimizing mean q-error outperformed mean-squared error and was more reliable than optimizing geometric mean q-error.Geometric mean q-error places less emphasis on heavy outliers.
5 DISCUSSION
The discussion presents MSCN as effective for cardinality estimation while outlining boundaries around generalization, predicate support, uncertainty estimation, database updates, and bitmap-based extensions.
- Discussion: MSCN beats state-of-the-art cardinality estimators and addresses 0-tuple situations and join-crossing correlations, especially with runtime sampling.
- Generalization: The model generalizes somewhat to queries with more joins than seen during training, but queries far from the training data remain challenging.
- Adaptive training: Training can use actual workloads or query structures, replacing user-query literals with database-derived placeholders to emphasize joins and predicates.
- Adaptive training: Adaptive sample generation could use validation-set error distributions to target difficult parts of the schema.
- Strings: String equality predicates could be supported by hashing string literals into a small integer domain.
- Complex predicates: Complex predicates such as LIKE and disjunctions are unsupported because they are not represented in the current model.Bitmap-only handling could reintroduce vulnerability to 0-tuple situations and make generalization challenging.
- More bitmaps: Additional per-predicate bitmaps could increase qualifying-sample likelihood and help with arbitrary complex predicates.This approach still fails when none of the predicate bitmaps contains qualifying samples.
- Uncertainty estimation: Uncertainty estimation remains an open, non-trivial research problem, with strict runtime constraints offered as one alternative.
6 CONCLUSIONS
MSCN provides a new deep learning approach for cardinality estimation, learning join-crossing correlations and addressing cases where no samples qualify. The set-based model may also support estimating unique values for group-by operators.
- MSCN learns join-crossing correlations and addresses the weakness of sampling-based techniques when no samples qualify.
- The model is trained with generated queries uniformly distributed within a constrained search space.
- MSCN is presented as a first step toward reliable machine-learning-based cardinality estimation.
- The set-based model can also predict unique values in one or multiple columns, estimating group-by result sizes.