R-Tree Index Rebuild Strategies

An RTREE index that was perfect the day it was built slowly rots under inserts, updates, and deletes until its node envelopes overlap so heavily that the optimizer quietly abandons it — this walkthrough, part of the spatial indexing internals reference, isolates exactly when to rebuild a DuckDB RTREE index, how to do it deterministically with DROP INDEX plus CREATE INDEX USING RTREE, and how to prove from the plan that the fresh tree is actually serving your bounding-box filters. The failure it targets is the “fast last week, slow today” index: correct results, an order of magnitude slower, with no error to page on.

Root-Cause Analysis of a Degraded Index #

A “slow after updates” spatial index is not one bug but a small family of them, and the remedy differs by cause. Diagnose before you rebuild — a rebuild is a heavy operation and cures only some of these.

• Node-envelope fragmentation from churn. Every insert widens the minimum-bounding-rectangle (MBR) of the leaf node it lands in and, transitively, its ancestors. Every delete leaves a node whose envelope is now larger than the geometry it still contains. After enough mutations the internal nodes overlap so much that a range descent must follow many subtrees, and the cheap MBR-prune stage stops pruning. This is the classic degradation the spatial indexing internals reference flags under heavy updates, and the only real fix is a rebuild.
• Index built before the bulk load. If you CREATE INDEX on an empty table and then INSERT or COPY millions of rows, every inserted row pays per-row tree-maintenance cost and the tree is assembled in arrival order, not a packed bottom-up order. The result is both a slow load and a low-quality tree. The fix is ordering, not tuning: load first, index second.
• Stale planner statistics. Sometimes the tree is fine but the optimizer’s cardinality estimate is not, so it costs the RTREE_INDEX_SCAN as more expensive than a SEQ_SCAN and skips it. Here a rebuild appears to “fix” the problem only because it refreshes statistics — the cheaper cure is to re-analyze.
• Unsorted insertion order. An index over rows with no spatial locality has overlapping sibling envelopes from birth. This is a quality problem present from the first build, not a degradation, and it compounds with churn.
• Intrinsically overlapping geometry. Rivers, road networks, and sprawling multipolygons have envelopes that overlap no matter how the tree is packed. No rebuild helps; decompose the geometry instead.

The distinguishing question is whether EXPLAIN ANALYZE still shows an RTREE_INDEX_SCAN that now emits far more candidate rows than it used to (fragmentation), or shows a SEQ_SCAN where an index scan used to be (statistics or eligibility). The diagnostics section below separates the two.

Deterministic Configuration #

Rebuilding an index has the same memory profile as building one — the bulk sort plus node buffers plus the source column must coexist under the process ceiling. Set the guardrails before any CREATE INDEX so a rebuild spills predictably rather than aborting midway.

INSTALL spatial; LOAD spatial;

-- Cap the working set: the sort feeding the packed tree, the node buffers, and
-- the geometry column compete for this. Too low → spill; too high on a shared
-- box → OS OOM-kill mid-rebuild, leaving the table with no usable index.
SET memory_limit = '8GB';

-- Physical cores only. The bulk sort ahead of a bottom-up build scales with
-- cores, but node-split locks serialize past the physical count, so extra
-- threads add contention without shortening the rebuild.
SET threads = 8;

-- A local spill target so a rebuild larger than memory_limit degrades to disk
-- instead of failing. Never point this at a network mount.
SET temp_directory = '/var/tmp/duckdb_rebuild';

-- Bound the spill so a runaway rebuild cannot fill the volume.
SET max_temp_directory_size = '40GB';

Confirm these preconditions before you touch a production index:

• The table is materialized on disk (an in-memory database loses every RTREE index when the process exits — persistence is covered below).
• The geometry column is native GEOMETRY, not a raw WKB BLOB; the cached-envelope difference is analyzed in ST_Geometry vs WKB storage.
• memory_limit leaves headroom for the sort plus the column, or a spill directory is set.
• You have a baseline plan (candidate-row count from EXPLAIN ANALYZE) to compare the rebuilt index against.

Optimized Execution Pattern #

The wrong order is the most common own-goal: creating the index and then loading. The right order builds the index once, over data already at rest, so the packed tree reflects the final row set.

-- ANTI-PATTERN: index first, then bulk load. Every COPY'd row pays per-row
-- tree maintenance and the tree ends up in arrival order — slow load, poor tree.
CREATE TABLE parcels (id BIGINT, geom GEOMETRY);
CREATE INDEX idx_parcels_geom ON parcels USING RTREE (geom);
COPY parcels FROM 'parcels/*.parquet';   -- millions of incremental tree inserts

-- OPTIMIZED: load first, then build once over data at rest. Sorting along a
-- space-filling curve first keeps sibling node envelopes tight and selective.
CREATE TABLE parcels (id BIGINT, geom GEOMETRY);
COPY parcels FROM 'parcels/*.parquet';

-- One-time Hilbert re-cluster so the packed R-tree's internal MBRs don't overlap.
CREATE TABLE parcels_sorted AS
  SELECT * FROM parcels
  ORDER BY ST_Hilbert(geom, ST_Extent_Agg(geom) OVER ());

CREATE INDEX idx_parcels_geom ON parcels_sorted USING RTREE (geom);

The behavioral change is entirely in ordering: the index now sees the whole population at once and packs leaves along the Hilbert curve, so each internal node encloses a spatially compact set of children. That is the same locality argument that makes a sorted GeoParquet layout prune whole row groups before the index is even consulted.

For a table already in production, a rebuild is a DROP then CREATE. Do the re-cluster in the same pass so you pay the sort cost once:

-- Rebuild a fragmented index. DROP releases the degraded tree; the ORDER BY
-- re-packs leaves; CREATE assembles a fresh, tight tree bottom-up.
DROP INDEX IF EXISTS idx_parcels_geom;

CREATE TABLE parcels_rebuilt AS
  SELECT * FROM parcels
  ORDER BY ST_Hilbert(geom, ST_Extent_Agg(geom) OVER ());

CREATE INDEX idx_parcels_geom ON parcels_rebuilt USING RTREE (geom);
CHECKPOINT;   -- flush the new index pages to the database file

The node fanout is tunable at build time. A larger max_node_capacity yields a shallower tree — fewer hops per descent — at the cost of coarser pruning per node, because each fatter node’s envelope encloses more children:

-- Shallower tree, fewer hops, coarser per-node pruning. Default is 128;
-- raise it for read-mostly tables with compact, non-overlapping geometry.
CREATE INDEX idx_parcels_geom ON parcels_rebuilt USING RTREE (geom)
  WITH (max_node_capacity = 256);

Rebuild Cost vs Incremental Inserts #

Whether to rebuild or let inserts accumulate is a throughput trade-off. A full rebuild is dominated by a sort of $O(N \log N)$ over the whole table plus a bottom-up tree assembly, so its cost is a function of total size, not delta size. Incremental inserts cost roughly $O(\log N)$ per row but degrade tree quality as they accumulate. The crossover is a ratio, not an absolute:

The rule of thumb: rebuild when the candidate-row count from the index scan has drifted well above its post-build baseline, or when a batch mutated more than a small fraction of the rows. For pure append workloads where the delta is small and spatially local, incremental inserts win outright.

Diagnostic Queries & Plan Validation #

Never rebuild on a hunch. First confirm the index exists and note its type, then measure whether the bounding-box filter still routes through it.

-- Confirm the index is registered and is an RTREE, not something else.
SELECT index_name, table_name, index_type, is_unique
FROM duckdb_indexes()
WHERE table_name = 'parcels_rebuilt';

-- The measured plan for a bbox filter. Watch the candidate-row count the
-- RTREE_INDEX_SCAN emits versus your post-build baseline.
EXPLAIN ANALYZE
SELECT count(*) FROM parcels_rebuilt
WHERE geom && ST_MakeEnvelope(-74.05, 40.68, -73.90, 40.82);

Three signals decide the verdict:

1. Operator identity. A fresh, healthy index shows RTREE_INDEX_SCAN feeding the exact predicate. A SEQ_SCAN here means the index was bypassed — a statistics or eligibility problem, not fragmentation, so re-analyze or unwrap the geom column before considering a rebuild.
2. Candidate rows emitted. If the index scan runs but emits many times the candidate count it did right after the last build, the tree has fragmented and a rebuild is warranted. This is the number to record as a baseline immediately after every build.
3. Estimated vs actual cardinality. A large gap tells the optimizer the wrong selectivity and can itself flip the plan to SEQ_SCAN; refresh statistics first, since that is far cheaper than a rebuild.

To confirm the rebuilt index persists across sessions, reconnect to the on-disk database and re-run the plan — the RTREE_INDEX_SCAN should reappear without any CREATE INDEX in between, because DuckDB stores the tree in the database file. If it does not, the table was in an in-memory database, or the process exited before a CHECKPOINT flushed the index pages. The same two-stage MBR-prune-then-exact routing this index enables is exploited across two tables by the spatial joins and proximity filters reference; whether the whole build fits in memory at all is governed by the in-memory vs disk storage boundaries.

Geometry Validation & Fallback Routing #

A rebuild is the right moment to repair geometry, because invalid rows produce wrong MBRs that the fresh tree will faithfully index. Quarantine and fix before the CREATE INDEX, never after:

-- Isolate offenders so a self-intersection can't seed a wrong envelope.
SELECT id, ST_IsValidReason(geom) AS why
FROM parcels
WHERE NOT ST_IsValid(geom);

-- Repair deterministically, then rebuild so the R-tree reflects fixed MBRs.
UPDATE parcels SET geom = ST_MakeValid(geom) WHERE NOT ST_IsValid(geom);

DROP INDEX IF EXISTS idx_parcels_geom;
CREATE INDEX idx_parcels_geom ON parcels USING RTREE (geom);

When the source table is too large for the sort feeding a rebuild to fit under memory_limit, do not fight the OOM — partition the rebuild. Split the table by a coarse spatial grid, materialize and index each partition separately, so each tree is built over a working set that fits:

-- Chunked rebuild: partition by a coarse cell, index each shard independently.
CREATE TABLE parcels_part AS
  SELECT *, floor(ST_X(ST_Centroid(geom)) / 10000) AS shard
  FROM parcels;

-- Build one RTREE per shard table if memory cannot hold the whole sort at once,
-- or set temp_directory (above) and let a single build spill gracefully.

If you are arriving here from a PostgreSQL background, the mechanics of translating a GiST index and its maintenance rhythm to DuckDB’s RTREE are covered in migrating GiST indexes to R-tree, where the same “build after load, rebuild after churn” discipline applies.

Related #

See also

• Spatial indexing internals — how the R-tree is built, traversed, and read from the plan, which this rebuild guide extends.
• Migrating GiST indexes to R-tree — the PostGIS-to-DuckDB translation of index creation and maintenance.
• Spatial joins and proximity filters — where a healthy, freshly rebuilt R-tree pays off across two tables.

Up: Spatial Indexing Internals · DuckDB Spatial Architecture & Fundamentals