# 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
```rust
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`):
```rust
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
| Op | Cost |
|---|---|
| `insert` | O(1) amortised + one geohash encode |
| `build` | O(n log n) sort, once |
| `query_bbox` | O(cells · log n + candidates) |
| `query_radius` | bbox query + haversine per candidate |
| `nearest(k)` | radius-doubling until ≥ k found, then sort |
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.