Partitioning Strategies for Spatial Workloads

In short: the partition is the pipeline’s most consequential decision, because it fixes the retry unit, the cache key, the parallelism and the failure blast radius all at once. Spatial data offers three families of partition — regular grids, existing administrative units and hierarchical cells — and all three are skewed, because the world is. Choose the family from what the data already partitions on, then plan for the skew rather than being surprised by it.

Every partitioning scheme in a spatial pipeline has to answer two questions that do not arise elsewhere. The first is what the cells mean on the ground, because a partition that cuts across a natural boundary forces every downstream step to reassemble it. The second is what to do about density, because spatial data is never uniform: a tile over a city has ten thousand times the features of a tile over an ocean, and a partitioning scheme that ignores that produces a run whose duration is set by one worker while the others idle.

Those two pressures pull in opposite directions. Regular grids are easy to reason about, trivially parallel and maximally skewed. Administrative units match the data’s own structure and vary in size by orders of magnitude. Hierarchical cells sit between the two and bring their own arithmetic. There is no partitioning scheme that is uniform, natural and simple, and the useful skill is knowing which of the three you are giving up.

It is worth saying plainly what makes this decision expensive to revisit, because that is the argument for spending an afternoon on it. The partition name ends up in the cache key, so changing it invalidates every cached result. It ends up in the ledger’s primary key, so changing it makes historical coverage figures incomparable. It ends up in object-storage prefixes, so changing it means either rewriting paths or living with two conventions. And it ends up in the vocabulary operators use — “the Manchester tile failed” — so changing it makes every runbook and every past incident slightly wrong. None of those is fatal individually and together they mean re-partitioning is a project rather than a refactor.

Prerequisites & Architecture Baseline#

• A stated deliverable: tiles, per-municipality extracts, a national mosaic
• A measured density distribution — features or pixels per candidate cell, not an assumption
• A canonical name per partition, stable across runs; see parametrizing spatial DAGs by tile index
• Timings from at least one full run, so the skew is a number rather than an impression
• A view on whether partitions are fixed or discovered per run
• Concurrency limits, since a partition scheme sets the fan-out width

Core Principles#

1. Partition on what the data already partitions on. Scenes arrive per scene, cadastres per municipality. A scheme that matches the delivery boundary can skip, retry and cache a delivery; one that does not spends its life recovering that structure.

2. The partition is the retry unit. Everything about failure handling follows from the cell size, so “how long does one take” is the question that sizes it, not “how many are there”.

3. Regular is not uniform. A grid is uniform in area and wildly non-uniform in content. Uniform work per partition is what matters, and no spatial grid delivers it.

4. Skew is the norm and must be planned for. The largest cell in a real spatial workload is routinely a hundred times the median. Detect it from metadata and route it, rather than discovering it as a timeout.

5. Hierarchy is worth having. A scheme with parents and children lets one level be the orchestrated unit and another the output, which resolves most granularity conflicts.

6. Changing the partition is expensive. Cache keys, ledgers, coverage histories and operator habits all encode it. Decide deliberately, and re-partition as its own project rather than alongside something else.

Production Implementation#

The comparison that matters is not which scheme is best but what each does to the work distribution, which is measurable before any work is done.

from __future__ import annotations

from dataclasses import dataclass
from statistics import median

import h3
from shapely.geometry import shape


@dataclass(frozen=True)
class PartitionStats:
    scheme: str
    count: int
    p50: float
    p99: float
    max: float

    @property
    def skew(self) -> float:
        """How much slower the worst partition is than the typical one."""
        return self.max / self.p50 if self.p50 else float("inf")


def profile(scheme: str, weights: list[float]) -> PartitionStats:
    ordered = sorted(weights)
    return PartitionStats(
        scheme=scheme,
        count=len(ordered),
        p50=median(ordered),
        p99=ordered[int(len(ordered) * 0.99)],
        max=ordered[-1],
    )


def weights_by_grid(features, zoom: int) -> list[float]:
    counts: dict[tuple[int, int], int] = {}
    for f in features:
        for x, y in tiles_intersecting(shape(f["geometry"]), zoom):
            counts[(x, y)] = counts.get((x, y), 0) + 1
    return list(counts.values())


def weights_by_admin(features, key: str = "municipality") -> list[float]:
    counts: dict[str, int] = {}
    for f in features:
        counts[f["properties"][key]] = counts.get(f["properties"][key], 0) + 1
    return list(counts.values())


def weights_by_h3(features, resolution: int = 6) -> list[float]:
    counts: dict[str, int] = {}
    for f in features:
        c = shape(f["geometry"]).representative_point()
        cell = h3.latlng_to_cell(c.y, c.x, resolution)
        counts[cell] = counts.get(cell, 0) + 1
    return list(counts.values())


def compare(features) -> list[PartitionStats]:
    return [
        profile("z10 grid", weights_by_grid(features, 10)),
        profile("municipality", weights_by_admin(features)),
        profile("h3 r6", weights_by_h3(features, 6)),
    ]

Running that over a real layer before choosing is twenty minutes of work and it replaces the entire argument:

scheme         count    p50      p99      max     skew
z10 grid        1 284      41    3 902   28 640    698x
municipality      374     820   19 400   61 200     75x
h3 r6           2 110      64    1 980    9 100    142x

Something worth noticing in those figures: the administrative scheme has the lowest skew despite having the most obviously unequal cells. That is not a coincidence — a municipality is a unit that exists because people live there, so its boundaries already correlate with density in a way a regular grid’s cannot. The grid’s cells are equal in area, which is precisely the dimension that does not predict work. Where a natural partition exists, it is usually less skewed than the artificial one people reach for first, and it is worth measuring rather than assuming.

The profiling function above is deliberately weight-based rather than time-based, and the distinction is worth understanding before trusting its output. Feature counts and pixel counts are proxies for work, and they are good proxies for most operations — a tile with ten thousand features takes roughly a hundred times as long as one with a hundred. They are poor proxies when the operation’s cost is superlinear, which happens with overlays, unions and anything doing pairwise geometry comparisons. Where the pipeline does that kind of work, square the weight before profiling, or the scheme that looks acceptable will be far more skewed in practice than the numbers suggested.

Step-by-Step Walkthrough#

1. Name the deliverable. If the product is a tile pyramid, the tile is a candidate; if it is per-municipality extracts, the municipality is.
2. Profile the candidates on real data, as above. Count, median, p99 and maximum, per scheme.
3. Pick the scheme from the deliverable and the skew together, preferring the one the data already carries.
4. Choose the grain so a typical partition takes one to fifteen minutes, which is the range where retries are cheap and overhead is negligible.
5. Plan for the tail: split it, route it to a larger pool, or accept it explicitly with a longer timeout.
6. Record the scheme and the grain where the ledger and the cache key can see them, because both encode it.

Step four is where most schemes go wrong, and the reason is that people size the partition from the count rather than from the duration. “Four hundred tiles” sounds like a sensible fan-out and says nothing about whether each takes four seconds or forty minutes; only the second number tells you whether a retry is cheap, whether progress is visible, and whether the run fits its window. Sizing from duration also makes the decision robust to the data growing: a scheme chosen because it yields a convenient number of cells becomes wrong the moment the resolution doubles, whereas one chosen because a cell takes about five minutes simply needs its grain adjusted.

Step six is the one that is easiest to skip and hardest to add later. The scheme and the grain belong in the cache key and in the ledger’s schema, so that a change to either is a change to the key rather than an invisible reinterpretation of existing rows. Without it, re-partitioning silently makes old ledger entries refer to units that no longer exist, and a coverage query returns a number that is arithmetically valid and semantically meaningless.

Edge Cases & Failure Recovery#

One partition dominates the run. The single commonest spatial partitioning problem; handling skewed partitions treats it in full. The short version is to detect it before scheduling and subdivide rather than waiting.

Features straddle partition boundaries. A road crosses a municipality line, a building sits on a tile edge. Decide once whether a feature belongs to the partition containing its representative point or to every partition it touches, and apply it everywhere — the two produce different totals and both are defensible.

The partition set changes. A municipality merges, a service area grows. Coverage history changes meaning, so the change belongs in a reviewed diff rather than as a silent recomputation.

Two products want different partitions. Common and fine: partition each product for its own deliverable and let them share the underlying data. Forcing one scheme on both means one product carries the other’s skew.

The partition is too small. Orchestration overhead dominates and the run slows down while looking more parallel. Benchmarking orchestrator overhead gives the numbers; batching adjacent partitions is the fix.

A partition has no work at all. Common at the edges of a footprint and in oceans, and worth handling deliberately: a task that produces nothing is not a failure, but a coverage figure that counts it as missing is misleading. Recording an empty partition as built-and-empty, rather than omitting it, is what keeps the arithmetic honest.

The natural unit is far too large. A single national dataset delivered as one file, with no internal structure. Subdividing it is then unavoidable, and the sensible response is to impose a grid on the output while treating the input as one unit — which is the shape most bulk-conversion pipelines take.

Configuration Reference#

Frequently Asked Questions#

Related#

• Choosing tile sizes for raster partitioning — picking the grain for rasters
• Partitioning vector data by H3 cell — the hierarchical-cell option
• Handling skewed partitions in spatial workloads — what to do about the tail
• DAG design principles for spatial ETL — why the partition decides the graph’s shape
• Parametrizing spatial DAGs by tile index — naming the partitions
• Benchmarking orchestrator overhead for small geotasks — the lower bound on grain

← Geospatial Orchestration Architecture Fundamentals