Module geo 

The geospatial kernels, which are Redis’s geohash arithmetic.

This sits here rather than beside the geo commands because two very different callers need the same arithmetic. GEOSEARCH walks a sorted set with it and a GEOFILTER on a search index walks a numeric index with it, and the two only agree with each other about where a boundary falls if they share a single copy of the interleave, the haversine and the box cover.

A geo key in Redis is not a type. It is a sorted set whose scores happen to be 52 bit interleaved geohashes, and every geo command is a sorted set command with some arithmetic in front of it. ZSCORE on a geo key answers the raw hash, ZRANGE works, TYPE says zset, and OBJECT ENCODING says listpack or skiplist. That is not an accident of the implementation, it is the documented behaviour, so it is what we do too.

The score

Longitude is mapped from [-180, 180] and latitude from [-85.05112878, 85.05112878], which are the EPSG:900913 limits and the reason you cannot store a point at either pole. Each is scaled to 26 bits and the two are interleaved, latitude in the even positions and longitude in the odd ones, giving 52 bits, which is exactly what an f64 holds without losing anything. That last part is why the score can be a float at all.

A shorter hash is the same thing with fewer bits, and it names a box rather than a point. Hash carries the step so the two cannot be confused, and align is what turns a box into the score range that covers it.

The search

A radius search is nine range queries. Work out how many bits of hash make a box about the size of the search area, find the box the centre is in, take its eight neighbours, and ask the sorted set for every member whose score falls in one of those nine ranges. Then throw away the ones that are in a box but outside the actual circle. The boxes are a filter and the distance is the answer.

Two adjustments in areas are what make that correct rather than nearly correct, and both are Redis’s. The step estimate can be one too coarse near the edge of a box, so the four side neighbours are decoded and the step is dropped by one if any of them fails to reach past the bounding box. And a neighbour that is entirely outside the bounding box is zeroed rather than searched, which is three of the nine gone in the common case.

The distance

Haversine on a sphere of radius 6372797.560856 metres, which is the WGS-84 quadratic mean radius. Not Vincenty, not the ellipsoid, and not accurate to better than about half a percent at continental distances. It is the number Redis answers and a client comparing our GEODIST against its own is comparing against this, so a better formula would read as a bug.

The one shortcut in it is Redis’s too: when the two longitudes are exactly equal the haversine collapses to asin(sin(x)), which is x over the latitude range, so the arc is computed directly and the trigonometry is skipped.

Structs

Area

The corners of a box, in degrees.

Hash

A box of the world, named by however many bits of hash it took to name it.

Search

The nine boxes a search has to look in, and where the search area is.

Shape

What is being searched for, and around where.

Enums

Kind

A circle or a rectangle.

Unit

What a distance is measured in.

Constants

HASH_CHARS

How many characters a GEOHASH reply has.

LAT_MAX

The highest latitude that can be stored.

LAT_MIN

The lowest latitude that can be stored.

LON_MAX

The highest longitude that can be stored.

LON_MIN

The lowest longitude that can be stored.

STEP_MAX

How many bits of hash a full precision point uses on each axis.

Functions

align

A box’s bits pushed up to where a full precision score keeps them.

area

The box a hash names.

areas

The nine boxes a search over this shape has to look in.

decode

The point a score decodes to, which is the middle of the box it names.

distance

The great circle distance between two points, in metres.

encode

The hash of a point at a given precision.

encode_in

The same, over ranges the caller picks.

geohash

The eleven character geohash string for a point.

in_range

Whether a point is somewhere the hash can name.

lat_distance

The arc between two latitudes, in metres.

range

The score range a box covers, low inclusive and high exclusive.

score

The score a point is stored under.

steps_for

How many bits of hash make a box roughly the size of a search.