Ein Optimierer für GReQL2

Inhaltsverzeichnis

1. Einleitung

1.1. Programmverstehen mit GUPRO
1.2. Die nächste Generation von GUPRO

2. Grundlagen
2.1. Die Anfragesprache GREQL2
2.1.1. Das Beispielschema RoadMap
2.1.2. Die Beispielinstanz des RoadMap-Schemas
2.1.3. Zwei exemplarische GREQL2-Anfragen
2.2. Das GREQL2-Schema
2.3. Der GREQL2-Auswerter
2.4. Die Anfrageoptimierung in relational Datenbankensystemen
2.4.1. Die algebraische Optimierung
2.4.2. Die Low-Level-Optimierung
2.4.3. Die Optimierung in Datenbanken und GREQL2

3. Die Arbeitsweise des GREQL1-Optimierers
3.1. Die Erkennung gleicher Teilausdrücke
3.2. Die Bewertungsfunktion
3.3. Die Transformationen
3.3.1. Selektion so früh wie möglich
3.3.2. Pfadprädikate in Pfadausdrücke wandeln
3.3.3. Boolsche Terme in IF-Form wandeln
3.3.4. Boolsche Terme in Konjunktionsketten wandeln
3.3.5. Variablen-Permutation 12 Inhaltsverzeichnis
3.3.6. Variablen mittels Heuristiken anordnen
3.3.7. Verlagere den Body quantifizierter Prädikate in Bedingung
3.3.8. Pfadprädikate zusammenfassen
3.4. Der Suchalgorithmus

4. Der GREQL2-Optimierer
4.1. Die Architektur des Optimierers
4.2. Wiederverwendung von optimierten Syntaxgraphen
4.3. Das Logging von Auswertungsgrößen
4.3.1. Das Interface EvaluationLogger
4.3.2. Granularitätsstufen beim Logging
4.3.3. Logging bei paralleler Anfrageauswertung
4.3.4. Die Wahl der Loggingdatei
4.3.5. Das Logging der Auswertungsgrößen der einzelnen Syntaxgraph- knoten
4.3.6. Zusammenfassung
4.4. Ein Kostenmodell basierend auf Erfahrungswerten
4.4.1. Das Interface CostModel
4.4.2. Die konkreten Kostenmodelle
4.5. Die Erkennung und Verschmelzung gemeinsamer Teilgraphen
4.6. Das Zusammenfassen von SimpleDeclarations
4.7. Die Transformation “Selektion so früh wie möglich”
4.7.1. Die Struktur der hier betrachteten Anfragen
4.7.2. Die Auswertung der betrachteten Anfragen
4.7.3. Das Finden von vorziehbaren Prädikaten
4.7.4. Die Transformationen für die frühe Selektion
4.7.5. Das Splitten einer SimpleDeclaration
4.7.6. Das Vorziehen von Prädikaten in eine SimpleDeclaration mit einer Variable
4.7.7. Das Vorziehen von Prädikaten in eine SimpleDeclaration mit mehreren Variablen
4.7.8. Einige Beispiele Inhaltsverzeichnis
4.8. Die Transformation “Pfadexistenz-Prädikate in Funktionsanwendungen wandeln”
4.8.1. Die Auswertung von Pfadexistenz-Prädikaten
4.8.2. Die Transformation
4.8.3. Einige Beispiele
4.9. Die Transformation “Variablendeklarationen anordnen”
4.9.1. Die Transformation
4.9.2. Ein Beispiel
4.10. Die Transformation “Minimierung von logischen Formeln”
4.10.1. Pfad-Dissolution
4.10.2. Ein Beispiel
4.10.3. Der DissolutionOptimizer
4.11. Die Transformation “Zusammengesetzte Prädikate in Konditionalausdrücke wandeln”
4.11.1. Das Verfahren
4.11.2. Ein Beispiel
4.11.3. Der ConditionalExpressionOptimizer
4.12. Die Optimierungsstrategie

5. Eine Bewertung und Ausblick
5.1. Einige Testanfragen zur Bewertung des Optimierers
5.1.1. Drei Phasen der Anfragebearbeitung
5.1.2. Der Testdatengraph
5.1.3. Die erste Testanfrage
5.1.4. Die zweite Testanfrage
5.1.5. Die dritte Testanfrage
5.2. Eine Bewertung der Optimierungsleistung und Ausblick

A. Glossar

B. Abbildungen

Abbildungsverzeichnis

Tabellenverzeichnis

Literaturverzeichnis

1. Einleitung

Dieses Kapitel soll kurz in die Begriffswelt rund um GUPRO und TGra- phen einführen, um die Einordnung des zu entwerfenden GREQL2- Optimierers zu erleichtern. Dazu wird das Themengebiet rund um GU- PRO beschrieben und eine kurze historische Einführung gegeben

