2021-11-12

Schnelle gleitende holistische Aggregationen

Richard Wesley

In einem früheren Beitrag haben wir die DuckDB-Windowing-Architektur beschrieben und die Unterstützung einiger fortgeschrittener gleitender Aggregationen erwähnt. In diesem Beitrag vergleichen wir die Leistung verschiedener möglicher gleitender Implementierungen dieser Funktionen und erklären, wie DuckDBs performante Implementierungen funktionieren.

Was ist eine Aggregatfunktion?

Wenn Menschen an Aggregatfunktionen denken, haben sie typischerweise etwas Einfaches im Sinn, etwa SUM oder AVG. Allgemeiner fasst eine Aggregatfunktion aber eine Menge von Werten zu einem einzelnen Wert zusammen. Solche Zusammenfassungen können beliebig komplex sein und jeden Datentyp betreffen. DuckDB bietet zum Beispiel Aggregationen zum Verketten von Strings (STRING_AGG) und zum Erzeugen von Listen (LIST). In SQL kommen aggregierte Mengen entweder aus einer GROUP BY-Klausel oder einer OVER-Windowing-Spezifikation.

Holistische Aggregationen

Alle grundlegenden SQL-Aggregatfunktionen wie SUM und MAX können berechnet werden, indem Werte nacheinander gelesen und verworfen werden. Es gibt aber Funktionen, die potenziell alle Werte im Blick behalten müssen, bevor sie ein Ergebnis liefern können. Das sind holistische Aggregationen, und sie erfordern mehr Sorgfalt bei der Implementierung.

Bei manchen Aggregationen (wie STRING_AGG) kann die Reihenfolge der Werte das Ergebnis ändern. Für Windowing ist das kein Problem, weil OVER-Klauseln eine Ordnung angeben können, in einer GROUP BY-Klausel sind die Werte jedoch ungeordnet. Um das zu handhaben, können ordnungssensitive Aggregationen eine Klausel WITHIN GROUP(ORDER BY <expr>) enthalten, um die Reihenfolge der Werte festzulegen. Weil die Werte alle gesammelt und sortiert werden müssen, sind Aggregationen mit der Klausel WITHIN GROUP holistisch.

Statistische holistische Aggregationen

Weil die Sortierung der Argumente einer windowierten Aggregation über die OVER-Klausel angegeben werden kann, könnte man sich fragen, ob es andere holistische Aggregationen gibt, die nicht sortieren oder eine andere Ordnung als die in der OVER-Klausel nutzen. Es gibt eine Reihe wichtiger statistischer Funktionen, die in SQL zu holistischen Aggregationen werden. Insbesondere unterstützt DuckDB derzeit diese statistischen holistischen Aggregationen:

Wirklich interessant wird es, wenn wir gleitende Versionen dieser Aggregationen berechnen. Ein gleitendes AVG ist zum Beispiel recht einfach: Sie können Werte, die den Frame verlassen haben, abziehen und die neuen addieren oder den Segment-Tree-Ansatz aus dem vorherigen Beitrag zu Windowing nutzen.

Python-Beispiel

Ein gleitender Median ist nicht so einfach. Schauen wir uns ein einfaches Beispiel an, wie wir einen gleitenden median in Python für die folgenden String-Daten umsetzen könnten, mit einem Frame, der ein Element von jeder Seite einschließt:

Für dieses Beispiel nutzen wir Strings, damit wir uns nicht um Interpolation kümmern müssen.

data = ('a', 'b', 'c', 'd', 'c', 'b',)
w = len(data)
for row in range(w):
    l = max(row - 1, 0)       # First index of the frame
    r = min(row + 1, w-1)     # Last index of the frame
    frame = list(data[l:r+1]) # Copy the frame values
    frame.sort()              # Sort the frame values
    n = (r - l) // 2          # Middle index of the frame
    median = frame[n]         # The median is the middle value
    print(row, data[row], median)

Jeder Frame hat eine andere Menge zu aggregierender Werte, und wir können die Reihenfolge in der Tabelle nicht ändern, also müssen wir sie jedes Mal kopieren, bevor wir sortieren. Sortieren ist langsam, und es gibt viel Wiederholung.

Alle diese holistischen Aggregationen haben ähnliche Probleme, wenn wir die einfachen Implementierungen einfach für gleitende Versionen wiederverwenden. Glücklicherweise gibt es für alle deutlich schnellere Ansätze.

Gleitende holistische Aggregation

Im vorherigen Beitrag zu Windowing haben wir die Komponentenoperationen erklärt, mit denen eine generische Aggregatfunktion umgesetzt wird (initialize, update, finalize, combine und window). Im Rest dieses Beitrags schauen wir uns an, wie sie für diese komplexen Aggregationen umgesetzt werden können.

Quantile

Die quantile-Varianten extrahieren alle den Wert (oder die Werte) an einem gegebenen Bruchteil (oder Brüchen) durch die geordnete Liste der Werte in der Menge. Die einfachste Variante ist die Funktion median, die wir in der Einleitung kennengelernt haben, mit dem Bruchteil 0.5. Es gibt weitere Varianten, je nachdem, ob die Werte quantitativ sind (d. h. sie haben eine Distanz und die Werte können interpoliert werden) oder nur ordinal (d. h. sie können geordnet werden, Gleichstände müssen aber aufgelöst werden). Weitere Varianten hängen davon ab, ob der Bruchteil ein einzelner Wert oder eine Liste von Werten ist, sie können aber alle ähnlich umgesetzt werden.

Ein üblicher Weg, quantile umzusetzen, den wir im Python-Beispiel gesehen haben, ist, alle Werte im Zustand zu sammeln, sie zu sortieren und dann die Werte an den angeforderten Positionen auszulesen. (Deshalb spricht der SQL-Standard vermutlich von einer „Ordered-Set-Aggregation“.) Zustände können durch Konkatenation kombiniert werden, was paralleles Gruppieren und Segment Trees für Windowing erlaubt.

Dieser Ansatz ist sehr zeitaufwendig, weil Sortieren O(N log N) ist, glücklicherweise können wir für quantile einen verwandten Algorithmus namens QuickSelect nutzen, der einen positionalen Wert in nur O(N) Zeit findet, indem er das Array teilweise sortiert. Diesen Algorithmus kennen Sie vielleicht, wenn Sie jemals std::nth_element in der C++-Standardbibliothek genutzt haben. Das funktioniert gut für gruppierte Quantile, für gleitende Quantile ist der Segment-Tree-Ansatz jedoch etwa 5 % langsamer als jedes Mal von vorn zu beginnen.

Um die Leistung gleitender Quantile wirklich zu verbessern, stellen wir fest, dass sich die Teilordnung zwischen Frames wahrscheinlich kaum ändert. Wenn wir eine Liste indirekter Indizes in das Window halten und nth_element auf den Indizes aufrufen, können wir die teilweise geordneten Indizes neu ordnen statt der Werte selbst. Im häufigen Fall, dass der Frame dieselbe Größe hat, können wir sogar prüfen, ob der neue Wert die Teilordnung überhaupt stört, und das Neuordnen überspringen! Mit diesem Ansatz erreichen wir einen deutlichen Leistungsschub von 1,5- bis 10-fach.

In diesem Beispiel haben wir einen 3-Elemente-Frame (grün), der sich für jeden Wert um eine Stelle nach rechts bewegt:

Die Medianwerte in Orange müssen von Grund auf berechnet werden. Im Beispiel passiert das nur am Anfang des Windows. Die Medianwerte in Weiß werden mit der bestehenden Teilordnung berechnet. Im Beispiel passiert das, wenn sich die Frame-Größe ändert. Schließlich brauchen die Medianwerte in Blau kein Neuordnen, weil der neue Wert derselbe ist wie der alte. Mit diesem Algorithmus können wir eine schnellere Implementierung von Ein-Bruchteil-quantile ohne Sortieren erzeugen.

Interquartilsabstände (IQR)

Wir können diese Implementierung auf Listen von Brüchen erweitern, indem wir nutzen, dass jeder Aufruf von nth_element die Werte teilweise ordnet, was die Leistung weiter verbessert. Der „Wiederverwendungs“-Trick lässt sich verallgemeinern, um zwischen ungestörten Brüchen und solchen, die neu berechnet werden müssen, zu unterscheiden.

Eine häufige Anwendung mehrerer Brüche ist die Berechnung von Interquartilsabständen mit der Bruchliste [0.25, 0.5, 0.75]. Das ist die Bruchliste, die wir für die Mehrfach-Bruch-Benchmarks nutzen. Zusammen mit gleitendem MIN und MAX kann diese gleitende Aggregation die Daten für ein gleitendes Box-and-Whisker-Diagramm erzeugen.

Mediane absolute Abweichung (MAD)

Das Halten der Teilordnung kann auch die Leistung der Aggregation mediane absolute Abweichung (oder mad) steigern. Leider kann die zweite Teilordnung den Einzelwert-Trick nicht nutzen, weil sich die „Funktion“, mit der die Werte teilweise geordnet werden, ändert, wenn sich der Datenmedian ändert. Die Werte sind aber wahrscheinlich immer noch nicht weit daneben, was die Leistung von nth_element erneut verbessert.

Mode

Die Aggregation mode gibt den häufigsten Wert in einer Menge zurück. Ein üblicher Weg, sie umzusetzen, ist, alle Werte im Zustand zu sammeln, sie zu sortieren und dann nach dem längsten Lauf zu scannen. Diese Zustände können durch Mergen kombiniert werden, was uns erlaubt, den Mode parallel zu berechnen und Segment Trees für Windowing zu bauen.

Wieder ist dieser Ansatz sehr zeitaufwendig, weil Sortieren O(N log N) ist. Er kann auch mehr Speicher brauchen als nötig, weil er alle Werte hält statt nur der eindeutigen Werte. Gibt es Heavy Hitter in der Liste (typischerweise das, wonach mode sucht), kann das erheblich sein.

