I like Data engineering and MLOPS.

3 minute read

Motivation

경로 기반 서비스를 개발하면서 특정 위치 기반 일정거리 이내에 존재하는 station 조회 쿼리의 비중이 중가하였습니다. (ex : 서울역으로부터 1km 이내의 station 들 찾기) 하지만 station이 저장된 초기 table에 위치 기반 filtering 조회시 전체 탐색 일어났고, 사용 유저 수 및 table 내 station 갯수가 지속적으로 증가함에 따라 부하가 점점 증가하는 현상이 발겼되었습니다. 또한 조회쿼리 분석 결과 station의 밀도가 낮은 지역(ex : 고속도로)에서 조회 비중도 적지 않았기 때문에 불필요한 지역의 데이터 탐색을 줄여야했습니다.

그래서 GIST index를 도입함으로써 위치 기반 조회 쿼리 성능이 개선된것을 공유하고자 합니다.

Content

GIST INDEX

postgresql는 현재 B-Tree, Hash, GIST, SP-GIST, GIN, BRIN index들을 지원하고 있고, 이중 spatial data index로 자주 활용되는 index는 GIST과 SP-GIST가 있습니다.

GIST는 b-tree와 유사하게 balanced search tree 구조를 가지고 있지만, b-tree는 one-dimensional data 간의 comparison operator(greater, smaller, same)을 지원하는 반면 GIST는 더 다양한 데이터 타입에 대한 operator들을 지원하고 있습니다.(ex : geodata, image, text document)

또한 GIST의 내부 자료구조로 position data type의 operator를 지원하기 위해 r-tree를 사용하고 있고, one-dimensional comparison이 아닌 geopoint data의 search를 위한 operator들이 별도로 정의되어 있습니다. leaf node에는 geopoint data 들이 저장되어 있고 internal node에는 각 operator별 boolean 형태의 predicate이 저장되어 있습니다(«해당 point가 box안에 들어가 있는가» 등등). 이를 이용하여 search시 internal node들에 대해서 search predicate을 검사하고 child node들을 탐색할지 결정을 합니다.

또한 geopoint를 지원하는 두 index GIST 과 SP-GIST 는 다음과 같은 차이점이 있는데요, SP-GIST는 spatial partitioning이 되는 quadtree, k-dimensional trees와 같은 자료구조들로 구성되어 있습니다. 대표적으로 quadtree는 area를 non-overlapping subdomain으로 나누고 unbalanced한 특성이 있습니다. unbalanced 하기 때문에 uniform하지 않은 데이터 분포를 가지고 있다면 탐색시 많은 internal node 탐색으로 인해 안정적이지 않은 조회 성능이 나올수 있습니다. 반면에 GIST 자료구조인 r-tree 는 balanced 되어 있기에 안정적인 조회 성능 개선을 기대할수 있습니다.

보유중인 station 데이터 특성상 uniform하지 않은 분포를 가지고 있기 때문에 geospatial data의 안정적 조회 성능 개선을 위해 GIST를 사용하였습니다.

GIST index 동작

GIST내부 구조를 가시화 하면 다음과 같습니다.

gist-index-logic-level-1.png

gist-index-logic-level-3.png

같은 레벨의 사각형들은 r-tree의 같은 height에 존재하고 point 탐색시 «탐색중인 point가 해당 box 내부에 존재 하는가» 와 같은 search predicate를 가지게 됩니다. 다음 레벨의 사각형들은 parent 도형을 다 cover할수 있게 분해가 됩니다. 각 도형은 overlapping 할수 있고, 한 index page에서 가장 많은 point를 가지도록 구성됩니다.

예를들어 특정레벨에 6개의 point(leaf node)가 존재하고, (4,7) point 로부터 가장 가까운 point 2개를 탐색한다고 가정하면 다음과 같은 연산이 진행됩니다.

select * from points order by p <-> point '(4,7)' limit 2

gist-index-logic-area-graph.png

