2025-08-08

Spatial Joins in DuckDB

Max Gabrielsson

Einleitung

Spatial Joins sind Join-Operationen, die Zeilen anhand der (geo-)räumlichen Beziehung zwischen Spalte(n) matchen. In der Praxis beantworten sie oft Fragen wie „welche dieser Punkte liegen in welchen dieser Polygone?“. Datensätze anhand der physischen Orte zu verbinden, die sie modellieren, ist grundlegend für das gesamte Feld der Geospatial Data Science, aber auf einer höheren Ebene auch ein extrem starker Weg, ansonsten disparate Datenquellen zu korrelieren und anzureichern, Insights in der realen Welt zu verankern – und nicht selten eine gute Geschichte mit der Analyse zu erzählen.

Seit ihrer Entstehung hat DuckDBs spatial-Extension einen GEOMETRY-Spaltentyp bereitgestellt, um Orte, Regionen und Formen darzustellen, zusammen mit vielen Spatial-Prädikat-Funktionen zur Nutzung beim JOIN. Erst kürzlich in DuckDB v1.3.0 wurden Spatial Joins aber wirklich skalierbar, dank der Einführung des eigenen Query-Operators SPATIAL_JOIN.

Wir haben noch schnell ein paar Infos zu diesem neuen Operator gegen Ende der v1.3.0-Release-Notes untergebracht, fanden aber, dass es genug zu erzählen gibt, um einen eigenen Blogbeitrag zu rechtfertigen. In diesem Beitrag schauen wir uns einige der Herausforderungen bei der Optimierung von Spatial Joins genauer an und wie der neue Operator SPATIAL_JOIN sie angeht, um neue Effizienzstufen zu erreichen.

Wie sieht ein Spatial Join nochmal aus?

Einen Spatial Join in SQL auszuführen ist eigentlich sehr einfach. Es braucht keine spezielle Syntax oder magische Formel. Wie Sie wahrscheinlich schon vermutet haben, müssen Sie einfach zwei Tabellen mit einer GEOMETRY-Spalte mit einem Spatial-Prädikat JOINen. Unten ein einfaches Beispiel, das zwei Tabellen some_table und another_table unter der Bedingung joint, dass die Geometrien in some_table.geom und another_table.geom sich „schneiden“, mit der Spatial-Prädikatfunktion ST_Intersects:

SELECT *
FROM some_table
JOIN another_table
  ON ST_Intersects(some_table.geom, another_table.geom);

Versuchen wir etwas Fortgeschritteneres. Wir analysieren den NYC-Citi-Bike-Trip-Datensatz, der etwa 58 Millionen Zeilen zu Leihradfahrten in New York City enthält, einschließlich Start- und Endort jeder Fahrt. Wir wollen Stadtteile in NYC finden, in denen die meisten Fahrten starten. Deshalb joinen wir die Bike-Trip-Daten mit einem Datensatz von NYC-Neighborhood-Polygonen. Dann zählen und gruppieren wir die Zahl der Fahrten, die in jedem Stadtteil starten, und sortieren und limitieren die Ergebnisse schließlich, um die Top-3-Stadtteile zurückzugeben, in denen die meisten Fahrten ihren Ursprung haben. Wir haben die Datensätze zusammengestellt und die relevanten Spalten für dieses Beispiel in zwei Tabellen, rides und hoods, in einer 218-MB-DuckDB-Datenbankdatei extrahiert.

Stellen wir sicher, dass die spatial-Extension installiert und geladen ist:

INSTALL spatial; -- Install the spatial extension
LOAD spatial;    -- Load the spatial extension

Unsere Query sieht so aus:

SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;

┌──────────────┬───────────┐
│ neighborhood │ num_rides │
│   varchar    │   int64   │
├──────────────┼───────────┤
│ Midtown      │   6253835 │
│ Chelsea      │   6238693 │
│ East Village │   4047396 │
└──────────────┴───────────┘

Diese Query joint die 58.033.724 Fahrten mit den 310 Neighborhood-Polygonen und braucht auf meinem Laptop etwa 30 Sekunden (MacBook mit M3-Pro-CPU und 36 GB RAM).

