Indeksowanie geoprzestrzenne dla obronności: H3, S2, R-Tree i zapytanie o milion śladów

Problem zapytania o milion śladów

Typowe zapytanie operatora w obronnej platformie fuzji brzmi: „pokaż mi wszystko w promieniu 5 km od tego punktu w ciągu ostatnich 60 sekund." Brzmi trywialnie. Na tabeli stu milionów aktualizacji śladów, zapisywanych przez odbiorniki AIS, kanały ADS-B, ślady radarowe, ESM i telemetrię dronów, naiwna implementacja załamuje się w ciągu trzech tygodni ruchu produkcyjnego.

Naiwne zapytanie to sequential scan. SELECT * FROM tracks WHERE ST_DWithin(geom, $point, 5000) AND ts > now() - interval '60 seconds'. Na tabeli stu milionów wierszy bez indeksu przestrzennego to 12 do 40 sekund w zależności od dysku. Przy tysiącu operatorów odświeżających co 2 sekundy baza płonie. Rozwiązaniem nie jest szybszy sprzęt. Rozwiązaniem jest indeks przestrzenny — a wybór indeksu dyktuje wszystko downstream: przepustowość ingest, opóźnienie zapytania, ślad pamięci masowej i koszt sharding rozproszonego.

Ten artykuł obchodzi cztery rodziny indeksów, które mają znaczenie dla obronności: H3, S2, rodowód R-Tree i trio PostGIS GiST/SP-GiST/BRIN. Następnie obejmuje hybrydowe wzorce time-series, dwuwarstwową architekturę cullingu dla wspólnego obrazu operacyjnego i historię migracji.

H3 (Uber heksagonalny)

H3 to hierarchiczny heksagonalny system siatki. Planeta jest podzielona na 122 komórki bazowe (10 pięciokątów, 112 sześciokątów), a każda komórka bazowa rekursywnie dzieli się na siedem dzieci, aż do rozdzielczości 15. Komórka przy rozdzielczości 9 to z grubsza 0,1 km² — wielkość bloku miejskiego. Komórka przy rozdzielczości 6 to około 36 km² — użyteczna operacyjna bańka angażowania.

Sześciokąty biją kwadraty w zapytaniach o bliskość, ponieważ każdy heksagonalny sąsiad siedzi w tej samej odległości od centroidu. Z siatką kwadratową sąsiedzi diagonalni są 1,41× dalej niż sąsiedzi krawędzi — każde obliczenie odległości musi to specjalnie obsługiwać. Z sześciokątami k-ring o promieniu 3 daje dokładnie 37 komórek, wszystkie w przewidywalnej odległości. Wyszukiwanie o promieniu 5 km staje się: konwertuj punkt zapytania na komórkę H3, rozszerz do k-ring pokrywającego 5 km, pobierz wszystkie ślady oznaczone tymi ID komórek, następnie udoskonal dokładnym ST_Distance.

