이전에 지리데이터를 다루면서 "클러스터링" 이라는 단어를 잘 모르고 쓴 적이 있다. 개발 초기, 창고의 검색 방식에 대해 고민하다가 "위치 정보 데이터가 많아지면 대체 원하는 정보를 어떻게 조회해오지?" 라는 거의 공상에 가까운 생각을 했다. 일단은 어떤 한 점(위경도)에서 주어진 반경 내의 데이터를 조회한다고 했을 때, 가장 먼저 떠올릴 수 있는 방법은 모든 데이터와의 거리를 일일이 다 계산해서 주어진 반경 내에 있는지 판단하는 방식을 먼저 떠올렸다. (그때는 풀 스캔, 시퀀셜 스캔이라는 단어도 몰라서 내가 알고 있는 단어인 브루트 포스 단어로 이 방법을 지칭했다.) 그러다가 당근 마켓을 떠올렸고 비슷한 지역끼리 묶어서 그 근처 지역만 먼저 조회하면 되지 않나? 라는 생각에서 "클러스터링" 이라는 말을 쓴 것이었다. 그런데 어이없게도 DB 공부를 시작하면 거의 바로 알 수 있는것이 클러스터링 인덱스라는 개념인데, 이게 내가 생각했던 '비슷한 지역끼리 묶어서 빠르게 조회하는' 방법이었다.
여튼 이걸 우리 프로젝트에도 직접 적용해보기로 했다.
1. 인덱스
1) 인덱스란
인덱스는 말그대로 데이터에 목차를 넣어주어 조회를 빠르게 할 수 있도록 돕는 기능이다. 만약 우리가 책에서 어떤 내용을 찾으려 한다면, 처음부터 한장 한장 넘겨가면서 찾기보다는 목차를 보고 큰 제목에서 소 제목으로 좁혀 가면서 원하는 내용이 있을 법한 부분 부터 찾을 것이다.
DB 에서의 인덱스는 기본적으로는 데이터들을 트리형태의 자료구조로 만들어서 조회의 시간복잡도를 N에서 logN 으로 만들어주는 방식으로 쿼리를 최적화 해준다. 따지자면 이분 탐색 알고리즘 와 유사하다.
Btree 데이터를 삽입 / 삭제하는 것을 시각화한 좋은 자료가 있어서 남겨둔다.
[ https://www.cs.usfca.edu/~galles/visualization/BTree.html ]
2) 공간 데이터 인덱스
그렇다면 공간 데이터는 어떤 기준으로 나눌 수 있을까? 숫자로 표현되는 id 값이야 대소 비교가 명확하지만 공간은 대체 그러한 대소가 불가능하다. 공간에서 어떠한 비교작업을 수행할 수 있는 부분은 한쪽이 다른 한쪽을 '포함하느냐' '포함하지 않느냐' 일 것이다.
이를 위해서 인덱스는 공간 데이터(점, 선, 면) 를 일정 단위로 묶어 전부를 포괄할 수 있는 최소 경계 박스 (Minimum Bounding Box) 로 정의하는 식으로 구현한다. 아래는 이 분류체계를 시각화한 이미지이다. 우리 프로젝트에서 쓰는 1차원 지리 데이터(점)로 예를 들자면, 먼저 주어진 중심좌표와 반경을 가지고 원을 만든 뒤 가장 큰 분류인 A, B, C 와 intersect 하는지를 판단후 닿지 않은 영역을 제거한다. 만약 반경이 B 와 C 만을 intersect 한다면 d, e, f 에 담긴 데이터는 판단할 필요가 없어지는 식인 것이다.
흠... 이걸 글로만 설명하는 것은 아무래도 언어와 지면(?) 의 한계 때문에 어려울 것 같고 공식 문서 링크를 남겨둔다.
PostGis Spatial Indexing [ https://postgis.net/workshops/postgis-intro/indexing.html ]
2. 테스트
1) Storage 적용
사실 그냥 냅다 인덱스 생성을 해놓고 완성! 이라고 외칠 수도 있겠으나, 실제로 잘 작동하는 지 보고싶고 그 효과도 눈으로 확인하고 싶은 것 이 인지상정일 것이다. 그러나 더미데이터도 많지 없고 실사용자는 아예 없는 실습용 프로젝트 한계상 직접 디비에서 그 효과를 보긴 힘들 것 같아서 동일한 환경의 test_db 에 더미데이터를 집어넣어서 테스트 환경을 만들었다. 창고를 20만개, 아이템을 30만개 넣었다.
우선 가장 간단하게 특정 좌표를 설정하고 반경 10키로 내의 창고를 조회해 보았다. 그런데 생각보다 쿼리 수행 속도가 높았다. 솔직히 이것밖에 걸리지 않는다는 것이 많이 놀라웠다. 어째서 20만건에 대해서 연산을 하는데 이것 밖에 안걸리나...
그리고 나서 아래와 같이 인덱스를 만들어주었다. 공간데이터 인덱싱은 R-tree 를 사용하는 것으로 공부했는데, Postgresql 은 이제 자체적으로 Rtree 를 개선한 Gist 라는 인덱스 알고리즘을 사용한다고 한다. 그래서 Rtree 는 obolete 라는 문구와 함께 Gist 로 인덱스가 생성된다. 아마 내부적으로는 거의 비슷한 동작을 하지 않을까 생각된다. 인덱스를 생성하면 자료들이 앞서 이야기한대로 트리형태로 재배열 되기 때문에 인덱스를 만드는데 시간이 조금 소요된다.
드디어 성과를 볼 차례다. 사실 언제나 글은 짧지만 글 뒤에는 무수한 시행착오와 삽질이 있었다. 기대하는 마음으로 조회쿼리를 실행했다.
소요 시간이 거진 40 분의 1 로 줄었다. explain 으로 query plan 을 살펴보면 Index Scan 을 적용한다는 볼 수 있다.
2) 데이터 삽입
데이터 삽입에서는 얼마나 차이가 날까? Rtree 의 데이터 삽입 알고리즘은 정확히 어떻게 수행되는지 모르지만 분명 차이는 있을 것 같아서 이것도 해봤다. (조회 쿼리 최적화의 효용을 능가하는 차이는 당연히 없고, 별 차이가 나지 않을 것이라고 예상했다.)
유의미한 차이인지 모르겠을 정도로 별 차이가 없었다. 추가 하는 좌표를 조금씩 다르게 했는데, 아마도 애매한 경계지점에 있을 경우 약간의 차이를 보이기도 했다.(평균적으로 15ms 정도의 시간이 소요되는데, 73.802ms 가 소요됨. 부모 노드를 분할 하는 연산이 일어나는 지점일 것 같다)
3) 다른 테이블과 조인이 포함된 쿼리
현재 프로젝트에서 지리 데이터는 정말 많은 쿼리에 쓰이고 있다. 그 중에서 위와 같이 지도의 특정 지역에서 창고를 조회하는 쿼리가 가장 대표적인 조회 쿼리일 것이다. 그 다음으로는 많이 쓰일 만한 곳이 아이템을 검색하는 쿼리일 것이다. 아이템은 지리 데이터가 없고, 창고에 의존해서 위치 조회가 이루어진다. 검색 쿼리에서 실제로 쓰일만한 조회 쿼리에 대해서 어떤식으로 쿼리가 수행되는지 Query Plan 을 출력해보았다.
조회 쿼리가 수행되는 과정을 보면, 먼저 아이템에 대한 Seq Scan을 수행한다. 그리고 나서 생성해두었던 geom_index 를 이용하여 storage 를 일차적으로 index Scan 을 하고 조인을 위한 Hash table 로 치환한다. 그리고 둘을 조인하는 식이다. 아래는 geom_index 를 drop 했을 때의 Query Plan 이다.
기본적으로 Id 값에 생성되어있는 B-tree Index 를 사용하여 Item 과 연관된 Storage 를 솎아낸 후, ST_DWithin 함수로 필터링 하는 방식이다. 해시 조인은 사용되지 않는다.
실제 수행결과에서의 차이
이즈음에서 약간 궁금한 것이 생겼다. 만약 카디널리티가 적은 enum 타입의 필드(item_type) 에 인덱스를 생성하면 어느정도의 차이가 있을까?
아예 인덱스를 사용하지도 않는다. 만든 사람 성의를 봐서라도 쓸 법도 한데..
+)
카디널리티가 작으면, 인덱스를 안쓰느니만 못할 수도 있기 때문에 옵티마이저가 쓰지 않기로 판단한 것이다. 인덱스 스캔을 해도 탐색 후에도 또 다시 테이블에서 다시 데이터를 가지고 오는 랜덤 I/O 작업을 하게 되는데, 차라리 그냥 데이터를 읽게 되면 랜덤 I/O 가 아닌 순차I/O 가 되어 디스크 읽기 작업이 빨라진다. 또한 인덱스 페이지와 테이블 데이터 페이지를 번갈아 읽는 것이 비효율적일 수도 있다.
3. 결론
개발을 시작하면서 들었던 이야기 중에, "내가 했던 고민들은 누구나 했던 고민이고, 이미 똑똑한 분들이 모든걸 만들어 놓았다" 라는 말을 자주 들었는데 정말이었다. 인덱싱이라는 기능은 누구나 생각해놓을 법한 기능이고 이미 쿼리 퍼포먼스 향상에 핵심적인 역할을 하고 있었다. 아무래도 이 기능은 얼만큼 잘 다루느냐에 따라 많은 성능 차이를 보일 것 같아서 잘 배워두는 것이 좋을 것 같다.
이번에 처음으로 query plan 이라는 기능을 써봤다. 최근에 LeetCode 에서 sql 문제를 꾸준히 풀고 있는데 조회 쿼리를 어떻게 짜느냐에 따라서 시간 차이가 상당히 난다는 것을 알았는데, 어떨 때는 서브쿼리를 쓰는게 빠르고 어떨 때는 느리게 동작하는 많았다. 대체 내부적으로 왜 그런차이가 있는지 혼란스러웠는데 이 기능을 쓰면 확실히 이해할 수 있을 것 같다. DB 를 이해하는 데에 정말 큰 도움이 되었다.
...
처음에는 로컬에서 테스트를 진행했는데, 내 컴퓨터에 깔려있던 postgresql 이 문제였는지 postgis 가 문제였는지 자꾸만 'no spatail operatory for 'ST_DWithin' 이라는 오류가 떠서 몇 시간을 헤맸다. 그러다가 그냥 AWS RDS 에서 테스트 해봤는데 잘 동작했다. 최근들어 가장 스트레스 받은 하루였다... 여튼 만족할만한 결과가 나와서 뿌듯하다.
