Postgresql DB의 인덱싱 알고리즘

 

 

Postgresql db를 사용하면서 다수의 row를 가진 데이터들을 다룰 때 양이 많아질수록 쿼리 시간이 길어지는 것이 보였다. 이를 개선하기 위해 여러가지 기법을 찾던 중, db의 인덱싱 알고리즘에 따라서 특정한 데이터들은 성능이 빨라진다는 것을 알게 되었다. 이에 대한 지식이 부족한 것 같아 간단히 정리했다.

 

알고리즘 종류의 필요성

---

현재 사용되는 db 서비스들은 대부분 기본값으로 b-tree 인덱싱을 사용하고 있다. 보편적으로 많이 사용되고 성능 또한 어느정도 검증이 되어 있어 이를 기반으로 구조가 이루어져 있다. 하지만 이것이 만능 인덱싱 알고리즘은 아닐 뿐더러 항상 특수한 경우가 생기기 마련이다. 이를 위해서 postgres 에서는 21년 현재 6개(사실상 5개)의 알고리즘을 지원하고 있다. 지원하는 알고리즘은 다음과 같다.

 

1. B-Tree

2. Hash

3. GiST

4. SP-GiST

5. GIN

6. BRIN

 

https://www.postgresql.org/docs/14/indexes.html

Chapter 11. Indexes

 

간단하게 하나씩 정리해 보자.

 

B-Tree

---

기존의 tree 구조의 형태는 평균 탐색 시간이 O(logN) 이나 최악의 경우에는 O(N)까지도 갈 수 있다는 단점이 있다. 이를 극복하기 위해서 데이터 삽입 및 삭제의 연산이 들어갈 때 tree 구조를 balanced화 하는 기능이 필요했다. 이를 추가한 것을 B-Tree 구조라고 하며 Red-Black tree와의 차이점은 한개의 노드에 연속된 데이터가 최대 2개까지 들어갈 수 있다는 점이다. B-Tree 구조는 일반적인 데이터 구조에서 균등한 속도를 내기 때문에 기본적인 알고리즘이라고 할 수 있다.

 

Hash

---

이 알고리즘은 해시 테이블 구조이다. 말 그대로 key, value 값만 가지는 db 구조이다. 이 db의 특징은 실행 속도가 O(1) 이며 탐색 속도가 매우 빠르다는 장점을 가지고 있다. 하지만 가장 큰 단점은 등호 연산을 제외하고는 어떠한 연산도 불가능하다는 것이다. 코드를 잘 작성하면 가능하기는 하나 실행 속도가  O(N)이라서 사실상 큰 의미가 없다. (전체 데이터는 정렬되지 않았으므로.)

 

GiST (SP-GiST)

---

이 알고리즘은 좌표 및 특정한 위치의 값을 다루는 데 가장 좋은 성능을 보인다. 다중 인덱싱 전략이라고 하는데, 자세한 내용은 다음 사이트에서 잘 설명이 되어 있다.

https://medium.com/postgres-professional/indexes-in-postgresql-5-gist-86e19781b5db

Indexes in PostgreSQL — 5 (GiST)

 

GIN

---

이 알고리즘은 장문의 문자열 안에 특정 문자열을 검색할 때 가장 좋은 성능을 보인다. 기본적인 구조는 B-Tree구조를 가지고 있다. 하지만 여기서 장문의 문자열이 오게 되면 이 문자열을 특정한 규칙에 따라 분할 (split) 한다. 이렇게 분할된 문자열들은 그 안에서도 B-Tree 구조를 가지고 있으므로 탐색 시간이 O(N)이 되는 일은 없을 것이다. 데이터 구조는 아래 사진에서 잘 설명하고 있다.

 

 

위와 같은 기능을 활용하기 위한 명령어는 %LIKE% 가 있다. 이를 이용해서 성능 개선을 경험한 사례도 있었다.

 

https://medium.com/vuno-sw-dev/postgresql-gin-%EC%9D%B8%EB%8D%B1%EC%8A%A4%EB%A5%BC-%ED%86%B5%ED%95%9C-like-%EA%B2%80%EC%83%89-%EC%84%B1%EB%8A%A5-%EA%B0%9C%EC%84%A0-3c6b05c7e75f

PostgreSQL GIN 인덱스를 통한 LIKE 검색 성능 개선

 

 

BRIN

---

이것은 특정한 범위에 따라서 데이터를 묶어 두고, 거기서 다시 찾아가는 방식이다. 이 방식에 특화되어 있는 db는 시간에 따라서 정렬해야 하는 데이터이다. 시간의 범위에 따라서 검색, 탐색 및 수정을 하는 작업에는 이 알고리즘이 좋다. 저장되는 방식을 도식화하면 아래와 같은 그림이 나오게 된다.

 

 

한국인 분들이 친절하게 정리한 사이트도 많아서 자료를 찾기에 편리했다. 하지만 제일 정리가 잘 된 사이트는 아래 사이트라고 생각한다. 시리즈별로 인덱스에 대해서 잘 설명해 주고 있다. 단점은 영어다. 알아서 잘 번역해서 읽어보자. 나는 구글번역기 썼다. (당당)

 

https://postgrespro.com/blog/pgsql/3994098

Indexes in PostgreSQL — 1

 

 

마지막으로 GIN 알고리즘에 대한 소스를 보다가 다음과 같은 문구를 보았다.

 

Gin stands for Generalized Inverted Index and should be considered as a genie, not a drink.

(진 (indexing) 은  Generalized Inverted Index 로 여겨져야 한다, 술이 아닌) 

 

술 종류 중의 진과 발음이 같아서 적어 놓은거 같다 ㅋㅋ

 

https://github.com/postgres/postgres/blob/master/src/backend/access/gin/README

GitHub - postgres/postgres: Mirror of the official PostgreSQL GIT repository. Note that this is just a *mirror* - we don't work