In-memory Incremental Maintenance of Provenance Sketches [extended version]
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912396097880064 |
|---|---|
| author | Li, Pengyuan Glavic, Boris Gawlick, Dieter Krishnaswamy, Vasudha Liu, Zhen Hua Porobic, Danica Niu, Xing |
| author_facet | Li, Pengyuan Glavic, Boris Gawlick, Dieter Krishnaswamy, Vasudha Liu, Zhen Hua Porobic, Danica Niu, Xing |
| contents | Provenance-based data skipping compactly over-approximates the provenance of a query using so-called provenance sketches and utilizes such sketches to speed-up the execution of subsequent queries by skipping irrelevant data. However, a sketch captured at some time in the past may become stale if the data has been updated subsequently. Thus, there is a need to maintain provenance sketches. In this work, we introduce In-Memory incremental Maintenance of Provenance sketches (IMP), a framework for maintaining sketches incrementally under updates. At the core of IMP is an incremental query engine for data annotated with sketches that exploits the coarse-grained nature of sketches to enable novel optimizations. We experimentally demonstrate that IMP significantly reduces the cost of sketch maintenance, thereby enabling the use of provenance sketches for a broad range of workloads that involve updates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_20683 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | In-memory Incremental Maintenance of Provenance Sketches [extended version] Li, Pengyuan Glavic, Boris Gawlick, Dieter Krishnaswamy, Vasudha Liu, Zhen Hua Porobic, Danica Niu, Xing Databases Provenance-based data skipping compactly over-approximates the provenance of a query using so-called provenance sketches and utilizes such sketches to speed-up the execution of subsequent queries by skipping irrelevant data. However, a sketch captured at some time in the past may become stale if the data has been updated subsequently. Thus, there is a need to maintain provenance sketches. In this work, we introduce In-Memory incremental Maintenance of Provenance sketches (IMP), a framework for maintaining sketches incrementally under updates. At the core of IMP is an incremental query engine for data annotated with sketches that exploits the coarse-grained nature of sketches to enable novel optimizations. We experimentally demonstrate that IMP significantly reduces the cost of sketch maintenance, thereby enabling the use of provenance sketches for a broad range of workloads that involve updates. |
| title | In-memory Incremental Maintenance of Provenance Sketches [extended version] |
| topic | Databases |
| url | https://arxiv.org/abs/2505.20683 |