30 Sekunden mögen auf den ersten Blick nicht beeindruckend wirken (ein HASH_JOIN über ähnlich große Eingaben würde eine Größenordnung schneller fertig), aber ich bin tatsächlich zufrieden, dass DuckDB einen Spatial Join in dieser Größenordnung in einer Zeit ausführen kann, die – wenn nicht großartig – für explorative Analyse immer noch akzeptabel ist (und das auf einem Laptop!). Um den Unterschied in der Ausführungszeit im Vergleich zu z. B. einem HASH_JOIN zu verstehen, müssen wir uns zuerst genauer anschauen, wie DuckDB Spatial Joins früher gemacht hat und warum Spatial Joins so schwer zu optimieren sind. Dann tauchen wir ein, wie der neue Operator SPATIAL_JOIN das Spiel ändert.

Wie DuckDB Spatial Joins (früher) gemacht hat

Spatial-Prädikate

Das Erste, das man verstehen muss: Ein Spatial-Prädikat ist im Grunde nur eine Funktion, die eine räumliche Relation zwischen zwei Geometrien auswertet und true oder false zurückgibt, z. B. „enthält a b“ oder „liegt a innerhalb der Distanz x von b“. Theoretisch könnte man eine eigene Spatial-Prädikatfunktion schreiben, in der Praxis nutzt man aber wahrscheinlich eine der vielen, die mit der spatial-Extension kommen. Die Nuancen der verschiedenen Spatial-Prädikate gehen über diesen Beitrag hinaus, hier aber ein kurzer Überblick über die am häufigsten genutzten, mit zwei Geometrien a und b:

Wir nutzen ST_Intersects in der Beispielquery oben, um es einfach zu halten, auch wenn ST_Contains oder ST_ContainsProperly für Point-in-Polygon-Joins angemessener sein könnten.

Da alle obigen Spatial-Prädikate in der spatial-Extension leben, weiß DuckDBs Query Planner im Grunde nichts über sie, außer ihren Namen und dass sie Funktionen sind, die zwei GEOMETRY-Argumente nehmen und einen Boolean-Wert zurückgeben. Das heißt, Vanilla-DuckDB allein kann keine speziellen Optimierungen auf sie anwenden und muss sie wie jede andere Funktion in der Datenbank behandeln.

Optimierungsherausforderungen

Plant DuckDB einen Join, dessen Join-Bedingung eine beliebige Funktion ist, kann es normalerweise keine der fortgeschrittenen eingebauten Join-Strategien wie HASH_JOIN oder RANGE_JOIN nutzen, die für Gleichheit oder Bereichsvergleiche optimiert sind. Stattdessen muss DuckDB auf die einfachste Join-Strategie zurückfallen: einen Nested Loop Join (NLJ), also die Join-Bedingung für jedes mögliche Paar von Zeilen in den zwei Tabellen auszuwerten. In Pseudocode sähe ein Nested Loop Join etwa so aus:

for row_a in table_a:
    for row_b in table_b:
        if join_condition(row_a, row_b):
            emit(row_a, row_b)

Das ist der allgemeinste Weg, einen Join umzusetzen, aber auch der ineffizienteste. Da die Komplexität des Joins O(nm) ist, wobei n und m die Zeilenzahlen der zwei Tabellen sind, wächst die Zeit für den Join quadratisch mit der Größe der Eingabe.

Komplexitätsherausforderungen

Quadratische Komplexität wird bei großen Joins schnell unpraktisch, aber DuckDBs rohe Ausführungskraft macht sie bei kleinen bis mittleren Tabellen meist erträglich.

Was die Nested-Loop-Join-Strategie für Spatial Joins aber besonders unpraktisch macht, selbst in kleinerem bis mittlerem Maßstab, ist, dass Spatial-Prädikate sehr rechenintensiv auszuwerten sein können. Das liegt vor allem an der schieren Komplexität der beteiligten Algorithmen, aber auch an der denormalisierten Natur von Geometrien, bei der eine einzelne Geometrie eine sehr große Zahl von Punkten enthalten kann. Außerdem gilt in der Realität von spatial, dass die meisten Spatial-Prädikate, die mit Hilfe von Drittanbieter-Bibliotheken umgesetzt sind, einen Deserialisierungsschritt brauchen, um das interne Binärformat der GEOMETRY-Spalte in eine ausführbare Datenstruktur zu wandeln. Das erfordert meist auch Speicherallokation außerhalb von DuckDBs eigenem Memory-Management, was Druck und Lock Contention auf den globalen Memory Allocator erhöht und die Wirksamkeit zusätzlicher Parallelität einschränkt.

Um zu zeigen, wie das in der Praxis aussieht, schauen wir uns den Query-Plan für die Beispielquery oben an, aber mit deaktivierter SPATIAL_JOIN-Optimierung, um DuckDB zu einem Nested Loop Join zu zwingen:

Experiment

LOAD spatial; -- Load the spatial extension

-- Disable the spatial join optimizer
SET disabled_optimizers = 'extension';

-- Print the new plan, using EXPLAIN to verify
-- that we are using a nested loop join
EXPLAIN SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;

┌───────────────────────────┐
│           TOP_N           │
│           Top: 3          │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│       HASH_GROUP_BY       │
│            ...            │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         PROJECTION        │
│            ...            │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│     BLOCKWISE_NL_JOIN     │
│    ────────────────────   │
│      Join Type: INNER     │
│                           ├──────────────┐
│         Condition:        │              │
│ ST_Intersects(start_geom, │              │
│            geom)          │              │
└─────────────┬─────────────┘              │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│         SEQ_SCAN          ││         SEQ_SCAN          │
│    ────────────────────   ││    ────────────────────   │
│        Table: rides       ││        Table: hoods       │
│            ...            ││            ...            │
│       ~58033724 Rows      ││         ~310 Rows         │
└───────────────────────────┘└───────────────────────────┘

Diese Query mit dem BLOCKWISE_NL_JOIN (blockweisem Nested Loop Join) braucht auf meinem Laptop jetzt 30 Minuten. Ich habe die Query auch mit einer Teilmenge der Zeilen in der Tabelle rides ausgeführt, um zu sehen, wie die Performance mit der Eingabegröße skaliert. Die Ergebnisse:

Das ist offensichtlich nicht gut. Schon 1/58 des vollen Datensatzes braucht länger als die Originalquery mit aktivierter Spatial-Join-Optimierung. Und den vollen Datensatz zu verarbeiten dauert fast eine halbe Stunde! Das ist ein klares Zeichen, dass die Nested-Loop-Join-Strategie für Spatial Joins in dieser Größenordnung nicht geeignet ist, und wir wirklich etwas tun mussten.

Die IE-Join-Optimierung

Um die Lage zu verbessern, war eine der ersten Optimierungen in den frühen Versionen der spatial-Extension eine Rewrite-Regel für den Query Planner.

Da das Auswerten der Spatial-Prädikatfunktion selbst so teuer ist, ist es eine gute Idee, zuerst etwas günstiges Filtern potenzieller Join-Matches zu versuchen, um die Zahl der Paare zu reduzieren, die tatsächlich durch die präzise räumliche Beziehungskontrolle müssen. Zum Glück ist das für die meisten Spatial-Prädikate relativ einfach, weil sie alle eine gemeinsame Eigenschaft haben. Fast alle Spatial-Prädikate implizieren irgendwie Intersection, und wenn zwei Geometrien sich schneiden, müssen sich auch ihre Bounding Boxes schneiden.

Die Bounding Box, manchmal Minimum Bounding Rectangle (MBR) einer Geometrie genannt, ist das kleinste Rechteck, das die Geometrie vollständig enthält. Weil Bounding Boxes im Wesentlichen die minimalen und maximalen x- und y-Koordinaten aller Vertices der Geometrie darstellen, sind sie relativ effizient zu berechnen, indem man die Geometrie einmal durchläuft. Zusätzlich ist die Prüfung, ob sich zwei Bounding Boxes schneiden, sehr günstig, da sie in konstanter Zeit mit ein paar einfachen Less-Than- und Greater-Than-Vergleichen möglich ist.

