License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2023.8
URN: urn:nbn:de:0030-drops-177508
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17750/
Go to the corresponding LIPIcs Volume Portal

Deeds, Kyle ; Suciu, Dan ; Balazinska, Magda ; Cai, Walter

Degree Sequence Bound for Join Cardinality Estimation

pdf-format:
LIPIcs-ICDT-2023-8.pdf (0.9 MB)

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.

BibTeX - Entry

@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.dagstuhl.de/opus/volltexte/2023/17750},
  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}
}

Keywords: Cardinality Estimation, Cardinality Bounding, Degree Bounds, Functional Approximation, Query Planning, Berge-Acyclic Queries
Collection: 26th International Conference on Database Theory (ICDT 2023)
Issue Date: 2023
Date of publication: 17.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI