Deutsch
Support

2025-02-19

AsOf-Joins planen

Richard Wesley

„I love it when a plan comes together.“
— Hannibal Smith, The A-Team

Einleitung

AsOf-Joins sind eine sehr nützliche Art von Operation für temporale Analytik. Wie der Name sagt, sind sie eine Art Lookup, wenn Sie eine Tabelle von Werten haben, die sich über die Zeit ändern, und den neuesten Wert zu einem anderen Satz von Zeitpunkten nachschlagen wollen. Anders gesagt erlauben sie die Frage „Was war der Wert der Eigenschaft zu diesem Zeitpunkt?“

DuckDB hat vor etwa 18 Monaten AsOf-Joins ergänzt, und in diesem Beitrag können Sie ihre Semantik nachlesen.

Was ist der Plan?

In jenem früheren Beitrag habe ich erklärt, warum wir einen eigenen Operator und eine eigene Syntax für AsOf-Joins haben, obwohl man sie in klassischem SQL implementieren kann. Die Superkraft von SQL ist, dass es deklarativ ist: Sie sagen uns was Sie wollen, und wir finden ein effizientes wie heraus. Indem Sie sagen können, dass Sie einen AsOf-Join wollen, können wir darüber nachdenken, wie Sie schneller zu Ergebnissen kommen!

Trotzdem muss der AsOf-Operator viel Arbeit tun. Nämlich:

Das ist viel Datenbewegung! Außerdem können wir, wenn eine der Tabellen groß ist, den Speicher überschreiten und auf Platte spulen, was die Operation noch weiter verlangsamt. Trotzdem ist sie, wie wir sehen werden, deutlich schneller als die reine SQL-Implementierung.

Das ist so eine Last, dass viele Datenbanken, die AsOf-Joins unterstützen, verlangen, dass die rechte Tabelle nach allen Keys, nach denen Sie joinen könnten, partitioniert und geordnet ist. Das passt nicht gut zu DuckDBs „Friendly SQL“-Ansatz, deshalb müssen wir das (vorerst) jedes Mal tun.

Klein halten

Es gibt einen sehr häufigen Fall für AsOf, bei dem die linke Tabelle klein ist. Angenommen, Sie haben ein Jahr Preisdaten, in hoher Granularität aufgezeichnet (z. B. Sekundenbruchteile), wollen aber nur eine kleine Zahl (sagen wir 20) Werte nachschlagen, die die Zeiten sind, zu denen Sie tatsächlich gekauft oder verkauft haben?

Die Preistabelle könnte auf Hunderte von Millionen, wenn nicht Milliarden Zeilen hinauslaufen, und allein das Sortieren braucht viel Zeit und Speicher. Angesichts dessen, wie teuer das ist, könnte man sich fragen, ob es einen Weg gibt, all dieses Sortieren zu vermeiden? Glücklicherweise lautet die Antwort ja!

Einfache Joins

Angenommen, wir tauschen die Seiten des Joins, bauen die alte linke Seite als kleine rechte Tabelle und streamen die riesige Tabelle durch die linke Seite des Joins. Wir könnten die AsOf-Bedingungen für den Join nutzen und hoffentlich einen Weg finden, die älteren Matches zu verwerfen (wir wollen nur das neueste Match behalten). Das würde sehr wenig Speicher nutzen, und das Streaming könnte stark parallelisiert werden.

Es gibt zwei streaming physische Join-Operatoren, die wir dafür nutzen könnten:

Wir können beide ausprobieren, sobald wir einen Weg haben, die Duplikate zu eliminieren. Eine Sache, die man im Blick behalten sollte: Beide sind N^2-Algorithmen, es gibt also eine Grenze, wie groß „klein“ sein kann.

Gruppierung

