Points and distances

Places on the earth in a collection: the metres between two, every row within a radius or a box, the nearest first — what an app adds Redis's GEOADD and GEOSEARCH or PostGIS for.

A geo field holds a point, [lon, lat] in degrees. distance(loc, p) is the metres between two points, within(loc, [west, south, east, north]) whether one lies in a box, and near loc p puts rows in order nearest first. @geo indexes the field, so a radius, a box and the nearest read the rows near the point rather than every row. Every answer is the one a scan of every row gives, row for row.

The other jobs an app adds Redis for — counters, locks, caches, job queues, pub/sub — are recipes of Instead of Redis.

Every FenecQL block on this page is run, statement by statement, by a test (crates/fenec-core/tests/geo_docs.rs), and each -- → x is the answer it checks: a write's count, or the first value of the first row it answered. The costs are make geo-bench on an M1 Air, over a million points.

Points

A point is written as a list of two numbers, its longitude first — GeoJSON's order, and the order Redis and PostGIS take them in.

create collection places (name text, kind text @hash, loc geo @geo)
put places [{name: "Palermo", kind: "city", loc: [13.361389, 38.115556]}, {name: "Catania", kind: "city", loc: [15.087269, 37.502669]}]   -- → 2
get places select loc where name = "Catania"   -- → [15.087269,37.502669]

• Redis: GEOADD Sicily 13.361389 38.115556 "Palermo" 15.087269 37.502669 "Catania".
• Kept as written. The two numbers are f64s and come back as they went in. Redis keeps a 52-bit geohash, which moves a point to the centre of a cell 0.6 m by 0.3 m at the equator: its GEOPOS answers 15.08726745843887329 for the 15.087269 it was given.
• A longitude from -180 to 180 and a latitude from -90 to 90, or the write is refused: a latitude of 91 is most often the two given the other way round. Redis takes latitudes to 85.05 only.
• null is no point. A row without one is in no radius and no box, and near answers only rows that hold one.

Distance

distance(a, b) is the metres between two points, on a sphere of Redis's radius (6 372 797.56 m) — so it is GEODIST's answer.

get places select distance(loc, [15.087269, 37.502669]) as m where name = "Palermo"   -- → 166274.2577914073

• Redis: GEODIST Sicily Palermo Catania answers 166274.1516, between the points it keeps: 0.11 m off, since it moved each to its cell. Over 2 000 pairs of points, crowded and spread over the earth, the two agree to 0.05 mm from the points Redis keeps (GEOPOS), and to 0.54 m from the points as written.
• PostGIS: ST_Distance(a, b, false) over geography is on a sphere of the earth's mean radius, 6 371 008.8 m, so its metres are 0.03% fewer: Palermo to Catania is 166 227.6 m. Its default, the WGS84 ellipsoid, differs from a sphere by up to 0.5%: 166 506.2 m.
• The same bits everywhere. The trigonometry is fenecdb's own, not the platform's: a point on a radius's edge is in or out alike on a server, a phone and a page.

Within a radius

get places select name where distance(loc, [15, 37]) <= 200000   -- → "Palermo": in id order
get places select name where distance(loc, [15, 37]) <= 100000   -- → "Catania"
get places where distance(loc, [15, 37]) <= 200000 count         -- → 2

• Redis: GEOSEARCH Sicily FROMLONLAT 15 37 BYRADIUS 200 km.
• A radius reaches the index written distance(loc, p) <= r or < r, either way round, in an and chain, the point and the radius each a literal or a parameter. A ring — distance(loc, p) > 1000 beside it — is tested on the rows the radius found.
• Any radius: 0 is the point itself, and one past half the earth's circumference is every row. A radius over a pole takes every longitude, and one across the antimeridian both sides of it.

Nearest first

near loc p orders the rows by their distance from p, a tie by id, and _score is the distance in metres:

get places select name, distance(loc, [15, 37]) as m near loc [15, 37] limit 1   -- → "Catania"
get places select name where distance(loc, [15, 37]) <= 200000 near loc [15, 37] limit 10   -- → "Catania": then Palermo
get places select name where distance(loc, [15, 37]) <= 200000 order distance(loc, [15, 37]) limit 10   -- → "Catania": the same rows

• Redis: GEOSEARCH Sicily FROMLONLAT 15 37 BYRADIUS 200 km ASC COUNT 10 WITHDIST. Redis needs a radius to search in; near needs none.
• The index is walked nearest first and stops at the page: the ten nearest of a million points took 33 to 38 us, whether they were a street or an ocean away.
• _score is an f32, as every score is: to the metre out to 16 777 km, and 2 m past it. Select distance(loc, p) for the f64.
• near loc p exact measures every row, as the collection without the index does: the same answer.
• order distance(loc, p) is the same order as a key of order, ties by id, beside other keys and in a write that picks its rows (The nearest job). With a limit it walks the index as near does where no row the filter passes lacks a point; a row with none has a null distance, which comes first, so where some may pass -- no radius or box on the field, and rows without a point -- every row the filter passes is measured. near leaves such rows out.