1.1. Programmverstehen mit GUPRO

GUPRO¹ ist eine vom Institut für Softwaretechnik der Universität Koblenz-Landau ent- wickelte integrierte Umgebung, die der Unterstützung des Verstehens von Programmen dient. Gerade im Reengineering ist es eine Hauptaufgabe die Struktur und etwaige Be- ziehungen zwischen Teilen von Altsystemen aufzudecken. Solche Altsysteme sind in der Regel über Jahre gewachsen und wurden ständig mit zumeist undokumentierten Bugfixes, Anpassungen an neue Gegebenheiten und Erweiterungen versorgt, so dass die ursprüng- liche Architektur stark verwässert ist

Um im Zuge von Reengineeringmaßnahmen Refactorings durchführen zu können, muss zuerst anhand der vorliegenden Artefakte (in der Regel dem Quellcode) das Programm verstanden werden. Dazu werden Parser benutzt, die aus den Artefakten Informationen extrahieren und in einem Repository speichern

Zur Speicherung der extrahierten Daten benutzt GUPRO TGraphen, d.h. gerichtete, an- geordnete Graphen, deren Kanten und Knoten typisiert und attributiert sind. Ein solcher Datengraph ist eine Instanz eines T-Graphen-Schemas

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.1.: Ein einfaches Beispielschema

Das grobgranulare Schema aus Abbildung 1.1 definiert beispielsweise den Knotentyp Function und den Kantentyp FunctionCall. Eine Funktion ist attributiert mit ihrem Namen und der Position ihrer Definition (Dateiname und Zeile), ein Funktionsaufruf ist attributiert mit seiner Position

Abbildung in dieser Leseprobe nicht enthalten

1.1. Programmverstehen mit GUPRO

Der in Abbildung 1.2 angegebene Datengraph genügt diesem Schema. Er beschreibt, dass eine Funktion a(), die in der Datei file.c ab Zeile 106 definiert wird, in der Zeile 113 eine andere Funktion b() aufruft, welche in der Datei misc.c ab Zeile 444 definiert wird

Um Anfragen an solche Datengraphen stellen zu können, wurde die Sprache GREQL ent- wickelt. In ihr formulierte Anfragen werden von einem Parser in einen Syntaxgraphen transformiert, welcher dann von einem Optimierer optimiert werden kann, um letztlich durch den Auswerter ausgewertet zu werden. Das Anfrageergebnis kann dann dem Be- nutzer präsentiert werden. Abbildung 1.3 verdeutlicht diesen Datenfluss

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.3.: Der Datenfluss bei GUPRO

Bei der Anfrageoptimierung unterscheidet man zwischen einer online- und einer offline- Verwendung. Bei der online-Verwendung hat der Optimierer neben dem Syntaxgraphen der Anfrage auch den Datengraphen und Schemainformationen zur Verfügung. Mit die- sen zusätzlichen Informationen kann eine gezieltere Optimierung vorgenommen werden. Jedoch darf die Optimierung nicht beliebig lange dauern, da in der Regel ein Benutzer die Anfrage über eine graphische Oberfläche gestellt hat und auf das Ergebnis wartet

Bei der offline-Verwendung werden Anfragen ohne Kenntnis des Datengraphen mit dem Ziel optimiert, die optimierten Anfragen zu speichern und erst später an einem Datengra- phen auszuwerten. Hier darf die Optimierung länger dauern, allerdings sind die Möglich- keiten aufgrund der fehlenden Informationen aus dem Datengraphen beschränkt

1.2. Die nächste Generation von GUPRO

Da die alte in C++ geschriebene GREQL-Implementation samt der meisten zugehöri- gen Tools und Komponenten im GUPRO-Umfeld nicht mehr heutigen softwaretechni- schen Ansprüchen genügen und nur schwer wartbar und erweiterbar sind, wurden in den letzten anderthalb Jahren umfangreiche Redesigns und Reimplementationen bestehender Altkomponenten in Java gestartet

So entwickelte Steffen Kahle im Rahmen seiner Diplomarbeit eine moderne Version der Klassenbibliothek für TGraphen namens JGRALAB. Diese erlaubt es dem Benutzer TGraphen zu erzeugen, zu manipulieren und zu traversieren. Zudem stellt sie eine objekt- orientierte Zugriffsschicht zur Verfügung, die automatisch aus einem gegebenen Schema generiert wird. Sie ermöglicht es direkt mit Instanzen der im Schema spezifizierten Kno- ten und Kanten anstatt der “Rohklassen” Vertex und Edge zu arbeiten

Katrin Marchewka ([Mar06]) entwarf eine neue GREQL-Sprachversion (GREQL2) und implementierte einen Parser für diese. GREQL2 unterstützt alle Features der Vorgän- gerversion und bringt noch einige Neuerungen mit sich. So unterstützt der Parser bei- spielsweise jetzt zusätzlich zu regulären Pfadausdrücken die von Tim Steffens in [Ste05] beschriebenen kontextfreien Pfadausdrücke

