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.
Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs
DSDSD - Dutch Seminar on Data Systems Design via YouTube
Overview
Syllabus
We hold bi-weekly talks on Fridays from PM to 5 PM CET for and by researchers and practitioners designing and implementing data systems. The objective is to establish a new forum for the Dutch Data Systems community to come together, foster collaborations between its members, and bring in high-quality international speakers. We would like to invite all researchers, especially also Ph.D. students, who are working on related topics to join the events. It is an excellent opportunity to receive feedback early on from researchers in your field.
Taught by
DSDSD - Dutch Seminar on Data Systems Design
Related Courses
-
Stardog Query Optimizer - Join Ordering and Cardinality Estimations for Graph Queries
-
LingoDB: An Open Compilation and Optimization Framework for Sustainable Data Processing
-
Database Schemas in the Wild - Learning from a Large Corpus of Relational Database Schemas
-
Towards LLM-augmented Database Systems
-
Implementing InfluxDB IOx Using Apache Arrow, DataFusion, and Rust
-
Leveraging Generative AI for Data Processing and Database Management
