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: 6192
Venue: SIGMOD
Year: 2021
Pagerank: 5.2592385e-05
Overall Rank: 5,951 | 58.61%
DOI: 10.1145/3448016.3457302

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,266	Learned Cardinality Estimation: An In-depth Study	2022	SIGMOD	7.3074684e-05
4,953	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8085795e-05
6,879	Detect, Distill and Update: Learned DB Systems Facing Out of Distribution Data	2023	SIGMOD	4.8971368e-05
7,920	JoinBoost: Grow Trees Over Normalized Data Using Only SQL	2023	VLDB	4.6163888e-05
9,852	Machine Unlearning in Learned Databases: An Experimental Analysis	2024	SIGMOD	4.2714575e-05
10,324	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.1945683e-05
10,481	FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network	2025	SIGMOD	4.1945683e-05
10,981	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.1945683e-05
11,285	Approximate Queries over Concurrent Updates	2023	VLDB	4.1945683e-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	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
217	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00033536712
608	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00019235898
834	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016135159
910	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00015423056
943	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015145883
980	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00014879747
1,167	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00013547713
1,204	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013319541
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
1,425	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012051353
1,547	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00011442359
2,501	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	8.6453446e-05
2,588	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	8.4909562e-05
2,779	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.1320575e-05
6,230	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR	5.145989e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
372	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354779
3,048	Fast, Randomized Join-Order Selection — Why Use Transformations?	1994	VLDB	7.6543116e-05
10,254	Secure Multi-Party Sampling over Joins	2026	VLDB	4.1945683e-05
11,698	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD	4.1945683e-05
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1897043e-05
5,104	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.6946113e-05
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
8,959	Reservoir Sampling over Joins	2024	SIGMOD	4.4206222e-05
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
11,453	XLJoins	2021	SIGMOD	4.1945683e-05