A Modular Graph-Native Query Optimization Framework

Bingqing Lyu, Xiaoli Zhou, Longbin Lai, Yufan Yang, Yunkai Lou, Wenyuan Yu, Ying Zhang, Jingren ZhouSigmod Conference Companion 2025 · DOI · OpenReview

TL;DR

This paper introduces GOpt, a modular framework for optimizing complex graph queries (CGPs). GOpt tackles the limitations of monolithic graph databases by offering a unified approach to handle multiple query languages, decouple optimization from specific graph systems, and integrate advanced optimization techniques, leading to significant performance improvements.

What Problem Does This Paper Address?

Graph databases are increasingly used for analyzing complex relationships. Complex Graph Patterns (CGPs) extend basic graph pattern matching with relational operations like selection and aggregation, making them more expressive for real-world applications. However, existing graph databases often have monolithic architectures that tightly couple query parsing, optimization, and execution. This makes it difficult to:

  1. Support multiple query languages: Systems are typically built for one language (e.g., Cypher for Neo4j, Gremlin for GraphScope), hindering interoperability and adaptation to new standards like GQL.
  2. Integrate advanced optimization techniques: Monolithic designs make it challenging to incorporate cutting-edge optimizations like high-order statistics or worst-case optimal joins, and to adapt to different backend systems' specific capabilities.

GOpt aims to solve these issues by providing a modular, language-agnostic, and system-agnostic optimization framework.

Methods

GOpt introduces a modular architecture with three key components:

  • Query Parser: Uses ANTLR to parse queries from various languages (Cypher, Gremlin) into an Abstract Syntax Tree (AST). A GraphIrBuilder then converts this AST into a unified, language-independent intermediate representation called Graph Intermediate Representation (GIR). This GIR decouples GOpt from specific languages.
  • Optimizer: This is the core component, employing a combination of:
  • Rule-Based Optimization (RBO): A set of heuristic rules designed to optimize interactions between graph patterns and relational operators. Examples include FilterIntoPattern (pushing filters into patterns) and JoinToPattern (merging joinable patterns).
  • Type Inference: An algorithm that infers implicit type constraints for pattern vertices and edges from the graph schema. This is crucial for optimizing patterns with arbitrary or "AllType" constraints, preventing unnecessary computation.
  • Cost-Based Optimization (CBO): Leverages high-order statistics from GLogS for accurate cardinality estimation, even with arbitrary type constraints. It uses a PhysicalSpec interface, allowing backend systems (like Neo4j and GraphScope) to register their specific physical operators and cost models. A top-down search framework with branch-and-bound strategies finds the optimal execution plan.
  • Metadata Provider: Supplies graph schema information and statistics (using GLogue for high-order statistics) to the optimizer.

GOpt is built on Apache Calcite, leveraging its relational optimization capabilities.

Datasets

The experiments utilized the LDBC Social Network Benchmark (LDBC SNB) datasets, specifically four datasets (G30, G100, G300, G1000) generated using the official data generator. These datasets were used to evaluate GOpt's performance across various graph sizes and query types (interactive and business intelligence workloads).

Key Insights and Ideas

  • Modularity is Key: Decoupling query parsing, optimization, and execution through a unified GIR is essential for supporting multiple languages and integrating advanced techniques.
  • Type Inference is Crucial for Performance: For patterns with "AllType" or unspecified types, inferring concrete type constraints can drastically reduce the search space and improve performance, avoiding unnecessary traversals.
  • Backend-Specific Cost Models Matter: The PhysicalSpec interface, allowing backends to register their own cost models for operators (e.g., ExpandInto vs. ExpandIntersect), is vital for achieving truly optimal plans, as generic cost models can lead to suboptimal choices.
  • High-Order Statistics Pay Off: Using high-order statistics (motif frequencies) significantly improves cardinality estimation accuracy for complex patterns, leading to better CBO decisions.
  • Hybrid Optimization is Powerful: Combining RBO for initial refinement and CBO for deep optimization, along with backend-specific cost models, yields substantial performance gains.

Key Results

  • Significant Speedups: GOpt achieved substantial performance improvements when integrated with existing systems:
  • Neo4j: Average speedup of 9.2x (up to 48.6x).
  • GraphScope: Average speedup of 33.4x (up to 78.7x).
  • Heuristic Rule Effectiveness: Rules like FilterIntoPattern showed dramatic improvements (orders of magnitude), while others like JoinToPattern and ComSubPattern also provided significant speedups.
  • Type Inference Impact: Type inference alone provided an average speedup of 51x on queries without explicit type constraints.
  • CBO Superiority: GOpt's CBO, utilizing backend-specific costs and high-order statistics, consistently outperformed generic or less informed approaches.
  • Scalability: Experiments on GraphScope demonstrated effective scalability with increasing data sizes, with performance degradation significantly lower than expected due to effective optimization.
  • Real-World Deployment: GOpt has been deployed at Alibaba for fraud detection, demonstrating its practicality and effectiveness in production environments.

Limitations and Future Work

  • Theoretical Completeness of GIR: The paper acknowledges concerns about the theoretical completeness of GIR in expressing diverse query languages and data models, referring readers to their open-source project for details.
  • Schema-Loose Systems: While GOpt addresses schema-loose systems like Neo4j by retrieving schema information from data, the paper notes that optimization is deferred if data is not initially present.
  • Relational Operator Optimization: While GOpt focuses on pattern optimization, the paper mentions that optimizing relational operators and their costs is handled by Calcite, with future work planned to integrate advanced selectivity estimation techniques for patterns with filters.
  • Standardized GQL Support: Support for the standardized GQL is not yet finalized as its official grammar interpretation tool is pending.

Summary updated

BibTeX
@inproceedings{lyu2025modular,
  author = {Bingqing Lyu and Xiaoli Zhou and Longbin Lai and Yufan Yang and Yunkai Lou and Wenyuan Yu and Ying Zhang and Jingren Zhou},
  title = {{A Modular Graph-Native Query Optimization Framework}},
  booktitle = {Sigmod Conference Companion},
  year = {2025},
  doi = {10.1145/3722212.3724425},
}
Figure