Da Bounding-Box-Intersection als Serie von Ungleichheitsprüfungen ausgedrückt werden kann, können wir DuckDBs bestehende Inequality-Join-Funktionalität nutzen, um einen Bounding-Box-Join auszuführen! Die inneren Abläufe von Inequality Joins gehen über diesen Beitrag hinaus, weil Richard das in seinem Blogbeitrag zu Range Joins schon gut erklärt hat; kurz gesagt ist es ein Join-Typ, der zwei Tabellen effizient mit einer Serie von Ungleichheitsoperatoren wie <, >, <=, >= usw. joinen kann.

Um das zu nutzen, haben wir folgende Änderungen an spatial vorgenommen:

• Eine approximative Bounding Box für jede Geometrie in der serialisierten Binärdarstellung der GEOMETRY-Spalte cachen, damit wir sie nicht jedes Mal neu berechnen müssen, wenn wir ein Spatial-Prädikat auswerten.
• Eine Rewrite-Regel einführen, die jeden inneren Nested-Loop-Join-Operator mit einem Spatial-Prädikat in zwei neue Operatoren ändert:
  • PIECEWISE_MERGE_JOIN, ein „IE“-(Inequality-)Range-Join-Operator, der auf der Intersection der Bounding Boxes joint, geschrieben als Serie von BETWEEN-Klauseln auf den Min-/Max-Werten der Bounding Boxes
  • ein FILTER-Operator, der die resultierenden Zeilen auf die tatsächliche Spatial-Prädikatfunktion filtert.

Um zu zeigen, wie das den Query-Plan beeinflusst, gehen wir in der Zeit zurück und nutzen DuckDB v1.2.0 (das die PIECEWISE_MERGE_JOIN-Optimierung enthält, aber nicht den SPATIAL_JOIN-Operator), um die Query von oben erneut auszuführen.

LOAD spatial; -- Load the spatial extension

-- Check that we are using DuckDB v1.2.0
PRAGMA version;

┌─────────────────┬────────────┐
│ library_version │ source_id  │
│     varchar     │  varchar   │
├─────────────────┼────────────┤
│ v1.2.0          │ 5f5512b827 │
└─────────────────┴────────────┘

-- Print the new query plan, using EXPLAIN
EXPLAIN SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;

┌───────────────────────────┐
│           TOP_N           │
│    ────────────────────   │
│           Top: 3          │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│       HASH_GROUP_BY       │
│    ────────────────────   │
│            ...            │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         PROJECTION        │
│            ...            │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│ ST_Intersects(start_geom, │ -- Here we evaluate the actual
│            geom)          │ -- precise spatial predicate
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│    PIECEWISE_MERGE_JOIN   │
│    ────────────────────   │
│      Join Type: INNER     │
│                           │
│        Conditions:        │
│  ST_XMin(ST_Extent_Approx │ -- Very complex join condition,
│  (start_geom)) <= ST_XMax │ -- but its all just inequality checks!
│  (ST_Extent_Approx(geom)) │
│  ST_XMax(ST_Extent_Approx │
│  (start_geom)) >= ST_XMin ├──────────────┐
│  (ST_Extent_Approx(geom)) │              │
│  ST_YMin(ST_Extent_Approx │              │
│  (start_geom)) <= ST_YMax │              │
│  (ST_Extent_Approx(geom)) │              │
│  ST_YMax(ST_Extent_Approx │              │
│  (start_geom)) >= ST_YMin │              │
│  (ST_Extent_Approx(geom)) │              │
│                           │              │
│       ~58033724 Rows      │              │
└─────────────┬─────────────┘              │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│         SEQ_SCAN          ││         SEQ_SCAN          │
│    ────────────────────   ││    ────────────────────   │
│            ...            ││            ...            │
│       ~58033724 Rows      ││         ~310 Rows         │
└───────────────────────────┘└───────────────────────────┘

Wie Sie sehen, hat der Operator PIECEWISE_MERGE_JOIN den Operator BLOCKWISE_NL_JOIN ersetzt, und die Join-Bedingung wurde umgeschrieben, um die approximativen Bounding Boxes der Geometrien (ST_Extent_Approx) zu nutzen statt direkt auf dem Spatial-Prädikat zu joinen. Der FILTER-Operator sitzt oben drauf, um die Spatial-Prädikatfunktionen nur auf die Zeilen anzuwenden, die die initiale Bounding-Box-Prüfung bestehen.

