PostgreSQL로 퍼지 검색 구축

Google은 우리가 무언가를 검색할 때 떠오르는 것을 입력하는 데 익숙해졌습니다.
Postgres 데이터베이스로 이러한 퍼지 검색을 어떻게 달성할 수 있습니까?

기본적으로 세 가지 접근 방식이 있습니다.

ILIKE '%searchterm%'와 패턴 일치하여 문자열 내에서 searchterm를 모두 찾습니다.

포스트그레스full-text search

Postgrespg_trgrm(트라이그램) 확장

이 문서에서는 입력 오류에 민감하지 않고 단어가 완전하지 않은 경우에도 일치해야 하는 퍼지 검색을 원하기 때문에 세 번째 접근 방식에 초점을 맞출 것입니다. 이 두 가지 기준은 처음 두 가지 접근 방식을 기각합니다.
이제 세 번째 접근 방식인 Trigrams에 대해 살펴보겠습니다!

괘

postgres documentation이 트라이그램에 대해 알려주는 내용을 살펴보겠습니다.

A trigram is a group of three consecutive characters taken from a string. We can measure the similarity of two strings by counting the number of trigrams they share. This simple idea turns out to be very effective for measuring the similarity of words in many natural languages.

이것이 무엇을 의미하는지 이해하려면 pg_trgrm 확장의 show_trgrm() 메서드를 확인하십시오.
그러나 먼저 trigram 확장을 활성화해야 합니다.

CREATE EXTENSION pg_trgm;
SELECT show_trgm('Hello');
            show_trgm            
---------------------------------
 {"  h"," he",ell,hel,llo,"lo "}
SELECT show_trgm('Hello World');
                           show_trgm                           
---------------------------------------------------------------
 {"  h","  w"," he"," wo",ell,hel,"ld ",llo,"lo ",orl,rld,wor}

유사성

이 유사성 메서드는 두 문자열이 얼마나 유사한지를 나타내는 0에서 1까지의 숫자를 반환합니다. 값 1은 문자열이 동일함을 의미합니다.
우리의 경우 첫 번째 문자열에는 총 12개의 괘가 있는 두 번째 문자열과 공통으로 6개의 괘가 있기 때문에 0.5입니다.

SELECT similarity('Hello', 'Hello world');
 similarity 
-----------------
        0.5

하지만 유사성 기능으로 큰 문자열에서 작은 문자열을 검색하면 점수가 급격히 떨어집니다. 두 문자열에 없는 트라이그램이 많이 있기 때문입니다.

SELECT similarity('Hello', 'Hello world, you wonderful planet!');
 similarity 
-----------------
 0.19354838

따라서 Postgres는 문자열의 단어 경계를 존중하는 두 가지 다른 기능을 제공합니다.

단어 유사성

단어 유사성 점수는 단어(strict_word_similarity) 각각의 하위 문자열(word_similarity)의 가장 높은 일치 유사도를 반영합니다.

Note: No matter how long the second string gets, the (strict) word similarity will always be 1, because Hello matches exactly a whole word in the example.

SELECT 
word_similarity('Hello', 'Hello world, you wonderful planet!'),
strict_word_similarity('Hello', 'Hello world, you wonderful planet!');
 word_similarity | strict_word_similarity 
----------------------+------------------------
               1 |                      1

The word similarity score can be understood as the greatest similarity between the first string and any substring of the second string. So said, it is useful for finding the similarity for parts of words.

The strict word similarity score is useful for finding the similarity of whole words.

트라이그램 비교의 멋진 점은 단어의 철자가 틀려도 상대적으로 유사성이 높다는 것입니다.

SELECT similarity('wonderfull', 'wonderful'), strict_word_similarity('wonderfull', 'Hello World, you wonderful planet!'), word_similarity('wonderfull', 'Hello World, you wonderful planet!');
 similarity | strict_word_similarity | word_similarity 
-----------------+------------------------+-----------------
       0.75 |                   0.75 |       0.8181818

예시

지금까지는 좋았으니 손을 더럽히자.

서점이 있다고 상상해보십시오. 종종 고객은 제목의 일부만 아는 책에 대해 묻거나 저자의 철자를 정확히 아는 방법을 모릅니다. 퍼지 검색에 딱 맞는 것 같습니다!

단순화를 위해 데이터 세트를 생성해 보겠습니다. 예, 이것이 검색을 위한 가장 아름다운 샘플 데이터가 아니라는 것을 알고 있지만 요점을 이해하시기 바랍니다.

CREATE TABLE books (
  id TEXT,
  title TEXT,
  abstract TEXT,
  author TEXT,
  PRIMARY KEY(id)
);

INSERT INTO books (
    id, title, abstract, author
)
SELECT
    left(md5(i::text), 10),
    left(md5(random()::text), 15),
    md5(random()::text),
    concat_ws(' ', left(md5(random()::text), 10), left(md5(random()::text), 10))
FROM generate_series(1, 100000) s(i);

SELECT * FROM books LIMIT 5;
     id     |      title      |             abstract             |        author         
