Полнотекстовый поиск в PostgreSQL

Полнотекстовый поиск в PostgreSQL

Vanya Khodor

Когда в молодых продуктах нужен полнотекстовый поиск как часть функционала (поиск не основная фича), часто можно встретить решение на основе PostgreSQL. Давайте попробуем понять, что такого Postgres вообще умеет для этой задачи и как далеко вы сможете с ним зайти.

Когда вы отдельно поддерживаете полнотекстовый движок вроде Elastic, вы храните информацию и в вашей бдшке, и в движке. Данные дублируются. Конечно, независимость движка даёт некоторые плюсы:

- возможность его кастомизации под сценарий поиска. Но теряется консистентность с основным хранилищем данных.  

- возможность частичной деградации: если в поиске набагали, остальной функционал будет работать. 

Но с другой стороны дублирование данных и повышенные требования к экспертизе имеют свои издержки.

Не будем смотреть на базовые LIKE/ILIKE и регулярные выражения, а сразу пойдём в специализированные для FTS штуки.

Text Search

В Postgre есть несколько типов для полнотекстового поиска: tsvector и tsquery. 

SELECT to_tsvector('The brown fox jumps over the lazy dog');
                 to_tsvector                 
---------------------------------------------
 'brown':2 'dog':8 'fox':3 'jump':4 'lazi':7
(1 row)

tsvector -- это сортированный список уникальных лексем. Лексема -- нормализованное слово из строки (убрали окончания, поменяли склонение). Вместе с лексемами мы получаем информацию о том, где это слово в строке можно найти. Судя по примеру выше это номер слова в строке с подсчётом с 1.

Можно указать позиции словам в тексте самостоятельно:

SELECT 'a:1 fat:2 cat:3 sat:4 on:5 a:6 mat:7 and:8 ate:9 a:10 fat:11 rat:12'::tsvector;
                              tsvector
-------------------------------------------------------------------​----
 'a':1,6,10 'and':8 'ate':9 'cat':3 'fat':2,11 'mat':7 'on':5 'rat':12 'sat':4

Это может быть использовано при proximity ranking.

Если у слова есть позиция, то дополнительно можно указать вес (от A до D), что поможет при их ранжировании:

SELECT 'a:1A fat:2B,4C cat:5D'::tsvector;
          tsvector
----------------------------
 'a':1A 'cat':5 'fat':2B,4C
(1 row)

Важно, что tsvector сам по себе ничего не нормализует. Он считает, что данные, которые в него кладутся, уже нормализованные. Так что эти преобразования происходит в функции to_tsvector.

Ещё один нужный тип -- tsquery:

SELECT 'fat & rat'::tsquery;
    tsquery    
---------------
 'fat' & 'rat'
(1 row)

Тут всё просто. Запрос это набор строк, которые можно соединять с помощью булевых операций & (AND), | (OR) и ! (NOT). 

SELECT 'fat & (rat | ! cat)'::tsquery;
        tsquery
------------------------
 'fat' & ('rat' & !'cat')
(1 row)

Можно догадаться, что использование скобок работает так же, как и в любых других булевых выражениях. 

SELECT 'fat:ab & cat'::tsquery;
    tsquery
------------------
 'fat':AB & 'cat'
(1 row)

Аналогично tsvector, лексемы в запросе могут иметь веса. Они выступают доп ограничением для матчинга лексем из tsvector с только указанными весами.

Очевидно, что мы можем захотеть в префиксный поиск. Это делается *:

SELECT 'super:*'::tsquery;
  tsquery
-----------
 'super':*
(1 row)

Если вы хотите получить tsquery из строки, делаем аналогично to_tsvector:

SELECT to_tsquery('fatty & rat');
   to_tsquery    
-----------------
 'fatti' & 'rat'
(1 row)

Эта функция тоже нормализует все поступающие ей лексемы. Так что результаты поиска не будут удивительными (поиск tsquery по tsvector происходит с помощью @@):

SELECT to_tsvector('postgraduate');
  to_tsvector  
---------------
 'postgradu':1
