Optimization of query sequences

Abstract

Query optimization is a well-known topic in database research since the 1970s. This thesis highlights a special area of query optimization that arises from new trends in the usage of databases. Whereas in the beginning databases were primarily used for transaction-oriented processing of operative data, today databases are also used to facilitate reporting and analysis on consolidated, historic data. For the latter, the data is loaded into a large data warehouse and afterwards it is being analyzed by the use of tools. The tools used to model the flows that extract the operative data from the source systems, transform these data and load it into the data warehouse as well as the tools that process the data stored in the data warehouse often generate sequences of SQL statements that break down a complex flow or request into a sequence of computational steps. The optimization of this kind of sequences with respect to runtime is the focus of this thesis. We propose a heuristic as well as a cost-based approach for this optimization problem. The cost-based approach is just an enhancement of the heuristic approach. It results from adding a cost estimation component to the optimizer architecture of the heuristic approach and by replacing the heuristic control strategy by a control strategy that considers cost estimates. Both approaches are rule-based approaches that rewrite a given sequence of SQL statements into a syntactically different but semantically equivalent sequence of SQL statements. Therefore, we specify a set of rewrite rules. For cost estimation, we employ the capabilities of the query optimizer of the underlying database management system (DBMS) which is responsible for the execution of the query sequences. To improve the quality of these cost estimates, we support the query optimizer of the underlying DBMS with statistics that we derive from histogram propagation. For this purpose, we need an interface that allows to access and manipulate statistics in the underlying DBMS. Since there exists no standardized interface for this purpose, we define our own DBMS-independent interface. For the heuristic approach as well as for the cost-based approach, we provide prototypic implementations in JAVA. Furthermore, we have implemented the DBMS-independent interface for the three commercial DBMSs IBM DB2, Oracle, and Microsoft SQL Server. We report on the results of experiments that we conducted with our prototypes and some sample sequences that we derived by using a commercial tool for online analytical processing (OLAP). They show the effectiveness of our optimization approach and they highlight the optimization potential that lies in rewriting sequences of SQL statements. Finally, we draw a conclusion and suggest some interesting points for future research.

Die Anfrageoptimierung in relationalen Datenbanksystemen ist ein Forschungsgebiet in der Informatik, dessen Anfänge bis in die 70er Jahre zurückreichen. Diese Arbeit fokussiert auf ein spezielles Gebiet innerhalb der Anfrageoptimierung, das sich aus neuen Trends der Datenbanknutzung ergibt. Während Datenbanksysteme in den Anfangsjahren in erster Linie für die transaktionale Verarbeitung operationaler Daten eingesetzt wurden, werden sie heute auch immer mehr im Rahmen von Business-Intelligence-Anwendungen zur Speicherung riesiger historischer Datenbestände genutzt, welche die Basis für umfangreiche Analysen und Berichte bilden. Dazu werden die Daten aus den operativen Systemen extrahiert, transformiert und in ein Data Warehouse geladen. Die Daten werden während der Transformation konsolidiert, bereinigt und teilweise auch aggregiert. Die Werkzeuge, die zur Modellierung der Prozesse, welche das Extrahieren, Transformieren und Laden bewerkstelligen, eingesetzt werden wie auch die Werkzeuge, welche anschließend die Daten des Data Warehouse verarbeiten, um daraus Modelle und Berichte zu erstellen, generieren oft Sequenzen von SQL-Anweisungen. Die Sequenzen von SQL-Anweisungen, die im Folgenden als Anfragesequenzen bezeichnet werden, repräsentieren die Realisierung eines solchen Prozesses oder einer komplexen Fragestellung in Form mehrerer einfacher Berechnungsschritte. Die Optimierung dieser Anfragesequenzen bezüglich ihrer Ausführungszeit ist der Schwerpunkt dieser Arbeit. Hierfür wird ein heuristischer Ansatz wie auch ein kostenbasierter Ansatz vorgestellt. Der kostenbasierte Optimierer stellt dabei eine Erweiterung des heuristischen Optimierers um eine Kostenschätzkomponente für Anfragesequenzen dar. Des Weiteren ersetzt der kostenbasierte Optimierer die heuristische Kontrollstrategie des heuristischen Optimierers durch eine kostenbasierte. Beide Ansätze basieren auf Restrukturierungsregeln, die eine gegebene Anfragesequenz in eine zwar syntaktisch andere, aber semantisch äquivalente Anfragesequenz umformen. Für die Kostenschätzung werden die Kostenschätzwerte des Optimierers im darunterliegenden Datenbanksystem, welches später die Anfragesequenzen ausführt, genutzt. Um die Qualität dieser Kostenschätzwerte zu verbessern, werden Histogramme durch die Anfragesequenzen propagiert und dem Optimierer im darunterliegenden Datenbanksystem als Statistiken zur Verfügung gestellt. Um auf die Statistiken im darunterliegenden Datenbanksystem zugreifen und diese manipulieren zu können, wird eine entsprechende Schnittstelle benötigt. Da es hierfür jedoch keine standardisierte Schnittstelle gibt, wird im Rahmen dieser Arbeit eine solche Schnittstelle definiert, welche einen Datenbankmanagementsystem-unabhängigen Zugriff erlaubt. Für den heuristischen Optimierer sowie für die Kostenschätzkomponente des kostenbasierten Optimierers wurde ein Prototyp in der Programmiersprache Java erstellt. Des Weiteren wurde die Schnittstelle, welche einen Datenbankmanagementsystem-unabhängigen Zugriff auf Statistiken erlaubt, für die drei Datenbankmanagementsysteme IBM DB2, Oracle und Microsoft SQL Server implementiert. Anschließend wurden mit den Prototypen und einer Auswahl an Anfragesequenzen Experimente durchgeführt, welche die Effektivität und das Potential dieser Optimierungsansätze belegen. Die Arbeit schließt mit einem Fazit und einem Ausblick auf mögliche Folgearbeiten.