R-tree vs GiST Index Performance in Test Environments

9 min read

When a test performs a spatial join, the index behind it drives both how fast the test runs and, subtly, what order results come back in. This comparison sits beneath choosing spatial testing tools and weighs an in-memory R-tree — Shapely’s STRtree or the index behind GeoPandas sjoin — against a PostGIS GiST index, on the axes that matter for a test suite: build and query cost, determinism of result ordering, memory footprint, and whether the test must exercise the same index type production uses. Both accelerate the same operation — finding candidate geometries whose bounding boxes intersect a query box — but they live in different places, and picking the wrong one either slows the suite or lets it pass against an index that does not match production.

The root difference: in-memory structure vs database access method

An R-tree is an in-memory tree you build over a set of geometries and query directly from Python; a GiST index is a PostgreSQL access method the planner uses to answer a spatial query. Both give an average query complexity of

O(log⁡n)O(\log n)

for a well-balanced tree over nn geometries, versus the O(n)O(n) of a brute-force scan — so the asymptotics are similar. The practical differences are elsewhere: the R-tree has no round-trip and no persistence but must be rebuilt each run and held in RAM, while GiST is persistent, planner-optimized, and shared with production but requires a database and returns rows in planner-determined order.

Both indexes do the same two-phase work

The performance argument makes more sense once it is clear that neither structure answers a spatial query directly. Both do the same thing: use bounding boxes to produce a small candidate set, then run the exact geometric predicate on the survivors. The index is a filter, and everything that differs between them is about where that filter lives and what it costs to build.

Filter, then refine — the shape both indexes share A two-phase pipeline. Phase one, the bounding-box filter, takes the full feature set and reduces it to a small candidate set; each comparison is a cheap rectangle overlap test. Phase two, the refinement, runs the exact geometric predicate through GEOS on the candidates only; each comparison is expensive. Annotations record that total query cost is dominated by the number of candidates surviving phase one, which is what the index choice actually influences, and that a query whose predicate cannot be expressed as a box test skips phase one entirely and pays the expensive phase on every feature. all features millions 1 · box filter rectangle overlap cheap per comparison 2 · exact predicate GEOS, on candidates only expensive per comparison millions a handful Total cost is dominated by how many candidates survive phase one — which is the only quantity the index choice really controls. A predicate the planner cannot reduce to a box test skips phase one entirely and pays phase two on every feature. That single failure explains far more slow spatial queries than any difference between the two structures.

Comparison reference

Axis R-tree (in-memory) GiST (PostGIS)
Location Python process PostgreSQL
Build cost Rebuilt per run, O(nlog⁡n)O(n\log n) Persisted, built once
Query cost O(log⁡n)O(\log n) avg, no round-trip O(log⁡n)O(\log n) avg + query overhead
Result ordering Insertion / array order Planner-determined
Memory Whole set in RAM Buffer cache
Matches production join Only if prod is in-process Yes, when prod uses PostGIS
Setup in CI None Needs a database service

Where the R-tree wins

For a join against an in-memory fixture that fits in RAM, an R-tree is the fastest path and needs no database in CI. Shapely 2.x’s STRtree builds once and answers many queries, which is ideal for validating an in-process transform’s output.

# Shapely STRtree: in-memory candidate lookup, no database
from shapely import STRtree
import geopandas as gpd

zones = gpd.read_file("tests/fixtures/zones.gpkg")
points = gpd.read_file("tests/fixtures/points.gpkg")

tree = STRtree(zones.geometry.values)          # build once, O(n log n)
for pt in points.geometry:
    idx = tree.query(pt, predicate="within")   # O(log n) average
    assert len(idx) == 1, "point must fall in exactly one zone"

GeoPandas sjoin uses the same in-memory index under the hood, so a whole-frame join is one call — the right tool when the data is already in a GeoDataFrame, echoing the Shapely vs PostGIS placement logic.

Where GiST wins

When the join under test is a query you also run in production, testing against a GiST index exercises the same access method and planner behaviour, catching ordering and cardinality differences an in-memory index would hide. It is also the only option when the data is too large to hold in memory.

-- PostGIS: the same join production runs, backed by GiST
CREATE INDEX ON zones USING GIST (geom);      -- built once
SELECT p.id, z.id
FROM points p JOIN zones z ON ST_Within(p.geom, z.geom);

Because the planner decides join order, a test that asserts on row order must sort explicitly — relying on the incidental order a GiST scan returns is how a suite passes locally and fails when the planner picks a different plan on the CI database.

Determinism: the trap in both

Neither index guarantees a stable result order for free. An R-tree query returns candidate indices in the tree’s internal order, and a GiST-backed query returns rows in planner order; both can change when the data or statistics change. Any assertion over a joined result must impose an explicit sort before comparing, or it becomes a flaky gate. This is the same determinism discipline the spatial assertion types work insists on — pin the order, then assert.

