|
Efficient Generation and Execution of DAG-Structured Query Graphs
Neumann, Thomas
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)  Vorschau |
|
PDF
dissertation.pdf
- Veröffentlichte Version
Download (1MB)
|
|
URL:
|
http://ub-madoc.bib.uni-mannheim.de/1089
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-10896
|
|
Dokumenttyp:
|
Dissertation
|
|
Erscheinungsjahr:
|
2005
|
|
Titel einer Zeitschrift oder einer Reihe:
|
None
|
|
Verlag:
|
Universität Mannheim
|
|
Gutachter:
|
Moerkotte, Guido
|
|
Datum der mündl. Prüfung:
|
1 Juli 2005
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Practical Computer Science III (Moerkotte 1996-)
|
|
Fachgebiet:
|
004 Informatik
|
|
Fachklassifikation:
|
CCS:
H.2.4 I.2. ,
|
|
Normierte Schlagwörter (SWD):
|
Datenbanksystem , Abfrageverarbeitung , Implementierung
|
|
Freie Schlagwörter (Englisch):
|
query optimization , factorization , runtime system
|
|
Abstract:
|
Traditional database management systems use tree-structured query evaluation plans. While easy to implement, a tree-structured query evaluation plan is not expressive enough for some optimizations like factoring common algebraic subexpressions or magic sets. These require directed acyclic graphs (DAGs), i.e. shared subplans. This work covers the different aspects of DAG-structured query graphs. First, it introduces a novel framework to reason about sharing of subplans and thus DAG-structured query evaluation plans. Second, it describes the first plan generator capable of generating optimal DAG-structured query evaluation plans. Third, an efficient framework for reasoning about orderings and groupings used by the plan generator is presented. And fourth, a runtime system capable of executing DAG-structured query evaluation plans with minimal overhead is discussed. The experimental results show that with no or only a modest increase of plan generation time, a major reduction of query execution time can be achieved for common queries. This shows that DAG-structured query evaluation plans are serviceable and should be preferred over tree-structured query plans.
|
|
Übersetzter Titel:
|
Effiziente Generierung und Ausführung von DAG-strukturierten Anfragegraphen
(Deutsch)
|
|
Übersetzung des Abstracts:
|
Traditionelle Datenbankmanagementsysteme verwenden baumstrukturierte Ausführungspläne. Diese sind effizient und einfach zu implementieren, allerdings nicht ausdrucksstark genug für einige Optimierungstechniken wie z.B. die Faktorisierung von gemeinsamen algebraischen Teilausdrücken oder magic sets. Diese Techniken erfordern gerichtete azyklische Graphen (DAGs), d.h. gemeinsam verwendete Teilpläne. Die Arbeit behandelt die verschiedenen Aspekte von DAG-strukturierten Anfragegraphen. Zunächst wird ein formalen Modell zum Schließen über gemeinsam verwende Teilpläne und damit über DAG-strukturierte Anfragepläne vorgestellt. Anschließend wird dieses Modell in einem Plangenerator zur Erzeugung von optimalen DAG-strukturierten Anfrageplänen verwendet; bisherige Ansätze konnten die optimale Lösung nicht garantieren. Weiterhin wird eine neue Datenstruktur beschrieben, die dem Plangenerator eine effiziente Verwaltung von Sortierungen und Gruppierungen ermöglicht. Schließlich wird ein Laufzeitsystem vorgestellt, das die Ausführung von DAG-strukturierten Anfrageplänen mit sehr geringem Mehraufwand relativ zu baumstrukturierten Anfrageplänen ermöglicht. Die experimentellen Ergebnisse zeigen, dass ohne bzw. mit nur etwas höherem Zeitaufwand im Plangenerator DAG-strukturierte Anfragepläne erzeugt werden können, die für übliche Anfragen eine erheblich Reduzierung der Ausführungszeit bewirken können. Diese Ergebnisse zeigen, dass DAG-strukturierte Anfragepläne mit vertretbarem Aufwand allgemein einsetzbar sind und deshalb anstelle von baumstrukturierten Anfrageplänen verwendet werden sollten.
(Deutsch)
|
|
Zusätzliche Informationen:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
|
