Back to search

University of Waterloo

Robust Recursive Query Parallelization in Graph Database Management Systems

Abstract

dc:description.abstract

Recursive joins such as shortest path and variable length path queries are a core feature set of modern graph database management systems (GDBMS). Since these queries tend to be computationally expensive and may suffer from high execution time, they require efficient parallel processing using multiple cores to achieve good performance. Existing work on parallel query processing includes the morsel driven parallelism approach that distributes a unit of work (denoted as “morsel”) to threads for parallel execution. We revisit this technique in the context of parallelization of recursive joins in GDBMS and discuss how the traditional approach of morsel driven query execution is inadequate to tackle recursive join queries. We show how this approach can be modified to better accommodate scalable parallelization of recursive joins. We further describe how this modified parallel query execution approach has been integrated into Kuzu, an embedded disk based columnar GDBMS. Compared to vanilla morsel driven parallelism, our modified parallel query execution approach can be orders of magnitude faster and scales well on multiple cores.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chakraborty, Anurag
Advisor dc:contributor.advisor
  • Salihoglu, Semih

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/21024

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chakraborty, Anurag. Robust Recursive Query Parallelization in Graph Database Management Systems. University of Waterloo, 2024. https://hdl.handle.net/10012/21024