Towards Efficient Random-Order Enumeration for Join Queries

Summary: Presents the first efficient worst-case-guaranteed uniform random-order enumeration algorithm for cyclic joins, with expected delay O(AGM(Q)/|Res(Q)|·log²|Q|). It needs only lightweight indexing, is near-optimal under the k-clique hypothesis, and outperforms prior methods experimentally. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14568
Venue: VLDB
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,622 | 27.13%
DOI: 10.14778/3796195.3796203

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Pengyu Chen (Harbin Engineering University)
2. Zizheng Guo (Harbin Engineering University; Zhengzhou Advanced Research Institute)
3. Jianwei Yang (Harbin Engineering University)
4. Dongjing Miao (Harbin Engineering University)

BibTeX Citation

@article{chen_vldb26,
        title = {{Towards Efficient Random-Order Enumeration for Join Queries}},
        author = {Chen, Pengyu and Guo, Zizheng and Yang, Jianwei and Miao, Dongjing},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {5},
        pages = {889--901},
        doi = {10.14778/3796195.3796203},
        url = {https://doi.org/10.14778/3796195.3796203},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
802	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013907725
1,699	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.975915e-05
1,857	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.6047945e-05
2,468	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	8.5358494e-05
2,777	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.1352657e-05
3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.4004131e-05
3,941	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	7.0074268e-05
5,551	PGMJoins: Random Join Sampling with Graphical Models	2021	SIGMOD	6.1782856e-05
5,804	A Relational Framework for Classifier Engineering	2017	PODS	6.0829486e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB
2	2,996	Fast, Randomized Join-Order Selection—Why Use Transformations?	1994	VLDB
3	499	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB
4	3,941	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
5	7,286	Efficient Computation of Quantiles over Joins	2023	PODS
6	3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS
7	5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB
8	2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
9	6,412	Ranked Enumeration of Join Queries with Projections	2022	VLDB
10	2,777	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS