Indexare Geospațială pentru Apărare: H3, S2, R-Tree și Interogarea cu Milioane de Urme

Problema Interogării cu Milioane de Urme

O interogare frecventă a unui operator într-o platformă de fuziune pentru apărare sună astfel: „arată-mi tot ce se află în 5 km de acest punct în ultimele 60 de secunde." Pare trivial. Pe un tabel cu o sută de milioane de actualizări de urme, generate de receptoare AIS, fluxuri ADS-B, urme radar, ESM și telemetrie de drone, o implementare naivă cedează în mai puțin de trei săptămâni de trafic de producție.

Interogarea naivă este o scanare secvențială. SELECT * FROM tracks WHERE ST_DWithin(geom, $point, 5000) AND ts > now() - interval '60 seconds'. Pe un tabel cu o sută de milioane de rânduri și fără index spațial, aceasta durează 12 până la 40 de secunde în funcție de disc. Cu o mie de operatori care actualizează la fiecare 2 secunde, baza de date se blochează. Soluția nu este hardware mai rapid. Soluția este un index spațial — iar alegerea indexului determină totul în aval: debitul de ingestie, latența interogărilor, amprenta de stocare și costul fragmentării distribuite.

Acest articol parcurge cele patru familii de indexuri importante pentru apărare: H3, S2, linia de descendență R-Tree și trio-ul PostGIS GiST/SP-GiST/BRIN. Apoi abordează pattern-urile hibride de serii temporale, arhitectura de culling pe două niveluri pentru imaginea operațională comună și procesul de migrare.

H3 (Uber Hexagonal)

H3 este un sistem de grilă hexagonală ierarhică. Planeta este împărțită în 122 de celule de bază (10 pentagoane, 112 hexagoane), iar fiecare celulă de bază se subdivizează recursiv în șapte celule copil, până la rezoluția 15. O celulă la rezoluția 9 are aproximativ 0,1 km² — dimensiunea unui bloc de oraș. O celulă la rezoluția 6 are aproximativ 36 km² — o bulă de angajament operațional utilă.

Hexagoanele sunt superioare pătratelor pentru interogările de proximitate deoarece fiecare vecin hexagonal se află la aceeași distanță față de centroid. Cu o grilă pătrată, vecinii diagonali sunt de 1,41× mai departe decât vecinii de margine — fiecare calcul de distanță trebuie să trateze acest caz special. Cu hexagoane, un k-ring de raza 3 produce exact 37 de celule, toate la distanță previzibilă. O căutare cu raza de 5 km devine: convertește punctul de interogare într-o celulă H3, extinde la un k-ring care acoperă 5 km, preia toate urmele etichetate cu acele ID-uri de celulă, apoi rafinează cu ST_Distance exact.

