Integrating skyline queries into spark SQL : Efficient and productive integration of skyline queries into apache spark SQL

Abstract

Skyline Anfragen werden üblicherweise von Datenanalysten und Datenanalystinnen verwendet, um "interessante" Punkte in Datenbanken oder ähnlichen Datensammlungen zu finden. Sie können in Empfehlungsmaschinen oder für die Visualisierung von "interessanten" Punkten verwendet werden. Die von Skyline Anfragen verarbeiteten Datenmengen sind häufig groß und in verteilten Datenbanksystemen gespeichert. Spark ist ein mächtiges, vereinheitlichtes Analyse-System, das gut zur Verarbeitung von großen verteilten Datenmengen geeignet ist. Die Komponente Spark SQL erlaubt es, SQL-ähnliche Datenabfragen als Zeichenkette oder als API-Zugriff zu schreiben. Skyline Anfragen werden in Spark nicht direkt unterstützt. Daher setzen wir uns die Integration von Skyline Anfragen in Spark zum Ziel. Dadurch kombinieren wir die Vorteile von Skyline Anfragen und Spark SQL. Dies erlaubt uns, Skyline Anfragen einfach als eine Erweiterung von SQL zu schreiben und diese mithilfe von Spark auszuführen. Um dies zu erreichen, zeigen wir, wie Skyline Anfragen integriert werden, sodass sowohl Anfragezeichenketten als auch Zugriffe per DataFrame/DataSet API ausgeführt werden können. Dies beinhaltet auch die PySpark Integration, sodass Skyline Anfragen auch in Python Skripten, die Spark verwenden, benutzt werden können. Wir implementieren unterschiedliche Algorithmen und Optimierungen, um die Leistungsfähigkeit zu steigern. Dies beinhaltet einen Block-Nested-Loop Algorithmus, einen verteilten Algorithmus auf Basis eines MapReduce-Ansatzes und einen spezialisierten verteilten Algorithmus für Skylines auf Basis von Datenmengen mit fehlenden Werten. Abschließend führen wir Benchmarks sowohl in einer lokalen Umgebung als auch in einer verteilten Cluster-Umgebung durch, um die Leistungsfähigkeit unserer Implementierung zu erheben. Aus diesen Benchmarks können wir eine gute Leistungsfähigkeit ablesen. Diese ist besser als jene von vergleichbaren Anfragen, die auf reines SQL setzen um dieselben Resultate zu berechnen.

Skyline queries are commonly used by data scientist for finding "interesting" data points in databases or other collections of data. They can also be used in recommendation engines or to visualize "interesting" parts of datasets. The datasets processed by skyline queries are often large and stored in a distributed manner. Spark is a powerful unified analytics engine that is good at handling large, distributed datasets. The Spark SQL component of Spark also allows writing SQL-like queries as strings and using an API to access the data. We, therefore, set the integration of skyline queries into Spark as our main goal. Thereby, we combine the advantages of skyline queries and Spark SQL. This allows us to easily write skyline queries as an extension of SQL and run the query using Spark. To achieve this, we show how skyline queries can be integrated into both query strings and the DataFrame/DataSet API of Spark. This includes integration into PySpark such that skyline queries can also be executed in Python scripts that use Spark. We implement different algorithms and optimizations to boost performance. This includes a block-nested-loop algorithm, a distributed algorithm based on common MapReduce approaches to compute skyline queries, and a specialized distributed algorithm which can handle skylines on incomplete datasets. Lastly, we run benchmarks on both a local and a clustered environment to get a better understanding of the performance of our implementation. From these benchmarks, we can see that the integration gives us good performance figures which are much better than those of equivalent "plain" SQL queries which calculate the same results.