Optimierung von Preference-SQL-Anfragen

Prof. Dr. Werner Kießling (Leiter)
B. Hafenrichter

Die Grundidee der Optimierung besteht darin, die relationale Algebra um einen zusätzlichen Operator, die so genannte Präferenz-Selektion σ[P](R) zu erweitern.

Veröffentlichungen

Das Design und die Implementierung von personalisierten Datenbankapplikationen stellt hohe Anforderungen an die zugrunde liegende Datenbanktechnologie. Personalisierung bedeutet, individuell auf die Wünsche eines Benutzers einzugehen und entsprechend dessen Wünschen zu reagieren. Gerade in diesem Bereich fällt die Unterstützung durch Datenbanksysteme sehr gering aus, da bis vor kurzem keinerlei Augenmerk auf diese Belange gelegt wurde.
Der Ansatz, Benutzerwünsche (Präferenzen) als strikte partielle Ordnungen zu modellieren, ist die Grundlage für die Erweiterung bestehender Datenbanksysteme. Hierbei sind aber nicht nur die reinen Modellierungsaspekte von Interesse. Ebenso wichtig ist die effiziente Berechnung von Abfragen bzw. Ergebnismengen. Dieser Aspekt ist Inhalt des Forschungsprojekts "Optimierung von Preference-SQL-Anfragen".
Die Grundidee besteht darin, die relationale Algebra um einen zusätzlichen Operator, die so genannte Preference-Selektion σ[P](R) zu erweitern. überträgt man die Erkenntnisse der klassischen Datenbankoptimierung auf den Bereich Präferenzen, so besteht das Ziel darin, möglichst frühzeitig überflüssige Daten zu eliminieren, um die Berechnung von Zwischenergebnissen zu beschleunigen (vgl. Abbildung). Hierzu ist es notwendig, den Operatorbaum so umzuformen, dass der Operator σ[P] möglichst frühzeitig angewandt wird. Neben den Gesetzen der klassischen relationalen Algebra wurden deshalb zusätzliche Transformationsregeln entwickelt, welche die Umformung von Preference-SQL-Abfragen erlauben.

Als Beispiel für die Transformation des Operatorbaums dient nachfolgende Preference-SQL-Abfrage:
"SELECT s.name, u.price
 FROM    used_cars u, category c, seller s
 WHERE  u.sid = s.sid AND
                 u.ref = c.ref AND
                (u.color = red OR u.color = gray)
 PREFERRING (LOWEST u.age AND u.price BETWEEN 5000, 6000)
                PRIOR& TO c.brand IN (BMW)
                PRIOR& TO s.zipcode AROUND 86609".

Abbildung:
Der zur obigen Preference-SQL-Abfrage zugeordnete Operatorbaum VOR der Optimierung (links) und NACH der Optimierung (rechts)

Um die Optimierungseffekte der Transformationsregeln zu evaluieren, wurde ein heuristischer Datenbankoptimierer als Forschungsprototyp entwickelt, welcher auf Basis von benutzerdefinierten Regeln beliebige Preference-SQL-Anfragen optimiert. Hierbei wurde besonderes Augenmerk auf eine hohe Flexibilität gelegt, so dass es jederzeit möglich ist, weitere Regeln hinzuzufügen. Das gesamte System wurde in Java 1.3 implementiert, wobei der Datenbankzugriff über JDBC erfolgt.
In umfangreichen Testreihen wurde die Qualität der einzelnen Optimierungen untersucht. Die Messergebnisse haben hierbei die Annahme bestätigt, Preference-Operatoren möglichst frühzeitig zu berechnen. Selbst im Vergleich mit dem Produkt "Preference-SQL", welches die Anfragen basierend auf einer Rewriting-Technologie berechnet, konnte der Prototyp seine Vorteile klar herausstellen. Insgesamt ist also der Ansatz der algebraischen Optimierung wesentlich besser als eine reine Rewriting-Technologie.
Ein Ergebnis aus den Testreihen ist die Aussage, dass der Umfang der möglichen Optimierungen stark von der Query-Struktur abhängt. Deshalb wird nun in einer dritten Phase untersucht, inwieweit die Join-Order der beteiligten Relationen Einfluss auf das Ergebnis einer Preference-SQL-Abfrage hat. Erste Ergebnisse belegen, dass mit einer geschickten Wahl der Join-Reihenfolge noch bessere Anfragezeiten erzielt werden können, als dies mit dem reinen heuristischen Optimierer möglich ist.
Wie die Testreihen gezeigt haben, liegt in dem Ansatz, Preference-SQL-Anfrage algebraisch zu optimieren, ein sehr hohes Potential. Aus diesem Grund müssen die Ergebnisse in weiteren Schritten auf so genannte "cost-based"-Optimierer übertragen werden.