Geospatial and Time-Series Data Questions

Direct answer

Keep the live "where is every available driver" state in memory, sharded by city, in a structure that answers radius queries directly: a geohash-keyed sorted set (Redis GEO) is the pragmatic choice. GPS pings flow through a partitioned log (Kafka) into a location service that overwrites each driver's single latest position, so the index size tracks online drivers, not ping history. A rider request does one radius query for the nearest 20 or so available drivers, filters out anyone whose last ping is too old, and re-ranks the short list by estimated time of arrival (ETA). If the index is stale or down, fall back in steps: widen the radius and the staleness tolerance, then query a coarser, slower copy of recent positions, and only then fail the request with a clear retry.

Requirements and load (inputs stated, arithmetic shown)

Assumptions for a large multi-city service: 500,000 drivers online at peak, one ping every 4 seconds, the biggest city holding 60,000 of them, 2,000 ride requests per second at peak across all cities, and a matching budget of well under a second (target: the proximity lookup under 20 ms at p99, the 99th-percentile latency).

So the index is write-heavy (125,000 writes against 2,000 reads per second) and small (one entry per online driver). Storage of history is a separate, append-only concern.

Architecture

flowchart LR
  D[Driver app] -->|ping every 4 s| G[Ingest gateway]
  G --> K[(Kafka topic partitioned by city)]
  K --> L[Location service]
  L --> R[(In-memory geo index per city)]
  L --> S[(Driver state: status and last seen)]
  K --> W[(Cold store for analytics)]
  Q[Rider request] --> M[Matching service]
  M --> R
  M --> S
  M --> E[ETA service]

Why a log in the middle. Kafka (a durable, partitioned, append-only message log) absorbs bursts, lets the location service restart and resume from its last offset (the position number of the next unread message in its partition; storing just that number, not the pings themselves, is what makes a restart cheap), and lets analytics consume (read) the same pings without touching the hot path. Kafka splits a topic into partitions (independent, ordered logs); partitioning by city keeps each city's writes on one partition, read by one consumer (a process reading a partition in order), so a driver's pings stay in order.

Representing and indexing driver locations

How Redis GEO works. A Redis sorted set keeps members ordered by a numeric score. GEOADD encodes longitude/latitude into a 52-bit geohash (an interleaving of latitude and longitude bits, so nearby points usually share leading bits) and uses it as the score. GEOSEARCH ... BYRADIUS scans the few score ranges covering the circle and then checks exact distance. Re-adding a member overwrites its position, which is exactly the "latest position only" semantics needed. Run against Redis 7 (redis-cli output, with each result's nested reply compacted onto one line):

> GEOADD drivers:available -97.7431 30.2672 d1 -97.7400 30.2700 d2 -97.7000 30.3000 d3 -97.9000 30.1000 d4
(integer) 4
> GEOSEARCH drivers:available FROMLONLAT -97.7420 30.2680 BYRADIUS 3 km ASC COUNT 10 WITHDIST
1) 1) "d1"  2) "0.1381"
2) 1) "d2"  2) "0.2939"
> GEOADD drivers:available -97.7419 30.2681 d4
(integer) 0
> GEOSEARCH drivers:available FROMLONLAT -97.7420 30.2680 BYRADIUS 3 km ASC COUNT 10 WITHDIST
1) 1) "d4"  2) "0.0148"
2) 1) "d1"  2) "0.1381"
3) 1) "d2"  2) "0.2939"

d3 (about 5 km away) is excluded. The second GEOADD returned 0 because d4 already existed: its position was updated in place and it now ranks first.

Committed layout, per city:

