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: 6193
Venue: SIGMOD
Year: 2021
Pagerank: 5.2547498e-05
Overall Rank: 5,952 | 58.64%
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,269	Learned Cardinality Estimation: An In-depth Study	2022	SIGMOD	7.3026051e-05
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
6,860	Detect, Distill and Update: Learned DB Systems Facing Out of Distribution Data	2023	SIGMOD	4.9008421e-05
7,920	JoinBoost: Grow Trees Over Normalized Data Using Only SQL	2023	VLDB	4.6120304e-05
9,841	Machine Unlearning in Learned Databases: An Experimental Analysis	2024	SIGMOD	4.2685233e-05
10,336	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.1905499e-05
10,491	FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network	2025	SIGMOD	4.1905499e-05
10,984	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.1905499e-05
11,287	Approximate Queries over Concurrent Updates	2023	VLDB	4.1905499e-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.00092569117
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
216	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00033560137
606	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00019251186
832	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016089705
905	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00015423174
941	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015147831
974	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00014882804
1,161	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013579831
1,172	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00013504249
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
1,425	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012044433
1,536	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00011458359
2,494	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	8.6457436e-05
2,589	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	8.4868591e-05
2,779	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.1314377e-05
5,799	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR	5.3219666e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
373	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354685
3,053	Fast, Randomized Join-Order Selection — Why Use Transformations?	1994	VLDB	7.6482987e-05
11,703	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD	4.1905499e-05
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1871115e-05
10,254	Secure Multi-Party Sampling over Joins	2026	VLDB	4.1905499e-05
5,085	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.7040225e-05
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
8,964	Reservoir Sampling over Joins	2024	SIGMOD	4.4163852e-05
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
11,456	XLJoins	2021	SIGMOD	4.1905499e-05