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.2308675e-05
Overall Rank: 3,502 | 76.53%
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
4,011	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	6.842581e-05
6,482	Output-sensitive Conjunctive Query Evaluation	2024	PODS	5.7529053e-05
7,490	Reservoir Sampling over Joins	2024	SIGMOD	5.499011e-05
7,537	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	5.4841462e-05
8,300	Subset Sampling over Joins	2026	PODS	5.3434957e-05
8,915	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.2361195e-05
9,258	An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication	2025	PODS	5.1860131e-05
10,464	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	4.9605343e-05
10,465	Towards Parameterized Hardness on Maintaining Conjunctive Queries	2026	PODS	4.9605343e-05
10,771	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.9605343e-05
11,138	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.9605343e-05
11,591	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9605343e-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.0003999751
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029805026
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029532435
318	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021178303
752	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014234789
793	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013903938
1,681	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.8821344e-05
1,695	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.8317087e-05
1,821	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5466386e-05
1,896	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4010932e-05
2,461	A Sampling Algebra for Aggregate Estimation	2013	VLDB	8.4123214e-05
2,766	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.0221503e-05
4,661	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.4656621e-05
4,714	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	6.4395938e-05
5,512	Compressed Representations of Conjunctive Query Results	2018	PODS	6.0867282e-05
5,514	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	6.0866191e-05
5,671	PGMJoins: Random Join Sampling with Graphical Models	2021	SIGMOD	6.026372e-05

Semantically Similar Papers

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