Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-5150
Main Title: Specification and optimization of analytical data flows
Translated Title: Spezifikation und Optimierung analytischer Datenflüsse
Author(s): Hüske, Fabian
Advisor(s): Markl, Volker
Referee(s): Kao, Odej
Gemulla, Rainer
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: In the past, the majority of data analysis use cases was addressed by aggregating relational data. Since a few years, a trend is evolving, which is called “Big Data” and which has several implications on the field of data analysis. Compared to previous applications, much larger data sets are analyzed using more elaborate and diverse analysis methods such as information extraction techniques, data mining algorithms, and machine learning methods. At the same time, analysis applications include data sets with less or even no structure at all. This evolution has implications on the requirements on data processing systems. Due to the growing size of data sets and the increasing computational complexity of advanced analysis methods, data must be processed in a massively parallel fashion. The large number and diversity of data analysis techniques as well as the lack of data structure determine the use of user-defined functions and data types. Many traditional database systems are not flexible enough to satisfy these requirements. Hence, there is a need for programming abstractions to define and efficiently execute complex parallel data analysis programs that support custom user-defined operations. The success of the SQL query language has shown the advantages of declarative query specification, such as potential for optimization and ease of use. Today, most relational database management systems feature a query optimizer that compiles declarative queries into physical execution plans. Cost-based optimizers choose from billions of plan candidates the plan with the least estimated cost. However, traditional optimization techniques cannot be readily integrated into systems that aim to support novel data analysis use cases. For example, the use of user-defined functions (UDFs) can significantly limit the optimization potential of data analysis programs. Furthermore, lack of detailed data statistics is common when large amounts of unstructured data is analyzed. This leads to imprecise optimizer cost estimates, which can cause sub-optimal plan choices. In this thesis we address three challenges that arise in the context of specifying and optimizing data analysis programs. First, we propose a parallel programming model with declarative properties to specify data analysis tasks as data flow programs. In this model, data processing operators are composed of a system-provided second-order function and a user-defined first-order function. A cost-based optimizer compiles data flow programs specified in this abstraction into parallel data flows. The optimizer borrows techniques from relational optimizers and ports them to the domain of general-purpose parallel programming models. Second, we propose an approach to enhance the optimization of data flow programs that include UDF operators with unknown semantics. We identify operator properties and conditions to reorder neighboring UDF operators without changing the semantics of the program. We show how to automatically extract these properties from UDF operators by leveraging static code analysis techniques. Our approach is able to emulate relational optimizations such as filter and join reordering and holistic aggregation push-down while not being limited to relational operators. Finally, we analyze the impact of changing execution conditions such as varying predicate selectivities and memory budgets on the performance of relational query plans. We identify plan patterns that cause significantly varying execution performance for changing execution conditions. Plans that include such risky patterns are prone to cause problems in presence of imprecise optimizer estimates. Based on our findings, we introduce an approach to avoid risky plan choices. Moreover, we present a method to assess the risk of a query execution plan using a machine-learned prediction model. Experiments show that the prediction model outperforms risk predictions which are computed from optimizer estimates.
In der Vergangenheit wurde die überwiegende Mehrheit der Datenanalyseanwendungen durch die Aggregation von relationalen Daten abgedeckt. Seit einigen Jahren entwickelt sich ein Trend der “Big Data” genannt wird und der große Auswirkungen auf den Bereich der Datenanalyse hat. Im Vergleich zu bisherigen Analyseanwendungen, werden nun wesentlich größere Datenmengen mit deutlich aufwändigeren und vielfältigeren Analysemethoden wie zum Beispiel Techniken der Informationsextraktion, des Data Minings, und Verfahren des maschinellen Lernens ausgewertet. Dabei werden auch Daten in die Analyse einbezogen, die weniger stark oder überhaupt nicht strukturiert sind. Die Veränderungen der Eigenschaften von Datenanalyseanwendungen wirken sich auch auf die Anforderungen an Systeme zur Datenverarbeitung aus. Aufgrund des gestiegenen Datenvolumens und des durch komplexere Analyseverfahren deutlich höheren Berechnungsaufwands müssen Daten massiv parallel verarbeitet werden. Die gestiegene Vielfalt von Analyseverfahren und die geringere Struktur der Daten erfordern häufig den Einsatz von benutzerdefinierten Funktionen und Datenstrukturen. Viele traditionelle Datenbanksysteme sind nicht flexibel genug, um diesen Anforderungen gerecht zu werden. Deshalb gibt es ein großes Interesse an neuen Programmierabstraktionen mit denen komplexe und parallele Datenanalyseanwendungen spezifiziert und effizient ausgeführt werden können. Der Erfolg der Anfragesprache SQL hat die Vorzüge von deklarativer Anfragespezifikation, wie zum Beispiel Optimierungspotenzial und Benutzerfreundlichkeit, deutlich gezeigt. Heute nutzt nahezu jedes relationale Datenbanksystem einen Anfrageoptimierer der deklarative Anfragen in physische Ausführungspläne übersetzt. Kostenbasierte Optimierer sind in der Lage aus Milliarden von möglichen Plänen einen effizienten Plan auszuwählen. Allerdings lassen sich traditionelle Optimierungsmethoden nicht ohne weiteres in Systeme integrieren, die neuartige Anwendungsfälle von Datenanalyse unterstützen wollen. Zum Beispiel kann der Einsatz von benutzerdefinierten Operationen das Optimierungspotenzial sehr stark reduzieren. Darüberhinaus sind selten detaillierte Datenstatistiken verfügbar, wenn große unstrukturierte Datensätze analysiert werden. Fehlende Statistiken haben häufig ungenaue Kostenschätzungen des Optimierers und somit die Auswahl von suboptimalen Ausführungsplänen zur Folge. In dieser Arbeit adressieren wir drei Herausforderungen im Kontext der Spezifikation und Optimierung von parallelen Datenanalyseprogrammen mit benutzerdefinierten Funktionen. Zunächst stellen wir ein paralleles Programmiermodell mit deklarativen Eigenschaften vor um Datenanalyseprogramme als Datenflußprogramme zu spezifizieren. In diesem Modell bestehen Datenverarbeitungsoperatoren aus einer systemeigenen Funktion zweiter Ordnung und einer benutzerdefinierten Funktion erster Ordnung. Ein kostenbasierter Optimierer übersetzt Datenflußprogramme, die in unserem Programmiermodell definiert wurden, in parallele Datenflüße. Unser Optimierer baut auf viele Techniken der relationalen Optimierung auf und überträgt sie in die Domäne von universellen parallelen Programmiermodellen. Zweitens präsentieren wir einen Ansatz zur Verbesserung der Optimierung von Datenflußprogrammen, die benutzerdefinierte Operatoren mit unbekannter Semantik enthalten. Wir identifizieren Eigenschaften von Operatoren und Bedingungen, um die Reihenfolge von benachbarten benutzerdefinierten Operatoren zu verändern ohne die Semantik eines Programms zu ändern. Wir zeigen wie diese Eigenschaften für benutzerdefinierte Operatoren vollautomatisch mit Hilfe von statischer Codeanalyse aus deren Quellcode extrahiert werden können. Mit unserem Ansatz können viele relational Optimierungen wie zum Beispiel die Optimierung der Reihenfolge von Filtern, Joins und Aggregationen emuliert werden ohne jedoch auf relationale Operatoren beschränkt zu sein. Drittens analysieren wir den Einfluß von sich verändernden Ausführungsbedingungen wie zum Beispiel variierenden Prädikatselektivitäten und verfügbaren Hauptspeichermengen auf die Laufzeit von relationalen Ausführungsplänen. Wir identifizieren Planeigenschaften, die deutliche Laufzeitschwankungen auslösen können. Im Fall von ungenauen Optimiererschätzungen können Pläne, die diese Eigenschaften enthalten, ein sehr großes Risiko darstellen. Wir präsentieren einen Ansatz, um die Auswahl von riskanten Plänen zu vermeiden. Darüberhinaus stellen wir eine Methode vor, um das Risiko von Ausführungsplänen mit Hilfe eines maschinell-gelernten Modells vorher zusagen. Unsere Evaluation zeigt, dass mit unserem Vorhersagemodell das Risikopotenzial eines Plans besser abgeschätzt werden kann als mit Hilfe eines kostenbasierten Optimierers.
URI: http://depositonce.tu-berlin.de/handle/11303/5482
http://dx.doi.org/10.14279/depositonce-5150
Exam Date: 14-Dec-2015
Issue Date: 2016
Date Available: 27-May-2016
DDC Class: DDC::000 Informatik, Informationswissenschaft, allgemeine Werke
Subject(s): parallel data processing
query optimization
PACT programming model
MapReduce
Apache Flink
data flows
data analysis
big data
database systems
parallele Datenverarbeitung
Anfrageoptimierung
PACT Programmiermodell
Datenflüsse
Datenanalyse
Datenbanksystem
Creative Commons License: https://creativecommons.org/licenses/by/4.0/
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Fachgebiet Datenbanksysteme und Informationsmanagement (DIMA) » Publications

Files in This Item:
File Description SizeFormat 
hueske_fabian.pdf2.1 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.