2024-08-08

Freundliche Listen und ihre Kumpel, die Lambdas

Tania Bogatsch, Maia de Graaf

Einleitung

Geschachtelte Datentypen wie Listen und Structs sind in der Analytik weit verbreitet. Mehrere beliebte Formate, darunter Parquet und JSON, unterstützen geschachtelte Typen. Traditionell erfordert die Arbeit mit geschachtelten Typen Normalisierungsschritte vor jeder Analyse. Um dann geschachtelte Ergebnisse zurückzugeben, müssen Systeme ihre Daten (wieder) aggregieren. Normalisierung und Aggregation sind sowohl aus Nutzungs- als auch aus Performance-Sicht unerwünscht. Um die Arbeit mit geschachtelten Daten zu vereinfachen, bieten analytische Systeme, einschließlich DuckDB, native Funktionalität auf diesen geschachtelten Typen.

In diesem Blogpost behandeln wir zuerst die Grundlagen von Listen und Lambdas. Dann tauchen wir in ihre technischen Details ein. Schließlich zeigen wir einige Beispiele aus der Community. Springen Sie gerne voraus, wenn Sie Listen und Lambdas schon kennen und nur wegen unserer fertigen Beispiele hier sind!

Listen

Bevor wir zu Lambdas springen, ein kurzer Umweg über DuckDBs LIST-Typ. Eine Liste enthält beliebig viele Elemente desselben Datentyps. Unten ist eine Tabelle mit zwei Spalten, l und n. l enthält Listen von Ganzzahlen, n enthält Ganzzahlen.

CREATE OR REPLACE TABLE my_lists (l INTEGER[], n INTEGER);
INSERT INTO my_lists VALUES ([1], 1), ([1, 2, 3], 2), ([-1, NULL, 2], 2);
FROM my_lists;

┌───────────────┬───────┐
│       l       │   n   │
│    int32[]    │ int32 │
├───────────────┼───────┤
│ [1]           │     1 │
│ [1, 2, 3]     │     2 │
│ [-1, NULL, 2] │     2 │
└───────────────┴───────┘

Intern bewegen sich alle Daten durch DuckDBs Ausführungsengine in Vectors. Mehr Details zu Vectors und vektorisierter Ausführung finden Sie in der Dokumentation und den jeweiligen Forschungsarbeiten (1 und 2). In diesem Fall erhalten wir zwei Vektoren, wie unten dargestellt. Diese Darstellung ist weitgehend ähnlich zu Arrows physischer Listendarstellung.

Bei genauerem Hinsehen fällt auf, dass der geschachtelte Child-Vektor von l verdächtig ähnlich zum Vektor n aussieht. Diese geschachtelten Vektordarstellungen erlauben es unserer Ausführungsengine, bestehende Komponenten auf geschachtelten Typen wiederzuverwenden. Warum das relevant ist, erläutern wir später.

Lambdas

Eine Lambda-Funktion ist eine anonyme Funktion, also eine Funktion ohne Namen. In DuckDB lautet die Syntax einer Lambda-Funktion lambda param1, param2, ...: expression. Die Parameter können beliebige Namen haben, und expression kann jeder SQL-Ausdruck sein.

Derzeit hat DuckDB drei Skalarfunktionen für die Arbeit mit Lambdas: list_transform, list_filter und list_reduce sowie ihre Aliase. Jede nimmt eine LIST als erstes Argument und eine Lambda-Funktion als zweites.

Lambdas waren der Gaststar in unserem Blogpost SQL Gymnastics: SQL in flexible neue Formen biegen. Diesmal wollen wir sie ins Rampenlicht stellen.

Heranzoomen: Listentransformationen

Zurück zu unserem vorherigen Beispiel: Wir wollen n zu jedem Element der zugehörigen Liste l addieren.

Rein relationale Lösung

Mit rein relationalen Operatoren, also ohne listen-native Funktionen, müssten wir folgende Schritte ausführen:

Die Listen entpacken und dabei die Verbindung zu ihren jeweiligen Zeilen halten. Das erreichen wir, indem wir einen temporären eindeutigen Identifikator erfinden, etwa eine rowid oder eine UUID.
Jedes Element transformieren, indem wir n addieren.
Mit unserem temporären Identifikator rowid können wir die transformierten Elemente wieder aggregieren, indem wir sie in Listen gruppieren.

In SQL sähe das so aus:

WITH flattened_tbl AS (
    SELECT unnest(l) AS elements, n, rowid
    FROM my_lists
)
SELECT array_agg(elements + n) AS result
FROM flattened_tbl
GROUP BY rowid
ORDER BY rowid;

┌──────────────┐
│    result    │
│   int32[]    │
├──────────────┤
│ [2]          │
│ [3, 4, 5]    │
│ [1, NULL, 4] │
└──────────────┘

