[PostgreSQL] postgres GIN 인덱스

본 포스팅은 다음 블로그 글을 참고하여 작성하였습니다.

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

Indexes in PostgreSQL — 7 (GIN)

 

개요

GIN은 Generalized Inverted Index로 역색인입니다.

 

GIN의 경우 주로 full text search에서 속도를 높이기 위해 사용됩니다.

 

문자열에서 키워드를 검색할 때 LIKE 연산을 사용하게 되면 index가 걸려있더라도 sequential SCAN을 하게 될 확률이 높습니다. 

 

특히 '%sentence%'와 같이 검색을 하게 되면 인덱스가 걸려있더라도 조건을 확인하기 위해 풀 스캔을 진행하게 됩니다.

 

그에 비해 역색인은 keyword를 기반으로 이 keyword를 사용 중인 문서를 저장하기 때문에 LIKE 연산보다 full text search에 유리합니다.

 

예를 들어 여러 문서에서 "postgres"라는 키워드가 사용되었다고 할 때 "postgres"라는 키워드를 사용한 문서들의 위치를 저장한다면 빠른 키워드 기반 검색이 가능합니다.

 

이번 포스팅에서는 postgres에서 제공해주는 GIN에 대해 알아볼건데 다음과 같은 선행 지식이 필요합니다.

 

1. B-tree 구조
2. full text search
3. Bitmap SCAN
4. TID

혹시 위 개념에 대해 잘 모르신다면 아래 포스팅을 참고하는 것을 추천드립니다.

 

https://growth-coder.tistory.com/22

[Database] Index structures (multi-level oredered) B-tree와 B+ tree

 

https://growth-coder.tistory.com/326

[PostgreSQL] PostgreSQL Full Text Search

 

https://growth-coder.tistory.com/329

[PostgreSQL] postgres SCAN 종류 (Bitmap SCAN)

 

GIN 구조

우선 다음과 같이 테이블을 생성해서 tsvector 컬럼을 생성하고 GIN을 적용합니다.

 

create table ts(doc text, doc_tsv tsvector);

insert into ts(doc) values
  ('Can a sheet slitter slit sheets?'), 
  ('How many sheets could a sheet slitter slit?'),
  ('I slit a sheet, a sheet I slit.'),
  ('Upon a slitted sheet I sit.'), 
  ('Whoever slit the sheets is a good sheet slitter.'), 
  ('I am a sheet slitter.'),
  ('I slit sheets.'),
  ('I am the sleekest sheet slitter that ever slit sheets.'),
  ('She slits the sheet she sits on.');

update ts set doc_tsv = to_tsvector(doc);

create index on ts using gin(doc_tsv);

 

이제 ctid와 tsvecor 컬럼을 출력해서 어떠한 형태인지 확인합니다.

 

참고로 ctid는 물리적 주소로 (블록 인덱스, 오프셋)으로 이루어져 있습니다.

 

select ctid, doc, doc_tsv from ts;

 

tsvector의 값을 보면 keyword 별로 해당 문서의 몇 번째에 등장하는지 알려주고 있습니다.

 

첫 번째 행만 살펴보면 sheet이라는  키워드는 3번째, 6번째에, slit이라는 키워드는 5번째에, slitter라는 키워드는 4번째에 존재하는 모습을 볼 수 있습니다.

 

can, a와 같은 크게 도움되지 않는 키워드는 저장하지 않습니다.

 

각 문서 별로 의미있는 키워드를 추출하고 문서의 어느 위치에 키워드가 나오는지 알려주고 있습니다.

 

이 GIN 구조를 그림으로 보면 다음과 같이 B-tree 구조로 이루어져 있다는 것을 확인할 수 있습니다.

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

우선 키워드를 보면 문자열 순서를 기반으로 자식 노드들이 존재하는 모습을 볼 수 있습니다.

 

 mani와 연결된 키워드들은 mani보다 순서가 빠른 문자열들이고 sleekest와 연결된 키워드들은 mani보다 순서가 느리면서 sleekest보다 순서가 빠르다는 것을 확인할 수 있습니다.

 

B-tree 구조를 알고 있다면 쉽게 이해할 수 있을 것입니다.

 

