Геопросторове індексування для оборони: H3, S2, R-Tree та запит на мільйон треків

Проблема запиту на мільйон треків

Поширений запит оператора в оборонній фьюжн-платформі звучить так: "покажи мені все в межах 5 км від цієї точки за останні 60 секунд." Звучить тривіально. На таблиці зі ста мільйонами оновлень треків, записаних AIS-приймачами, ADS-B фідами, радарними треками, ESM та телеметрією дронів, наївна реалізація обвалюється протягом трьох тижнів продакшн-трафіку.

Наївний запит — це послідовний скан. SELECT * FROM tracks WHERE ST_DWithin(geom, $point, 5000) AND ts > now() - interval '60 seconds'. На таблиці зі ста мільйонів рядків без просторового індексу це 12–40 секунд залежно від диска. З тисячею операторів, які кожен оновлюється раз на 2 секунди, база даних згорає. Виправлення — не швидше залізо. Виправлення — просторовий індекс, і вибір індексу диктує усе далі по конвеєру: пропускну спроможність прийому, затримку запитів, обсяг сховища та вартість розподіленого шардингу.

Ця стаття проходить чотири сімейства індексів, що мають значення для оборони: H3, S2, лінію R-Tree та трійцю PostGIS GiST/SP-GiST/BRIN. Потім розглядає гібридні часові патерни, dual-layer culling-архітектуру для єдиного оперативного образу та історію міграції.

H3 (Uber Hexagonal)

