PGMJoins: Random Join Sampling with Graphical Models

Summary: PGMJoins uses probabilistic graphical models to derive provably uniform samples of join results (n-way key-joins, many-to-many, cyclic/acyclic). Introduces SP-MPA for efficient uniform sampling of the true joint distribution and optimizes graph structure and inference, achieving 2x–28x speedups on TPC-H, JOB, TPC-DS, and Twitter versus prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h6beb076889760477
Venue: SIGMOD
Year: 2021
Pagerank: 6.0461e-05
Overall Rank: 5,657 | 61.98%
DOI: 10.1145/3448016.3457302

Incoming Non-self Citations Over Time

Authors

1. Ali Mohammadi Shanghooshabad (University of Warwick)
2. Meghdad Kurmanji (University of Warwick)
3. Qingzhi Ma (University of Warwick)
4. Michael Shekelyan (University of Warwick)
5. Mehrdad Almasi (University of Warwick)
6. Peter Triantafillou (University of Warwick)

BibTeX Citation

@inproceedings{shanghooshabad_sigmod21,
        title = {{PGMJoins: Random Join Sampling with Graphical Models}},
        author = {Shanghooshabad, Ali Mohammadi and Kurmanji, Meghdad and Ma, Qingzhi and Shekelyan, Michael and Almasi, Mehrdad and Triantafillou, Peter},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457302},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457302},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,342	Learned Cardinality Estimation: An In-depth Study	2022	SIGMOD	8.6074783e-05
3,494	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.2548566e-05
5,715	Detect, Distill and Update: Learned DB Systems Facing Out of Distribution Data	2023	SIGMOD	6.0178585e-05
6,552	JoinBoost: Grow Trees Over Normalized Data Using Only SQL	2023	VLDB	5.7475822e-05
8,952	Machine Unlearning in Learned Databases: An Experimental Analysis	2024	SIGMOD	5.2517414e-05
11,077	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.9769913e-05
11,193	FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network	2025	SIGMOD	4.9769913e-05
11,542	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9769913e-05
11,800	Approximate Queries over Concurrent Updates	2023	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061067652
57	On Random Sampling over Joins	1999	SIGMOD	0.00040095727
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029858107
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029618887
318	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021166957
510	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00017059914
521	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016923519
596	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015782051
731	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00014400356
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.0001409096
795	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013934719
842	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00013535734
1,058	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012224038
1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012074369
1,828	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.547768e-05
2,028	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.1584244e-05
2,354	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.5872598e-05
4,779	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR	6.416435e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,208	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD
2	1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
3	10,734	Secure Multi-Party Sampling over Joins	2026	VLDB
4	3,994	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
5	8,285	Subset Sampling over Joins	2026	PODS
6	57	On Random Sampling over Joins	1999	SIGMOD
7	9,642	Poisson Sampling over Acyclic Joins	2026	SIGMOD
8	7,471	Reservoir Sampling over Joins	2024	SIGMOD
9	795	Random Sampling over Joins Revisited	2018	SIGMOD
10	11,964	XLJoins	2021	SIGMOD