Pessimistic Cardinality Estimation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909410570272768 |
|---|---|
| author | Khamis, Mahmoud Abo Deeds, Kyle Olteanu, Dan Suciu, Dan |
| author_facet | Khamis, Mahmoud Abo Deeds, Kyle Olteanu, Dan Suciu, Dan |
| contents | Cardinality Estimation is to estimate the size of the output of a query without computing it, by using only statistics on the input relations. Existing estimators try to return an unbiased estimate of the cardinality: this is notoriously difficult. A new class of estimators have been proposed recently, called "pessimistic estimators", which compute a guaranteed upper bound on the query output. Two recent advances have made pessimistic estimators practical. The first is the recent observation that degree sequences of the input relations can be used to compute query upper bounds. The second is a long line of theoretical results that have developed the use of information theoretic inequalities for query upper bounds. This paper is a short overview of pessimistic cardinality estimators, contrasting them with traditional estimators. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_00642 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Pessimistic Cardinality Estimation Khamis, Mahmoud Abo Deeds, Kyle Olteanu, Dan Suciu, Dan Databases Information Theory Cardinality Estimation is to estimate the size of the output of a query without computing it, by using only statistics on the input relations. Existing estimators try to return an unbiased estimate of the cardinality: this is notoriously difficult. A new class of estimators have been proposed recently, called "pessimistic estimators", which compute a guaranteed upper bound on the query output. Two recent advances have made pessimistic estimators practical. The first is the recent observation that degree sequences of the input relations can be used to compute query upper bounds. The second is a long line of theoretical results that have developed the use of information theoretic inequalities for query upper bounds. This paper is a short overview of pessimistic cardinality estimators, contrasting them with traditional estimators. |
| title | Pessimistic Cardinality Estimation |
| topic | Databases Information Theory |
| url | https://arxiv.org/abs/2412.00642 |