Das obige Beispiel ist noch einigermaßen lesbar, komplexere Transformationen können aber zu langen Abfragen werden, die schwer zu komponieren und zu warten sind. Wichtiger: Diese Abfrage fügt eine unnest-Operation und eine Aggregation (array_agg) mit GROUP BY hinzu. Ein GROUP BY kann teuer sein, besonders bei großen Datensätzen.

Um vollständig zu verstehen, warum die obige Abfrage suboptimale Performance liefert, müssen wir in die technischen Implikationen eintauchen. Intern führt die Abfrageausführung die im Diagramm unten dargestellten Schritte aus. Für die unnest-Operation können wir den Child-Vektor direkt emittieren, also ohne Daten zu kopieren. Für die korrelierten Spalten rowid und n nutzen wir Selection Vectors, die wiederum das Kopieren von Daten vermeiden. So können wir unsere Ausdrucksausführung auf den Child-Vektor, einen weiteren geschachtelten Vektor und den expandierten Vektor n feuern.

Die schwerwiegende Operation ist die letzte: das Wiederaggregieren der transformierten Elemente in ihre jeweiligen Listen. Da wir den Parent-Vektor nicht weiterreichen, haben wir keine Information über die Korrelation der resultierenden Elemente zu den ursprünglichen Listen. Das Neuerzeugen dieser Listen erfordert eine vollständige Kopie der Daten und Partitionierung, was selbst mit DuckDBs hochperformantem Aggregationsoperator die Performance trifft.

Die normalisierte Herangehensweise ist also sowohl umständlich zu schreiben als auch ineffizient, weil sie trotz der relativen Einfachheit der Abfrage erheblichen (und unnötigen) Overhead erzeugt. Das ist wieder ein Beispiel dafür, wie das Formen geschachtelter Daten in relationale Formen oder das Zwingen durch Rechtecke einen erheblichen negativen Performance-Effekt haben kann.

Native Listenfunktionen

Mit Unterstützung für native Listenfunktionen mildert DuckDB diese Nachteile, indem es direkt auf der LIST-Datenstruktur arbeitet. Da Listen, wie wir gesehen haben, im Wesentlichen geschachtelte Spalten sind, können wir diese Funktionen in Konzepte umformen, die unsere Ausführungsengine bereits versteht, und ihr volles Potenzial nutzen.

Bei Transformationen ist die entsprechende listen-native Funktion list_transform. Hier die umgeschriebene Abfrage:

SELECT list_transform(l, lambda x: x + n) AS result
FROM my_lists;

Alternativ mit Pythons List-Comprehension-Syntax:

SELECT [x + n FOR x IN l] AS result
FROM my_lists;

Intern expandiert diese Abfrage alle verwandten Vektoren, in diesem Fall nur n. Wie zuvor nutzen wir Selection Vectors, um Datenkopien zu vermeiden. Dann nutzen wir die Lambda-Funktion x: x + n, um unsere Ausdrucksausführung auf den Child-Vektor und den expandierten Vektor n zu feuern. Da dies eine listen-native Funktion ist, kennen wir die Existenz eines Parent-Vektors und halten ihn am Leben. Sobald wir das Ergebnis der Transformation haben, können wir den Wiederaggregationsschritt komplett weglassen.

Um die Effizienz von list_transform in Aktion zu sehen, haben wir einen einfachen Benchmark ausgeführt. Zuerst haben wir 1 Million Zeilen zu unserer Tabelle my_lists hinzugefügt, jede mit fünf Elementen.

INSERT INTO my_lists
    SELECT [r, r % 10, r + 5, r + 11, r % 2], r
    FROM range(1_000_000) AS tbl(r);

Dann haben wir sowohl die normalisierte als auch die listen-native Abfrage auf diesen Daten ausgeführt. Beide Abfragen liefen in der CLI mit DuckDB v1.0.0 auf einem MacBook Pro 2021 mit M1-Max-Chip.

Normalisiert	Nativ
0.522 s	0.027 s

Wie wir sehen, ist die native Abfrage mehr als 10× schneller. Fantastisch! Schauen wir uns den Ausführungsplan mit EXPLAIN ANALYZE an (in diesem Blogpost nicht gezeigt), sehen wir, dass DuckDB die meiste Zeit in den Operatoren HASH_GROUP_BY und UNNEST verbringt. Diese Operatoren gibt es im listen-nativen Query-Plan nicht mehr.

Listen und Lambdas in der Community

Um besser zu zeigen, was die Kombination aus unserem LIST-Typ und Lambda-Funktionen ermöglicht, haben wir den Community-Discord und GitHub sowie einige entlegene Winkel des Internets nach spannenden Einsatzfällen durchsucht.

`list_transform`

Wie zuvor festgestellt, wendet list_transform eine Lambda-Funktion auf jedes Element der Eingabeliste an und gibt eine neue Liste mit den transformierten Elementen zurück. Hier hat einer unserer Nutzer eine Funktion list_shuffle implementiert, indem er verschiedene LIST-native Funktionen verschachtelt.

