On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms

Summary: Dynamic index for equi-joins using Õ(IN) space and O(1) updates, returning a uniform join sample in Õ(IN^{rho*}/max{1,OUT}) time w.h.p., where rho* is the fractional edge covering number. Shows that under the combinatorial k-clique hypothesis no combinatorial algorithm can output the full join in O(IN^{rho*−ε}) w.h.p. even when OUT ≤ IN^{ε}, thereby justifying the O(IN^{rho*}) worst-case optimal bound. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h835d03a86f12bccb
Venue: PODS
Year: 2023
Pagerank: 7.2548566e-05
Overall Rank: 3,494 | 76.52%
DOI: 10.1145/3584372.3588666

Incoming Non-self Citations Over Time

Authors

1. Shiyuan Deng (Chinese University of Hong Kong)
2. Shangqi Lu (Chinese University of Hong Kong)
3. Yufei Tao (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{deng_pods23,
        address = {New York, NY, USA},
        series = {{PODS} '23},
        title = {{On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms}},
        url = {https://dl.acm.org/doi/10.1145/3584372.3588666},
        doi = {10.1145/3584372.3588666},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Deng, Shiyuan and Lu, Shangqi and Tao, Yufei},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,994	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	6.8652819e-05
6,469	Output-sensitive Conjunctive Query Evaluation	2024	PODS	5.7719911e-05
7,471	Reservoir Sampling over Joins	2024	SIGMOD	5.5172544e-05
7,518	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	5.5023404e-05
8,285	Subset Sampling over Joins	2026	PODS	5.3612232e-05
8,895	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.2534908e-05
9,234	An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication	2025	PODS	5.2032182e-05
10,398	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	4.9769913e-05
10,399	Towards Parameterized Hardness on Maintaining Conjunctive Queries	2026	PODS	4.9769913e-05
10,710	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.9769913e-05
11,077	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.9769913e-05
11,542	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
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
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021236408
749	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014261044
795	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013934719
1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.9056116e-05
1,690	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.8565419e-05
1,813	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5759542e-05
1,892	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4150583e-05
2,455	A Sampling Algebra for Aggregate Estimation	2013	VLDB	8.4377251e-05
2,757	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.0487636e-05
4,644	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.4869417e-05
4,700	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	6.4609577e-05
5,491	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	6.1067499e-05
5,492	Compressed Representations of Conjunctive Query Results	2018	PODS	6.1066968e-05
5,657	PGMJoins: Random Join Sampling with Graphical Models	2021	SIGMOD	6.0461e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,661	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
2	10,399	Towards Parameterized Hardness on Maintaining Conjunctive Queries	2026	PODS
3	8,285	Subset Sampling over Joins	2026	PODS
4	11,077	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB
5	402	Worst-case Optimal Join Algorithms	2012	PODS
6	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
7	7,471	Reservoir Sampling over Joins	2024	SIGMOD
8	315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS
9	3,994	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
10	10,398	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS