nordisk/skade

Spatial index (skade::spatial) — design, guide, and the idiot guide

The first spatial acceleration structure in the warehouse. A dependency-free geohash grid index over point rows: bounding-box, radius, and k-nearest queries in O(log n + hits), built from the Arrow batches the warehouse already reads.

See the ranked backlog it comes from: .nornir/warehouse-capability-gaps.md §3.

1. Why (the gap it closes)

skade already streams OSM / GeoParquet features (ParquetWindows) and korp renders a geo view, but the warehouse could not answer a spatial question without a full table scan. It had columnar storage + ACID + time-travel + bloom point-lookups — but no structure that turns "which points are in this box / within this radius / nearest to here" into anything better than reading every row. geoint / OSM is a named use case; this was the biggest capability-for-effort gap, and it needs no external service and no new dependency.

2. The idea (why a sorted Vec is a spatial index)

A geohash interleaves the bits of latitude and longitude and base-32 encodes them, so it is a prefix code: two points that are close in space share a long geohash prefix, and every point inside a given cell shares that cell's geohash as a prefix. Therefore:

• Sort the points by geohash → points in the same region are contiguous.
• A bounding box maps to a small set of covering cells (geohash prefixes).
• Each covering cell is a contiguous range found by one binary search.

No R-tree, no geo crate, no quadtree pointers — a Vec<(geohash, id, lat, lon)> sorted once is the index. The lat/lon are kept so every candidate is verified against its real coordinates: results are exact, with no false positives (the geohash grid only decides what to look at, never what to return).

insert →  Vec<Entry{ hash, id, lat, lon }>          (unsorted)
build  →  sort by hash                              (contiguous cells)
query  →  pick covering cells → binary-search each → verify coords exactly

3. API

use skade::spatial::GeoIndex;

let mut idx = GeoIndex::new(9);      // precision 9 ≈ 5 m cells (good OSM default)
idx.insert(59.3293, 18.0686, 1);     // (lat, lon, id)
idx.insert(59.9139, 10.7522, 2);
idx.build();                          // sort once; idempotent

idx.query_bbox(58.0, 9.0, 61.0, 19.0);   // Vec<id> inside [minlat,minlon,maxlat,maxlon]
idx.query_radius(59.33, 18.07, 600_000.); // Vec<(id, metres)> within radius (haversine)
idx.nearest(59.33, 18.07, 5);             // Vec<(id, metres)>, closest first (kNN)

The warehouse read seam — build straight off the Arrow batches skade already hands back (read_all / read_columns / ParquetWindows):

let batches = skade::read_all(&table).await?;
let idx = GeoIndex::from_batches(&batches, "lat", "lon", "id", 9)?; // already built

from_batches accepts any float/int lat-lon columns and any int id column, skips rows with a null in any of the three, and errors on a missing/wrong-typed column. This is the same builder shape the future graph / full-text / bitmap indexes will follow (see gaps §11), so it is deliberately the template, not a one-off.

4. Correctness & determinism

• Exactness. query_bbox verifies every candidate against min/max lat/lon; query_radius/nearest verify with haversine_m. The grid can only over-select candidates, never miss or falsely return — proven by the tiny_bbox_matches_a_full_scan test (2 000 points, index == brute force) and global_bbox_returns_everything.
• No missed cells. cover_cells samples the query box on a half-cell grid at a precision chosen (pick_precision) so one cell is ≥ the box in both dimensions — so the box is covered by a handful of cells and every covering cell is sampled. A near-global box that would exceed MAX_COVER_CELLS (4096) falls back to an exact full scan.
• Determinism. geohash_encode is pure and allocation-stable (one String of exactly len bytes); identical inputs give byte-identical output (encode_is_deterministic) — the property the sorted index and the bench rely on.
• Argument-order safety. query_bbox normalises swapped corners.

5. Complexity & when to use which precision

Precision picks the cell size (higher = finer = tighter candidate sets, at more distinct hashes): p6 ≈ 1.2 km, p7 ≈ 150 m, p8 ≈ 40 m, p9 ≈ 5 m, p12 ≈ 3.7 cm. For city-scale OSM points p9 is the sweet spot; for country-scale aggregation p6.

6. Tests & bench posture

skade/tests/spatial.rs — 12 tests: prefix-code property, determinism, bbox selection + corner normalisation, brute-force equivalence over 2 000 points, global box, radius great-circle correctness, kNN ordering, haversine vs. a known Stockholm↔Oslo distance, the from_batches read seam (incl. null-skipping and bad-column rejection), and a LIGHT in-process timing guard (light_query_timing_is_sublinear, 50 k points) that catches a future regression from prefix-scan back to full-scan.

Bench posture (nordisk BENCH RULE): the timing check is a light, pure in-process guard only — no heavy runs on this box. A heavy N-sweep (millions of OSM points, geohash-vs-scan crossover) belongs on Loki/Odin and is not run here. This structure is new capability, so "keep only if faster AND byte-identical" does not apply (there is no prior implementation to be byte-identical to); the determinism test is the analogous guarantee.

7. For the absolute beginner ("idiot guide")

You have a table of things with a latitude and a longitude (shops, sensors, OSM nodes). You want "everything near here" without reading the whole table.

1. Make an index: let mut idx = GeoIndex::new(9);
2. Put your points in: idx.insert(lat, lon, row_id); (or one call GeoIndex::from_batches(&batches, "lat", "lon", "id", 9)? straight from what skade read for you).
3. idx.build(); (once, after inserting).

4. Ask:

   • "what's in this rectangle?" → idx.query_bbox(minlat, minlon, maxlat, maxlon)
   • "what's within 2 km of me?" → idx.query_radius(mylat, mylon, 2000.0)
   • "the 5 closest?" → idx.nearest(mylat, mylon, 5)

Behind the scenes it turns each map cell into a short text code (a "geohash"), sorts them, and jumps straight to the codes near you with a binary search instead of scanning every row. The answers are exact — it double-checks the real coordinates before handing anything back.

8. Next iterations (not this round — see gaps §3 / §11)

• Z-order/Hilbert-curve variant for better locality on skewed data.
• Persist the index as an Iceberg side-table (_geo_<col>) so it time-travels with the data.
• Wire a ScanFilter::Bbox file-pruner into read_filtered so spatial predicates skip Parquet files, not just post-filter.
• Drive it from korp's geo view (headless robot-ui scenario + testmatrix cell).
• Factor the shared SecondaryIndex trait this from_batches seam prototypes.