Zusammenfassung. Die Nutzung komplexer Algorithmen zur Analyse oft hochdimensionaler Datensatze gerat im Kontext von "Big Data\ immer mehr in das Zentrum der Aufmerksamkeit. Um diese komplexen Datenanalysen e zient zu ermoglichen liegt es nahe, sie in die am weitesten verbreiteten Datenspeicher zu integrieren { in relationale Datenbanksysteme. Dies fuhrt zu interessanten Fragestellungen nicht nur im Bereich der technischen Integration sondern besonders auch in der Anfragespezi kation und -auswertung. In diesem Kurzbeitrag beschreiben wir, wie Algorithmen zur Datenanalyse e zient und nutzerfreundlich in das relationale Hauptspeicherdatenbanksystem HyPer integriert werden konnen. Wir evaluieren unseren Ansatz anhand eines Vergleichs mit zwei verbreiteten Datenanalysesystemen auf Graph- und Vektordaten.
SAP HANAs Predictive Analytics Library [
Im Gegensatz hierzu streben wir eine tiefere Integration mit SQL an, sodass SQL- und Data-Mining-Anfragen nahtlos miteinander verwendet und kompiliert werden konnen.
In diesem Kurzbeitrag stellen wir am Beispiel von HyPer dar, wie Data-MiningAlgorithmen e zient in relationale Datenbanksystemen integriert werden konnen. Die wichtigsten Kontributionen unseres Beitrags sind zusammengefasst: { Mehrschichtiges Spezi kationsmodell zur Erstellung und Nutzung der Algorithmen, bestehend aus Laien-, Domanenexperten- und Programmierer-Sicht { SQL-Erweiterung zur Spezi kation von e zienten iterativen Algorithmen { Laufzeitvergleiche mit Data-Mining-Anwendungen am Beispiel der Algorithmen PageRank (fur Graphdaten) und K-Means (fur Vektordaten) 2
Arten der Integration von Algorithmen in HyPer Existierende Datenanalysesysteme nutzen hau g eigene, meist proprietare, Sprachen oder APIs, um Analysen zu spezi zieren. Dies hat diverse Nachteile. Unubliche Anfragesprachen machen es notig, die Nutzer { hau g Datenanalysten aus der Anwendungsdomane { aufwandig zu schulen. Werden Hochsprachen-APIs { z.B. in Java { verwendet, gibt es zwar viele erfahrene Programmierer, jedoch haben diese selten das notige Domanenwissen. Bei in Hochsprachen spezi zierten Anfragen ist es zudem fur das Datenanalysesystem sehr schwierig, die Anfrage zu optimieren, um eine e ziente Ausfuhrung zu ermoglichen.
Wir wahlen daher einen neuartigen, mehrstu gen Ansatz fur die Integration von Data Mining in HyPer. Unser Ziel ist es, Domanenspezialisten auf einfache Art und Weise e ziente Anfragen spezi zieren zu lassen, wahrend Spezialisten alle Freiheitsgrade behalten. Die vier im folgenden vorgestellten Stufen der Integration unterscheiden sich daher sowohl in der Machtigkeit der Spezi kation, als auch in den Moglichkeiten des DBMS, die Anfragen zu optimieren.
Um allgemeine Data-Mining-Funktionalitat anzubinden, bei der das DBMS nur als Datenspeicher verwendet wird, bietet HyPer PostgreSQL-kompatible Datenbankschnittstellen, u.a. JDBC. Zwar ermoglichen diese beliebige Berechnungen, jedoch verhindert der Zugri uber sie umfassende Anfrageoptimierungen und fuhrt potentiell zu teurem Datenaustausch zwischen den beteiligten Systemen. 2.2
Als tiefergehende Integration von Data Mining erlaubt HyPer die Ausfuhrung von Nutzercode als User-de ned Functions (UDFs). Wie bei anderen Datenbanksystemen konnen berechtigte Nutzer dabei beliebige Funktionalitat hinzufugen. Diese wird dann entweder direkt innerhalb des Datenbanksystems (unfenced ) oder in einer Sandbox (fenced ) ausgefuhrt. Dadurch ist es nicht mehr notig, Daten in externe Systeme zu kopieren. 2.3
Oft lassen sich Data-Mining-Algorithmen nur umstandlich in SQL ausdrucken. Dies liegt unter anderem daran, dass viele Verfahren iterativ sind. Um diese in SQL abzubilden kommen hau g rekursive Common Table Expressions (WITHStatements) zum Einsatz, die eine monoton wachsende Relation berechnen. Da iterative Algorithmen im Normalfall jedoch nur auf die Daten der vorherigen Iteration zugreifen, um die aktuelle Iteration zu berechnen, wird bei diesem Vorgehen viel Speicher unnutz belegt. Dies ist vor allem fur Hauptspeicherdatenbanksysteme ein Problem, da Speicher hier eine besonders wertvolle Ressource ist. Als Losung fur dieses Problem schlagen wir ein Iterationskonzept fur SQL vor. Syntaktisch ist dieses an WITH angelehnt: with recursive [Algo] as ([Initialization] iterate [Step] until [Condition]) select * from [Algo]
Es wird hier eine temporare Relation Algo erstellt, die anfangs das Resultat der
Unteranfrage Initialization enthalt und auf die iterativ Step angewendet wird, bis
der boolsche Ausdruck Condition wahr ist. Diese Spracherweiterung erlaubt es uns,
iterative Data-Mining-Verfahren auf einfache Weise direkt in SQL auszudrucken.
Dies ermoglicht nicht nur die direkte Verwendung des ausgereiften
state-of-theart relationalen Anfrageoptimierers von HyPer, sondern auch die Nutzung der
hochoptimierten parallelen Codegenerierungs- und Ausfuhrungsengine [
Im Gegensatz zu anderen Datenbanksystemen integriert HyPer wichtige DataMining-Funktionalitat direkt im Datenbankkern. Fur den Nutzer sind diese syntaktisch nicht von den zuvor beschriebenen UDFs zu unterscheiden. So berechnet folgende Anfrage fur jeden Knoten des durch die Kanten in edges gebildeten Graphen die parametrisierte PageRank-Metrik:1 select * from pagerank((select src,dest from edges), 0.85, 0.001)
Intern wird die Berechnung jedoch von spezialisierten Operatoren ausgefuhrt, in diesem Fall durch einen Sort- gefolgt von einem PageRank-Operator.
HyPer wahlt dabei u.a. eine e ziente interne Graphreprasentation und fuhrt weitere Vorverarbeitungsschritte durch, um die Metrik zu berechnen. Des Weiteren kennt der Anfrageoptimierer die genauen Eigenschaften des PageRank-Operators und kann somit den optimalen Ausfuhrungsplan wahlen.
Lambda-Ausdrucke Vorde nierte Funktionen allein decken jedoch nicht alle Einsatzzwecke ab. HyPer erlaubt daher die Verwendung von Lambda-Ausdrucken in SQL-Anfragen. Dies ermoglicht etwa im K-Means-Algorithmus den Einsatz benutzerde nierter Distanzfunktionen, wobei die volle Optimierbarkeit der Anfrage erhalten bleibt. Bei entsprechend gewahlter Distanzfunktion konnen dabei numerische und kategorische Daten kombiniert analysiert werden, was unverzichtbar fur Datenbanksysteme mit ihren verschiedenen Datentypen ist.
In diesem Abschnitt evaluieren wir unsere Ansatze aus den Abschnitten 2.3,
nachfolgend HyPer SQL, und 2.4, im Folgenden HyPer Op. Wir
implementieren dazu jeweils einen Graph- und Vektoralgorithmus. PageRank wahlen wir
als bekannten Vertreter der Graphverfahren und als Basis weiterer iterativer
Algorithmen. Fur Vektordaten verwenden wir K-Means, ein hau g genutztes
Clusteringverfahren [
Als Vergleichssysteme verwenden wir Apache Spark 1.4.0 [
In unseren Tests, Tabelle 2, zeigt MATLAB die langsten Laufzeiten und das schlechtere Skalierungsverhalten3, weshalb wir uns in der weiteren Auswertung auf den Vergleich mit Spark fokussieren. Im Bezug auf die Vektordatensatze zeigen HyPer und Spark ein ahnliches Skalierungsverhalten, wobei HyPer im Datenbankkern jedoch um Faktor 1{2 schneller ist. Fur die PageRank-Graphanalyse zeigt sich, dass HyPer sowohl besser skaliert als Spark, als auch 1{2 Gro enordnungen schneller ist. HyPer mit in SQL spezi zierten Data-Mining-Anfragen zeigt Potential, erzeugt aber im Fall von K-Means noch keine optimalen Ausfuhrungsplane. 1 Die explizite Klammerung der Unteranfrage ist notig, da wir dort beliebige Anfragen erlauben; einfache Kommatrennung fuhrt zu Mehrdeutigkeiten in der Grammatik. 2 Siehe https://github.com/ldbc/ldbc_snb_datagen. 3 MATLAB fuhrt die Algorithmen sequentiell aus. Jedoch ware die Laufzeit auch bei perfekter Skalierung uber die sechs verfugbaren CPU-Kerne noch immer unterlegen.
Tabelle 1. Datensatze zur Evaluierung der gewahlten Verfahren Datensatz K-Means, k = 3, 3 Iterationen PageRank, d = 0:85, e = 0:0001
Tabelle 2. Laufzeiten in Sekunden, OOM = Out of Memory
HyPer Op
HyPer SQL Syn 1 Syn 2 Syn 3 LDBC SF 1 LDBC SF 10 Zusammenfassung Wir haben eine vierschichtige Integration von Data Mining in unser relationales Hauptspeicherdatenbanksystem HyPer vorgestellt. Wichtige Algorithmen sind hochoptimiert im Datenbankkern integriert und konnen direkt per SQL aufgerufen werden, wo sie auch Laien leicht zuganglich sind. Zusatzliche Algorithmen konnen durch unsere Spracherweiterung direkt in SQL spezi ziert werden und nutzen somit HyPers e ziente Codegenerierung und Laufzeitumgebung. Unsere Testergebnisse zeigen, dass Data Mining auf Vektor- und Graphdaten in HyPer performanter ist und besser skaliert als in vergleichbaren state-of-the-art Datenanalysesystemen. Zeitaufwandige ETL-Zyklen entfallen.