In a box

within(loc, [west, south, east, north]) holds a point inside the box or on its edge. A box whose west is east of its east crosses the antimeridian:

get places where within(loc, [12, 37, 16, 39]) count   -- → 2
put places [{name: "Suva", kind: "city", loc: [178.4419, -18.1248]}, {name: "Apia", kind: "city", loc: [-171.7513, -13.8333]}, {name: "Nuku'alofa", kind: "city", loc: [-175.2018, -21.1394]}]   -- → 3
get places where within(loc, [170, -25, -170, -10]) count   -- → 3
get places select name near loc [180, -15] limit 1   -- → "Suva"

• Redis's BYBOX is a width and a height in metres around a centre; within takes the corners, as a map's visible area gives them. The rows of a map's view are within(loc, $bounds) with limit.
• PostGIS: loc && ST_MakeEnvelope(w, s, e, n, 4326), whose box does not wrap: one across the antimeridian is two.

With the rest of a query

A radius or a box is one condition of an and chain, so the rest of the query goes with it: other conditions, an order, a count, a facet, a lookup.

put places [{name: "Cafe A", kind: "cafe", loc: [15.0912, 37.5047]}, {name: "Cafe B", kind: "cafe", loc: [15.0855, 37.5076]}, {name: "Fish market", kind: "market", loc: [15.0868, 37.5005]}]   -- → 3
get places select name where kind = "cafe" and distance(loc, [15.087269, 37.502669]) <= 1000 near loc [15.087269, 37.502669] limit 5   -- → "Cafe A"
get places where kind = "cafe" and distance(loc, [15.087269, 37.502669]) <= 1000 count   -- → 2
get places select name where distance(loc, [15.087269, 37.502669]) <= 1000 facet kind

• Whichever index names fewer rows is read, and the other condition tested on each: a @hash bucket of a few dozen cafes, or the rows of a radius narrower than the bucket. A near over a set of a few thousand rows measures it whole rather than walk the points.
• A scoped token finds only the points its rules let it read: its filter is ANDed in as it is into every statement (Security).
• or reads every row, as it does for any index. Two radii are two statements, or one statement each in a /batch.

Positions that expire

Couriers, drivers, a user's last known place: each one's position written over as it moves, and gone when it stops being sent. @ttl takes a row out of every read once its time is past.

create collection couriers (name text @unique, loc geo @geo, seen timestamp @ttl(30s))
put couriers {name: "ada", loc: [15.0901, 37.5031], seen: now()} if absent else set {loc: new.loc, seen: new.seen}   -- → 1
put couriers {name: "bo", loc: [15.0702, 37.5120], seen: now()} if absent else set {loc: new.loc, seen: new.seen}    -- → 1
get couriers select name near loc [15.087269, 37.502669] limit 1   -- → "ada"
-- 20 s later
put couriers {name: "bo", loc: [15.0880, 37.5030], seen: now()} if absent else set {loc: new.loc, seen: new.seen}    -- → 1: bo moved
get couriers select name near loc [15.087269, 37.502669] limit 1   -- → "bo"
-- 20 s later
get couriers select name near loc [15.0901, 37.5031] limit 1       -- → "bo": ada's position is 40 s old
get couriers count   -- → 1

• An upsert a position: the row made the first time, its point and time set after, one statement whichever it is.
• Gone at once: a row past its @ttl is out of every read the moment it is, and the server's sweeper deletes it one to two minutes later (Rows that expire).

The nearest job

An order waiting for a courier, a ride for a driver: the job nearest a worker that is ready, taken in one statement under the write lock, so two workers never take the same one. order takes the distance as its key in a set that picks its rows, and returning answers what was taken (Writes that pick their rows):

create collection deliveries (pickup geo @geo, run_at timestamp @sorted, courier text)
put deliveries [{pickup: [15.0912, 37.5047], run_at: now()}, {pickup: [15.0855, 37.5076], run_at: now()}, {pickup: [15.0880, 37.5031], run_at: now() + 600000}]   -- → 3
set deliveries {courier: "ada", run_at: now() + 45000} where run_at <= now() and distance(pickup, [15.0901, 37.5031]) <= 3000 order distance(pickup, [15.0901, 37.5031]) limit 1 returning id   -- → 1: the nearest ready; 3 is nearer, and waits ten minutes
set deliveries {courier: "bo", run_at: now() + 45000} where run_at <= now() and distance(pickup, [15.0901, 37.5031]) <= 3000 order distance(pickup, [15.0901, 37.5031]) limit 1 returning id   -- → 2: the one left
set deliveries {courier: "cy", run_at: now() + 45000} where run_at <= now() and distance(pickup, [15.0901, 37.5031]) <= 3000 order distance(pickup, [15.0901, 37.5031]) limit 1 returning id   -- → no row: none ready within 3 km
-- 50 s later
set deliveries {courier: "cy", run_at: now() + 45000} where id in (get deliveries select id where run_at <= now() near pickup [15.0901, 37.5031] limit 1)   -- → 1: ada's lease lapsed

