Dossinger Manuel

• Processing data streams is a classical and ubiquitous problem. A query is registered against a potentially endless data stream and continuously delivers results as tuples stream in. Modern stream processing systems allow users to express queries in different ways. However, when a query involves joins between multiple input streams, the order of these joins is not transparently optimized. In this thesis, we explore ways to optimize multi-way theta joins, where the join predicates are not limited to equality and multiple inputs are referenced. We put forward a novel operator, MultiStream, which joins multiple input streams using iterative probing and bringing minimal materialization effort in. The order in which tuples are sent inside a MultiStream operator is optimized using a cost-based model. Further, a query can be answered using an multi-way tree comprising multiple MultiStream operators where each inner operator represents a materialized intermediate result. We integrate equi-joins in MultiStream to reduce communication, such that mixed queries of theta and equality predicates are supported. Streaming queries are long-standing and thus multiple queries might be registered at the system at the same time. Hence, we research joint answering of multiple multi-way join queries and optimize the global ordering using integer linear programming. All these approaches are implemented in CLASH, a system for generating Apache Storm topologies including runtime components that enables users to pose queries in a declarative way and let the system craft the suitable topology.
• Datenstromverarbeitung ist ein klassisches und universelles Problem. Datenströme sind endlos und das Ergebnis einer Datenstromanfrage ist wiederum ein Strom, daher ist eine Anfrage potentiell für eine unbegrenzte Zeit aktiv. Moderne datenstromverarbeitende Systeme erlauben es Benutzern, Anfragen auf verschiedene Arten auszudrücken. Allerdings wird die Reihenfolge von mehreren Join-Operationen nicht transparent optimiert, wenn eine Anfrage mehrere Eingabeströme involviert. In dieser Arbeit erforschen wir wie Mehrwege-Theta-Joins – das bedeutet, Prädikate sind nicht auf Gleichheit beschränkt und mehrere Eingaben werden referenziert – optimiert werden können. Wir stellen einen neuartigen Operator vor, MultiStream, welcher mehrere Eingabeströme mittels iterativen Sondierens verbinden kann und der minimalen Materialisierungsaufwand benötigt. Die Reihenfolge, in der Tupel innerhalb eines MultiStream-Operators gesendet werden, wird mit Hilfe eines kostenbasierten Models optimiert. Weiterhin kann eine Anfrage durch einen Mehrwegebaum beantwortet werden, welche aus mehreren MultiStream-Operatoren besteht und wobei jeder innere Operator einem materialisierten Zwischenergebnis entspricht. Um den Kommunikationsaufwand für Anfragen, die zum einen Teil aus beliebigen Prädikaten und zum anderen Teil aus Gleichheiten bestehen, zu verringern, integrieren wir Equijoinberechnung in MultiStream. Datenstromanfragen sind für längere Zeit aktiv and so können mehrere Anfragen gleichzeitig in einem System registriert sein. Für solche Fälle untersuchen wir das gemeinsame Beantworten mehrerer solcher Mehrwege-Join-Anfragen und optimieren die globale Reihenfolge mittels ganzzahliger linerarer Programmierung. Alle diese Ansätze haben wir in CLASH implementiert, ein System, das Apache-Storm-Topologien und passende Laufzeitkomponenten erstellt. Dieses System erlaubt Benutzern beliebige Anfragen deklarativ zu stellen und erstellt daraufhin eine passende Topologie.