Geospatiale indexering voor defensie: H3, S2, R-Tree en de miljoen-trackquery

Het miljoen-trackquery-probleem

Een veelvoorkomende operatorquery in een defensie-fusieplatform luidt: "toon me alles binnen 5 km van dit punt in de afgelopen 60 seconden." Het klinkt eenvoudig. Op een tabel van honderd miljoen trackupdates, geschreven door AIS-ontvangers, ADS-B-feeds, radarsporen, ESM en drontelemetrie, bezwijkt een naïeve implementatie binnen drie weken productieverkeer.

De naïeve query is een sequentiële scan. SELECT * FROM tracks WHERE ST_DWithin(geom, $point, 5000) AND ts > now() - interval '60 seconds'. Op een tabel van honderd miljoen rijen zonder ruimtelijke index duurt dat 12 tot 40 seconden afhankelijk van de schijf. Met duizend operators die elke 2 seconden vernieuwen, verbrandt de database. De oplossing is geen snellere hardware. De oplossing is een ruimtelijke index — en de keuze van de index bepaalt alles stroomafwaarts: ingest-doorvoer, querylatentie, opslagvoetafdruk en de kosten van gedistribueerde sharding.

Dit artikel bespreekt de vier indexfamilies die van belang zijn voor defensie: H3, S2, de R-Tree-lijn en het PostGIS GiST/SP-GiST/BRIN-trio. Vervolgens komen hybride tijdreekspatronen, de tweelaagsculling-architectuur voor het gemeenschappelijk operationeel beeld en het migratieverhaal aan bod.

H3 (Uber hexagonaal)

H3 is een hiërarchisch hexagonaal rastersysteem. De planeet is opgedeeld in 122 basiscel len (10 vijfhoeken, 112 zeshoeken), en elke basiscel wordt recursief onderverdeeld in zeven kinderen, tot resolutie 15. Een cel op resolutie 9 is ruwweg 0,1 km² — ter grootte van een stadsblok. Een cel op resolutie 6 is circa 36 km² — een bruikbare operationele betrokkenheidsbel.

Zeshoeken zijn beter dan vierkanten voor nabijheidsquery's omdat elke hexagonale buur op dezelfde centroïdafstand ligt. Bij een vierkant raster zijn diagonale buren 1,41× verder dan randburen — elke afstandsberekening moet hiermee rekening houden. Bij zeshoeken levert een k-ring van straal 3 precies 37 cellen op, allemaal op voorspelbare afstand. Een zoekopdracht met een straal van 5 km wordt: converteer het querypunt naar een H3-cel, vergroot tot een k-ring die 5 km beslaat, haal alle tracks op met die cel-ID's, verfijn vervolgens met exacte ST_Distance.

Defensievriendelijke kenmerken: H3-cel-ID's zijn 64-bit gehele getallen, triviaal te indexeren in elke KV-opslag. Cellidmaatschap is hashbaar, zodat een track met een H3-kolom op celprefix kan worden gesharded zonder eigen logica. Aggregaten op celniveau ("hoeveel tracks per H3-7-cel in het afgelopen uur") reduceren rechtstreeks tot een GROUP BY h3_index. Wij hebben H3-geïndexeerde tracktabellen 5 km-nabijheidsquery's zien beantwoorden in 8–14 ms op tabellen van 200 miljoen rijen.

Google S2

S2 partitioneert de bol via een quadtree-projectie op het oppervlak van een ingeschreven kubus. Elke vlak wordt recursief onderverdeeld in vier kinderen tot niveau 30, waar cellen circa 1 cm² zijn. De S2CellId is een 64-bit geheel getal dat celvlak, positie langs een Hilbert-curve en niveau codeert. De Hilbert-codering is de truc: cellen die dicht bij elkaar op de bol liggen hebben dichtbijgelegen ID's, zodat een BETWEEN-bereik op de gehele-getalkolom gedraagt als een ruimtelijke bereikquery.

Dat voordeel van geheelgetalrekenkunde is wanneer S2 wint. Als de werkopslag een gesharde RDBMS is, een vlakke KV (DynamoDB, Cassandra) of een zoekmachine (Elasticsearchs geo_shape gebruikt BKD-bomen, maar bereikquery's op S2CellId's zijn even snel), houdt S2 nabijheidslogica binnen goedkope geheelgetalvergelijkingen. Geen GIS-extensie vereist.

H3 versus S2 in de praktijk: H3 is gebruiksvriendelijker voor uniforme-afstandsredenering, aggregaties en door mensen leesbare cellen. S2 is gebruiksvriendelijker wanneer de opslaglaag geen geometrieondersteuning heeft en u werkt met miljarden punten over wereldwijde dekking waar penta goonvervorming in H3 (10 cellen per planeet hebben slechts 5 buren in plaats van 6) problemen oplevert. NATO maritieme bewakingsteams die wereldwijde AIS-data indexeren zijn om precies deze reden overgestapt op S2. Regionale luchtbeelden met continentale reikwijdte blijven grotendeels op H3.

R-Tree en varianten

De R-Tree, geïntroduceerd door Guttman in 1984, indexeert geometrieën op omsluitende rechthoeken. Elk boomknooppunt slaat de minimale omsluitende rechthoek (MBR) van zijn kinderen op. Een nabijheidsquery loopt de boom af, waarbij subbomen worden gesnoeid waarvan de MBR de query-enveloppe niet overlapt. Het slechtste geval is matig — overlapping tussen MBR's degradeert naar lineaire scan — maar het gemiddelde geval op echte data is uitstekend.

R*-Tree (1990) vermindert MBR-overlapping met slimmere knoopopsplitsingen en herinvoeging bij overloop. Het is de variant die de meeste productiesystemen tegenwoordig implementeren, inclusief de in-memory R-Tree in libspatialindex die door GeoPandas wordt gebruikt en in de ruimtelijke extensie van DuckDB.

Het bulk-laadverhaal is van belang. Het één voor één laden van een miljoen geometrieën in een R-Tree is traag en produceert een slecht gebalanceerde boom. De Sort-Tile-Recursive (STR) bulk-load bouwt de volledige boom in één doorloop na het sorteren van geometrieën langs een ruimtevullende curve, wat een vrijwel optimale MBR-indeling oplevert. Altijd bulk-laden bij het opzetten van een nieuwe index op een achterafgevulde dataset.

Wanneer de in-memory R-Tree nog steeds wint: client-side geometrie-indexen in een enkel operatorwerkstation (Qt-gebaseerde COP-clients, browser-side Leaflet/Mapbox supercluster-lagen) en stateloze geofence-services waarbij de geofence-set in RAM past. Een R-Tree met 100k geofences in libspatialindex bedient punt-in-polygoon-opzoekingen in 30–60 µs. PostGIS voor dezelfde workload, met netwerk-round-trip, is eerder 1–2 ms.

PostGIS-indexering — GiST vs SP-GiST vs BRIN

PostGIS is de standaard geospatiale ruggengraat voor de meeste defensie-fusiestacks waarmee Corvus heeft gewerkt, en de indexkeuze daarbinnen is niet triviaal. Zie onze uitgebreidere PostGIS voor defensie-walkthrough voor de volledige instelling; dit gedeelte is de samenvatting van de indexselectie.

GiST is de generalized-search-tree, die PostGIS gebruikt om een R-Tree-equivalent over geometrieën te implementeren. Het is de standaard. Past goed wanneer geometrieën heterogeen van grootte zijn (mixen van punten, lijnen, polygonen) en wanneer de workload lezen en schrijven combineert. Bouwtijd op 100M puntrijen is ruwweg 15–25 minuten op een snelle SSD met maintenance_work_mem afgesteld op 2 GB.

SP-GiST (space-partitioned GiST) implementeert quadtrees en k-d bomen. Sneller op workloads met alleen punten waar data gelijkmatig verdeeld is. Wij hebben SP-GiST gemeten als 1,4–1,8× sneller dan GiST voor pure punt-nabijheidsquery's op een tracktabel van 50M rijen, met een 25% kleinere indexvoetafdruk.

BRIN (block range index) is de goedkope optie wanneer data al fysiek geclusterd is op locatie — bijvoorbeeld wanneer trackinvoer is gepartitioneerd per regio en fysiek in geografische volgorde wordt toegevoegd. BRIN-indexen zijn klein (kilobytes voor tabellen die gigabytes aan GiST nodig hebben) en nuttig als secundair filter, niet als primaire ruimtelijke index. Ze blinken uit op koude archiefpartities.

Het gecombineerde ruimtelijk-temporele indexpatroon: voor workloads "binnen 5 km in de afgelopen 60 seconden" moet u niet proberen een enkele meerkolomsindex te bouwen. Bouw in plaats daarvan een GiST op geom en een B-tree op ts, en partitioneer de tabel vervolgens op tijd. De queryplanner combineert beide, en partitiesnoei elimineert 99% van de data voordat er ruimtelijk werk plaatsvindt. Echte queryplannen op partities van een miljoen rijen beantwoorden in 4–12 ms. Dezelfde query zonder partitiesnoei, op dezelfde geïndexeerde tabel, is 200–400 ms.

Hybride tijdreeks + geospatiale stack

Defensietracks zijn in de kern tijdreeksen. Elke trackupdate is een toevoeging. Leesbewerkingen zijn overwegend "laatste positie per zender" en "spoor van de afgelopen N minuten." De hybride stack is van belang.

TimescaleDB hypertabellen met PostGIS. Een hypertabel partitioneert automatisch op tijdblokken (1-uurse of 6-uursblokken voor feeds met hoog volume). PostGIS GiST-indexen worden per blok gebouwd. Compressie op blokken ouder dan 24 uur levert 8–14× opslagreductie op. Continue aggregaten berekenen per-H3-cel-uurlijkse samenvattingen voor. Dit is de aanbevolen startstack voor de meeste defensie-fusie-implementaties.

kdb+/q voor de gevallen met de hoogste doorvoer. Wanneer het platform honderdduizenden trackupdates per seconde moet verwerken — grote radarnetwerken gefusioneerd met multi-source ESM — blijft kdb+ kolomopslag met q-sql toonaangevend. q-sql is sober, de licentie is duur, maar de doorvoer is reëel. Het geospatiale verhaal is handgemaakt (H3 of S2 cel-ID's als gewone long-kolommen) in plaats van een native GIS-extensie.

ClickHouse met geohash-kolommen. ClickHouse verwerkt de analytische-herhalingslaag goed — herhaal de afgelopen zeven dagen tracks tegen een nieuw correlatiealgoritme. Geohash-kolommen (variabele-lengte base32-strings, prefix-gelijkheid = begrenzingsvak-insluiting) zijn de pragmatische index. ClickHouse 24.x heeft native geoDistance- en S2-functies toegevoegd; op een historische tracktabel van 5 miljard rijen lost een 10 km-nabijheidsscan op in 1–3 seconden. Niet interactief, maar acceptabel voor analystworkloads.

Indexen voor het operationele beeld

Het gemeenschappelijk operationeel beeld (COP) is de canonieke consument van geospatiale indexen. Honderden tot duizenden operatorsessies, elk met tracks binnen een viewport, die 1–4 keer per seconde vernieuwen. Zonder een tweelaagsculling-architectuur sterft de backend als eerste.

Server-side culling. De server past het viewport-begrenzingsvak toe als een ruimtelijke indexquery, past vervolgens het tijdvensterfilter toe en vervolgens entiteitstype- en machtigingsfilters. Het resultaat is een begrensd payload — doorgaans afgetopt op 5.000 tracks per respons om de berichtgrootte voorspelbaar te houden. Op een correct geïndexeerde PostGIS-hypertabel is dit 6–20 ms per sessie.

Client-side culling. De client ontvangt een iets grotere enveloppe dan de zichtbare viewport (zodat pannen niet onmiddellijk een herlaad activeert), onderhoudt een in-memory R-Tree van tracks en rendert alleen wat binnen het zichtbare canvas valt. De R-Tree verwerkt pannen, zoomen en hover-raaktests lokaal op 60 FPS zonder server-round-trips.

De dubbele laag is wat schaalt naar duizenden gelijktijdige sessies. Server-side culling begrenst de backendkosten. Client-side culling begrenst de frontendkosten. Elke laag afzonderlijk breekt. Dit patroon is essentieel of de COP nu een thick client is (Qt, .NET) of een browserkaart (Mapbox GL, MapLibre, deck.gl) — zie de bredere pijplijnreferentie in deel 1 van onze defensie-fusiepijplijnserie.

Migratiepraktijk

De migratie van "alles in één tabel zonder ruimtelijke index" naar een correct geïndexeerde, gepartitioneerde, hypertabel-ondersteunde opslag is waar de meeste defensie-dataprogramma's struikelen. Drie regels uit leveringservaring:

Dubbel schrijven vóór overzetting. De nieuwe geïndexeerde opslag draait minimaal twee operationele cycli parallel aan de legacy-tabel (doorgaans twee weken). Schrijfbewerkingen gaan naar beide. Leesbewerkingen verschuiven geleidelijk. Terugdraaien is een configuratiemarkering, geen databasemigratie.

Schema-evolutiediscipline. Een kolom toevoegen aan een hypertabel van 500 GB met volledige GiST-indexering is geen ALTER TABLE van 5 seconden. Plan kolomtoevoegingen als doelbewuste releases. Gebruik JSONB-payloads voor velden onder experimentatie; promoveer stabiele velden naar getypeerde kolommen zodra het schema zich heeft gestabiliseerd.

Achterafvullen in tijdgeordende stukken. Historische trackdata in omgekeerde chronologische volgorde (nieuwste eerst) in de nieuwe hypertabel herstellen betekent dat het operationeel relevante venster als eerste querybaar is, terwijl oudere stukken op de achtergrond worden ingevoerd. Wacht niet op de volledige achterafvulling voordat leesbewerkingen worden overgeschakeld.