Constructing a relational query optimizer for non-relational languages [Elektronische Ressource] / vorgelegt von Jan Rittinger

Constructing a Relational Query Optimizerfor Non-Relational LanguagesDissertationder Mathematisch-Naturwissenschaftlichen Fakult atder Eberhard Karls Universit at Tubingenzur Erlangung des Grades einesDoktors der Naturwissenschaften(Dr. rer. nat.)vorgelegt vonJan Rittingeraus KarlsruheTubingen2010iiTag der mundlic hen Quali kation: 08.04.2011Dekan: Prof. Dr. Wolfgang Rosenstiel1. Berichterstatter: Prof. Dr. Torsten Grust2. Berich Prof. Dr. Guido MoerkotteZusammenfassungDie Speicherung von Daten in achen, ungeordneten Tabellen sowie eine deklara-tive Anfragesprache sind Grunde fur den Erfolg relationaler Datenbanksysteme:Sie erlauben einem Datenbankoptimierer nicht nur die Auswahl verschiedenerAlgorithmen, sondern auch die Wahl der besten Auswertungsreihenfolge. Dankjahrzehntelanger Forschung und Entwicklung ahlenz relationale Datenbanksystemezu den besten Auswertungsplattformen fur gro e Datenmengen.In den meisten Programmiersprachen werden, im Gegensatz zu Datenbanksys-temen, sortierte und mitunter verschachtelte Datenstrukturen verwendet. Diemeisten Software-Entwickler arbeiten aglict h mit diesen Datenstrukturen inder Programmiersprache ihrer Wahl, was dazu fuhrt, dass das Schreiben vonDatenbankanfragen oft ein Umdenken erfordert, beziehungsweise eine potentielleFehlerquelle darstellt.
Publié le : vendredi 1 janvier 2010
Lecture(s) : 19
Tags :
Source : D-NB.INFO/1011393948/34
Nombre de pages : 137
Voir plus Voir moins

