1. A General Cardinality Estimation Framework for Subgraph Matching in Property Graphs
- Author
-
van Leeuwen, Wilco, Fletcher, George, Yakovets, Nikolay, Database Group, and EAISI Foundational
- Subjects
FOS: Computer and information sciences ,Query processing ,Data models ,InformationSystems_DATABASEMANAGEMENT ,Databases (cs.DB) ,Database languages ,Topology ,Computer Science Applications ,Databases ,Computational Theory and Mathematics ,Computer Science - Databases ,graph databases ,Cardinality estimation ,selectivity estimation ,property graph data model ,Pattern matching ,Estimation ,Computer Science::Databases ,Information Systems ,query optimization - Abstract
Many techniques have been developed for the cardinality estimation problem in data management systems. In this document, we introduce a framework for cardinality estimation of query patterns over property graph databases, which makes it possible to analyze, compare and combine different cardinality estimation approaches. This framework consists of three phases: obtaining a set of estimates for some subqueries, extending this set and finally combining the set into a single cardinality estimate for the query. We show that (parts of) many of the existing cardinality estimation approaches can be used as techniques in one of the phases from our framework. The three phases are loosely coupled, this makes it possible to combine (parts of) current cardinality estimation approaches. We create a graph version of the Join Order Benchmark to perform experiments with different combinations of techniques. The results show that query patterns without property constraints can be accurately estimated using synopses for small patterns. Accurate estimation of query patterns with property constraints require new estimation techniques to be developed that capture correlations between the property constraints and the topology in graph databases.
- Published
- 2023