GIN + trigram 실습 노트 (2) — 유사도 함수 / GiST

13. similarity() vs word_similarity() 개념

similarity()는 이런 식으로 계산됨:

similarity = 공통 trigram 개수 / 전체 trigram 개수 (합집합)

14. similarity() 검증

SELECT similarity('postgresql', 'postgres');

결과:

0.6666667

손으로 검증:

'postgresql' 토큰(11개): p, po, pos, ost, stg, tgr, gre, res, esq, sql, ql
'postgres'   토큰(9개) : p, po, pos, ost, stg, tgr, gre, res, es
공통(8개): p, po, pos, ost, stg, tgr, gre, res

similarity = 8 / (11 + 9 - 8) = 8 / 12 = 0.667

SELECT similarity('공원 코스', '공원 산책');

결과:

0.33333334

15. word_similarity() 개념 및 비교

word_similarity(): 긴 문자열 안에서 검색어와 가장 잘 맞는 부분 구간만 잘라내서 유사도를 계산하는 함수. 짧은 검색어로 긴 텍스트를 부분 검색할 때 사용됨.

SELECT similarity('공원', '서울 공원 코스는 정말 좋은 산책로입니다');

결과:

0.13043478

SELECT word_similarity('공원', '서울 공원 코스는 정말 좋은 산책로입니다');

결과:

1

결론: similarity()는 두 문자열이 전체적으로 얼마나 닮았는지를 보고, word_similarity()는 짧은 검색어가 긴 문자열 어딘가에 얼마나 잘 그대로 존재하는지를 봄.

16. 구조도 정리

GIN (인덱스 자료구조, 역인덱스)
  └─ gin_trgm_ops (pg_trgm 확장이 제공하는 연산자 클래스)
       ├─ 토큰화 방식: trigram
       └─ 이 토큰 덕분에 인덱스를 탈 수 있는 연산자
            ├─ LIKE / ILIKE / ~ (정규식)
            └─ %  (유사도 임계값 검색)

pg_trgm 확장이 제공하는 유사도 계산 함수 (인덱스와 별개, 순수 계산)
  ├─ similarity(a, b)       → 전체 문자열 기준 유사도
  └─ word_similarity(a, b)  → 부분 매칭 기준 유사도

B-Tree에서는 LIKE '%...%'는 꿈도 못 꿈. 앞에 %가 있으면 풀스캔 때려버림. GIN trigram에서는 LIKE '%...%'가 인덱스 타버림 (검색어 길이 조건은 앞서 실습에서 확인함).

17. % 연산자 — 유사도 임계값 검색

% 연산자 : 특정 문자열과 전체적으로 비슷한지를 묻는 연산자.

SHOW pg_trgm.similarity_threshold;

결과:

0.3

SELECT * FROM route WHERE name % '공원코스';

결과:

1    "서울대공원코스"

LIKE '%...%' vs % 차이

• LIKE : 그 문자열이 글자 그대로, 순서대로 포함되어 있는가
• % : trigram 집합끼리 겹치는 비율이 임계값(기본 0.3) 이상인가

즉, %는 내부적으로 similarity()를 사용하고 있는 거임. similarity()가 계산한 값을 임계값보다 높은지 필터링해서 보여주는 연산자 형태임.

18. <% 연산자 — word_similarity 임계값 검색

<%는 내부적으로 word_similarity()를 쓰는 것.

SHOW pg_trgm.word_similarity_threshold;

결과:

0.6

SELECT * FROM route WHERE '공원' <% name;

결과:

5000     "서울5000번 공원 코스"
10000    "서울10000번 공원 코스"
15000    "서울15000번 공원 코스"
20000    "서울20000번 공원 코스"
25000    "서울25000번 공원 코스"
30000    "서울30000번 공원 코스"
35000    "서울35000번 공원 코스"
40000    "서울40000번 공원 코스"
45000    "서울45000번 공원 코스"
50000    "서울50000번 공원 코스"
50006    "하늘 공원 가자"

