2025-02-10

Aufholen beim Windowing

Richard Wesley

Hintergrund

Am Anfang ging es im relationalen Datenverarbeitungsmodell um Mengen. Das war Codds große Einsicht, und viele Jahre nahm die relationale Verarbeitung kaum Notiz von Datenordnung.

Es gibt aber viele analytische Operationen, die mit Ordnung zusammenhängen. Zum Beispiel ist das Glätten von Rauschen in Zeitreihen in klassischen SQL-Queries sehr schwierig – es braucht Self-Joins mit Ungleichheitsbedingungen! Ende der 1990er begannen Datenbankanbieter deshalb, Windowing-Operationen zu ergänzen. Indem die Absicht der Nutzer klar wurde, ließen sich die Operationen viel effizienter implementieren, und sie wurden schließlich in den SQL:2003-Standard aufgenommen.

DuckDB unterstützt Window-Funktionen seit den frühen Tagen. Wenn sie neu für Sie sind, beginnen Sie am besten mit meinen früheren Blogbeiträgen zu Windowing in DuckDB und Fast Moving Holistic Aggregates oder einfach der Dokumentation zu Window-Funktionen. In diesem Beitrag stelle ich zuerst die neueren Funktionsergänzungen vor. In einem Folgebeitrag tauche ich in die Internals ein und spreche über Performance- und Skalierungsverbesserungen.

Für die Beispiele bleibe ich meist bei einer Tabelle sportlicher results:

Feld	Typ	Beschreibung
`event`	`VARCHAR`	Name der Disziplin (z. B. 200-Meter-Schmetterling).
`athlete`	`VARCHAR`	Name der Wettkämpferin bzw. des Wettkämpfers (z. B. Michael Phelps).
`date`	`TIMESTAMP`	Startzeit der Disziplin.
`time`	`DECIMAL(18, 3)`	Die Zeit der Athletin bzw. des Athleten in dieser Disziplin (in Sekunden).

`GROUPS`-Framing

Zusätzlich zu den Frame-Grenztypen ROWS und RANGE (die wir schon länger unterstützen) definiert der Standard auch GROUPS als Grenztyp. ROWS ist einfach: Es zählt die Zahl der Zeilen. RANGE ist kniffliger: Es behandelt seine Zähler als Distanzen vom Wert des ORDER BY-Ausdrucks der aktuellen Zeile. Deshalb darf es nur einen solchen Ausdruck geben, und man muss damit rechnen können.

GROUPS liegt dazwischen. Eine „Gruppe“ in der Sprache des Standards sind alle „Peers“ einer Zeile, also alle Zeilen mit demselben Wert des ORDER BY-Ausdrucks der aktuellen Zeile. Im ursprünglichen Windowing-Code war das nicht leicht zu implementieren, aber nach mehreren Jahren Arbeit hat sich die Infrastruktur weiterentwickelt, und ab v1.2.0 unterstützen wir diesen letzten Framing-Typ.

Frame Exclusion

Ein weiteres fehlendes Stück der Spezifikation von 2003 war die Klausel EXCLUDE. Dank der Arbeit eines Community-Mitglieds unterstützen wir das seit v0.10.0, haben es aber irgendwie nie in einem Blogbeitrag erwähnt!

EXCLUDE ist ein optionaler Modifikator der Frame-Klausel, um Zeilen um die CURRENT ROW auszuschließen. Das ist nützlich, wenn Sie einen Aggregatwert nahegelegener Zeilen berechnen und die aktuelle Zeile damit vergleichen wollen. In diesem Beispiel wollen wir wissen, wie die Zeit einer Athletin bzw. eines Athleten in einer Disziplin mit dem Durchschnitt aller für diese Disziplin innerhalb von ±10 Tagen erfassten Zeiten vergleichbar ist:

SELECT
    event,
    date,
    athlete,
    avg(time) OVER w AS recent,
FROM results
WINDOW w AS (
    PARTITION BY event
    ORDER BY date
    RANGE BETWEEN INTERVAL 10 DAYS PRECEDING AND INTERVAL 10 DAYS FOLLOWING
        EXCLUDE CURRENT ROW
)
ORDER BY event, date, athlete;

Es gibt vier Optionen für EXCLUDE, die festlegen, wie die aktuelle Zeile behandelt wird:

CURRENT ROW – nur die aktuelle Zeile ausschließen
GROUP – die aktuelle Zeile und alle ihre „Peers“ ausschließen (Zeilen mit demselben ORDER BY-Wert)
TIES – alle Peer-Zeilen ausschließen, aber nicht die aktuelle Zeile (das macht ein Loch auf beiden Seiten)
NO OTHERS – nichts ausschließen (der Standard)

Exclusion ist sowohl für Window-Aggregate als auch für die Funktionen first, last und nth_value implementiert.

Klausel `QUALIFY`

Es ist vielleicht nicht sofort offensichtlich, aber die SQL-Sprache hat Regeln für die Reihenfolge, in der verschiedene Ausdrücke berechnet werden. Aggregate (wie sum) werden zum Beispiel nach zeilenweisen Ausdrücken (wie +) berechnet. Deshalb hat SQL zwei Filterklauseln: WHERE und HAVING: WHERE gilt für zeilenweise Berechnungen, HAVING wird nach GROUP BY angewendet.

Als Windowing eingeführt wurde, kam eine weitere Berechnungsschicht hinzu: Window-Funktionen werden nach Aggregaten berechnet. Das ist großartig – aber wie filtert man die Ergebnisse einer OVER-Funktion? Ursprünglich musste man die Query in einen Common Table Expression (oder CTE) packen, der durch eine WITH-Klausel definiert wird:

