CS Paper Radar

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

Harshit Modi, Abhishek Santra, Sharma Chakravarthy

cs.DB cs.DCcs.IR ·submitted 2026-10-23 00:29 UTC · v1

Abstract

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, query processing over graph data has not received the same attention. Only recently, systems, such as Neo4J, and others have started using graphs for data representation on a large scale. Their approaches and algorithms remain proprietary. In this paper, we address the problem of answering graph queries and their efficient processing on arbitrary-sized graphs. We propose the partitioning of graphs and the use of the distributed paradigm to achieve efficiency and scalability. Our approach takes a subgraph as query input including wild cards and comparison operations. Our partitioned approach leverages focused exploration and distributed processing to achieve the desired parallelism and improve the response time. We also present heuristics to reduce the number of partitions loaded for query processing. We present our partitioning algorithm, distributed processing architecture used, and load balancing for computing query answers. We establish the correctness of the approach in the presence of partitions, compare heuristics for load balancing, and extensive experimental results over large synthetic and real-world graph data sets.

Closest papers

Nearest neighbours by meaning across the whole index.

Relational-Core Graph Analytics Querying graphs at SQL scale, and why the node/edge model is a performance tax, not a truer picture of connected data

cs.DB cs.AIcs.PL ·2026-09-01 ·Gene Zhang
benchmarkposition similarity 0.69
Abstract

A durable assumption holds that graph analytics requires a purpose-built graph engine, and that relational systems are ill-suited to connected data. We argue the opposite for the workloads enterprises actually run. A columnar relational engine fronted by a graph query language matches or exceeds native graph engines on analytical graph queries, and - decisively - scales past the point where in-memory graph engines fail. We further argue that the node/edge property graph is not a more faithful model of connected data but a re-encoding of relationships that already exist explicitly in relational tables; reconstructing them at query time is pure overhead. We present ClickGraph and its Databricks-dialect sibling DeltaGraph, systems that translate Cypher directly onto the native relational schema - the tables, columns, and foreign keys as they already exist - and execute in place on ClickHouse, Databricks, or in-process on lakehouse files, with no import and no separate cluster. Because the output is ordinary SQL, an underperforming query is an open optimization surface: it can be rewritten, and the engine itself extended. We support the argument with a peer system's own published benchmark, in which a columnar engine outruns Neo4j by two-to-four orders of magnitude, and with reproducible measurements across the LDBC Social Network Benchmark suite.

0.19

HorizANN: Elastically Scaling Vector Search with Ghost Edges

cs.DB ·2026-11-14 ·Talika Gupta, Yunqi Li, Aditya Kunte, Claire Lin, Supawit Chockchowwat +3 more
similarity 0.64
Abstract · 14 pages, 11 figures

Approximate nearest neighbor search (ANNS) is fundamental to modern data-intensive AI applications such as retrieval-augmented generation, recommendation systems, and semantic search. Among existing indexing methods, graph-based indexes emerge as the state of the art due to their superior recall-throughput tradeoffs. Scaling these indexes to multiple machines requires partitioning the data and building indexes on each. However, when new machines are added or removed, the data must be repartitioned and the indexes reconstructed from scratch, making horizontal scaling costly at billion scale. In this work, we present HorizANN, a distributed graph-based ANNS system that scales horizontally without requiring full index reconstruction. To achieve this, we introduce ghost edges, a mechanism for preserving cross-partition connectivity as partition boundaries change during repartitioning. By reusing the structural information that would otherwise be discarded during repartitioning, HorizANN avoids costly full index reconstruction. As the index grows from 100M vectors on one worker to 1B vectors on ten workers, HorizANN inserts each 100M vectors within 2.5 hours and sustains 3.4--3.5K queries per second at 0.998 Recall@10.

0.19

Graph Memory for LLM Agents: At What Cost? A Comparative Evaluation of Query, Ingest, and Update Performance Across Graph Database Engines

cs.DB cs.AI ·2026-09-20 ·Donald Nguyen, Gurbinder Gill, Hadi Ahmadi, Christopher J. Rossbach
benchmark similarity 0.63
Abstract

