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

Published in

VUNO SW Dev

9 min readSep 8, 2020

안녕하세요, 뷰노 SW 개발팀의 김병묵입니다.

뷰노는 의료영상, 음성인식 그리고 신호처리 분야의 인공지능을 만들고 있습니다. 이 글에서는 의료영상 중 흉부 엑스레이 영상 판독 분야의 웹 서비스를 제공하며 경험한 PostgreSQL GIN 인덱스를 통한 LIKE 검색 성능 개선 사례와 DB 인덱스 및 GIN 인덱스 개념에 대해 설명하려 합니다.

Problem

위 이미지는 VUNO Med®-Chest X-ray 제품의 화면으로 좌측 리스트에서 각 환자의 흉부 엑스레이 영상 리스트를 조회 및 검색할 수 있습니다. 환자의 이름, 환자고유번호 등으로 검색할 수 있으며 이 때 아래 조건을 만족해야 합니다.

검색 창에 입력한 값이 DB에 저장된 값과 완전히 일치하는 경우가 아니라 부분적으로 일치하는 경우에도 조회 되어야 합니다. (ex: “정아”를 입력하는 경우 환자명이 “김정아”, “박정아”, “정아영”인 데이터가 모두 조회되어야 합니다.) 즉, %LIKE% 연산을 수행해야 합니다.

위 상황에 대해 PostgreSQL GIN 인덱스 적용을 통해 인덱스가 적용되지 않았던 경우 대비 약 9~10배 정도 속도를 개선할 수 있었습니다. 이 과정에서 배운 내용에 대해 아래 순서로 설명 드리겠습니다.

I. 인덱스 원리 및 종류
II. B-tree 인덱스와 GIN 인덱스
III. 테스트 환경 구축 및 인덱스 생성
IV. B-tree 인덱스와 GIN 인덱스 성능 비교

I. 인덱스 원리 및 종류

검색 쿼리에 대해 적절한 인덱스가 없는 경우, Full scan을 통해 탐색하게 됩니다. Full scan은 테이블을 처음부터 끝까지 모든 레코드를 체크하며 조건에 맞는 것만 추출하는 방식을 의미합니다. 일반적으로 가장 느린 방식으로 시간복잡도는 O(N)이 됩니다.

해당 검색 쿼리에 적절한 인덱스를 설정하는 경우, 인덱스 자료 구조를 생성하여 보다 효율적으로 탐색한 뒤 이에 대응되는 실제 테이블 레코드에 접근하는 방식으로 추출합니다.

여기서 생각해 볼 점은 검색 쿼리의 종류에 따라 해당 탐색에 적합한 인덱스 자료 구조가 다를 수 있다는 점입니다. 따라서, DB 설계시 수행할 검색 조건에 적합한 인덱스 타입을 결정해야 합니다. PostgreSQL의 경우 12 버젼 기준으로 B-tree, Hash, GiST, SP-Gist, GIN, BRIN 타입을 지원하고 있습니다.

II. B-tree 인덱스와 GIN 인덱스

위 인덱스 타입들 중 가장 일반적으로 사용되는 타입은 B-tree 이며, PostgreSQL는 특별히 타입을 지정하지 않고 인덱스를 생성하는 경우 B-tree 인덱스를 생성합니다. B-tree 인덱스는 데이터의 삽입과 삭제에 대해 항상 균형 트리를 유지하는 자료 구조를 이용해, 순차 비교에 대해 최악의 경우에도 탐색의 시간복잡도가 O(log N)이 되도록 합니다. B-Tree Visualization 링크를 통해 삽입/삭제/탐색시 B-Tree 가 동작하는 방식을 확인할 수 있습니다.

한편, B-tree 인덱스는 인덱스를 적용하는 컬럼의 값을 변형하지 않고 원래의 값을 이용합니다. 따라서 = 연산과 같은 값 자체에 대한 탐색 (single value search)에는 효과적이지만 %LIKE% 연산과 같이 검색어가 데이터 값에 포함 되었는지 여부 (testing the presence of an item)를 확인하는 것에는 적용되기 어렵습니다.

반면, GIN (Generalized Inverted Index) 인덱스는 인덱스를 적용하는 컬럼의 값을 일정한 규칙에 따라 쪼개고(split), 이렇게 쪼갠 요소들을 사용합니다. 이에 따라 포함 여부를 확인하는 경우 보다 효과적으로 동작할 수 있습니다.

또한 값을 쪼개는 방법 및 값의 타입에 따라 적합한 여러가지 operator class들이 있는데, PostgreSQL의 경우 12버젼 기준으로 array_ops, tsvector_ops, jsonb_ops, jsonb_path_ops 의 operator class를 built-in으로 지원하고 있으며, 그 외에도 확장 모듈(extension)을 통해 pg_trgm을 사용할 수 있습니다.

이번 문제에서는 문자열에 대해 간단하게 구현할 수 있는 pg_trgm 라는 operator class를 이용 했습니다. 한편 pg_trgm은 문자열을 3글자 (trigram) 씩 쪼개는 방식이기 때문에 3글자 이상 부터 인덱스를 통한 탐색이 Full Scan 대비 효율적이라는 한계점이 있습니다.

