popoto.backends.postgres.geo¶
popoto.backends.postgres.geo
¶
GeoField on Postgres without PostGIS (#759 M5).
Redis keeps a GeoField in a sorted set whose scores are 52-bit geohashes
(GEOADD), and answers a radius search (GEORADIUS /
GEORADIUSBYMEMBER) by scanning up to nine geohash boxes around the center
and keeping the members whose haversine distance is within the radius. This
module reproduces that arithmetic operation for operation, from Redis's own C
(src/geohash.c, src/geohash_helper.c, src/geo.c; read at tag
8.10.2), so that the same points, searched the same way, give the same keys
and the same distances to the bit as a Redis built without floating-point
contraction (see "Arithmetic" below).
Storage. Beside the field's own jsonb value (the coordinates exactly
as given, which is what a read returns on both backends), a GeoField
f gets three auxiliary columns:
f__geohash bigint-- the member's score,geohashEncodeWGS84at step 26 andgeohashAlign52Bits: the very integer Redis stores as the zset score.NULLmeans "not in the geo index", which is where Redis'son_saveZREMs the member (no value, or a zero/Nonelatitude or longitude) and where a deleted record leaves it. A B-tree on it serves the box scan: each geohash box is one[min, max)score range, exactlyZRANGEBYSCORE's, so the prefilter is Redis's own and needs no GiST.f__geolon/f__geolat double precision-- the member's position decoded from the score (geohashDecodeToLongLatWGS84): the cell's center, i.e. whatGEOPOSreturns. Redis measures distance from this quantised position, never from the coordinates as given, so the columns hold it, computed once at save.
Search. The geohash boxes (geohashCalculateAreasByShapeWGS84, with
its step estimate, its "decrease the step" check and its pruning of useless
neighbours) are computed here; one statement fetches the rows in those score
ranges (live rows only, on a Meta.ttl model); each candidate's distance
is geohashGetDistance and the radius test is geohashGetDistanceIfInRadius
(distance > radius * conversion excludes). The matched keys then scope
the query's own statement as _pk = ANY(…), and the distances order it.
Arithmetic: plain IEEE doubles, never fused. Every a*b + c here is
two roundings, as CPython evaluates it. That is deliberate: a Postgres
deployment has no Redis to mirror, so the port must not depend on how a
compiler built Redis, and the only portable reading of its C is the one with
no contraction. Encode and decode use no libm, so scores and decoded
positions are bit-identical, on every platform, to a Redis built without
contraction (the x86-64 builds, e.g. redis:7-alpine, which CI runs). A
Redis built with clang on arm64 (e.g. Homebrew 8.10.2) contracts two
expressions into fused multiply-adds -- the decode's
min + (i / 2**step) * scale and the haversine's
u*u + cos(lat1)*cos(lat2)*v*v -- so its decoded positions and distances
are one fused rounding away from this in places (for a near-antipodal
distance, where asin's slope amplifies it, up to about 0.19 m), and a
member that close to the radius can be in on one and out on the other.
sin/cos/asin are the host Python's libm, as Redis uses its own.
Libms agree to within an ulp but not on the last bit (CI's musl-linked Redis
against its glibc Python shows it), so a distance can differ by that much,
propagated through the formula, from a Redis on another libm.
sqrt is IEEE, correctly rounded everywhere. scripts/probe_geo_parity.py
classifies both kinds of difference. The distance stays in Python rather
than SQL so that the save's decode and the search's test share one
implementation; nothing in it needs Python beyond that.
Distances are reported as Redis replies them: WITHDIST divides the
meters by the unit's conversion factor and prints four decimals
(fixedpoint_d2string: llrint(d * 10000), ties to even), which redis-py
parses back with float. :func:reply_distance is that value.
What is not reproduced. COUNT/ANY/DESC/WITHCOORD/
WITHHASH are GEOSEARCH options the public GeoField API does not
expose (it sends WITHDIST and ASC with with_distances, nothing
otherwise), so there is nothing to reproduce. PostGIS (a geography
column and a GiST index) could replace the box scan later as an
optimisation; it would not change the arithmetic above, and it is not a
dependency.
D_R = math.pi / 180.0
module-attribute
¶
#define D_R (M_PI / 180.0): folded to the same double.
UNIT_TO_METERS = {'m': 1.0, 'km': 1000.0, 'ft': 0.3048, 'mi': 1609.34}
module-attribute
¶
extractUnitOrReply.
NAN_DISTANCE_REPLY = float('-922337203685477.5808')
module-attribute
¶
What WITHDIST replies for a distance that computes to NaN, as an
x86-64 Redis replies it (CI's redis:7-alpine, the reference build):
fixedpoint_d2string prints llrint(NaN * 10000), and x86-64's
llrint (cvtsd2si) returns LLONG_MIN for NaN, which prints as
-922337203685477.5808. An arm64 Redis's llrint(NaN) is 0 and it
replies 0.0000 instead: a documented divergence.
GeoResolved
dataclass
¶
A geo leaf after its search ran: the keys it matched (a
Cond(field, Op.WITHIN, GeoResolved) renders _pk = ANY(…)) and,
with with_distances, each key's distance as Redis replies it.
Source code in src/popoto/backends/postgres/geo.py
encode(longitude, latitude, step=GEO_STEP_MAX)
¶
geohashEncode over the WGS84 ranges. The caller has range-checked
the point (extractLongLatOrReply).
Source code in src/popoto/backends/postgres/geo.py
as_score(bits)
¶
A 52-bit hash as the zset holds it: a double. A point on the
latitude limit sets bit 52 and one on longitude 180 bit 53, and past
2**53 the conversion rounds (to even) -- so GEOADD of such a
point stores, and GEOPOS decodes, a neighbouring cell's score. Range
bounds go through the same conversion (geoGetPointsInRange takes
doubles), so integer comparisons of rounded values are the zset's
double comparisons.
Source code in src/popoto/backends/postgres/geo.py
score_of(longitude, latitude)
¶
The score GEOADD stores for a point (geohashEncodeWGS84 at step
26, geohashAlign52Bits, then a double).
Source code in src/popoto/backends/postgres/geo.py
decode_point(score)
¶
(longitude, latitude) of a stored score: the cell's center,
clamped to the WGS84 ranges (geohashDecodeAreaToLongLat) -- what
GEOPOS returns.
Source code in src/popoto/backends/postgres/geo.py
search_ranges(longitude, latitude, radius, conversion)
¶
The score ranges [min, max) Redis scans for a radius search
(geohashCalculateAreasByShapeWGS84 then membersOfAllNeighbors /
scoresOfGeoHashBox): the center box and the neighbours it keeps.
Source code in src/popoto/backends/postgres/geo.py
distance(lon1d, lat1d, lon2d, lat2d)
¶
geohashGetDistance: haversine on Redis's earth radius, with its
equal-longitude shortcut. asin of a rounding-inflated argument above
1 is NaN in C (Python raises), and NaN > radius is false there, so
such a point is kept -- reproduced.
Source code in src/popoto/backends/postgres/geo.py
reply_distance(meters, conversion)
¶
The distance as WITHDIST replies it and redis-py reads it:
meters / conversion printed with four decimals
(fixedpoint_d2string: llrint(d * 10000), ties to even), parsed
back with float. A NaN distance (asin of a rounding-inflated
argument above 1) replies :data:NAN_DISTANCE_REPLY, as on x86-64.
Source code in src/popoto/backends/postgres/geo.py
parse_double(value, message)
¶
getDoubleFromObjectOrReply: the argument as redis-py sends it,
parsed as the server parses it; refused with message.
Source code in src/popoto/backends/postgres/geo.py
parse_point(longitude, latitude)
¶
extractLongLatOrReply: both parsed, then range-checked.
Source code in src/popoto/backends/postgres/geo.py
parse_radius(radius)
¶
extractDistanceOrReply's radius (the unit is checked earlier, by
GeoField.parse_query).
Source code in src/popoto/backends/postgres/geo.py
geo_columns(spec)
¶
<f>__geohash bigint and the decoded <f>__geolon /
<f>__geolat per GeoField (auxiliary: never hydrated).
Source code in src/popoto/backends/postgres/geo.py
geo_indexes(spec, index_name)
¶
A partial B-tree on the score: each search box is one range of it.
Source code in src/popoto/backends/postgres/geo.py
geo_save_values(ts, spec, obj, names)
¶
The geo columns a save writes, for each GeoField in names.
GeoField.on_save's rule: a value with a falsy latitude or longitude
(None, 0) leaves the member out of the index (ZREM), else
GEOADD stores the step-26 score. A point GEOADD refuses raises
ValueError with Redis's text before anything is written; on Redis
the hash has already been written by then (a documented divergence: the
Postgres save is atomic).
Source code in src/popoto/backends/postgres/geo.py
resolve_geo(backend, ts, where, uow=None)
¶
Run every geo leaf of where and replace it with its matched keys
(on uow's connection when one is given, #776).
Returns the rewritten predicate, the distances of the leaves that asked
for them (merged in predicate order: a later leaf's distance for a key
wins, as a later state.geo_distances.update does on Redis), and the
unit of the last such leaf; None for both when no leaf asked.
Source code in src/popoto/backends/postgres/geo.py
within_sql(c, params)
¶
A resolved geo leaf: the keys its search matched.