Привет Хабр! Меня зовут Михаил. Я backend-разработчик в команде Биллинга в Тензоре.

Недавно мне поставили задачу. Звучала она достаточно тривиально:

В таблице существует поле формата JSONB, обеспечить оптимальный поиск по тексту в нём.

Структура поля следующая:

{
   "ru": {
      "Много текста в Русской локали спец символов нет все слова разделены пробелами"
   },
   "en":{
      "There is a lot of text in the English locale there are no special characters all words are separated by spaces"
   },
   .....
}

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

Эта статья — обзор вариантов индексации таких полей и оптимального поиска текста в них, который мы проделали вместе с командой. Так как используем PostgresSQL, все варианты валидны для него.

Композитный индекс по группам

Postgres, как и множество других СУБД, поддерживает композитный индекс.

Композитный индекс — индекс, строящийся по нескольким столбцам таблицы, а не по одному. Этот индекс оптимизирует запросы, которые фильтруют или сортируют данные на основе комбинации этих столбцов, так как он обрабатывает значения в определенной последовательности, обеспечивая быстрый поиск по нескольким критериям одновременно. 

Окей, а как нам использовать этот тип индекса по отношению к нашему полю? Ведь мы не очень явно можем выделить какие-то группы в рамках одного поля. Но, как оказалось, Postgres умеет отлично строить этот тип индекса и для таких не стандартных полей. Достаточно написать триггерную функцию, которая будет парсить наше поле на 4 группы и на основе их и строить индекс. Почему именно 4 группы? Потому что в Postgres на эту фишку заложено всего 2 бита — подробнее про то, как реализована эта фишка, можно почитать тут. Сам способ, как построить такой индекс, включая пример триггер функции, описан здесь.

Если же говорить кратко, то это работает следующим образом:

• Создаётся новое поле формата tsvector и триггер, который, при обновлении\записи поля, разбивает входящий jsonb на 4 под-группы следующим образом:

Поле -> ключ_1 ; Поле -> ключ_2; Поле -> ключ_3; Поле -> ключ_4.

• Далее поверх этого нового поля накатывается GIN индекс.

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

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

Использование расширения JsQuery

Поиск в интернете подсказал, что для работы с JSON полями в Postgers существует удобное расширение JsQuery. Это звучит уже интересно, так как в документации по данному расширению указано, что существует поддержка GIN индекса для поиска, а это как раз то, что нам необходимо.

Помимо разнообразных плюшек, которое даёт это расширение при работе с JSON и JSONB, нас интересуют 2 функции:

• jsonb_path_value_ops - Класс jsonb_path_value_ops представляет элемент в виде пары хеша пути и значения. В итоге получается следующая структура: (hash(элемент_пути_1.элемент_пути_2. ... .элемент_пути_n); значение)

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

• jsonb_value_path_ops - Класс jsonb_value_path_ops представляет элемент в виде пары значения и фильтра блума для пути. (значение; bloom(элемент_пути_1) | bloom(элемент_пути_2) | ... | bloom(элемент_пути_n)). При сравнении записей значение является старшей частью записи, а фильтр Блума для пути — младшей. Это определяет характеристики этого класса операторов. Так как значение находится в старшей части, мы можем выполнять очень эффективно только поиск точного значения. Поиск значений в интервале возможен, но для этого придётся отфильтровать все другие пути, в которых будут найдены подходящие значения. Фильтр Блума по элементам пути позволяет использовать индекс для условий, содержащихся в путях % и *.

На первый взгляд из очевидных минусов использования этого решения только то, что JsQuery отсутствует в стандартных расширениях для Postgres. Это значит, что нам нужно будет согласовывать его включение. Ещё в индексе будет большое количество записей, так как на каждый ключ нашей локали мы будем строить свой собственный путь. Но прежде, чем выдавать вердикт, рассмотрим ещё и плюсы этого решения:

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

Мультииндекс GIN для большого кол-во ключей

Помимо композитного индекса, в PG так же существует и мультииндекс — индекс, который включает в себя два и более столбца в одном объекте. Здесь можно узнать про мультииндекс подробнее.

И как оказалось, PG прекрасно умеет сам строить мультииндекс на поле формата JSONB. Более того, это решение подходит для ситуаций, когда у нас есть большое количество ключей в нашем объекте. А у нас как раз может быть достаточно много локалей. Также мы можем забить на точное указание языка и индексировать просто всю строку целиком.

Как это работает: cоздаём GIN индекс с использованием jsonb_to_tsvector и конфигурацией только на текстовые значения без уточнения языка. Т.е что то типа такого: GIN(jsonb_to_tsvector('simple', data, '["string"]'))

Тут:

• simple -- Используется для общего поиска без языковой морфологии. Такое решение подходит для мультиязычных данных.

• string -- Указатель на то, что индексируем только строковые значения без цифр и спец. символов.

Окей, как это работает — понятно, но подходит ли нам в нашей ситуации решение? Или пойдём искать дальше?

Как и выше, распишем очевидные плюсы и минусы в виде таблицы и сделаем выводы:

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

MATERIALIZED VIEW

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

Решение нам показалось достаточно изящным и вот почему:

1. Предвычисляем tsvector и объединяем для каждого поля всё в единый tsvector вне зависимости от локализации. Это позволит избежать повторных вычислений при каждом поиске.

2. Вешаем GIN индекс на наш созданный tsvector.

3. При изменении данных обновляем представление.

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

Как обычно, распишем очевидные плюсы и минусы:

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

Бонусный "грязный" вариант

В какой-то момент закралась мысль: а какой самый дешёвый способ решения проблемы? И появился этот вариант. Не очень хочется длинно расписывать его, поэтому осветим кратко.

Меняем формат нашего поля на текстовое и пишем туда весь текст одной строкой без разбития на локали. Далее векторизуем это дело и накатываем GIN индекс.

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

Посмотрим внимательнее на решение со всех сторон:

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

Полезный материал

В ходе поиска решения наткнулся на гайд от МГУ. Он достаточно старый (написан для версии 8.3 вышедший в 2008), но очень подробный и интересный.

Заключение

В этой небольшой статье мы привели варианты решения достаточно распространённой в разработке задачи. С радостью отвечу на ваши вопросы. Пишите, о каких ещё способах знаете? Может, кто-то сталкивался с подобной задачей? Если да, то как её решали? Буду рад обратно связи и дополнениям!