R-Tree-Indizes

Die spatial-Erweiterung bietet Unterstützung für räumliche Indizierung über den R-Tree-Erweiterungsindextyp.

Warum sollte ich einen R-Tree-Index verwenden?

Bei der Arbeit mit georäumlichen Datensätzen ist es sehr üblich, Zeilen anhand ihrer räumlichen Beziehung zu einem bestimmten Interessengebiet zu filtern. Obwohl die vektorisierte Ausführungs-Engine von DuckDB ziemlich schnell ist, skaliert diese Art von Operation bei großen Datensätzen nicht sehr gut, da immer ein vollständiger Tabellenscan nötig ist, um jede Zeile der Tabelle zu prüfen. Durch das Indizieren einer Tabelle mit einem R-Tree können solche Abfragen jedoch deutlich beschleunigt werden.

Wie funktionieren R-Tree-Indizes?

Ein R-Tree ist eine balancierte Baumdatenstruktur, die das ungefähre minimum bounding rectangle jeder Geometrie (und die interne ID der entsprechenden Zeile) in den Blattknoten speichert und in jedem internen Knoten das Bounding Rectangle, das alle Kindknoten umschließt.

Das minimum bounding rectangle (MBR) einer Geometrie ist das kleinste Rechteck, das die Geometrie vollständig umschließt. Wenn wir vom Bounding Rectangle einer Geometrie sprechen (oder von der Bounding „Box“ im Kontext 2D-Geometrie), meinen wir üblicherweise das minimum bounding rectangle. Außerdem gehen wir in der Regel davon aus, dass Bounding Boxen/Rechtecke achsenparallel sind, d. h. das Rechteck ist nicht rotiert – die Seiten sind immer parallel zu den Koordinatenachsen. Das MBR eines Punktes ist der Punkt selbst.

Durch das Durchlaufen des R-Trees von oben nach unten ist es möglich, sehr schnell in einer R-Tree-indizierten Tabelle nur jene Zeilen zu suchen, deren indizierte Geometriespalte ein bestimmtes Interessengebiet schneidet, da ganze Teilbäume übersprungen werden können, wenn die Bounding Rectangles ihrer Elternknoten die Abfrageregion überhaupt nicht schneiden. Sobald die Blattknoten erreicht sind, müssen nur die konkreten Zeilen, deren Geometrien die Abfrageregion schneiden, von der Festplatte geholt werden, und die oft deutlich teurere exakte räumliche Prädikatsprüfung (und alle anderen Filter) muss nur für diese Zeilen ausgeführt werden.

Was sind die Einschränkungen von R-Tree-Indizes in DuckDB?

Bevor Sie mit dem R-Tree-Index beginnen, gibt es einige Einschränkungen, die Sie kennen sollten:

• Der R-Tree-Index wird nur für den Datentyp GEOMETRY unterstützt.
• Der R-Tree-Index wird nur für „Index-Scans“ verwendet, wenn die Tabelle (mit einer WHERE-Klausel) mit einer der folgenden räumlichen Prädikatsfunktionen gefiltert wird (da alle eine Schnittmenge implizieren): ST_Equals, ST_Intersects, ST_Touches, ST_Crosses, ST_Within, ST_Contains, ST_Overlaps, ST_Covers, ST_CoveredBy, ST_ContainsProperly.
• Eines der Argumente der räumlichen Prädikatsfunktion muss eine „Konstante“ sein (d. h. ein Ausdruck, dessen Ergebnis zur Abfrageplanungszeit bekannt ist). Das liegt daran, dass der Query Planner die Bounding Box der Abfrageregion vor der Ausführung der Abfrage selbst kennen muss, um den R-Tree-Index-Scan zu verwenden.

Zukünftig möchten wir R-Tree-Indizes auch zur Beschleunigung weiterer Prädikatsfunktionen und komplexerer Abfragen wie Spatial Joins nutzen.

Wie R-Tree-Indizes in DuckDB verwendet werden

Um einen R-Tree-Index zu erstellen, verwenden Sie einfach die Anweisung CREATE INDEX mit der Klausel USING RTREE und übergeben die zu indizierende Geometriespalte in Klammern. Zum Beispiel:

-- Create a table with a geometry column
CREATE TABLE my_table (geom GEOMETRY);

-- Create an R-tree index on the geometry column
CREATE INDEX my_idx ON my_table USING RTREE (geom);

Sie können beim Erstellen eines R-Tree-Index auch zusätzliche Optionen über die Klausel WITH übergeben, um das Verhalten des R-Tree-Index zu steuern. Um beispielsweise die maximale Anzahl von Einträgen pro Knoten im R-Tree festzulegen, können Sie die Option max_node_capacity verwenden:

CREATE INDEX my_idx ON my_table USING RTREE (geom) WITH (max_node_capacity = 16);

Die Auswirkungen, die das Anpassen dieser Optionen auf die Leistung hat, hängen stark von der Systemumgebung ab, auf der DuckDB läuft, von der räumlichen Verteilung des Datensatzes und von den Abfragemustern Ihrer konkreten Last. Die Standardwerte sollten ausreichend gut sein, aber wenn Sie mit verschiedenen Parametern experimentieren möchten, siehe die vollständige Liste der Optionen hier.

