F.36. pg_trgm

F.36.1. Понятия, связанные с триграммами (или триграфами)

Триграмма — это группа трёх последовательных символов, взятых из строки. Мы можем измерить схожесть двух строк, подсчитав число триграмм, которые есть в обеих. Эта простая идея оказывается очень эффективной для измерения схожести слов на многих естественных языках.

F.36.2. Функции и операторы

Реализованные в модуле pg_trgm функции перечислены в Табл. F-26, а операторы — в Табл. F-27.

F.36.3. Параметры GUC

F.36.4. Поддержка индексов

Модуль pg_trgm предоставляет классы операторов индексов GiST и GIN, позволяющие создавать индекс по текстовым столбцам для очень быстрого поиска по критерию схожести. Эти типы индексов поддерживают вышеописанные операторы схожести и дополнительно поддерживают поиск на основе триграмм для запросов с LIKE, ILIKE, ~ и ~*. (Эти индексы не поддерживают простые операторы сравнения и равенства, так что вам может понадобиться и обычный индекс-B-дерево.)

Пример:

CREATE TABLE test_trgm (t text);
CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops);

или

CREATE INDEX trgm_idx ON test_trgm USING GIN (t gin_trgm_ops);

На этот момент у вас будет индекс по столбцу t, используя который можно осуществлять поиск по схожести. Пример типичного запроса:

SELECT t, similarity(t, 'word') AS sml
  FROM test_trgm
  WHERE t % 'word'
  ORDER BY sml DESC, t;

Он выдаст все значения в текстовом столбце, которые достаточно схожи со словом word, в порядке сортировки от наиболее к наименее схожим. Благодаря использованию индекса, эта операция будет быстрой даже с очень большими наборами данных.

Другой вариант предыдущего запроса:

SELECT t, t <-> 'word' AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

Он может быть довольно эффективно выполнен с применением индексов GiST, а не GIN. Обычно он выигрышнее первого варианта только когда требуется получить небольшое количество близких совпадений.

Вы также можете использовать индекс по столбцу t для поиска по схожести. Например:

SELECT t, word_similarity('word', t) AS sml
  FROM test_trgm
  WHERE t %> 'word'
  ORDER BY sml DESC, t;

Этот запрос выдаст все значения в текстовом столбце, содержащие слово, достаточно схожее со словом word, в порядке сортировки от наиболее к наименее схожим. Благодаря использованию индекса, эта операция будет быстрой даже с очень большими наборами данных.

Другой вариант предыдущего запроса:

SELECT t, t <->> 'word' AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

Он может быть довольно эффективно выполнен с применением индексов GiST, а не GIN.

Начиная с PostgreSQL 9.1, эти типы индексов также поддерживают поиск с операторами LIKE и ILIKE, например:

SELECT * FROM test_trgm WHERE t LIKE '%foo%bar';

При таком поиске по индексу сначала из искомой строки извлекаются триграммы, а затем они ищутся в индексе. Чем больше триграмм оказывается в искомой строке, тем более эффективным будет поиск по индексу. В отличие от поиска по B-дереву, искомая строка не должна привязываться к левому краю.

Начиная с PostgreSQL 9.3, индексы этих типов также поддерживают поиск по регулярным выражениям (операторы ~ и ~*), например:

SELECT * FROM test_trgm WHERE t ~ '(foo|bar)';

При таком поиске из регулярного выражения извлекаются триграммы, а затем они ищутся в индексе. Чем больше триграмм удаётся извлечь из регулярного выражения, тем более эффективным будет поиск по индексу. В отличие от поиска по B-дереву, искомая строка не должна привязываться к левому краю.

Относительно поиска по регулярному выражению или с LIKE, имейте в виду, что при отсутствии триграмм в искомом шаблоне поиск сводится к полному сканирования индекса.

Выбор между индексами GiST и GIN зависит от относительных характеристик производительности GiST и GIN, которые здесь не рассматриваются. Как правило, индекс GIN быстрее индекса GiST при поиске, но строится или обновляется он медленнее; поэтому GIN лучше подходит для статических, а GiST для часто изменяемых данных.

F.36.5. Интеграция с текстовым поиском

Сопоставление триграмм — очень полезный приём в сочетании с применением полнотекстового индекса. В частности это может помочь найти слова, написанные неправильно, которые не будут находиться непосредственно механизмом полнотекстового поиска.

В первую очередь нужно построить дополнительную таблицу, содержащую все уникальные слова в документе:

CREATE TABLE words AS SELECT word FROM
        ts_stat('SELECT to_tsvector(''simple'', bodytext) FROM documents');

Здесь documents — это таблица с текстовым полем bodytext, по которому мы будем выполнять поиск. Конфигурация simple используется с функцией to_tsvector вместо конфигурации для определённого языка по той причине, что нам нужен список исходных (необработанных стеммером) слов.

Затем нужно создать индекс триграмм по столбцу со словами:

CREATE INDEX words_idx ON words USING GIN (word gin_trgm_ops);

Теперь мы можем использовать запрос SELECT, подобный показанному в предыдущем примере, и предлагать варианты исправлений слов, введённых пользователем с ошибками. Кроме того, может быть полезно дополнительно проверить, что выбранные слова также имеют длину, примерно равную длине ошибочных слов.

F.36.6. Ссылки

Сайт разработки GiST http://www.sai.msu.su/~megera/postgres/gist/

Сайт разработки Tsearch2 http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/

F.36.7. Авторы

Олег Бартунов <[email protected]>, Москва, Московский Государственный Университет, Россия

Фёдор Сигаев <[email protected]>, Москва, ООО «Дельта-Софт», Россия

Документация: Кристофер Кингс-Линн

Разработку этого модуля спонсировало ООО «Дельта-Софт», г. Москва, Россия.