Abstract We study the optimization of navigational graph queries in the form of the Regular Queries, i.e., queries which combine recursive and pattern-matching fragments. Current approaches to their evaluation are not effective in practice. Towards addressing this, we present a number of novel powerful optimization techniques which aim to constrain the intermediate results during query evaluation. We show how these techniques can be planned effectively and executed efficiently towards the first practical evaluation solution for complex navigational queries on real-world workloads. Indeed, our experimental results show several orders of magnitude improvement in query evaluation performance over state-of-the-art techniques on a wide range of queries on diverse datasets.

We demonstrate AvantGraph, a graph query processing engine developed by the Database group at TU Eindhoven. Designed for efficient processing of both subgraph matching and navigational graph queries, AvantGraph encompasses innovation in three key areas: the planner, the cardinality estimator, and the execution engine. We present demonstration scenarios covering a wide range of workloads across diverse domains which (1) provides deep insights into the core challenges of complex graph query processing and (2) showcases corresponding critical optimizations via "under-the-hood" operational insights of AvantGraph's key components.