Beispiel

Hier ist ein Beispiel, das zeigt, wie ein R-Tree-Index auf einer Geometriespalte erstellt wird und in dem wir sehen können, dass der Operator RTREE_INDEX_SCAN verwendet wird, wenn die Tabelle mit einem räumlichen Prädikat gefiltert wird:

INSTALL spatial;
LOAD spatial;

-- Create a table with 10_000 random points
CREATE TABLE t1 AS SELECT point::GEOMETRY AS geom
FROM st_generatepoints({min_x: 0, min_y: 0, max_x: 100, max_y: 100}::BOX_2D, 10_000, 1337);

-- Create an index on the table.
CREATE INDEX my_idx ON t1 USING RTREE (geom);

-- Perform a query with a "spatial predicate" on the indexed geometry column
-- Note how the second argument in this case, the ST_MakeEnvelope call is a "constant"
SELECT count(*) FROM t1 WHERE ST_Within(geom, ST_MakeEnvelope(45, 45, 65, 65));

390

Wir können selbst prüfen, dass ein R-Tree-Index-Scan verwendet wird, indem wir die Anweisung EXPLAIN nutzen:

EXPLAIN SELECT count(*) FROM t1 WHERE ST_Within(geom, ST_MakeEnvelope(45, 45, 65, 65));

┌───────────────────────────┐
│    UNGROUPED_AGGREGATE    │
│    ────────────────────   │
│        Aggregates:        │
│        count_star()       │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│ ST_Within(geom, '...')    │
│                           │
│         ~2000 Rows        │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│     RTREE_INDEX_SCAN      │
│    ────────────────────   │
│   t1 (RTREE INDEX SCAN :  │
│           my_idx)         │
│                           │
│     Projections: geom     │
│                           │
│        ~10000 Rows        │
└───────────────────────────┘

Leistungsaspekte

Bulk Loading & Wartung

Das Erstellen von R-Trees auf einer bereits befüllten Tabelle ist deutlich schneller, als zuerst den Index zu erstellen und dann die Daten einzufügen. Das liegt daran, dass sich der R-Tree nach einem Insert periodisch neu balancieren und eine vergleichsweise teure Split-Operation durchführen muss, wenn ein Knoten die maximale Kapazität erreicht, wodurch weitere Splits im Baum nach oben kaskadieren können. Wenn der R-Tree-Index hingegen auf einer bereits befüllten Tabelle erstellt wird, wird ein spezieller Bottom-up-„Bulk-Loading-Algorithmus“ (Sort-Tile-Recursive) verwendet, der alle Einträge in einen bereits balancierten Baum aufteilt, da die insgesamt benötigte Knotenzahl von Anfang an berechnet werden kann.

Darüber hinaus erzeugt der Bulk-Loading-Algorithmus in der Regel einen R-Tree mit besserer Struktur (weniger Überlappung zwischen Bounding Boxen), was üblicherweise zu besserer Abfrageleistung führt. Wenn Sie feststellen, dass die Leistung beim Abfragen des R-Trees nach einer großen Zahl von Updates oder Löschungen nachlässt, kann das Löschen und erneute Erstellen des Index einen qualitativ besseren R-Tree ergeben.

Speicherverbrauch

Wie der eingebaute ART-Index von DuckDB werden alle zugehörigen Buffer, die den R-Tree enthalten, lazy von der Festplatte geladen (wenn DuckDB im disk-backed Modus läuft), sie werden derzeit jedoch nie entladen, außer wenn der Index gelöscht wird. Das bedeutet: Wenn Sie den gesamten Index scannen, wird der gesamte Index in den Speicher geladen und bleibt dort für die Dauer der Datenbankverbindung. Allerdings wird der gesamte vom R-Tree-Index verwendete Speicher (auch während des Bulk-Loadings) von DuckDB erfasst und zählt zum Speicherlimit, das durch den Konfigurationsparameter memory_limit gesetzt ist.

Tuning

Je nach Ihrer konkreten Last möchten Sie möglicherweise mit den Optionen max_node_capacity und min_node_capacity experimentieren, um die Struktur des R-Trees und sein Verhalten bei Inserts und Deletes zu ändern, siehe die vollständige Liste der Optionen hier. Im Allgemeinen kann ein Baum mit einer höheren Gesamtzahl von Knoten (d. h. einem niedrigeren max_node_capacity) zu einer feineren Struktur führen, die beim Ausführen der Abfrage ein aggressiveres Pruning von Teilbäumen ermöglicht, erfordert aber auch mehr Speicher für den Baum selbst und ist bei Abfragen größerer Regionen teurer, weil mehr interne Knoten durchlaufen werden müssen.

Optionen

Die folgenden Optionen können in der Klausel WITH beim Erstellen eines R-Tree-Index übergeben werden: (z. B. CREATE INDEX my_idx ON my_table USING RTREE (geom) WITH (⟨option⟩ = ⟨value⟩);{:.language-sql .highlight})

