Avoiding spatial index for trade-off

대량 위치 조회에서 Spatial Index를 걷어낸 이유: 정확도와 성능의 Trade-off

(사내 보안 규정에 따라 실제 서비스·테이블·코드 식별자는 모두 일반화되어 있습니다)

1. 문제 및 배경: "우리 동네 질문글 알림"

저희 서비스는 지역 기반의 커뮤니티 SNS입니다. 유저가 글을 올리고 이를 "단지 질문글"로 설정하면, 해당 지역에 있는 유저들에게 알림 생성, 푸시가 발송됩니다.

1.1. 초기 접근

처음에는 MySql의 Spatial Index(R-Tree)를 사용하고, 정확한 반경 계산을 위해 ST_Distance_Sphere 함수를 적용했습니다.

SELECT * FROM users
WHERE ST_Distance_Sphere(location, :center_point) <= 5000; -- 반경 5km

하지만 유저 수가 늘어나면서, 이 "정석"적인 쿼리는 예기치 못한 성능 저하를 일으켰습니다.

1.2. R-Tree(Rectangle Tree)란 무엇인가

R-Tree는 공간 객체(spatial object)를 빠르게 찾기 위한 자료구조 입니다.

• R-Tree: 2차원 이상 영역을 기반으로 탐색하는 트리 구조.

• B-Tree(Balanced Tree, 균형 트리): 정렬된 1차원 값에 최적화된 균형 트리

R-Tree의 구조

[Root MBR]
   |
   +-- [Internal Node MBR]
   |       |
   |       +-- [Leaf Node MBR] -> 좌표들
   |       +-- [Leaf Node MBR] -> 좌표들
   |
   +-- [Internal Node MBR]
           |
           +-- [Leaf Node MBR] -> 좌표들

• 모든 사각형은 MBR 노드를 나타냅니다.

• 리프 노드: 실제 좌표(Point)

• 리프 노드 MBR: 해당 리프 노드에 들어 있는 좌표 전체를 감싸는 사각형

• 내부 노드: 여러 리프/하위 노드를 가리킴

• 내부 노드 MBR: 자식 노드들의 MBR을 다시 감싸는 사각형

• 루트 MBR: 트리 전체 영역

• 모든 노드에는 MBR이 있습니다.

리프 노드 MBR

여러 좌표(point)를 감쌈

[Leaf Node MBR]
 ├─ (x1, y1)
 ├─ (x2, y2)
 └─ (x3, y3)

내부 노드 MBR

여러 하위 노드의 MBR을 감쌈

[Internal Node MBR]
 ├─ [Leaf MBR A]
 └─ [Leaf MBR B]

검색은 이 계층을 위에서 아래로 내려간다.

검색 흐름 (반경 검색 예시)

1. 검색 영역 생성 (원 또는 사각형)

2. 루트 MBR과 겹치는지 확인

3. 겹치면:

   • 자식 노드들의 MBR과 비교

4. 겹치는 노드만 계속 내려감

5. 리프 노드 도달 → 좌표 후보 확보

검색 영역
   ↓
Root MBR
   ↓
Internal MBR (여러 개 가능)
   ↓
Leaf MBR (여러 개 가능)
   ↓
좌표 후보

왜 R-Tree는 이런 구조를 선택했는가

R-Tree는:

• 동적 삽입/삭제 지원

• 공간 데이터의 유연한 분포 대응

• 균형 유지

를 위해:

• 영역을 딱 맞게 나누지 않는다

• overlap을 허용한다

정확한 분할보다 유연성 우선

2. 왜 Spatial Index(R-Tree)는 병목이 되었는가

R-Tree는 2차원 공간 데이터를 빠르게 검색하기 위한 자료구조입니다. 다만, 해당 기능의 특성과는 맞지 않은 두 가지 문제가 있었습니다.

2.1. 병목1: DB CPU 부하

DB CPU 사용률 급증이 첫번째 문제였습니다.

• 원인: ST_Distance_Shphere 함수는 지구의 곡률을 고려해서 거리를 계산합니다. (삼각함수 연산)

• 현상: 배치 작업이 돌 때마다, spatial index로 필터링된 최종 후보군에 대해 단건 연산을 수행하며 거리를 구합니다. 이때 전체 DB CPU가 100%를 찍었고, 단순한 조회가 아니라 단건 연산이 병목이 됐습니다.

검색 과정

1. 검색 영역 생성: 반경 원 또는 감싸는 사각형 (MBR)

2. 루트 노드부터 시작: 검색 영역과 겹치는 MBR 노드들만 탐색

3. 겹치는 MBR 노드들을 찾으면: 그 노드의 자식 노드로 내려감. (계층 구조)

4. 리프 노드 도달: 실제 좌표 후보들 획득

