Wissen
Die Evolution des Volcano Iterator Modells: Von Graefes Paper hin zu modernen DWH Systemen
1994 veröffentlichte Götz Graefe, einer der weltweit führenden Wissenschaftler im Bereich Datenbanken, sein grundlegendes Paper "Volcano, an Extensible and Parallel Query Evaluation System", in dem er ein Framework zur Abfrageverarbeitung innerhalb von Datenbanksystemen vorstellt. Ziel dieses Blogbeitrages ist es, die wesentlichen Konzepte des Volcano Iterator Modells vorzustellen und einen Überblick über die historische Evolution dieses Modell zu geben - soweit es für Databricks, SQL Server und Microsoft Fabric relevant ist.
Das Framework wurde schnell angenommen und bildet die Basis für die Abfrageausführung beispielsweise von Microsoft SQL Server sowie älteren Versionen von Spark. In den 30 Jahren seit der Veröffentlichung des Papers haben sowohl SQL Server als auch Spark das Modell verbessert und an Data Warehouse Workloads adaptiert. Es ist interessant zu bemerken, dass Spark in Version 2.0 zunächst vom Iterator Modell abgewichen ist, Databricks es nun aber mit der Photon Engine wieder aufnimmt.
Das Volcano Iterator Model
Das Modell betrachtet eine Abfrage als eine Menge diskreter Operatoren die auf Daten wirken und einander aufrufen. So kann ein Operator Daten aus einer Datei einlesen, der nächste Operator filtert diese Daten entlang eines Prädikats, der nächste Operator fügt eine berechnete Spalte zu den Daten hinzu und so weiter. Betrachten wir einmal eine simple SQL Abfrage. Nehmen wir an, wir haben eine Kundentabelle, die die Vor- und Nachnamen von Kunden beinhaltet, und wir führen folgende Abfrage in SQL Server aus.
SELECT
FirstName + ' ' + LastName
FROM dbo.Customer
WHERE LastName = 'Ackermann'
SQL Server erzeugt den folgenden Abfrageplan:
Wir sehen drei Operatoren. Der Table Scan Operator liest die Daten von der Festplatte (oder dem Buffer Cache), der Compute Scalar Operator konkateniert die FirstName und LastName Spalte, und der SELECT Operator sendet das Ergebnis an die aufrufende Anwendung.
Man beachte, dass wir keinen Filter Operator sehen, obwohl wir auf die LastName Spalte filtern. Ein solcher Operator existiert durchaus in SQL Server, aber der Query Optimizer versucht Prädikate so weit wie möglich nach unten zu schieben. In unserem Fall führt dies dazu, dass der Table Scan Operator bereits beim Einlesen der Daten die Zeilen filtert. Das sieht man auch, wenn man sich die Details des Operators anzeigen lässt.
Im Volcano Model implementiert jeder Operator drei Methoden:
- Open,
- Next, und
- Close.
Die Open Methode initialisiert den Operator (setzt also Datenstrukturen auf die den Zustand der Operators beschreiben), und die Close Methode baut diese Datenstrukturen ab, damit der Speicher wieder freigegeben werden kann.
Die Next Methode führt die eigentlichen Transformationen aus. Diese Methode gibt eine einzelne Zeilen an den aufrufenden Operator zurück. Der aufgerufene Operator wird selbst die Next Methode an allen seinen Child Operatoren aufrufen, um alle Daten zu sammeln die er zum Arbeiten benötigt.
Die Stärke dieses Modells liegt in seiner Einfachheit. Jede Transformation kann als eigener Operator entwickelt werden und interagiert mit anderen Transformationen mittels der Next Methode. Die klaren Grenzen zwischen den Transformationen ermöglichen einen leicht zu verstehenden grafischen Ausführungsplan. Dies hilft nicht nur bei der Entwicklung der Operatoren, sondern auch bei der Abfrageoptimierung.
Ein offensichtlicher Nachteil dieses Modells ist der große Overhead der Funktionsaufrufe bei großen Datenmengen. Da jeder Aufruf der Next Methode nur eine einzelne Zeile liefert, skaliert die Anzahl der Funktionsaufrufe linear mit der Anzahl der Zeilen.
Batch Mode / Vectorized Execution
In 2012 führte SQL Server den Batch Execution Mode ein. Im Batch Mode gibt die Next Methode einen ganzen Batch an Zeilen (etwa 900) zurück. Zunächst hatten nur eine Hand voll Operatoren den Batch Mode unterstützt, aber heute können viel mehr Operatoren damit umgehen. Der Batch Mode wurde zusammen mit Columnstore Indizes eingeführt, und es sollte zur Kenntnis genommen werden, dass Batch Mode Operatoren eine spaltenweise in memory Repräsentation der Daten verwenden, in Abweichung von der gewöhnlichen spaltenweisen Repräsentation.
Spaltenweise Repräsentation ist inzwischen zum Standard für Data Warehouse Workloads geworden und findet sich auch in Systemen wie Power BI Datasets, Parquet Dateien, dem Apache Arrow In-Memory Format sowie dem Apache Arrow Flight Netzwerkprotokoll.
Spark führte mit Version 2.0 in 2016 das gleiche Konzept unter dem Namen Vectorization ein. Databricks arbeitet zur Zeit an der proprietären Photon Engine, die ausschließlich Batch Mode mit spaltenweiser Datenrepräsentation verwendet. Das Photon Paper hebt hervor, dass zeilenweise Repräsentation immer noch der Standard in Spark ist, was die Frage aufwirft welche Teile von Spark bisher vektorisiert worden sind.
Abgesehen von diesen beiden Punkten (Spaltenweise Repräsentation von Daten und Operatoren arbeiten auf einem ganzen Batch von Zeilen), folgt der Batch Mode immer noch dem Prinzip des Volcano Iterator Modells, welches einzelne Operatoren einander aufruft und die Ergebnisse weiterreicht.
Whole-Stage Code Generation
Zusammen mit Vektorisierung hat Spark 2.0 ein weiteres Feature zur Performanceoptimierung eingeführt: Whole-Stage Code Generation. Nehmen wir noch einmal unsere SQL Abfrage von vorhin. Theoretisch könnten wir diese Abfrage auch als eine einfache For-Schleife ausdrücken (hier in PowerShell Pseudo Code):
Das wäre offensichtlich performanter als Funktionen an Operatoren aufzurufen! Und genau das ist es was Code Generation tut. Es nimmt eine SQL Abfrage, erzeugt Code der das Ergebnis dieser Abfrage berechnet, kompiliert ihn und führt ihn aus.
Der Nachteil ist, dass wir die Einfachheit des Volcano Modells verlieren. Als Databricks sich entschieden hat eine neue Ausführungsengine für die Databricks Runtime zu entwickeln haben sie zunächst zwei Prototypen gebaut, einer der auf dem Prinzip der Vektorisierung basiert (dies wurde später zur Photon Engine), und einer der aus Code Generation basiert. Dabei hat sich gezeigt, dass Code Generation zwar eine bessere Performance liefert, das Debuggen sich allerdings sehr schwierig gestaltet. Außerdem konnten sie der Photon Engine Optimisierungsregeln hinzufügen, mit denen fast die Performance des Code Generation Ansatzes erreicht wurde.
Zusammenfassend kann man festhalten, dass das Volcano Iterator Model (in der gebatchten und spaltenbasierten Version) immer noch weit verbreitet bei Data Warehouse Workloads ist. Code Generation wäre ein alternativer Ansatz, der bessere Performance liefern könnte, aber sehr schwierig zu entwickeln ist.
Über den Autor:
Benjamin Konrad ist seit 2016 als BI Berater im Microsoft Umfeld tätig und seit 2022 Teil der drjve AG. Seine Kerngebiete umfassen Power BI, Azure Data Platform und Infrastruktur, Big Data Systeme sowie Datenmodellierung. Mit langjähriger, branchenübergreifender sowie internationaler Projekterfahrung bietet er umfassende Expertise in den Bereichen Business Intelligence, Datentransformation- und analyse, und Architektur.
Bei Fragen stehe ich Ihnen gerne zur Verfügung:
Benjamin Konrad
Senior Consultant