Constructing a Relational Query Optimizer
for Non-Relational Languages
Dissertation
der Mathematisch-Naturwissenschaftlichen Fakult at
der Eberhard Karls Universit at Tubingen
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. nat.)
vorgelegt von
Jan Rittinger
aus Karlsruhe
Tubingen
2010ii
Tag der mundlic hen Quali kation: 08.04.2011
Dekan: Prof. Dr. Wolfgang Rosenstiel
1. Berichterstatter: Prof. Dr. Torsten Grust
2. Berich Prof. Dr. Guido MoerkotteZusammenfassung
Die Speicherung von Daten in achen, ungeordneten Tabellen sowie eine deklara-
tive Anfragesprache sind Grunde fur den Erfolg relationaler Datenbanksysteme:
Sie erlauben einem Datenbankoptimierer nicht nur die Auswahl verschiedener
Algorithmen, sondern auch die Wahl der besten Auswertungsreihenfolge. Dank
jahrzehntelanger Forschung und Entwicklung ahlenz relationale Datenbanksysteme
zu den besten Auswertungsplattformen fur gro e Datenmengen.
In den meisten Programmiersprachen werden, im Gegensatz zu Datenbanksys-
temen, sortierte und mitunter verschachtelte Datenstrukturen verwendet. Die
meisten Software-Entwickler arbeiten aglict h mit diesen Datenstrukturen in
der Programmiersprache ihrer Wahl, was dazu fuhrt, dass das Schreiben von
Datenbankanfragen oft ein Umdenken erfordert, beziehungsweise eine potentielle
Fehlerquelle darstellt. Um die Vorteile von relationalen Datenbanksystemen
fur Entwickler in ihrer bekannten Umgebung nutzbar zu machen, stellen wir
eine nicht-relationale Sprache vor, die mit Ordnung, verschachtelten Listen und
komplexeren Datenstrukturen, wie zum Beispiel Tupeln, benannten Records
und XML-Daten, umgehen kann. Wir ub ersetzen in dieser Sprache formulierte
Anfragen in ungeordnete relationale Anfragen, die auf Tabellen arbeiten.
Die Ubersetzung ist integraler Bestandteil des Compilers Path nder und
beruht auf dem Konzept des loop lifting: Sie stellt die genaue Transformation der
\fremden" Sprachkonzepte in die relationale Welt sicher. Die Zielsprache ist eine un-
geordnete logische Algebra, deren Operatoren aus bekannten Algebra-Operatoren
der Datenbankliteratur sowie zus atzlichen Nummerierungs- und XML-Op
besteht. Die zus atzlichen Operatoren erm oglichen die genaue Ubersetzung von
Ordnung, verschachtelten Listen und komplexeren Datenstrukturen.
Im Gegensatz zu normalen Datenbankanfragen besteht ein Algebraplan durch-
schnittlich nicht aus dutzenden, sondern aus hunderten von Operatoren. Die Kom-
bination aus Gr o e des Plans, Vernetzung der Operatoren und Nummerierungsop-
eratoren ub erfordert alle von uns getesten Datenbankoptimierer. In dieser Arbeit
stellen wir einen eigenen Optimierer vor, der die logischen Algebrapl ane analysiert
und jeden Operator mit Annotationen versieht. Diese Anmerkungen beschreiben
Eigenschaften des umgebenden Planes und werden verwendet um gezielt lokale
Plantransformationen vorzunehmen. Die Optimierungen werden durch Heuristiken
gesteuert und fuhren jeweils zu einer inkrementellen Verbesserung des Plans. Ziel
iiiiv ZUSAMMENFASSUNG
der Optimierungen ist das Entfernen m oglichst vieler Operatoren|im Speziellen
der Nummerierungsoperatoren|unter Beruc ksichtigung semantischer Aquivalenz.
Die vereinfachten Anfragepl ane werden entweder in SQL-Anfragen oder in
Skripte fur das Hauptspeicher-Datenbanksystem MonetDB/XQuery ub ersetzt.
MonetDB/XQuery kann, dank vieler XML-spezi scher Algorithmen und Er-
weiterungen, Anfragen auf XML-Daten sehr e zient auswerten. Die generierten
SQL-Anfragen k onnen stattdessen auf fast jedem relationalen Datenbanksystem
ausgewertet werden und pro tieren zus atzlich von den eingebauten Anfrageop-
timierern der Datenbanksysteme. In unseren Experimenten analysieren wir die
Qualit at der optimierten Anfragepl ane und vergleichen die Auswertungszeiten. Die
untersuchten, Anfragen erinnern in ihrer E zienz an handgeschriebene
Anfragen.
Die Kombination aus Ubersetzung in logische Algebrapl ane, Optimierung
und Generierung von Datenbankanfragen ergibt einen Compiler, der den Einsatz
von relationalen Datenbanksystemen als e ziente Laufzeitumgebungen fur nicht-
relationale Sprachen erm oglicht.Abstract
Flat, unordered table data and a declarative query language established today’s
success of relational database systems. Provided with the freedom to choose the
evaluation order and underlying algorithms, their complex query optimizers are
geared to come up with the best execution plan for a given query. With over
30 years of development and research, relational database management systems
belong to the most mature and e cient query processors (especially for substantial
amounts of data).
In contrast, ordered lists of possibly nested data structures are used throughout
in programming languages. Most developers handle these constructs on a daily
basis and need to change their programming style, when confronted with a
relational database system. To leverage the potential of the relational query
processing facility in the context of non-relational languages|without the need
for a context switch|we provide a query language that copes with order, nesting,
and more complex data structures (such as tuples, named records, and XML data).
Queries expressed in this language are compiled into relational queries over at,
unordered tables.
We take great care in the faithful mapping of the \alien" language constructs.
This work describes the Path nder compiler achieving the transformation based
on the loop lifting compilation strategy. The compiler transforms the input queries
into logical algebra plans. The operators of this unordered algebra consist mainly
of standard table algebra operators. Additional numbering and XML operators
generate surrogate values to ensure an accurate representation of order, nesting,
and more complex data structures.
Because of the exotic plan shape|the average plan consists of hundreds of
operators and a large number of sharing points|and the numbering operators, the
query optimizers of all tested database systems fail to come up with an e cient
execution plan. We faced this challenge ourselves and describe an optimization
framework that annotates the operators with plan properties and performs local
rewrites based on the collected properties. The optimizations are guided by
heuristics that are geared to signi cantly decrease the number of operators and
order constraints.
The resulting plans are either turned into declarative SQL queries or scripts
written for more specialized relational database systems, most notable Mon-
vvi ABSTRACT
etDB/XQuery. Whereas MonetDB/XQuery ships with a highly tuned runtime for
XML processing, the generated SQL code allows to additionally bene t from the
builtin optimizers of relational database systems. Experiments as well as plan
analyses show that, in contrast to the initial plans, most optimized plans resemble
queries from an ordinary database workload and are evaluated e ciently.
In summary, the compiler turns relational database systems into high-perfor-
mance query processors for non-relational languages.Contents
Zusammenfassung iii
Abstract v
1 Introduction 1
1.1 Optimizations in the Context of Path nder . . . . . . . . . . . . . 2
1.2 Logical Query Optimization . . . . . . . . . . . . . . . . . . . . . 5
1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Prior Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Loop Lifted Query Compilation 7
2.1 Loop Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 An Algebra for Non-Relational Languages . . . . . . . . . . . . . 9
2.3 Algebraic List Processing . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.1 The Compilation Scheme . . . . . . . . . . . . . . . . . . . 12
2.3.2 Literals and Lists . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.3 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.4 Operations and Conditionals . . . . . . . . . . . . . . . . . 14
2.3.5 Loop Lifting in Action . . . . . . . . . . . . . . . . . . . . 15
2.4 More Order Constructs . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 Adding Data Diversity . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5.1 Support for XML Data . . . . . . . . . . . . . . . . . . . . 19
2.5.2 An Ordered View of Tables . . . . . . . . . . . . . . . . . 20
2.5.3 A Uniform Variant of SQL/XML . . . . . . . . . . . . . . . 22
2.6 A Flat Representation of Nesting . . . . . . . . . . . . . . . . . . 22
2.6.1 (Un)Boxing . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.6.2 Compilation of Nesting . . . . . . . . . . . . . . . . . . . . 27
2.6.3 Nesting in Action . . . . . . . . . . . . . . . . . . . . . . . 29
2.7 Summary and Related Work . . . . . . . . . . . . . . . . . . . . . 29
2.7.1 Logical Algebra and Order . . . . . . . . . . . . . . . . . . 31
2.7.2 Representing Nesting . . . . . . . . . . . . . . . . . . . . . 32
2.7.3 More Loop Lifting . . . . . . . . . . . . . . . . . . . . . . 32
viiviii CONTENTS
3 Back-End Code Generation 35
3.1 MonetDB/XQuery . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.1 MonetDB . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1.2 MonetDB Interpreter Language . . . . . . . . . . . . . . . 37
3.1.3 Plan Generation for MonetDB . . . . . . . . . . . . . . . . 37
3.1.4 MIL Code Generation . . . . . . . . . . . . . . . . . . . . 40
3.2 SQL Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.1 Translating Algebra Plans to SQL . . . . . . . . . . . . . . 41
3.3 A First Quantitative Assessment . . . . . . . . . . . . . . . . . . 42
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4 Logical Query Optimization 47
4.1 Peephole . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2 House Cleaning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.1 Empty Table Propagation . . . . . . . . . . . . . . . . . . 50
4.2.2 Standard Operator Simpli cation . . . . . . . . . . . . . . 51
4.2.3 An Alternative to Selection Pushdown . . . . . . . . . . . 58
4.2.4 Ane to Projectionwn . . . . . . . . . . 62
4.2.5 Common Subplan Elimination . . . . . . . . . . . . . . . . 65
4.2.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.3 Order Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3.1 Order Simpli cation . . . . . . . . . . . . . . . . . . . . . 71
4.3.2 Numbering Operator Conversion . . . . . . . . . . . . . . 73
4.3.3 Order Pushup . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.4 Query Unnesting . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4.1 Equi-Join Pushdown . . . . . . . . . . . . . . . . . . . . . 78
4.4.2 Distinct Operator Relocation . . . . . . . . . . . . . . . . 81
4.4.3 Dependency Disentanglement . . . . . . . . . . . . . . . . 83
4.4.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.5 Improving XML Queries . . . . . . . . . . . . . . . . . . . . . . . 87
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5 Optimization Assessment 91
5.1 Analyzing the Query Plan Shape . . . . . . . . . . . . . . . . . . 91
5.1.1 Detection of Value-Based Joins . . . . . . . . . . . . . . . 92
5.1.2 Query Formulation . . . . . . . . . . . . . . . . . . . . . . 96
5.2 Quantitative Evaluation . . . . . . . . . . . . . . . . . . . . . . . 99
5.2.1 XMark on MonetDB/XQuery . . . . . . . . . . . . . . . . . 100
5.2.2 Join Graph Isolation on DB2 . . . . . . . . . . . . . . . . 102
5.2.3 Loop Lifting an Ordinary Database Workload . . . . . . . 107CONTENTS ix
6 Summary and Outlook 111
6.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.1.1 Optimization of Large Query Plans . . . . . . . . . . . . . 112
6.1.2 Order Minimization . . . . . . . . . . . . . . . . . . . . . . 112
6.1.3 Unnesting of Loop Lifted Query Plans . . . . . . . . . . . 112
6.1.4 MonetDB/XQuery and Path nder . . . . . . . . . . . . . . 113
6.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.3 Open Problems and Future Work . . . . . . . . . . . . . . . . . . 114
6.3.1 More XML Related Optimizations for XQuery . . . . . . 114
6.3.2 Surrogate Values in Optimized Query Plans . . . . . . . . 114
6.3.3 Automatization of Rewrites . . . . . . . . . . . . . . . . . 115
Bibliography 117
Acknowledgments 127x CONTENTS

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.