EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Approximate Sketches

Brian Tsan, Asoke Datta, Yesdaulet Izenov, Florin Rusu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →