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: 1917
Venue: PODS
Year: 2023
Pagerank: 7.4004131e-05
Overall Rank: 3,453 | 76.32%
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,941	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	7.0074268e-05
6,678	Output-sensitive Conjunctive Query Evaluation	2024	PODS	5.8053953e-05
7,335	Reservoir Sampling over Joins	2024	SIGMOD	5.64193e-05
8,724	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.3766157e-05
8,728	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	5.3766157e-05
9,048	An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication	2025	PODS	5.3251649e-05
9,719	Subset Sampling over Joins	2026	PODS	5.2319816e-05
10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	5.093636e-05
10,170	Towards Parameterized Hardness on Maintaining Conjunctive Queries	2026	PODS	5.093636e-05
10,515	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	5.093636e-05
10,622	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	5.093636e-05
11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	5.093636e-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
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
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
737	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014490983
802	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013907725
1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	0.00010070362
1,673	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	0.00010040854
1,857	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.6047945e-05
1,893	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.5269935e-05
2,413	A Sampling Algebra for Aggregate Estimation	2013	VLDB	8.6116764e-05
2,777	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.1352657e-05
4,630	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.5955933e-05
4,781	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	6.5116536e-05
5,364	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	6.2472125e-05
5,383	Compressed Representations of Conjunctive Query Results	2018	PODS	6.2374576e-05
5,551	PGMJoins: Random Join Sampling with Graphical Models	2021	SIGMOD	6.1782856e-05

Semantically Similar Papers

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