같은 결과를 word_similarity() 함수로 직접 재현:

SELECT * FROM route WHERE word_similarity('공원', name) >= 0.6;

결과:

(위와 완전히 동일한 11건)

인덱스 타는지 확인:

EXPLAIN ANALYZE
SELECT * FROM route WHERE '공원' <% name;

결과:

"Bitmap Heap Scan on route  (cost=34.45..52.76 rows=5 width=587) (actual time=0.080..0.137 rows=11.00 loops=1)"
"  Filter: ('공원'::text <% (name)::text)"
"  Heap Blocks: exact=10"
"  Buffers: shared hit=18"
"  ->  Bitmap Index Scan on idx_route_name_trgm  (cost=0.00..34.45 rows=5 width=0) (actual time=0.040..0.040 rows=11.00 loops=1)"
"        Index Cond: ((name)::text %> '공원'::text)"
"        Index Searches: 1"
"        Buffers: shared hit=8"
"Planning:"
"  Buffers: shared hit=1"
"Planning Time: 0.502 ms"
"Execution Time: 0.177 ms"

인덱스 당연히 탐. (Index Cond에 %>로 연산자가 바뀌어 나오는데, 이건 GIN 인덱스가 컬럼을 왼쪽에 두고 비교해야 해서 <%의 좌우를 뒤집은 짝 연산자(%>)로 자동 치환된 거임 — 계산 결과는 동일함.)

19. tsvector

trigram과 다르게 형태소 분석기를 거쳐 단어 단위로 쪼갬.

SELECT to_tsvector('english', 'The cats are running fast');

결과:

'cat':2 'fast':5 'run':4

근데 한국어는 기본으로 지원 안 함.

SELECT to_tsvector('simple', '자전거를 타고 공원에 갔습니다');

결과:

'갔습니다':4 '공원에':3 '자전거를':1 '타고':2

띄어쓰기 기준으로만 자름 (형태소 분석 없음 — "공원에"가 "공원"으로 안 바뀜).

mecab-ko 같은 외부 형태소 분석기를 확장으로 연결하면 진짜 한국어 형태소 분석이 가능함 (별도 형태소 분석 엔진을 서버에 설치하고, PostgreSQL이 그걸 불러쓸 수 있게 연결하는 확장 — mecab-ko 자체나 pg_mecab 같은 프로젝트 — 을 별도로 빌드/설치해야 함. 안 해봐서 잘 모르는 영역).

정정할 부분: "trigram 쓰면 mecab-ko 없이도 되니까 trigram이 더 이득"이라고 적었는데, 이건 좀 과한 일반화임. trigram은 부분 문자열/오타 허용 검색엔 강하지만, tsvector(형태소 분석) 쪽이 잘하는 게 따로 있음 — 예를 들어 관련도 순 랭킹(ts_rank), 불용어 처리, "정확한 단어 단위" 매칭의 정밀도 같은 거임. 그러니까 "trigram이 항상 이득"이 아니라, 부분 검색/오타 허용이 핵심이면 trigram, 랭킹/정확한 단어 매칭이 핵심이면 형태소 분석(mecab-ko + tsvector) 이렇게 용도에 따라 갈리는 문제임. 이력서에서도 trigram과 pgvector(임베딩)를 Strategy 패턴으로 전환 가능하게 설계하신 것도 결국 "trigram 하나로 다 되는 게 아니다"라는 전제가 깔려있는 설계였음.

20. GiST (Generalized Search Tree)

B-Tree처럼 계층적으로 좁혀나가는 트리이지만, B-Tree처럼 "정확히 같다/크다/작다"가 아니라 "이 영역 안에 있다/겹친다/가깝다" 같이 추상적이고 애매한 관계를 다루는 걸로 일반화된 구조임.

동작 방식: 트리의 각 노드가 "이 아래 자식들은 전부 이런 특성 범위 안에 있다"는 경계 정보를 들고 있음.