• The lease is the ready time moved on: a courier who goes quiet holds the job until it lapses, and the next claim takes it, with nothing written to say so. Its pickup, delivery and every beat are set ... where id = $1 and courier = $2 require 1, refused once another holds it (Job queues).
• The radius bounds the walk: the point index is walked nearest first and stops at the page or 3 km out, whichever comes first. With a radius on the field the walk is taken even where some rows hold no point, since none of those passes it.
• Or an inner get with near, run first and its one id written, under the same lock. A near takes no order, and a write takes no near of its own: the distance is a key of order there.

From a client

Over HTTP a point is a JSON array, and a filter is FenecQL's:

curl -X POST http://127.0.0.1:8080/places -d '{"name": "Catania", "loc": [15.087269, 37.502669]}'
curl 'http://127.0.0.1:8080/places?select=name&where=distance(loc,%5B15,37%5D)%3C%3D200000'
curl -X POST http://127.0.0.1:8080/places/near -d '{"field": "loc", "vector": [15, 37], "limit": 10}'
curl -X POST http://127.0.0.1:8080/query \
  -d '{"query": "get places select name near loc $1 limit 10", "params": [[15, 37]]}'

The builders write it as an object condition:

import { connect, distance, type Point } from '@fenecdb/web/client';
import type { FenecSchema } from './fenec-schema.js';   // fenec types app.fenec

const db = connect<FenecSchema>('http://127.0.0.1:8080');
const here: Point = [15.087269, 37.502669];
const cafes = await db.from('places')
  .select('name', distance('loc', here).as('m'))
  .where({ kind: 'cafe', loc: { distance: { from: here, lte: 1000 } } })
  .near('loc', here)
  .limit(10)
  .rows();
const inView = await db.from('places').where({ loc: { within: [12, 37, 16, 39] } }).rows();

Python's, Go's, .NET's, Swift's, Kotlin's and Dart's builders take the same within and distance conditions and render the same text. fenec types writes a geo field as each language's pair of doubles, and a Drizzle table's geometry('loc', { type: 'point' }) with a GiST index is a geo field with @geo.

• The degrees as written. Every reader without a schema — a query's parameters, a JSON body, the browser module — reads a list of numbers as a vector's f32s, which would move a point by up to 1.7 m at the antimeridian. A list going to a geo field or a distance, within or near over one is read again as written.
• In the page. The browser module answers the same statements over a database in the page or a synced replica, its index and all.

From PostGIS

fenec import takes a geometry(Point, 4326) or geography(Point) column, or PostgreSQL's own point, as a geo field:

fenec import postgres://app@db:5432/app --table stores --into stores --index "loc@geo"

A column of other shapes — lines, polygons — or of another SRID is refused naming it; --follow mirrors the table as it changes (Import).

What it costs

A million points crowded round 48 cities, as a shop's or a courier's lie, make geo-bench: fenecdb in process; PostGIS 3.5 (a geography(Point) column, GiST, ST_DWithin(…, false) and <->) and Redis 7 (GEOSEARCH) in Docker, each server's own mean time of the query from pg_stat_statements, planning included, and INFO commandstats — the network's 0.3 ms left out. The median of a thousand queries near a point of the data:

• A put with @geo costs 1.19 us, against 0.62 without an index and 0.98 with @sorted on a float.
• Spread evenly over the earth, a million points are about 20 km apart: a radius of up to 10 km took 5 to 10 us, 100 km 24 us, the ten nearest 35 us.
• Redis sorts every member of the cells round the point by distance: the ten nearest anywhere is a search past half the earth, every member measured. PostGIS plans each statement again, half a millisecond of its time, and its GiST over geography read 132 pages for a radius of 100 m.
• Over HTTP a request adds its round trip, as it does to PostgreSQL's and Redis's: 0.3 ms through Docker's network here.

What this does not cover

• Shapes other than points: no lines, polygons or a point in a polygon. A box is the one area a query takes; a polygon's bounding box narrows, and the app tests the rest.
• The ellipsoid. Distances are on the sphere, as Redis's are: within 0.5% of WGS84's, which PostGIS's geography takes by default.
• A distance between two rows in one statement: the other row's point is read first and passed as a parameter.
• GEOHASH strings and STORE: a search's rows are answered, not written to another key.