• drivers:available:{city}: the geo set holding only drivers who can take a ride right now. Available-only membership means a query never wastes its COUNT on busy drivers.
• drivers:lastseen:{city}: a sorted set scored by last ping time, used to evict drivers whose app went silent.
• driver:{id}: a hash with status, vehicle type and the ping's own timestamp.
• Status changes (driver accepts a trip, goes offline) remove the driver from the available set and update the hash in one atomic step (a MULTI transaction: Redis's way of running several commands as one all-or-nothing batch, or a small Lua script: a short program Redis runs server-side in a single atomic step instead of several separate round trips), so a busy driver is never offered.

Why not the alternatives. A PostGIS table with a GiST index answers the same query well, but PostgreSQL never updates a row in place: an UPDATE writes a brand-new copy of the row and marks the old copy a dead row version, left for a background process called vacuum to reclaim later. So 15,000 row updates per second in one city means 15,000 dead row versions and 15,000 index entries per second for vacuum to clean up, for data that is worthless 30 seconds later; vacuum falling behind that rate bloats the table and slows every query on it. An in-process grid (hash map from cell ID to driver set) is the fastest option and is what very large operators build eventually, but it means writing your own replication and sharding. Redis is the middle: in-memory, replicated, with the radius query built in.

Keeping the index fresh under heavy ping volume

1. Overwrite, never append: one member per driver, so memory is bounded by online drivers.
2. Coalesce: if the consumer falls behind, apply only the newest ping per driver from each batch (use a pipeline of GEOADD calls: send many Redis commands back to back without waiting for each individual reply, so one network round trip carries the whole batch). Applying 5 old pings for the same driver is pure waste.
3. Drop out-of-order pings: compare the ping's device timestamp with the stored one; ignore older ones so a delayed retry cannot move a driver backwards.
4. Evict the silent: every few seconds, ZRANGEBYSCORE drivers:lastseen:{city} -inf (now - 30s) and remove those drivers from the available set: this reads every member scored from negative infinity up to, but not including (the leading (), "now minus 30 seconds", which is exactly the drivers whose last ping is more than 30 seconds old. Sorted-set members have no per-member expiry, so this sweep is required.
5. Check age at read time too: the matcher drops any candidate whose last ping is older than, say, 15 seconds, so a sweep that lags does not produce ghost offers.
6. Watch consumer lag: the gap, in seconds, between the newest message at the head of the Kafka partition (the most recently written offset) and the offset the location service has actually processed. Track it as the freshness SLO (service-level objective), for example 99% of pings applied within 2 seconds.

Serving a request

1. GEOSEARCH radius 3 km, ASC COUNT 20 WITHDIST on the rider's city set.
2. Drop stale or ineligible candidates (wrong vehicle type, rating filters).
3. Straight-line distance is a poor proxy across rivers and one-way grids, so send the short list to the ETA service and rank by estimated pickup time.
4. If fewer than 3 candidates survive, retry with 6 km, then 10 km.
5. Offer to the best candidate with a short reservation (a lock with an expiry on that driver) so two riders cannot both be matched to the same driver.

Fallbacks when the index is stale or unavailable

The key property is that the index is rebuildable: it is a cache of the last 4 seconds of pings, so recovery is "wait one ping interval", not "restore a backup".

Trade-offs and pitfalls

• Hot cities and events: a stadium letting out concentrates demand into a few cells. Sharding by city handles steady load; a single dense city may need splitting by geohash prefix.
• Memory is not the constraint: 60,000 members per city is a small sorted set. Write rate per shard is the real limit, which is why the city split and coalescing matter.
• Ping rate is a cost lever: halving the interval to 2 seconds doubles writes to 250,000 per second and only reduces the staleness from 60 m to 30 m. Adaptive rates (faster while en route to a pickup, slower while idle) usually beat a global increase.
• What would change the design: if matching needed road-network proximity for every candidate across a very dense city, an in-process grid co-located with the ETA engine would replace the network hop to Redis.

Direct answer

Grid systems such as H3, S2 and quadtrees (each defined just below) turn "search the map" into "look up a few cell IDs". Every GPS point is converted to the ID of the cell that contains it at a chosen resolution. A nearby-drivers query then reads the rider's cell and its neighbours, and a heatmap is a GROUP BY cell_id. Exact distance or road ETA (estimated time of arrival) is computed only on that small candidate set. My default for a ride-hailing routing and ETA stack is H3 for dispatch candidate search and heatmap aggregation, with the resolution chosen by driver density (fine cells downtown, coarse cells on highways). I would add S2 for polygon work (airport zones, city boundaries) and key highway speed and ETA features by road segment rather than by cell.

What each scheme is

• Geohash (the familiar baseline): interleaves longitude and latitude bits and writes them as a base-32 string. Nearby points often share a prefix, so a prefix scan finds them. Cells are rectangles that get narrower towards the poles.
• H3 (Uber's open-source index): covers the globe with hexagons at 16 resolutions (0 to 15). Each step down divides a cell into 7 smaller ones (the "aperture"), and each cell has a 64-bit ID. To tile a sphere, exactly 12 cells per resolution must be pentagons; the grid is oriented so they sit in the ocean.
• S2 (Google's library): projects the Earth onto the 6 faces of a cube and splits each face recursively into 4 squares, down to level 30. Cells are ordered along a Hilbert curve (a space-filling curve that keeps nearby cells close in the 1-D ordering), so a region becomes a few contiguous ID ranges, which suits range scans (reading every row whose key falls between two bounds in one sequential sweep, cheap in a store that keeps its keys sorted) in a sorted key-value store: the fewer separate ranges a region needs, the fewer sweeps a query costs.
• Quadtree: a tree where each node covers a rectangle and splits into 4 children only when it holds too many points. Unlike the fixed grids above, its cell size ADAPTS to density: tiny cells downtown, huge cells in the desert.

Resolution trade-offs (numbers)

The script below prints the real H3 figures and derives S2 and geohash sizes from their definitions: S2 average area is Earth's area / (6 × 4^level); a geohash of length L holds 5L bits split between longitude and latitude. Requires pip install h3 (version 4 API).

import math
import h3

print("h3", h3.__version__)
print("res  avg_area_km2  avg_edge_km  cells_on_earth")
for res in (6, 7, 8, 9, 10):
    print(f"{res:3d}  {h3.average_hexagon_area(res, unit='km^2'):12.4f}  {h3.average_hexagon_edge_length(res, unit='km'):11.4f}  {h3.get_num_cells(res):,}")

# Google S2: 6 faces, each level splits a cell into 4, so average area = Earth area / (6 * 4^level)
earth_km2 = 4 * math.pi * 6371.0088 ** 2
for level in (12, 13, 14, 15):
    print(f"S2 level {level}: avg area {earth_km2 / (6 * 4 ** level):.4f} km2")

# Geohash: each char = 5 bits, alternating lon/lat starting with lon
for length in (5, 6, 7):
    bits = 5 * length
    lon_bits, lat_bits = (bits + 1) // 2, bits // 2
    w = 360 / 2 ** lon_bits * 111.195  # km per degree at equator
    h = 180 / 2 ** lat_bits * 111.195
    print(f"geohash len {length}: {w:.3f} km wide x {h:.3f} km tall at the equator")

# Neighbour geometry: hex neighbours are all one step away, squares have edge and corner neighbours
cell = h3.latlng_to_cell(37.7749, -122.4194, 9)
ring1 = h3.grid_ring(cell, 1)
c0 = h3.cell_to_latlng(cell)
dists = sorted(round(h3.great_circle_distance(c0, h3.cell_to_latlng(n), unit='m')) for n in ring1)
print("res 9 cell", cell, "ring-1 neighbours:", len(ring1), "center distances m:", dists)
print("grid_disk sizes k=1,2,3:", [len(h3.grid_disk(cell, k)) for k in (1, 2, 3)])
print("pentagons per resolution:", len(h3.get_pentagons(9)))
parent = h3.cell_to_parent(cell, 8)
kids = h3.cell_to_children(parent, 9)
print("children per parent:", len(kids), "| our cell among them:", cell in kids)

Output:

h3 4.5.0
res  avg_area_km2  avg_edge_km  cells_on_earth
  6       36.1291       3.7245  14,117,882
  7        5.1613       1.4065  98,825,162
  8        0.7373       0.5314  691,776,122
  9        0.1053       0.2008  4,842,432,842
 10        0.0150       0.0759  33,897,029,882
S2 level 12: avg area 5.0670 km2
S2 level 13: avg area 1.2668 km2
S2 level 14: avg area 0.3167 km2
S2 level 15: avg area 0.0792 km2
geohash len 5: 4.886 km wide x 4.886 km tall at the equator
geohash len 6: 1.222 km wide x 0.611 km tall at the equator
geohash len 7: 0.153 km wide x 0.153 km tall at the equator
res 9 cell 89283082803ffff ring-1 neighbours: 6 center distances m: [348, 348, 355, 355, 364, 364]
grid_disk sizes k=1,2,3: [7, 19, 37]
pentagons per resolution: 12
children per parent: 7 | our cell among them: True

What this means in practice:

• Too fine (H3 res 10, about 0.015 km² per cell): most cells hold zero or one driver, counts are noisy, and a proximity search must visit many cells.
• Too coarse (res 6, about 36 km²): a single cell returns hundreds of candidates to rank, and a heatmap blurs a stadium exit into the whole district.
• Comparable sizes: H3 res 7 ≈ S2 level 12 (about 5 km² each) and H3 res 8 ≈ geohash length 6 at the equator (1.222 × 0.611 ≈ 0.75 km² vs 0.74 km²), which helps when migrating between schemes.

Neighbour adjacency: why it matters for routing

The printed res-9 check shows all 6 neighbours of a San Francisco cell have centres 348 to 364 m away. With squares, the 4 edge neighbours sit at distance 1 and the 4 corner neighbours at √2 ≈ 1.41 (41% farther), so "one ring out" is lopsided. That uniformity matters for:

• Expanding search: grid_disk(cell, k) (all cells within k steps, 3k² + 3k + 1 of them: 7, 19, 37 as printed) grows as a near-circle.
• Smoothing (spreading demand into neighbouring cells so one noisy cell does not stand out) and diffusion (modelling supply, such as idle drivers, as gradually spreading into neighbouring cells over time, the way heat spreads through a material, useful for forecasting where drivers will be a few minutes from now): both treat every neighbour alike.
• Geohash's boundary trap: two points 10 m apart on opposite sides of a major cell boundary (for example the equator or the prime meridian) can share no prefix at all, so a prefix-only search misses them. You must compute the 8 neighbour cells explicitly.

Two H3 caveats: children only approximately fill their parent (aperture 7 hexagons cannot nest exactly), so rolling up counts should go point to parent directly rather than summing child cells when exact boundaries matter. And code that assumes every cell has 6 neighbours will be wrong at the 12 pentagons; the library's grid_disk handles them.

Use case 1: nearest drivers

1. On every driver ping, write driver_id → cell_id at the dispatch resolution, and keep cell_id → set of available drivers.
2. For a ride request, compute the rider's cell and read grid_disk(cell, k). Always use k ≥ 1: a rider 20 m from a cell edge has their nearest driver in the next cell as often as in their own, because drivers scatter around the city without any regard for where the grid's lines happen to fall, so a boundary that sits 20 m from the rider splits their immediate surroundings roughly in half; on average about as many of the closest few drivers land just across that line as land on the rider's own side.
3. If the disk returns fewer than the needed number of candidates, increase k (or drop to a coarser resolution) and retry.
4. Compute exact straight-line distance on the candidates, keep the closest 20 to 50, then rank those by road-network ETA from the routing engine. The grid only decides who is worth asking about.

Use case 2: heatmap and surge aggregation

Bucket ride requests and available drivers per cell per minute, then compute a demand/supply ratio per cell to drive pricing (raising the price when a cell has many requests and few available drivers, commonly called surge pricing) or repositioning suggestions (nudging idle drivers toward under-supplied cells before demand actually arrives there). Hexagons suit this because their near-equal area makes cell counts comparable, and neighbour smoothing (averaging a cell with its ring) reduces noise from tiny counts. Store at a fine resolution and roll up to parents for city-level dashboards. Areas are near-equal, not identical, so when comparing density across distant regions divide by each cell's actual area.

Picking a scheme: urban vs highway

The rule I use: for a given resolution, grow k from 0 and stop at the smallest k whose disk is expected to hold about 10 or more available drivers, then compare that outcome across a few candidate resolutions and pick whichever keeps both k and the cell count reasonable. Because k only takes whole-number steps, the two results below do not land on exactly 10: downtown, res 9 needs k = 1 (k = 0 alone gives only about 3.5 drivers, short of 10; k = 1 jumps straight to about 25), and a coarser resolution would already overshoot 10 at k = 0. The script computes, for two densities and a few resolutions, the smallest ring that reaches the target, so the resolution/k trade-off is visible instead of assumed.

import h3

def ring_needed(drivers_per_km2, want=10, res=9):
    area = h3.average_hexagon_area(res, unit="km^2")
    k = 0
    while (3 * k * k + 3 * k + 1) * area * drivers_per_km2 < want:  # grid_disk(k) holds 3k^2+3k+1 cells
        k += 1
    cells = 3 * k * k + 3 * k + 1
    return k, cells, cells * area * drivers_per_km2

for label, density in (("dense downtown, 2000 drivers / 60 km2", 2000 / 60),
                       ("highway corridor, 40 drivers / 1600 km2", 40 / 1600)):
    for res in (9, 8, 7):
        k, cells, expected = ring_needed(density, want=10, res=res)
        print(f"{label:42s} res {res}: k={k:3d}, cells={cells:5d}, expected drivers={expected:6.1f}")

Output:

dense downtown, 2000 drivers / 60 km2      res 9: k=  1, cells=    7, expected drivers=  24.6
dense downtown, 2000 drivers / 60 km2      res 8: k=  0, cells=    1, expected drivers=  24.6
dense downtown, 2000 drivers / 60 km2      res 7: k=  0, cells=    1, expected drivers= 172.0
highway corridor, 40 drivers / 1600 km2    res 9: k= 36, cells= 3997, expected drivers=  10.5
highway corridor, 40 drivers / 1600 km2    res 8: k= 13, cells=  547, expected drivers=  10.1
highway corridor, 40 drivers / 1600 km2    res 7: k=  5, cells=   91, expected drivers=  11.7

• Urban core (about 33 drivers per km²): H3 res 9 with k = 1 visits 7 cells and expects about 25 drivers. Res 8 reaches the same count in a single cell, but that is k = 0 and misses nearby drivers across the cell edge; res 8 with k = 1 would return about 172, which is wasteful to rank. Res 9 (average edge length about 200 m) also resolves block-level hotspots for the heatmap.
• Highway or rural corridor (about 0.025 drivers per km²): res 9 would need k = 36, which is 3,997 cell lookups per request. Res 7 reaches the target with k = 5 (91 cells). In practice either store both resolutions, or pick the resolution per zone from its measured density.
• Highway ETA features belong on road segments, not cells. A hexagon that straddles a motorway also contains the frontage road beside it, so "average speed in this cell" mixes traffic doing 100 km/h with traffic doing 30 km/h. Use map matching (snapping GPS traces onto the road graph) and aggregate speed by road segment and direction per time bucket. Cells stay useful for coarse, area-level signals such as regional demand.
• When S2 or a quadtree wins instead: S2's region coverer (an algorithm that picks a small set of cells, at a mix of levels, whose union approximates an arbitrary shape within a chosen size or precision budget) can approximate a buffered highway polyline (the highway's route line expanded outward by a fixed distance into a thin polygon, the shape you would cover to mean "near this highway") or an airport pickup zone with a mix of cell levels (fine where the shape is narrow, coarse where it is wide), with exact parent-child containment, and its Hilbert ordering gives a few range scans in a sorted key-value store. A quadtree wins for an in-memory index where density varies by orders of magnitude, because it splits only where points are, at the cost of irregular neighbours and rebalancing (the tree having to split or merge nodes as point density shifts, unlike H3 or S2, whose cell boundaries stay fixed no matter how the underlying points move) as drivers move.

Trade-offs and pitfalls

• Choosing one resolution for the whole planet. Density varies by more than 1,000 times between the two example zones above; a single fixed resolution is wrong for one of them.
• Stopping at the cell. Returning "all drivers in my cell" without the neighbour ring or exact distance gives visibly wrong matches at cell edges.
• Treating cell adjacency as road adjacency. Two adjacent cells can be on opposite banks of a river; only the road graph knows travel time.
• Heatmaps at too fine a resolution. Counts of 0, 1 or 2 per cell per minute swing wildly; aggregate over a longer window, smooth with neighbours, or coarsen.
• Pinning to library versions. H3 renamed most functions between v3 and v4 (for example k_ring became grid_disk); pin the version in services that share cell IDs, although the IDs themselves are the same across versions.

Direct answer

All three turn a latitude/longitude into a cell ID so "who is near this rider" becomes "who is in these cells". Geohash cuts the latitude/longitude rectangle in half again and again and interleaves the bits into a base-32 string (each character packs 5 bits, using digits and lowercase letters); it is simple and works as a prefix in any sorted key-value store (a database that keeps its keys in sorted order, so a shared prefix or a range of keys can be fetched in one query), but its cells are rectangles whose size and shape change with latitude, and nearby points can share no prefix. S2 projects the Earth onto a cube and subdivides each face as a quadtree (a tree where each square node splits into four smaller quadrant children, repeated at each level), giving 64-bit IDs ordered along a Hilbert curve with roughly square cells and no special cases at the poles or the 180 degree meridian. H3 tiles the sphere with hexagons whose six neighbours are all the same distance away, which makes rings of neighbours, smoothing (averaging a noisy value, such as demand, across nearby cells so a single cell's spike doesn't dominate) and zone-based pricing clean, at the price of imperfect parent/child nesting and 12 pentagons per resolution (a sphere cannot be tiled with hexagons alone; H3 starts from an icosahedron, a 20-triangle-faced solid, and one pentagon appears near each of its 12 vertices at every resolution, however many times the faces are subdivided). For a real-time ride-matching index I would pick H3 (or S2) over geohash, keeping geohash where the storage layer only offers string or prefix range scans.

Terms used

• Cell: one tile of the grid; every point on Earth falls into exactly one cell at a given resolution.
• Resolution / level / precision: how finely the grid is cut. Higher means smaller cells.
• Space-filling curve: a path that visits every cell once, so 2-D cells can be stored in a 1-D sorted order. Geohash uses a Z-order curve, also called a Morton curve after its inventor; S2 uses a Hilbert curve, which has fewer long jumps.
• Neighbour expansion: finding the cells around a given cell so a radius query does not miss a driver just across a cell edge.
• Antimeridian: the 180 degree longitude line, where longitude jumps from +180 to -180.
• RegionCoverer: an S2 library function that, given a shape such as a circle, returns a small set of cells (of mixed sizes) whose union covers it.

How each supports spatial queries

Neighbour expansion in practice. A rider's own cell is never enough, because a rider near a cell edge has drivers a few metres away in the next cell. Geohash: choose a precision whose cell is at least as large as the search radius in both directions, then query the cell and its 8 neighbours. S2: ask a region coverer for, say, at most 8 cells that cover the circle; it mixes big cells in the middle with small ones at the edge. H3: pick a resolution (resolution 9 hexagons average 0.105 km² with 201 m edges) and take grid_disk(k), where k is the radius divided by the centre-to-centre spacing between adjacent hexagons (edge length x sqrt(3), about 348 m for resolution 9's 201 m edge), rounded up. In every case the cells only produce candidates; an exact distance check then filters them.

Trade-offs on the four axes

Query granularity. Geohash sizes jump by a factor of 32 per character (alternately 4x8 and 8x4 splits), so you often choose between a cell that is too big and one that is too small. S2 levels change area by 4x and H3 resolutions by about 7x, both finer steps. Geohash cells also stretch: at 60 degrees latitude a cell is half as wide in metres as at the equator. S2 cell areas at one level vary by about 2x (level 12 spans 3.04 to 6.38 km²); H3 hexagons vary less and are more uniform in shape, which matters when cells are used as pricing or supply zones.

Edge cases (antimeridian and poles). Geohash is defined on the lat/lon rectangle, so a cell at longitude 179.999 and one at -179.999 are neighbours on Earth but have unrelated strings; neighbour code must wrap longitude explicitly. Near the poles geohash cells become thin slivers and the top row has no northern neighbour. S2 and H3 are built on the sphere (cube and icosahedron projections), so neither the antimeridian nor the poles need special cases. H3's special case is different: the 12 pentagons have 5 neighbours, and a few grid operations (for example grid distance between cells) can return an error when the path crosses a pentagon's distorted area, so code must handle that error. They sit mostly in oceans, so ride matching rarely meets one, but "rarely" is not "never".

Index size. Geohash at 7 characters is 7 bytes as text (often stored as an 8-byte integer); S2 and H3 IDs are 8-byte integers. For 1M online drivers the ID column is about 8 MB either way. The real memory is the index structure: a hash map from cell to a set of driver IDs, sized by drivers, not by the encoding.

Update cost for moving drivers. Computing a cell ID is a small constant amount of work for all three. The expensive part is moving the driver between cell sets, which happens only on a boundary crossing. Estimate: for a vehicle crossing a convex cell along a random straight line, the average path length inside it is about pi x area / perimeter. This is a standard result from geometric probability (the same relationship used to compute a particle's mean free path through a convex container): average over every straight line that crosses the cell, in every direction and every offset, and the mean chord length works out to pi times the cell's area divided by its perimeter. For an H3 resolution 9 hexagon with a 200.8 m edge that is about 273 m; for a geohash precision 7 cell at San Francisco's latitude (about 153 m x 121 m) it is about 106 m. At 10 m/s (36 km/h), 100,000 moving drivers cause about 100,000 x 10 / 273, or 3,700 index moves per second with H3, versus 100,000 x 10 / 106, or 9,400 with geohash. This is an estimate that assumes straight-line motion; with location pings every 4 seconds the raw ping rate is 25,000 per second either way, and the index writes are the fraction of pings that change cell.

When to choose which

• Geohash: the store only supports string keys and prefix or range scans (Redis, an in-memory data store, has GEO commands that use a 52-bit geohash as the score in a sorted set, a data structure that keeps its members ordered by a score so a range of them can be fetched quickly; Elasticsearch has geohash grid aggregations), traffic is regional and away from the antimeridian, and simplicity wins.
• S2: you need exact hierarchy and covering of arbitrary regions (a polygonal airport zone or city boundary) with integer range scans, for example in a sorted key-value store.
• H3: matching, surge pricing (raising the price shown to riders in a zone when demand there outstrips available drivers) and supply/demand analytics on equal-sized, equal-neighbour zones; ring searches (grid_disk) for "expand the search if no driver answers"; aggregation by zone in dashboards.

For a new ride-matching system I would use H3 resolution 9 for the live driver index and for pricing zones, run a grid_disk expansion (k = 1, then 2, 3) until enough candidates appear, and filter candidates by road travel-time estimate, not by straight distance.

Pitfalls

• Treating a shared prefix as "nearby" (or a different prefix as "far"): both are wrong at cell edges.
• Forgetting that H3 parents do not exactly contain their children, then summing child counts into a parent and expecting exact totals.
• Picking the resolution by habit instead of from the search radius and driver density: too fine means many cells per query, too coarse means many false candidates.

Direct answer

Split the system into two paths that each meet one requirement well. Ingest goes through Kafka into a columnar, log-structured store (ClickHouse's MergeTree family is the concrete choice), sorted by (sensor_id, ts) and partitioned by day, so writes are large sequential appends. Queries go through a router that picks the coarsest pre-aggregated tier that still answers the question: raw rows for one sensor, 1-minute rollups for a few hours across many sensors, 1-hour rollups for fleet-wide 30-day windows. Sub-second 30-day aggregation is only possible because no query ever scans 30 days of raw points; the arithmetic below shows why.

The numbers that drive the design

Assume 10 million sensors reporting every 10 seconds (10 M / 10 s = 1 M points/s) grouped into 10,000 sites. Then:

• One sensor, 30 days, raw: 30 × 86,400 / 10 = 259,200 points. Sorted by (sensor_id, ts), that is one contiguous range: sub-second on raw data.
• Fleet-wide, 30 days, raw: 2.59 trillion points. No engine scans that in under a second. Needs rollups.
• Per-site 1-minute rollup, 30 days: 10,000 × 43,200 = 432 million rows. Seconds, not sub-second.
• Per-site 1-hour rollup, 30 days: 10,000 × 720 = 7.2 million rows. Comfortably sub-second.

Storage engine class: TSDB vs LSM tree

An LSM tree (log-structured merge tree: writes go to an in-memory table, are flushed as sorted immutable files called SSTables, and are merged in the background) is what Cassandra, RocksDB and ClickHouse's MergeTree share in spirit. A purpose-built metrics TSDB (time-series database, Prometheus-style) also keeps a mutable in-memory head and immutable blocks, but its index is an inverted index over labels and its unit of storage is a compressed chunk per series.

A few terms from that table: a memtable is the in-memory sorted table that buffers recent writes before they are flushed to disk, the LSM equivalent of a per-series open chunk. Vectorised execution processes many rows at once per CPU instruction instead of one row at a time, which is what makes arbitrary SQL aggregations fast in a columnar engine. A window join combines or aggregates rows that fall within a shared sliding time window of each other, for example "pair each order with any refund in the next 24 hours." Concretely, "average temperature per site over the last hour" reads one compressed chunk per series in a metrics TSDB, one per-key row range in a generic LSM store (with no native GROUP BY, so the aggregation happens in application code), and a single vectorised SELECT avg(value) ... GROUP BY site_id scan over the relevant parts in the columnar MergeTree, which is why the SQL-shaped question favors the last one.

For sensor analytics with SQL-shaped questions ("average temperature per site over a sliding 30 days"), I pick the columnar MergeTree. I would flip to a metrics TSDB if the workload were mostly alerting on per-series thresholds with PromQL (Prometheus's query language).

Partitioning

• Partition key: toDate(ts) (one partition per day). Retention and tiering then act on whole partitions, and a 30-day query touches 30 partitions.
• Sort key: ORDER BY (sensor_id, ts). Points for one sensor sit together, which serves per-sensor queries and makes the delta codecs effective.
• Sharding across nodes: hash sensor_id across shards, each shard replicated twice. A fleet-wide query fans out to every shard in parallel; a per-sensor query hits one shard.

Write batching, coalescing and backpressure

• Batching: every insert creates a new on-disk part, and many tiny parts cause a "too many parts" error and a merge storm (background merge jobs pile up faster than they can finish, competing for the same disk and CPU that ingestion needs). Gateways coalesce points into batches of tens of thousands of rows or a 1-second deadline, whichever comes first (ClickHouse can also batch server-side with async_insert=1).
• Coalescing: duplicate readings from retrying sensors are collapsed by (sensor_id, ts) at the gateway, or by a ReplacingMergeTree that keeps one row per key at merge time.
• Backpressure mechanism, end to end: backpressure means the system pushing back on producers that are sending faster than it can absorb, rather than silently falling over or dropping data unannounced. Sensors buffer locally; gateways accept writes into bounded in-memory queues and return 429 (retry later) when the queue is full, so devices back off with jitter. Kafka absorbs longer stalls: at an assumed 40 B/point on the wire, 1 M points/s is 40 MB/s, so 12 hours of topic retention is about 1.7 TB per replica. Inserter consumers only commit Kafka offsets after the database acknowledges a batch, which gives at-least-once delivery (duplicates possible, loss not), and the coalescing step removes the duplicates.

Compression

Columnar storage lets each column use its own codec. DoubleDelta stores each timestamp as the change in the gap since the previous one (a "delta of a delta"): at a steady 10-second interval that difference is 0 almost every time, and a 0 costs a single bit, so ts compresses to nearly nothing. Gorilla (the encoding from Facebook's Gorilla time-series database) stores each value as the bits that differ from the previous value via XOR; a slowly changing reading shares most of its bits with the last one, so only a small run of bits needs storing. Delta simply stores the plain difference from the previous value: cheaper than Gorilla when values move in small, regular steps, less effective when they jump around. Low-cardinality dictionary encoding replaces a column with few distinct values, such as site_id, with small integer codes plus a lookup table. On top of these, ZSTD and LZ4 are general-purpose compressors: ZSTD compresses harder (smaller output, more CPU), LZ4 is faster with a lower ratio. Use your own data to measure bytes per point; the 1.5 to 3 B range above is a planning assumption, not a promise.

Indexing

• The sort key gives a sparse primary index: instead of indexing every row, ClickHouse stores one lookup entry per 8,192-row block (a granule, its default read unit) pointing at where that block starts on disk. Over the full 2-year raw dataset (63.1 trillion rows from the table above), that is about 63.1e12 / 8,192 ≈ 7.7 billion entries in total, spread across every shard and replica in the cluster rather than held by any single node, which is what makes it fit in memory. A lookup does a binary search over that shard's slice of sparse entries to find the right granule, then scans just that granule's 8,192 rows.
• ts is covered by partition pruning plus min/max stats per part (each part records the smallest and largest ts it holds, so a query can skip whole parts outside its time range without opening them).
• Add a data-skipping index (a secondary index that lets ClickHouse skip whole granules that cannot match a filter, without indexing every row) only for filters outside the sort key, for example a bloom_filter (a compact structure that can quickly say "definitely not present" for a value) on firmware_version when hunting a bad release.

Downsampling and the sliding window

Downsampling means storing data at a coarser resolution than it arrived at, so long-range queries scan far fewer rows. Materialized views (views whose results are precomputed and stored, then kept up to date incrementally as new rows arrive, rather than recomputed from scratch on every query) compute 1-minute and 1-hour rollups on insert, storing mergeable partial aggregates: sum, count, min, max, and a quantile sketch for percentiles (a compact, approximate summary of the distribution that can be combined across time buckets, unlike a single stored percentile number). "Mergeable" is the key property: these five pieces can be recombined into a correct result for any larger window, unlike a stored average or percentile, which cannot. A sliding 30-day average is then sum(sum) / sum(count) over 720 hourly rows per site, plus the partial current hour read from the 1-minute tier, so the window slides without recomputing history.

Query routing

flowchart TD
  Q[Query: range, step, scope] --> R{Router}
  R -->|one sensor, any range| RAW[(Raw table)]
  R -->|many sensors, range under 6h| M1[(1-minute rollups)]
  R -->|many sensors, range 6h to 30d| H1[(1-hour rollups)]
  R -->|older than 30 days| COLD[(Cold tier on object storage)]

Rule: use the coarsest tier whose resolution is at least as fine as the requested step (a chart with 300 pixels across 30 days needs 2.4-hour steps, so hourly data is enough).

Data lifecycle

Pitfalls

• Late-arriving points (a sensor offline for a day) land in old partitions; rollups for those hours must be recomputed, so the materialized views need a correction path.
• A fleet-wide percentile cannot be built from per-site percentiles; only sketches merge correctly.
• Sub-second targets are p99 (99th percentile) targets for the routed query shapes above; state explicitly that a raw fleet-wide 30-day scan is out of contract.

Direct answer

Store (or index) each listing as a geography point, put a partial GiST index on it covering only active listings, and drive the per-search lookup with a LEFT JOIN LATERAL subquery that filters with ST_DWithin(..., 5000) and orders by the <-> distance operator with LIMIT 5. The lateral join runs one small index probe per search instead of comparing every search against every listing. The city percentage is a second aggregation over the per-search result counts. One gap in the stated schema has to be closed first: searches has no city column and no key, so the answer adds a search_id and assigns a city with a point-in-polygon join (a join whose condition is "this point falls inside this polygon", here testing whether a search's coordinate lands inside a city's boundary shape) against a cities boundary table.

Why each piece is there

Key terms.

• A spatial index lets the database skip rows that are nowhere near the query point. PostGIS uses GiST (Generalized Search Tree), which stores a bounding box per row in a tree, so "which boxes overlap this 10 km square" is answered by walking a few tree pages.
• geography vs geometry: geometry treats coordinates as flat x/y, so distances come out in degrees. geography measures on the Earth's surface, so ST_DWithin(a, b, 5000) means 5,000 metres. With raw lat, lon input and a kilometre requirement, geography is the correct type.
• SRID 4326 is the identifier for plain WGS 84 (World Geodetic System 1984) longitude/latitude, the coordinate system GPS reports.
• A lateral join (LATERAL) is a subquery that may reference columns of the rows to its left, so it runs once per search row. That is exactly the "top N per group" shape.
• KNN (k-nearest-neighbour) ordering: ORDER BY a <-> b LIMIT k lets PostGIS return rows nearest-first straight from the index.

Design decisions.

Runnable solution (PostgreSQL 16, PostGIS 3.4)

The script creates the tables, generates deterministic synthetic data with a pinned seed, builds the indexes, runs both queries and checks the plan. Run it with psql -f in a database where PostGIS is installed.

-- Setup: tables as given, plus a surrogate search_id and a city boundary table.
CREATE EXTENSION IF NOT EXISTS postgis;
DROP TABLE IF EXISTS listings, searches, cities;

CREATE TABLE listings (
  listing_id bigint PRIMARY KEY,
  lat double precision NOT NULL,
  lon double precision NOT NULL,
  is_active boolean NOT NULL,
  price_usd numeric(10,2) NOT NULL,
  geog geography(Point,4326)
    GENERATED ALWAYS AS (ST_SetSRID(ST_MakePoint(lon, lat), 4326)::geography) STORED
);
CREATE TABLE searches (
  search_id bigserial PRIMARY KEY,
  lat double precision NOT NULL,
  lon double precision NOT NULL,
  search_time timestamptz NOT NULL
);
CREATE TABLE cities (city text PRIMARY KEY, geom geometry(Polygon,4326) NOT NULL);

-- Deterministic synthetic data (PostgreSQL 16).
SELECT setseed(0.42);
INSERT INTO cities VALUES
 ('Austin', ST_MakeEnvelope(-97.90, 30.15, -97.60, 30.45, 4326)),
 ('Denver', ST_MakeEnvelope(-105.10, 39.60, -104.80, 39.90, 4326));
-- Austin: 3000 listings, Denver: 60 listings, ~80% active.
INSERT INTO listings (listing_id, lat, lon, is_active, price_usd)
SELECT g, 30.15 + random()*0.30, -97.90 + random()*0.30, random() < 0.8, round((50 + random()*450)::numeric, 2)
FROM generate_series(1, 3000) g;
INSERT INTO listings (listing_id, lat, lon, is_active, price_usd)
SELECT g, 39.60 + random()*0.30, -105.10 + random()*0.30, random() < 0.8, round((50 + random()*450)::numeric, 2)
FROM generate_series(3001, 3060) g;
-- 500 searches per city.
INSERT INTO searches (lat, lon, search_time)
SELECT 30.15 + random()*0.30, -97.90 + random()*0.30, timestamptz '2026-01-01' + g * interval '1 minute'
FROM generate_series(1, 500) g;
INSERT INTO searches (lat, lon, search_time)
SELECT 39.60 + random()*0.30, -105.10 + random()*0.30, timestamptz '2026-01-01' + g * interval '1 minute'
FROM generate_series(1, 500) g;

-- Indexes: partial GiST on active listings, GiST on city polygons.
CREATE INDEX listings_active_geog_gix ON listings USING gist (geog) WHERE is_active;
CREATE INDEX cities_geom_gix ON cities USING gist (geom);
ANALYZE listings; ANALYZE searches; ANALYZE cities;

-- Query 1: up to 5 nearest active listings within 5 km, per search.
CREATE TEMP TABLE search_results AS
SELECT s.search_id, s.search_time, COALESCE(c.city, 'unassigned') AS city,
       nn.listing_id, nn.distance_km, nn.price_usd
FROM searches s
CROSS JOIN LATERAL (SELECT ST_SetSRID(ST_MakePoint(s.lon, s.lat), 4326) AS pt) p
LEFT JOIN cities c ON ST_Covers(c.geom, p.pt)
LEFT JOIN LATERAL (
  SELECT l.listing_id, l.price_usd,
         round((ST_Distance(l.geog, p.pt::geography) / 1000.0)::numeric, 3) AS distance_km
  FROM listings l
  WHERE l.is_active
    AND ST_DWithin(l.geog, p.pt::geography, 5000)
  ORDER BY l.geog <-> p.pt::geography
  LIMIT 5
) nn ON true;

SELECT search_id, city, listing_id, distance_km, price_usd
FROM search_results WHERE search_id IN (1, 501)
ORDER BY search_id, distance_km;

-- Query 2: % of searches per city with at least 3 results.
SELECT city,
       count(*) AS searches,
       count(*) FILTER (WHERE n_results >= 3) AS with_3plus,
       round(100.0 * count(*) FILTER (WHERE n_results >= 3) / count(*), 1) AS pct_3plus
FROM (SELECT search_id, city, count(listing_id) AS n_results
      FROM search_results GROUP BY search_id, city) per_search
GROUP BY city ORDER BY city;

-- Plan check for the lateral probe.
EXPLAIN (COSTS OFF)
SELECT l.listing_id FROM listings l
WHERE l.is_active AND ST_DWithin(l.geog, ST_SetSRID(ST_MakePoint(-97.75, 30.30), 4326)::geography, 5000)
ORDER BY l.geog <-> ST_SetSRID(ST_MakePoint(-97.75, 30.30), 4326)::geography
LIMIT 5;

Output of that script (the empty setseed result and the NOTICE lines from the DROP ... IF EXISTS are omitted):

 search_id |  city  | listing_id | distance_km | price_usd
-----------+--------+------------+-------------+-----------
         1 | Austin |       1985 |       0.117 |    311.20
         1 | Austin |        925 |       0.197 |    239.97
         1 | Austin |       1743 |       0.398 |    223.44
         1 | Austin |       2100 |       0.554 |    445.05
         1 | Austin |        267 |       0.627 |    129.20
       501 | Denver |       3034 |       0.776 |    347.95
       501 | Denver |       3041 |       1.057 |    278.69
       501 | Denver |       3010 |       2.690 |    306.64
       501 | Denver |       3036 |       3.902 |    432.48

  city  | searches | with_3plus | pct_3plus
--------+----------+------------+-----------
 Austin |      500 |        500 |     100.0
 Denver |      500 |        373 |      74.6

 Limit
   ->  Sort
         Sort Key: ((geog <-> '...'::geography))
         ->  Bitmap Heap Scan on listings l
               Recheck Cond: is_active
               Filter: st_dwithin(geog, '...'::geography, '5000'::double precision, true)
               ->  Bitmap Index Scan on listings_active_geog_gix
                     Index Cond: (geog && _st_expand('...'::geography, '5000'::double precision))

(The long hex point literals in the plan are abbreviated to '...'.)

Reading the result

• Search 501 in Denver returned only 4 rows, which is correct: only 4 active listings sit within 5 km. The LIMIT 5 is a ceiling, not a guarantee.
• The density difference drives the percentage. Austin has 3,000 listings in a 0.30 by 0.30 degree box, so every Austin search clears 3 results. Denver has only 60 listings in a box of the same size, 46 of them active in this run: spread over that box, which at Denver's latitude works out to about 25.6 km by 33.4 km, roughly 856 km², that is about 0.054 active listings per km². A 5 km search radius is a circle of about pi x 5^2 = 78.5 km², so a search is expected to find about 0.054 x 78.5, roughly 4.2 active listings, close to the 3-result bar the query checks against. With the expected count that close to the bar, whether any one search actually clears it varies a lot from search to search, and 373 of 500 Denver searches do: 373 / 500 = 74.6%.
• Reading the plan, line by line. Bitmap Index Scan on listings_active_geog_gix walks the partial GiST index and builds a bitmap (an in-memory list of candidate row locations) instead of visiting table rows directly; Index Cond: (geog && _st_expand(...)) is the actual index lookup, where _st_expand grows the search point into a bounding box covering the 5,000 m radius and && (PostGIS's "bounding boxes overlap" operator) is the cheap, index-supported test the GiST tree can answer. Bitmap Heap Scan on listings l then visits just those candidate rows in the table's own storage (the heap, as opposed to the index) to check the conditions the bitmap step could only approximate: Recheck Cond: is_active re-checks the real condition against each row once it gets there, because a bitmap only marks which pages might contain a match, and Filter: st_dwithin(...) re-checks the true distance the same way, since the bounding box only proves "close enough to be worth checking", not "actually within 5 km". The Bitmap Index Scan line is what proves the partial index was actually used; the Recheck/Filter lines are why the plan is still correct even though its first pass over the box is approximate.
• The plan confirms the partial index is used: Bitmap Index Scan on listings_active_geog_gix with the && bounding-box condition that ST_DWithin generated. The planner chose a bitmap scan plus a small sort here rather than a pure KNN index walk, because a 5 km radius holds few enough rows that sorting them is cheap. Either plan touches only nearby rows, which is the point.

Complexity

Let S be the number of searches, L the number of active listings and m the listings inside one 5 km radius. Each probe costs roughly O(log L + m log m) (tree descent, then sort the candidates), so the whole query is about O(S (log L + m log m)); with m capped by the LIMIT 5 in practice this stays cheap, but the honest bound keeps the log m term rather than dropping it. The naive cross join is O(S * L): with 1,000 searches and 3,000 listings that is 3,000,000 distance computations, and it grows with both tables.

Edge cases and pitfalls

• Longitude first. ST_MakePoint(x, y) takes (lon, lat). Swapping them puts Austin in Antarctica and the query silently returns nothing.
• Distance units. ST_Distance on geography returns metres (divide by 1,000 for km). On geometry in SRID 4326 it returns degrees, which is meaningless as a distance.
• Sphere vs spheroid. <-> on geography orders by sphere distance while ST_Distance defaults to the more exact spheroid. The two can disagree by a fraction of a percent, which only matters for near-ties in ordering.
• Ties. Add , l.listing_id to the ORDER BY if results must be stable across runs when two listings are equidistant.
• Searches with no city. Counting only INNER JOIN matches hides searches outside the polygon table; the COALESCE(..., 'unassigned') bucket keeps them visible.
• search_time is unused by the spec, but the same pattern takes a time filter trivially (for example restricting to the last 7 days before the lateral step), which is how you would run it incrementally over a large searches table.
• At larger scale, run the lateral step in batches keyed by search_id or by day, and consider physically reordering the table by location so nearby listings share heap pages (the fixed-size blocks of storage that hold a table's actual rows, the "heap"; reading fewer distinct pages means fewer disk or cache reads). CLUSTER (the command that physically rewrites a table's heap in index order) needs a non-partial index, so it would use a separate full GiST index on geog.