Please note: This PhD seminar will take place in DC 1304.
Anurag Chakraborty, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Semih Salihoğlu
Efficient multi-core parallel processing of recursive queries is critical for achieving good performance in graph database management systems (GDBMSs), as even very simple queries can be computationally expensive. The direct application of the state-of-the-art morsel-driven parallelism approach to specialized operators of GDBMS parallelizes work at the source node level, which can be inadequate, as it can assign the entire work of some queries to a single thread.
We propose an approach that breaks queries into morsels at multiple granularities: (i) source morsels parallelize work at the source node-level; and (ii) frontier morsels parallelize the work of each iteration of a computation from a single source morsel. We further show that our hybrid approach can be enhanced by sharing scans akin to the multi-source breadth-first search algorithm by constructing multi source morsels. We implemented our approach in the Kùzu GDBMS. Our approach achieves robust parallelism under a large variety of workloads and outperforms existing graph and relational DBMSs.