Graph databases are frequently positioned as categorically necessary for connected-data workloads, yet the systems dimension along which they actually differ - query planning, indexing, and data-readiness cost - is rarely isolated from vendor framing. We construct a synthetic, biomedical-shaped property graph (1.02 million nodes, 5.34 million total node and edge rows) and a twenty-query workload spanning neighborhood lookups, bounded paths, set intersections, anti-joins, grouped aggregation, top-k ranking, temporal filters, full scans, and relational joins. We benchmark Corvic AI - a purpose-built columnar query engine underlying Corvic's ontology management layer ("memories")- against seven purpose-built or graph-extension database systems (LoraDB, Ladybug, DuckPGQ, Memgraph, Neo4j, HugeGraph, and FalkorDB) at three graph scales spanning three orders of magnitude. We report query latency geomeans, bulk-ingest throughput, point-update latency, and answer correctness for each system, and we derive a simple total-cost-of-ownership model that expresses the ingest/query trade-off as a function of query volume. Our central finding is that no system in this sample is categorically fastest: a native graph engine (Ladybug) outperforms Corvic AI on narrow, bounded-neighborhood shapes, while Corvic AI is faster on shapes that scan or join a large fraction of the graph, and a system implementing graph query syntax via SQL/PGQ (DuckPGQ) is measurably slower purely due to query-plan choice. The dominant cost differential in our data is not query latency but the cost of making data queryable at all: bulk-ingest throughput varies by three orders of magnitude across engines (5.0k-4.3M rows/s), a gap that a simple crossover-point calculation shows dominates total cost for any workload with fewer than roughly 105 queries per data refresh.

0.13

Cost Characterization of Vertically Partitioned Federated Knowledge Graphs

cs.AI cs.DBcs.IR ·2026-09-12 ·Md Saikat Islam Khan Bappy, Oshani Seneviratne
published similarity 0.63
Abstract · Accepted at DMKG'26: 2nd International Workshop on Data Management for Knowledge Graphs, co-located with ISWC 2026; to appear in CEUR-WS pro…

Knowledge graphs are increasingly distributed across autonomous organizations that share an entity space but own disjoint subsets of relations, forming a vertical partition. Answering a multi-hop query may require combining facts from several silos, making the partitioning strategy a key data management decision that affects communication, indexing, load balance, and query latency. However, the costs associated with different partitioning strategies remain insufficiently studied. We formalize vertical partitioning as a design space and compare four strategies: semantic domain grouping, frequency-balanced partitioning, co-occurrence graph-cut partitioning, and random partitioning. We evaluate them using five metrics: communication cost, candidate index size, cross-silo path length, load balance, and end-to-end query latency. Three of the five prove to be determined by the graph and the silo count rather than by the partition, which reduces the design problem to two conflicting axes, cross-silo path length and load balance. Experiments on MetaQA and PathQuestion use a fixed federated knowledge graph question-answering architecture based on TransE embeddings and a frozen BERT encoder across three silo configurations. By keeping the learning model unchanged, we isolate the effect of partitioning and show that the trade-off between locality and balance holds only where each silo can hold several relations, weakening as the number of silos increases. The study provides practical guidance for deployments constrained by cross-silo reasoning or by silo load.

0.29

GRBench: A Comprehensive Benchmark Evaluation for Graph-relational Data Management

cs.DB ·2026-08-31 ·Zepeng Liu, Xinxin Huang, Xuanming Liu, Sheng Wang, Zhiyong Peng
benchmark similarity 0.63
Abstract

Modern data-intensive applications increasingly require database systems to manage structured records and graph data. This demand gives rise to graph-relational data management, spanning storage, query processing, and optimization across relational and graph data. In response, relational database extensions, multi-model databases, and dedicated graph-relational systems have emerged with diverse architectures. However, evaluation methodologies have not kept pace. Existing relational and graph benchmarks assess the two models largely in isolation, while multi-model benchmarks provide limited coverage of graph-relational workloads. Available graph-relational workloads mainly support functional validation and end-to-end latency measurement, revealing little about how storage, operator, and optimization designs affect performance. To evaluate system capabilities in graph-relational data management, we present GRBench. First, GRBench constructs a linked graph-relational schema from the real-world SciSciNet-v2 dataset and derives scalable instances through consistency-preserving subset extraction. Second, it organizes purpose-built query series for controlled evaluation of query processing and system components. Third, GRBench provides semantically equivalent native query formulations and evaluates representative system architectures through a unified, multidimensional methodology. Based on this evaluation, we analyze design trade-offs and identify open challenges to guide future system design and optimization.

0.26

Traveling with a Map: Reducing the Search Space of Link Traversal Queries Using RDF Shapes