Das sieht deutlich komplizierter aus als der ursprüngliche Nested Loop Join – wie performt es?

Viel besser, wir haben die Ausführungszeit von 30 Minuten auf knapp unter 2 Minuten für den vollen Datensatz reduziert! Das war eine enorme Verbesserung. Ohne eigenen Operator-Code konnten wir DuckDBs bestehende Inequality-Join-Funktionalität nutzen, um auch Spatial Joins deutlich zu beschleunigen.

Dieser Ansatz hat aber noch einige Nachteile:

• Dieses Rewrite ist nur für INNER-Joins möglich.
• Wir müssen jetzt Bounding Boxes für jede Geometrie speichern, was den Memory Footprint der GEOMETRY-Spalte erhöht, und wir müssen sie neu berechnen, wann immer wir eine GEOMETRY erzeugen oder ändern.
• Der Operator PIECEWISE_MERGE_JOIN muss die zwei Eingabetabellen sortieren, was viel Speicher braucht und bei großen Tabellen wirklich langsam werden kann, sobald die Daten nicht mehr in den Speicher passen.

DuckDB hat das Sortieren seitdem erheblich optimiert, und spatial und seine Funktionen haben verschiedene Optimierungen erhalten, die die Performance etwas verbessern. Trotzdem war das immer eher eine Zwischenlösung, um Spatial Joins im üblichen Fall zumindest nutzbar zu machen. Wie können wir es besser machen?

Der Spatial-Join-Operator

R-Tree-Indexierung

Kurz zur Erinnerung, wie ein R-Tree funktioniert: Es ist eine balancierte Baumdatenstruktur, in der interne Knoten Bounding Boxes enthalten, die die Bounding Boxes ihrer Kindknoten überdecken, und Blattknoten eine Bounding Box für die Geometrie und einen Pointer auf die zugehörige Tabellenzeile enthalten. So lassen sich schnell alle Geometrien nachschlagen, die eine gegebene Bounding Box schneiden, indem man den Baum von oben nach unten durchläuft und nur Zweige folgt, die die Suchbox schneiden.

Eine der Motivationen, den RTREE-Index letztes Jahr in der spatial-Extension umzusetzen, war, irgendwann die PIECEWISE_MERGE_JOIN-Optimierung durch eine indexbasierte Join-Strategie ersetzen zu können. Nach der Umsetzung des RTREE haben wir aber festgestellt, dass das Erzeugen eines R-Tree-basierten Index auf bestehenden Daten tatsächlich überraschend schnell ist. Statt vom Nutzer zu verlangen, Daten immer zuerst in eine Tabelle zu laden und dann zu indexieren, nur um Spatial Joins zu beschleunigen – was, wenn wir einfach einen temporären R-Tree-Index on-the-fly beim Ausführen des Joins erzeugen? Ähnlich wie wir eine temporäre Hash-Tabelle erzeugen, wenn wir einen HASH_JOIN ausführen.

Joinen mit R-Trees

Genau das tut der neue Operator SPATIAL_JOIN. Er nimmt zwei Eingabetabellen, buffert die gesamte Eingabe der „rechten“ Tabelle (also der Tabelle, von der der Join-Order-Optimizer erwartet, dass sie kleiner ist), baut einen R-Tree-Index auf der gesammelten Eingabe auf und führt dann einen Join aus, indem er jede Zeile der „linken“ Tabelle im R-Tree-Index nachschlägt, sobald sie ankommt. Die Idee ist genau dieselbe wie bei einem HASH_JOIN, nur dass wir statt einer Hash-Tabelle einen R-Tree als Beschleunigungsdatenstruktur nutzen, um die matchenden Zeilen nachzuschlagen.

Im Vergleich zum PIECEWISE_MERGE_JOIN-basierten Ansatz deutlich komplexer umzusetzen, hat das mehrere Vorteile:

