Module 18 · Lesson 3 of 10Free

Spatial grids: geohash, S2 and H3 compared

Level

Advanced

Topic

Location, maps and matching systems

Reading time

19 min

At Rydo, a courier stands 20 metres from a restaurant. Dispatch searches the restaurant’s grid cell and finds nobody. The courier is across the cell boundary.

Would replacing rectangular cells with hexagons fix this? How should Rydo choose between geohash, S2 and H3 without losing nearby couriers?

For this lesson’s scenario, Rydo searches within a 2 km radius. It also groups courier supply into neighbourhood reports. Those jobs share coordinates, but they do not necessarily need the same grid settings.

A cell is not a radius

A spatial grid divides a surface into named cells. Turning coordinates into a cell identifier lets a database group nearby records.

The proximity search lesson established the two-stage approach: retrieve possible matches, then test their distances. A grid supplies the first stage.

A conservative covering is a set of cells containing the entire search region. It may include extra territory, but it must not leave gaps.

For a complete index, this gives a useful contract:

• Every courier within the radius appears among the candidates.
• Some candidates may lie outside the radius.
• The distance test removes those extra candidates.

Selecting cells whose centres lie inside the circle does not satisfy that contract. A cell centre can be outside even when part of its cell overlaps the circle.

This boundary problem exists with all three grids. Their differences appear in how they name cells, represent neighbours and relate coarse cells to fine ones.

Three grids organize space differently

Geohash keeps prefixes useful

Geohash encodes a latitude–longitude rectangle as a string. Longer strings identify smaller cells. Shorter strings identify larger cells. ^{1Geohash grid aggregationElastic, Elasticsearch Reference}

As covered in Geohash, extending a prefix selects a smaller rectangle inside it. That makes prefix grouping useful when your storage already supports string keys.

Rydo could group fine-cell records by their shared prefix. But adjacent rectangles can sit across a prefix boundary. A prefix scan is therefore a region lookup, not a nearest-neighbour operation.

Cell dimensions also change with latitude. Elastic’s dimensions table explicitly describes equatorial sizes rather than universal dimensions. ^{1Geohash grid aggregationElastic, Elasticsearch Reference} A precision selected for one city should not become an unmeasured global distance assumption.

Geohash is attractive when the existing index already uses it. Moving away needs a measured benefit, not a preference for another shape.

S2 nests cells on a sphere

S2 starts with six cube faces projected onto a sphere. Each cell divides into four children. Its cells are spherical quadrilaterals, rather than latitude–longitude rectangles. ^{2S2 CellsS2Geometry}

The nesting gives Rydo a useful operation: represent a large region with coarse cells and refine its boundary with smaller cells. Descendants stay within their parent’s geographic boundary.

S2 stores cell identity in 64 bits and orders cells along a Hilbert curve. This curve visits spatial regions in an ordered sequence. ^{2S2 CellsS2Geometry} The identifier is an address within that ordering, not a distance measurement.

An implementation can exploit hierarchy when searching or grouping regions. However, readers and writers must agree on levels and descendant lookup rules. A coarse covering cannot directly equality-match an index containing only fine-cell IDs.

S2’s advantage here is hierarchical region organization. It does not remove the need to cover boundaries correctly.

H3 favours hexagonal neighbourhoods

H3 builds a mostly hexagonal grid using an icosahedron, a solid with twenty faces. Each resolution also contains twelve pentagons. ^{3Overview of the H3 Geospatial Indexing SystemH3}

For an ideal flat hexagonal patch, each cell has six edge-sharing neighbours. That gives neighbourhood analysis a consistent local pattern, unlike square grids where edge and diagonal neighbours differ.

This motivates testing H3 for Rydo’s supply reports. A neighbourhood could combine a cell with its surrounding cells. However, that is a grid neighbourhood, not a fixed road distance or travel time.

H3 has a subtle hierarchy rule. A hexagonal cell has seven logical children, but those children do not fit exactly inside its geographic outline. Logical ownership is exact; geometric containment across resolutions is approximate. ^4IndexingH3

At one resolution, cell boundaries remain well-defined. The limitation concerns relationships between resolutions, not uncertainty about which fine cell contains a point.

That difference matters when Rydo turns fine-cell counts into coarse reports.

A parent can mean two things

Suppose Rydo indexes each courier in a fine H3 cell. It then replaces each fine-cell ID with its logical parent to produce a neighbourhood report.

The resulting count answers:

“How many indexed couriers belong to this parent in the hierarchy?”

It need not answer:

“How many courier coordinates lie inside this coarse cell’s geographic outline?”

For H3, directly indexing a coordinate at a coarse resolution can differ from taking the parent of its fine-resolution cell. ^4IndexingH3

Neither H3 report is inherently wrong. The error is promising one interpretation and computing the other.

For a stable hierarchy-based dashboard, choose a fine resolution and roll up its logical parents. For counts inside a particular geographic boundary, test coordinates against that boundary instead.

This also separates dispatch from reporting. Dispatch needs complete candidate retrieval for a radius. Reports need a documented rule for assigning events to groups.

The grid choice should follow those contracts, rather than forcing every operation into one interpretation of “nearby”.

Choose the operation before the shape

The pilot selects a grid family. It has not yet selected a resolution, which often determines more of the query cost.

Smaller cells exchange one cost for another

Large cells reduce the number of bucket lookups. They also bring more unrelated couriers into the candidate set.

Small cells reject more territory before records are read. However, the query must enumerate and retrieve more buckets.

Use an illustrative local workload, not a published benchmark. Assume the search region has roughly uniform density. All areas below are measured totals for hypothetical conservative coverings, not actual H3 resolution sizes.

The useful target is lower total work per successful query, not smaller cells by themselves.

Keep the index contract explicit

Rydo’s small implementation needs three responsibilities. The grid planner is code inside dispatch, not a separate service.

The cell index can begin as a database table:

CREATE TABLE courier_latest (
  courier_id TEXT PRIMARY KEY,
  scheme TEXT NOT NULL,
  resolution SMALLINT NOT NULL,
  cell_id TEXT NOT NULL,
  latitude DOUBLE PRECISION NOT NULL
    CHECK (latitude BETWEEN -90 AND 90),
  longitude DOUBLE PRECISION NOT NULL
    CHECK (longitude BETWEEN -180 AND 180),
  position_version BIGINT NOT NULL,
  received_at TIMESTAMPTZ NOT NULL
);

CREATE INDEX courier_cell_lookup
  ON courier_latest (scheme, resolution, cell_id);

The primary key gives each courier one current row. The secondary index serves “couriers in these cells”. The indexes lesson explains the database mechanism.

The write path is:

1. Authenticate the reporting courier and validate the coordinates.
2. Encode the point using the configured scheme and resolution.
3. Update coordinates, cell ID and timestamp together.
4. Reject an older position version rather than moving the courier backwards.

Assume versions increase within an authenticated reporting session. A new session needs a server-recognized generation; a phone counter alone is not enough.

The read path is:

1. Construct a conservative covering at the stored resolution.
2. Fetch rows matching its cell IDs.
3. Reject stale positions using the configured freshness rule.
4. Test distance using each remaining row’s coordinates.
5. Return candidates to dispatch, which separately checks availability.

A failed bucket read is not an empty bucket. Returning partial results as complete could leave a waiting rider unmatched.

Implement the final filtering step

The query processor owns this function. It accepts already-retrieved buckets and a distance predicate.

The predicate keeps geographic distance calculation outside this example. Production supplies a tested geographic implementation; the grid does not supply that guarantee.

from collections.abc import Callable, Mapping, Sequence
from dataclasses import dataclass

@dataclass(frozen=True)
class Courier:
    id: str
    latitude: float
    longitude: float
    received_at: float

def filter_candidates(
    buckets: Mapping[str, Sequence[Courier]],
    covered_cells: Sequence[str],
    cutoff: float,
    within_radius: Callable[[float, float], bool],
) -> list[str]:
    matches: set[str] = set()
    for cell in set(covered_cells):
        for courier in buckets.get(cell, ()):
            if courier.received_at < cutoff:
                continue
            if within_radius(courier.latitude, courier.longitude):
                matches.add(courier.id)
    return sorted(matches)

type Courier = Readonly<{
  id: string;
  latitude: number;
  longitude: number;
  receivedAt: number;
}>;

function filterCandidates(
  buckets: ReadonlyMap<string, readonly Courier[]>,
  coveredCells: readonly string[],
  cutoff: number,
  withinRadius: (latitude: number, longitude: number) => boolean,
): string[] {
  const matches = new Set<string>();
  for (const cell of new Set(coveredCells)) {
    for (const courier of buckets.get(cell) ?? []) {
      if (courier.receivedAt < cutoff) continue;
      if (withinRadius(courier.latitude, courier.longitude)) {
        matches.add(courier.id);
      }
    }
  }
  return [...matches].sort();
}

Here, an absent map entry means a successfully read, empty bucket. The retrieval layer must raise dependency failures before calling this function.

The set prevents duplicate output IDs. It cannot repair missing coverage, stale records or conflicting location versions.

That boundary is important: a correct filter cannot recover a courier the index never returned.

Production failures test the contract

Use Rydo’s established four-second location reporting interval. For an illustrative fleet of 8,000 online couriers, that creates 2,000 position writes per second.

That is the incoming workload, not a database capacity claim. Measure index-update cost as well as query latency.

A courier crosses a boundary. With the table design, one row update changes coordinates and cell membership together. If cells become separate distributed buckets, moving between them needs an explicit consistency policy. Otherwise, dispatch may briefly miss the courier or see two versions.

A phone stops reporting. Cell membership alone keeps the courier discoverable forever. A freshness cutoff removes old positions. Monitor the share of rejected positions to distinguish poor connectivity from an empty neighbourhood.

One district becomes crowded. Smaller cells may reduce false positives, but cannot eliminate couriers genuinely inside the radius. Monitor candidates per query and rows per cell. A large result is not always an indexing failure.

The index times out. Record the dependency error and return a retryable search failure. Do not tell the rider that no couriers exist. Recovery uses bounded retries or an explicitly designed fallback.

A new resolution is deployed. Readers must not switch before the new index is populated. Build it alongside the old one, compare results, then switch. Keep the old reader available during rollback.

Test points on opposite sides of cell edges, near vertices and around global seams. Compare indexed answers with a full coordinate scan over the same frozen dataset. This checks coverage independently from traffic timing.

Common mistakes

• Using one neighbour ring for every radius. Grid steps are not a universal distance budget.
• Treating cell IDs as distances. Identifier order is not a radius predicate.
• Comparing raw counts as density. Density divides count by measured cell area.
• Confusing discovery with reservation. Finding a courier does not prevent another request from assigning them.

Where this shows up

• Design: a nearby restaurants service uses cells to retrieve places before applying geographic and product filters.
• Design: ride matching like Uber separates nearby-candidate discovery from assigning a driver.

The grid contract is now explicit; the next lesson asks how Redis can serve these location queries with low latency.

Check your understanding

Summary