PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zepeng Liu, Xinxin Huang, Xuanming Liu, Sheng Wang, Zhiyong Peng

arXiv:2608.31027v1cs.DB

TL;DR

Graph-relational systems need benchmarks that evaluate relational and graph operations together, while existing suites offer limited integrated and component-level coverage. GRBench constructs a scalable real-world workload and controlled equivalent queries, finding substantial design trade-offs without one architecture consistently dominating all workloads.

  • Problem

    Existing benchmarks largely isolate relational and graph models or provide limited graph-relational coverage, leaving systematic evaluation of integrated execution and optimization insufficient.

  • Method

    GRBench builds a linked, consistently scaled SciSciNet-v2 schema, organizes controlled query series, and evaluates semantically equivalent native formulations across representative systems.

  • Results

    The evaluation reveals substantial differences across storage, execution, and optimization designs, with no single architecture consistently dominating all workloads.

  • Takeaways & Limitations

    GRBench identifies design trade-offs and open challenges for future graph-relational system design and optimization.

  • Takeaways & Limitations

    The benchmark excludes highly concurrent OLTP, distributed execution, aggregation-heavy hybrid analytics, and graph algorithm workloads.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Graph-relational workloads combine relational operations with graph processing, but existing benchmarks provide limited integrated coverage and little fine-grained insight into system designs. GRBench addresses these gaps with a real-world linked schema, parameterized GRHQs, controlled query series, and unified evaluation.

  • Motivation: Graph-relational hybrid queries combine relational filtering and joins with graph pattern matching in one logical workload.Relational results can constrain graph search, requiring systems to execute and optimize both models together.
  • Research Gaps: Existing relational and graph benchmarks evaluate their respective models largely in isolation and miss cross-model interactions.Relational benchmarks do not evaluate graph-specific processing, while graph benchmarks primarily target graph-native workloads.
  • Research Gaps: Multi-model benchmarks provide sparse GRHQ coverage, with none of UniBench’s 10 queries and only one of M2Bench’s 17 tasks jointly exercising relational and graph processing.This limits systematic characterization of performance differences across systems.
  • Research Gaps: Existing graph-relational workloads mainly support functional validation and end-to-end latency measurement, lacking controlled series for storage, operators, and optimization.The gap prevents fine-grained evaluation of graph-relational system components.
  • GRBench: GRBench builds a linked SciSciNet-v2 schema, derives consistently scaled instances, defines 24 GRHQs with three selectivity variants, and organizes purpose-built query series.The resulting workload contains 72 parameterized GRHQ instances designed for controlled evaluation.
  • GRBench: GRBench systematically characterizes storage architectures, execution models, optimization techniques, and design trade-offs using unified metrics and semantically equivalent queries.It also identifies open challenges in optimization, graph-aware execution, update consistency, and cross-language usability.

2 RELATED WORK

Prior benchmarks cover relational, graph, multi-model, and heterogeneous-data workloads, but their goals and model combinations differ from systematic execution and optimization evaluation for graph-relational operations.

  • Relational and Graph Benchmarks: Relational benchmarks cover OLTP, OLAP, joins, scans, aggregations, and optimizer evaluation using standardized workloads.TPC-C, TPC-H, TPC-DS, and related benchmarks provide reproducible comparisons across relational operations.
  • Relational and Graph Benchmarks: Synthetic relational benchmark data follows predefined distributions and is less suited to optimizer robustness under real-world correlations and skew.JOB addresses this issue with real-world IMDB data and multi-join SQL queries.
  • Relational and Graph Benchmarks: LDBC benchmarks evaluate transactional graph processing, graph OLAP, pattern matching, traversal, connectivity tests, and updates over graph-native workloads.Their queries operate over a single logical graph dataset or its related representations.
  • Multi-model Benchmarks: Multi-model benchmarks such as BigBench and UniBench combine multiple data models for analytics or application scenarios.These workloads extend beyond a single model but are not described as focused on graph-relational execution and optimization.
  • Adjacent Benchmarks: FDABench and RelBench target data-agent analysis or predictive learning over heterogeneous or relationally connected data.They do not target execution and optimization of relational and graph operations within database systems.

3 DATA MODEL AND EVALUATION SCOPE

