Deep Dive into Geohashes
Geohash is a public domain geocode system that encodes a geographic location into a short string of letters and digits. It works by recursively subdividing the Earth's surface into a grid.
How Geohash Works
The algorithm interleaves bits derived from the latitude and longitude. The first step is to divide the Earth into two halves. If the point is in the right half, it gets a 1; if left, a 0. This process is repeated recursively, alternating between longitude and latitude, until the desired precision is reached. Finally, the binary string is converted to a base32 string.
Prefix Matching for Proximity
A geohash prefix identifies one rectangular cell. Two points with a sufficiently long shared prefix occupy that cell, but they may still be far apart within it; nearby points on opposite sides of a cell boundary may share little prefix. Prefix lookup is candidate generation, not proof that a point lies within the requested radius.
SELECT * FROM places WHERE geohash LIKE '9q8y%';The Edge Case Problem
A robust query chooses a cell precision from the requested radius and latitude, computes a covering that fully contains the search shape, fetches candidates from every covered cell, deduplicates them, and applies an exact distance check. The center cell plus eight neighbors is sufficient only for particular radius/cell-size combinations; larger radii require more cells, and dateline or polar cases need explicit longitude-wrapping and geometry handling.
Choosing the Right Precision
The length of the Geohash string determines its precision (sizes below are at the equator; the east-west width shrinks with the cosine of latitude):
- 4 characters: ~39 km x 19.5 km
- 5 characters: ~4.9 km x 4.9 km
- 6 characters: ~1.2 km x 0.6 km
In a system design interview, selecting a precision of 5 or 6 characters is typically appropriate for a localized proximity search (like finding nearby restaurants).
Worked example: encoding San Francisco
Encode latitude 37.7749, longitude -122.4194. Bits alternate, starting with longitude; each bit halves the current range.
- Longitude in [-180, 180]: -122.4 is below the midpoint 0, bit 0, range becomes [-180, 0].
- Latitude in [-90, 90]: 37.8 is at or above 0, bit 1, range [0, 90].
- Longitude in [-180, 0]: below -90, bit 0, range [-180, -90].
- Latitude in [0, 90]: below 45, bit 0, range [0, 45].
- Longitude in [-180, -90]: at or above -135, bit 1, range [-135, -90].
The first five bits 01001 equal 9, and base32 character 9 is "9". Continuing gives 9q8yyk8 at 7 characters, a cell about 150 m on a side. Each character adds 5 bits, alternating which axis gets the extra bit, so cells alternate between square-ish and 2:1 rectangles.
Precision table (at the equator)
| Length | Cell width x height | Typical use |
|---|---|---|
| 4 | 39.1 km x 19.5 km | Metro region sharding |
| 5 | 4.89 km x 4.89 km | City-scale search, radius a few km |
| 6 | 1.22 km x 0.61 km | Neighbourhood search, radius under 1 km |
| 7 | 153 m x 153 m | Walking distance, driver matching |
| 8 | 38.2 m x 19.1 m | Building level |
| 9 | 4.77 m x 4.77 m | Precise points; beyond GPS accuracy for many phones |
Choosing a covering
- Pick the longest precision whose cell size is at least the search radius in both dimensions at the query latitude; then center plus 8 neighbours is guaranteed to cover the circle.
- For larger radii at a fixed precision, compute all cells intersecting the circle's bounding box; the count grows with the square of radius over cell size.
- Near the antimeridian (longitude 180) neighbours wrap to the opposite sign; near the poles cells become very narrow, so use a spherical library rather than hand-rolled math.
How real systems use it
- Redis GEO stores a 52-bit geohash integer as a sorted-set score and scans neighbouring ranges.
- Elasticsearch supports geohash grid aggregations for map heat-maps, and many teams store a geohash column with a B-tree index in PostgreSQL or DynamoDB sort keys for simple prefix queries.