Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs

Explore an in-depth conference talk examining summary-based cardinality estimators in graph database management systems through the innovative lens of Cardinality Estimation Graphs (CEGs). Delve into both optimistic estimators that rely on uniformity and conditional independence assumptions, and newer pessimistic estimators utilizing information theoretic linear programs. Learn how optimistic estimators can be modeled using bottom-to-top paths in CEGs, where nodes represent sub-queries and edge weights indicate average degree statistics. Discover the effectiveness of different path selection strategies based on query structure - maximum-weight paths for acyclic queries and small cycles, versus minimum-weight paths for larger cycles. Understand the surprising connection between optimistic and pessimistic estimators through their shared CEG modeling capabilities, leading to new optimization opportunities and combinatorial solutions. Presented by Associate Professor Semih Salihoglu from the University of Waterloo, known for his work on graph database management systems including Graphflow and GraphSurge projects.