pg_trgm을 사용한 문자열 유사성 검색 및 빠른 LIKE 연산자

SQL은 LIKE 및 % 와일드카드를 허용하는 _ 연산자를 사용하여 문자열에 대한 와일드카드 검색을 지원합니다. LIKE의 문제는 행이 많고 쿼리가 non-sargable 인 경우 매우 빠르지 않다는 것입니다. 그리고 어떤 경우에는 결과가 쿼리와 정확히 일치할 필요가 없는 퍼지 검색 기능을 제공해야 합니다.

PostgreSQL에는 두 가지 문제를 모두 해결하는 pg_trgm extension이 있습니다.

속도 향상을 위한 gin 및 gist 인덱스LIKE 및 기타 문자열 연산자

가 있습니다.

트라이그램을 이용한 문자열 유사도 검색을 위한 similarity 기능과 % 연산자가 있습니다.

다음 테이블이 있다고 가정해 보겠습니다.

CREATE TABLE persons (
    id int4 NOT NULL GENERATED ALWAYS AS IDENTITY,
    forenames varchar(100) NOT NULL,
    surname varchar(100) NOT NULL,
    forenames_normalized varchar(100) NOT NULL,
    surname_normalized varchar(100) NOT NULL,
    CONSTRAINT persons_pk PRIMARY KEY (id)
);

참고: 정규화된 열은 일반 열의 소문자 버전이며 특수 문자는 제거됩니다. 문자 악센트를 제거할 수도 있습니다. 이는 사용자가 정확한 대소문자와 구두점을 입력할 필요가 없기 때문에 사용자에게 더 나은 검색 경험을 제공하기 위한 것입니다.

Bogus에 의해 생성된 10M 행의 가짜 데이터를 테이블에 삽입했습니다. 할 수 있습니다download the dump here.
LIKE 쿼리를 실행하면:

select * from persons p 
where surname_normalized like '%tche%' and forenames_normalized like '%nde%'

내 랩톱에서 결과를 반환하는 데 PostgreSQL이 약 1초가 걸립니다.

Gather  (cost=1000.00..142174.75 rows=10 width=30) (actual time=9.719..639.460 rows=75 loops=1)
  Workers Planned: 2
  Workers Launched: 2
  ->  Parallel Seq Scan on persons p  (cost=0.00..141173.75 rows=4 width=30) (actual time=3.425..605.240 rows=25 loops=3)
        Filter: (((surname_normalized)::text ~~ '%tche%'::text) AND ((forenames_normalized)::text ~~ '%nde%'::text))
        Rows Removed by Filter: 3333308
Planning Time: 0.097 ms
Execution Time: 639.494 ms

모든 행 행이 테이블에서 스캔되는 것처럼 보입니다. 속도를 높이려면 먼저 데이터베이스에서 pg_trgm 확장을 활성화해야 합니다.

create extension if not exists pg_trgm;

그런 다음 정규화된 열에서 gin 인덱스를 사용할 수 있습니다.

create index if not exists idx_gin_persons_on_names on persons using gin (forenames_normalized gin_trgm_ops, surname_normalized gin_trgm_ops)

참고: gin 인덱스 및 gin_trgm_ops 연산자는 pg_trgm 의 일부입니다.
gin 인덱스를 추가하는 데 랩톱에서 1천만 행에 대해 약 1분이 걸렸습니다.

이제 결과가 개선되었는지 살펴보겠습니다.

Bitmap Heap Scan on persons p  (cost=54.20..3692.46 rows=995 width=30) (actual time=4.011..4.066 rows=75 loops=1)
  Recheck Cond: (((forenames_normalized)::text ~~ '%nde%'::text) AND ((surname_normalized)::text ~~ '%tche%'::text))
  Heap Blocks: exact=75
  ->  Bitmap Index Scan on idx_gin_persons_on_names  (cost=0.00..53.95 rows=995 width=0) (actual time=3.999..3.999 rows=75 loops=1)
        Index Cond: (((forenames_normalized)::text ~~ '%nde%'::text) AND ((surname_normalized)::text ~~ '%tche%'::text))
Planning Time: 0.092 ms
Execution Time: 4.120 ms

