Optimierung datenintensiver Workflows: Konzepte und Realisierung eines heuristischen, regelbasierten Optimierers

Abstract

Um die Modellierung datenintensiver Workflows, die große relationale Datenmengen verarbeiten, zu vereinfachen, wurden Workflowbeschreibungssprachen, wie BPEL, von führenden Herstellern von Workflow- und Datenbankmanagementsystemen um SQL-Funktionalität erweitert. Dadurch müssen Datenverarbeitungsoperationen, wie SQL-Anweisungen oder Aufrufe benutzerdefinierter Prozeduren, nicht mehr in Web-Services gekapselt werden, sondern können direkt auf der Workflowebene definiert werden. Daraus resultiert eine neue Möglichkeit der Anfrageoptimierung, die existierende Optimierungsansätze in Datenbanksystemen ergänzt: Suboptimal modellierte Datenverarbeitungsoperationen lassen sich in einer Workflowbeschreibung unter Verwendung von Restrukturierungsregeln derart transformieren, dass sie von einem Workflow- bzw. Datenbankmanagementsystem wesentlich effizienter ausgeführt werden können. In dieser Doktorarbeit werden Konzepte zur Realisierung eines heuristischen, regelbasierten Optimierers für datenintensive Workflows vorgestellt. Der Optimierer wendet eine Regelbasis gemäß einer wohldefinierten Kontrollstrategie auf eine interne Repräsentation für datenintensive Workflows, dem sogenannten Prozessgraphenmodell (PGM), an, um die Datenverarbeitung eines datenintensiven Workflows zu optimieren. PGM erlaubt eine effiziente und sprachunabhängige Definition und Anwendung der Restrukturierungsregeln und unterstützt somit eine Optimierung von Datenverarbeitungsoperationen, die in unterschiedlichen Beschreibungssprachen definiert sein können. Die Regelbasis enthält Restrukturierungsregeln, die auf existierenden und neuen Optimierungsstrategien beruhen. Insbesondere nutzen die Restrukturierungsregeln das Wissen über Abhängigkeiten in einer Workflowbeschreibung aus, um die darin eingebetteten Datenverarbeitungsoperationen unter Beibehaltung der ursprünglichen Ausführungssemantik eines datenintensiven Workflows zu optimieren. Die Kontrollstrategie bestimmt, welche Restrukturierungsregeln in welcher Reihenfolge auf welche Teile einer Workflowbeschreibung angewendet werden, um zum einen das Optimierungspotential eines datenintensiven Workflows umfassend zu nutzen und zum anderen die Korrektheit der Regelanwendungen sicherzustellen. Die ausführliche Beschreibung des Prozessgraphenmodells, der Regelbasis und der Kontrollstrategie stehen im Mittelpunkt dieser wissenschaftlichen Abhandlung. Des Weiteren wird eine prototypische Implementierung des Optimierungsansatzes vorgestellt, welche dessen praktische Einsatzfähigkeit unterstreicht. Schließlich wird die Effektivität der einzelnen Restrukturierungsregeln mithilfe verschiedener Messszenarien untersucht. Dabei wird gezeigt, dass durch Anwendung der Restrukturierungsregeln Leistungssteigerungen in mehreren Größenordnungen erreicht werden können.

Leading vendors of workflow- and database management systems extended workflow description languages like BPEL by SQL-functionality. This simplifies the modeling of data-intensive workflows that process huge amount of relational data. Thereby, data processing operations like SQL statements or stored procedure calls may be defined directly on the workflow level, instead of encapsulating them into Web services. Thus, a workflow description discloses the whole optimization potential concerning its data management. The outcome of this is a new query optimization approach that completes existing approaches in database systems: Rewrite rules transform inefficient data processing operations in a workflow description into equivalent operations that perform better on a workflow- and database management system respectively. This results in an improved performance of data-intensive workflows with respect to their data management. This doctoral thesis introduces a heuristic, rule-based optimizer for data-intensive workflows. In order to improve the data management of a data-intensive workflow, the optimizer applies an appropriate rule set according to a well-defined control strategy on an internal representation for data-intensive workflows, the so-called process graph model (PGM). PGM is adjusted to the optimization of data-intensive workflows and is the appropriate basis for rule-based transformations. It allows for an exact and language independent definition of rewrite rules. Consequently, it supports various optimization scenarios covering a multitude of data processing operations defined in different description languages. The rule set contains rewrite rules that are based on existing as well as on new optimization techniques. Each rewrite rule consists of two parts: a condition and an action part. The condition part defines what conditions have to hold for a rule application in order to preserve the original workflow semantics. It refers to control flow dependencies as well as to data and communication dependencies. Additionally, it considers detailed information of activities. The action part of a rewrite rule defines the transformations applied to a workflow description provided that the corresponding condition part is fulfilled. The purpose of the control strategy is to use efficiently the optimization potential of a data-intensive workflow and to ensure the correctness of a rule's application. Therefore, it identifies so-called optimization spheres, i.e., parts of a workflow, for which applicable rewrite rules should be identified. Determining such spheres is necessary because if one applies rewrite rules across spheres, the semantics of a workflow may change. Another function of the control strategy is to define the order, in which rule conditions are checked for applicability and the order, in which rules are finally applied. This scientific paper focuses in detail on the process graph model, the rule set and the control strategy. Furthermore, a prototype of the optimizer demonstrates its practical utilizability. Finally, several experiments emphasize the effectiveness of the optimization approach. The experimental results show that performance gains of orders of magnitude are achievable when applying the given set of rewrite rules to data-intensive workflows.