더 구체적으로: 특정 데이터를 찾기 위해 들어오면, 아래 자식 노드들 각각에 "이걸 넣으면 그 자식의 서명을 얼마나 더 넓게 확장해야 하나?"를 계산함 (확장 비용). 확장 비용이 가장 적은 쪽으로 데이터를 넣음.

(서명 = 문자열 하나를 고정된 크기의 비트 뭉치로 압축한 요약본)

찾을 목적 데이터(F), 왼쪽 자식(L), 오른쪽 자식(R)이라고 하면, F의 서명은 01001101... 이런 식으로 32비트 정도의 비트 패턴으로 되어있음. F를 L, R 각각과 비교해서 관련 없는 쪽은 무시하고 관련 있는 쪽으로 이동함.

검색 단계에서는 <-> 연산자 사용.

CREATE INDEX idx_route_name_gist
ON route USING gist (name gist_trgm_ops);

결과:

CREATE INDEX
Query returned successfully in 1 secs 632 msec.

확실히 오래 걸림. 왜냐면 얘는 넣을 때마다 비용 계산해서 어디로 갈지 정함 (서명으로 압축해서 어디로 갈지 정함):

1. 그 행의 trigram 집합을 서명(고정 크기 비트로 압축)으로 만듦 — 계산 작업
2. 트리 루트부터 시작해서, 왼쪽/오른쪽(또는 여러 자식) 중 "이 서명을 넣으면 어디가 제일 덜 넓어지나"를 계산 — 비교 연산
3. 리프까지 내려가서 삽입
4. 만약 그 노드가 꽉 차 있으면 분할(split) 알고리즘까지 돌림 — 이것도 추가 계산

21. <-> 정렬 검색

SELECT name, name <-> '대공원코스' AS distance
FROM route
ORDER BY name <-> '대공원코스'
LIMIT 5;

결과:

"서울대공원코스"          0.6
"서울5000번 공원 코스"    0.94736844
"서울40000번 공원 코스"   0.94736844
"서울20000번 공원 코스"   0.94736844
"서울50000번 공원 코스"   0.94736844

<->는 1 - similarity(a, b)로 계산됨. 즉 거리 = 1 - 유사도.

SELECT similarity('대공원코스', '서울5000번 공원 코스');

결과:

0.05263158

(1 - 0.94736844 = 0.05263156 — 반올림 오차 범위 내에서 정확히 일치함)

22. GiST 인덱스 타는지 확인

EXPLAIN ANALYZE
SELECT name, name <-> '대공원코스' AS distance
FROM route
ORDER BY name <-> '대공원코스'
LIMIT 5;

결과:

"Limit  (cost=0.28..0.72 rows=5 width=27) (actual time=12.772..13.100 rows=5.00 loops=1)"
"  Buffers: shared hit=500"
"  ->  Index Scan using idx_route_name_gist on route  (cost=0.28..4452.42 rows=50007 width=27) (actual time=12.770..13.096 rows=5.00 loops=1)"
"        Order By: ((name)::text <-> '대공원코스'::text)"
"        Index Searches: 1"
"        Buffers: shared hit=500"
"Planning Time: 0.357 ms"
"Execution Time: 13.753 ms"

idx_route_name_gist 인덱스 정확히 탐.

23. GIN vs GiST 정리

	GIN	GiST
인덱스 생성/쓰기 (INSERT, UPDATE)	빠름	상대적으로 느림
LIKE, % 같은 필터 검색	매우 빠름, 정확	상대적으로 느림 (근사치라 recheck 필요)
ORDER BY ... LIMIT (Top-K 정렬)	못 함 (전체 계산 필요)	빠름 (트리 타면서 가지치기)

→ 정렬이 필요 없는 필터링만 필요하면 GIN, 유사도 순 정렬(Top-K)이 필요하면 GiST가 적합함. 실무에서는 두 인덱스를 같은 컬럼에 동시에 걸어두고, 쿼리 종류에 따라 옵티마이저가 알아서 골라 쓰게 하는 것도 가능함.