[Database][Postgresql] Full Text Search(FTS) -1

자체 서비스에서 주소 검색 서버를 개발하는 프로젝트를 진행했던 적이 있다. 주소 데이터베이스 구축부터 검색 서버까지 개발하는 프로젝트였다. 서드 파티를 사용하면 되지, 왜 자체 주소 검색 서비스를 만드는가에 대한 의문도 있겠지만 이는 도메인 특성상 주소나 영역에 대해서 서드파티로는 한계가 있던 부분이 많았기 때문이었다.

이때 사용했던 postgresql의 full text search에 대해 조사했던 것을 다시 정리해 보았다. (나중에는 postgresql > elasticsearch로 개발하였다.)

내용이 조금 많기에 순차적으로 포스팅할 예정이다. 이번 포스팅에서는 Full text search에 사용되는 기본 개념을 소개하고 다음 포스팅에서는 정확한 주소 검색을 위해 고민했던 방법에 대해서 정리해 보려고 한다. (당시 정리 없이 기록하여 기억을 더듬어 적어야 하기 때문에 시간이 조금 걸릴 수도..)

오늘의 목차는 아래와 같다

1. 인덱스를 타지 않는 like %keyword% 검색

2. text search를 위한 index type

3. 텍스트를 분석하는 tsvector , tsquery

4. 마무리

1. 인덱스를 타지 않는 like %keyword% 검색

일치하는 text를 찾기 위해 like 쿼리를 사용한다. 하지만 like 검색은 인덱스를 타지 않는다.

B-tree 인덱스는 정렬된 순서로 저장이 되고 LEFT-TO-RIGHT 방식으로 왼쪽에서 오른쪽으로 정렬되는 방식으로 데이터를 저장하고 탐색한다. 즉, 첫 번째 문자부터 순차적으로 비교하도록 최적화되어있다. 시작문자로 되어있는 Like검색은 이게 적용이 된다. ( like'keyword%' ) 이런 특성으로 주로 '<   <=   =   >=   >'  등의 연산과 같이 특정 값, 범위 내에 있는 값을 찾을 때 적절하다.

LIKE '%keyword%' 의 경우엔 정렬된 순서를 사용할 수 없어서 전체 테이블을 검색하게 된다. % 나 와일트카드(*)가 중간에 있는 경우도 마찬가지다. 이 경우 인덱스가 적용되지 않기 때문에 데이터의 양이 증가할수록 시간이 선형적으로 증가한다 O(n)의 시간 복잡도를 갖는다
아래와 같이 테이블이 있다고 했을 때 각 LIKE '%keyword%' , like'keyword%' 검색의 인덱스 사용 유무를 확인할  수 있다.

mydatabase=# select doc_btree from ts;
                       doc_btree
--------------------------------------------------------
 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.
(9 rows)

- LIKE 'keyward%'

- LIKE '%keyword%'

다행히 postgresql에서는 text 검색을 위해 지원해 주는 기능이 있다. text검색을 위한 index가 있고 여러 익스텐션을 사용해서 전문검색을 지원한다. 이 공식문서를 확인해 보면 postgresql가 지원하는 full text serarch에 대해 자세히 알 수 있다.

 

2. text search를 위한 index type

이 postgresql의 공식문서를 확인해보면 전문 검색을 위한 인덱스로 GiST 인덱스와 Gin 인덱스를 소개한다

보통 GiST보다 Gin 인덱스를 텍스트 검색에 더 많이 사용한다. 무슨 차이가 있는지 알아보자

2.1 GiST Index

GiST Index 공식문서

64.2. GiST Indexes

1. GiST란
   GiST(Generalized Search Tree)는 다양한 데이터 타입과 검색 연산을 지원할 수 있도록 설계된 플러그인 인덱스 구조이다. 덕분에 GiST를 이용해서 텍스트, 기하학적 데이터, 범위 데이터 등 복합 데이터 타입에 대한 검색을 최적화할 수 있다.
   GiST index는 보통 PostGIS와 함께 사용하면서 지리적 좌표나 다각형 등 기하학적인 데이터를 검색할 때 효율적으로 검색할 수 있도록 한다. 나 또한 PostGIS에서 공간 데이터를 다룰 때 GiST 인덱스로 인덱싱을 했었다.
   뿐만 아니라 tsvector(Full text search를 위해 문서를 토큰화하는 방법 중 하나)와 함께 결합하여 full text search로도 사용될 수 있다.