(1 row)

SELECT to_tsquery('postgres:*');
 to_tsquery 
------------
 'postgr':*
(1 row)

SELECT to_tsvector('postgraduate') @@ to_tsquery('postgres:*');
 ?column? 
----------
 t
(1 row)

Есть ещё дополнительный оператор для поиска: <->. Он означает конкатенацию лексем == ищет в тексте их рядом:

SELECT 
  to_tsvector('The brown fox jumps over the lazy dog') @@ 
  to_tsquery('brown <-> fox');
 ?column? 
----------
 t
(1 row)

Ещё с его помощью можно задавать количество лексем между искомыми: <N>. <-> эквивалентен <1>.

SELECT 
  to_tsvector('The brown fox jumps over the lazy dog') @@ 
  to_tsquery('brown <6> dog');
 ?column? 
----------
 t
(1 row)

Есть ещё всякие дополнительные функции, вроде plainto_tsquery (запрос из строки), phraseto_tsquery (запрос с оператором <->).

Что-то более серьёзное

То, что мы посмотрели выше, это конечно хорошо, но всё-таки данные обычно лежат у нас в БД и мы хотим искать не по одной строке, а по большому их количеству. Тут нам поможет индексация.

В Postgres, упрощённо, есть два основных подхода к индексации данных для поиска:

GIN является стандартным инвертированным индексом (писал тут). Что логично, он склоняет трейдоф между поиском и обновлениями в сторону поиска: он быстрый, а обновления не очень.

GiST это некоторый общий способ укладывания различных поисковых деревьев в Postgres. Тут поиск будет чуть дольше, но зато легче обновлять данные. Обычно, когда пытаются сделать GiST индекс для text search, в вершины укладывают хеши лексем и некоторые битовые маски, которые в родительских вершинах OR-ятся. Правда, раз он хранит хеши, ему нужно перепроверять данные при ответе, что портит его перф. Нужен он в довольно специфических случаях, когда паттерн чтения примерно "часто пишем, редко ищем", так что скорее вам нужен GIN.

Создать индекс можно так (для удобства заведём процедурку make_tsvector):

CREATE TABLE IF NOT EXISTS articles(
    id SERIAL PRIMARY KEY,
    title VARCHAR(128),
    context TEXT
);

CREATE OR REPLACE FUNCTION make_tsvector(title TEXT, content TEXT)
  RETURNS tsvector AS $$
BEGIN
  RETURN (
    setweight(to_tsvector(title), 'A') ||
    setweight(to_tsvector(content), 'B')
  );
END
$$ LANGUAGE 'plpgsql' IMMUTABLE;

CREATE INDEX IF NOT EXISTS idx_articles 
    ON articles
USING gin(make_tsvector(title, content));

И можно поискать (предположим, мы заполнили данными):

SELECT id, title FROM articles 
WHERE 
  make_tsvector(title, content) @@ to_tsquery('bjarne <-> stroustrup');

Правда пока мы будем получать результаты в абсолютно случайном порядке. То есть все строки из articles, которые подходят под запрос. Давайте отранжируем!

Делается это добавлением одного ORDER BY:

SELECT id, title FROM articles,
  to_tsquery('bjarne <-> stroustrup') as q
WHERE make_tsvector(title, content) @@ q
ORDER BY ts_rank(make_tsvector(title, content), q) DESC;

Правда подход выше плохо работает на широких запросах, т.к. GIN не очень хорошо умеет в оптимизации ранжирования.

Стандартного решения нет, но в Postgres Professional чуваки придумали индекс rum, который используется точно так же, но быстрее. Суть в том, что чуваки в метадате в индексе хранят доп инфу, вроде сразу посчитанной релевантности документа для некоторой лексемы, таймстемпы и т.д. Теперь при ранжировании можно не смотреть на документы ещё раз, а сразу сортить по релевантности/свежести и отдавать ответ.

Из важного ещё ранжирование происходит не с помощью ts_rank, а с помощью ts_score, который является комбинацией ts_rank_cd.

Нечёткий поиск (fuzzy search)

