Optimization of Boolean expressions for main memory database systems


Kastrati, Fisnik


[img]
Vorschau
PDF
thesis.pdf - Veröffentlichte Version

Download (1MB)

URL: https://madoc.bib.uni-mannheim.de/44275
URN: urn:nbn:de:bsz:180-madoc-442758
Dokumenttyp: Dissertation
Erscheinungsjahr: 2018
Ort der Veröffentlichung: Mannheim
Hochschule: Universität Mannheim
Gutachter: Moerkotte, Guido
Datum der mündl. Prüfung: 29 Januar 2018
Sprache der Veröffentlichung: Englisch
Einrichtung: Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Practical Computer Science III (Moerkotte 1996-)
Lizenz: CC BY 4.0 Creative Commons Namensnennung 4.0 International (CC BY 4.0)
Fachgebiet: 004 Informatik
Normierte Schlagwörter (SWD): In-Memory-Datenbank , Abfrageverarbeitung , Optimierung , Boolesche Funktion
Freie Schlagwörter (Englisch): 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.
Übersetzung des Abstracts: 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. (Deutsch)




Dieser Eintrag ist Teil der Universitätsbibliographie.

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




Metadaten-Export


Zitation


+ Suche Autoren in

+ Download-Statistik

Downloads im letzten Jahr

Detaillierte Angaben



Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail


Actions (login required)

Eintrag anzeigen Eintrag anzeigen