2. GiST 구조
   GiST는 균형 트리로 구성되어 있다. root, internal, leaf노드로 구성된다. 각 노드는 여러 개의 자식 노드를 갖고 있는데 상위 노드는 각 자식노드가 포함하는 데이터의 범위를 포함하고 있다. 리프노드는 실제 데이터가 저장되는 위치를 가리킨다. 여기에 추가적으로 GiST는 signature로 인덱스를 고정 길이의 비트맵 바이트로 변환하여 저장한다. 이를 통해 단어 집합의 크기에 영향을 받지 않을 수 있다.
   글로만 보면 어려우니까 간단하게 GiST인덱스를 적용한 테이블을 만들어보고 확인해 보자.
   ( 참고로 to_tsvector는 tsvector로 만드는 함수이다. 간단하게 말하면 문서(row)를 파싱, 정규화, 불용어를 제거, tsvector 형식으로 변환하는 함수이다. 아래에 정리를 해두었다. )

-- 1. 테이블 생성 및 tsvector 컬럼 지정
CREATE TABLE documents (
    id SERIAL PRIMARY KEY,
    content TEXT,
    tsv_content TSVECTOR GENERATED ALWAYS AS (to_tsvector('english', content)) STORED
);

-- 2. GiST 인덱스 생성
CREATE INDEX idx_gist_documents ON documents USING GIST (tsv_content);

-- 3. 데이터 삽입
INSERT INTO documents (content) VALUES
('PostgreSQL is a powerful database.'),
('Database management systems are important.'),
('A powerful system provides high performance.');

-- 4. 변환 결과 확인
mydatabase=# SELECT * FROM documents;

tsv_content 칼럼을 확인해 보면 database : 숫자 형식으로 되어있는데 이것은 database라는 단어가 해당 row에서 다섯 번째에 있다는 의미이다

GiST 인덱스의 상위 노드는 자식 노드의 데이터 범위를 포함한다고 했다. 아래의 그림과 같이 internal node는 leaf node의 문자 집합을 union 한 것을 key로 갖는다. 그리고 그 상위 노드는 다시 자식 노드의 문자 집합을 key로 갖는 형태이다.

그리고 아래와 같이 쿼리를 하게 되면 power가 포함된 두 개의 row가 출력된다

index 검색을 확인해 보면 아래와 같이 진행된다

