E.31. pg_trgm

Модуль pg_trgm предоставляет функции и операторы для определения схожести алфавитно-цифровых строк на основе триграмм, а также классы операторов индексов, поддерживающие быстрый поиск схожих строк.

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

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

Замечание: pg_trgm, извлекая триграммы из строк, игнорирует символы, не относящиеся к словам (не алфавитно-цифровые). При выделении триграмм, содержащихся в строке, считается, что перед каждым словом находятся два пробела, а после — один пробел. Например, из строки "cat" выделяется набор триграмм: " c", " ca", "cat" и "at ". Из строки "foo|bar" выделяются триграммы: " f", " fo", "foo", "oo ", " b", " ba", "bar" и "ar ".

E.31.2. Функции и операторы

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

Таблица E-22. Функции pg_trgm

ФункцияВозвращаетОписание
similarity(text, text)realВозвращает число, показывающее, насколько близки два аргумента. Диапазон результатов — от нуля (это значение указывает, что две строки полностью различны) до одного (это значение указывает, что две строки идентичны).
show_trgm(text)text[]Возвращает массив всех триграмм в заданной строке. (На практике это редко бывает полезно, кроме как для отладки.)
show_limit()realВозвращает текущий порог схожести, который использует оператор %. Это значение задаёт минимальную схожесть между двумя словами, при которой они считаются настолько близкими, что одно может быть, например, ошибочным написанием другого.
set_limit(real)realЗадаёт текущий порог схожести, который использует оператор %. Это значение должно быть в диапазоне от 0 до 1 (по умолчанию 0.3). Возвращает то же значение, что было передано на вход.

Таблица E-23. Операторы pg_trgm

ОператорВозвращаетОписание
text % textbooleanВозвращает true, если схожесть аргументов выше текущего порога, заданного функцией set_limit.
text <-> textrealВозвращает "расстояние" между аргументами, то есть один минус значение similarity().

E.31.3. Поддержка индексов

Модуль 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. Обычно он выигрышнее первого варианта только когда требуется получить небольшое количество близких совпадений.

Начиная с 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 для часто изменяемых данных.

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

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

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

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, подобный показанному в предыдущем примере, и предлагать варианты исправлений слов, введённых пользователем с ошибками. Кроме того, может быть полезно дополнительно проверить, что выбранные слова также имеют длину, примерно равную длине ошибочных слов.

Замечание: Так как таблица words была сформирована как отдельная статическая таблица, её нужно периодически обновлять, чтобы она достаточно хорошо соответствовала набору документов. Постоянно поддерживать её в полностью актуальном состоянии обычно не требуется.

E.31.6. Авторы

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

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

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

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