GRBench models relational tables and property graphs as distinct but connected representations, then evaluates their interaction through hybrid queries, graph operators, updates, and relational baselines within a centralized scope.

  • Data Model: GRBench treats relational tables and property graphs as separate representations connected through shared identifiers.This separation supports evaluation of interactions across structured records and relationship-centric topology.
  • Data Model: Relational fragments use selection, projection, and joins, with joins linking records across relational tables.Relational data stores structured entities and attributes in tables.
  • Data Model: The graph representation is a property graph whose vertices represent entities, edges represent associations, and queries use pattern matching and shortest-path search.The graph is denoted G = (V, E, λ, ϕ), with labels and properties assigned to vertices and edges.
  • Evaluation Dimensions: GRHQ Capability evaluates whether systems combine relational selection, projection, and joins with graph pattern matching and optimize across both models.It also tests relational-graph interaction within one logical task.
  • Evaluation Dimensions: Operator Scalability tests compatibility with shortest-path search and other graph operators when they participate in hybrid queries with relational joins.The dimension examines operator performance and optimization when relational predicates determine path processing.
  • Evaluation Dimensions: Pure Graph Query Capability isolates graph operator efficiency by removing relational joins while retaining comparable graph structures and patterns.These graph-only queries provide controlled baselines for GRHQ workloads.
  • Evaluation Dimensions: Graph Update Support measures the consistency-maintenance cost of vertex and edge changes across records, topology structures, and auxiliary indexes.Systems use different storage organizations, including edge tables and adjacency indexes.
  • Evaluation Dimensions: Relational-equivalent baselines compare selected graph and hybrid queries with semantically equivalent join-based relational translations.The comparison tests when relational execution is sufficient and when graph processing is necessary.

4 GRBENCH

GRBench builds a scalable graph-relational benchmark from SciSciNet-v2, preserving links between relational records and graph entities. Its workload uses controlled query series and equivalent formulations to evaluate hybrid processing, graph operators, updates, and relational baselines.

  • Benchmark Construction: GRBench transforms SciSciNet-v2 into coordinated relational tables and graphs capturing attributes, citations, collaboration, and other relationships.The benchmark avoids introducing additional data models and focuses on interaction between relational and graph representations.
  • Workload Organization: Five workload series vary query structure and isolate graph-relational, graph-only, update, and relational execution capabilities.The H-series evaluates hybrid processing, S-series shortest-path operators, G-series pure graph matching, U-series updates, and R-series relational equivalents.
  • Schema Design: The coupled schema contains 10 relational tables, 9 vertex labels, and 11 edge-labeled property graphs, with papers and authors linking the two models.The schema supports up to 12 schema-level joins while keeping descriptive attributes relational and relationship-centric records in graphs.
  • Data Scaling: GRBench derives five scale factors from SF=100 to SF=10^4 through subset extraction, producing instances from 488K to 249M papers and 249K to 2.49B reference edges.Retained records preserve real-data attribute correlations, degree skew, and long-tail relationship patterns.
  • H-series: The H-series uses a 2 × 2 × 2 design over join intensity, matched-subgraph count, and graph-pattern depth to study their controlled interaction.Its query variants use average predicate selectivities of 45.19%, 33.15%, and 4.01%.
  • S-series: The S-series evaluates bounded and unbounded shortest paths, path-result composition, and cost-based path search beyond fixed graph-pattern matching.Examples combine shortest-path results with graph-pattern or relational bindings under endpoint filtering and joins.

5 SYSTEM LANDSCAPE

The system landscape spans relational extensions, multi-model databases, and native graph-relational designs. These systems differ in how they store topology, reuse relational execution, add graph-specific operators, and optimize cross-model queries.

  • Relational Extensions: Relational extensions retain relational storage while adding graph interfaces or execution components above an existing relational engine.AGE transforms Cypher into PostgreSQL query-tree nodes, while DuckPGQ defines property graphs over existing typed tables and injects graph structures into DuckDB plans.
  • Graph-native Multi-model Systems: Multi-model systems share storage or execution infrastructure across graph, relational, document, key-value, or object models.AgensGraph combines SQL and openCypher within a PostgreSQL-derived engine, while ArangoDB and OrientDB provide native traversal or link-navigation operators.
  • Native Graph-relational Systems: Native graph-relational designs integrate graph-specific storage and execution mechanisms directly into the database core.Kùzu uses CSR adjacency structures and factorized joins; GRFusion maintains adjacency-list indexes and connects graph scans to relational operators through binding joins.
  • Execution Reuse: Systems reuse relational execution through scans, joins, indexes, planning, parallel UDFs, vectorized functions, and relational plans for bounded graph patterns.Path queries in DuckPGQ can build an on-the-fly CSR representation.
  • Topology-aware Processing: Topology-aware processing uses endpoint or vertex-centric indexes, traversal pruning, native path operators, RID joins, bitmap filters, and factorized graph operators.These mechanisms target graph traversal and pattern execution without relying solely on value-based relational joins.
  • Cross-model Optimization: Cross-model optimization interleaves graph traversal, relational joins, and mappings through graph-specific rewrites or dynamic-programming plan enumeration.RelGo retains an explicit matching operator, while Chimera constructs Traversal-Join graphs for plan search.

6 EXPERIMENTS

The experiments evaluate representative open-source systems using unified latency, speedup, query conciseness, and resource-utilization metrics across controlled graph-relational workloads.

  • Five research questions assess overall performance, graph-query extensibility, pattern-matching efficiency, update processing, and relational-equivalent execution.
  • Systems Under Test: Seven open-source systems are evaluated, including relational extensions, graph databases, and graph-relational systems.The systems include PostgreSQL with AGE, DuckDB with DuckPGQ, ArangoDB, AgensGraph, OrientDB, GRainDB, and Kùzu.
  • Evaluation Metrics: End-to-end latency measures wall-clock time to materialize results, while query-set latency is summarized by geometric mean.
  • Evaluation Metrics: Graph-relational speedup compares equivalent graph and relational queries using L(RQ)/L(Q), with values above one indicating faster graph-based execution.
  • Evaluation Metrics: Query conciseness uses Halstead-style metrics, and resource measurements record average and peak CPU and memory usage during execution.CPU is reported as equivalent utilized cores and memory in GB; these measures distinguish low latency from higher resource consumption.
  • Implementation Details: Experiments use default container configurations, system-specific indexes, and three fixed-order workload runs on a 72-core, 512-GiB server.

6.2 Efficiency on GRHQs (RQ1)

GRBench compares H-series latency across systems at SF=101 using geometric means over three predicate-selectivity variants. Performance depends on query predicates and graph-relational execution architecture.

  • OrientDB achieves the lowest latency in most H-series queries, while PostgreSQL with AGE shows the highest latency in most cases.AGE incurs overhead when graph-derived relations are composed through PostgreSQL joins, especially for multiple graph subqueries or multi-hop patterns.
  • Figure 3 reports geometric-mean latency across three predicate-selectivity variants for each H-series query at SF=101.
  • Exact identifier predicates favor OrientDB because MATCH execution and indexes can locate the starting vertex before traversal.
  • H10–H12 and H22–H24 favor DuckDB, while OrientDB and ArangoDB become less competitive with prefix predicates.Prefix predicates prevent direct binding of a starting vertex before traversal; DuckPGQ executes translated SQL/PGQ patterns within DuckDB’s relational framework.

6.3 Graph Operator Scalability (RQ2)

GRBench evaluates graph operators, pure-graph queries, and graph updates across systems, revealing operator-specific support and execution trade-offs. Performance depends on execution strategy, intermediate results, and storage-update mechanisms.

  • Shortest-path support: GRainDB cannot execute any S-series query because it lacks the required shortest-path semantics, despite supporting variable-length path patterns.This demonstrates that pattern-matching support does not guarantee extensibility to additional graph operators.
  • Shortest-path support: No system dominates S1–S5: Kùzu is fastest on S2, S3, and S5, while OrientDB leads on S1 and S4.Both provide native path operators, whereas DuckPGQ uses on-demand CSR-based vectorized path search.
  • Pure-graph query performance: DuckDB achieves the lowest latency across most G-series queries by lowering graph patterns into its vectorized parallel relational execution framework.PostgreSQL is competitive on selected queries, while AGE incurs overhead processing multiple graph-matching results through cypher().
  • Pure-graph query performance: Graph-native storage or predefined access structures alone do not determine latency; starting predicates, intermediate-result sizes, and execution strategy also matter.Hop depth and matched-subgraph count do not produce monotonic latency growth across G-series queries.
  • Graph updates: DuckDB is fastest on most U-series updates, while Kùzu and GRainDB achieve the best or second-best latency on many tasks.GRainDB consistently outperforms ArangoDB, AgensGraph, and OrientDB, but its deletions are 4.1–6.9× slower than corresponding insertions because it maintains RID references and optional indexes.
  • Graph updates: AGE and AgensGraph do not support standalone vertex deletions in U1 and U2 when incident edges remain.Both systems reject deletion of vertices that still have incident edges.

6.6 Speedup over Relational Equivalents (RQ5)

GRBench compares graph-relational queries with relational equivalents and examines how their relative performance changes with workload and data scale. The results show that graph formulations do not uniformly outperform relational ones, while scaling varies by system and query family.

  • Speedup comparison: PostgreSQL with AGE remains below break-even for every H- and G-series group because graph representation and MATCH execution add overhead over relational storage.AGE translates Cypher into PostgreSQL plans over vertex and edge label tables and represents graph values with agtype.
  • Speedup comparison: DuckDB and ArangoDB remain close to, but mostly below, break-even because their graph formulations use the same base data or access paths as relational equivalents while adding processing overhead.DuckPGQ lowers SQL/PGQ patterns into DuckDB plans over the same base tables.
  • Speedup comparison: Kùzu’s speedup is set to 1 as a reference because it exposes only a Cypher-based graph interface and lacks a semantically equivalent relational formulation.The comparison therefore does not measure an observed graph-versus-relational speedup for Kùzu.
  • Data-scale impact: DuckDB shows the most stable scaling across representative H-, G-, and R-series workloads as scale increases from SF=100 to SF=10^4.DuckPGQ uses DuckDB’s shared relational execution framework for graph matching and relational operators.
  • Data-scale impact: PostgreSQL exhibits steep latency growth for H-series queries as scale increases, especially on H1–H3 and H16–H18.The increase mainly occurs with larger joins and graph-derived intermediate results that AGE materializes before relational combination.
  • Data-scale impact: DuckDB remains comparatively stable across representative S-series queries, whereas PostgreSQL grows most sharply and ArangoDB deteriorates markedly on S2.DuckPGQ constructs an on-demand CSR representation and uses vectorized shortest-path algorithms.

6.8 Impact of Predicate Selectivity

GRBench varies predicate selectivity across H-, G-, and S-series queries to expose how systems respond to filtering changes. The results show that selectivity sensitivity depends on workload structure and where systems apply filtering during graph-relational execution.

  • Measurement: L(Q_b)/L(Q_a) and L(Q_c)/L(Q_a) quantify latency sensitivity across progressively lower predicate selectivities.Q_a, Q_b, and Q_c are the three selectivity variants for each query Q.
  • Observations: DuckDB cases remain close to one when stricter predicates do not reduce starting sets or prune graph expansion early.Similar scans and fixed-depth patterns continue to dominate execution.
  • Observations: GRainDB reaches 3.54 on G1c after an endpoint-property predicate adds property access and filtering.The result suggests altered filtering or join placement in GRainDB’s predefined relational access path; the exact cause requires execution plans.
  • Observations: S3 produces the strongest selective-variant response in AgensGraph and OrientDB, moderate sensitivity in DuckDB and Kùzu, and little change in PostgreSQL and ArangoDB.S3 places the predicate on the terminal vertex of a three-hop citation pattern before joining graph results with metadata relations.

7 OPEN PROBLEMS

GRBench identifies five open problems for graph-relational data management, beginning with the need to optimize graph and relational processing jointly. The challenges also include extensible graph operators and selectivity-aware optimization.

  • Joint Optimization of Graph and Relational Operators: Joint optimization requires unified cardinality and cost models plus plan search across graph pattern evaluation and graph-relational join orders.H-series performance varies with join count, matched subgraphs, and intermediate-result size.
  • Extensible Graph Operator Integration: Graph operators need common algebraic representations, plan organizations, statistics, and physical interfaces to support extensible optimization.The S-series shows that efficient pattern matching does not necessarily extend to shortest-path processing.
  • Selectivity-aware Optimization: Selectivity-aware optimization requires graph-aware cardinality estimation that tracks predicate effects through starting vertices, expansion, joins, and intermediates.Predicate selectivity causes large, sometimes non-monotonic performance differences across systems.

8 CONCLUSIONS

GRBench combines scalable real-world data, purpose-built query series, and semantically equivalent native formulations to evaluate graph-relational systems. Its results reveal substantial design differences, with no architecture consistently dominating all workloads.

  • Conclusions: No single architecture consistently dominates all workloads across GRBench’s evaluation.The benchmark reveals substantial differences in storage, execution, and optimization designs, highlighting trade-offs for future system development.
Loading 2608.31027v1…