Selected problems in cardinality estimation


Müller, Magnus


[img] PDF
Dissertation_Magnus_Mueller.pdf - Published

Download (4MB)

URN: urn:nbn:de:bsz:180-madoc-636836
Document Type: Doctoral dissertation
Year of publication: 2022
Place of publication: Mannheim
University: Universität Mannheim
Evaluator: Moerkotte, Guido
Date of oral examination: 21 December 2022
Publication language: English
Institution: School of Business Informatics and Mathematics > Practical Computer Science III (Moerkotte 1996-)
License: CC BY 4.0 Creative Commons Attribution 4.0 International (CC BY 4.0)
Subject: 004 Computer science, internet
Keywords (English): cardinality estimation , query optimization
Abstract: Cardinality estimation remains a critical task in query processing. Query optimizers rely on the accuracy of cardinality estimates when generating execution plans, and, in approximate query answering, estimated cardinalities affect the quality of query results. In this thesis, we present multiple new cardinality estimation techniques. The techniques differ vastly by the query under consideration. For single relation queries, we use the principle of maximum entropy to combine information extracted from samples and histograms. For join size estimation, we rely on a model that requires one to find estimates for the intersection size of join attributes. For queries with multiple joins, sketches serve as compact representations of join results that are combined via a data structure that approximates the joint frequency distribution of join attributes. In addition, we present a technique to transform selection predicates into a representation that allows estimators based on machine learning to effectively learn query result cardinalities. For each cardinality estimator presented in this thesis, we precisely define its problem scope, the construction process, and how to obtain estimates. Then, we compare to state-of-the-art cardinality estimators and run a thorough evaluation with queries over multiple data sets. Based on our observations, we analyze the strengths and limitations of each of our cardinality estimators and identify its preferred use case.




Dieser Eintrag ist Teil der Universitätsbibliographie.

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




Metadata export


Citation


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item