Indexation géospatiale pour la défense : H3, S2, R-Tree et la requête au million de pistes

Le problème de la requête au million de pistes

Une requête opérateur courante dans une plateforme de fusion de défense s'écrit : « montrez-moi tout ce qui se trouve à moins de 5 km de ce point dans les 60 dernières secondes. » Cela paraît trivial. Sur une table de cent millions de mises à jour de pistes, écrites par des récepteurs AIS, des flux ADS-B, des pistes radar, des ESM et de la télémétrie de drones, une implémentation naïve s'effondre en moins de trois semaines de trafic en production.

La requête naïve est un scan séquentiel. SELECT * FROM tracks WHERE ST_DWithin(geom, $point, 5000) AND ts > now() - interval '60 seconds'. Sur une table de cent millions de lignes sans index spatial, cela représente 12 à 40 secondes selon le disque. Avec mille opérateurs rafraîchissant chacun toutes les 2 secondes, la base de données brûle. La solution n'est pas du matériel plus rapide. La solution est un index spatial — et le choix de l'index dicte tout en aval : débit d'ingestion, latence de requête, empreinte de stockage, et coût du sharding distribué.

Cet article parcourt les quatre familles d'index qui comptent pour la défense : H3, S2, la lignée R-Tree, et le trio PostGIS GiST/SP-GiST/BRIN. Puis il couvre les motifs hybrides temporel-géospatial, l'architecture de culling à double couche pour l'image opérationnelle commune, et l'histoire de la migration.

H3 (hexagonal Uber)

H3 est un système de grille hexagonale hiérarchique. La planète est partitionnée en 122 cellules de base (10 pentagones, 112 hexagones), et chaque cellule de base se subdivise récursivement en sept enfants, jusqu'à la résolution 15. Une cellule à la résolution 9 mesure environ 0,1 km² — la taille d'un pâté de maisons. Une cellule à la résolution 6 est d'environ 36 km² — une bulle d'engagement opérationnel utile.

Les hexagones battent les carrés pour les requêtes de proximité car chaque voisin hexagonal est à la même distance du centroïde. Avec une grille carrée, les voisins diagonaux sont à 1,41× la distance des voisins d'arête — chaque calcul de distance doit traiter ce cas spécial. Avec les hexagones, un k-ring de rayon 3 produit exactement 37 cellules, toutes à distance prévisible. Une recherche de rayon 5 km devient : convertir le point de requête en cellule H3, étendre à un k-ring couvrant 5 km, récupérer toutes les pistes étiquetées avec ces ID de cellules, puis raffiner avec un ST_Distance exact.

Caractéristiques favorables à la défense : les ID de cellule H3 sont des entiers 64 bits, triviaux à indexer dans n'importe quel store KV. L'appartenance à une cellule est hashable, donc une piste avec une colonne H3 peut être shardée par préfixe de cellule sans logique sur mesure. Les agrégats au niveau de cellule (« combien de pistes par cellule H3-7 dans la dernière heure ») s'effondrent directement en un GROUP BY h3_index. Nous avons vu des tables de pistes indexées H3 répondre à des requêtes de proximité de 5 km en 8–14 ms sur des tables de 200 millions de lignes.

Google S2

S2 partitionne la sphère via une projection en quadtree sur la surface d'un cube inscrit. Chaque face est récursivement subdivisée en quatre enfants jusqu'au niveau 30, où les cellules font environ 1 cm². Le S2CellId est un entier 64 bits encodant la face de la cellule, la position le long d'une courbe de Hilbert, et le niveau. L'encodage de Hilbert est l'astuce : les cellules proches sur la sphère ont des ID proches, donc une plage BETWEEN sur la colonne entière se comporte comme une requête de plage spatiale.