B-tree의 리프에는 레코드의 물리적 위치 즉, ctid의 리스트 또는 트리가 담겨 있습니다.

 

개수가 적을 경우 list 구조로, 개수가 많을 경우 검색 효율을 위해 tree 구조로 저장하고 있는 모습을 확인할 수 있습니다.

 

이제 keyword 기반 검색의 query plan을 확인해봅시다.

 

아래는 many와 slitter keyword를 모두 포함하는 문서를 검색하는 쿼리입니다.

EXPLAIN ANALYZE select doc from ts where doc_tsv @@ to_tsquery('many & slitter');

 

GIN을 생성했지만 sequential SCAN을 하고 있습니다.

 

아마 데이터의 양이 적었기 때문에 sequential SCAN이 더욱 효율적이라고 내부적으로 판단한 것 같습니다.

 

그러면 동일한 데이터를 100만개 넣어봅시다.

WITH data AS (
  SELECT 'Can a sheet slitter slit sheets?' AS doc UNION ALL
  SELECT 'How many sheets could a sheet slitter slit?' UNION ALL
  SELECT 'I slit a sheet, a sheet I slit.' UNION ALL
  SELECT 'Upon a slitted sheet I sit.' UNION ALL
  SELECT 'Whoever slit the sheets is a good sheet slitter.' UNION ALL
  SELECT 'I am a sheet slitter.' UNION ALL
  SELECT 'I slit sheets.' UNION ALL
  SELECT 'I am the sleekest sheet slitter that ever slit sheets.' UNION ALL
  SELECT 'She slits the sheet she sits on.'
)
INSERT INTO ts (doc)
SELECT doc
FROM data
JOIN generate_series(1, 100000) gs ON true;

 

이제 다시 query plan을 확인해봅시다.

EXPLAIN ANALYZE select doc from ts where doc_tsv @@ to_tsquery('many & slitter');

이번에는 Bitmap SCAN을 하는 모습을 확인할 수 있습니다.

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

 

B-tree에서 mani와 slitter의 TID 리스트를 조회했다면 둘 모두를 만족하는 TID를 찾아야 합니다.

 

 

그 결과로 다음과 같은 문서를 찾았습니다.

느린 갱신

GIN에서 데이터 삽입이나 갱신 속도는 상당히 느립니다.

 

각 문서는 인덱싱 할 많은 키워드들이 존재하고 조금의 변경 사항이 발생해도 인덱스 트리를 대량으로 갱신하게 됩니다.

 

이 문제를 해결하기 위해 fastupdate를 적용할 수 있습니다.

create index on ts using gin(doc_tsv) with (fastupdate = true);

 

fastupdate를 활성화하면 변경 사항은 순서가 없는 리스트에 저장되고 어느 정도 크기가 커지거나 vacuum이 진행될 때 인덱스에 변경 사항이 반영됩니다.

 

하지만 검색을 할 때 순서 없는 리스트도 탐색을 하기 때문에 검색 속도가 느려집니다.

 

그리고 이 리스트가 overflow 될 경우 다음 갱신에 오랜 시간이 걸릴 수 있습니다.

 

어휘의 빈도

위에서 many와 slitter가 동시에 등장하는 문서를 검색하는 과정을 알아보았습니다.

 

그런데 만약 many는 20만 개의 문서에서 등장하고 slitter는 2개의 문서에서 등장하면 어떨까요?

 

many 키워드를 포함하는 20만 개의 문서를 검색하고 slutter를 포함하는 2개의 문서를 검색한 다음 둘 다 만족하는 TID를 찾는 과정은 비효율적입니다.

 

다행히 알고리즘은 어떠한 어휘가 자주 등장하고 어떠한 어휘가 드물게 등장하는지 알고 있습니다.

 

그래서 드물게 등장하는 어휘인 slitter를 먼저 검색한 뒤 검색 결과에서 자주 등장하는 many가 등장하는지 확인하기 때문에 slitter를 단독으로 검색하는 것보다 훨씬 빠르게 검색할 수 있습니다.

 

 

 

set gin_fuzzy_search_limit = 100000;