# Sketched Sum-Product Networks for Joins

arXiv: https://arxiv.org/abs/2506.14034 · HTML: https://mlsanity.com/paper/2506.14034/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 57 references that are in the map.
- First posted on arXiv 16 Jun 2025.

## Builds on (most cited first, 14 of 14)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [MADE: Masked Autoencoder for Distribution Estimation](https://mlsanity.com/paper/1502.03509/) (2015)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation](https://mlsanity.com/paper/2109.05877/) (2021)
- [The Randomized Dependence Coefficient](https://mlsanity.com/paper/1304.7717/) (2013)
- [FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation](https://mlsanity.com/paper/2011.09022/) (2020)
- [A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation](https://mlsanity.com/paper/2107.12295/) (2021)
- [FactorJoin: A New Cardinality Estimation Framework for Join Queries](https://mlsanity.com/paper/2212.05526/) (2022)
- [ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads (Extended)](https://mlsanity.com/paper/2310.05349/) (2023)
- [BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation](https://mlsanity.com/paper/2012.14743/) (2020)
- [Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries](https://mlsanity.com/paper/2402.15953/) (2024)
- [A Unified Model for Cardinality Estimation by Learning from Data and Queries via Sum-Product Networks](https://mlsanity.com/paper/2505.08318/) (2025)
- [The Power of Hashing with Mersenne Primes](https://mlsanity.com/paper/2008.08654/) (2020)

## Abstract (arXiv)

Sketches have shown high accuracy in multi-way join cardinality estimation, a critical problem in cost-based query optimization. Accurately estimating the cardinality of a join operation -- analogous to its computational cost -- allows the optimization of query execution costs in relational database systems. However, although sketches have shown high efficacy in query optimization, they are typically constructed specifically for predefined selections in queries that are assumed to be given a priori, hindering their applicability to new queries. As a more general solution, we propose for Sum-Product Networks to dynamically approximate sketches on-the-fly. Sum-Product Networks can decompose and model multivariate distributions, such as relations, as linear combinations of multiple univariate distributions. By representing these univariate distributions as sketches, Sum-Product Networks can combine them element-wise to efficiently approximate the sketch of any query selection. These approximate sketches can then be applied to join cardinality estimation. In particular, we implement the Fast-AGMS and Bound Sketch methods, which have successfully been used in prior work, despite their costly construction. By accurately approximating them instead, our work provides a practical alternative to apply these sketches to query optimization.