Zuletzt entwickelte Daniel Bildhauer in seiner Diplomarbeit ([Bil06]) einen GREQL2- Auswerter, welcher eine Anfrage, gegeben als GREQL2-Syntaxgraph, an einem gege- benen Datengraph auswertet und das Ergebnis als Objekt des ebenfalls in dieser Arbeit entwickelten, generischen Containerformats JValue liefert

Die einzige noch fehlende Kernkomponente ist der Optimierer, der in der vorliegenden Diplomarbeit entwickelt werden soll

2. Grundlagen

Dieses Kapitel führt in alle Grundlagen ein, die zum Verständnis der späteren Kapitel notwendig sind

Dazu wird zuerst die Sprache GREQL2 anhand eines Beispiels eingeführt, worauf sich weitere Abschnitte zum Sprachschema und der Auswertung von GREQL2-Anfragen anschließen

Zuletzt wird noch ein Blick über den Tellerrand geworfen und die An- frageoptimierung in relationalen Datenbanksystemen erläutert

2.1. Die Anfragesprache GREQL

In diesem Abschnitt soll die Anfragesprache GREQL2 anhand eines einfachen Beispiels vorgestellt werden. Damit es auch ohne GRALAB-Vorkenntnisse nachvollziehbar ist, wird zunächst ein anschauliches Schema in Form einer vereinfachten Straßenkarte eingeführt

2.1.1. Das Beispielschema RoadMap

Als Beispiel soll eine einfache Straßenkarte dienen. Das Schema ist in Abbildung 2.1 visualisiert

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1.: Das RoadMap-Schema

Die Definition mittels des JGRALAB-Formates TG ist in Listing 2.1 zu finden

In einer Straßenkarte (RoadMap) existieren zwei verschiedene Arten von Knoten (Junc- tion): Zum einen gibt es Kreuzungen (Intersection) und zum anderen gibt es Städte (City). Das Attribut roundabout gibt an, ob eine Kreuzung ein Kreisverkehr ist. Das Attribut population gibt die Einwohnerzahl einer Stadt an

Das Schlüsselwort abstract vor Junction bestimmt, dass es keine direkten Junction- Instanzen geben darf, sondern nur Instanzen von nichtabstrakten Subklassen. Sowohl Kreuzungen als auch Städte haben ein Namensattribut name, welches direkt in der Va- terklasse Junction deklariert wird. Der Einfachheit halber wird angenommen, dass alle Knoten einen eindeutigen Namen haben

Knoten, also Kreuzungen und Städte, werden durch Kanten verbunden. In einer Straßen- karte sind das Straßen (Street). Jede Straße hat einen Namen (name) und eine Länge (length). Im Schema verbindet eine Straße immer genau zwei Knoten. So wird eine reale Straße wie die B42 durch mehrere Abschnitte vom Typ Street modelliert. Ein Spe- zialfall einer Straße ist eine Autobahn (Highway), welche als zusätzliche Information die Anzahl der Spuren (lanes) trägt

2.1. Die Anfragesprache GREQL2

Abbildung in dieser Leseprobe nicht enthalten

Listing 2.1: Das RoadMap-Schema

2.1.2. Die Beispielinstanz des RoadMap-Schemas

Die konkrete Instanz dieses Schemas, anhand derer die Beispielanfragen ausgewertet wer- den, ist eine einfache Straßenkarte des Gebietes von Koblenz bis in den hohen Westerwald (Abb. 2.2, Seite 22)

Die Repräsentation als TGraph ist in Abbildung 2.3 auf Seite 23 zu sehen

Im Kontext von JGRALAB unterscheidet man zwischen Klasse und Typ. Der Knoten v7 gehört zur Klasse Intersection, aber ebenso zu deren Superklasse Junction. Eben- so gehört die Kante e6 zur Klasse Highway als auch zu deren Vaterklasse Street. Der JGRALAB-Klassenbegriff gleicht also jenem der objektorientierten Programmierung. Im Gegensatz dazu hat jeder Knoten oder jede Kante genau einen Typ, welcher gleich seiner speziellsten Klassenzugehörigkeit ist. Der Typ von v7 ist also Intersection, der Typ von e6 ist Highway

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2.: Die Straßenkarte von Koblenz bis in den hohen Westerwald

2.1.3. Zwei exemplarische GREQL2-Anfragen

Die Anfrage aus Listing 2.2 gibt alle Knoten (Junction) des Graphen zusammen mit dem jeweiligen Typ des Knotens aus, für die gilt, dass sie mit dem Stadtknoten mit Namen Montabaur direkt verbunden sind

