Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916713346367488 |
|---|---|
| author | Deeds, Kyle Sabale, Diandre Kayali, Moe Suciu, Dan |
| author_facet | Deeds, Kyle Sabale, Diandre Kayali, Moe Suciu, Dan |
| contents | Graph workloads pose a particularly challenging problem for query optimizers. They typically feature large queries made up of entirely many-to-many joins with complex correlations. This puts significant stress on traditional cardinality estimation methods which generally see catastrophic errors when estimating the size of queries with only a handful of joins. To overcome this, we propose COLOR, a framework for subgraph cardinality estimation which applies insights from graph compression theory to produce a compact summary that captures the global topology of the data graph. Further, we identify several key optimizations that enable tractable estimation over this summary even for large query graphs. We then evaluate several designs within this framework and find that they improve accuracy by up to 10$^3$x over all competing methods while maintaining fast inference, a small memory footprint, efficient construction, and graceful degradation under updates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_06767 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation Deeds, Kyle Sabale, Diandre Kayali, Moe Suciu, Dan Databases Graph workloads pose a particularly challenging problem for query optimizers. They typically feature large queries made up of entirely many-to-many joins with complex correlations. This puts significant stress on traditional cardinality estimation methods which generally see catastrophic errors when estimating the size of queries with only a handful of joins. To overcome this, we propose COLOR, a framework for subgraph cardinality estimation which applies insights from graph compression theory to produce a compact summary that captures the global topology of the data graph. Further, we identify several key optimizations that enable tractable estimation over this summary even for large query graphs. We then evaluate several designs within this framework and find that they improve accuracy by up to 10$^3$x over all competing methods while maintaining fast inference, a small memory footprint, efficient construction, and graceful degradation under updates. |
| title | Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation |
| topic | Databases |
| url | https://arxiv.org/abs/2405.06767 |