H3 — це ієрархічна гексагональна сіткова система. Планета розділена на 122 базові комірки (10 п'ятикутників, 112 шестикутників), і кожна базова комірка рекурсивно ділиться на сім дочірніх, аж до резолюції 15. Комірка на резолюції 9 — приблизно 0.1 км², розмір міського кварталу. Комірка на резолюції 6 — близько 36 км², корисна оперативна бульбашка зіткнення.

Шестикутники перемагають квадрати для proximity-запитів, бо кожен гексагональний сусід знаходиться на однаковій центроїдній відстані. З квадратною сіткою діагональні сусіди в 1.41× далі за реберних — кожен розрахунок відстані має це окремо обробляти. З гексагонами k-ring радіуса 3 дає рівно 37 комірок, усі на передбачуваній відстані. Пошук радіусом 5 км стає: конвертувати точку запиту в комірку H3, розширити до k-ring, що покриває 5 км, отримати всі треки, помічені цими ID комірок, потім уточнити точним ST_Distance.

Оборонно-дружні характеристики: ID комірок H3 — 64-бітні цілі, тривіальні для індексування у будь-якому KV-сторі. Належність до комірки хешована, тож трек із колонкою H3 можна шардити за префіксом комірки без власної логіки. Агрегати рівня комірки ("скільки треків на H3-7 комірку за останню годину") згортаються прямо до GROUP BY h3_index. Ми бачили H3-індексовані таблиці треків, що відповідають на запити proximity 5 км за 8–14 мс на таблицях у 200 мільйонів рядків.

Google S2

S2 розділяє сферу через квадтрі-проєкцію на поверхню вписаного куба. Кожна грань рекурсивно ділиться на чотири дочірні аж до рівня 30, де комірки мають близько 1 см². S2CellId — 64-бітне ціле, що кодує грань комірки, позицію вздовж кривої Гільберта та рівень. Гільбертове кодування — це фокус: комірки, близькі на сфері, мають близькі ID, тож BETWEEN-діапазон на цілому стовпці поводиться як просторовий запит діапазону.

Ця перевага цілочисельної арифметики — там, де S2 виграє. Якщо робоче сховище — шардована RDBMS, плоский KV (DynamoDB, Cassandra) або пошуковий движок (geo_shape в Elasticsearch використовує BKD-дерева, але запити діапазонів на S2CellIds однаково швидкі), S2 тримає proximity-логіку всередині дешевих цілочисельних порівнянь. Не потрібне жодне GIS-розширення.

H3 vs S2 на практиці: H3 дружніший для рівновіддалених міркувань, агрегацій та читабельних людиною комірок. S2 дружніший, коли у шарі сховища немає підтримки геометрії і ви працюєте з мільярдами точок глобального покриття, де п'ятикутникові спотворення в H3 (10 комірок на планету мають лише 5 сусідів замість 6) створюють проблеми. Команди NATO морського спостереження, що індексують глобальні AIS-дані, перейшли на S2 саме з цієї причини. Регіональні повітряні картини з континентальним обсягом переважно залишаються на H3.

R-Tree та варіанти

R-Tree, представлений Гутманом у 1984, індексує геометрії за bounding box'ами. Кожен вузол дерева зберігає мінімальний обмежувальний прямокутник (MBR) своїх дочірніх. Proximity-запит проходить дерево, відсікаючи піддерева, чий MBR не перетинається з обвідною запиту. Найгірший випадок поганий — перекриття між MBR деградує до лінійного скану — але середній випадок на реальних даних відмінний.

R*-Tree (1990) зменшує перекриття MBR розумнішими розщепленнями вузлів і повторною вставкою при переповненні. Це варіант, який сьогодні реалізують більшість продакшн-систем, включно з in-memory R-Tree всередині libspatialindex, що його використовують GeoPandas і spatial extension у DuckDB.

Історія bulk-load має значення. Завантаження мільйона геометрій по одній у R-Tree повільне й дає погано збалансоване дерево. Sort-Tile-Recursive (STR) bulk-load будує все дерево за один прохід після сортування геометрій вздовж кривої заповнення простору, даючи майже оптимальну розкладку MBR. Завжди bulk-load'те при підніманні нового індексу на backfill'ованому датасеті.

Коли in-memory R-Tree все ще виграє: client-side геометричні індекси всередині однієї робочої станції оператора (Qt-based COP-клієнти, browser-side Leaflet/Mapbox supercluster-шари) та stateless геозональні сервіси, де набір геозон вміщується в RAM. R-Tree зі 100k геозон у libspatialindex обслуговує point-in-polygon lookups за 30–60 мкс. PostGIS на тому ж навантаженні з мережевим round-trip ближче до 1–2 мс.

Індексування PostGIS — GiST vs SP-GiST vs BRIN

PostGIS — дефолтний геопросторовий хребет для більшості оборонних фьюжн-стеків, до яких торкався Corvus, і вибір індексу всередині нього нетривіальний. Див. наш детальніший огляд PostGIS для оборони щодо повного налаштування; цей розділ — підсумок вибору індексу.

GiST — узагальнене пошукове дерево, яке PostGIS використовує для реалізації R-Tree-еквівалента над геометріями. Це дефолт. Добре підходить, коли геометрії гетерогенні за розміром (змішуючи точки, лінії, полігони) і коли навантаження змішує читання і запис. Час побудови на 100M рядків точок — приблизно 15–25 хвилин на швидкому SSD з maintenance_work_mem, налаштованим на 2 ГБ.

SP-GiST (space-partitioned GiST) реалізує квадтрі та k-d дерева. Швидший на навантаженнях лише з точками, де дані рівномірно розподілені. Ми вимірювали SP-GiST у 1.4–1.8× швидшим за GiST для чистих point proximity-запитів на таблиці треків 50M рядків, з на 25% меншим обсягом індексу.

BRIN (block range index) — дешева опція, коли дані вже фізично кластеризовані за локацією — наприклад, коли вставки треків партиціоновані за регіоном і фізично дописуються в географічному порядку. Індекси BRIN крихітні (кілобайти для таблиць, що потребують гігабайтів GiST) і корисні як вторинний фільтр, а не первинний просторовий індекс. Вони сяють на холодних архівних партиціях.

Патерн комбінованого просторово-часового індексу: для навантажень "у межах 5 км за останні 60 секунд" не намагайтеся будувати єдиний multi-column індекс. Натомість будуйте GiST на geom і B-tree на ts, потім партиціонуйте таблицю за часом. Планувальник запитів комбінує обидва, і partition pruning усуває 99% даних до того, як почнеться будь-яка просторова робота. Реальні плани запитів на партиціях у мільйон рядків відповідають за 4–12 мс. Той самий запит без partition pruning, на тій же індексованій таблиці, — 200–400 мс.

Гібрид Time-Series + Geospatial

Оборонні треки за суттю — це часові ряди. Кожне оновлення треку — це append. Читання переважно "остання позиція на емітер" і "слід за останні N хвилин". Гібридний стек має значення.

Гіпертаблиці TimescaleDB з PostGIS. Гіпертаблиця автоматично партиціонує за часовими чанками (1-годинні або 6-годинні чанки для високооб'ємних фідів). Індекси PostGIS GiST будуються per chunk. Компресія на чанках, старших за 24 години, дає 8–14× зменшення сховища. Continuous aggregates попередньо обчислюють per-H3-комірку погодинні зведення. Це рекомендований стартовий стек для більшості оборонних фьюжн-розгортань.

kdb+/q для найвищих по throughput випадків. Коли платформа має поглинати кілька сотень тисяч оновлень треків на секунду — великі радарні мережі, об'єднані з multi-source ESM — стовпчасте сховище kdb+ з q-sql залишається best-of-breed. q-sql суворий, ліцензування дороге, але throughput реальний. Геопросторова історія — handrolled (ID комірок H3 або S2 як звичайні long-колонки), а не нативне GIS-розширення.

ClickHouse з geohash-колонками. ClickHouse добре справляється з аналітично-replay шаром — replay'те останні сім днів треків проти нового алгоритму кореляції. Geohash-колонки (рядки base32 змінної довжини, prefix-рівність = містить bounding box) — прагматичний індекс. ClickHouse 24.x додав нативні функції geoDistance і S2; на історичній таблиці треків у 5 мільярдів рядків proximity-скан на 10 км вирішується за 1–3 секунди. Не інтерактивно, але прийнятно для навантажень аналітиків.

Індекси для оперативного образу

Єдиний оперативний образ (COP) — канонічний споживач геопросторових індексів. Сотні-тисячі сесій операторів, кожна рендерить треки у в'юпорті, оновлюється 1–4 рази на секунду. Без dual-layer culling-архітектури першим помирає бекенд.

Server-side culling. Сервер застосовує bounding box в'юпорта як просторовий індексний запит, потім фільтр часового вікна, потім фільтри типу сутності та допуску. Результат — обмежений payload — типово обмежений 5 000 треками на відповідь, щоб тримати розмір по дроту передбачуваним. На правильно індексованій гіпертаблиці PostGIS це 6–20 мс на сесію.

Client-side culling. Клієнт отримує трохи більшу обвідну, ніж видимий в'юпорт (щоб панорама не миттєво тригерила refetch), тримає in-memory R-Tree треків і рендерить лише те, що всередині видимого canvas. R-Tree обробляє pan, zoom і hover hit-testing локально на 60 FPS без серверних round-trips.

Подвійний шар — те, що масштабується до тисяч одночасних сесій. Server-side culling обмежує вартість бекенду. Client-side culling обмежує вартість фронтенду. Будь-який шар окремо ламається. Цей патерн необхідний, чи COP — товстий клієнт (Qt, .NET) чи браузерна карта (Mapbox GL, MapLibre, deck.gl) — див. ширше довідник по конвеєру в частині 1 нашої серії про оборонний фьюжн-конвеєр.

Реалії міграції

Міграція з "усе в одній таблиці без просторового індексу" до правильно індексованого, партиціонованого, hypertable-backed сховища — це там, де більшість оборонних дата-програм спотикається. Три правила з досвіду доставки:

Dual-write до cutover. Нове індексоване сховище працює паралельно зі старою таблицею щонайменше два оперативні цикли (типово два тижні). Записи йдуть в обидва. Читання поступово переходять. Rollback — це конфіг-прапор, а не міграція БД.

Дисципліна еволюції схеми. Додавання колонки до гіпертаблиці на 500 ГБ із повним GiST-індексуванням — це не 5-секундний ALTER TABLE. Плануйте додавання колонок як свідомі релізи. Використовуйте JSONB-payload'и для полів під експериментом; промоутьте стабільні поля до типізованих колонок, щойно схема усталиться.

Backfill чанками за часом. Відновлення історичних треків у нову гіпертаблицю у зворотному хронологічному порядку (найновіші спершу) означає, що оперативно релевантне вікно стає запитуваним першим, поки старіші чанки приймаються у фоні. Не чекайте повного backfill перед перемиканням читань.