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: 6254
Venue: SIGMOD
Year: 2021
Pagerank: 6.1782856e-05
Overall Rank: 5,551 | 61.92%
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,543	Learned Cardinality Estimation: An In-depth Study	2022	SIGMOD	8.4445934e-05
3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.4004131e-05
6,132	Detect, Distill and Update: Learned DB Systems Facing Out of Distribution Data	2023	SIGMOD	5.9660278e-05
6,585	JoinBoost: Grow Trees Over Normalized Data Using Only SQL	2023	VLDB	5.8350362e-05
9,587	Machine Unlearning in Learned Databases: An Experimental Analysis	2024	SIGMOD	5.2525104e-05
10,622	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	5.093636e-05
10,760	FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network	2025	SIGMOD	5.093636e-05
11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	5.093636e-05
11,484	Approximate Queries over Concurrent Updates	2023	VLDB	5.093636e-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
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
131	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00030424509
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
323	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021264788
513	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00017190574
536	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.0001693369
593	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00016027871
715	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00014655327
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014147905
802	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013907725
820	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00013814535
1,064	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012336248
1,071	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012322342
1,799	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.7326398e-05
1,995	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.3403665e-05
2,308	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.7738996e-05
4,789	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR	6.5072039e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,902	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD
2	10,542	Secure Multi-Party Sampling over Joins	2026	VLDB
3	1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
4	3,941	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
5	9,719	Subset Sampling over Joins	2026	PODS
6	54	On Random Sampling over Joins	1999	SIGMOD
7	9,512	Poisson Sampling over Acyclic Joins	2026	SIGMOD
8	7,335	Reservoir Sampling over Joins	2024	SIGMOD
9	802	Random Sampling over Joins Revisited	2018	SIGMOD
10	11,651	XLJoins	2021	SIGMOD