Abbildung in dieser Leseprobe nicht enthalten

Listing 2.2: An Montabaur angrenzende Knoten

Eine einfache GREQL-Query besteht aus einem sogenannten FWR-Ausdruck, wobei FWR für From-With-Report steht

Im from-Teil werden lokale Variablen deklariert. Im Beispiel wird also eine Variable junction der Knotenklasse (man beachte das V für Vertex) Junction deklariert und eine Variable montabaur der Knotenklasse City

Bei der Auswertung wird die Variable junction nacheinander an alle Knoten gebun- den, welche einer der Subklassen Intersection oder City angehören. Die Variable montabaur wird für jede Belegung von junction nacheinander an alle City-Knoten gebunden. Das liegt daran, dass junction außen und montabaur innen deklariert ist, was semantisch zwei geschachtelten Schleifen entspricht

2.1. Die Anfragesprache GREQL2

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3.: Die TGraphrepräsentation der Straßenkarte

Es folgt ein optionaler with-Teil, der ein Prädikat enthält, welches die Werte der dekla- rierten Variablen erfüllen müssen. In oben genanntem Beispiel muss das Namensattribut der Variable montabaur den Wert “Montabaur” haben, und die Knoten montabaur und junction müssen über eine beliebige Kante verbunden sein. Dies wird durch den regu- lären Pfadausdruck in Zeile 4 von Listing 2.2 erreicht

Ein regulärer Pfadausdruck lässt sich nach Behling [Beh97] und Marchewka [Mar06] induktiv wie folgt definieren:

Definition 1. Eine einfache Pfadbeschreibung besteht aus einem Kantensymbol (−− >,

< −− oder < − >), welchem optional ein in geschweifte Klammern eingeschlossener Kantentypbezeichner folgt

Sind p1 und p2 Pfadbeschreibungen, so auch

- die Sequenz p1p
- die Iterationen p∗ (beliebig oft) und p+ (einmal oder öfter)
1
- die Alternative p1 | p
- die Option [p1]

24 2. Grundlagen

- die Zielknotenrestriktion p1 & VertexType
- die Klammerung (p1)
- die Potenz pn
- die transponierte Pfadbeschreibung pT
- die Startknotenrestriktion VertexType & p
- die Kantenpfadbeschreibung p1 − −anEdge− > p
- die Zwischenknotenrestriktion p1 aNode&{Expression} p

Ein Pfad ist eine alternierende Folge von Kanten und Knoten

Die report-Klausel bestimmt, welche Ausdrücke in die Ergebnismultimenge aufgenom- men werden. Im Beispiel aus Listing 2.2 besteht diese aus dem Knoten, welcher in der Form id: Typ ausgegeben wird, und seinem Namen

Ein FWR-Ausdruck wird durch das Schlüsselwort end abgeschlossen. Das Ergebnis der Auswertung der Query ist:

{v7: Intersection, Autobahndreieck Dernbach (A3/A48)}

{v2: City, Langenhahn}

{v5: City, Neuhaeusel}

Ein Vergleich mit Abbildung 2.3 auf Seite 23 zeigt, dass die gefundenen drei Knoten tat- sächlich die einzigen direkt mit Montabaur verbunden Knoten sind

Zuletzt soll noch eine etwas komplexere Anfrage betrachtet werden. Um diese zu ver- stehen, müssen zusätzlich zu den regulären Pfadausdrücken noch Pfadsysteme eingeführt werden

Ein Pfadsystem wird nach Berg [Ber03] durch einen Anfangsknoten v und einen regu- lären Pfadausdruck α bestimmt. In ihm ist zu jedem von v über einen α-förmigen Pfad erreichbaren Knoten genau ein Pfad enthalten. Im allgemeinen kann es mehrere solche Pfade geben

Die GREQL2-Anfrage aus Listing 2.3 berechnet einen Weg von Rennerod nach Koblenz mit Zwischenstation Hachenburg

In den Zeilen eins bis drei werden dazu Variablen der Klasse City deklariert. Sie werden ohne Optimierung nacheinander an alle möglichen Städtekombinationen gebunden, aber nur wenn der Ausdruck in den Zeilen vier bis sechs zu true evaluiert, wird der report- Teil ausgewertet. In diesem wird der gefundene Pfad ausgegeben

In Zeile 7 wird der Pfad von Rennerod über Hachenburg nach Koblenz berechnet. Da- zu wird zuerst ein Pfadsystem mit Anfangsknoten ren erzeugt, welches zu jedem von ren über hab erreichbaren Knoten genau einen Pfad enthält. Da die Variablen ren, hab und kob bereits im with-Teil geeignet eingeschränkt wurden, extrahiert die Funktion

2.1. Die Anfragesprache GREQL2

Abbildung in dieser Leseprobe nicht enthalten

