Skip to content

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

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.

View source

Similar papers

Preprint Oct 2026

Scaling Graph Query Processing: Focused Exploration on Partitions Using Load Balancing

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...

Harshit Modi, Abhishek Santra, Sharma Chakravarthy · 0 citations
Open access 2024

HYPERION-Q: A Graph-Guided Self-Validating and Hardware-Aware Framework for High-Performance Query Processing

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 · 1 citation
Book Open access Nov 2026

Cimos: Cost-Effective Multi-Query Oriented Continuous Subgraph Matching

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. · 0 citations
Open access 2025

CODAQ: Context-Oriented Distributed Adaptive Query Processing for Large-Scale Graph and Data Systems

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 · 4 citations
Preprint Oct 2026

RiftANN: Efficient Graph Traversal for Vector Search with RDMA-Based Memory Disaggregation

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.