При создании сервиса мне потребовалось реализовать поиск по разным сущностям (компаниям, сообщениям, документам и др). Каждая сущность имеет свою длину строки, по которой нужно производить поиск. Например, компания имеет короткое название (в среднем 20-40 символов), сообщение имеет текст средней длины (обычно до 200 символов), а документ может быть очень длинным.
В итоге у меня возникли следующие вопросы:
- Какие индексы вообще используются для поиска по тексту?
- Чем они отличаются друг от друга? Сколько они занимают дополнительного места на диске? Какой индекс быстрее производит поиск?
- Какой индекс лучше использовать для поиска по коротким строкам (напр, по названиям компаний), а какой для поиска по длинным строкам (напр, по сообщениям в чате или по содержаниям текстовых документов)? Можно ли использовать один индекс для всех ситуаций?
В рамках данной статьи мы ответим на эти вопросы, сравнив разные индексы и сделав вывод, в каких ситуациях какие индексы стоит использовать для поиска по тексту.
В начале хочу сделать небольшое отступление и ответить на вопрос: зачем вообще нужно использовать индексы и когда их нужно использовать?
Что такое индексы и зачем они нужны
Индексы – это дополнительные структуры данных, которые используются не только для значительного ускорения поиска в базе данных, но и для реализации ограничений целостности (например, ограничения уникальности, с помощью которого можно сделать так, чтобы все значения в колонке были уникальными).
По умолчанию, PostgreSQL автоматически создает индексы для unique (ограничение уникальности) и primary key (ограничение первичного ключа, которое является комбинацией ограничения уникальности и ограничения «не NULL»). Соответственно, если вы используете primary key, то вы уже используете индексы. Для foreign key PostgreSQL не создает индекса, поэтому при использовании JOIN-ов необходимо создавать эти индексы самостоятельно, но это уже не тема данной статьи.
В PostgreSQL существует множество индексов (B-tree, GiST, SP-GiST, GIN, RUM, BRIN, Bloom и др), каждый из которых используется в своей ситуации. Детально все эти индексы описаны в этой серии статей на хабре.
По умолчанию, если создать индекс без указания его названия, то будет создан B-tree индекс, который используется в работе чаще всего.
CREATE TABLE messages (id int, body text);
CREATE INDEX messages_body_idx ON messages (body);Существует негласное правило именования индексов, которое можно посмотреть тут. Им я и буду пользоваться в данной статье.
Если мы хотим воспользоваться другим индексом, например, GIN, то нужно указать его явно:
CREATE INDEX messages_body_idx ON messages USING gin (body);Если вы разрабатываете новый сервис и у вас пока нет пользователей, то может возникнуть хороший вопрос: «Зачем мне нужно использовать индексы, если у меня пока мало пользователей? Вот когда будут высокие нагрузки, вот тогда и буду разбираться с индексами».
С одной стороны вы будете правы. Пока на ваш сервис заходит пара землекопов в день и пока в базе хранится лишь несколько сотен сущностей, то вы не увидите разницы между наличием и отсутствием индексов. Более того, планировщик запросов PostgreSQL может предпочесть последовательное сканирование таблицы, как будто индекса и вовсе нет.
Однако, при разработке сервиса вы продумываете его структуру, проектируете базу данных и закладываете основу, на которую в дальнейшем накладываются доработки. И не хотелось бы, когда будет приток активных пользователей столкнуться с медленным выполнением запросов к базе данных, от чего UI будет подвисать, что будет «бесить» ваших пользователей. Причем, вы не узнаете в какой момент все начало медленно работать, пока вам кто-нибудь не напишет. Однако, на практике крайне редко кто-то пишет – если что-то не работает, то просто уходят с сервиса, тем более, если только что зарегистрировались. Устранение проблемы может повлечь за собой переписывание части основного функционала вашего сервиса, изменение структуры базы данных и самих SQL-запросов. Вы к этому готовы? Быстрее и надежнее предусмотреть это сразу при разработке сервиса.
Какие индексы можно использовать для поиска по тексту?
В начале выдвинем требования к индексу и отсортируем их по приоритету. Итак, выбранный индекс должен:
- Поддерживать поиск по любой части подстроки. Например, введя в строку поиска «центр» у пользователя должна отобразиться сущность с названием «Детский центр».
- Находить не точные совпадения. Например, по запросу «центры» сущность с названием «Детский центр» также должна отобразиться.
- Быть нечувствительным к регистру. По запросу «Центр» должна найтись сущность «Детский центр».
- Поддерживать ограничение выборки, используя LIMIT, чтобы реализовать пагинацию.
- Поддерживать сортировку по релевантности поисковому запросу.
- Производить поиск как можно быстрее.
- Занимать как можно меньше места на диске.
В целом для поиска по тексту можно использовать либо триграммы (pg_trgm), либо полнотекстовый поиск (Full Text Search). Давайте в начале разберемся с ними, а затем вернемся к сравнению индексов.
Триграммы
Поиск состоит в следующем. Строка разбивается на множество триграмм. Триграмма – это 3 последовательные символа.
SELECT show_trgm('word'); -- {" w"," wo",ord,"rd ",wor}При этом игнорируются символы, которые не являются буквой или цифрой.
SELECT show_trgm('a&b'); -- {" a"," b"," a "," b "}Также игнорируется регистр букв.
SELECT show_trgm('A'); -- {" a"," a "}При создании триграмм к началу строки добавляется 2 пробела, а к концу 1 пробел.
Далее можно сравнить на сколько одна строка (то, что ввел пользователь в строке поиска) похожа на другую (например, на содержание конкретного сообщения), просто посчитав количество схожих триграмм.
SELECT 'elephant' % 'one elephant'; -- TRUE
SELECT similarity('elephant', 'one elephant'); -- 0.6923077Символ % используется для сравнения похожести 2 строк. Если значение выше pg_trgm.similarity_threshold (по умолчанию 0.3), то возвращается TRUE. Значение similarity находится в диапазоне от 0 (строки совершенно разные) до 1 (строки идентичны).
SHOW pg_trgm.similarity_threshold; -- 0.3Это значение можно изменить, например, чтобы сделать поиск более строгим:
SET pg_trgm.similarity_threshold = 0.8;Но давайте оставим это значение по умолчанию.
Если пользователь допустит опечатку в слове «elephant», то результат все равно будет положительным, однако значение similarity упадет.
SELECT 'wlephant' % 'one elephant'; -- TRUE
SELECT similarity('wlephant', 'one elephant'); -- 0.375Однако, если пользователь введет несуществующее слово «cat», то строки будут не похожи.
SELECT 'cat' % 'one elephant'; -- FALSE
SELECT similarity('cat', 'one elephant'); -- 0На самом деле в PostgreSQL 13 существует 3 разные функции для вычисления схожести двух строк: similarity, word_similarity и strict_word_similarity. Каждая из функций вычисляет схожесть строк по-своему.
Чтобы прочувствовать разницу между этими функциями, давайте возьмем строку «dark wood round table» (к примеру, в таблице products у нас есть товар с таким названием) и попробуем определить, на сколько она похожа на разные поисковые запросы (то, что пользователь вводит, чтобы найти этот стол), используя разные функции. Возьмем следующие поисковые запросы:
- «dark» и «wood», которые одинаковы по длине, но располагаются в разных местах строки: одна ближе к началу, другая – дальше.
- «table» и «tabla», чтобы определить, на сколько сильно влияет наличие ошибки в слове.
- «tabl» и «able», чтобы посмотреть, будет ли первая подстрока более релевантной, чем вторая.
- «round table», «wood table» и «dark table», чтобы определить на сколько дистанция между словами влияет на результат.
Поиск товара с названием «dark wood round table»:
+------------------+------------+-----------------+------------------------+
| Поисковый запрос | similarity | word_similarity | strict_word_similarity |
+------------------+------------+-----------------+------------------------+
| dark | 0.22727273 | 1 | 1 |
| wood | 0.22727273 | 1 | 1 |
| table | 0.27272728 | 1 | 1 |
| tabla | 0.16666667 | 0.6666667 | 0.5 |
| tabl | 0.17391305 | 0.8 | 0.5714286 |
| able | 0.125 | 0.6 | 0.375 |
| round table | 0.54545456 | 1 | 1 |
| wood table | 0.5 | 0.64705884 | 0.64705884 |
| dark table | 0.5 | 0.54545456 | 0.54545456 |
+------------------+------------+-----------------+------------------------+Первое, что можно заметить, для similarity важно, чтобы одна строка была максимально похожей на другую строку, а для word_similarity и strict_word_similarity, чтобы первая строка была максимально похожей на один из фрагментов второй строки. Если открыть официальную документацию, то можно увидеть, что так оно и есть: similarity считает общее количество одинаковых триграмм двух строк, а word_similarity считает сколько триграмм из первой строки совпадает с непрерывным фрагментом упорядоченного набора триграмм во второй строке.
Если бы мы использовали для поиска функцию similarity, то пользователь не смог бы найти товар с названием «dark wood round table» по поисковому запросу «table», потому что пороговое значение pg_trgm.similarity_threshold по умолчанию равно 0.3.
Давайте проверим это:
SELECT 'table' % 'dark wood round table'; -- FALSEЧтобы решить эту проблему, можно уменьшить пороговое значение, скажем до 0.2.
SET pg_trgm.similarity_threshold = 0.2;
SELECT 'table' % 'dark wood round table'; -- TRUEОднако, если название товара будет чуть длиннее, то пользователь снова не сможет его найти.
SELECT 'table' % 'dark brown wood round dining table'; -- FALSEПоэтому лучше выбрать функцию word_similarity или strict_word_similarity.
Вернемся к нашей сравнительной таблице. Заметим, что все функции имеют одинаковое значение для «dark» и «wood», а значит, что близость первой строки к началу второй не влияет на результат.
Функция strict_word_similarity при наличии опечатки («tabla» вместо «table») выдает значение меньше, чем word_similarity (0.5 и 0.6666667 соответственно), а значит она более чувствительна к опечаткам. Если ввести «able» вместо «tabl», то при использовании strict_word_similarity значение упадет сильнее, чем при использовании word_similarity.
Давайте посмотрим, будет ли показан товар с названием «dark wood round table», если пользователь в начале введет «tabl», а потом «able». Ранее для сравнения 2 строк, используя функцию similarity мы указывали символ %. Для word_similarity используется символ <%, а для strict_word_similarity символ <<%.
/* word_similarity */
SELECT 'tabl' <% 'dark wood round table'; -- TRUE
SELECT 'able' <% 'dark wood round table'; -- TRUE
/* strict_word_similarity */
SELECT 'tabl' <<% 'dark wood round table'; -- TRUE
SELECT 'able' <<% 'dark wood round table'; -- FALSEЕсли ввести «tabl», то товар будет показан при использовании обоих функций. Если же ввести «able», то при использовании word_similarity товар будет показан, а при strict_word_similarity не будет. Однако, вряд ли пользователь будет искать товар, набирая окончание слова («able» вместо «table»). Скорее будет как раз наоборот – будут искать по префиксу («tabl»). Поэтому strict_word_similarity подходит лучше.
Стоит заметить, что каждая функция имеет свои пороговые значения, которые равны следующим значениям:
SHOW pg_trgm.similarity_threshold; -- 0.3
SHOW pg_trgm.word_similarity_threshold; -- 0.6
SHOW pg_trgm.strict_word_similarity_threshold; -- 0.5Теперь давайте посмотрим, на сколько влияет отсутствие промежуточных слов в поисковом запросе. Напомню, что оригинальная строка – «dark wood round table» (например, название товара).
У similarity, как мы видим, «round table» (нет пропущенных слов) имеет значение немного выше, чем «wood table» (пропущено 1 слово), но это лишь из-за того, что первая строка на 1 символ длиннее второй. Значения для запросов «wood table» (пропущено 1 слово) и «dark table» (пропущено 2 слова) совпадают, что и следовало ожидать, т.к. для similarity важно только количество совпавших триграмм. Однако, чем меньше пропущенных слов, тем результат поиска должен быть более релевантен, а значит функция similarity опять проигрывает.
Давайте теперь посмотрим, будет ли показан наш товар с названием «dark wood round table» пользователю, который будет использовать рассмотренные нами поисковые запросы:
/* similarity */
SELECT 'round table' % 'dark wood round table'; -- TRUE
SELECT 'wood table' % 'dark wood round table'; -- TRUE
SELECT 'dark table' % 'dark wood round table'; -- TRUE
/* word_similarity */
SELECT 'round table' <% 'dark wood round table'; -- TRUE
SELECT 'wood table' <% 'dark wood round table'; -- TRUE
SELECT 'dark table' <% 'dark wood round table'; -- FALSE
/* strict_word_similarity */
SELECT 'round table' <<% 'dark wood round table'; -- TRUE
SELECT 'wood table' <<% 'dark wood round table'; -- TRUE
SELECT 'dark table' <<% 'dark wood round table'; -- TRUEПри всех запросах наш товар показывается пользователю, кроме запроса «dark table» при использовании word_similarity. Значение функции равно 0.54545456, а пороговое значение 0.6. Давайте уменьшим пороговое значение до 0.5.
SET pg_trgm.word_similarity_threshold = 0.5;
SELECT 'dark table' <% 'dark wood round table'; -- TRUEЕсли уменьшение порогового значения для similarity не имело смысла, т.к. название товара может быть длиннее, чем указано в примере, то в данном случае в этом есть смысл.
Важно отметить, что в отличии от similarity, функции word_similarity и strict_word_similarity не обладают переместительным свойством, поэтому важно располагать строки в нужном порядке: первым аргументом передаем поисковый запрос, а вторым – строку, с которой сравниваем (например, название товара).
SELECT similarity('table', 'dark table'); -- 0.54545456
SELECT similarity('dark table', 'table'); -- 0.54545456
SELECT word_similarity('table', 'dark table'); -- 1
SELECT word_similarity('dark table', 'table'); -- 0.54545456
SELECT strict_word_similarity('table', 'dark table'); -- 1
SELECT strict_word_similarity('dark table', 'table'); -- 0.54545456В итоге функция similarity не подходит, т.к. нам нужно выдавать даже те результаты, в которых было совпадение лишь небольшой части строки. Например, по «table» должен находиться товар с названием «dark wood round table».
Функции word_similarity и strict_word_similarity похожи, но я решил отдать предпочтение именно последней, т.к. она будет выдавать меньше не релевантных результатов. Например, при запросе «able» товар с названием «dark wood round table» не будет находиться при использовании порогового значения по умолчанию.
Полнотекстовый поиск
Полнотекстовый поиск (Full Text Search) похож на любую популярную поисковую систему, которая выдает список сайтов (документов), которые соответствуют определенному запросу. При этом, в отличии от триграмм, поисковый запрос может быть более сложным. Например, можно найти документы, в которых присутствует несколько слов, даже если они находятся далеко друг от друга, либо можно найти документы, в которых есть точное вхождение запроса.
При использовании триграмм схожесть 2 строк падает, если написать 1 слово, например, не в единственном числе («table»), а в множественном («tables»). Таким образом, можно потерять релевантные результаты, написав одно из слов в поисковом запросе в другой форме. При полнотекстовом поиске данная проблема отсутствует.
Поиск производится следующим образом. В начале парсер разбивает строку (напр, название товара) на набор токенов (минимальных элементов). Токеном может быть число, слово и др. Затем, используя встроенные словари, токены преобразуются в лексемы таким образом, что разные формы одного и того же слова преобразуются в одну и ту же лексему. В итоге из строки получается набор лексем. Затем по этому набору лексем определяется, соответствует ли строка определенному запросу, который тоже представляет из себя набор лексем.
Для хранения набора лексем используется тип tsvector, в который можно преобразовать строку, используя функцию to_tsvector.
SELECT to_tsvector('table'); -- 'tabl':1
SELECT to_tsvector('tables'); -- 'tabl':1У каждой лексемы указывается ее позиция в документе, которая будет в дальнейшем использоваться для сортировки документов по релевантности.
Из списка лексем удаляются так называемые стоп-слова. В них входит все, что повторяется в документах слишком часто и не должно влиять на поиск (например, соединительный союз).
SELECT to_tsvector('spoons and forks'); -- 'fork':3 'spoon':1В данном случае «and» удалился, т.к. это стоп-слово, а слова «spoons» и «forks» преобразовались к лексемы «spoon» и «fork» и рядом с ними указаны позиции в документе («spoon» находится на первом месте, а «fork» на третьем).
Кроме позиции лексемы, можно также хранить ее приоритет. Всего существует 4 приоритета: A (самый высокий), B, C и D (самый низкий; не указывается рядом с лексемой). Например, если необходимо искать по статьям, то можно назначить названию статьи приоритет A, содержанию статьи – B, а имени автора – D.
SELECT setweight(to_tsvector('Comparision of indexes'), 'A') || setweight(to_tsvector('The content of the article'), 'B') || setweight(to_tsvector('Ilya Ordin'), 'D');
/* 'articl':8B 'comparis':1A 'content':5B 'ilya':9 'index':3A 'ordin':10 */Для поисковых запросов используется тип tsquery. Для создания таких запросов существует несколько функций: to_tsquery, plainto_tsquery, phraseto_tsquery и websearch_to_tsquery.
Используя функцию to_tsquery можно писать запросы, используя логические операторы. При этом слова будут преобразованы в лексемы. Оператор @@ используется для определения соответствия запроса документу (напр, названию товара).
SELECT to_tsquery('tables'); -- 'tabl'
SELECT to_tsvector('dark wood round table') @@ to_tsquery('tables'); -- TRUE
SELECT to_tsquery('tables & dark'); -- 'tabl' & 'dark'
SELECT to_tsvector('dark wood round table') @@ to_tsquery('tables & dark'); -- TRUE
SELECT to_tsquery('tables | armchairs'); -- 'tabl' | 'armchair'
SELECT to_tsvector('dark wood round table') @@ to_tsquery('tables | armchairs'); -- TRUE
SELECT to_tsquery('tables & ! dark'); -- 'tabl' & !'dark'
SELECT to_tsvector('dark wood round table') @@ to_tsquery('tables & ! dark'); -- FALSE
SELECT to_tsquery('round <-> tables'); -- 'round' <-> 'tabl'
SELECT to_tsvector('dark wood round table') @@ to_tsquery('round <-> tables'); -- TRUE
SELECT to_tsvector('dark wood round table') @@ to_tsquery('dark <-> tables'); -- FALSE
SELECT to_tsvector('dark wood round table') @@ to_tsquery('dark <3> tables'); -- TRUE
SELECT to_tsvector('dark wood round table') @@ to_tsquery('round <1> tables'); -- TRUE
SELECT to_tsvector('dark wood round table') @@ to_tsquery('round <3> tables'); -- FALSE
SELECT to_tsvector('dark wood round table') @@ to_tsquery('dark <-> wood <-> round <-> table'); -- TRUEОператор <-> означает, что слова следуют друг за другом. Можно также указать длину между словами. Например, <3> означает, что между словами должно находится еще 2 слова. Если количество слов будет меньше, то документ не будет соответствовать запросу. Как мы видим запрос round <3> tables не соответствует документу «dark wood round table», а dark <3> tables соответствует. <1> аналогичен <->.
Функцию to_tsquery удобно использовать, когда нужно составить запрос вручную, т.к. между словами обязательно должны стоять логические операторы, иначе будет ошибка.
SELECT to_tsquery('dark tables'); -- ERROR: syntax error in tsquery: "dark tables"Запросы от пользователей нужно передавать в другие функции, которые сейчас разберем.
plainto_tsquery преобразует все слова в набор лексем и ставит между ними оператор &. Функция phraseto_tsquery делает то же самое, но между лексемами ставит оператор <->.
SELECT plainto_tsquery('dark wood tables'); -- 'dark' & 'wood' & 'tabl'
SELECT phraseto_tsquery('dark wood tables'); -- 'dark' <-> 'wood' <-> 'tabl'Соответственно, если необходимо показывать пользователю, например, товары, в названии которых содержится одно из слов, то нужно использовать plainto_tsquery, а если производится поиск по фразе (слова должны идти друг за другом), то phraseto_tsquery.
Функция websearch_to_tsquery позволяет строить запросы более гибко:
SELECT websearch_to_tsquery('dark wood tables'); -- 'dark' & 'wood' & 'tabl'
SELECT websearch_to_tsquery('"dark wood tables"'); -- 'dark' <-> 'wood' <-> 'tabl'
SELECT websearch_to_tsquery('tables or armchairs'); -- 'tabl' | 'armchair'
SELECT websearch_to_tsquery('tables -dark'); -- 'tabl' & !'dark'Таким образом поиск по документам будет реализован по аналогии с поиском у поисковых систем.
Теперь давайте попробуем найти наш товар с названием «dark wood round table» по разным префиксам.
SELECT to_tsvector('dark wood round table'); -- 'dark':1 'round':3 'tabl':4 'wood':2
SELECT to_tsvector('dark wood round table') @@ to_tsquery('tables'); -- TRUE
SELECT to_tsvector('dark wood round table') @@ to_tsquery('table'); -- TRUE
SELECT to_tsvector('dark wood round table') @@ to_tsquery('tabl'); -- TRUE
SELECT to_tsvector('dark wood round table') @@ to_tsquery('tab'); -- FALSEСлово «table» преобразуется в лексему «tabl», а значит, чтобы найти товар с названием «dark wood round table», пользователю потребуется в поиске ввести как минимум «tabl». Этот товар нельзя будет найти по запросу «tab».
Давайте рассмотрим еще один пример. Добавим в наш каталог товар с названием «black leather armchair» и попытаемся найти его по запросу «armcha».
SELECT to_tsvector('black leather armchair'); -- 'armchair':3 'black':1 'leather':2
SELECT to_tsvector('black leather armchair') @@ to_tsquery('armcha'); -- FALSEПо такому запросу пользователь, к сожалению, не сможет найти товар, однако, в запросе можно указать, что мы хотим найти все лексемы, которые имеют данный префикс:
SELECT to_tsvector('black leather armchair') @@ to_tsquery('armcha:*'); -- TRUEТ.к. поисковый запрос вводит пользователь, то на стороне сервера можно сделать предварительное преобразование запроса, добавив к последнему слову :*.
Например, пользовательский запрос «black armcha» можно преобразовать в «black & armcha:*»:
SELECT to_tsquery('black & armcha:*'); -- 'black' & 'armcha':*
SELECT to_tsvector('black leather armchair') @@ to_tsquery('black & armcha:*'); -- TRUEи запрос «black armchairs» в «black & armchairs:*»:
SELECT to_tsquery('black & armchairs:*'); -- 'black' & 'armchair':*
SELECT to_tsvector('black leather armchair') @@ to_tsquery('black & armchairs:*'); -- TRUEВ обоих случаях пользователь увидит в результате поиска товар в названием «black leather armchair», что нам и нужно.
А вот если попытаться допустить опечатку в лексеме, то мы не сможем найти данный товар:
SELECT to_tsvector('black leather armchair') @@ to_tsquery('armchair'); -- TRUE
SELECT to_tsvector('black leather armchair') @@ to_tsquery('wrmchair'); -- FALSEЭто является существенным минусом по сравнению с триграммами. Однако и в этом случае есть решение. Можно создать отдельную таблицу со словами, которые используются во всех названиях товаров и предлагать пользователю варианты исправления слов, которые были введены с опечатками. Подробнее здесь.
До текущего момента мы все писали на английском языке. Но что будет, если поисковый запрос и название товара будет на другом языке (например, на русском)?
По умолчанию, для преобразования токенов в лексемы используется язык, указанный в default_text_search_config:
SHOW default_text_search_config; -- pg_catalog.englishЕсли мы попытаемся преобразовать в tsvector русские слова, то лексемы будут равны первоначальным токенам, т.к. в английских словарях эти слова не будут найдены.
SELECT to_tsvector('черные кресла'); -- 'кресла':2 'черные':1В любую вышеупомяную функцию (to_tsvector, to_tsquery, plainto_tsquery и др) можно в качестве первого аргумента передать название языка, который необходимо использовать (название схемы pg_catalog можно опустить):
SELECT to_tsvector('pg_catalog.russian', 'черные кресла'); -- 'кресл':2 'черн':1
SELECT to_tsvector('russian', 'черные кресла'); -- 'кресл':2 'черн':1Но что, если у нас в одной таблице хранятся документы на разных языках? Например, русскоязычные пользователи переписываются в чате на русском языке, а англоговорящие на английском. Существует 2 варианта решения данной проблемы.
Вариант 1. Создать в таблице дополнительную колонку, в которой будет храниться язык текущего сообщения.
CREATE TABLE messages (id int, body varchar, lng regconfig);
INSERT INTO messages VALUES (1, 'Good news everyone!', 'english'), (2, 'Это просто замечательно!', 'russian');
SELECT to_tsvector(lng, body) FROM messages;
/* 'everyon':3 'good':1 'news':2 */
/* 'замечательн':3 'прост':2 'эт':1 */Если язык сообщения неизвестен, то можно написать функцию, которая будет определять его, перебирая to_tsvector с разными языками. Тот язык, для которого длина лексем будет минимальной, скорее всего на этом языке и написано сообщение.
SELECT to_tsvector('english', 'черные кресла'); -- 'кресла':2 'черные':1
SELECT to_tsvector('russian', 'черные кресла'); -- 'кресл':2 'черн':1Вариант 2. Можно создать свой словарь, который будет состоять из словарей разных языков. Подробная инструкция описана тут.
В этом случае, в отличии от первого варианта, в одном сообщении могут быть слова сразу на нескольких языках. Например, если англоязычный пользователь что-то написал и дополнительно вставил в сообщение цитату на русском.
Давайте поговорим немного про ранжирование результатов поиска. Скорее всего пользователю необходимо показать первые N результатов, которые наиболее релевантны его запросу. Для этого необходимо воспользоваться функцией для вычисления релевантности. PostgreSQL предоставляет 2 функции: ts_rank и ts_rank_cd. Чем выше значение, тем результат поиска более релевантен.
Значение ts_rank зависит от частоты лексем. Чем чаще встречается лексема в документе, тем менее она ценна, тем меньше значение.
Функция ts_rank_cd схожа с ts_rank, только учитывается близость лексем друг к другу. Для этого используются позиции у лексем, которые хранятся в tsvector. Кстати, судя по этой презентации (22-23 слайды) функция ts_rank_cd плохо работает с оператором |.
Теперь давайте вернемся к индексам.
Какие индексы будем сравнивать
Для ускорения поиска, используя триграммы, можно создать либо GiST, либо GIN индекс. Для ускорения полнотекстового поиска, можно использовать 3 вида индексов: GiST, GIN или RUM. Предлагаю сравнить все и выяснить, какой из них работает быстрее.
GiST индекс для триграмм
Для начала давайте создадим следующую таблицу:
CREATE TABLE messages (id int, body text);GiST индекс для триграмм создается следующей командой:
CREATE INDEX messages_body_idx ON messages USING gist (body gist_trgm_ops);Давайте поговорим о том, как работает GiST индекс. Предположим, что у нас в таблице всего 3 коротких сообщения: «table», «able» и «tab». Так будут выглядеть для них триграммы:
SELECT show_trgm('table'); -- {" t"," ta",abl,ble,"le ",tab}
SELECT show_trgm('able'); -- {" a"," ab",abl,ble,"le "}
SELECT show_trgm('tab'); -- {" t"," ta","ab ",tab}Для каждой триграммы создается своя сигнатура (битовая строка), в которой все биты нулевые, кроме одного. Например, это может выглядет следующим образом:
- « t» – 00100000 (3-й бит)
- « ta» – 00000100 (6-й бит)
- «abl» – 10000000 (1й бит)
- «ble» – 00010000 (4-й бит)
- «le » – 00000001 (8-й бит)
- «tab» – 00001000 (5-й бит)
- « a» – 10000000 (1-й бит)
- « ab» – 00100000 (3-й бит)
- «ab » – 01000000 (2-й бит)
Номер бита определяется хеш-функцией, на вход которой подается триграмма, а на выходе номер бита. Длина битовой строки (сигнатуры) в нашем случае равна 8 битам или 1 байту. По умолчанию, длина сигнатуры равна 12 байтам, но ее можно поменять, указав параметр siglen следующим образом:
CREATE INDEX messages_body_idx ON messages USING gist (body gist_trgm_ops(siglen=32));Длина сигнатуры может быть от 1 до 2024 байтов.
Вернемся к нашему примеру. Думаю, вы уже заметили, что у некоторых триграмм сигнатура одинаковая (например, у «abl» и « a»), т.к. для них хеш-функция выдала один и тот же номер бита. Это называется коллизией. Скоро вы увидите, как это повлияет на поиск, но сейчас важно понимать, что чем длиннее сигнатура, тем меньше шанс того, что для 2 разных триграмм хеш-функция вернет один и тот же номер бита и сигнатура у них будет одинаковой. Однако чем длиннее сигнатура, тем индекс занимает больше места на диске.
Затем вычисляются сигнатуры всех документов (строк), используя логическое сложение (ИЛИ) всех триграмм, которые в них используются:
- «table» – 00100000 (« t») | 00000100 (« ta») | 10000000 («abl») | 00010000 («ble») | 00000001 («le ») | 00001000 («tab») = **10111101**
- «able» – 10000000 (« a») | 00100000 (« ab») | 10000000 («abl») | 00010000 («ble») | 00000001 («le ») = **10110001**
- «tab» – 00100000 (« t») | 00000100 (« ta») | 01000000 («ab ») | 00001000 («tab») = **01101100**
GiST индекс строит сигнатурное дерево, в листьях которого находятся сигнатуры документов (в нашем случае 10111101, 10110001 и 01101100). Корневой и каждый внутренний узел дерева содержит ссылки либо на другие внутренние узлы, либо на листья. При этом в них хранится сигнатура всех документов, на которые они ссылаются. Например, если в нашем случае существует только корневой узел, то в он хранит в себе сигнатуру 11111101 (10111101 | 10110001 | 01101100).
При поиске запрос разбивается на триграммы и вычисляется его сигнатура. Затем, начиная с корня дерева идет сравнение узла с сигнатурой запроса. Если все положительные биты из сигнатуры запроса совпадают с положительными битами сигнатуры узла, то входим в этот узел и так доходим до листьев, где хранятся ссылки на строки таблицы.
Вспомним, что мы можем задавать длину сигнатуры. Чем сигнатура короче, тем индекс занимает меньше места на диске, но в этом случае сигнатуры разных триграмм могут совпадать. В итоге, при поиске мы лишний раз будем заходить в листья, которые на самом деле не соответствуют запросу, что будет приводить к замедлению поиска. Ложный результат нам выдаваться не будет, т.к. GiST индекс будет перепроверять результаты с реальными значениями (если они занимают немного места, то они будут храниться внутри узла и скорость поиска не сильно пострадает, иначе потребуется обращение к таблице, что еще сильнее замедлит поиск).
Итак, возникает вопрос: какую же длину сигнатуры выбрать? Чтобы посмотреть, на сколько влияет длина сигнатуры на скорость поиска и место на диске, предлагаю сравнить 3 длины сигнатуры: 12 байтов (значение по умолчанию), 120 байтов и 1200 байтов. Само сравнение ниже.
GiST индекс производит поиск в глубину, а это значит, что он может сразу выдавать первые найденные результаты. Это нам и нужно, чтобы реализовать пагинацию, используя LIMIT.
Подробнее про устройство GiST индекса можно почитать здесь.
GIN индекс для триграмм
GIN индекс для триграмм создается следующей командой:
CREATE INDEX messages_body_idx ON messages USING gin (body gin_trgm_ops);GIN индекс для хранения триграмм использует B-дерево, в листьях которого содержаться триграммы и ссылки на строки таблицы, в которых эти триграммы встречаются. Если ссылок немного в одном листовом узле, то они хранятся в виде списка (posting list) вместе с самими значениями, иначе отдельно в виде B-дерева. Подробнее можно почитать про GIN индекс и посмотреть как он выглядит здесь.
Поиск по GIN индексу обычно производится быстро, т.к. в отличии от GiST лишние обходы не производятся. Однако, он не умеет производить поиск в глубину, а значит, что не может сразу вернуть нам первые найденные элементы. При использовании LIMIT в начале будут получены все результаты, а затем будет выполнена выборка первых элементов. Таким образом, если элементов много, то поиск будет медленным.
Можно ограничить выборку GIN индекса, задав параметр gin_fuzzy_search_limit, но это подойдет только в том случае, если не производится сортировка результата по релевантности. Иначе наиболее релевантные результаты скорее всего будут отброшены и не будут показаны пользователю.
GIN индекс занимает обычно немного места, т.к. одна и та же лексема хранится только 1 раз. Помимо этого за счет того, что ссылки на строки таблицы хранятся упорядочено, каждая последующая ссылка хранится не как полноценная ссылка, а как разность текущей ссылки с предыдущей.
Итак, по сравнению с GiST, GIN индекс производит поиск быстрее и занимает меньше места, но он не умеет возвращать первые найденные результаты сразу. Посмотрим, как это повлияет на скорость его работы.
Поддержка LIKE и ILIKE при использовании триграмм
Помимо разных функций similarity, которые мы разобрали ранее, индексы GiST и GIN для триграмм также поддерживают операторы LIKE и ILIKE. Используя эти операторы, поиск производится быстрее, т.к. все что нужно – это найти точное совпадение нужной подстроки, вместо того, чтобы определять на сколько одна строка похожа на другую.
Индекс B-tree тоже умеет использовать оператор LIKE, но только в том случае, если поиск производится по префиксу. Например, ILIKE 'abcd%' (строка начинается с «abcd»). В отличии от B-tree, индексы GiST и GIN, используя триграммы, могут производить поиск по любой части строки. Например, ILIKE '%abcd%' (строка содержит «abcd»). На практике это используется гораздо чаще. Индексы GiST и GIN не поддерживают сравнение на равенство, поэтому, если это необходимо, потребуется создать дополнительный B-tree индекс.
Ограничение по количеству символов при использовании триграмм
При использовании триграмм с операторами LIKE и ILIKE, в запросе необходимо указывать как минимум 3 символа. В ином случае, индекс не будет использоваться. Цитата из официальной документации: «For both LIKE and regular-expression searches, keep in mind that a pattern with no extractable trigrams will degenerate to a full-index scan».
Попробуем произвести поиск, указав в ILIKE 3 символа:
EXPLAIN ANALYZE SELECT * FROM messages WHERE body ILIKE '%heh%';Bitmap Heap Scan on messages (cost=844.55..9333.91 rows=90909 width=31) (actual time=8.578..488.423 rows=52910 loops=1)
Recheck Cond: (body ~~* '%heh%'::text)
Heap Blocks: exact=7352
-> Bitmap Index Scan on messages_body_idx (cost=0.00..821.82 rows=90909 width=0) (actual time=7.436..7.442 rows=52910 loops=1
)
Index Cond: (body ~~* '%heh%'::text)
Planning Time: 0.417 ms
Execution Time: 842.995 msПланировщик PostgreSQL воспользовался индексом. Теперь попробуем указать 2 символа:
EXPLAIN ANALYZE SELECT * FROM messages WHERE body ILIKE '%he%';Seq Scan on messages (cost=0.00..19853.00 rows=494949 width=31) (actual time=0.020..4550.681 rows=472940 loops=1)
Filter: (body ~~* '%he%'::text)
Rows Removed by Filter: 527060
Planning Time: 0.415 ms
Execution Time: 7684.939 msПланировщик выбрал последовательное сканирование, вместо использования индекса, от чего время выполнения запроса выросло почти в 10 раз.
При использовании операторов similarity такого ограничения нет:
EXPLAIN ANALYZE SELECT * FROM messages WHERE body %>> 'h';Bitmap Heap Scan on messages (cost=88.78..455.04 rows=100 width=31) (actual time=1546.646..1546.664 rows=0 loops=1)
Recheck Cond: (body %>> 'h'::text)
Rows Removed by Index Recheck: 356196
Heap Blocks: exact=7353
-> Bitmap Index Scan on messages_body_idx (cost=0.00..88.75 rows=100 width=0) (actual time=32.912..32.918 rows=356196 loops=1
)
Index Cond: (body %>> 'h'::text)
Planning Time: 0.890 ms
Execution Time: 1546.862 msПланировщик воспользовался индексом.
Для операторов LIKE и ILIKE необходимо указывать минимум 3 символа, чтобы получилась хотя бы 1 триграмма, но при использовании функций similarity достаточно 1 символа, т.к. даже из него формируется 2 триграммы, которые будут участвовать в поиске.
SELECT show_trgm('h'); -- {" h"," h "}Если вы используете LIKE или ILIKE, то необходимо указать минимальную длину поисковых запросов, которые вводят пользователи в интерфейсе вашего приложения.
GiST индекс для полнотекстового поиска
Давайте создадим другую таблицу, в которой будем хранить еще и tsvector:
CREATE TABLE messages (id int, body text, body_tsv tsvector GENERATED ALWAYS AS (to_tsvector('english', body)) STORED);Вспомним, что в GiST индексе в листьях помимо сигнатуры документа могут храниться и сами документы, но только в том случае, если они занимают немного места (примерно пол килобайта, если размер страницы 8 КБ). В ином случае, GiST индекс будет хранить ссылки на строки таблицы, где храняться документы. Если мы не будем хранить tsvector в отдельной колонке, то при каждом таком обращении к строкам таблицы будет вычисляться tsvector проверяемой строки, что значительно замедлит работу поиска. Чтобы этого избежать, мы будем хранить tsvector прямо в таблице и вычислять его при добавлении новых документов или изменении уже существующих. Это займет дополнительное место на диске, но ускорит поиск.
Теперь создадим GiST индекс:
CREATE INDEX messages_body_tsv_idx ON messages USING gist (body_tsv);GiST индекс для полнотекстового поиска работает также, как и для триграмм, только вместо триграмм используются лексемы. Отличие в том, что по умолчанию используется сигнатура длиной 124 байта (в gist_trgm_ops 12 байт).
Изменить длину сигнатуры можно следующим образом:
CREATE INDEX messages_body_tsv_idx ON messages USING gist (body_tsv tsvector_ops(siglen=512));GIN индекс для полнотекстового поиска
Напомню, что для GiST индекса мы добавляли колонку, в которой хранится tsvector. Для GIN индекса эта колонка может потребоваться, а может и нет. Все зависит от того, какие запросы будут использоваться. Если будут использоваться операторы фразового поиска (<->), в которых важна дистанция между словами (например, чтобы слова шли строго друг за другом), то tsvector тоже нужно хранить в таблице. Если они не будут использоваться (например, все пользовательские запросы будут преобразовываться, используя функцию plainto_tsquery), то tsvector в таблице не нужен. Это связано с тем, что при использовании операторов фразового поиска (<->) нужно знать дистанцию между словами. В GIN индексе эта дистанция не хранится, поэтому каждый раз будет идти обращение к таблице для перепроверки. При сортировке результата по релевантности, используя ts_rank или ts_rank_cd, tsvector также нужно хранить в таблице, т.к. эти функции используют позицию лексем для вычислений.
Если колонка с tsvector не нужна, то индекс будет создаваться следующим образом:
CREATE TABLE messages (id int, body text);
CREATE INDEX messages_body_idx ON messages USING gin (to_tsvector('english', body));Чтобы использовать индекс, созданный таким образом, необходимо в каждом SQL-запросе указывать выражение, которое использовалось при создании индекса. В нашем случае это to_tsvector('english', body).
INSERT INTO messages VALUES (1, 'Hello everyone!');
EXPLAIN ANALYZE SELECT * FROM messages WHERE to_tsvector('english', body) @@ to_tsquery('hello');Bitmap Heap Scan on messages (cost=12.30..24.77 rows=6 width=36) (actual time=0.045..0.088 rows=1 loops=1)
Recheck Cond: (to_tsvector('english'::regconfig, body) @@ to_tsquery('hello'::text))
Heap Blocks: exact=1
-> Bitmap Index Scan on messages_body_idx (cost=0.00..12.30 rows=6 width=0) (actual time=0.021..0.033 rows=1 loops=1)
Index Cond: (to_tsvector('english'::regconfig, body) @@ to_tsquery('hello'::text))
Planning Time: 0.094 ms
Execution Time: 0.215 msПланировщик воспользовался индексом, т.к. указано такое же выражение, какое использовалось и при создании индекса. Давайте теперь попробуем не указывать regconfig с названием языка.
EXPLAIN ANALYZE SELECT * FROM messages WHERE to_tsvector(body) @@ to_tsquery('hello');Seq Scan on messages (cost=10000000000.00..10000000660.88 rows=6 width=36) (actual time=149.690..149.708 rows=1 loops=1)
Filter: (to_tsvector(body) @@ to_tsquery('hello'::text))
Planning Time: 0.082 ms
JIT:
Functions: 2
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 0.865 ms, Inlining 84.521 ms, Optimization 44.615 ms, Emission 20.293 ms, Total 150.295 ms
Execution Time: 184.425 msИндекс не использовался и скорость поиска значительно упала.
Если колонка с tsvector нужна, то индекс создается следующим образом:
CREATE TABLE messages (id int, body text, body_tsv tsvector GENERATED ALWAYS AS (to_tsvector('english', body)) STORED);
CREATE INDEX messages_body_tsv_idx ON messages USING gin (body_tsv);GIN индекс для полнотекстового поиска схож с GIN индексом для триграмм, только вместо триграмм используются лексемы.
RUM индекс для полнотекстового поиска
RUM индекс очень похож на GIN, но он:
- хранит позиции лексем, а значит что поддерживаются операторы фразового поиска (<->).
- умеет производить поиск в глубину, а значит сразу выдавать первые результаты.
- умеет отдавать результаты в порядке их релевантности.
Данный индекс не входит в стандартный PostgreSQL. Чтобы его установить, воспользуйтесь инструкцией, которая доступна в официальном GitHub-репозитории индекса.
RUM индекс создается следующей командой:
CREATE TABLE messages (id int, body text);
CREATE INDEX messages_body_idx ON messages USING rum (to_tsvector('english', body));RUM индекс можно создать с классом операторов rum_tsvector_hash_ops. В этом случае вместо самих лексем будет хранится их хеш. Это может уменьшить размер индекса, но поиск будет работать медленнее и потребуются перепроверки. Также данный класс операторов не поддерживает поиск по префиксу (:*).
CREATE TABLE messages (id int, body text, body_tsv tsvector GENERATED ALWAYS AS (to_tsvector('english', body)) STORED);
CREATE INDEX messages_body_idx ON messages USING rum (body_tsv rum_tsvector_hash_ops);Со слов разработчиков RUM индекса, rum_tsvector_hash_ops стоит использовать только в том случае, если лексемы очень длинные (например, если лексемой является цепочка нуклеотидов). Для естественных языков хеширование лексем не имеет смысла, т.к. размер лексем небольшой, но предлагаю это проверить.
Подробнее про RUM индекс можно почитать здесь и посмотреть тут.
Итак, в итоге будем сравнивать следующие индексы:
- GiST для триграмм с сигнатурами длиной 12, 120 и 1200 байт.
- GIN для триграмм.
- GiST для полнотекстового поиска с сигнатурами длиной 12, 120 и 1200 байт.
- GIN для полнотекстового поиска.
- RUM для полнотекстового поиска, используя rum_tsvector_ops.
- RUM для полнотекстового поиска, используя rum_tsvector_hash_ops.
Про сравнение индексов читайте во второй части статьи.