Listing 2.3: Die Suche nach einer mögliche Route von Rennerod nach Koblenz mit Zwi- schenstation Hachenburg

extractPath() einen Pfad, der tatsächlich von Rennerod über Hachenburg noch Ko- blenz führt. Hierbei ist wichtig zu beachten, dass die Pfade in einem Pfadsystem keines- falls die kürzesten sein müssen. Im allgemeinen ist nicht einmal Zyklenfreiheit garan- tiert

Das Anfrageergebnis ist

v1: City ---e1: Street-> v2: City ---e3: Street->

v3: City ---e4: Street-> v5: City ---e5: Street-> v6: City

In Abbildung 2.3 auf Seite 23 kann abgelesen werden, dass der gefundene Weg von Ren- nerod über Langenhahn nach Montabaur führt. Von dort aus geht es über Neuhäusel nach Koblenz

2.2. Das GREQL2-Schema

Wie bereits erwähnt, erzeugt der GREQL2-Parser beim Lesen einer Anfrage einen ab- strakten Syntaxgraphen, welcher die interne TGraphen-Repräsentation der Anfrage dar- stellt und dem GREQL2-Schema genügt. Dieses ist ausführlich in Katrin Marchewkas Diplomarbeit [Mar06] beschrieben, so dass hier nur eine kurze Einführung anhand des Beispiels in Listing 2.4 gegeben wird

Abbildung in dieser Leseprobe nicht enthalten

Listing 2.4: Die Anfrage zur Bestimmung aller Straßen

Man kann sehen, dass lokale Variablen einer Kantenklasse mit E für Edge deklariert wer- den. Da kein with-Teil angegeben wurde, wird jeder an die Variable street gebunde- ne Wert in die Ergebnismultimenge aufgenommen. reportBag ist gleichbedeutend mit report, jedoch erlaubt letzteres noch die Angabe von Spaltennamen, die hier ohnehin nicht verwendet werden. Will man statt einer Multimenge, die Duplikate enthalten darf, lieber eine Menge als Ergebnis haben, so kann man dies in der Anfrage durch reportSet zum Ausdruck bringen

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4.: Der Syntaxgraph der Kantenanfrage

Der Syntaxgraph der Anfrage aus Listing 2.4 ist in Abbildung 2.4 angegeben

Das Wurzelelement einer GREQL-Query ist immer ein Knoten des Typs Greql2Expres- sion

Der FWR-Ausdruck wird als BagComprehension-Knoten v6 modelliert.

Die Variablendeklarationen im from-Teil werden durch einen über eine isCompDeclOf-Kante verbundenen Declaration-Knoten, welcher beliebig viele SimpleDeclaration-Knoten enthält, repräsentiert.

Im Beispiel wird nur eine Variable street deklariert. Sie wird an Kanten (E im Anfragetextbzw. EdgeSetExpression im Syntaxgraphen) gebunden und wird durch ihreKlassenzugehörigkeit eingeschränkt (isTypeRestrOf). Diese muss Street oder eineUnterklasse davon (type = false) sein. Bei type = true könnten nur Kanten vom TypStreet an die Variable street gebunden werden, nicht aber Kanten vom Typ Highway.Mit excluded = true lässt sich die Bedeutung invertieren: street ließe sich dann nuran Kanten, die gerade nicht der Klasse Street angehören, binden. Im Beispielgraphenaus Abbildung 2.3 auf Seite 23 träfe das jedoch auf keine Kante zu, so dass das Auswertungsergebnisdie leere Menge wäre.

Die Gestalt der einzelnen Ergebnisse, die durch die reportBag-Klausel bzw. den entsprechendenBagComprehension-Knoten zusammengefasst werden, wird durch den durch eineisCompResultDefOf-Kante verbundenen Ausdruck bestimmt. Da im Beispiel sowohldie String-Repräsentation der Kante als auch der Kantenname ausgegeben werden sollen,muss mittels einer TupleConstruction ein Tupel erzeugt werden. Das erste Elementist der Wert der Variable street an sich, das zweite Element ist das Resultat der Funktionsanwendung(FunctionApplication) street.getValue(“name”), das denWert desAttributs name des an die Variable street gebundenen Elements liefert.

Der Vollständigkeit halber soll auch hier das Auswertungsergebnis der Anfrage angegebenwerden.

{e6: Highway , A3}

{e4: Street , B49}

{e2: Street , B414}

{e3: Street , B255}

{e1: Street , B255}

{e7: Highway , A48}

{e5: Street , B49}

Auch hier lässt sich die Korrektheit wieder leicht anhand Abbildung 2.3 auf Seite 23verifizieren.

2.3. Der GREQL2-Auswerter

In diesem Abschnitt wird die Funktionsweise des GREQL2-Auswerters beschrieben, da nur dann Aussagen über Optimierungsmöglichkeiten gemacht werden können.

