Optimizing SQL-based unbounded regular path queries in a relational database

Abstract

Graph processing within relational databases is increasingly gaining attention, as data scientists seek to retrieve information from graphs that are stored in tabular format inside RDBMSs. One particularly challenging class of graph queries that is applicable to a number of scenarios, such as money laundering detection, is unbounded regular path queries (RPQs). However, despite the importance of unbounded RPQs, existing techniques fail to provide sufficient performance, mainly for a lack of integration with the internals of the database engine. To address this problem, a new specialized kernel that is embedded in a relational database was developed. The kernel operates by issuing internal SQL statements during its runtime. This SQL statements are critical for its performance, it is thus imperative to handle them efficiently. We propose and implement several techniques to optimize the SQL-based execution of the kernel. Our optimizations yield remarkable results, achieving up to a 67-fold improvement in end-to-end performance compared to the original version of the kernel.