Optimization of Boolean expressions for main memory database systems


Kastrati, Fisnik


[img]
Preview
PDF
thesis.pdf - Published

Download (1MB)

URL: https://madoc.bib.uni-mannheim.de/44275
URN: urn:nbn:de:bsz:180-madoc-442758
Document Type: Doctoral dissertation
Year of publication: 2018
Place of publication: Mannheim
University: Universität Mannheim
Evaluator: Moerkotte, Guido
Date of oral examination: 29 January 2018
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
Subject headings (SWD): In-Memory-Datenbank , Abfrageverarbeitung , Optimierung , Boolesche Funktion
Keywords (English): Query Optimization, Main Memory Database Systems, Boolean Expressions, Conjunctive Predicates, Disjunctive Predicates
Abstract: With the ubiquity of main memory databases which are increasingly replacing the old disk-oriented databases, relations are being stored in denormalized form in order to increase the query throughput, thus, the dominance of join operators in terms of costsis being replaced by the costs of evaluating selection predicates. Boolean expressions containing selection predicates connected both conjunctively and disjunctively have been thus far solved by rather simple heuristics which leaves a large optimization potential unharvested. To exacerbate the matter, such heuristics rely on the independent predicate selectivity assumption which typically does not hold, and the constant predicate costs assumption which in terms of main memory database systems does not hold either. In this thesis we tackle the problem of optimizing Boolean expressions by not relying on the independence assumption nor the constant predicate costs assumption. We present optimization algorithms for queries containing both conjunctively and disjunctively connected predicates together with a cost model which precisely captures CPU architectural characteristics such as branch misprediction. Our optimization algorithms achieve the optimum in terms of plan quality, thus, they harvest the entire optimization potential inherent in Boolean expressions.
Translation of the abstract: Die sich wandelnde Hardwarelandschaft führt dazu, dass Hauptspeicher-Datenbanksysteme die klassischen disk-basierten Systeme zunehmend verdrängen. Hauptspeicher-Datenbanksysteme speichern Relationen in denormalisierter Form um den Durchsatz an Anfragen zu erhöhen. In Folge dessen übernehmen Selektionsprädikate die Rolle von Joins als entscheidenden Kostenfaktor. Konjunktiv sowie disjunktiv verknüpfte Boolesche Ausdrücke, welche Selektionsprädikate enthalten, wurden bisher von simplen Heuristiken optimiert. Dies hat viel Spielraum für Optimierungen gelassen. Die kritischen Schwachstellen dieser Heuristiken sind, dass sie sowohl annehmen, dass die Selektivtäten Unabhängigkeit voneinander sind, welches im Allgemeinen nicht gilt, sowie, dass die Evaluationskosten von Prädikaten unempfindlich gegenüber ihrer Selektivität sind. Letzteres spiegelt insbesondere in Hauptspeicher-Datenbanksystemen die Realität nicht wider. Diese Arbeit behandelt die Optimierung von Booleschen Ausdrücken ohne diese Annahmen. Wir zeigen Optimierungsalgorithmen für Anfragen, die sowohl konjunktiv als auch disjunktiv verknüpfte Prädikate enthalten. Darüber hinaus präsentieren wir ein dafür angepasstes Kostenmodell, welches Charakteristiken der Prozessorarchitektur, wie branch misprediction, präzise modelliert. Unsere Optimierungsalgorithmen sind optimal in Bezug auf die Planqualität; sie schöpfen das gesamte Optimierungspotential Boolescher Ausdrücke aus. (German)




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