Der Auswerter muss eine Funktion GreqlSyntaxgraph×Datengraph→JValue berechnen. Er bekommt also eine GREQL-Anfrage in Form eines Syntaxgraphen und den Datengraphen, auf welchen sich die Anfrage bezieht. Dann wertet er die Anfrage auf dem Datengraphen aus und liefert das Ergebnis als Objekt des generischen Containerformats JValue.

Das ist wie folgt implementiert: VertexEvaluator ist die Vaterklasse von über fünfzig weiteren Auswerterklassen, die spezialisiert für die einzelnen Knotentypen sind. Diese heißen TEvaluator, wenn T der Name eines Knotentyps ist. VertexEvaluator selbst ist abstrakt und definiert eine Methode evaluate(), die das Ergebnis der Auswertung des Knotens als JValue liefert und von allen Subklassen geeignet implementiert werden muss. Zusätzlich enthält VertexEvaluator eine statische Factory-Methode

VertexEvaluator createVertexEvaluator (Vertex vertex ,

GreqlEvaluator eval),

die mittels Reflection anhand des Typs von vertex den passenden VertexEvaluator für diesen Knoten erzeugt.

Im ersten Auswertungsschritt wird über alle Knoten des Syntaxgraphen iteriert. Für jeden Knoten wird mit createVertexEvaluator() ein passender VertexEvaluator erzeugt und als temporäres Attribut des Knotens gespeichert.

Die eigentliche Auswertung wird dann durch Aufruf der evaluate()-Methode des Auswerterobjekts des Wurzelknotens Greql2Expression gestartet. Dessen Auswerter, der Greql2ExpressionEvaluator, ermittelt nun die VertexEvaluator-Objekte der Kindknoten und ruft bei jenen die getResult()-Methode auf, welche entweder evaluate() aufruft oder ein bereits berechnetes und zwischengespeichertes Ergebnis zurückgibt. Dies wird rekursiv bis zu den Blättern des Syntaxgraphen fortgeführt, und jeder Nicht-Blatt- Knoten kombiniert die Ergebnisse seiner Kindknoten entsprechend seiner Semantik.

Um den Berechnungsaufwand möglichst gering zu halten, erfolgt die Auswertung falls möglich nach dem Prinzip der lazy evaluation (verzögerte Auswertung). Das heißt, dass Teilergebnisse nur dann (neu) berechnet werden, wenn sie in einer anderen Berechnung benötigt werden.

Da die Funktionen der GREQL-Funktionsbibliothek aber als Klassen mit einer eval- uate()-Methode definiert sind, welche die Funktionsargumente als Parameter vom Typ JValue erhält, kann dieses Prinzip bei der Auswertung von FunctionApplication- Knoten nicht eingesetzt werden. So werden beim Funktionsaufruf and(A, B) die Ausdrücke A und B vor der Funktionsanwendung and() ausgewertet, obwohl die Berechnung des Ergebnisses von B unnötig ist, falls A bereits zu false ausgewertet wurde. Bei der Auswertung von GREQL2-Funktionen handelt es sich also um eager evaluation (strikte Auswertung).

Das Ergebnis einer Knoten-Auswertung wird als temporäres Attribut des entsprechendenVertexEvaluator-Elements gespeichert. Wird danach erneut getResult() aufgerufen,so wird das zwischengespeicherte Ergebnis geliefert. Der Auswerter speichert zu jederVariable eine Liste von VertexEvaluator-Objekten, deren Ergebnisse von dieser Variablebeeinflusst werden. Bei jeder Variableniteration werden die dadurch ungültig werdendenTeilergebnisse gelöscht und somit eine Neuberechnung veranlasst.

Dies soll am Beispiel aus Listing 2.5 verdeutlicht werden.

Abbildung in dieser Leseprobe nicht enthalten

Listing 2.5: Ein Primzahlbeispiel

In der Anfrage werden a, b und c nacheinander an die Belegungen (7, 7, 7), (7, 7, 8), ..., (20, 20, 19) bis (20, 20, 20) gebunden. Dabei wird zuerst die innerste Variable c inkrementiert, dann b und zuletzt die äußerste Variable a. Da jede der Variablen 14 verschiedene Werte annehmen kann, gibt es insgesamt 143 = 2744 Belegungen, für die der with-Teil evaluiert werden muss.

Wie bereits erwähnt, sind in GREQL2 alle Operatoren wie das logische and oder equals als Funktion implementiert, was zur Folge hat, dass alle Parameter ausgewertet werden müssen. Der with-Teil der Anfrage in äquivalenter Präfix-Notation ist:

and(isPrime(a), and(equals(a, b), equals(b, c)))