-- Find the third fastest times in each event
WITH windowed AS (
    SELECT
        event,
        athlete,
        time,
        row_number() OVER w AS r
    FROM results
    WINDOW w AS (
        PARTITION BY event
        ORDER BY time
    )
)
SELECT event, athlete, time
FROM windowed
WHERE r = 3;

Das war etwas klobig, deshalb wurde irgendwann die Klausel QUALIFY zum Filtern von Window-Funktionen vorgeschlagen. DuckDB unterstützt das und macht es leichter, die Ergebnisse von Window-Funktionen zu filtern:

-- Find the third fastest times in each event
SELECT event, athlete, time
FROM results
WINDOW w AS (
    PARTITION BY event
    ORDER BY time
)
QUALIFY row_number() OVER w = 3;

Aggregate-Modifikatoren

Es gibt mehrere Modifikatoren für gewöhnliche Aggregatfunktionen (FILTER, DISTINCT und ORDER BY als Argument), die nicht Teil des SQL:2003-Standards für Windowing sind, aber auch im Windowing-Kontext nützlich sind. FILTER ist ziemlich geradlinig (und DuckDB unterstützt es schon länger), die anderen sind nicht leicht effizient zu implementieren.

Natürlich lassen sie sich naiv implementieren (Akademikersprache für „langsam“!), indem jede Zeile unabhängig berechnet wird:

alle Werte neu lesen,
die unerwünschten herausfiltern,
sie in eine Hashtabelle stecken, um Duplikate zu entfernen,
die Ergebnisse sortieren,
sie an die Aggregatfunktion schicken, um das Ergebnis zu bekommen.

Wir haben eine Implementierung, die das tut (erreichbar, wenn man den Optimizer abschaltet), und wir nutzen sie, um schickere Implementierungen zu prüfen – sie ist aber furchtbar langsam.

Glücklicherweise waren diese letzten beiden Modifikatoren Gegenstand von Forschung, die in den letzten 10 Jahren veröffentlicht wurde, und wir haben diese Algorithmen jetzt zu den Windowing-Aggregaten hinzugefügt. Den Modifikator DISTINCT können wir dann nutzen, um Duplikate im Frame auszuschließen:

-- Count the number of distinct athletes at a given point in time
SELECT count(DISTINCT athlete) OVER (ORDER BY date) FROM results;
-- Concatenate those distinct athletes into a list
SELECT list(DISTINCT athlete) OVER (ORDER BY date) FROM results;

Den Modifikator ORDER BY können wir auch mit ordnungssensitiven Aggregaten nutzen, um sortierte Ergebnisse zu bekommen:

-- Return an alphabetized list of athletes who made or beat a time
SELECT list(athlete ORDER BY athlete) OVER (
    PARTITION BY event, date
    ORDER BY time DESC
)
FROM results;

Ich sollte erwähnen, dass die Forschung zu diesen Erweiterungen andauert und ihre Kombination uns oft zur naiven Implementierung zwingt. Wollten wir zum Beispiel die Athletin bzw. den Athleten ausschließen, die bzw. der die Zeit gelaufen ist:

-- Return an alphabetized list athletes who beat the each time
SELECT list(athlete ORDER BY athlete) OVER (
    PARTITION BY event, date
    ORDER BY time DESC
    EXCLUDE CURRENT ROW
)
FROM results;

DuckDB berechnet das trotzdem für Sie, es kann aber sehr langsam sein.

Funktionsmodifikatoren

Der Modifikator ORDER BY ergibt auch für einige nicht-aggregierende Window-Funktionen Sinn, besonders wenn wir sie damit mit Framing nutzen lassen:

-- Compute the current world record holder over time for each event
SELECT
    event,
    date,
    first_value(time ORDER BY time DESC) OVER w AS record_time,
    first_value(athlete ORDER BY time DESC) OVER w AS record_holder,
FROM results
WINDOW w AS (
    PARTITION BY event
    ORDER BY date
    ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
)
ORDER BY event, date;

Alle nicht-aggregierenden Window-Funktionen (außer dense_rank) unterstützen jetzt Order-Argumente und nutzen den Frame statt der gesamten Partition, wenn ein Order-Argument angegeben ist.

Tipp: Wollen Sie den gesamten Frame mit einem Order-Argument nutzen, müssen Sie explizit RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING verwenden.

Hinweis: Wollen Sie die Frame-Ordnung und die Frame-Grenzen mit einer nicht-aggregierenden Funktion nutzen, müssen Sie ORDER BY zweimal angeben (einmal in der Frame-Spezifikation und einmal in der Argumentliste). Das ist noch nicht optimiert, wird es aber im Release v1.3.0.

Fazit

Windowing ist ein sehr natürlicher Weg, über ordnungsabhängige Analyse nachzudenken, steht aber im Widerspruch zur klassischen ungeordneten Query-Verarbeitung. Trotzdem bietet die SQL-Sprache seit 2003 Syntax, um eine große Bandbreite solcher Queries auszudrücken. In den letzten Jahren hat die Community weitere Spracherweiterungen erwogen (etwa QUALIFY und Argumentmodifikatoren wie DISTINCT und ORDER BY), um die Ausdruckskraft zu verbessern. Hier bei DuckDB lieben wir es, diese Art von Ausdruckskraft als Teil unserer Arbeit an „Friendly SQL“ bereitzustellen. Weniger offensichtlich ist vielleicht: Wenn wir Nutzerinnen und Nutzern erlauben, ihr Problem natürlicher auszudrücken, hilft uns das, performantere Lösungen zu liefern! Im nächsten Beitrag gehe ich tiefer in die jüngsten Verbesserungen bei Performance und Ressourcennutzung des Windowings.