In a geohash-indexed nearby-places service, how do you choose the cell precision and scan pattern so a radius query misses no point?

middlemust knowfreq 62%

answer

the user can stand on an edge
centre plus its ring of cells
one full cell past every side
shorter side, at this latitude
scans versus discarded rows

basics

~10 s

Pick the finest precision whose cells are at least as large as the radius on their shorter side, scan the query's cell plus its eight neighbours, then keep only candidates within the exact distance.

solid answer

~50 s

The query point can sit right next to a cell edge, so the search circle spills into adjacent cells; scanning only its own cell misses points just across the line. The standard fix is a 3x3 block: the centre cell plus its eight neighbours, nine prefix range scans. That block reaches at least one full cell beyond the centre cell in every direction, so it covers any circle whose radius is no larger than the cell's shorter side, measured at the query's latitude. So I pick the finest precision that still satisfies that rule, scan the nine cells, and filter candidates by exact great-circle distance before sorting. The trade-off is cell size versus result count: finer cells than the rule allows would miss points unless I widen the block, while coarser cells return many candidates that the distance filter throws away.

The query point can sit right next to a cell edge, so the search circle spills into adjacent cells; scanning only its own cell misses points just across the line. The standard fix is a 3x3 block: the centre cell plus its eight neighbours, nine prefix range scans. That block reaches at least one full cell beyond the centre cell in every direction, so it covers any circle whose radius is no larger than the cell's **shorter** side, measured at the query's latitude. So I pick the finest precision that still satisfies that rule, scan the nine cells, and filter candidates by exact great-circle distance before sorting. The trade-off is cell size versus result count: finer cells than the rule allows would miss points unless I widen the block, while coarser cells return many candidates that the distance filter throws away.

code

pseudocode · 13 lines

pseudocode

function nearby(lat, lng, radiusKm):
  p = finest precision where shorterSideKm(p, lat) >= radiusKm
  centre = geohash(lat, lng, p)
  cells = unique([centre] + eightNeighbours(centre))
  candidates = []
  for cell in cells:
    candidates += rangeScan(keyPrefix = cell)
  results = []
  for c in candidates:
    d = haversineKm(lat, lng, c.lat, c.lng)
    if d <= radiusKm:
      results.append((c, d))
  return sortByDistance(results)

go deeper

for a junior

Remember the picture: the user may stand at a cell's edge, so the query checks the eight surrounding cells too and then measures real distance.

for a middle

Explain why a 3x3 block covers any radius up to the cell's shorter side, and why the shorter side must be measured at the query's latitude.

for a senior

Show you can size the scan: estimate candidates per cell from local density, choose between fewer coarse scans and more fine scans, and handle the antimeridian and poles.

for a principal

Frame precision selection as a cost model over scan count and discarded rows that varies by region, and decide whether per-query or per-region precision is worth the complexity.

Why one cell is never enough

A geohash names a rectangular cell, and a prefix range scan on a sorted index returns every point inside it. A radius query, however, asks about a circle centred on the user, and the user can be anywhere inside their cell, including a metre from its edge. In that case most of the circle lies in neighbouring cells, whose geohash strings may share little or no prefix with the user's cell. Scanning only the user's own cell silently drops the nearest results, which is the most visible bug a nearby feature can have.

The 3x3 block and the precision rule

The standard pattern scans the centre cell plus its eight neighbours (north, south, east, west and the four diagonals).

Whatever the user's position inside the centre cell, the block extends at least one full cell past that cell on every side.
So the block contains every point within distance s of the user, where s is the cell's shorter side in metres.
The rule is therefore: choose the finest precision whose shorter side is at least the radius, computed at the query's latitude, because cell width in metres shrinks as latitude grows.

The shorter side matters because even-length geohashes are 2:1 rectangles. A 6-character cell is about 1.2 km wide but only 0.61 km tall, so it is not safe for a 1 km radius even though its width looks sufficient.

Cell size versus result count

The precision choice is a trade between the number of range scans and the number of wasted candidates. A worked example, assuming a 1 km radius near the equator and evenly spread places:

Plan	Cells scanned	Area scanned	Share of candidates inside the circle
5-character cells (4.9 km), 3x3 block	9	about 216 km2	about 1.5%
6-character cells (1.2 x 0.61 km), 3 wide x 5 tall	15	about 11 km2	about 28%

The circle's area is about 3.14 km2. With 5-character cells the block is 14.7 km on a side, so roughly 98% of fetched rows are discarded by the distance check. Moving to 6-character cells needs two rows of neighbours above and below (because 0.61 km is less than 1 km) but only one column on each side, giving 15 smaller scans and far fewer wasted rows. Which plan wins depends on how expensive a range scan is compared with reading and discarding rows:

In a dense downtown, the coarse plan may pull tens of thousands of rows, so the finer plan is cheaper.
In a sparse rural area, both plans return few rows, and fewer scans is simpler.
Some systems pick precision per query from the radius and the latitude; others store two or three precisions and choose at query time.

The full query path

Compute the precision from the radius and the query latitude.
Encode the user's position at that precision.
Compute the neighbour cells and remove duplicates.
Run one prefix range scan per cell (these can run in parallel).
Compute the exact great-circle distance for every candidate, typically with the haversine formula.
Drop candidates beyond the radius, sort by distance, and apply the page size.

Steps 5 and 6 are not optional. The cells are a candidate filter; the block's corners reach well outside the circle, so unfiltered results include points that are too far away.

Edge cases a correct neighbour function handles