Wenn Sie lange genug um Datenbanken herum sind, wissen Sie, dass die Phrase „die Duplikate eliminieren“ GROUP BY bedeutet! Um die Duplikate zu eliminieren, wollen wir also einen Aggregationsoperator an die Ausgabe hängen. Der knifflige Teil: Wir wollen nur die gematchten Werte behalten, die die „größten“ Zeiten haben. Glücklicherweise hat DuckDB ein Paar Aggregatfunktionen, die genau das tun: arg_max und arg_min (auch max_by und min_by genannt).

Das kümmert sich um die Felder aus der Lookup-Tabelle, aber was ist mit den Feldern aus der kleinen Tabelle? Nun, diese Werte sind alle gleich, wir können also einfach die Aggregatfunktion first für sie nutzen.

Streaming Window

Aber wonach sollen wir gruppieren? Man könnte versucht sein, nach den nachgeschlagenen Zeiten zu gruppieren, das könnte aber problematisch sein, wenn es doppelte Lookup-Zeiten gibt (nur eine der Zeilen würde zurückgegeben!). Stattdessen brauchen wir einen eindeutigen Identifikator für jede nachgeschlagene Zeile. Der einfachste Weg ist, den Streaming-Window-Operator mit der Window-Funktion row_number() zu nutzen. Dann gruppieren wir nach dieser Zeilennummer.

Zusammenkommen

Das klingt alles gut, aber wie funktioniert es in der Praxis? Wie groß kann „klein“ werden? Um das zu beantworten, habe ich eine Reihe von Benchmarks ausgeführt, die kleine Tabellen gegen große joinen. Die Tabellen heißen prices und times:

CREATE OR REPLACE TABLE prices_{prices_size} AS
    SELECT
        r AS id,
        '2021-01-01T00:00:00'::TIMESTAMP +
            INTERVAL (random() * 365 * 24 * 60 * 60) SECOND
            AS time,
        (random() * 100000)::INTEGER AS price,
    FROM range({prices_size}) tbl(r);


CREATE OR REPLACE TABLE times_{times_size} AS
    SELECT
        r AS id,
        '2021-01-01'::TIMESTAMP +
            INTERVAL ((random() * 365 * 24 * 60 * 60)::INTEGER) SECONDS
            AS probe
    FROM range({times_size}) tbl(r);

Dann habe ich eine Benchmark-Query ausgeführt:

SELECT count(*)
FROM (
    SELECT
        t.probe,
        p.price
    FROM times_{times_size} t
        ASOF JOIN prices_{prices_size} p
        ON t.probe >= p.time
    ) t;

für eine Matrix der folgenden Werte:

Hier die Ergebnisse:

AsOf Plan Matrix

Wie Sie sehen, heißt die quadratische Natur der Joins, dass „klein“ „<= 64“ bedeutet. Das ist ziemlich klein, aber die Tabelle im ursprünglichen User-Issue hatte nur 21 Werte.

Wir sehen auch, dass die Sortierung durch den Piecewise Merge Join nicht viel zu helfen scheint, deshalb ist der schlichte Nested Loop Join die beste Wahl.

Es ist klar, dass die Performance des Standardoperators bei jeder Größe stabil ist, aber langsam sinkt, wenn die Zahl der Threads steigt. Das ergibt Sinn, weil Sortieren rechenintensiv ist und je weniger Kerne wir zuweisen können, desto länger dauert es.

Wenn Sie mehr mit den Daten spielen wollen, finden Sie die interaktive Visualisierung auf unserer Tableau-Public-Seite.

Speicher

Der Loop-Join-Plan ist bei kleinen Größen klar schneller, aber wie viel Speicher nutzen die beiden Pläne? Das sind die groben Speichermengen, die nötig sind, bevor übermäßiges Paging oder Allokationsfehler auftreten:

Price-Zeilen AsOf-Speicher Loop-Join-Speicher
1B 48 GB 64 MB
100M 6 GB 64 MB
10M 256 MB 64 MB
1M 32 MB 64 MB
100K 32 MB 64 MB