추가적으로 위에서 고정 길이의 비트맵 바이트로 변환하여 저장한다고 하였다. root로 갈수록 단어의 집합이 커지므로 매우 비효율적이다. 비트맵으로 변경하면 아래와 같은 모양이 된다 (참고 사이트 https://postgrespro.com/blog/pgsql/4175817)

이런 고정된 길이의 비트 시그니처를 사용하여  데이터를 압축해서 표현하므로 필요한 노드만 검색하게 되어 검색속도는 빠를 수 있지만 Lossy 특성(일부 정보가 손실될 수 있음)으로 인해 정확한 데이터 구분이 어려울 수 있다. 만약 다른 데이터가 동일한 비트 위치에 매핑되면 다른 단어임에도 불구하고 일치한다고 잘못 판단할 가능성이 있다. 따라서 GiST 인덱스는 정확도가 크게 중요하지 않거나 삽입과 삭제가 빈번한 경우 사용할 수 있을 것 같다.

2.2 GIN Index

GIN Index 공식문서

64.2. GiST Indexes

1. Gin Index 란

GIN 인덱스는 Generalized Inverted Index의 약자로, 데이터베이스에서 '역 인덱스' 역할을 한다. 이는 책의 맨 뒷장에서 특정 단어가 들어있는 페이지들이 적혀있는 '찾아보기'와 유사하게, 특정 "키"가 데이터베이스의 어느 행에 포함되어 있는지를 빠르게 찾을 수 있게 해 준다. GIN 인덱스는 배열, JSON, 텍스트 검색 등 다중 값이 포함된 데이터에서 효율적으로 검색을 수행하도록 설계되어 있다. 예를 들어, 텍스트 검색에서 특정 단어가 등장하는 모든 문서를 찾거나 JSON 필드 내의 값을 빠르게 검색할 때 유용하다."

2. Gin Index 구조

GIN 인덱스는 key, posting list 쌍의 집합이다. 여기서 posting list는 key를 포함하는 행의 ID집합이다.

위의 그림은 GIN 인덱스 공식문서에서 가져온 내부 구조이다. 각 구조에 대한 설명은 아래와 같다.

- meta page : GIN 인덱스의 메타데이터를 저장하는 페이지이다. 인텍스에 포함된 키의 수, 현재 사용 중인 구조에 대한 정보 등이 저장된다.

- entry tree : GIN 인덱스의 핵심 부분으로 B-tree 구조로 구성되어 있다.  GIN 인덱스는 key를 중심으로 구성되고 이 key는 Entry tree에 저장된다. 각 key는 posting list 또는 posting  tree로 연결된다.

- posting list : 특정 키가 포함된 행(문서 등)의 ID 목록을 단순히 저장한다. 예를 들면 "database"라는 단어가 다섯 개의 문서에서만 나타나면, 이 단어에 대한 포인터 리스트가 다섯 개의 행 ID를 포함한다

- posting tree : 특정 키가 수백 개 이상의 많은 행(문서 등)에 나타나면 단순리 리스트에 모든 행 ID를 저장하기 힘들다. 이런 경우 행 ID들을 B-tree 구조로 구성하여 저장한다.  

- pending list : 인덱스가 업데이트될 때 새로운 항목을 임시로 저장하는 영역이다. 업데이트가 발생할 때마다 GIN 인덱스는 바로 트리를 재구성하지 않고 이 panding list에 기록한다. 이는 나중에 vacuum, Auto analyze, gin_clean_pending_list함수가 호출되거나 gin_pending_list_limit을 넘기는 경우 GIN 인덱스 구조로 이동한다.

pending list는 업데이트 성능을 빠르게 해 주지만 쿼리 검색 시 pending list도 추가적으로 스캔을 해야 하기 때문에 너무 많을 경우 검색 속도가 느려질 수 있다. 이런 경우 autovacuum을 적절히 사용하여 pending list가 커지기 전에 정리가 되도록 수행하여 문제를 최소화할 수 있다.

GIN 인덱스를 통한 검색 과정은 쿼리가 들어오면 Entry tree를 탐색하여 해당 키를 찾는다. 키는 posting tree 또는 posting list로 연결되며 이를 통해 키가 포함된 모든 행을 바르게 찾을 수 있다.

2.3 GiST 인덱스 VS GIN 인덱스

정리를 해보면 다음과 같다

GiST 인덱스는 데이터의 서명을 비교하여 일치 여부를 판단한다. 이런 구조는lossy 한 특성을 갖기 대문에 false positive(일부 잘못된 일치)가 발생할 수 있다.  하지만 GIN 인덱스는 키(단어)를 중심으로 인덱스를 생성하고 해당 키가 포함된 모든 row ID를 관리하는 구조를 갖는다. 이런 구조를 통해 특정 단어를 포함하는 문서의 위치를 즉시 검색할 수 있다. 뿐만 아니라 단어를 기준으로 검색하므로 GiST보다 정확한 검색 결과를 얻을 수 있다. 

요구사항과 목적에 따라 다르겠지만 만약 검색 쿼리와의 유사도 및 정확도가 중요하다면 GIN 인덱스를 사용하는 것이 더 유리해 보인다.

3.  텍스트를 분석하는 tsvector , tsquery

GIN 인덱스는 key를 기준으로 역 인덱싱을 한다고 했다. 그렇다면 key는 어떤 기준으로 정해야 할까? 공백을 기준으로 분리할 수도 있고 특정 문자를 기준으로 할 수도 있다. 이런 기준은 데이터의 특성을 분석하고 사용자의 쿼리 패턴을 분석하여 결정할 수 있다.

이렇게 인덱스를 하기 위해 key를 분석하는 것 중 하나가 tsvector, tsquery이다.

공식문서를 확인해 보면 postgresql에서는 text search를 위해 아래와 같은 단계를 통해 텍스트에 대해 전처리를 한다. 텍스트 검색 시 이 전처리된 데이터를 통해 검색을 함으로써 전문검색이 가능하도록 한다.

전처리를 단계별로 확인해 보자

1. Parsing documents into tokens(토큰화) : 문서를 작은 단위로 나누는 것을 의미한다. 작은 단위는 숫자, 단어, 복합어, 이메일주소 등 다양한 형태일 수 있으며 'Parser'를 사용하여 토큰화를 한다. 기본적으로 표준 파서가 제공되며 사용자 정의 파서 또한 만들 수 있다

2. Converting tokens into lexemes(토큰 정규화) :
   Lexem이란 같은 의미를 가진 단어들을 하나의 형태로 통일한 것을 의미한다. 검색에 유용하지 않는 불용어(is, a 등) s, es 등의 접미사를 제거하여 단어의 변형된 형태들을 통일시킨다. postgresql은 이 작업을 위해 사전(dictionary)을 사용한다. 표준사전이 존재하며 사용자 정의 사전도 만들 수 있다. 이 작업을 통해 비슷한 의미의 단어의 다양한 변형을 통일시킬 수 있다.

3. Storing preprocessed documents optimized for searching. : 이렇게 전처리가 된 문서는 검색에 최적화된 형태로 저장된다. 정렬된 렉셈 배열로 저장하거나 위치 정보를 같이 저장하여 검색 시 밀집된 문서가 흩어진 문서보다 더욱 높은 쉰 위를 받을 수 있도록 한다.

postgresql에서는 full text search를 위해 tsvector, tsquery 두 가지 타입을 제공한다.

위의 단계를 통해 가공된 문서는 tsvector라는 데이터 타입으로 저장이 된다. 그리고 tsquery 유형을 통해 쿼리를 처리한다.

tsvector가 어떻게 문서를 토큰화하는지 확인해 보자

tsvector, tsquery공식문서

1. tsvector

tsvector 타입은 토큰화된 단어(lexem)와 그 위치 정보를 저장한 자료구조이다. 여러 단어는 정렬되어 있으며 중복되지 않는다. 여기서 단어의 위치란 문서 내에서 해당 단어나 나타나는 위치(토근의 순서)를 나타낸다.
- 아래의 ::tsvector는 텍스트를 tsvector 타입으로 casting 할 때 사용한다. 단순히 형식을 바꾸는 것이며 정규화 등은 하지 않는다. 중복 제거 및 정렬만 한다. 

mydatabase=# SELECT '홍시 맛이 나서 홍시라 생각한 것이온데 왜 홍시 맛이 난다고 하시면'::tsvector;
                                 tsvector
--------------------------------------------------------------------------
'것이온데' '나서' '난다고' '맛이' '생각한' '왜' '하시면' '홍시' '홍시라'

위의 토큰화된 단어를 보면 중복은 제거되었고 정렬됨을 볼 수 있다. (위에서 언급했듯이  ::tsvector는 정규화는 하지 않는다)

실제로 전처리시 사용되는 함수는 to_tsvector이다

to_tsvector는 주어진 텍스트를 파싱 하고, 정규화, 불용어를 제거, tsvector 형식으로 변환하는 함수이다. parser와 dictionary를 사용하여 토큰화, lexem 등의 처리가 수행되며 검색에 사용할 문서 전처리시 사용한다. 아래의 예시를 보자

CREATE TABLE index_test (
    id SERIAL PRIMARY KEY,
    content TEXT,
    tsv_content TSVECTOR GENERATED ALWAYS AS (to_tsvector('english', content)) STORED
);


INSERT INTO index_test (content) 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.');

직접 테이블을 생성해서 content와 tsvector를 적용하여 tsv_content을 생성하였다

tsv_content를 보면 'sheet':3,6과 같이 숫자가 함께 있는 것을 볼 수 있는데 이는 해당 문자가 원본문자에 어떤 위치에 있는지를 표시해 주는 것이다.

그리고 위의 ::tsvector 과는 달리 to_tsvector 함수를 통해 정규화 처리까지 된 것을 확인할 수 있다.

2. tsquery

tsquery는 tsvector에 저장된 텍스트 데이터를 기반으로 검색 쿼리를 작성할 때 사용한다

tsvector로 텍스트를 정규화하고 토큰화를 했으니 검색하는 쿼리 또한 이런 과정이 필요하다. 그래야 서로 비교를 해서 일치하는지 안 하는지 알 수 있기 때문이다. 아래와 같이 to_tsquery를 사용하여 검색할 수 있다.

 

이렇게 토큰화된 키는 아래와 같이 인덱스 생성에 사용될 수 있다.

CREATE INDEX name ON table USING GIST (column [ { DEFAULT | tsvector_ops } (siglen = number) ] );

CREATE INDEX idx_gist_index_test ON index_test USING GIST (tsv_content);

 

postgresql은 문자 정규화를 위해 위와 같은 방식으로 변환하고 쿼리 할 수 있다.

 

4. 마무리

문제의 시작은 like query가 인덱스를 타지 않는데서부터 시작했다. 그리고 전문검색을 위해 postgresql에서 제공해 주는 index타입 두 가지를 알아보았다. 특히 GIN 인덱스는 인덱스는 text를 여러 key로 분리해서 역색인(역인덱싱)을 하여 검색한다.

그리고 key를 분리하는 대표적인 방법인 tsvector 타입을 알아보았다. tsvector로 key를 분리하고 이 키가 역색인에 사용되는 방식인 것이다. 

이외에 key를 분리하는 방법이  존재한다. 이후의 포스팅에서는 이를 위한 extension인 pg_trgm과 pg_bigm을 추가적으로 더 알아보도록 하자!

참고 사이트

https://jojoldu.tistory.com/590

Amazon Aurora PostgreSQL 에서 pg_bigm 모듈사용하기

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