-----------------+-----------------+----------------------------------+-----------------------
 c4ca4238a0 | 06629ea8b04aaa7 | 9f0ad3e3542ecf1efbdddd98cca507a6 | 4dceb23e53 0f01b57e71
 c81e728d9d | 0a284b57f95d997 | fdd45a7d9eda64c9deb4882ccbb42296 | f3fbf4ed2a ef99e869d2
 eccbc87e4b | b464a24deba866e | 0eda8641e61327719906b493080cd96f | fca64a442c db03ca6331
 a87ff679a2 | 6275469f9e41990 | f3771fb3afdb463d302d7849c38d5641 | fbe106a816 b4313ad5c3
 e4da3b7fbb | b2e9f3a8bad3aec | a9f4b8432c1b6655ae8775dd5b904498 | 6df1b43a13 87c7a303a4

하지만 기다려. 여러 열을 어떻게 검색할 수 있습니까?

잘 잡았다. 여러 열을 검색하려면 concat_ws 함수로 검색해야 하는 모든 열을 연결해야 합니다.

Note: The <% operator returns true if the word_similarity is above the pg_trgm.word_similarity_threshold parameter.

The <% operator has a commutator %<.
So 'Hello' <% 'Hello World' = 'Hello World' %< 'Hello'

SHOW pg_trgm.word_similarity_threshold ;
 pg_trgm.word_similarity_threshold 
----------------------------------------
 0.6

SELECT * FROM books WHERE '9c9f6' <% concat_ws(' ', title, abstract, author);
     id     |      title      |             abstract             |        author         
-----------------+-----------------+----------------------------------+-----------------------
 2804d14b1b | 0152e58b57b94ff | 9c9f468fa58fc140427f7354f1a2b88e | b520b29fae ae1297ce25
 c764c89e73 | 2f81a4878b09a36 | 667ddc5f403d9c96b43912628e1cb73c | ebab7d5c7c 9c9ffbfd82
 5fa8101625 | 30071f6f0e9c9f6 | 5f3250393ac1b214340af81f239e7ca5 | ffec138ddb 3b9060d0c4
 7cb394c278 | ce5ad25e38577fc | 805d0e2ca8081c6a8a178b1f0650c9f6 | 9c5332d434 cd79b0e802
 9b39d07008 | a58ecb6f4e41c96 | 2df452e5bd0b1102733bbc89dd78e6ee | 9c9fb041fa 980becdc8f
(5 rows)
Time: 1245,955 ms (00:01,246)

아야, 너무 오래 걸렸어. 자, 진의 시간입니다!

GIN으로 검색 성능 향상

Postgres에는 이 사용 사례에 대한 특수 인덱스가 있으며 이를 GIN (General Inverted Index) 이라고 합니다.

"GIN is designed for handling cases where the items to be indexed are composite values, and the queries to be handled by the index need to search for element values that appear within the composite items."

완벽하게 맞는 것 같습니다. 그러나 약간의 문제가 있습니다. concat_ws 함수는 변경할 수 없기 때문에 인덱스를 만들 수 없습니다. 연결된 열에 인덱스를 생성하려면 변경할 수 없는 함수 래퍼를 빌드해야 합니다.

-- create immutable function wrapper for concat_ws
CREATE OR REPLACE FUNCTION f_immutable_concat_ws(t1 text, t2 text, t3 text)
  RETURNS text AS
$func$
SELECT concat_ws(' ', t1, t2, t3)
$func$ LANGUAGE sql IMMUTABLE;

-- create a GIN index
CREATE INDEX search_gin_trgm_idx ON books
USING gin (f_immutable_concat_ws(title, abstract, author) gin_trgm_ops);
-- validate performance improvements
EXPLAIN ANALYZE SELECT * FROM books WHERE '9c9f6' <% f_immutable_concat_ws(titale, abstract, author);
                                                           QUERY PLAN                                                           
-------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on books  (cost=21.68..152.10 rows=100 width=82) (actual time=1.937..2.394 rows=5 loops=1)
   Filter: ('9c9f6'::text <% f_immutable_concat_ws(title, abstract, author))
   Rows Removed by Filter: 13
   Heap Blocks: exact=18
   ->  Bitmap Index Scan on search_gin_trgm_idx  (cost=0.00..21.65 rows=100 width=0) (actual time=1.653..1.663 rows=18 loops=1)
         Index Cond: (f_immutable_concat_ws(title, abstract, author) %> '9c9f6'::text)
 Planning Time: 4.487 ms
 Execution Time: 2.533 ms
(8 rows)

Time: 9,965 ms

예, 이것은 125배 더 빠릅니다! 🏎

여기서 어디로 가야합니까?

시도해 볼 수 있습니다.

strict_word_similarity <<%

GUC Parameters에 대한 또 다른 유사성 임계값 설정

검색 문자열에 여러 단어가 포함된 경우 모든 단어에 대해 위의 WHERE 조건을 사용하고 AND로 연결합니다.

구문 유사성만으로는 충분하지 않습니까?
Word2vec은 단어의 의미적 유사성을 비교하는 옵션이 될 수 있습니다. 운 좋게도 이미 이에 대한 postgres-word2vec extension이 있습니다.

의견에서 Postgres에 대한 퍼지 검색에 대한 솔루션에 대해 듣고 싶습니다.

건배!