Ein anderer Weg, mode umzusetzen, ist eine Hash-Map als Zustand, die Werte auf Zähler abbildet. Hash-Tabellen sind typischerweise O(N) für die Akkumulation, eine Verbesserung gegenüber Sortieren, und sie müssen nur eindeutige Werte speichern. Wenn der Zustand auch den bisher größten gesehenen Wert und Zähler verfolgt, können wir beim Finalisieren der Aggregation einfach diesen Wert zurückgeben. Zustände können durch Mergen kombiniert werden, was paralleles Gruppieren und Segment Trees für Windowing erlaubt.

Leider ist dieser Segment-Tree-Ansatz für Windowing, wie die Benchmarks unten zeigen, recht langsam! Der Overhead des Mergens der Hash-Tabellen für die Segment Trees ist etwa 5 % langsamer als für jede Zeile im Window eine neue Hash-Tabelle zu bauen. Für eine gleitende mode-Berechnung können wir stattdessen eine einzelne Hash-Tabelle anlegen und sie jedes Mal aktualisieren, wenn sich der Frame bewegt, die alten Werte entfernen, die neuen addieren und das Werte-/Zähler-Paar aktualisieren. Manchmal kann der Zähler des aktuellen Mode-Werts verringert werden, dann können wir die Tabelle neu scannen, um den neuen Mode zu finden.

In diesem Beispiel bewegt sich der 4-Elemente-Frame (grün) für jeden Wert um eine Stelle nach rechts:

Wenn der Mode unverändert bleibt (blau), kann er direkt genutzt werden. Wenn der Mode mehrdeutig wird (orange), müssen wir die Tabelle neu scannen. Dieser Ansatz ist viel schneller und kommt in den Benchmarks zwischen 15- und 55-mal schneller als die anderen beiden.

Mikrobenchmarks

Um die verschiedenen Implementierungen zu benchmarken, führen wir gleitende Window-Abfragen gegen eine 10-Millionen-Tabelle von Integern aus:

CREATE TABLE rank100 AS
    SELECT b % 100 AS a, b FROM range(10000000) tbl(b);

Die Ergebnisse werden dann auf eine Zeile reaggregiert, um den Einfluss des Streamens der Ergebnisse zu entfernen. Die Frames sind 100 Elemente breit, und der Test wird mit einem festen nachlaufenden Frame wiederholt:

SELECT quantile_cont(a, [0.25, 0.5, 0.75]) OVER (
    ORDER BY b ASC
    ROWS BETWEEN 100 PRECEDING AND CURRENT ROW) AS iqr
FROM rank100;

und einem variablen Frame, der sich pseudozufällig um den aktuellen Wert bewegt:

SELECT quantile_cont(a, [0.25, 0.5, 0.75]) OVER (
    ORDER BY b ASC
    ROWS BETWEEN mod(b * 47, 521) PRECEDING AND 100 - mod(b * 47, 521) FOLLOWING) AS iqr
FROM rank100;

Die beiden Beispiele hier sind die Interquartilsabstands-Abfragen; die anderen Abfragen nutzen die Ein-Argument-Aggregationen median, mad und mode.

Als letzten Schritt haben wir dieselbe Abfrage mit count(*) ausgeführt, die denselben Overhead wie die anderen Benchmarks hat, aber trivial zu berechnen ist (sie gibt nur die Frame-Größe zurück). Dieser Overhead wurde von den Laufzeiten abgezogen, um die Algorithmuszeiten zu ergeben:

Wie man sieht, gibt es einen erheblichen Nutzen davon, die Window-Operation für all diese Aggregationen umzusetzen, oft in der Größenordnung eines Faktors zehn.

Ein unerwartetes Ergebnis war, dass der Segment-Tree-Ansatz für diese komplexen Zustände immer langsamer ist (um etwa 5 %) als den Zustand für jede Ausgabezeile einfach neu zu erzeugen. Das legt nahe: Beim Schreiben kombinierbarer komplexer Aggregationen lohnt es sich, die Aggregation zu benchmarken und dann eine Window-Operation bereitzustellen, statt sich auf die Segment-Tree-Maschinerie zu verlassen.

Fazit

DuckDBs Aggregate-API ermöglicht Aggregatfunktionen, eine Windowing-Operation zu definieren, die die Leistung gleitender Window-Berechnungen für komplexe Aggregationen deutlich verbessern kann. Diese Funktionalität wurde genutzt, um Windowing für mehrere statistische Aggregationen wie Mode, Interquartilsabstände und mediane absolute Abweichung deutlich zu beschleunigen.

DuckDB ist ein freies und quelloffenes Datenbankmanagementsystem (MIT-Lizenz). Es will das SQLite für Analysen sein und bietet ein schnelles, effizientes Datenbanksystem ohne externe Abhängigkeiten. Es ist nicht nur für Python verfügbar, sondern auch für C/C++, R, Java und mehr.