• Die Query-Rewrite-Regel ist viel einfacher: Wir müssen nur einen Nested Loop Join mit einem Spatial-Prädikat erkennen und durch einen SPATIAL_JOIN-Operator ersetzen. Keine weiteren Änderungen am Query-Plan sind nötig.
• Nur die kleinere Seite der Eingabe muss materialisiert (und zum Bau des R-Trees sortiert) werden. Die linke Seite kann parallel gestreamt werden, und matchende Zeilen können sofort emittiert werden, sobald sie gefunden sind.
• Die hierarchische Struktur des R-Trees erlaubt uns, mehr von der rechten Eingabe genauer zu prunen.
• Da die gesamte Logik in einem Operator liegt, brauchen wir uns nicht auf einen separaten FILTER-Operator zu verlassen und können deshalb LEFT-, RIGHT- und FULL OUTER-Joins ebenso unterstützen wie INNER-Joins.

Experiment

Nur um zu zeigen, wie dieser Plan aussieht: Das bekommen Sie, wenn Sie dieselbe Query auf DuckDB v1.3.0 oder später mit aktiviertem SPATIAL_JOIN-Operator ausführen:

LOAD spatial; -- Load the spatial extension

-- Print the new query plan, using EXPLAIN
EXPLAIN SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;

┌───────────────────────────┐
│           TOP_N           │
│    ────────────────────   │
│           Top: 3          │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│       HASH_GROUP_BY       │
│    ────────────────────   │
│            ...            │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         PROJECTION        │
│    ────────────────────   │
│            ...            │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│        SPATIAL_JOIN       │
│    ────────────────────   │
│      Join Type: INNER     │
│                           │
│        Conditions:        ├──────────────┐
│ ST_Intersects(start_geom, │              │
│            geom)          │              │
│                           │              │
│       ~58033724 Rows      │              │
└─────────────┬─────────────┘              │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│         SEQ_SCAN          ││         SEQ_SCAN          │
│    ────────────────────   ││    ────────────────────   │
│            ...            ││            ...            │
│       ~58033724 Rows      ││         ~310 Rows         │
└───────────────────────────┘└───────────────────────────┘

Schön, wir sind wieder bei einer einzelnen Join-Bedingung. Wie performt das? Wir haben im ersten Beispiel schon gesehen, dass DuckDB v1.3.2 die Originalquery in etwa 30 Sekunden mit dem SPATIAL_JOIN-Operator ausführen konnte, hier aber die präzisen Ergebnisse für alle Größen und Join-Strategien zum Vergleich. Alle Queries liefen auf demselben Apple MacBook M3 Pro mit 36 GB Speicher, Zeiten gemittelt über 3 Läufe:

Der Operator SPATIAL_JOIN kann den vollen 58-Millionen-Zeilen-Datensatz schneller ausführen, als der ursprüngliche naive Nested Loop Join den 1-Millionen-Zeilen-Datensatz ausführen konnte. Das ist eine 58×-Verbesserung!

Einschränkungen und zukünftige Arbeit

Auch wenn wir viel verbessert haben, sind Spatial Joins in DuckDB noch nicht ganz perfekt. Wie immer gibt es noch viel zu tun, und wir haben ein paar Ideen, wie wir den Operator SPATIAL_JOIN noch weiter verbessern können.

Build-Seiten größer als der Speicher

Die aktuelle Implementierung des Operators SPATIAL_JOIN buffert die gesamte rechte Eingabe im Speicher, um den R-Tree-Index zu bauen. Das heißt, er kann nur rechte Eingaben behandeln, die in den Speicher passen. Wir planen, Unterstützung für R-Trees größer als der Speicher hinzuzufügen, indem wir die rechte Seite in kleinere separate R-Trees partitionieren und dann die Join-Ergebnisse jeder Partition mergen, ähnlich wie der Operator HASH_JOIN Hash-Tabellen größer als der Speicher behandelt.

Mehr Parallelität

DuckDBs Execution Engine passt die Zahl der Threads in einer Query dynamisch an die Zahl der gescannten Zeilen an, aber da Spatial-Prädikate so teuer auszuwerten sind, könnten wir potenziell von mehr Parallelität profitieren, weil Spatial Joins vor allem CPU-gebunden sind. Insbesondere erwägen wir, auch die linke Seite des Joins zu buffern und zu partitionieren, was uns erlauben würde, eigene Worker-Tasks innerhalb des Operators zu spawnen, um die Join-Bedingung über eine Zahl von Threads entkoppelt von der Kardinalität der Eingabe auszuwerten. Das würde den Speicherverbrauch erhöhen und verhindern, dass der Join gestreamt wird, aber eine ähnliche Technik haben wir beim Bau des HNSW-(Hierarchical-Navigable-Small-Worlds-)Index in der vss-Extension mit großem Erfolg eingesetzt.