Cet avantage arithmétique entier est quand S2 gagne. Si le store de travail est un SGBDR shardé, un KV plat (DynamoDB, Cassandra), ou un moteur de recherche (le geo_shape d'Elasticsearch utilise des arbres BKD mais les requêtes de plage sur S2CellIds sont tout aussi rapides), S2 garde la logique de proximité dans des comparaisons entières peu coûteuses. Aucune extension SIG requise.

H3 versus S2 en pratique : H3 est plus convivial pour le raisonnement à distance uniforme, les agrégations et les cellules lisibles par l'humain. S2 est plus convivial quand la couche de stockage n'a pas de support de géométrie et que vous travaillez avec des milliards de points sur une couverture mondiale où la distorsion pentagonale dans H3 (10 cellules par planète n'ont que 5 voisins au lieu de 6) crée des problèmes. Les équipes de surveillance maritime OTAN indexant des données AIS mondiales sont passées à S2 exactement pour cette raison. Les images aériennes régionales à portée continentale restent principalement sur H3.

R-Tree et variantes

Le R-Tree, introduit par Guttman en 1984, indexe les géométries par boîtes englobantes. Chaque nœud de l'arbre stocke le rectangle englobant minimum (MBR) de ses enfants. Une requête de proximité parcourt l'arbre, élaguant les sous-arbres dont le MBR n'intersecte pas l'enveloppe de requête. Le pire cas est mauvais — le chevauchement entre MBR dégénère en scan linéaire — mais le cas moyen sur données réelles est excellent.

R*-Tree (1990) réduit le chevauchement de MBR avec des splits de nœuds plus intelligents et la réinsertion en cas de débordement. C'est la variante que la plupart des systèmes de production implémentent aujourd'hui, y compris le R-Tree en mémoire à l'intérieur de libspatialindex utilisé par GeoPandas et à l'intérieur de l'extension spatiale de DuckDB.

L'histoire du bulk-load compte. Charger un million de géométries une à une dans un R-Tree est lent et produit un arbre mal équilibré. Le bulk-load Sort-Tile-Recursive (STR) construit l'arbre entier en une seule passe après avoir trié les géométries le long d'une courbe de remplissage de l'espace, donnant une disposition MBR quasi optimale. Toujours bulk-load lors de la mise en place d'un nouvel index sur un jeu de données rétrocomblé.

Quand le R-Tree en mémoire l'emporte encore : index de géométrie côté client à l'intérieur d'un seul poste d'opérateur (clients d'image opérationnelle commune basés sur Qt, couches supercluster Leaflet/Mapbox côté navigateur), et services de géoclôture sans état où l'ensemble de géoclôtures tient en RAM. Un R-Tree de 100k géoclôtures dans libspatialindex sert les recherches point-dans-polygone en 30–60 µs. PostGIS pour la même charge de travail, avec aller-retour réseau, est plus proche de 1–2 ms.

Indexation PostGIS — GiST vs SP-GiST vs BRIN

PostGIS est l'épine dorsale géospatiale par défaut pour la plupart des piles de fusion de défense que Corvus a touchées, et le choix d'index à l'intérieur n'est pas trivial. Voir notre guide PostGIS pour la défense plus approfondi pour la configuration complète ; cette section est le résumé de sélection d'index.

GiST est l'arbre de recherche généralisé, que PostGIS utilise pour implémenter un équivalent R-Tree sur les géométries. C'est le défaut. Convient bien quand les géométries sont hétérogènes en taille (mélangeant points, lignes, polygones) et quand la charge de travail mélange lecture et écriture. Le temps de build sur 100M lignes de points est d'environ 15–25 minutes sur un SSD rapide avec maintenance_work_mem réglé à 2 Go.

SP-GiST (GiST partitionné par l'espace) implémente des quadtrees et des k-d trees. Plus rapide sur les charges de travail uniquement points où les données sont uniformément distribuées. Nous avons mesuré SP-GiST 1,4–1,8× plus rapide que GiST pour les requêtes de proximité de points purs sur une table de pistes de 50M lignes, avec une empreinte d'index 25% plus petite.

BRIN (block range index) est l'option économique quand les données sont déjà physiquement groupées par localisation — par exemple, quand les insertions de pistes sont partitionnées par région et ajoutées physiquement en ordre géographique. Les index BRIN sont minuscules (kilooctets pour des tables qui nécessitent des gigaoctets de GiST) et utiles comme filtre secondaire, pas comme index spatial primaire. Ils brillent sur les partitions d'archive froides.

Le motif d'index combiné spatial-temporel : pour les charges « à moins de 5 km dans les 60 dernières secondes », n'essayez pas de construire un seul index multi-colonnes. Construisez plutôt un GiST sur geom et un B-tree sur ts, puis partitionnez la table par temps. Le planificateur de requêtes combine les deux, et l'élagage de partition élimine 99% des données avant tout travail spatial. Les plans de requête réels sur des partitions d'un million de lignes répondent en 4–12 ms. La même requête sans élagage de partition, sur la même table indexée, prend 200–400 ms.

Hybride séries temporelles + géospatial

Les pistes de défense sont des séries temporelles au cœur. Chaque mise à jour de piste est un ajout. Les lectures sont principalement « dernière position par émetteur » et « traînée des N dernières minutes ». La pile hybride compte.

Hypertables TimescaleDB avec PostGIS. Une hypertable partitionne automatiquement par chunks temporels (chunks de 1 heure ou 6 heures pour les flux à haut volume). Les index GiST PostGIS sont construits par chunk. La compression sur les chunks de plus de 24 heures donne 8–14× de réduction de stockage. Les agrégats continus pré-calculent des résumés horaires par cellule H3. C'est la pile de départ recommandée pour la plupart des déploiements de fusion de défense.

kdb+/q pour les cas de débit le plus élevé. Quand la plateforme doit absorber plusieurs centaines de milliers de mises à jour de pistes par seconde — grands réseaux radar fusionnés avec ESM multi-sources — le stockage en colonnes de kdb+ avec q-sql reste le meilleur de sa catégorie. q-sql est austère, la licence est chère, mais le débit est réel. L'histoire géospatiale est faite à la main (ID de cellules H3 ou S2 comme colonnes long régulières) plutôt qu'une extension GIS native.

ClickHouse avec colonnes geohash. ClickHouse gère bien la couche de rejeu analytique — rejouer les sept derniers jours de pistes contre un nouvel algorithme de corrélation. Les colonnes geohash (chaînes base32 de longueur variable, égalité de préfixe = contenance dans une boîte englobante) sont l'index pragmatique. ClickHouse 24.x a ajouté les fonctions natives geoDistance et S2 ; sur une table de pistes historiques de 5 milliards de lignes, un scan de proximité de 10 km se résout en 1–3 secondes. Pas interactif, mais acceptable pour les charges de travail d'analystes.

Index pour l'image opérationnelle

L'image opérationnelle commune (COP) est le consommateur canonique des index géospatiaux. Des centaines à des milliers de sessions d'opérateurs, chacune rendant les pistes dans une fenêtre d'affichage, rafraîchissant 1–4 fois par seconde. Sans une architecture de culling à double couche, le backend meurt en premier.

Culling côté serveur. Le serveur applique la boîte englobante de la fenêtre d'affichage comme requête d'index spatial, puis applique le filtre de fenêtre temporelle, puis applique les filtres de type d'entité et d'habilitation. Le résultat est une charge utile bornée — typiquement plafonnée à 5 000 pistes par réponse pour garder la taille filaire prévisible. Sur une hypertable PostGIS correctement indexée, c'est 6–20 ms par session.

Culling côté client. Le client reçoit une enveloppe légèrement plus grande que la fenêtre d'affichage visible (pour que le panoramique ne déclenche pas immédiatement un re-fetch), maintient un R-Tree en mémoire des pistes, et ne rend que ce qui est à l'intérieur du canvas visible. Le R-Tree gère panoramique, zoom et test de survol localement à 60 FPS sans aller-retour serveur.

La double couche est ce qui scale à des milliers de sessions concurrentes. Le culling côté serveur plafonne le coût backend. Le culling côté client plafonne le coût frontend. L'une ou l'autre couche seule casse. Ce motif est essentiel que le COP soit un client lourd (Qt, .NET) ou une carte navigateur (Mapbox GL, MapLibre, deck.gl) — voir la référence de pipeline plus large dans la partie 1 de notre série de pipeline de fusion de défense.

Réalités de migration

La migration de « tout dans une seule table sans index spatial » vers un store correctement indexé, partitionné et soutenu par hypertable est l'endroit où la plupart des programmes de données de défense trébuchent. Trois règles issues de l'expérience de livraison :

Double écriture avant le basculement. Le nouveau store indexé tourne en parallèle avec la table héritée pendant au moins deux cycles opérationnels (typiquement deux semaines). Les écritures vont vers les deux. Les lectures basculent graduellement. Le rollback est un drapeau de configuration, pas une migration de base de données.

Discipline d'évolution de schéma. Ajouter une colonne à une hypertable de 500 Go avec une indexation GiST complète n'est pas un ALTER TABLE de 5 secondes. Planifiez les ajouts de colonnes comme des releases délibérées. Utilisez des charges utiles JSONB pour les champs en expérimentation ; promouvez les champs stables en colonnes typées une fois que le schéma s'est stabilisé.

Rétrocomblement en chunks ordonnés temporellement. Restaurer les données historiques de pistes dans la nouvelle hypertable en ordre chronologique inverse (le plus récent en premier) signifie que la fenêtre opérationnellement pertinente est interrogeable en premier, tandis que les chunks plus anciens sont ingérés en arrière-plan. N'attendez pas le rétrocomblement complet avant de basculer les lectures.