# Impose a deterministic order before asserting on a join result
joined = gpd.sjoin(points, zones, predicate="within").sort_values(["id_left", "id_right"])
assert list(joined["id_right"]) == expected_ids

Where the build cost lands in a test run

The performance question that matters in a test environment is not query speed — both structures answer a query in microseconds at fixture scale — it is where the index construction cost falls and how many times you pay it. That is a fixture-scope question dressed up as an index question.

An in-memory tree is built once per process and dies with it, so under pytest-xdist every worker rebuilds it. A database index is built once when the table is populated and persists for the life of the container, so all workers share it — but the container itself has to start, and the table has to be loaded. Which arrangement is cheaper depends entirely on the ratio of workers to tests.

In-memory tree Database index
Built Once per process Once per table load
Under 8 xdist workers Built 8 times Built once, shared
Setup before first query Milliseconds Container start plus load
Survives a process restart No Yes, for the container’s life
Cost scales with Worker count Data volume
Index build cost against worker count A chart of total index construction cost versus the number of parallel test workers. The in-memory tree line begins at almost zero for a single worker and rises in a straight line, since each worker constructs its own copy of the tree. The database index line begins high, because the container must start and the table must be loaded, and then stays flat as workers are added because they all share the same index. The lines cross at a moderate worker count. An annotation records that the crossing point shifts to the left as the fixture grows, so which structure is cheaper is a function of dataset size and parallelism rather than a fixed property of either. build cost xdist workers in-memory tree — once per worker database index — once, shared crossing point moves left as the fixture grows container start + load

The practical reading: for a small fixture and a handful of workers, the in-memory tree is obviously right and a database is overhead. For a large fixture under high parallelism the position reverses, and it reverses silently — the suite simply gets slower as the team adds workers, with no failure to investigate. Measuring the index build separately from the queries, once, is what makes that visible before it becomes a mystery.

Same set, different order — and the assertion that survives it One query is shown running against two index types. The in-memory tree returns the matching features in insertion order; the database index returns the identical set in index traversal order. Two assertions are then compared: one that compares the returned list directly, which fails whenever the index or planner changes even though the result set is identical, and one that compares sets or sorts by a stable key first, which passes under both. A closing rule states that no assertion should depend on an order that no explicit ordering clause guaranteed. one query, one result set in-memory tree [7, 3, 12, 5] · insertion order database index [3, 5, 7, 12] · traversal order assert result == [7, 3, 12, 5] fails on the other index — same set assert set(result) == {3, 5, 7, 12} passes under both Rule: never assert on an order that no explicit ordering clause guaranteed. Index choice is exactly the kind of thing that changes underneath you.

Failure modes and edge cases

  1. Asserting on unsorted join order. Both indexes return implementation-ordered results; sort explicitly or the gate flakes.
  2. Rebuilding the R-tree in a loop. Constructing an STRtree per query instead of once turns an O(log⁡n)O(\log n) lookup into repeated O(nlog⁡n)O(n\log n) builds.
  3. Testing R-tree when production is GiST. An in-memory join can pass while the production query returns different cardinality at boundary-touching geometries.
  4. No GiST index in the test database. Forgetting CREATE INDEX ... USING GIST makes the planner do a sequential scan, so the test measures nothing like production performance.
  5. Empty and null geometries. Both indexes skip null geometry; a join that should flag an unmatched point silently drops it — assert expected match counts, not just the matches found.

What to measure before choosing

Two numbers settle this for a given suite, and both take minutes to obtain. First, the index build time at your fixture size, measured on its own rather than inside a test — construct the tree, or create the index and load the table, and time only that. Second, the query time for a representative predicate, run enough times to be stable.

If build time dominates query time by an order of magnitude, which it usually does at fixture scale, then the index structure is nearly irrelevant to the suite’s runtime and the decision should be made on other grounds: whether the production path uses the database, whether the assertion needs set-level semantics, whether a container is already running for other reasons. Choosing an index for query performance in a test suite is optimising the smaller number, and it is the reason this comparison is more often about fixtures than about trees.

Conclusion

R-tree and GiST share O(log⁡n)O(\log n) average query cost, so the choice is about placement and fidelity: an in-memory R-tree for fast joins against fixtures that fit in RAM, a GiST index when the join mirrors a production query or the data is too large to load. Whichever you pick, impose an explicit result order before asserting, because neither guarantees a stable one. For the full tool-selection framework, return to choosing spatial testing tools.

When production and test disagree about which index answers a query, the test is measuring something production never does — which is worth checking before either structure is optimised.

Record the index type the test used in the run summary, so a later performance question can be answered without re-running anything.