실행 시간은 639.494 ms 대신 4.1 ms 만 걸립니다! 문서의 모든 행을 순차적으로 스캔하는 대신 gin 인덱스를 스캔했기 때문입니다.

좋습니다. 이제 퍼지 검색을 수행하는 방법을 살펴보겠습니다.

이름이 anderson이고 성이 mitchell인 사람을 찾으려고 한다고 가정해 보겠습니다.

select id, forenames, surname, ((similarity('mitchel', surname_normalized) + similarity('andersen', forenames_normalized)) / 2) as score from persons p
order by score desc
limit 10

이 쿼리를 완료하는 데 약 58초가 걸립니다. similarity 함수는 고가이므로 최대한 사용하지 않도록 노력해야 합니다. 이를 위해 유사성 연산자( % )를 사용하여 특정 임계값 미만인 행을 필터링할 수 있습니다. 기본적으로 임계값은 30% 유사도( 0.3 )이지만 set_limit 를 사용하여 변경할 수 있습니다. 이제 사용해보자:

select id, forenames, surname, ((similarity('mitchel', surname_normalized) + similarity('andersen', forenames_normalized)) / 2) as score from persons p
where forenames_normalized % 'andersen' and surname_normalized % 'mitchel'
order by score desc
limit 10

이제 내 랩톱에서 약 100ms 걸립니다. 58초에 걸친 엄청난 향상 :)

엣지 케이스

pg_trgm는 인덱싱을 위해 트라이그램을 사용합니다. 이는 각 문자열이 가능한 모든 3글자 구성요소로 분할됨을 의미합니다. 예를 들어 mitchel 의 트라이그램은 다음과 같습니다. mit , itc , tch . 그들은 2개의 트라이그램을 공유하므로 che와 hel의 유사도는 30%입니다.

이 접근 방식은 3자 미만의 단어에는 유용하지 않습니다. 트라이그램을 형성할 수 없기 때문입니다. 따라서 이 쿼리는 다음과 같습니다.

select * from persons p 
where surname_normalized like '%he%' and forenames_normalized like '%de%'

PostgreSQL이 두 테이블 모두에 대해 순차적 스캔을 수행하기 때문에 인덱싱된 테이블과 인덱싱되지 않은 테이블 모두에서 동일한 시간이 걸립니다.

Gather  (cost=1000.00..147095.90 rows=49229 width=30) (actual time=1.169..655.329 rows=21216 loops=1)
  Workers Planned: 2
  Workers Launched: 2
  ->  Parallel Seq Scan on persons p  (cost=0.00..141173.00 rows=20512 width=30) (actual time=0.397..583.521 rows=7072 loops=3)
        Filter: (((surname_normalized)::text ~~ '%he%'::text) AND ((forenames_normalized)::text ~~ '%de%'::text))
        Rows Removed by Filter: 3326261
Planning Time: 0.105 ms
Execution Time: 655.974 ms

인덱스가 작업을 느리게 만드는 경우가 있을 수 있습니다. 따라서 자신의 사용 사례에 대해 테스트하고 장단점을 고려하십시오. inserts and updates take longer with the index 도 염두에 두십시오.

벤치마크

BenchmarkDotNet을 사용하여 매우 간단한 벤치마크를 작성했으며 결과는 다음과 같습니다.

// * Summary *

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.928 (2004/?/20H1)
Intel Core i7-8550U CPU 1.80GHz (Kaby Lake R), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.201
  [Host]     : .NET Core 5.0.4 (CoreCLR 5.0.421.11614, CoreFX 5.0.421.11614), X64 RyuJIT
  DefaultJob : .NET Core 5.0.4 (CoreCLR 5.0.421.11614, CoreFX 5.0.421.11614), X64 RyuJIT


|            Method    |         Mean |      Error |     StdDev |     Median |
|---------------------:|-------------:|-----------:|-----------:|-----------:|
|    LikeOnGinIndex    |     5.398 ms |  0.7167 ms |   2.113 ms |   4.170 ms |
|              Like    | 1,035.140 ms | 55.0098 ms | 158.716 ms | 991.495 ms |
| SimilarityOnGinIndex |   137.339 ms | 14.7610 ms |  43.523 ms | 114.342 ms |

참고: GitHub 에서 데이터베이스 덤프 및 코드를 다운로드하십시오.