Sieve: A Learned Data-Skipping Index for Data Analytics
Proceedings of the VLDB Endowment · 2023-07 · 16 (11) · 3214-3226
DOI: 10.14778/3611479.3611520 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 24.08.2023. Verfasst von Yulai Tong und 6 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 45 Literaturangaben.
Abstract (Originalsprache)
Modern data analytics services are coupled with external data storage services, making I/O from remote cloud storage one of the dominant costs for query processing. Techniques such as columnar block-based data organization and compression have become standard practices for these services to save storage and processing cost. However, the problem of effectively skipping irrelevant blocks at low overhead is still open. Existing data-skipping efforts maintain lightweight summaries (e.g., min/max, histograms) for each block to filter irrelevant data. However, such techniques ignore patterns in real-world data, enabling ineffective use of the storage budget and may cause serious false positives. This paper presents Sieve, a learning-enhanced index designed to efficiently filter out irrelevant blocks by capturing data patterns. Specifically, Sieve utilizes piece-wise linear functions to capture block distribution trends over the key space. Based on the captured trends, Sieve trades off storage consumption and false positives by grouping neighboring keys with similar block distributions into a single region. We have evaluated Sieve using Presto, and experiments on real-world datasets demonstrate that Sieve achieves up to 80% reduction in blocks accessed and 42% reduction in query times compared to its counterparts.
Zitieren
APA
Tong, Y., Liu, J., Wang, H., Zhou, K., He, R., Zhang, Q., & Wang, C. (2023). Sieve: A Learned Data-Skipping Index for Data Analytics. Proceedings of the VLDB Endowment, 16(11), 3214-3226. https://doi.org/10.14778/3611479.3611520
Vancouver
Tong Y, Liu J, Wang H, Zhou K, He R, Zhang Q, et al. Sieve: A Learned Data-Skipping Index for Data Analytics. Proceedings of the VLDB Endowment. 2023;16(11):3214-3226. doi:10.14778/3611479.3611520
BibTeX
@article{Tong2023,
author = {Tong, Yulai and Liu, Jiazhen and Wang, Hua and Zhou, Ke and He, Rongfeng and Zhang, Qin and Wang, Cheng},
title = {Sieve: A Learned Data-Skipping Index for Data Analytics},
journal = {Proceedings of the VLDB Endowment},
year = {2023},
volume = {16},
number = {11},
pages = {3214--3226},
doi = {10.14778/3611479.3611520}
}
EUVIMED