التفاصيل البيبلوغرافية
| العنوان: |
Parallel Acyclic Joins: Optimal Algorithms and Cyclicity Separation. |
| المؤلفون: |
Hu, Xiao, Tao, Yufei |
| المصدر: |
Journal of the ACM; Feb2024, Vol. 71 Issue 1, p1-44, 44p |
| مصطلحات موضوعية: |
ALGORITHMS, DATABASES, HYPERGRAPHS, OPEN-ended questions, PARALLEL algorithms |
| مستخلص: |
We study equi-join computation in the massively parallel computation (MPC) model. Currently, a main open question under this topic is whether it is possible to design an algorithm that can process any join with load O(N polylog N/p1/ρ*) — measured in the number of words communicated per machine — where N is the total number of tuples in the input relations, ρ* is the join's fractional edge covering number, and p is the number of machines. We settle the question in the negative for the class of tuple-based algorithms (all the known MPC join algorithms fall in this class) by proving the existence of a join query with ρ* = 2 that requires a load of Ω (N/p1/3) to evaluate. Our lower bound provides solid evidence that the "AGM bound" alone is not sufficient for characterizing the hardness of join evaluation in MPC (a phenomenon that does not exist in RAM). The hard join instance identified in our argument is cyclic, which leaves the question of whether O(N polylog N/p1/ρ*) is still possible for acyclic joins. We answer this question in the affirmative by showing that any acyclic join can be evaluated with load O(N / p1/ρ*), which is asymptotically optimal (there are no polylogarithmic factors in our bound). The separation between cyclic and acyclic joins is yet another phenomenon that is absent in RAM. Our algorithm owes to the discovery of a new mathematical structure — we call "canonical edge cover" — of acyclic hypergraphs, which has numerous non-trivial properties and makes an elegant addition to database theory. [ABSTRACT FROM AUTHOR] |
|
Copyright of Journal of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
