Query Optimization in Distributed Heterogeneous Data Stream Systems

Data stream systems support queries on continuously arriving data. They provide similar query facilities like relational database systems. However, data stream systems continuously evaluate the queries on the arriving data and discard the data afterwards. Thus, it is possible to process high volumes of rapidly arriving data. Application examples are the monitoring of IT infrastructure or the processing of data from wireless sensor networks in wildland or animal surveillance scenarios. Compared to centralized data stream systems, distributed data stream systems can lower the resource demand, improve the performance and increase the lifetime of wireless sensor networks. This is particularly true if the data sources are already distributed and the hosts of the data sources take part in query processing. In my dissertation, I investigate the interdependencies of logical query optimization and the assignment of operators to hosts for distributed data stream systems on heterogeneous hosts. In particular, I discuss the mathematical representation of selected optimization goals and constraints like resource limits for cost-based query optimization. I propose a technique to estimate whether logical query optimization steps may interfere with the subsequent assignment of operators to hosts. Well-known heuristic algorithms are adapted to the optimization problem of assigning operators to hosts. An evaluation compares the different algorithms. Moreover, I propose an algorithm for load balancing by multiple instantiation of operators. Datenstromsysteme ermöglichen die Auswertung von Anfragen auf kontinuierlich anfallenden Daten in ähnlicher Weise wie relationale Datenbanksysteme auf persistenten Daten. Jedoch speichern Datenstromsysteme die Daten nicht, sondern werten sie direkt beim Eintreffen gemäß den vorhandenen Anfragen aus. Dadurch ist die Verarbeitung großer Mengen stetig eintreffender Daten möglich. Anwendungsbeispiele sind die Infrastrukturüberwachung in Rechenzentren und die Auswertung von Daten drahtloser Sensornetzwerke zur Überwachung von Tieren oder Bereichen in der Natur. Verteilte Datenstromsysteme können gegenüber nicht verteilten Datenstromsystemen eine höhere Leistungsfähigkeit bieten, den Ressourcenbedarf senken und im Falle von drahtlosen Sensornetzwerken deren Lebensdauer erhöhen. Dies ist insbesondere möglich bei verteilten Datenquellen und wenn die Systeme der Datenquellen selbst Teile der Anfrageverarbeitung übernehmen. Die vorliegende Dissertation untersucht die Zusammenhänge zwischen logischer Optimierung und der Entscheidung, welcher Operator auf welchem System ausgeführt werden soll, im Kontext verteilter Datenstromsysteme auf heterogenen Systemen. Konkret werden mathematische Repräsentationen ausgewählter Optimierungsziele und Nebenbedingungen, wie etwa Ressourcenbeschränkungen, für die kostenbasierte Optimierung beschrieben. Es wird eine Möglichkeit vorgestellt abzuschätzen, ob eine bestimmte logische Optimierung nachteilig für die folgende Zuweisung von Operatoren zu den Systemen sein kann. Mehrere bekannte heuristische Algorithmen werden an das Optimierungsproblem, welches System welche Operatoren ausführen soll, angepasst. In einer Evaluation wird die Eignung der verschiedenen Algorithmen für dieses Optimierungsproblem verglichen. Schließlich wird ein Algorithmus zur Lastverteilung mittels mehrfacher Instanziierung von Operatoren vorgestellt.