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.2582926e-05
Overall Rank: 3,494 | 76.51%
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,992	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	6.8685334e-05
6,467	Output-sensitive Conjunctive Query Evaluation	2024	PODS	5.7747248e-05
7,467	Reservoir Sampling over Joins	2024	SIGMOD	5.5198675e-05
7,513	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	5.5049463e-05
8,279	Subset Sampling over Joins	2026	PODS	5.3637624e-05
8,886	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.2559789e-05
9,224	An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication	2025	PODS	5.2056825e-05
10,386	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	4.9793485e-05
10,387	Towards Parameterized Hardness on Maintaining Conjunctive Queries	2026	PODS	4.9793485e-05
10,700	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.9793485e-05
11,068	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.9793485e-05
11,536	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9793485e-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.00040108301
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029866033
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029627449
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021246
750	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014265196
795	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013938779
1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.9088372e-05
1,690	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.8609347e-05
1,812	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5803973e-05
1,891	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4184294e-05
2,456	A Sampling Algebra for Aggregate Estimation	2013	VLDB	8.4377192e-05
2,757	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.0525756e-05
4,642	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.4898745e-05
4,698	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	6.4640177e-05
5,487	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	6.1096421e-05
5,489	Compressed Representations of Conjunctive Query Results	2018	PODS	6.1095111e-05
5,657	PGMJoins: Random Join Sampling with Graphical Models	2021	SIGMOD	6.0488437e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,660	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
2	10,387	Towards Parameterized Hardness on Maintaining Conjunctive Queries	2026	PODS
3	8,279	Subset Sampling over Joins	2026	PODS
4	11,068	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,467	Reservoir Sampling over Joins	2024	SIGMOD
8	315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS
9	3,992	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
10	10,386	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS