A Graph-native Optimization Framework for Complex Graph Queries

Bingqing Lyu, Xiaoli Zhou, Longbin Lai, Yufan Yang, Yunkai Lou, Wenyuan Yu, Ying Zhang ‡ , Jingren Zhou · 2025

Read A Graph-native Optimization Framework for Complex Graph Queries by Bingqing Lyu, Xiaoli Zhou, Longbin Lai, Yufan Yang, Yunkai Lou, Wenyuan Yu, Ying Zhang ‡ , Jingren Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-22091.txt.

Introduction

Bingqing Lyu and co-authors present a long technical report from 2025 on software that answers hard questions about graph data. Graphs store links between items, and slow queries can hold up large systems. Their framework, called GOpt, plans how a query should run before the system carries it out.

Readers get the full set of planning rules, a guide to how query languages treat matching in different ways, and notes on linking the tool to two backends. Tests on a standard set of graph queries are also covered in depth. The report will help builders of graph systems tune queries with more care and less guesswork.

Catalog record

CREATORBingqing Lyu, Xiaoli Zhou, Longbin Lai, Yufan Yang, Yunkai Lou, Wenyuan Yu, Ying Zhang ‡ , Jingren Zhou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-22091

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Graph-native Optimization Framework for Complex Graph Queries Bingqing Lyu, Xiaoli Zhou, Longbin Lai, Yufan Yang, Yunkai Lou, Wenyuan Yu, Ying Zhang ‡ , Jingren Zhou Abstract . This technical report extends the SIGMOD 2025 paper "A Modular Graph-Native Query Optimization Framework" by providing a comprehensive exposition of \gopt ’s advanced technical mechanisms, implementation strategies, and extended evaluations. While the original paper introduced \gopt ’s unified intermediate representation ( \ir ) and demonstrated its performance benefits, this report delves into the framework’s implementation depth: (1) the full specification of \gopt ’s optimization rules; (2) a systematic treatment of semantic variations (e.g., homomorphism vs. edge-distinct matching) across query languages and their implications for optimization; (3) the design of GOpt’s Physical integration interface, enabling seamless integration with transactional (Neo4j) and distributed (GraphScope) backends via engine-specific operator customization; and (4) a detailed analysis of plan transformations for LDBC benchmark queries. DOI: XXXXXXX.XXXXXXX Conference: International Conference on Management of Data; June 22–27, 2025; Berlin, Germany 1. Introduction Graph databases have become indispensable tools for managing interconnected data across domains such as social networks, fraud detection, and recommendation systems. At the heart of these systems lies the need to efficiently execute Complex Graph Patterns ( CGPs ) , which combine graph pattern matching with relational operations like projection, aggregation, and filtering. While existing graph databases like Neo4j ( neo, 2024 ) and GraphScope ( Fan et al., 2021 ) provide foundational support for CGPs , their monolithic architectures impose critical limitations: (1) tight coupling with single query languages (e.g., Cypher ( Francis et al., 2018 ) or Gremlin ( Rodriguez, 2015 ) ), hindering cross-language interoperability, and (2) fragmented optimization strategies that lack integration of state-of-the-art techniques like worst-case optimal joins or high-order statistics. These constraints impede performance and flexibility in real-world applications, where evolving query requirements and industrial-scale datasets demand modular, graph-native optimization. In our SIGMOD 2025 paper, "A Modular Graph-Native Query Optimization Framework" ( Lyu et al., 2024 ) , we introduced \gopt , a unified optimization framework designed to address these challenges. \gopt decouples query parsing, optimization, and execution through a graph intermediate representation ( \ir ), enabling support for multiple query languages (Cypher, Gremlin) and seamless integration with diverse backend engines (Neo4j, GraphScope). By combining heuristic rule-based optimizations (RBO), automatic type inference, and a cost-based optimizer (CBO) leveraging high-order statistics, \gopt achieves significant performance gains – up to 48.6 \times speedup on Neo4j and 78.7 \times on GraphScope. This technical report expands on the SIGMOD work by delving into \gopt ’s architectural nuances and practical implementations. Key contributions include: (1) In-Depth Optimization Strategies : We detail \gopt ’s rule-based optimizations (e.g., FilterIntoPattern , PatternJoin ), cost-model-driven physical operator selection, and hybrid join strategies (binary joins, vertex expansion) tailored for backend engines. (2) Semantic Adaptations : We formalize \gopt ’s handling of diverse pattern-matching semantics (homomorphism, edge-distinct) across query languages, ensuring correctness while preserving optimization opportunities. (3) Physical Interface for Multiple Backends : We demonstrate how \gopt ’s PhysicalConverter allows engines to covert their own executable operators (e.g., Neo4j’s ExpandInto , GraphScope’s ExpandIntersect ), enabling backend-specific optimizations without compromising modularity. (4) Industrial Validation : Through a granular analysis of \gopt ’s optimization impact on the LDBC Social Network Benchmark (SNB) ( LDBC Social Network Benchmark, 2022 ) , we dissect how and why specific plan transformations – such as pattern order refinement, common pattern removal, and aggregation/filter pushdown – enable significant performance gains. These case studies provide actionable insights for the community, offering a blueprint for optimizing complex graph queries. The report is structured as follows: Section 2 gives background knowledge of graph pattern matching. Section 3 and Section 4 revisit \gopt ’s \ir abstraction and core architecture, respectively. We detail the optimization strategies in Section , and their applications to optimizing both simple and complex graph queries in Section and Section 6 . Section 7 details the design principles of \gopt ’s physical integration interface, formalizing two backend-specific methodologies for seamless integration with Neo4j and GraphScope, tailored to their Java-native and distributed execution models, respectively. By bridging the gap between academic advancements and industrial demands, \gopt establishes a new paradigm for graph query optimization—one that is modular, extensible, and graph-native. This report serves as a comprehensive guide for practitioners seeking to leverage \gopt ’s full potential in real-world graph analytics pipelines. 2. Preliminaries Table 1. Frequently used notations. Notation Definiton G(V_{G},E_{G}) A data graph with V_{G} and E_{G} P(V_{P},E_{P}) A pattern graph with V_{P} and E_{P} \footnotesize{\textsf{$N_{G}$}}(v) , \footnotesize{\textsf{$N_{G}^{E}$}}(v) Out neighbors and out edges of v in graph G \lambda_{G}(v) , \lambda_{G}(e) The type of vertex v and edge e in graph G \tau_{P}(v) , \tau_{P}(e) The type constraint of vertex v and edge e in pattern P , can be BasicType , UnionType or AllType \mathcal{F}_{P,G} The number of mappings of pattern P in graph G 2.1. The Definitions Data graph G=(V_{G},E_{G}) in this report adheres to the definition of the property graph model ( Angles et al., 2017 ) . V_{G} and E_{G} are the sets of vertices and edges, where |V_{G}| and |E_{G}| represent the number of vertices and edges. Given u,v\in V_{G} , (u,v)\in E_{G} is an edge directed from u to v , and all the out neighbors and out edges of u are denoted as \textsf{$N_{G}$}(v) and \textsf{$N_{G}^{E}$}(v) , respectively. Each vertex or edge in G is associated with a type, denoted as \lambda_{G}(v) and \lambda_{G}(e) respectively. Both vertices and edges can carry properties, which are key-value pairs. Note that if no ambiguity arises, we omit G from the subscript in the notations, and so as the follows. Considering two graphs G_{1} and G_{2} , we assert that G_{2} is a subgraph of G_{1} , symbolized as G_{2}\subseteq G_{1} , if and only if V_{G_{2}}\subseteq V_{G_{1}} , and E_{G_{2}}\subseteq E_{G_{1}} . A pattern P=(V_{P},E_{P}) is a small connected graph. Note that if P is not connected, matching the pattern is equivalent to taking the Cartesian product of the matches for its connected components, which is naturally the problem of CGPs in the following. Each vertex and edge in the pattern graph is associated with a set of types as a type constraint, denoted as \tau_{P}(v) and \tau_{P}(e) , respectively. Besides, predicates can be specified to vertices and edges in the pattern graph as well. Finding matches of P in G involves identifying all subgraphs G^{\prime} in G where P can be mapped to G^{\prime} via a homomorphism preserving edge relations and type constraints. The mapping function h:V_{P}\rightarrow V_{G^{\prime}} ensures that \forall e=(u,v)\in E_{P} , there is a corresponding edge (h(u),h(v))\in E_{G^{\prime}} . Additionally, the types of vertices and edges in G^{\prime} must align with the type constraints specified in P : (1) \forall v\in V_{P},\lambda_{G^{\prime}}(h(v))\in\tau_{P}(v) , and (2) \forall e=(u,v)\in E_{P},\lambda_{G^{\prime}}((h(u),h(v)))\in\tau_{P}(e) . The number of mappings of P in G is called pattern frequency , denoted as \mathcal{F}_{P,G} , or simply \mathcal{F}_{P} when G is clear. A complex graph pattern, termed as CGP , extends patterns with further relational operations. Optimizing CGPs is challenging due to their hybrid semantics. A straightforward way is to first identify matches of P in G , and then subject the matched subgraphs to the remaining relational operators in CGPs

Read the complete text