The antimeridian. East of longitude +180 is -180; the neighbour there has an unrelated prefix, and a naive string trick that just increments a character gets it wrong.
The poles. There is no row of cells beyond the top or bottom, and cells become very narrow east-west, so the precision rule picks coarser cells there.
Duplicates. At coarse precision or near the poles, some neighbour computations can return the same cell twice; deduplicate before scanning so results are not double-counted.

What interviewers listen for

The circle-crosses-the-edge argument, stated unprompted.
Nine cells, not one, and why nine is enough only when the radius fits the cell.
Shorter side, at the query's latitude.
The exact distance filter after the scan.
Awareness that cell size trades scan count against wasted candidates, and that density changes the answer.

## Why one cell is never enough A **geohash** names a rectangular cell, and a prefix range scan on a sorted index returns every point inside it. A radius query, however, asks about a **circle** centred on the user, and the user can be anywhere inside their cell, including a metre from its edge. In that case most of the circle lies in neighbouring cells, whose geohash strings may share little or no prefix with the user's cell. Scanning only the user's own cell silently drops the nearest results, which is the most visible bug a nearby feature can have. ## The 3x3 block and the precision rule The standard pattern scans the **centre cell plus its eight neighbours** (north, south, east, west and the four diagonals). - Whatever the user's position inside the centre cell, the block extends **at least one full cell** past that cell on every side. - So the block contains every point within distance `s` of the user, where `s` is the cell's **shorter side** in metres. - The rule is therefore: **choose the finest precision whose shorter side is at least the radius**, computed at the query's latitude, because cell width in metres shrinks as latitude grows. The shorter side matters because even-length geohashes are 2:1 rectangles. A 6-character cell is about 1.2 km wide but only 0.61 km tall, so it is not safe for a 1 km radius even though its width looks sufficient. ## Cell size versus result count The precision choice is a trade between the **number of range scans** and the **number of wasted candidates**. A worked example, assuming a 1 km radius near the equator and evenly spread places: | Plan | Cells scanned | Area scanned | Share of candidates inside the circle | |---|---|---|---| | 5-character cells (4.9 km), 3x3 block | 9 | about 216 km2 | about 1.5% | | 6-character cells (1.2 x 0.61 km), 3 wide x 5 tall | 15 | about 11 km2 | about 28% | The circle's area is about 3.14 km2. With 5-character cells the block is 14.7 km on a side, so roughly 98% of fetched rows are discarded by the distance check. Moving to 6-character cells needs two rows of neighbours above and below (because 0.61 km is less than 1 km) but only one column on each side, giving 15 smaller scans and far fewer wasted rows. Which plan wins depends on how expensive a range scan is compared with reading and discarding rows: - In a dense downtown, the coarse plan may pull tens of thousands of rows, so the finer plan is cheaper. - In a sparse rural area, both plans return few rows, and fewer scans is simpler. - Some systems pick precision per query from the radius and the latitude; others store two or three precisions and choose at query time. ## The full query path 1. Compute the precision from the radius and the query latitude. 2. Encode the user's position at that precision. 3. Compute the neighbour cells and remove duplicates. 4. Run one prefix range scan per cell (these can run in parallel). 5. Compute the exact great-circle distance for every candidate, typically with the **haversine** formula. 6. Drop candidates beyond the radius, sort by distance, and apply the page size. Steps 5 and 6 are not optional. The cells are a **candidate filter**; the block's corners reach well outside the circle, so unfiltered results include points that are too far away. ## Edge cases a correct neighbour function handles - **The antimeridian.** East of longitude +180 is -180; the neighbour there has an unrelated prefix, and a naive string trick that just increments a character gets it wrong. - **The poles.** There is no row of cells beyond the top or bottom, and cells become very narrow east-west, so the precision rule picks coarser cells there. - **Duplicates.** At coarse precision or near the poles, some neighbour computations can return the same cell twice; deduplicate before scanning so results are not double-counted. ## What interviewers listen for - The circle-crosses-the-edge argument, stated unprompted. - Nine cells, not one, and why nine is enough only when the radius fits the cell. - Shorter side, at the query's latitude. - The exact distance filter after the scan. - Awareness that cell size trades scan count against wasted candidates, and that density changes the answer.

What goes wrong if the precision is finer than the radius allows but the scan stays at 3x3?
The block then reaches less than one radius past the centre cell on at least one side, so a point inside the circle but two cells away is never fetched. The query returns a plausible-looking but incomplete list, which is hard to spot in testing. The fix is to either coarsen the precision or widen the block by as many rings as the radius needs in each direction.
Why can't a neighbour cell be found by incrementing the last geohash character?
Characters encode interleaved longitude and latitude bits, so moving one cell east changes only the longitude bits, which can carry into earlier characters. A correct neighbour function decodes the bits, adjusts the longitude or latitude part, handles wraparound at the antimeridian and the edge at the poles, and re-encodes the result.

saying these in an interview costs you the question

Scanning only the query point's own cell is enough
Finer precision is always better because it returns fewer rows
Comparing the cell's longer side to the radius is safe
A cell of a given length has the same size at every latitude
Rows from the cell scans are already the final radius result

In a geohash-indexed nearby-places service, how do you choose the cell precision and scan pattern so a radius query misses no point?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Why one cell is never enough

The 3x3 block and the precision rule

Cell size versus result count

The full query path

Edge cases a correct neighbour function handles

What interviewers listen for

▾common follow-ups2 questions

▾red flags5 flags

Why one cell is never enough

The 3x3 block and the precision rule

Cell size versus result count

The full query path

Edge cases a correct neighbour function handles

What interviewers listen for

answer

go deeper