III. 테스트 환경 구축 및 인덱스 생성

위에 설명드린 내용과 관련하여 실제 데이터셋에 대해 1) 인덱스 없는 경우, 2) B-tree 인덱스를 적용한 경우, 3) GIN 인덱스(pg_trgm)를 적용한 경우의 성능을 비교해보기 위해 테스트 환경을 구축하고 인덱스를 생성하였습니다.

테스트 환경은 아래와 같습니다.

PostgreSQL 12.1
실제 환경과 가능한 유사하게 랜덤하게 생성한 1,000,000 건의 환자 정보 레코드 사용

인덱스 설정은 PostgreSQL을 통해 직접 할 수 있고, Sqlalchemy를 통해서도 할 수 있습니다. 아래는 각 경우에 대한 코드 예시입니다.

PostgreSQL에서 하는 경우

# B-tree 인덱스 생성
CREATE INDEX btree_pid_idx ON patients USING btree (pid);
CREATE INDEX btree_name_idx ON patients USING btree (name);# GIN 인덱스 (pg_trgm) 생성
CREATE EXTENSION pg_trgm;
CREATE INDEX gin_pid_idx ON patients USING gin (pid gin_trgm_ops);
CREATE INDEX gin_name_idx ON patients USING gin (name gin_trgm_ops);# 생성된 인덱스 확인
## 생성문과 함께 확인
SELECT * FROM pg_indexes WHERE tablename='patients'; 
## 인덱스 테이블 용량과 함께 확인
\di+# 생성된 인덱스 제거
DROP INDEX <인덱스명>;

Sqlalchemy 에서 하는 경우 (간소화한 코드 예시)

from sqlalchemy.ext.declarative import declarative_basefrom sqlalchemy import Column, String, Index
base = declarative_base()
# B-tree 인덱스 생성
class Patient(base):    
    __tablename__ = 'patients'    
    pid = Column(String(100), index=True)    
    name = Column(String(100), index=True)
    ...
# GIN 인덱스 (pg_trgm) 생성
class Patient(base):    
    __tablename__ = 'patients'    
    pid = Column(String(100))    
    name = Column(String(100))
    ...    __table_args__ = (        
        Index('gin_name_idx', name, 
            postgresql_ops={'name': 'gin_trgm_ops'},
            postgresql_using="gin"),
        Index('gin_pid_idx', pid, 
            postgresql_ops={'pid': 'gin_trgm_ops'},
            postgresql_using="gin"),
        )

IV. B-tree 인덱스와 GIN 인덱스 성능 비교

앞서 생성한 테스트 환경 및 인덱스를 이용하여 성능을 비교해보았습니다. B-tree 인덱스와 GIN 인덱스의 효과 비교를 위해 = 연산 (완전히 값이 동일한 경우)과 %LIKE% 연산 2가지를 모두 테스트 해보았습니다.

성능 확인 및 비교를 위해 PostgreSQL 문법 중 EXPLAIN ANALYSE 를 사용했습니다.

1. = 연산인 경우

사용한 SQL 문은 아래와 같습니다.

EXPLAIN ANALYSE SELECT * FROM patients where patients.pid =’11111' or patients.name ='11111';

위 결과로 부터 아래 사항들을 확인할 수 있었습니다.

= 연산의 경우 B-tree 인덱스가 효과적으로 동작합니다.
GIN 인덱스는 인덱스가 없는 경우와 동일 (Full scan)하게 동작합니다.

2. %LIKE% 연산인 경우

사용한 SQL 문은 아래와 같습니다.

EXPLAIN ANALYSE SELECT * FROM patients where patients.pid LIKE '%11111%' or patients.name LIKE '%11111%';

위 결과로 부터 아래 사항들을 확인할 수 있었습니다.

%LIKE% 연산의 경우 GIN 인덱스가 효과적으로 동작합니다.
B-tree 인덱스는 인덱스가 없는 경우와 동일 (Full scan)하게 동작합니다.

Conclusion

= 연산의 경우 B-tree 인덱스가 효과적이지만, %LIKE% 연산의 경우 GIN 인덱스가 효과적으로 동작하는 것을 확인할 수 있습니다.

이는 앞서 살펴 봤던대로 B-tree 인덱스는 인덱스를 적용하는 컬럼의 값을 변형하지 않고 원래의 값을 이용하므로 값 자체에 대한 비교에 적합하고, GIN 인덱스 (pg_trgm)는 컬럼의 값을 3글자씩 쪼개서 인덱싱에 사용하므로 3글자 이상의 검색에 대해 포함 여부를 파악하기에 적합하기 때문입니다.

한편, 본 문제의 경우 검색 창에 입력한 값이 DB에 저장된 값과 완전히 일치하는 경우가 아니라 부분적으로 일치하는 경우에도 조회 되어야 하므로 GIN 인덱스를 사용하는 것이 보다 적합함을 알 수 있습니다.

References