Degree Sequence Bound For Join Cardinality Estimation
| Autor: | Deeds, Kyle, Suciu, Dan, Balazinska, Magda, Cai, Walter |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Cardinality Estimation Theory of computation → Data modeling Query Planning Databases (cs.DB) Degree Bounds Functional Approximation Information systems → Query optimization Computer Science - Databases Cardinality Bounding Theory of computation → Database query processing and optimization (theory) Berge-Acyclic Queries Computer Science::Databases Information systems → Query planning |
| Popis: | 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. LIPIcs, Vol. 255, 26th International Conference on Database Theory (ICDT 2023), pages 8:1-8:18 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|