Das Ergebnis von isPrime(a) wird nur 14 mal berechnet, da a nur 14 mal den Wert wechselt. Die restlichen 2730 mal liefert getResult() des entsprechenden Function- ApplicationEvaluator-Objekts das zwischengespeicherte Ergebnis der letzten Neuberechnung.

Das Resultat der Funktionsanwendung equals(a, b), welches in obiger Anfrage in der Infixnotation a = b geschrieben wurde, wird nur 196 mal neu berechnet, weil b nur nach jeweils 14 Iterationsschritten an einen neuen Wert gebunden wird. Der zweite Vergleich equals(b, c) wird immer komplett neu berechnet, da sich der Wert von c nach jedem Iterationsschritt ändert.

Damit müssen auch beide and-Funktionsanwendungen bei jedem Iterationsschritt erneut berechnet werden. Die folgende Tabelle fasst die Anzahl der Neuberechnungen der jeweiligen Ausdrücke noch einmal zusammen.

Abbildung in dieser Leseprobe nicht enthalten

Das Ergebnis der Anfrage ist die Menge aller Dreiertupel gleicher Primzahlen zwischen 7 und 20.

{11, 11, 11}

{17, 17, 17}

{19, 19, 19}

{7, 7, 7}

{13, 13, 13}

Im folgenden Abschnitt wird der Themenbereich rund um GREQL2 kurzzeitig verlassen und ein Einblick in die Optimierung von Anfragen in relationalen Datenbanksystemen gegeben.

2.4. Die Anfrageoptimierung in relational Datenbankensystemen

Gemäß [Vos04] unterteilt sich die Anfrageverarbeitung in relationalen Datenbanksystemen in vier Phasen.

1. In der Vorverarbeitung wird der als Anfrage in einer deklarativen Hochsprache wie SQL vorliegende Ausdruck in eine interne, prozedurale Form der Relationenalgebra umgeformt und Views durch ihre Definitionen ersetzt.
2. Danach erfolgt die High-Level- oder algebraische Optimierung, bei der Äquivalenzumformungen auf den Ausdruck angewendet werden.
3. Bei der Low-Level-Optimierung wird zum bereits optimierten Ausdruck ein möglichst kostenminimaler Ausführungsplan (query execution plan, QEP) erzeugt.
4. In der Anfrage-Ausführung wird zuletzt der im vorangegangenen Schritt gewählte QEP ausgeführt und das Anfrageergebnis berechnet.

Ziel der Anfrageoptimierung der Schritte 2 und 3 ist, einen Anfrageausdruck vor der Ausführung in einen äquivalenten Ausdruck umzuformen, dessen Ergebnis mit dem der Originalanfrage übereinstimmt, die Ausführungskosten jedoch geringer sind.

Dabei können die Kostenarten vielfältig und für jede Datenbank und jeden Einsatzzweck verschieden gewichtet sein. Einige Faktoren sind zum Beispiel

- die Wartezeit für den Benutzer,
- die tatsächlich verbrauchte CPU-Zeit,
- der Speicherverbrauch,
- die Anzahl von I/O-Operationen, insbesondere von Sekundärspeicherzugriffen,
- der gesamte Ressourcenverbrauch und eventuell auch
- der benötigte Energieverbrauch.

In den folgenden Abschnitten werden die beiden Optimierungsschritte 2 und 3 etwas genauer erläutert.

2.4.1. Die algebraische Optimierung

In der algebraischen Optimierung wird ein in der Relationenalgebra vorliegender Ausdruck in mehreren Schritten in einen äquivalenten Ausdruck, der allerdings kosteneffizienter zu berechnen ist, umgeformt.

Vossen liefert in [Vos04] folgende Äquivalenz-Definition.

Definition 2. Es sei D = (R, .); E und E′ seien Ausdrücke aus RA. E und E′ heißen

äquivalent, i. Z. E ≈ E′, falls gilt: (∀d ∈ Dat(R)) vE(d) = vE′(d)

Zwei Ausdrücke E und E′ der Relationenalgebra RA heißen also äquivalent, falls sie bei jeder Auswertung bezüglich jedes aktuellen Zustands d über dem gegebenen Datenbankschema D das gleiche Ergebnis liefern.

Die Ausdrücke liegen dabei als Baum vor, wobei die Blätter die Operanden, die inneren Knoten Operationen und die Kanten den Datenfluss repräsentieren. Zur Optimierung wird insbesondere versucht die Zwischenergebnisse der Auswertung zu verkleinern indem Selektionen und Projektionen möglichst weit nach unten im Baum gezogen und so möglichst früh angewendet werden.

Eine von Vossen beschriebene Heuristik zur Durchführung der algebraischen Optimierung

umfasst zum Beispiel die folgenden Schritte:

1. Zerlege Selektionsoperationen, deren Bedingung eine Konjunktion von elementaren Bedingungen ist, in eine Folge von Selektionsoperationen. Damit können die Selektionen in späteren Schritten separat behandelt werden.
2. Schiebe Selektionen vorbei an anderen Operationen so weit wie möglich nach unten im Anfragebaum.
3. Nimmt man an, dass der Anfragebaum von links nach rechts ausgewertet wird, so rearrangiere die Blätter des Baums derart, dass jene, die mit den restriktivsten Selektionsoperationen verbunden sind, am weitesten links stehen.
4. Im letzten Schritt zerlege Projektionen und verschiebe sie im Baum so weit wie möglich nach unten.

Hierbei muss darauf geachtet werden, dass keine Join-Attribute, die später benötigt werden, durch Projektionen entfernt werden, was den Verbund zu einem teuren

kartesischen Produkt degenerieren würde.

Zuletzt kann sich eine Suche nach identischen Teilausdrücken anschließen, mit dem Ziel, diese zu verschmelzen und so nur einmal auszuwerten.

2.4.2. Die Low-Level-Optimierung

Bei der Low-Level-Optimierung geht es um die Erzeugung eines möglichst effizienten Ausführungsplans. Während die algebraische Optimierung auf der sogenannten logischen Algebra, also dem Datenmodell des Systems (z.B. Relationenalgebra) arbeitet, benutzt die Low-Level-Optimierung zur Formulierung von QEPs die physische Algebra. Diese stellt systemspezifische Operatoren bereit, die jene der logischen Algebra implementieren. Somit können hier Implementierungsdetails berücksichtigt werden.

Hierbei gibt es drei wesentliche Aspekte:

1. die Umformung eines Ausdrucks der logischen Algebra in einen Ausführungsplan
2. eine Suchstrategie, die beschreibt, wie zu einem gegebenen QEP weitere alternative QEPs erzeugt werden können
3. eine Kostenfunktion, mit der sich die einzelnen Ausführungspläne bewerten lassen

Bei den Suchstrategien gibt es zum einen die vollständige Suche (z.B. Tiefensuche oder Breitensuche), die aus einem initialen QEP alle möglichen Alternativ-QEPs erzeugt und bewertet. Nur bei vollständiger Suche kann der Fund eines optimalen Ausführungsplans garantiert werden, jedoch ist der Kostenaufwand dazu immens. Zum anderen existieren Heuristiken, die meistens zwar einen suboptimalen QEP liefern, dafür aber hinreichend schnell sind. In der Regel ist man vor allem an der Vermeidung eines besonders schlechten als am Fund des optimalen Ausführungsplans interessiert, so dass der Einsatz von Heuristiken ausreichend ist.

Zur Bewertung alternativer Ausführungspläne zwecks Selektion des Besten, hat die Kostenfunktion die Aufgabe, die gegebenen QEPs einer möglichst realistischen und effizienten Kostenabschätzung zu unterziehen. Hierbei können alle bereits am Anfang dieses Abschnitts erwähnten Faktoren wie CPU-Zeit oder die Anzahl von I/O-Operationen eingehen. Wurde zwischen den verschiedenen alternativen Ausführungsplänen der laut Kostenfunktion effizienteste gewählt, wird dieser zur Ausführung gebracht.

2.4.3. Die Optimierung in Datenbanken und GREQL2

Bei der Anfrageauswertung in Datenbanksystemen entfallen große Teile der Kosten auf Zugriffe auf den Hintergrundspeicher oder die Generierung von Dateien zur Speicherung von Zwischenergebnissen. Die Bibliothek JGRALAB hält den Datengraphen, auf dem eine Anfrage ausgewertet werden soll, komplett im Hauptspeicher. Daher können solche Kosten vernachlässigt werden, und der Fokus liegt auf den reinen Berechnungskosten.

3. Die Arbeitsweise des GREQL1-Optimierers

Dieses Kapitel beleuchtet die Arbeitsweise des GREQL1-Optimierers von David Polock ([Pol97]). Dieser hat die gleiche Zielsetzung wie der zu entwickelnde GREQL2-Optimierer, nämlich die Umformung des Syntaxgraphen der Anfrage derart, dass das Auswertungsergebnis der optimierten und der Originalanfrage gleich sind, jedoch die Auswertungszeit der optimierten Anfrage stark verringert wird. Die Gliederung wurde von Polocks Arbeit übernommen.

Zuerst wird beschrieben, wie der GREQL1-Optimierer die Mehrfachberechnung gleicher Teilausdrücke in Anfragen vermeidet.

Danach wird die Bewertungsfunktion vorgestellt, mit welcher der Optimierer abschätzt, ob eine Umformung des Syntaxgraphen die Auswertung beschleunigt.

Zuletzt werden alle Transformationen, die der GREQL1-Optimierer auf den Syntaxgraphen anwenden kann, beschrieben.

[...]

---

¹ Generic Understanding of PROgrams,http://www.gupro.de