Attempts in Worst-Case Optimal Joins on Relational Data Systems: A Literature Survey
Ayoub Berdai, Dalila Chiadmi · 2023
Binary join algorithms are a very well researched topic in the databases field, but recent progress in establishing tighter bounds over the size of the result of a join query has exposed the suboptimal performance of these widely-used fine-tuned algorithms across various classes of queries. This has motivated the development of a novel category of join algorithms known as Worst-Case Optimal Join (WCOJ) algorithms, showing potential for integration into data analytic systems in which joins are an essential element. Given the growing interest in adopting these algorithms, particularly for the efficient processing of graph queries, this paper presents a literature survey aiming to expound the theoretical background of WCOJ, review existing algorithms, and analyze their methodologies and limitations.