Cechy przyjazne obronności: ID komórek H3 to 64-bitowe liczby całkowite, trywialne do zaindeksowania w jakimkolwiek KV store. Członkostwo komórki jest hashowalne, więc ślad z kolumną H3 może być shardowany przez prefiks komórki bez bespoke logic. Agregaty na poziomie komórki („ile śladów na komórkę H3-7 w ciągu ostatniej godziny") zwija się prosto do GROUP BY h3_index. Widzieliśmy tabele śladów zaindeksowane H3 odpowiadające na zapytania o bliskość 5 km w 8–14 ms na tabelach 200 milionów wierszy.

Google S2

S2 dzieli sferę przez quadtree projekcji na powierzchnię wpisanego sześcianu. Każda ściana jest rekursywnie dzielona na cztery dzieci aż do poziomu 30, gdzie komórki mają około 1 cm². S2CellId to 64-bitowa liczba całkowita kodująca ścianę komórki, pozycję wzdłuż krzywej Hilberta i poziom. Kodowanie Hilberta jest trikiem: komórki bliskie na sferze mają bliskie ID, więc zakres BETWEEN na kolumnie integer zachowuje się jak zapytanie o zakres przestrzenny.

Ta przewaga arytmetyki integer jest tym, kiedy S2 wygrywa. Jeśli działający store to sharded RDBMS, płaski KV (DynamoDB, Cassandra) lub silnik wyszukiwania (geo_shape Elasticsearch używa drzew BKD, ale zapytania o zakres na S2CellId są równie szybkie), S2 utrzymuje logikę bliskości wewnątrz tanich porównań integer. Brak wymaganego rozszerzenia GIS.

H3 vs S2 w praktyce: H3 jest przyjaźniejszy dla rozumowania o jednolitej odległości, agregacji i komórek czytelnych dla człowieka. S2 jest przyjaźniejszy, gdy warstwa magazynu nie ma wsparcia geometrii i pracujesz z miliardami punktów w globalnym pokryciu, gdzie zniekształcenia pięciokątów w H3 (10 komórek na planetę ma tylko 5 sąsiadów zamiast 6) tworzą problemy. Zespoły dozoru morskiego NATO indeksujące globalne dane AIS przeszły na S2 z dokładnie tego powodu. Regionalne obrazy powietrzne ze zakresem kontynentalnym głównie zostają na H3.

R-Tree i warianty

R-Tree, wprowadzone przez Guttmana w 1984, indeksuje geometrie po bounding boxach. Każdy węzeł drzewa przechowuje minimalny prostokąt opisujący (MBR) swoich dzieci. Zapytanie o bliskość chodzi po drzewie, przycinając poddrzewa, których MBR nie przecina się z kopertą zapytania. Najgorszy przypadek jest słaby — nakładanie się MBR degraduje do liniowego skanu — ale średni przypadek na realnych danych jest doskonały.

R*-Tree (1990) redukuje nakładanie MBR mądrzejszymi podziałami węzłów i ponownym wstawianiem przy overflow. To wariant, który większość systemów produkcyjnych dziś implementuje, w tym in-memory R-Tree wewnątrz libspatialindex używany przez GeoPandas i wewnątrz spatial extension DuckDB.

Historia bulk-load ma znaczenie. Ładowanie miliona geometrii pojedynczo do R-Tree jest powolne i produkuje słabo zbalansowane drzewo. Bulk-load Sort-Tile-Recursive (STR) buduje całe drzewo w jednym przebiegu po sortowaniu geometrii wzdłuż krzywej wypełniającej przestrzeń, dając niemal optymalny układ MBR. Zawsze bulk-load przy stawianiu nowego indeksu na backfilled datasetcie.

Kiedy in-memory R-Tree wciąż wygrywa: client-side indeksy geometrii wewnątrz pojedynczej stacji roboczej operatora (klienty wspólnego obrazu operacyjnego oparte na Qt, browser-side warstwy Leaflet/Mapbox supercluster) oraz stateless serwisy geofence, gdzie zestaw geofence mieści się w RAM. R-Tree 100 tys. geofence w libspatialindex obsługuje wyszukiwania point-in-polygon w 30–60 µs. PostGIS dla tego samego obciążenia, z network round-trip, jest bliżej 1–2 ms.

Indeksowanie PostGIS — GiST vs SP-GiST vs BRIN

PostGIS to domyślny kręgosłup geoprzestrzenny dla większości obronnych stosów fuzji, których Corvus dotknął, a wybór indeksu wewnątrz niego jest nietrywialny. Zobacz nasz głębszy przewodnik po PostGIS dla obronności dla pełnego setup; ta sekcja to podsumowanie wyboru indeksu.

GiST to generalized-search-tree, którego PostGIS używa do implementacji R-Tree-equivalent nad geometriami. To domyślny. Pasuje dobrze, gdy geometrie są heterogeniczne rozmiarem (mieszanie punktów, linii, poligonów) i gdy obciążenie miesza odczyt i zapis. Czas budowy na 100M wierszy punktowych to z grubsza 15–25 minut na szybkim SSD z maintenance_work_mem dostrojonym do 2 GB.

SP-GiST (space-partitioned GiST) implementuje quadtree i drzewa k-d. Szybszy na obciążeniach tylko-punktowych, gdzie dane są jednolicie rozłożone. Zmierzyliśmy SP-GiST 1,4–1,8× szybszy niż GiST dla czystych zapytań o bliskość punktów na tabeli śladów 50M wierszy, z 25% mniejszym śladem indeksu.

BRIN (block range index) to tania opcja, gdy dane są już fizycznie sklastrowane według lokalizacji — na przykład gdy wstawienia śladów są partycjonowane według regionu i fizycznie dodawane w porządku geograficznym. Indeksy BRIN są maleńkie (kilobajty dla tabel, które potrzebują gigabajtów GiST) i użyteczne jako wtórny filtr, nie jako pierwotny indeks przestrzenny. Świecą na zimnych partycjach archiwum.

Wzorzec łączonego indeksu spatial-temporal: dla obciążeń „w promieniu 5 km w ostatnich 60 sekundach" nie próbuj budować pojedynczego wielokolumnowego indeksu. Zamiast tego zbuduj GiST na geom i B-tree na ts, następnie partycjonuj tabelę po czasie. Query planner łączy obydwa, a partition pruning eliminuje 99% danych przed jakąkolwiek pracą przestrzenną. Realne plany zapytań na partycjach miliona wierszy odpowiadają w 4–12 ms. To samo zapytanie bez partition pruning, na tej samej zaindeksowanej tabeli, to 200–400 ms.

Hybryda Time-Series + geoprzestrzenna

Ślady obronne to time-series u serca. Każda aktualizacja śladu to append. Odczyty to przeważnie „najnowsza pozycja per emiter" i „trail z ostatnich N minut." Stos hybrydowy ma znaczenie.

Hypertable TimescaleDB z PostGIS. Hypertable partycjonuje automatycznie po chunkach czasu (chunki 1-godzinne lub 6-godzinne dla kanałów o wysokim wolumenie). Indeksy PostGIS GiST są budowane per chunk. Kompresja na chunkach starszych niż 24 godziny daje 8–14× redukcji magazynu. Continuous aggregates pre-obliczają godzinne podsumowania per komórka H3. To rekomendowany startowy stos dla większości obronnych wdrożeń fuzji.

kdb+/q dla przypadków najwyższej przepustowości. Gdy platforma musi wchłonąć kilkaset tysięcy aktualizacji śladów na sekundę — duże sieci radarowe zfuzjowane z multi-source ESM — kolumnowy magazyn kdb+ z q-sql pozostaje best-of-breed. q-sql jest surowy, licencjonowanie drogie, ale przepustowość jest realna. Historia geoprzestrzenna jest hand-rolled (ID komórek H3 lub S2 jako zwykłe kolumny long) zamiast natywnego rozszerzenia GIS.

ClickHouse z kolumnami geohash. ClickHouse dobrze obsługuje warstwę analitycznego odtwarzania — odtwarzaj ostatnich siedem dni śladów względem nowego algorytmu korelacji. Kolumny geohash (stringi base32 o zmiennej długości, równość prefiksu = zawieranie bounding box) to pragmatyczny indeks. ClickHouse 24.x dodał natywne funkcje geoDistance i S2; na tabeli historycznych śladów 5 miliardów wierszy, skan bliskości 10 km rozwiązuje się w 1–3 sekundy. Nie interaktywne, ale akceptowalne dla obciążeń analityków.

Indeksy dla obrazu operacyjnego

Wspólny obraz operacyjny (COP) to kanoniczny konsument indeksów geoprzestrzennych. Setki do tysięcy sesji operatorów, każda renderująca ślady w viewport, odświeżająca 1–4 razy na sekundę. Bez dwuwarstwowej architektury cullingu backend ginie pierwszy.

Server-side culling. Serwer aplikuje bounding box viewportu jako zapytanie indeksu przestrzennego, następnie aplikuje filtr okna czasowego, następnie aplikuje filtry typu encji i klauzuli. Wynikiem jest ograniczony payload — zazwyczaj ograniczony do 5 000 śladów na odpowiedź, aby rozmiar drutu był przewidywalny. Na właściwie zaindeksowanej hypertable PostGIS to 6–20 ms na sesję.

Client-side culling. Klient otrzymuje nieco większą kopertę niż widoczny viewport (aby panoramowanie nie wyzwalało natychmiast refetch), utrzymuje in-memory R-Tree śladów i renderuje tylko to, co jest wewnątrz widocznego płótna. R-Tree obsługuje pan, zoom i hover hit-testing lokalnie przy 60 FPS bez round-tripów serwera.

Dwie warstwy są tym, co skaluje się do tysięcy współbieżnych sesji. Server-side culling ogranicza koszt backendu. Client-side culling ogranicza koszt frontendu. Żadna warstwa sama się łamie. Ten wzorzec jest niezbędny, czy COP to thick client (Qt, .NET) czy mapa przeglądarki (Mapbox GL, MapLibre, deck.gl) — zobacz szerszą referencję potoku w części 1 naszej serii o potoku fuzji obronnej.

Realia migracji

Migracja z „wszystko w jednej tabeli bez indeksu przestrzennego" do właściwie zaindeksowanego, partycjonowanego, hypertable-backed store to miejsce, gdzie większość obronnych programów danych się potyka. Trzy reguły z doświadczenia dostarczania:

Dual-write przed cutover. Nowy zaindeksowany store działa równolegle z legacy tabelą przez co najmniej dwa cykle operacyjne (zazwyczaj dwa tygodnie). Zapisy idą do obu. Odczyty stopniowo się przesuwają. Rollback to flaga config, nie migracja bazy.

Dyscyplina ewolucji schematu. Dodanie kolumny do hypertable 500 GB z pełnym indeksowaniem GiST nie jest 5-sekundowym ALTER TABLE. Planuj dodawanie kolumn jako celowe wydania. Używaj payloadów JSONB dla pól pod eksperymentem; promuj stabilne pola do typowanych kolumn, gdy schemat się ustabilizuje.

Backfill w chunkach uporządkowanych po czasie. Przywracanie historycznych danych śladów do nowej hypertable w odwrotnym porządku chronologicznym (najnowsze pierwsze) oznacza, że operacyjnie istotne okno jest queryable pierwsze, podczas gdy starsze chunki ingestują w tle. Nie czekaj na pełny backfill przed przełączeniem odczytów.