Adaptive H3 Resolution for Skewed Datasets

This guide builds a versioned depth mapping that assigns each region of a dataset the grid resolution at which its partitions land inside the target size band, so a globally uniform resolution stops producing partitions that differ by three orders of magnitude.

Context and prerequisites

A single H3 resolution applied worldwide produces partitions whose sizes follow population density: a cell over a metropolitan area holds millions of rows while a cell over ocean holds none. Adaptive resolution assigns depth per region instead. This recipe uses PySpark 3.5 with the H3 bindings; the sizing arithmetic is in spatial partitioning schemes, and the join-side consequences in handling skew in large spatial joins.

What the mapping does

The mapping is a table of a few thousand rows at most, because it is keyed on a coarse base resolution. That size matters: it can be broadcast to every writer and every reader without any concern, and it can be inspected and diffed by a human when a decision looks wrong.

Complete working solution

import h3
from pyspark.sql import functions as F, types as T

BASE_RES     = 4          # the resolution the mapping is keyed on
MAX_RES      = 9          # never subdivide beyond this
TARGET_ROWS  = 4_000_000  # rows per partition at the target file size
MAPPING_VER  = 3          # bump whenever the mapping changes

def build_depth_mapping(spark, table: str, sample: float = 0.01):
    """One row per base cell: the depth at which its partitions hit the target."""
    counts = (spark.table(table).sample(sample)
        .selectExpr(f"h3_point_to_cell(bbox_min_x, bbox_min_y, {BASE_RES}) AS base")
        .groupBy("base").count()
        .withColumn("est_rows", F.col("count") / F.lit(sample)))

    @F.udf(T.IntegerType())
    def choose_depth(est_rows):
        depth = BASE_RES
        rows = float(est_rows)
        while rows > TARGET_ROWS and depth < MAX_RES:
            depth += 1
            rows /= 7.0          # each level divides a cell roughly sevenfold
        return depth

    return (counts.withColumn("depth", choose_depth("est_rows"))
                  .withColumn("mapping_version", F.lit(MAPPING_VER))
                  .select("base", "depth", "est_rows", "mapping_version"))

def apply_mapping(spark, df, mapping):
    """Derive the partition column at the depth this row's base cell was assigned."""
    with_base = df.selectExpr("*",
        f"h3_point_to_cell(bbox_min_x, bbox_min_y, {BASE_RES}) AS base")
    joined = with_base.join(F.broadcast(mapping.select("base", "depth",
                                                       "mapping_version")),
                            "base", "left")
    return (joined
        .withColumn("depth", F.coalesce("depth", F.lit(BASE_RES)))
        .withColumn("mapping_version",
                    F.coalesce("mapping_version", F.lit(MAPPING_VER)))
        .selectExpr("*", "h3_point_to_cell(bbox_min_x, bbox_min_y, depth) AS h3_cell")
        .drop("base"))

Step-by-step walkthrough

1. Key the mapping on a coarse base resolution. Keying it on the final resolution would make it as large as the partition count, which defeats the purpose. A base two or three levels above the finest depth keeps the mapping broadcastable.

2. Estimate from a sample, not a full count. The mapping needs the right order of magnitude per cell, not an exact figure, and a one-percent sample gives that in a fraction of the time.

3. Divide by seven per level. Each H3 resolution step subdivides a cell into approximately seven children, so a cell with fifty million rows reaches the target in two levels. The approximation is good enough because the target is a band rather than a point.

4. Cap the maximum depth. Without a cap, an extremely dense cell subdivides until the partition count explodes. A cap of five levels below the base is generous; hitting it is a signal that the base resolution is wrong rather than that more depth is needed.

5. Record the mapping version on every row. This is what makes a mapping change survivable: rows written under version 3 stay findable, and a query can restrict itself to one version when the layouts must not be mixed.

Common errors and fixes

Reading a mixed-depth table

The union is larger than a single-depth expansion, which is the cost of the scheme: a query touching a mixed-depth region names more cells. In practice the increase is small — the depths present in any one area are one or two — and it is far outweighed by the elimination of the straggler.

Build this expansion into a helper view or function rather than leaving it to callers, and read the set of depths present from the mapping table rather than hard-coding it. A caller who expands at one depth against a mixed-depth table gets a silently partial result, which is the worst available failure mode.

Verification

def verify_mapping(spark, table: str, target: int = 4_000_000, tol: float = 4.0):
    counts = (spark.table(table).groupBy("h3_cell").count()
                   .selectExpr("percentile_approx(count, 0.5) med", "max(count) mx"))
    row = counts.collect()[0]
    ratio = row["mx"] / row["med"]
    assert ratio < tol, f"skew persists after adaptive resolution: {ratio:.1f}×"
    assert row["med"] < target * 2, "median partition above target — base too coarse"

Run it after the first write under a new mapping version, and again quarterly. A ratio that has crept back above the tolerance means density has shifted since the mapping was built, which is the expected outcome over a year and the signal to rebuild — a scheduled change rather than an incident.

Versioning the Mapping Properly

The mapping is the piece of state that makes this scheme work and the piece most likely to be mishandled. Treating it as an ordinary configuration file is what turns a well-designed layout into an unexplainable one.

Store the mapping as a table rather than a file, with the version as part of the key, so every historical version remains readable. That makes the third box tractable: a reader encountering rows under two versions can resolve both, because both mappings still exist.

Publish a new version by writing new rows rather than by updating existing ones, and have the write path read the current version from a pointer. That makes activation atomic, makes rollback a pointer change, and leaves an audit trail of which mapping was in force when — which is the question that arises when a partition size looks wrong in retrospect.

The rewrite that brings history forward is optional, and treating it as optional is the point. A mixed-version table works; it is simply slightly less well pruned in the regions where the versions differ. Scheduling the rewrite for a quiet period, partition by partition, converts what would otherwise be a blocking migration into ordinary background maintenance.

When Uniform Resolution Is Still Right

Adaptive resolution is machinery, and machinery has a maintenance cost. Three situations do not justify it.

A geographically bounded dataset. Data covering one metropolitan area, one country of modest extent, or one utility network has a density range narrow enough that a single well-chosen resolution produces acceptable partitions. Measure the skew ratio at a uniform resolution before assuming otherwise — under four, there is nothing to fix.

A dataset whose density is stable and known. Where the distribution has been the same for years and will remain so, the simpler answer is a hand-maintained list of exceptions rather than a derived mapping: three cities get one level deeper, everything else stays uniform. It is the same idea with a tenth of the machinery, and it is honest about the fact that somebody is making the decision.

Small tables. Below a few hundred gigabytes the partition sizes are small enough that skew costs little in absolute terms, and the operational overhead of a versioned mapping outweighs the benefit. Revisit when the table grows.

The general principle is that adaptive resolution earns its complexity when the density range across the dataset spans more than about two orders of magnitude and the table is large enough that a straggler costs real time. Continental and global datasets almost always qualify; regional ones frequently do not, and adopting it there produces a system that is harder to reason about for no measurable gain.

Whichever route is taken, record the decision and the measured skew ratio in the table properties. The next person to look at partition sizes will want to know whether the current arrangement was chosen or inherited, and a one-line answer saves them re-deriving the whole analysis. It also documents the intent, which a partition specification on its own never does. A partition spec says what the layout is; the recorded reasoning says why, and only the second survives a change of team. Two sentences in the table properties are worth more than a design document nobody can find.