Caracteristici favorabile apărării: ID-urile celulelor H3 sunt întregi pe 64 de biți, trivial de indexat în orice magazin KV. Apartenența la celulă este hashabilă, deci o urmă cu o coloană H3 poate fi fragmentată după prefixul celulei fără logică personalizată. Agregatele la nivel de celulă („câte urme per celulă H3-7 în ultima oră") se reduc direct la un GROUP BY h3_index. Am văzut tabele de urme indexate H3 care răspund la interogări de proximitate de 5 km în 8–14 ms pe tabele de 200 de milioane de rânduri.

Google S2

S2 împarte sfera printr-o proiecție quadtree pe suprafața unui cub inscris. Fiecare față este subdivizată recursiv în patru celule copil până la nivelul 30, unde celulele au aproximativ 1 cm². S2CellId este un întreg pe 64 de biți care codifică fața celulei, poziția de-a lungul unei curbe Hilbert și nivelul. Codificarea Hilbert este cheia: celulele apropiate pe sferă au ID-uri apropiate, astfel că un interval BETWEEN pe coloana de întregi se comportă ca o interogare spațială de interval.

Avantajul aritmeticii pe întregi este momentul în care S2 câștigă. Dacă magazinul de lucru este un RDBMS fragmentat, un KV plat (DynamoDB, Cassandra) sau un motor de căutare (geo_shape din Elasticsearch folosește arbori BKD, dar interogările de interval pe S2CellIds sunt la fel de rapide), S2 păstrează logica de proximitate în comparații ieftine de întregi. Nu este necesară nicio extensie GIS.

H3 față de S2 în practică: H3 este mai prietenos pentru raționamentul la distanță uniformă, agregări și celule lizibile de om. S2 este mai prietenos când nivelul de stocare nu are suport pentru geometrie și lucrezi cu miliarde de puncte la acoperire globală, unde distorsiunea pentagonală din H3 (10 celule per planetă au doar 5 vecini în loc de 6) creează probleme. Echipele de supraveghere maritimă NATO care indexează date AIS globale au trecut la S2 exact din acest motiv. Imaginile aeriene regionale cu scop continental rămân în general pe H3.

R-Tree și Variantele Sale

R-Tree-ul, introdus de Guttman în 1984, indexează geometriile prin casete de delimitare. Fiecare nod al arborelui stochează dreptunghiul de delimitare minim (MBR) al copiilor săi. O interogare de proximitate parcurge arborele, eliminând subarborii al căror MBR nu intersectează anvelopa interogării. Cel mai rău caz este slab — suprapunerea între MBR-uri degradează la o scanare liniară — dar cazul mediu pe date din lumea reală este excelent.

R*-Tree (1990) reduce suprapunerea MBR cu diviziuni de noduri mai inteligente și reinserție la depășire. Este varianta pe care o implementează astăzi majoritatea sistemelor de producție, inclusiv R-Tree-ul în memorie din libspatialindex folosit de GeoPandas și din extensia spațială DuckDB.

Povestea încărcării în bloc contează. Încărcarea a un milion de geometrii una câte una într-un R-Tree este lentă și produce un arbore prost echilibrat. Încărcarea în bloc Sort-Tile-Recursive (STR) construiește întregul arbore într-o singură trecere după sortarea geometriilor de-a lungul unei curbe de umplere a spațiului, producând un layout MBR aproape optim. Încarcă întotdeauna în bloc când configurezi un nou index pe un set de date completat retroactiv.

Când R-Tree-ul în memorie câștigă totuși: indexuri de geometrie pe partea clientului într-o singură stație de lucru a operatorului (clienți de imagine operațională comună bazați pe Qt, straturi supercluster Leaflet/Mapbox pe browser) și servicii de geogarantare fără stare unde setul de geogarantări încape în RAM. Un R-Tree de 100k-geogarantări în libspatialindex deservește căutări punct-în-poligon în 30–60 µs. PostGIS pentru aceeași sarcină de lucru, cu dus-întors în rețea, este mai aproape de 1–2 ms.

Indexarea PostGIS — GiST vs SP-GiST vs BRIN

PostGIS este coloana vertebrală geospațială implicită pentru majoritatea stivelor de fuziune pentru apărare cu care a lucrat Corvus, iar alegerea indexului în cadrul acestuia nu este trivială. Consultați ghidul nostru aprofundat PostGIS pentru apărare pentru configurarea completă; această secțiune este rezumatul selectării indexului.

GiST este arborele de căutare generalizat, pe care PostGIS îl folosește pentru a implementa un echivalent R-Tree peste geometrii. Este implicit. Se potrivește bine când geometriile sunt eterogene ca dimensiune (amestecând puncte, linii, poligoane) și când sarcina de lucru combină citiri și scrieri. Timpul de construire pe 100M rânduri de puncte este aproximativ 15–25 minute pe un SSD rapid cu maintenance_work_mem ajustat la 2 GB.

SP-GiST (GiST partiționat spațial) implementează quadtree-uri și arbori k-d. Mai rapid pe sarcini de lucru cu puncte exclusiv unde datele sunt distribuite uniform. Am măsurat SP-GiST de 1,4–1,8× mai rapid decât GiST pentru interogări pure de proximitate punct pe un tabel de urme cu 50M rânduri, cu o amprentă de index cu 25% mai mică.

BRIN (index de interval de bloc) este opțiunea ieftină când datele sunt deja grupate fizic după locație — de exemplu, când inserările de urme sunt partiționare după regiune și adăugate fizic în ordine geografică. Indexurile BRIN sunt minuscule (kiloocteți pentru tabele care necesită gigaocteți de GiST) și utile ca filtru secundar, nu ca index spațial primar. Strălucesc pe partițiile de arhivă reci.

Pattern-ul indexului spațio-temporal combinat: pentru sarcini de lucru „în 5 km în ultimele 60 de secunde", nu încercați să construiți un singur index pe mai multe coloane. În schimb, construiți un GiST pe geom și un B-tree pe ts, apoi partiționați tabelul după timp. Planificatorul de interogări le combină pe amândouă, iar tăierea partițiilor elimină 99% din date înainte de orice lucru spațial. Planurile reale de interogări pe partițiile cu milioane de rânduri răspund în 4–12 ms. Aceeași interogare fără tăierea partițiilor, pe același tabel indexat, este de 200–400 ms.

Hibrid Serii Temporale + Geospațial

Urmele de apărare sunt în esență serii temporale. Fiecare actualizare a urmei este o adăugare. Citirile sunt predominant „ultima poziție per emițător" și „traseul ultimelor N minute." Stiva hibridă contează.

Hipertabele TimescaleDB cu PostGIS. Un hipertabel partiționează automat după fragmente de timp (fragmente de 1 oră sau 6 ore pentru fluxuri cu volum mare). Indexurile PostGIS GiST sunt construite per fragment. Compresia pe fragmentele mai vechi de 24 de ore produce o reducere a stocării de 8–14×. Agregatele continue pre-calculează rezumate orare per celulă H3. Aceasta este stiva de pornire recomandată pentru majoritatea implementărilor de fuziune pentru apărare.

kdb+/q pentru cazurile cu cel mai mare debit. Când platforma trebuie să absoarbă câteva sute de mii de actualizări de urme pe secundă — rețele radar mari fuzionate cu ESM multi-sursă — stocarea coloanară kdb+ cu q-sql rămâne cea mai bună soluție. q-sql este auster, licențierea este costisitoare, dar debitul este real. Povestea geospațială este implementată manual (ID-uri de celulă H3 sau S2 ca coloane lungi obișnuite) mai degrabă decât o extensie GIS nativă.

ClickHouse cu coloane geohash. ClickHouse gestionează bine nivelul de reluare analitică — reluarea ultimelor șapte zile de urme față de un nou algoritm de corelație. Coloanele geohash (șiruri base32 de lungime variabilă, egalitatea prefixului = containment cutie de delimitare) sunt indexul pragmatic. ClickHouse 24.x a adăugat funcții native geoDistance și S2; pe un tabel de urme istorice cu 5 miliarde de rânduri, o scanare de proximitate de 10 km se rezolvă în 1–3 secunde. Nu este interactivă, dar acceptabilă pentru sarcinile de lucru ale analiștilor.

Indexuri pentru Imaginea Operațională

Imaginea operațională comună (COP) este consumatorul canonic al indexurilor geospațiale. Sute până la mii de sesiuni de operatori, fiecare redând urme în cadrul unui viewport, actualizând de 1–4 ori pe secundă. Fără o arhitectură de culling pe două niveluri, backend-ul cedează primul.

Culling pe server. Serverul aplică caseta de delimitare a viewport-ului ca interogare de index spațial, apoi aplică filtrul de fereastră de timp, apoi aplică filtrele de tip entitate și autorizare. Rezultatul este un payload delimitat — de obicei limitat la 5.000 de urme per răspuns pentru a menține dimensiunea firului previzibilă. Pe un hipertabel PostGIS indexat corespunzător, aceasta este 6–20 ms per sesiune.

Culling pe client. Clientul primește o anvelopă ușor mai mare decât viewport-ul vizibil (astfel încât panoramarea nu declanșează imediat o reîncărcare), menține un R-Tree în memorie al urmelor și redă doar ceea ce se află în interiorul canvasului vizibil. R-Tree-ul gestionează local panoramarea, mărirea și testarea de accesare la hover la 60 FPS fără dus-întorsuri la server.

Stratul dublu este cel care scalează la mii de sesiuni concurente. Culling-ul pe server limitează costul backend-ului. Culling-ul pe client limitează costul frontend-ului. Oricare strat singur cedează. Acest pattern este esențial indiferent dacă COP-ul este un client gros (Qt, .NET) sau o hartă de browser (Mapbox GL, MapLibre, deck.gl) — consultați referința mai amplă a conductei în partea 1 a seriei noastre despre conducta de fuziune pentru apărare.

Realitățile Migrării

Migrarea de la „totul într-un singur tabel fără index spațial" la un magazin corect indexat, partiționat, susținut de hipertabel este locul unde se poticnesc majoritatea programelor de date pentru apărare. Trei reguli din experiența de livrare:

Scriere dublă înainte de comutare. Noul magazin indexat rulează în paralel cu tabelul moștenire pentru cel puțin două cicluri operaționale (de obicei două săptămâni). Scrierile merg la ambele. Citirile se deplasează treptat. Revenirea este un indicator de configurare, nu o migrare a bazei de date.

Disciplina evoluției schemei. Adăugarea unei coloane la un hipertabel de 500 GB cu indexare GiST completă nu este un ALTER TABLE de 5 secunde. Planificați adăugările de coloane ca versiuni deliberate. Utilizați sarcini utile JSONB pentru câmpurile în experimentare; promovați câmpurile stabile în coloane tipizate odată ce schema se stabilizează.

Completare în fragmente ordonate temporal. Restaurarea datelor istorice de urme în noul hipertabel în ordine cronologică inversă (cele mai noi primul) înseamnă că fereastra relevantă operațional este interogabilă mai întâi, în timp ce fragmentele mai vechi se ingerează în fundal. Nu așteptați completarea integrală înainte de a comuta citirile.