Query execution time estimation in graph databases based on graph neural networks

Abstract

Query execution time estimation is an essential task for databases, accurate estimation results can help administrators to manage and monitor systems. This study proposes an interaction-aware and dependency-aware query execution time estimation approach that utilizes graph neural networks to capture dependence and interaction relationships. We divide graph query execution time estimation tasks into three stages: workload generation and running, graph-based feature modeling and representation, training and estimation. Specifically, we generate query workloads and run them to collect the database and plan information when queries are executed. Then, the collected plan and database components are modeled into vertexes, the interaction and dependency between them are modeled into edges of graph-based feature representation. We develop an estimation model based on graph neural networks, in which the vertex embedding network is proposed to deal with the vertex heterogeneity, and the message passing network is proposed to aggregate the local representation into the global representation to obtain an embedding that can represent the higher-order feature information of the whole graph, and the estimation network is proposed to estimate execution times. The experiment results on datasets show that our estimation approach can improve estimation quality and outperform other estimation approaches in terms of estimation accuracy.

Keywords

• Neo4j database management systems
• Deep learning
• Graph neural network
• Graph queries
• Execution time estimation