Efficient Generation and Execution of DAG-Structured Query Graphs


Neumann, Thomas


[img]
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.




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