Nav-Index: A High-Performance, Adaptive Index for Shortest Path Queries in RDBMS

Shortest path queries are a fundamental operation on graphs with numerous applications. Efficiently executing shortest path searches in RDBMS is challenging, as graphs can not only be static relations but might also occur as ad-hoc intermediate results of complex analytical queries. Especially single-pair shortest path queries are difficult to accelerate, because they require minimizing the search space and intermediate results cannot be shared e.g. for multiple destinations. To address these challenges, we present Nav-Index, an adaptive index for relational DBMS that accelerates large-scale shortest path queries with seamless integration into SQL and relational algebra. Nav-Index switches adaptively between three modes: an ad-hoc generic mode using Dijkstra's algorithm, an ad-hoc optimized mode for sparse graphs leveraging contraction hierarchies (CH), and a table index mode for static graphs also leveraging CHs.

Graph DBMS typically provide specific implementations for such queries and are valuable for many workloads. In practice, however, existing systems show limited throughput for large-scale graphs such as road networks and offer limited optimization for analytical relational processing. Embedding Nav-Index into an RDBMS allows for a seamless composition with other relational operators, query decorrelation, cost-based optimization, morsel-driven parallelism, and pipelining. In the case of sparse graphs, Nav-Index's CH mode transforms the graph into a contraction hierarchy, allowing algorithmic speedups by orders of magnitude.

We implemented Nav-Index into the compiling RDBMS Umbra and evaluate it extensively on road networks from small cities to the whole planet and social graphs. In our experiments, Nav-Index outperforms all other database systems that we have tested by orders of magnitude due to algorithmic advantages and an efficient implementation. It can index the road network of Europe in under 12 minutes and Earth in less than 68 minutes, allowing planet-scale shortest path queries in milliseconds in a general-purpose RDBMS.