Anders gesagt braucht der Loop-Join-Plan nur genug Speicher, um die Lookup-Tabelle einzupagen! Ist die Tabelle also groß und Sie haben begrenzten Speicher, ist der Loop-Join-Plan die beste Option, selbst wenn er schmerzhaft langsam ist. Denken Sie nur daran, dass der Loop-Join-Plan mit der Geschwindigkeit des Standardoperators unter Paging konkurrieren muss, und der kann ab einem bestimmten Punkt immer noch schneller sein.

Backup-Pläne

Als Teil des Experiments habe ich auch gemessen, wie die alte SQL-Implementierung performen würde, und sie hat nicht gut abgeschnitten. Auf der 1B-Zeilen-Stufe musste ich sie nach einem Lauf abschneiden, um keine Zeit zu verschwenden:

AsOf SQL Implementation

Hinweis: Die Y-Achse ist hier eine Log-Skala!

Einstellung

Es ist schön, dass wir einen Default-Wert für solche Planentscheidungen liefern, Ihre Ergebnisse können aber, wie man so sagt, abweichen. Haben Sie mehr Zeit als Speicher, könnte es sich für Sie lohnen, die Loop-Join-Schwelle etwas anzuheben. Die Schwelle ist eine neue Einstellung namens asof_loop_join_threshold mit einem Default-Wert von 64, und Sie können sie mit einem PRAGMA-Statement ändern:

PRAGMA asof_loop_join_threshold = 128;

Denken Sie aber daran: Das ist eine quadratische Operation, und sie zu hoch zu setzen, könnte eine Sehr Lange Zeit dauern (besonders wenn Sie sie in Altem Entisch ausdrücken!).

Wenn Sie das Feature deaktivieren möchten, können Sie es einfach auf null setzen:

PRAGMA asof_loop_join_threshold = 0;

Selbst gebaut

Diese Loop-Join-Plan-Optimierung kommt erst in v1.3, aber wenn Sie heute Probleme haben, können Sie immer Ihre eigene Version so schreiben:

SELECT
    first(t.probe) AS probe,
    arg_max(p.price, p.time) AS price
FROM prices p
INNER JOIN (
    SELECT
        *,
        row_number() OVER () AS pk
    FROM times
) t
ON t.probe >= p.time
GROUP BY pk
ORDER BY 1;

Wenn Sie wissen, dass die Probe-Zeiten eindeutig sind, können Sie das vereinfachen zu:

SELECT
    t.probe,
    arg_max(p.price, p.time) AS price
FROM prices p
INNER JOIN times t
ON t.probe >= p.time
GROUP BY 1
ORDER BY 1;

Zukünftige Arbeit

Das neue AsOf-Loop-Join-Plan-Feature deckt nur eine häufige, aber sehr spezifische Situation ab, und der Standardoperator könnte deutlich effizienter gemacht werden, wenn er wüsste, dass die Daten bereits sortiert sind. Das ist oft der Fall, aber wir haben noch nicht die Fähigkeit, Partitionierung und Ordnung zwischen Operatoren zu verfolgen. Diese Art von Metadaten zu verfolgen, wäre sehr nützlich, um eine große Zahl von Operationen zu beschleunigen, einschließlich Sortierung (!), partitionierter Aggregation, Windowing, AsOf-Joins und Merge Joins. Das ist Arbeit, an der wir sehr interessiert sind – bleiben Sie dran!

Fazit

Mit Entschuldigung an Guido van Rossum: Es gibt meist mehr als einen Weg, etwas zu tun, aber jeder Weg kann radikal unterschiedliche Performance-Eigenschaften haben. Eine der Aufgaben einer relationalen Datenbank mit einer deklarativen Query-Sprache wie SQL ist, intelligente Entscheidungen zwischen den Optionen zu treffen, damit Sie als Nutzer sich auf das Ergebnis konzentrieren können. Hier bei DuckDB freuen wir uns darauf, mehr Wege zu finden, Ihre Queries zu planen, damit Sie sich auf das konzentrieren können, was Sie am besten können!

Anmerkungen