Schnellere Prädikatfunktionen

Die meisten Prädikatfunktionen in der spatial-Extension sind mit Drittanbieter-Bibliotheken umgesetzt, die Overhead mitbringen, weil wir sie nicht so eng mit DuckDBs Execution Engine und Memory-Management integrieren können und oft irgendeine Art von Deserialisierung oder Konvertierung brauchen. Das kann ziemlich teuer sein, besonders bei großen Geometrien. Um die Auswirkung in der Praxis zu zeigen, können wir die Performance des Joinens auf ST_Intersects(x, y) mit dem einigermaßen äquivalenten ST_DWithin(x, y, 0) vergleichen, indem wir die vorherigen Ergebnisse mit den Zeiten der folgenden Query vergleichen:

SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_DWithin(rides.start_geom, hoods.geom, 0)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;

Nun, ST_DWithin ist nicht streng dasselbe wie ST_Intersects, das ist also kein fairer Vergleich. Auch wenn sie in diesem Beispiel dieselbe Ausgabe erzeugen, sollten Sie nicht eilig alle Instanzen von ST_Intersects durch ST_DWithin ersetzen, nur um etwas Extra-Performance herauszuholen. Tatsächlich tut ST_DWithin technisch mehr Arbeit, weil der Algorithmus komplexer ist. Der Grund, warum es in diesem Fall trotzdem schneller ist – und warum wir es erwähnen – ist, dass seine Implementierung in der spatial-Extension kürzlich auf unsere eigene hochoptimierte native Implementierung umgestellt wurde. Diese Implementierung geht den Extra-Schritt, Speicherallokation und Kopieren zu vermeiden, und die Ergebnisse sprechen für sich. Das zeigt, wie das Optimieren der Spatial-Prädikatfunktionen selbst die Performance von Spatial Joins deutlich verbessern kann. Wir arbeiten aktiv daran, optimierte Versionen der restlichen häufig genutzten Spatial-Prädikate (wie ST_Intersects, ST_Contains, ST_Within usw.) zur spatial-Extension hinzuzufügen und erwarten ähnliche Performancegewinne über die ganze Linie. Bleiben Sie also bei ST_Intersects, wenn es passt, und freuen Sie sich auf weitere Performancegewinne in der Zukunft!

Fortgeschrittene Join-Bedingungen

Der Operator SPATIAL_JOIN unterstützt derzeit nur den Fall, dass die Join-Bedingung eine einzelne Spatial-Prädikatfunktion ist. Wir planen, Unterstützung für komplexere Join-Bedingungen hinzuzufügen, die Vergleiche, arithmetische Operationen und andere Funktionen in Kombination mit den Spatial-Prädikaten enthalten können. Das erlaubt Nutzern, komplexere räumliche Beziehungen in ihren Joins auszudrücken, z. B. JOIN ... ON ST_Intersects(a.geom, b.geom) AND a.id = b.id{:.language-sql .highlight}.

ANTI- / SEMI-Joins

Der Operator SPATIAL_JOIN unterstützt derzeit nur INNER-, LEFT-, RIGHT- und FULL OUTER-Joins. Wir planen, in Zukunft Unterstützung für ANTI- und SEMI-Joins hinzuzufügen.

Fazit

Spatial Joins sind ein starker Weg, Datensätze anhand ihrer geospatialen Beziehung zu verbinden und anzureichern. DuckDBs spatial-Extension bietet eine breite Auswahl an Spatial-Prädikatfunktionen, mit denen sich Spatial Joins in SQL ausführen lassen. Während die Performance von Spatial Joins in der Vergangenheit wegen der Komplexität der Spatial-Prädikate und der Grenzen der Join-Strategien eine Herausforderung war, hebt der neue Operator SPATIAL_JOIN in DuckDB v1.3.0 Effizienz und Skalierbarkeit dieser Workloads deutlich an und macht Spatial Joins zu First-Class Citizens in DuckDBs Execution Engine.