cs.DB ·2026-10-08 ·Bryan-Elliott Tam, Joanna Van Herwegen, Pieter Colpaert, Ruben Verborgh, Ruben Taelman
benchmark similarity 0.62
Abstract

The centralization of web information raises legal and ethical concerns, particularly in social, healthcare, and education applications. Decentralized architectures offer a promising alternative by keeping data closer to its source, yet efficient query processing remains a significant challenge. Link Traversal Query Processing (LTQP) enables querying across decentralized networks but often suffers from long execution times and high data transfer costs due to the large number of HTTP requests involved. Many queries are highly selective with respect to the data model objects distributed across the network. For example, in a social media application where users store heterogeneous data, a query may target only users' posts and comments, ignoring their other information. We refer to such queries as data-model selective. We propose a shape-based pruning approach that relies on shape indexes and a query-shape subsumption algorithm to reduce the search space and thus the number of HTTP requests. We formalize this approach as a link pruning mechanism for LTQP and evaluate it on social media queries from the SolidBench benchmark across multiple metrics. Our results show that shape-based pruning substantially improves query execution time, first-result arrival time, diefficiency, and network usage for data-model selective queries, while having a negligible impact on non-selective data-model queries. These gains cost only a minor increase in triples per shape-index instance. Our approach is also resilient, retaining its benefits even when some data providers do not supply shape indexes. This work demonstrates that shape-based metadata can significantly optimize LTQP in decentralized knowledge graphs for an important class of queries. By exposing such metadata, data providers not only enhance data quality and interoperability but also improve the efficiency of traversal-based query processing.

0.45

AkasicDB: Demonstrating Omni RAG with a Unified Vector-Graph-Relational DBMS

cs.DB cs.AI ·2026-08-10 ·Geonho Lee, Jeongho Park, Donghyoung Han, Min-Soo Kim
published similarity 0.62
Abstract · SIGMOD 2026 demonstration

Recent Retrieval-Augmented Generation (RAG) systems increasingly combine vector retrieval with structured knowledge, such as Graph RAG and Filtered vector search. However, existing database architectures struggle to support such complex RAG workflows efficiently, as they rely on out-of-DB pipelines or in-DB non-native integration, leading to high overhead. This demo paper presents AkasicDB, a database system that natively supports such RAG workflows by jointly executing vector similarity search, graph traversal, and relational filtering within a single execution framework. AkasicDB extends our prior work, Chimera, with native vector support to enable such unified execution. Based on AkasicDB, we demonstrate the first native integration of Vector-Graph-Relational RAG, which we refer to as Omni RAG. Through an interactive chat-style demonstration, users execute and visualize Omni RAG queries, directly experiencing its superior retrieval and reasoning over vector-only approaches while observing the practical limitations of existing database architectures in supporting Omni RAG. A demonstration video is available at https://youtu.be/8d09_dtrEIM

0.72

Distributed Datalog at Scale with Worst-Case Optimal Joins

cs.DB ·2026-10-08 ·Kunting Qi, Yihao Sun, Kristopher Micinski, Thomas Gilray, Sidharth Kumar
similarity 0.62
Abstract

Scalable logic-based analytics are frequently dominated by cyclic multi-way joins over large relational datasets. State-of-the-art systems evaluate these joins through chains of binary joins, incurring substantial overhead from large intermediate relations that must be materialized and redistributed across the network. Worst-Case Optimal Joins (WCOJ) offer a provably superior alternative by evaluating joins one variable at a time, eliminating intermediate blowup. However, existing WCOJ implementations target either shared-memory machines or one-shot, non-recursive queries on dataflow and big-data platforms, leaving WCOJ-based recursive evaluation on distributed-memory HPC systems an open problem. We present, to our knowledge, the first distributed-memory Datalog engine that uses WCOJ for recursive fixpoint evaluation. Our design builds on HyperCube partitioning, which hash-partitions relations along variable-aligned grid dimensions and replicates them along missing dimensions, and extends it from a single shuffle to iterative execution: in every semi-naive iteration, only newly derived tuples are repartitioned and re-replicated, using MPI all-to-all collectives and per-dimension all-gathers over subcube communicators, while the same layout is reused across iterations so that all WCOJ intersections remain rank-local. We evaluate our system on the Aurora and Polaris leadership-class supercomputers at Argonne National Laboratory using graph mining and program analysis benchmarks, demonstrating strong scalability, outperforming state-of-the-art Datalog engines on most benchmarks, and characterizing how partition dimensionality trades runtime against memory feasibility.

0.31