Jul 2026· Proceedings of the VLDB Endowment· Vol 19, pp. 3344-3356· 0 citations· 33 references
Computer Science
TL;DR
Nav-Index is presented, an adaptive index for relational DBMS that accelerates large-scale shortest path queries with seamless integration into SQL and relational algebra and outperforms all other database systems that have been tested by orders of magnitude.
Abstract
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.
The focus of this paper is on query processing and not search (approximate or exact). The goal is to find all or k answers and the expressiveness of a query (as opposed to a search expression which is typically simpler) is considered important. Although SQL query processing has matured over the last several decades, qu...
Modern data management systems must simultaneously address three critical challenges: efficient query optimization for large queries, reliable detection of logical errors in database engines, and high-performance processing across heterogeneous hardware
architectures. Traditional query optimizers rely on dynamic progra...
Praveen Kumar Kumbum, Ramachandra Reddy Vangala· Journal of Data Science and...· 1 citation
Continuous subgraph matching over dynamic graphs is a fundamental problem in graph databases, with broad applications in real-time pattern monitoring and risk control. In practice, applications often require monitoring multiple graph patterns simultaneously, making multi-query oriented continuous subgraph matching (MCS...
Zi-Qi Zou, Kang-Fei Zhao, Qiyan Li et al.· Proceedings of the 35th ACM...· 0 citations
Modern data-driven applications increasingly rely on distributed graph databases and machine learning pipelines to extract knowledge from massive datasets. However, efficient query processing in distributed environments remains challeng-ing due to
issues such as graph partitioning inefficiencies, dynamic connectivity u...
Praveen Kumar Kumbum, Ramachandra Reddy Vangala· Journal of Business Intellig...· 4 citations
Graph indexes for billion-scale vector collections can exceed a single server's DRAM capacity. Passive RDMA-based disaggregated memory provides scalable capacity without memory-node computation, but conventional best-first search performs poorly in this setting. Fine-grained and unnecessary remote reads increase commun...
Qi Lin, Zhen-Yu Zhang, Jun Kong et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.