CREATE OR REPLACE MACRO list_shuffle(l) AS (
    list_select(l, list_grade_up([random() FOR _ IN l]))
);

Ein anderer Nutzer hat das Abfragen entfernter Parquet-Dateien mit DuckDB untersucht. In seiner Abfrage nutzt er zuerst list_transform, um eine Liste von URLs für Parquet-Dateien zu erzeugen. Danach folgt die Funktion read_parquet, die die Parquet-Dateien liest und die Gesamtgröße der Daten berechnet. Die Abfrage sieht so aus:

SELECT
    sum(size) AS size
FROM read_parquet(
    ['https://huggingface.co/datasets/vivym/midjourney-messages/resolve/main/data/' ||
        format('{:06d}', n) || '.parquet'
        FOR n IN generate_series(0, 55)
    ]
);

`list_filter`

Die Funktion list_filter filtert alle Elemente der Eingabeliste, für die die Lambda-Funktion true zurückgibt.

Hier ein Beispiel mit list_filter aus einer Diskussion auf unserem Discord, in der der Nutzer das Element am Index idx aus jeder Liste entfernen wollte.

CREATE OR REPLACE MACRO remove_idx(l, idx) AS (
    list_filter(l, lambda _, i: i != idx)
);

Bisher haben wir uns in diesem Blogpost vor allem auf unsere Lambda-Funktionsunterstützung konzentriert. Doch mit SQL und seinen reichen Dialekten gibt es oft viele mögliche Wege. Wir konnten nicht widerstehen zu zeigen, wie wir dieselbe Funktionalität mit einigen unserer anderen nativen Listenfunktionen erreichen. In diesem Fall haben wir list_slice und list_concat genutzt.

CREATE OR REPLACE MACRO remove_idx(l, idx) AS (
    l[:idx - 1] || l[idx + 1:]
);

`list_reduce`

Zuletzt haben wir list_reduce hinzugefügt, das eine Lambda-Funktion auf einen Akkumulatorwert anwendet. Der Akkumulator ist das Ergebnis der vorherigen Lambda-Funktion und auch das, was die Funktion am Ende zurückgibt.

Das folgende Beispiel stammt aus einer Diskussion auf GitHub. Der Nutzer wollte ein Lambda nutzen, um BSN-Nummern zu prüfen, das niederländische Äquivalent zur Sozialversicherungsnummer. Eine BSN muss 8 oder 9 Ziffern haben; um den Rahmen zu halten, konzentrieren wir uns nur auf BSNs mit 9 Ziffern. Nach dem Multiplizieren jeder Ziffer mit ihrem Index von 9 bis 2 und der letzten Ziffer mit -1 muss die Summe durch 11 teilbar sein, um gültig zu sein.

Setup

Für unser Beispiel nehmen wir an, dass Eingabe-BSNs vom Typ INTEGER[] sind.

CREATE OR REPLACE TABLE bsn_tbl AS
    FROM VALUES
        ([2, 4, 6, 7, 4, 7, 5, 9, 6]),
        ([1, 2, 3, 4, 5, 6, 7, 8, 9]),
        ([7, 6, 7, 4, 4, 5, 2, 1, 1]),
        ([8, 7, 9, 0, 2, 3, 4, 1, 7]),
        ([1, 2, 3, 4, 5, 6, 7, 8, 9, 0])
        tbl(bsn);

Lösung

CREATE OR REPLACE MACRO valid_bsn(bsn) AS (
    bsn.list_reverse().list_reduce(
        lambda x, y, i: IF (i = 2, -x, x) + y * i
    ) % 11 = 0
    AND len(bsn) = 9
);

Mit unserem Macro und der Beispieltabelle erhalten wir folgendes Ergebnis:

SELECT bsn, valid_bsn(bsn) AS valid
FROM bsn_tbl;

┌────────────────────────────────┬─────────┐
│              bsn               │  valid  │
│            int32[]             │ boolean │
├────────────────────────────────┼─────────┤
│ [2, 4, 6, 7, 4, 7, 5, 9, 6]    │ true    │
│ [1, 2, 3, 4, 5, 6, 7, 8, 9]    │ false   │
│ [7, 6, 7, 4, 4, 5, 2, 1, 1]    │ true    │
│ [8, 7, 9, 0, 2, 3, 4, 1, 7]    │ true    │
│ [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] │ false   │
└────────────────────────────────┴─────────┘

Fazit

Native Unterstützung geschachtelter Typen ist für analytische Systeme entscheidend. Deshalb bietet DuckDB native Unterstützung geschachtelter Typen und viele Funktionen, um direkt mit diesen Typen zu arbeiten. Diese Funktionen machen die Arbeit mit geschachtelten Typen einfacher und wesentlich schneller. In diesem Blogpost haben wir uns die technischen Details der Arbeit mit geschachtelten Typen angesehen, indem wir in unsere Funktion list_transform eingetaucht sind. Zusätzlich haben wir verschiedene Einsatzfälle hervorgehoben, die uns in der Community begegnet sind.