Option	Beschreibung	Standard
max_node_capacity	Die maximale Anzahl von Einträgen pro Knoten im R-Tree	128
min_node_capacity	Die minimale Anzahl von Einträgen pro Knoten im R-Tree	0.4 * max_node_capacity

*Sollte ein Knoten nach einer Löschung unter die minimale Anzahl von Einträgen fallen, wird der Knoten aufgelöst und alle Einträge werden vom oberen Ende des Baums neu eingefügt. Das ist eine übliche Operation in R-Tree-Implementierungen, um zu verhindern, dass der Baum zu unbalanciert wird.

R-Tree-Tabellenfunktionen

Die Tabellenfunktion rtree_index_dump(VARCHAR) kann verwendet werden, um alle Knoten innerhalb eines R-Tree-Index zurückzugeben, was beim Debuggen, Profilieren oder allgemeinen Untersuchen der Indexstruktur nützlich sein kann. Die Funktion nimmt den Namen des R-Tree-Index als Argument und gibt eine Tabelle mit den folgenden Spalten zurück:

Spaltenname	Typ	Beschreibung
level	INTEGER	Die Ebene des Knotens im R-Tree. Der Wurzelknoten hat die Ebene 0
bounds	BOX_2DF	Die Bounding Box des Knotens
row_id	ROW_TYPE	Wenn dies ein Blattknoten ist, die rowid der Zeile in der Tabelle, sonst NULL

Beispiel:

-- Create a table with 64 random points
CREATE TABLE t1 AS SELECT point::GEOMETRY AS geom
FROM st_generatepoints({min_x: 0, min_y: 0, max_x: 100, max_y: 100}::BOX_2D, 64, 1337);

-- Create an R-tree index on the geometry column (with a low max_node_capacity for demonstration purposes)
CREATE INDEX my_idx ON t1 USING RTREE (geom) WITH (max_node_capacity = 4);

-- Inspect the R-tree index. Notice how the area of the bounding boxes of the branch nodes
-- decreases as we go deeper into the tree.
SELECT
  level,
  bounds::GEOMETRY AS geom,
  CASE WHEN row_id IS NULL THEN st_area(geom) ELSE NULL END AS area,
  row_id,
  CASE WHEN row_id IS NULL THEN 'branch' ELSE 'leaf' END AS kind
FROM rtree_index_dump('my_idx')
ORDER BY area DESC;

┌───────┬──────────────────────────────┬────────────────────┬────────┬─────────┐
│ level │             geom             │        area        │ row_id │  kind   │
│ int32 │           geometry           │       double       │ int64  │ varchar │
├───────┼──────────────────────────────┼────────────────────┼────────┼─────────┤
│     0 │ POLYGON ((2.17285037040710…  │  3286.396482226409 │        │ branch  │
│     0 │ POLYGON ((6.00962591171264…  │  3193.725100864862 │        │ branch  │
│     0 │ POLYGON ((0.74995160102844…  │  3099.921458393704 │        │ branch  │
│     0 │ POLYGON ((14.6168870925903…  │ 2322.2760491675654 │        │ branch  │
│     1 │ POLYGON ((2.17285037040710…  │  604.1520104388514 │        │ branch  │
│     1 │ POLYGON ((26.6022186279296…  │  569.1665467030252 │        │ branch  │
│     1 │ POLYGON ((35.7942314147949…  │ 435.24662436250037 │        │ branch  │
│     1 │ POLYGON ((62.2643051147460…  │ 396.39027683023596 │        │ branch  │
│     1 │ POLYGON ((59.5225715637207…  │ 386.09153403820187 │        │ branch  │
│     1 │ POLYGON ((82.3060836791992…  │ 369.15115640929434 │        │ branch  │
│     · │              ·               │          ·         │      · │  ·      │
│     · │              ·               │          ·         │      · │  ·      │
│     · │              ·               │          ·         │      · │  ·      │
│     2 │ POLYGON ((20.5411434173584…  │                    │     35 │ leaf    │
│     2 │ POLYGON ((14.6168870925903…  │                    │     36 │ leaf    │
│     2 │ POLYGON ((43.7271652221679…  │                    │     39 │ leaf    │
│     2 │ POLYGON ((53.4629211425781…  │                    │     44 │ leaf    │
│     2 │ POLYGON ((26.6022186279296…  │                    │     62 │ leaf    │
│     2 │ POLYGON ((53.1732063293457…  │                    │     63 │ leaf    │
│     2 │ POLYGON ((78.1427154541015…  │                    │     10 │ leaf    │
│     2 │ POLYGON ((75.1728591918945…  │                    │     15 │ leaf    │
│     2 │ POLYGON ((62.2643051147460…  │                    │     42 │ leaf    │
│     2 │ POLYGON ((80.5032577514648…  │                    │     49 │ leaf    │
├───────┴──────────────────────────────┴────────────────────┴────────┴─────────┤
│ 84 rows (20 shown)                                                 5 columns │
└──────────────────────────────────────────────────────────────────────────────┘