Часто при вводе запроса пользователь ошибается. Как исправляются опечатки в движках, я уже писал. Там целое поле для ресёрча. В Postgres так закапываться не надо и можно получить какое-то качество стандартными расширениями.

Например с помощью поиска по n-граммам (pg_trgm):

CREATE EXTENSION pg_trgm;

CREATE INDEX idx_trgm_index ON articles USING gin(title gin_trgm_ops);

Теперь давайте опечатаемся и поищем:

SELECT title, similarity(title, 'Straustrup')
FROM articles
WHERE title % 'Straustrup';
       title        |   similarity
--------------------|----------------
 Bjarne Stroustrup  |      0.35
(1 row)

similarity -- число, показывающее насколько строка похожа на запрос и лежащее в промежутке [0; 1]. По умолчанию возвращаются строки, уровень которых 0.3 или выше. Это значение можно переопределить функцией set_limit.

Стало интересно, почему при одной опечатке similarity падает аж до 0.35. Нашёл следующую формулу: 
similarity = c / (len1 + len2 - c)
где len1 и len2 -- количество уникальных триграмм в словах, а c -- кол-во совпадающих триграмм.
Правда всё равно получается 0.4.
В коде это происходит вот тут. Возможно дело в том, что не всегда используется формула выше, т.к. она лежит под макросом, который может раскрыться в другую. Не получается.
Потом понял, что я неправильно считаю триграммы:
SELECT show_trgm('Stroustrup');
                    show_trgm                    
-------------------------------------------------
 {"  s"," st",ous,rou,rup,str,tro,tru,"up ",ust}
(1 row)
Почему-то они содержат в том числе триграммы с пробелами на концах. Тогда в итоге получится 
similarity = 7 / (10 + 10 - 7) = 0.54
Всё равно не сходится. Оставил копания.

Это же расширение может быть полезно при использовании LIKE. Те же триграммные индексы помогают сильно ускорить большинство запросов с такими конструкциями.

Ещё есть расширение fuzzystrmatch. Поизучать его оставим упражнением.

Немного про словари

to_tsvector и to_tsquery умеют принимать ещё один параметр: словарь.

Например, если ваши документы на английском языке, то можете сделать так:

SELECT to_tsvector('english', 'The quick brown fox jumps over the lazy dog');
                      to_tsvector                      
-------------------------------------------------------
 'brown':3 'dog':9 'fox':4 'jump':5 'lazi':8 'quick':2
(1 row)

Вроде на русском тоже заработает:

SELECT to_tsvector('Быстрая коричневая лиса прыгает через ленивую собаку');
                            to_tsvector                                    
-----------------------------------------------------------------------
 'быстрая':1 'коричневая':2 'ленивую':6 'лиса':3 'прыгает':4 'собаку':7 'через':5
(1 row)

Но мы можем заметить, что слова не нормализованы, что может ощутимо ухудшить качество поиска. Надо поправить!

SELECT to_tsvector('russian', 'Быстрая коричневая лиса прыгает через ленивую собаку');
                         to_tsvector                          
--------------------------------------------------------------
 'быстр':1 'коричнев':2 'ленив':6 'лис':3 'прыга':4 'собак':7
(1 row)

Тут возникает проблема -- поиск на разных языках пока делается только так:

SELECT * FROM articles 
WHERE 
    to_tsvector('english', text) @@
    to_tsquery('english', query)
OR
    to_tsvector('german', text) @@
    to_tsquery('german', query);

Словарей бывает много разных. Есть пак в стандартной postgres, а можно затаскивать свои.

Источники

  1. [documentation] Full Text Search in PostgreSQL.
  2. [talk] Полнотекстовый поиск в PostgreSQL.
  3. [talk] Новые возможности полнотекстового поиска в PostgreSQL.

Тут автор рассказывает про то, почему full text search на БД лучше внешнего движка, но я всё же останусь при своём мнении, что это хороший старт, а не целевая картина.

Report content on this page

Report Page

Please submit your DMCA takedown request to dmca@telegram.org