Rebuilding spatial indexes without a memory spike

A static index is cheap to query and awkward to change: the only supported edit is to build a new one and swap it in. On a workstation that is unremarkable. On a 512 MB gateway it means both indexes exist at once, at exactly the moment the device is also parsing a freshly synced reference layer — and that combination is the single most reliable way to get a spatial service killed by the OOM reaper. This guide bounds that peak, inside the constraints described in spatial indexing on constrained devices and the wider Local Spatial Processing Patterns guide.

What the peak is actually made of #

The naïve rebuild holds four things simultaneously: the parsed features from the new layer, the sort scratch used to order them, the new index under construction, and the old index still answering queries. Only the last of those is strictly necessary during the rebuild, and it is the smallest.

For a 40 000-feature layer the arithmetic looks like this. Parsed geometry as Python objects is roughly 42 MB. The envelope list is 40 000 tuples of four floats — about 12 MB with object overhead, or 640 KB as a packed array. Sorting by Hilbert index materialises a key list and a permutation, another 3 MB. The new packed index is 845 KB, and the old one the same. The naïve total peaks near 58 MB; the same rebuild done carefully peaks near 4 MB, and the difference is entirely in representation rather than in algorithm.

The rebuild, done in bounded memory #

# index_rebuild.py — build a replacement index without materialising geometry.
# Runs on the maintenance task, never inside the ingestion path.
# The old index stays live and queryable throughout; the swap is one assignment.
import array
import gc
import os
import tempfile

from packed_rtree import PackedRTree


class IndexHolder:
    """Publishes exactly one index. Readers take a local reference; the writer
    replaces the attribute. Rebinding an attribute is atomic under the GIL, so
    no reader ever observes a partially built index."""

    def __init__(self, index=None):
        self._index = index

    @property
    def current(self):
        return self._index

    def publish(self, new_index):
        old = self._index
        self._index = new_index          # atomic rebind: readers see old or new
        return old                        # caller drops the last reference


def stream_envelopes(feature_source) -> array.array:
    """One pass over the layer, emitting envelopes straight into a packed array.
    Geometry is decoded, reduced to four floats, and discarded before the next
    feature is read — so peak memory is one feature, not the whole layer."""
    buf = array.array("f")
    for raw in feature_source:                    # yields bytes, not objects
        x0, y0, x1, y1 = envelope_of(raw)         # decodes without building a geometry
        buf.extend((x0, y0, x1, y1))
    return buf


def rebuild(holder: IndexHolder, feature_source, budget_bytes: int) -> bool:
    """Build and publish a replacement index inside a memory budget."""
    envelopes = stream_envelopes(feature_source)
    n = len(envelopes) // 4
    projected = n * 20 + 64 * 1024                # 16 B/entry + slack
    if projected > budget_bytes:
        return False                              # refuse rather than risk the OOM killer

    # The collector cannot help during the build (no cycles are created), and a
    # pass here costs 30–80 ms on this hardware, so freeze it for the duration.
    gc.disable()
    try:
        new_index = PackedRTree.from_packed(envelopes)
    finally:
        gc.enable()

    old = holder.publish(new_index)
    del old                                       # last reference: freed here
    del envelopes
    gc.collect()                                  # one deterministic pass, off the hot path
    return True


def rebuild_via_file(holder: IndexHolder, feature_source, path: str) -> bool:
    """Lowest-peak variant: build to a temp file, fsync, rename, then mmap it.
    Peak is one page rather than a whole index, at the cost of a flash write."""
    tmp_fd, tmp_path = tempfile.mkstemp(dir=os.path.dirname(path))
    try:
        with os.fdopen(tmp_fd, "wb") as fh:
            PackedRTree.write_packed(fh, stream_envelopes(feature_source))
            fh.flush()
            os.fsync(fh.fileno())
        os.rename(tmp_path, path)                 # atomic on POSIX
    except OSError:
        os.unlink(tmp_path)
        return False
    holder.publish(PackedRTree.map_file(path))    # pages fault in on demand
    return True

Three mechanisms carry the whole result. Streaming envelopes means geometry never accumulates — the parser yields raw bytes, the envelope is extracted, and the bytes are dropped before the next feature is read. Disabling the collector across the build removes a pause that would otherwise land in the middle of the largest allocation the process makes. And the file variant moves the peak off the heap entirely: the index is written page by page, then memory-mapped, so the kernel decides how much is resident and can evict it under pressure.

Constraint validation #

Gotchas and edge cases #

• The old index must be dropped explicitly. Holding a reference in a local variable, a log line, or a closure keeps both indexes alive long after the swap. publish returns the old one precisely so the caller has to decide what happens to it.
• gc.disable() is not gc.freeze(). Disabling stops collection; freezing moves existing objects out of the generational bookkeeping. On a process that builds an index once per sync window, disabling is enough — but call gc.freeze() after the initial load if the whole reference layer is long-lived, so the collector stops walking it on every pass.
• A refused rebuild needs a policy. Returning False is correct and insufficient. The caller must decide: keep the old index and alert, or degrade to a linear scan over the new layer. Silently keeping a stale index is the worst of the three, because queries continue and answers are quietly wrong.
• Memory-mapped indexes are not free of memory. The pages are resident once touched, and a query pattern that sweeps the whole index will fault all of it in. The advantage is that the kernel can evict it, not that it never occupies RAM.
• Watch out for a rebuild triggered by every message. A layer-change signal that fires per-feature rather than per-batch turns a bounded operation into a continuous one. Debounce the trigger and coalesce changes within a window, the same discipline used for threshold-based event mapping.

Verification #

Instrument three numbers around every rebuild and the whole operation becomes auditable: peak resident memory during the build, wall-clock build duration, and the feature count that went in. A rebuild whose feature count jumped 30% explains a peak that jumped 30%; one whose duration doubled with the same count usually means the device was thermally throttled at the time, which the sysfs thermal polling guide covers.

Run the rebuild once on the bench against the largest layer the fleet will ever see, with the memory watermark recorded, before shipping. The number that comes out of that run is the one the budget_bytes check should carry, with a margin — a budget guessed from the average layer will refuse nothing on the day the largest one arrives.

Deciding when a rebuild is worth its cost #

A rebuild is never free, so it needs a trigger with a defensible threshold rather than a schedule. Three triggers cover the realistic cases.

Feature-set change is the honest one: the reference layer was replaced or extended, so the index no longer describes the data. Rebuild on the change, and only on the change.

Selectivity drift is the subtle one. The layer is unchanged but the index has become less useful because the query pattern moved — traffic that used to spread across a region now concentrates on one corridor, so the cell size or node fanout that suited the old distribution over-returns candidates for the new one. The signal is candidates-per-probe climbing with no change in feature count, and the fix is a rebuild with recomputed parameters rather than the same build repeated.

Fragmentation of the overlay applies to the hybrid layout: the base is fine, the overlay has grown past the point where querying both is cheaper than merging them. Threshold it on overlay size relative to the base — a common figure is 5%.

Related #

• Spatial Indexing on Constrained Devices — the index structures this rebuild produces.
• Packed Hilbert R-tree in a static buffer — the buffer layout that makes the file variant possible.
• Profiling RSS and heap fragmentation on ARM gateways — measuring the peak this guide is trying to avoid.