gist-index-logic-area-tree-structure.png

  1. point (4, 7)과 각 region(두 area s1, s2)과의 “최소 거리” 구합니다. (s1 = 4.0, s2 = 1.0) ”최소 거리” 이기 때문에 child node들 과의 거리를 underestimate 합니다.
  2. 더 가까운 s2 = 1.0 area 탐색 ⇒ 2.2, 3.2, 4.1 거리 계산
  3. 최근접 point 2개 까지 구한다면 2.2, 3.2 Point return
  4. 하지만 최근접 point 3개를 구한다면 efficiency를 포기하고서라도 두번째 area뿐만 아니라 첫번째 area까지 탐색하고 거리를 계산합니다. 이는 internal node의 predicate이 “최소 거리”를 기반으로 search하는것과 연관이 있는데요, 첫번째 area와의 거리가 4.0으로 두번째 area의 가장 먼 마지막 point 거리 4.1보다 가깝기 때문에 정확도를 위해 첫번째 area까지 탐색하는것입니다.

이를 실제 데이터에 적용해보자면, 예를 들어 부산시청에서 2km내 station들 100개를 탐색할때 서울 근방 station들은 distance 기반 search predicate을 통과하지 못했기 때문에 탐색 범위에서 제외가 된다고 볼수 있습니다.

performance 측정

거리기반 filtering operator를 사용하기 위해 table에 station_point라는 point type column을 생성하겠습니다.

UPDATE data.geo_index_station_table
SET station_point = ('SRID=4326;POINT('||latitude||' ' ||longitude||')')

station_point에 별다른 index를 생성하지 않고 execution time 및 query plan을 살펴보면, parallel seq scan이 일어나고 490ms에 가까운 실행 시간이 걸림을 확인할수 있습니다.

EXPLAIN ANALYSE
SELECT * FROM data.geo_index_station_table
WHERE ST_DWithin('SRID=4326;POINT(37.15 127.178)', station_point, 0.02);

Parallel Seq Scan on geo_index_station_table  (cost=0.00..812568.00 rows=3 width=473) (actual time=378.494..402.728 rows=6 loops=3)
        Filter: st_dwithin('0101...64CB5F40'::geometry, station_point, '0.02'::double precision)
        Rows Removed by Filter: 25754

Planning Time: 0.204 ms
Execution Time: **489.599 ms**

이제 station_point에 GIST index를 생성하겠습니다.

CREATE INDEX gist_idx_station_point ON data.geo_index_station_table  USING gist (station_point);

이제 index가 생성된 station_point에 대해 위치 기반 operator를 사용하여 filtering query를 실행해보겠습니다. index scan이 일어나고 실행시간도 0.643ms으로 많이 줄어든것을 확인할수 있습니다.

EXPLAIN ANALYSE
SELECT * FROM data.geo_index_station_table 
WHERE ST_DWithin('SRID=4326;POINT(37.15 127.178)', station_point, 0.02);

Index Scan using gist_idx_station_point on geo_index_station_table  (cost=0.53..642.91 rows=8 width=473) (actual time=0.243..0.534 rows=19 loops=1)
  Index Cond: (station_point && st_expand('0101...F40'::geometry, '0.02'::double precision))
  Filter: st_dwithin('01010...F40'::geometry, station_point, '0.02'::double precision)
  Rows Removed by Filter: 4

Planning Time: 1.469 ms
Execution Time: **0.643 ms**

Conclusion

지금까지 station point들에 대해 gist-index를 사용하여 거리기반 조회 쿼리의 성능을 대폭 증가시킨 내용을 정리하였습니다. 하지만 단순히 spatial한 index를 사용한 성능개선 이상의 의미가 있는 작업이었다고 생각합니다.

앞으로 여러 MLOPS 프로젝트를 진행하면서 이미지, 자연어 텍스트 또는 다른 two-dimensional 이상의 데이터를 사용할것이고 서비스를 운용하면서 쿼리 성능 개선을 고민하게 될것입니다. 그때 이미지/자연어 텍스트 간의 distance, operator 정의는 어떻게 할것이며 search할 자료구조는 어떠한 형태여야하는지 미리 생각해볼수 있는 시간이었습니다.

만약 사용중인 db내에서 지원하지 않는다면 외부 Metastore db에 index를 직접 구현해야할수도 있기 때문에 의미있는 시간이었다고 생각합니다.

Reference

Indexes in PostgreSQL — 5 (GiST)

Indexes in PostgreSQL — 6 (SP-GiST)

R-Tree Index 와 공간 탐색

How to create a spatial index on a PostgreSQL GEOMETRY field?

You may also enjoy