5. 최종 거리 계산: 진짜 반경 내인지 판별

" 이 사각형A가 이 사각형B와 겹치는가? " 를 판단합니다. (좌표 밀도가 높은 경우에 하나의 MBR 노드에는 수천~수만 개의 좌표가 포함되고, 이후 단계에서 수행되는 연산이 문제가 됩니다.

Distance 함수가 붙는 순간 Index-Only Scan은 불가능

SELECT *
FROM user_location
WHERE MBRContains(
  ST_GeomFromText(:mbr),
  location
)
AND ST_Distance_Sphere(location, :center) <= 10000;

동작 원리

MBRContains( ST_GeomFromText(:mbr), location)

• MBRContains: R-Tree는 루트(최상위) MBR(사각형)들로 구성되어 있습니다.

• 각 MBR들은 내부 노드(MBR)들을 포함하고 있고,

• 계층 아래 쪽에 있는 MBR들은 결국 리프 노드(좌표)들을 가지고 있습니다.

• 전체 좌표들 중 후보들을 빠르게 추리기 위한 필터링 방법입니다.

• 이 과정을 생략하게 되면, 존재하는 모든 좌표들에 대해 거리 계산을 하게 됩니다.

ST-Distance_Sphere

• 거리 계산을 위해 사용되며 기준 좌표와 대상 좌표의 거리를 나타냅니다.

• 내부 MBR이 어떻게 생겼는지 알기가 어렵기 때문에, 이 과정을 생략하면 정확도가 많이 떨어집니다.

1. 좌표와 반지름이 주어졌을때, 해당 원을 포함하는 최소한의 x각형을 구성하고, 좌표들을 만들어냅니다. (예를 들어, 사각형이라면 4개의 좌표들이 생성됩니다.)

2. 4개의 좌표들로, 루트 MBR 들을 순회하면서 도형이 교차하는지 검증하고, 교차하지 않으면 후보에서 제외합니다.

3. 후보 루트 MBR들안에 포함되어있는 내부 MBR들을 같은 방식으로 검증하게됩니다.

4. 마지막 MBR 내부의 좌표들을 가져옵니다.

해당 쿼리의 핵심 문제는:

• ST_Distance_Sphere:

  • 삼각함수 기반

  • CPU 연산 비용이 높습니다.

• Spatial Index는:

  • 거리 조건을 최적화하지 못합니다.

  • 후보를 찾은 뒤, 모든 row에 대해 거리 계산 수행

결과적으로, Spatial Index는 후보를 줄여줄 수는 있지만, 거리 계산 비용 자체를 줄여주지는 못합니다.

예시 EXPLAIN ANALYZE 분석

EXPLAIN ANALYZE
SELECT *
FROM user_location
WHERE MBRContains(
  ST_GeomFromText(:mbr),
  location
)
AND ST_Distance_Sphere(location, :center) <= 10000;

-> Filter: (st_distance_sphere(...) <= 10000)
   -> Index range scan on user_location using idx_location_spatial
      rows=120000

Spatial Index로 12만건 후보를 추출하게 되고, 이후 12만번 거리를 계산합니다. DB CPU 사용률이 급증하고, Batch 작업에 따라 DB 전체 성능이 저하됩니다.

2.2. 병목2: 쓰기 성능 오버헤드

다른 문제는 인덱스 유지보수 비용입니다.

• R-tree 구조: R-Tree는 데이터를 MBR(Minimum Bounding Rectangle. 최소 경계 사각형)으로 감싸 관리합니다. 데이터가 추가되거나 변경되면, MBR 영역을 재계산하고 트리의 균형을 맞춥니다. 이때 노드 분할과 병합 비용이 발생합니다.

• 비용 불균형: 이 기능은 일주일에 2~3번 실행이되며, 상대적으로 변경이 더 잦은 유저의 위치 업데이트보다 비싼 R-Tree 갱신 비용이 발생하고 있었습니다.

3. 대안 검토: Geohash와 Quadtree는 왜 적절하지 않은가

R-Tree 대안으로는 Geohash 방식과 Quadtree 방식이 있습니다. 아래 이유들로 채택하지 않았습니다.

3.1. Geohash

• 원리: 지도를 격자 형태로 나누고 각 격자에 고유한 문자열 ID를 부여합니다. 이는 경도, 위도 정보인 2차원 데이터를 1차원으로 변경한 것입니다. 이를 통해 LIKE 'abcd%' 처럼 prefix 검색이 가능합니다.

• 기각 사유: 사용자가 격자 경계선에 위치한 경우, 바로 옆집이라도 해시값이 달라집니다. 이를 해결하려면 주변 8개의 셀을 추가로 계산해서 조회해야하는데, 구현 복잡도가 높습니다.

기각 사유1: 구현 복잡도

만약 5키로 미터내의 유저들을 검색할때, Geohash길이(Level)을 약 5자리로 설정합니다(4.9km x 4.9km). 기준점 반경 원(wydmc)이 옆 격자까지 걸쳐져 있는 경우에는 옆에 지역까지 같이 검색을 해야합니다. 총 8방향 이웃 격자를 포함하게 됩니다.

이떄, 오른쪽의 격자가 완전히 다른 Geohash 값을 가지고 있는 상황이 발생할 수 있습니다. 그러면 그 값을 알기 위해서는:

1. 디코딩: wydmc를 위도/경도 숫자로 복원

2. 이동: 격자 폭만큼 오른쪽으로 이동합니다

3. 인코딩: 이동한 새로운 좌표를 다시 Geohash 알고리즘에 넣어서 문자열로 변환

4. 결과: wxdmc 라는 값이 나옵니다.

그 다음으로, sql문을 호출합니다.

SELECT * FROM users
WHERE geohash LIKE 'wydmc%'  -- 기준 격자 (Center)
   OR geohash LIKE 'wxdmc%'  -- 오른쪽 격자. 아까 계산해서 알아낸 값
   -- (나머지 7개 방향도 똑같이 계산해서 OR로 붙임)

인덱스를 타긴 하지만, OR 조건이 많아질수록 Random access가 많아지고, 반경이 커질수록 쿼리 OR 조건들이 크게 늘어나게 되며 쿼리 성능 저하.

3.2. Quadtree

• 원리: 공간을 재귀적으로 4등분하여 데이터 밀도에 따라 깊이를 조절합니다.

• 기각 사유: RDBMS로는 지원되지 않고, 애플리케이션 레벨에서 구현을 직접 해야합니다.

기각 사유1: 구현 복잡도

• 애플리케이션 레벨 구현: DB 엔진이 해주던 인덱스 관리를 개발자가 직접 해야 합니다.

• Write 복잡성 (Node Split 문제): 예를 들어, 한 구역(노드)의 최대 수용 인원이 100명이라고 가정합니다.

  1. 상황: 현재 100명이 꽉 찬 노드에 유저 A가 새로 진입합니다.

  2. 분할(Split): 용량이 초과되었으므로, 시스템은 해당 노드를 4개의 자식 노드로 쪼개고 기존 유저들을 재배치해야 합니다.

  3. 충돌: 하필 이 찰나의 순간에 유저 B도 같은 구역으로 진입합니다.

  4. 문제: 유저 B는 분할되기 전의 부모 노드에 들어가야 할까요, 아니면 분할 중인 자식 노드에 들어가야 할까 같은 문제가 발생합니다.

기각 사유2: 데이터 편향에 따른 쓰기 부하

Quadtree는 데이터 밀도에 따라 트리의 깊이(Depth)가 달라집니다. 인구가 극단적으로 쏠리는 SNS 서비스 특성상, 트리 깊이의 불균형이 쓰기 성능을 저하시킵니다.

• 트리 깊이(Depth)의 불균형:

  • 강원도 산골: 유저가 적어 트리가 얕습니다. (Depth: 3)

  • 서울 강남: 유저가 폭발적으로 밀집되어 트리가 기형적으로 깊어집니다. (Depth: 20+)

• 쓰기(Update) 비용 증가: 강남역에 있는 유저가 이동할 때마다, 시스템은 20단계 이상의 깊은 노드를 매번 탐색(Traverse)하고 갱신해야 합니다.

• 구조적 변경: 유저들이 이동함에 따라 노드 인원이 임계치를 넘나들면, 트리는 계속해서 노드를 쪼개고(Split) 합치는(Merge) 연산을 반복합니다. 이는 단순한 좌표 값 수정(Update)보다 훨씬 비싼 비용을 치르게 됩니다.

4. 해결책: 하이브리드 전략(정적 지역 + 동적 유저)

문제를 다시 생각해봤을때, 좌표가 중요하지 않고, 그 좌표 반경의 "동네" 사람들을 찾는 것이 목표입니다. 그래서, 대상을 User테이블에서 Region테이블로 연산 대상을 옮겼습니다.

4.1. Trade-off 정확도 vs 성능/안정성

이 과정에서 팀과 논의 후에 Trade-off를 바탕으로 의사결정을 내렸습니다.

• AS-IS (정확도 100%): ST_Distance_Sphere를 사용한 완벽한 원형 반경 검색.

• TO-BE (근사치 검색): 행정구역(Region) 단위의 MBR(사각형) 교차 검색.

이 방식은 원형 반경보다 범위가 조금 더 넓게 잡히거나, 불규칙한 지역 경계로 인해 일부 오차가 발생할 수 있습니다. 하지만 저희는 이를 "허용 가능한 오차"로 판단했습니다. SNS 알림 서비스 특성상 "인접한 이웃을 빠뜨리지 않는 것"이 중요하며, 조금 더 넓은 범위의 이웃에게 알림이 가는 것은 오히려 득이 될 수 있기 때문입니다.

대신 압도적인 성능과 시스템 안정성을 얻었습니다.

4.2. 아키텍처 전환

• AS-IS: 유저 테이블에 직접 공간 쿼리 (ST_Distance)

• TO-BE:

  • Region 필터링: 질문글 좌표 반경에 포함되는 지역ID를 먼저 찾음 (R-Tree)

  • User 조회: 해당 지역 ID를 가진 유저 조회. (B-Tree)

4.3. 핵심 구현: "정적인 공간"과 "동적인 유저"의 분리

알림 발송 시점에 유저 거리를 일일이 개산하지 않고 비용을 줄이기 위해 지역ID 개념을 도입했습니다.

• AS-IS: 유저는 좌표(x, y)만 가지고 있음. (비구조화된 공간 데이터)

• TO-BE: 유저는 region_id (Foreign Key)를 가짐. (구조화된 관계형 데이터)

  • 지역 테이블: 지역을 크게 묶은 행정 구역이며, 인덱스 재구성이 거의 없는 테이블입니다.

  • 유저가 회원가입하거나 위치를 업데이트할 때, 해당 좌표가 속한 법정동 코드를 기반으로 region_id를 매핑해 둡니다.

1단계: 정적 영역: R-tree로 후보 지역 '빠르게' 찾기

지역 데이터는 변경이 거의 발생하지 않습니다. 따라서 R-Tree의 단점인 쓰기 부하가 발생하는 경우가 드뭅니다. 여기서는 MBRContains 함수를 사용하였고, 검색 박스 안에 있는 지역ID들을 1차적으로 빠르게 조회했습니다.

// Native Query: 지역 테이블은 정적이므로 공간 인덱스(R-Tree)를 활용하여 검색 효율을 높인다.
@Query(value = """
    SELECT 지역 테이블.id
    FROM 서비스.지역 테이블
    WHERE MBRContains(
        ST_GeomFromText(:polygonWKT, 4326), -- 내 검색 범위 (사각형)
        지역 테이블.location                   -- 지역의 좌표
    )
""", nativeQuery = true)
fun findIdsByBoundingBox(...): List<Long>

• 원리: 내 검색 반경(사각형) 안에 중심점이나 영역이 포함되는 '지역 ID 리스트'를 추출합니다.

• 비용: 대상 데이터가 수천 건(읍면동 개수)에 불과하므로, 공간 연산 비용이 부담되지 않습니다.

2단계: 동적 영역: B-Tree로 유저 조회하기

확보된 Region ID들을 바탕으로 유저 테이블을 조회합니다. 유저 테이블은 Update가 발생할 수 있기에, 공간 인덱스를 제거하고 가벼운 B-Tree 인덱스(Foreign Key)를 사용했습니다.

fun find대상By지역idsWithCursor(
        지역Ids: List<Long>,
        ..,
        커서오프셋ID: Long?,
        size: Long,
    ): List<Long>

5. 결과

이 방식이 해결한 문제들은 아래와 같습니다.

1. 쓰기 성능 확보

'쓰기 오버헤드'를 해결했습니다.

• 빈번하게 이동하는 유저 테이블에서 무거운 R-Tree를 제거하고 가벼운 B-Tree(FK)로 대체했습니다.

• 이로 인해 유저의 위치가 바뀌해도, 지역 테이블 R-Tree의 노드 분할, 재구성 비용이 전혀 발생하지 않습니다.

2. 검색 비용의 최적화

공간 연산(MBRContains)의 대상을 수십만 건의 유저에서 수천~만 건의 지역(Region) 테이블로 축소시켰습니다.

• 카디널리티가줄어들었기 때문에, 공간 연산을 수행해도 CPU 부하가 적습니다.

3. 운영 안정성 확보

대량 처리 시 시스템이 멈추지 않도록 구현했습니다.

• Cursor Paging: 메모리 폭발(OOM) 방지 및 Non-blocking 조회.

• Application Throttling (Thread.sleep): 의도적인 지연을 통해 DB 리소스를 독점하지 않게 했습니다.

4. 아키텍처 확장성

"공간 검색(Region)"과 "유저 조회(User)"의 관심사를 분리함으로써, 미래를 위한 최적화 기반을 마련했습니다.

• 현재는 DB의 R-Tree를 사용하지만, 트래픽이 폭증할 경우 애플리케이션 코드 수정 없이 지역 검색 로직만 교체할 수 있습니다.

• 정적인 지역 데이터를 Redis나 로컬 캐시(In-Memory)를 사용하여, DB 부하를 없애는 성능 튜닝이 언제든 가능합니다.