1 Search Results for "Balazinska, Magda"

Document
DOI: 10.4230/LIPIcs.ICDT.2023.8
Degree Sequence Bound for Join Cardinality Estimation

Authors: Kyle Deeds, Dan Suciu, Magda Balazinska, and Walter Cai

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
Recent work has demonstrated the catastrophic effects of poor cardinality estimates on query processing time. In particular, underestimating query cardinality can result in overly optimistic query plans which take orders of magnitude longer to complete than one generated with the true cardinality. Cardinality bounding avoids this pitfall by computing an upper bound on the query’s output size using statistics about the database such as table sizes and degrees, i.e. value frequencies. In this paper, we extend this line of work by proving a novel bound called the Degree Sequence Bound which takes into account the full degree sequences and the max tuple multiplicity. This work focuses on the important class of Berge-Acyclic queries for which the Degree Sequence Bound is tight. Further, we describe how to practically compute this bound using a functional approximation of the true degree sequences and prove that even this functional form improves upon previous bounds.
Cite as

Kyle Deeds, Dan Suciu, Magda Balazinska, and Walter Cai. Degree Sequence Bound for Join Cardinality Estimation. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{deeds_et_al:LIPIcs.ICDT.2023.8,
  author =	{Deeds, Kyle and Suciu, Dan and Balazinska, Magda and Cai, Walter},
  title =	{{Degree Sequence Bound for Join Cardinality Estimation}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.8},
  URN =		{urn:nbn:de:0030-drops-177508},
  doi =		{10.4230/LIPIcs.ICDT.2023.8},
  annote =	{Keywords: Cardinality Estimation, Cardinality Bounding, Degree Bounds, Functional Approximation, Query Planning, Berge-Acyclic Queries}
}
  • Refine by Author
  • 1 Balazinska, Magda
  • 1 Cai, Walter
  • 1 Deeds, Kyle
  • 1 Suciu, Dan

  • Refine by Classification
  • 1 Information systems → Query optimization
  • 1 Information systems → Query planning
  • 1 Theory of computation → Data modeling
  • 1 Theory of computation → Database query processing and optimization (theory)

  • Refine by Keyword
  • 1 Berge-Acyclic Queries
  • 1 Cardinality Bounding
  • 1 Cardinality Estimation
  • 1 Degree Bounds
  • 1 Functional Approximation
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact