Please note: This PhD seminar will be given online.
Amine Mhedhbi, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Semih Salihoglu
Querying graph-structured relations, i.e., those with many-to-many (m-n) relationships between entities, is ubiquitous and integral to a wide range of analytical applications such as recommendations on social networks and fraud detection in financial transactional networks. These queries are heavy on joins, can be broadly categorized as cyclic and acyclic, and tend to be challenging as they produce large intermediate results. For cyclic queries, the large intermediate results can be unnecessary and due to the suboptimality of the most common core join algorithms being binary joins. For acyclic queries, while the large intermediate results are part of the final results they contain a lot of redundancy.
In this talk, I first review two algorithmic solutions to handle the large intermediate results challenge: 1) worst-case optimal joins; and 2) factorized representations. I will present a comprehensive query processor design and implementation that integrates the two solutions and go over various research questions tackled to make the integration possible and efficient. Our query processor is capable of having a robust query plan space with many efficient plans that lead to orders of magnitude speedups. We further implement a dynamic programming query optimizer backed with extra optimization rules to pick efficient plans.