Approximate Sketches
Proceedings of the ACM on Management of Data · 12.03.2024 · 2 (1) · 1-24
DOI: 10.1145/3639321 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 26.03.2024. Verfasst von Brian Tsan und 3 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 35 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSF.
Abstract (Originalsprache)
Sketches are single-pass small-space data summaries that can quickly estimate the cardinality of join queries. However, sketches are not directly applicable to join queries with dynamic filter conditions --- where arbitrary selection predicate(s) are applied --- since a sketch is limited to a fixed selection. While multiple sketches for various selections can be used in combination, they each incur individual storage and maintenance costs. Alternatively, exact sketches can be built during runtime for every selection. To make this process scale, a high-degree of parallelism --- available in hardware accelerators such as GPUs --- is required. Therefore, sketch usage for cardinality estimation in query optimization is limited. Following recent work that applies transformers to cardinality estimation, we design a novel learning-based method to approximate the sketch of any arbitrary selection, enabling sketches for join queries with filter conditions. We train a transformer on each table to estimate the sketch of any subset of the table, i.e., any arbitrary selection. Transformers achieve this by learning the joint distribution amongst table attributes, which is equivalent to a multidimensional sketch. Subsequently, transformers can approximate any sketch, enabling sketches for join cardinality estimation. In turn, estimating joins via approximate sketches allows tables to be modeled individually and thus scales linearly with the number of tables. We evaluate the accuracy and efficacy of approximate sketches on queries with selection predicates consisting of conjunctions of point and range conditions. Approximate sketches achieve similar accuracy to exact sketches with at least one order of magnitude less overhead.
Förderung
- NSF
Zitieren
APA
Tsan, B., Datta, A., Izenov, Y., & Rusu, F. (2024). Approximate Sketches. Proceedings of the ACM on Management of Data, 2(1), 1-24. https://doi.org/10.1145/3639321
Vancouver
Tsan B, Datta A, Izenov Y, Rusu F. Approximate Sketches. Proceedings of the ACM on Management of Data. 2024;2(1):1-24. doi:10.1145/3639321
BibTeX
@article{Tsan2024,
author = {Tsan, Brian and Datta, Asoke and Izenov, Yesdaulet and Rusu, Florin},
title = {Approximate Sketches},
journal = {Proceedings of the ACM on Management of Data},
year = {2024},
volume = {2},
number = {1},
pages = {1--24},
doi = {10.1145/3639321}
}
EUVIMED