EUVIMEDEUVIMED entdecken
Crossref

Towards Efficient Random-Order Enumeration for Join Queries

Pengyu Chen, Zizheng Guo, Jianwei Yang, Dongjing Miao

Proceedings of the VLDB Endowment · 01.01.2026 · 19 (5) · 889-901

DOI: 10.14778/3796195.3796203 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 05.05.2026. Verfasst von Pengyu Chen und 3 weiteren Autor:innen. Die Arbeit nennt 27 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In many data analysis pipelines, a basic and time-consuming process is to produce join results and feed them into downstream tasks. Numerous enumeration algorithms have been developed for this purpose. To be a statistically meaningful representation of the whole join result, the result tuples are required to be enumerated in uniformly random order. However, existing studies lack an efficient random-order enumeration algorithm with a worst-case runtime guarantee for (cyclic) join queries. In this paper, we develop an efficient random-order enumeration algorithm for join queries with no large hidden constants in its complexity, achieving expected [EQUATION] delay, O (AGM( Q ) log | Q |) total running time after O (| Q | log | Q |)-time index construction, where | Q | is the size of input, AGM( Q ) is the AGM bound, and | Res ( Q )| is the size of the join result. We prove that our algorithm is near-optimal in the worst case, under the combinatorial k -clique hypothesis. Our algorithm requires no query-specific preprocessing and can be flexibly adapted to many common database indexes with only minor modifications. We also devise non-trivial techniques to speed up enumeration and reduce memory usage, and present an experimental study of their impact on our algorithm. The experimental results show that our algorithm, enhanced with the proposed techniques, significantly outperforms existing state-of-the-art methods.

Zitieren

APA

Chen, P., Guo, Z., Yang, J., & Miao, D. (2026). Towards Efficient Random-Order Enumeration for Join Queries. Proceedings of the VLDB Endowment, 19(5), 889-901. https://doi.org/10.14778/3796195.3796203

Vancouver

Chen P, Guo Z, Yang J, Miao D. Towards Efficient Random-Order Enumeration for Join Queries. Proceedings of the VLDB Endowment. 2026;19(5):889-901. doi:10.14778/3796195.3796203

BibTeX
@article{Chen2026,
  author = {Chen, Pengyu and Guo, Zizheng and Yang, Jianwei and Miao, Dongjing},
  title = {Towards Efficient Random-Order Enumeration for Join Queries},
  journal = {Proceedings of the VLDB Endowment},
  year = {2026},
  volume = {19},
  number = {5},
  pages = {889--901},
  doi = {10.14778/3796195.3796203}
}
Kostenlos starten →