Poisson Sampling over Acyclic Joins

Summary: Introduces near-instance-optimal Poisson sampling for acyclic joins with tuple-specific probabilities, avoiding full materialization via random-access join indexes. Achieves O(|db| + k log |db|) time and a shared basis for sampling and Yannakakis-style processing. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: 7474
Venue: SIGMOD
Year: 2026
Pagerank: 5.2571354e-05
Overall Rank: 9,512 | 34.74%
DOI: 10.1145/3802101

Incoming Non-self Citations Over Time

Authors

1. Liese Bekkers (Hasselt University)
2. Frank Neven (Hasselt University)
3. Lorrens Pantelis (Hasselt University)
4. Stijn Vansummeren (Hasselt University)

BibTeX Citation

@inproceedings{bekkers_sigmod26,
        title = {{Poisson Sampling over Acyclic Joins}},
        author = {Bekkers, Liese and Neven, Frank and Pantelis, Lorrens and Vansummeren, Stijn},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3802101},
        url = {https://dl.acm.org/doi/10.1145/3802101},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,719	Subset Sampling over Joins	2026	PODS	5.2319816e-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
802	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013907725
993	Simulation of Database-Valued Markov Chains Using SimSQL	2013	SIGMOD	0.00012789598
1,122	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.0001209124
2,130	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	9.1244275e-05
2,777	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.1352657e-05
3,155	Query Shredding: Efficient Relational Evaluation of Queries over Nested Multisets	2014	SIGMOD	7.695861e-05
4,553	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6346951e-05
5,529	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.18591e-05
6,434	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.8799421e-05
7,142	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	5.6917227e-05
7,335	Reservoir Sampling over Joins	2024	SIGMOD	5.64193e-05
7,386	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	5.6273882e-05
9,719	Subset Sampling over Joins	2026	PODS	5.2319816e-05
9,720	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	5.2319816e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,622	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB
2	5,551	PGMJoins: Random Join Sampling with Graphical Models	2021	SIGMOD
3	173	Simple Random Sampling from Relational Databases	1986	VLDB
4	10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
5	5,743	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB
6	3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS
7	7,335	Reservoir Sampling over Joins	2024	SIGMOD
8	54	On Random Sampling over Joins	1999	SIGMOD
9	802	Random Sampling over Joins Revisited	2018	SIGMOD
10	9,719	Subset Sampling over Joins	2026	PODS