솔직히 말해서, 대용량 GIS 데이터를 다루다 보면 ST_Intersects 쿼리 하나 때문에 퇴근 시간이 늦어지는 경험, 다들 한 번쯤 있으실 겁니다. “그냥 인덱스 태우면 되는 거 아니야?”라고 쉽게 말하는 사람도 있지만, 수억 건의 폴리곤과 포인트가 얽히면 이야기가 달라집니다.

최근 FloeDB 팀에서 Geo Join 성능을 무려 400배나 향상시킨 사례를 공유했는데, 그 접근 방식이 꽤 흥미롭습니다. 단순히 데이터베이스 튜닝을 넘어서, 문제를 ‘기하학(Geometry)‘의 영역에서 ‘집합 연산(Set Operation)‘의 영역으로 치환해버렸기 때문입니다. 오늘은 이 기술적인 접근법과 그 이면에 있는 트레이드오프, 그리고 제 개인적인 견해를 섞어 분석해 보겠습니다.

왜 Geo Join은 느린가?

기본적으로 ST_Intersects(A.geo, B.geo) 같은 공간 조건(Spatial Predicate)은 데이터베이스 입장에서 정말 골치 아픈 녀석입니다. 일반적인 DB 최적화의 꽃은 Hash Join 인데, 공간 데이터는 명확한 ‘Join Key’가 없기 때문이죠.

결국 DB는 Nested Loop Join 을 선택하거나, R-Tree 같은 공간 인덱스를 타더라도 엄청난 랜덤 I/O를 발생시킵니다. 데이터가 커질수록 복잡도는 $O(N^2)$에 가까워지고, 쿼리 플랜을 보는 엔지니어의 혈압도 같이 올라갑니다.

해결책: H3를 이용한 ‘Equi-Join’으로의 전환

이 글의 핵심 아이디어는 간단하지만 강력합니다. “공간 문제를 정수(Integer) 비교 문제로 바꾸자” 는 것입니다.

여기서 우버(Uber)가 만든 H3 인덱스가 등장합니다. H3는 지구를 육각형(Hexagon) 셀로 쪼개고, 각 셀에 고유한 BIGINT ID를 부여합니다.

원리는 다음과 같습니다:

1. Decomposition: Join 하려는 두 테이블의 Geometry를 H3 셀 ID들의 집합으로 변환합니다.
2. Rewrite: 이제 ST_Intersects가 아니라, 두 집합 간에 공유하는 H3 Cell ID가 있는지 를 확인하는 문제로 바뀝니다.
3. Execution: H3 Cell ID는 정수이므로, DB는 매우 효율적인 Hash Join 을 수행할 수 있습니다.

즉, 무거운 연산을 가벼운 필터링 단계(Approximation)와 정밀 검증 단계(Exact Check)로 나눈 것입니다.

실제 쿼리 패턴

이 방식은 보통 CTE(Common Table Expression)를 사용하여 구현됩니다. 원본 글에서 제시한 쿼리 패턴을 보면 이해가 빠릅니다.

WITH
a_cells AS (
  SELECT a.id, a.geo, c.cell
  FROM A a
  JOIN h3_coverage(a.geo, 3, true) c ON TRUE
),
b_cells AS (
  SELECT b.id, b.geo, c.cell
  FROM B b
  JOIN h3_coverage(b.geo, 3, true) c ON TRUE
),
candidates AS (
  SELECT DISTINCT
    a_cells.id AS a_id, a_cells.geo AS a_geo,
    b_cells.id AS b_id, b_cells.geo AS b_geo
  FROM a_cells
  JOIN b_cells USING (cell) -- 여기서 고속 Hash Join 발생
)
SELECT *
FROM candidates
WHERE ST_Intersects(a_geo, b_geo); -- 최종 정밀 검증

데이터베이스는 이 쿼리를 통해 수천만 번의 ST_Intersects 호출을 수십만 번 수준으로 줄일 수 있습니다. 실제로 벤치마크 결과, 459초 걸리던 쿼리가 1.17초 로 줄어들었습니다. 거의 마법에 가까운 수치죠.

엔지니어링 관점에서의 분석과 비판

물론 세상에 공짜 점심은 없습니다. 이 방식에도 명확한 한계와 고려사항이 있습니다.

1. Resolution(해상도)의 딜레마

H3 해상도를 어떻게 잡느냐가 성능을 좌우합니다.

• 해상도가 너무 낮으면(큰 육각형): 필터링 효과가 떨어져서 candidates가 너무 많이 남습니다. (False Positive 증가)
• 해상도가 너무 높으면(작은 육각형): 하나의 폴리곤이 수천, 수만 개의 셀로 쪼개져서 JOIN 부하가 폭증합니다.

위 그래프의 U자형 곡선이 이를 잘 보여줍니다. 데이터의 특성에 맞는 ‘Sweet Spot’을 찾는 튜닝 과정이 필수적입니다.

2. S2 vs H3: Hacker News의 논쟁

이 글과 관련해 Hacker News 에서는 꽤 흥미로운 논쟁이 있었습니다. 일부 유저들은 “왜 H3냐? S2 가 더 낫지 않냐?”라는 의견을 제시했습니다.

핵심은 Congruency(일치성) 문제입니다. H3의 육각형은 부모 셀이 자식 셀을 완벽하게 포함하지 않습니다(약간 어긋남). 반면 구글의 S2(사각형 기반)는 부모가 자식을 완벽히 포함합니다. 엄밀한 계층 구조가 필요한 연산에서는 S2가 수학적으로 더 깔끔합니다.

하지만 제 생각은 조금 다릅니다. 이 유스케이스에서 H3는 ‘Pre-filter’ 용도입니다. 어차피 마지막에 ST_Intersects로 정밀 검증을 하기 때문에, H3의 약간의 부정확함(False Positive)은 결과의 정합성에 영향을 주지 않습니다. 오히려 시각화나 생태계의 편의성 면에서 H3가 주는 이점이 크다고 봅니다.

3. On-the-fly vs Materialized

원문에서는 쿼리 실행 시점에 H3 인덱스를 생성(On-the-fly)하는 방식을 택했습니다. 이는 유지보수 관점에서 매우 현명한 선택입니다. 별도의 인덱스 테이블을 관리하고 동기화하는 것은 운영 비용을 크게 증가시키기 때문입니다. 물론, 데이터가 정말 자주 조회되는 정적 데이터라면 Materialized View로 구워두는 것이 더 효율적일 것입니다.

결론: 그래서 써야 할까?

대규모 공간 데이터를 조인해야 하는 상황이라면, 이 패턴은 강력히 추천 합니다. PostGIS의 기본 인덱스만 믿고 있다가는 스케일링 이슈에 직면하기 쉽습니다.

하지만 무작정 적용하기보다는 다음을 체크해보세요:

• 데이터의 밀도가 균일한가? (특정 지역에 몰려있다면 H3 셀 폭발이 일어날 수 있음)
• 적절한 H3 해상도를 테스트할 여유가 있는가?

공간 데이터 처리는 결국 ‘얼마나 빨리 정답이 아닌 것들을 버리느냐’의 싸움입니다. H3는 그 싸움에서 아주 훌륭한 무기가 되어줄 겁니다.