Linglin Yang's paper "gCBO: A Cost-based Optimizer for Graph Databases" has been accepted by CIKM 2022.
Query optimization is an especially challenging problem in graph databases due to its wide plan space and the difficulty in gathering statistics. This paper proposes a new cost-based query optimizer called gCBO for graph databases and implement it in a specific graph database (i.e., gStore). To tackle the aforementioned challenges, gCBO employs a hybrid plan enumerator based on dynamic programming, cost models that capture the characteristics of different types of joins, and a sampling-based cardinality estimation strategy that gathers the necessary statistics on-the-fly. What is more, to absorb the experience of users, we build an interactive component for gCBO, which allows users to receive the optimized execution plans with detailed information and generate their own plans for execution.