# FactorJoin: A New Cardinality Estimation Framework for Join Queries

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 79 references that are in the map.
- First posted on arXiv 11 Dec 2022.

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

- [Neo: A Learned Query Optimizer](https://mlsanity.com/paper/1904.03711/) (2019)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [An End-to-End Learning-based Cost Estimator](https://mlsanity.com/paper/1906.02560/) (2019)
- [Deep Unsupervised Cardinality Estimation](https://mlsanity.com/paper/1905.04278/) (2019)
- [Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation](https://mlsanity.com/paper/2109.05877/) (2021)
- [Deep Reinforcement Learning for Join Order Enumeration](https://mlsanity.com/paper/1803.00055/) (2018)
- [Plan-Structured Deep Neural Network Models for Query Performance Prediction](https://mlsanity.com/paper/1902.00132/) (2019)
- [FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation](https://mlsanity.com/paper/2011.09022/) (2020)
- [Flow-Loss: Learning Cardinality Estimates That Matter](https://mlsanity.com/paper/2101.04964/) (2021)
- [A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation](https://mlsanity.com/paper/2107.12295/) (2021)
- [Size bounds and query plans for relational joins](https://mlsanity.com/paper/1711.03860/) (2017)
- [A Unified Transferable Model for ML-Enhanced DBMS](https://mlsanity.com/paper/2105.02418/) (2021)
- [One Model to Rule them All: Towards Zero-Shot Learning for Databases](https://mlsanity.com/paper/2105.00642/) (2021)
- [Multi-Attribute Selectivity Estimation Using Deep Learning](https://mlsanity.com/paper/1903.09999/) (2019)
- [An Approach Based on Bayesian Networks for Query Selectivity Estimation](https://mlsanity.com/paper/1907.06295/) (2019)
- [FSPN: A New Class of Probabilistic Graphical Model](https://mlsanity.com/paper/2011.09020/) (2020)
- [What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?](https://mlsanity.com/paper/1612.02503/) (2016)

## Built on by (most cited first, 13 of 13)

- [PRICE: A Pretrained Model for Cross-Database Cardinality Estimation](https://mlsanity.com/paper/2406.01027/) (2024)
- [A Practical Theory of Generalization in Selectivity Learning](https://mlsanity.com/paper/2409.07014/) (2024)
- [GenJoin: Conditional Generative Plan-to-Plan Query Optimizer that Learns from Subplan Hints](https://mlsanity.com/paper/2411.04525/) (2024)
- [DistJoin: A Decoupled Join Cardinality Estimator based on Adaptive Neural Predicate Modulation](https://mlsanity.com/paper/2503.08994/) (2025)
- [Data-Agnostic Cardinality Learning from Imperfect Workloads](https://mlsanity.com/paper/2506.16007/) (2025)
- [Is it Bigger than a Breadbox: Efficient Cardinality Estimation for Real World Workloads](https://mlsanity.com/paper/2510.03386/) (2025)
- [Optimize Cardinality Estimation Model Pretraining by Simplifying the Training Datasets](https://mlsanity.com/paper/2502.14350/) (2025)
- [Sketched Sum-Product Networks for Joins](https://mlsanity.com/paper/2506.14034/) (2025)
- [A Lightweight Learned Cardinality Estimation Model](https://mlsanity.com/paper/2508.09602/) (2025)
- [ZeroCard: Cardinality Estimation with Zero Dependence on Target Databases -- No Data, No Query, No Retraining](https://mlsanity.com/paper/2510.07983/) (2025)
- [CoLSE: A Lightweight and Robust Hybrid Learned Model for Single-Table Cardinality Estimation using Joint CDF](https://mlsanity.com/paper/2512.12624/) (2025)
- [TiCard: Deployable EXPLAIN-only Residual Learning for Cardinality Estimation](https://mlsanity.com/paper/2512.14358/) (2025)
- [Towards Anticipatory Databases Through Shared Data and Workload Semantics](https://mlsanity.com/paper/2609.14255/) (2026)

## Abstract (arXiv)

Cardinality estimation is one of the most fundamental and challenging problems in query optimization. Neither classical nor learning-based methods yield satisfactory performance when estimating the cardinality of the join queries. They either rely on simplified assumptions leading to ineffective cardinality estimates or build large models to understand the data distributions, leading to long planning times and a lack of generalizability across queries. In this paper, we propose a new framework FactorJoin for estimating join queries. FactorJoin combines the idea behind the classical join-histogram method to efficiently handle joins with the learning-based methods to accurately capture attribute correlation. Specifically, FactorJoin scans every table in a DB and builds single-table conditional distributions during an offline preparation phase. When a join query comes, FactorJoin translates it into a factor graph model over the learned distributions to effectively and efficiently estimate its cardinality. Unlike existing learning-based methods, FactorJoin does not need to de-normalize joins upfront or require executed query workloads to train the model. Since it only relies on single-table statistics, FactorJoin has small space overhead and is extremely easy to train and maintain. In our evaluation, FactorJoin can produce more effective estimates than the previous state-of-the-art learning-based methods, with 40x less estimation latency, 100x smaller model size, and 100x faster training speed at comparable or better accuracy. In addition, FactorJoin can estimate 10,000 sub-plan queries within one second to optimize the query plan, which is very close to the traditional cardinality estimators in commercial DBMS.