Функциональность поиска на Val Town не очень впечатляет. Сейчас в её основе лежит механизм ILIKE Postgres, работающий на основе алгоритма поиска подстроки: если искомое выражение в коде есть, оно выводится в результатах. Этот процесс не включает никакого ранжирования, и очень слабо поддерживает запросы из нескольких слов. Более эффективный поиск является одной из самых желанных для нас возможностей.

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

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

▍ Поиск по коду и естественно-языковой поиск

Типичная проблема готовых поисковых решений в том, что они предназначены для работы с английским и другими естественными языками. К примеру, вот несколько алгоритмов, которые действуют по умолчанию при стандартной настройке поиска по всему тексту (FTS, Full Text Search):

• Удаление стоп-слов: из текста перед его индексацией удаляются слова вроде «the» и «it», поскольку их слишком высокая частота создаёт больше проблем, нежели они несут пользы.
• Стемминг: эта функция, по сути, отсекает от слова окончание, приводя его к основе (при этом основа не обязательно будет совпадать с корнем слова, – прим. пер.). Например, слово «running» в этом случае превратится в «run», и при выполнении поиска «runs» вы также получите результаты из документа, содержащего слова «running».
• Лемматизация*: некоторые поисковые индексы достаточно наворочены, чтобы соотносить наиболее распространённые слова с их синонимами. Благодаря этому, вы можете выполнить поиск «excellent» и получить результаты из документов, содержащих «great».

*Прим. пер.: по факту лемматизация подразумевает преобразование слова в его изначальную, словарную форму.

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

select * from to_tsvector('english', 'I am writing this example sentence');
--- 'exampl':5 'sentenc':6 'write':3

Проблема со всеми этими правилами в том, что они вносят в код хаос. К примеру, the в TypeScript не является стоп-словом. Это допустимое имя переменной, которое вы вполне можете искать. Границы слов тоже в этом случае другие, и подвергать стеммингу названия функций смысла нет:

select * from to_tsvector('english',
  'function stringifyNumber(a: number): string { return a.toString() }');
-- 'a.tostring':7 'function':1 'number':4 'return':6 'string':5 'stringifynumb':2

Это довольно плохой индекс: в нём есть слова, которые должны быть стоп-словами, например, function, и он не разделяет a.to.String() на два токена, потому что . по умолчанию не является границей слова.

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

В Postgres есть расширение Full Text Search, которое поддерживается нашим провайдером хостинга, компанией Render. Я уже использовал FTS в других проектах, и при определённых масштабах этот механизм прекрасно работал. Можно попробовать задействовать Postgres для всего. Собственно, до сих пор мы так и делали – вытрясали из неё, всё что можно. Это фантастическая технология, которая имеет отличную документацию и полноценно поддерживается нашим провайдером.

Если мы можем использовать Postgres для чего-либо, то так и делаем: для нашей небольшой команды очень важно сохранять инфраструктуру максимально простой.

Тем не менее в предыдущих проектах, где я использовал FTS, возникали проблемы с производительностью и масштабированием. К примеру, Observable в итоге перешёл на Elasticsearch. У нас есть куча val (фрагменты TS- и JS-кода, написанные и выполняемые в браузере на серверах Val Town, — прим. пер.), и мы испытываем пределы возможностей кластера Postgres, состоящего из одного узла. Сложно найти упоминания успешной реализации поиска по коду с помощью FTS, хотя, возможно, об этом просто не пишут. Я же не хотел применять этот подход в качестве изначального и решил оставить его про запас.

▍ pg_trgrm

Решение, которое мы предварительно запустили (soft-launch) в виде алгоритма поиска v2, основано на модуле pg_trgrm, реализующем в Postgres поиск по триграммам. Для поиска по коду такой подход должен вполне сгодиться. Расс Кокс в своей известной работе «Regular Expression Matching with a Trigram Index» от 2012 года рассказывает историю о том, как разработчики Google Code Search использовали триграммные индексы и специальную реализацию регулярных выражений. В новой системе поиска GitHub, помимо всяческих технологий, которым лично я завидую, также используется триграммный индекс. И у Sourcegraph тоже есть инструмент поиска на основе триграмм, который они позаимствовали у Google.

Мы же в использовании pg_trgrm преимущественно опирались на серию статей Стивена Гутеканста, посвящённую локальной индексации репозиториев в Postgres. Мы создали индекс GIN, применив gin_trgrm_ops к столбцу с текстом для поиска.

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

▍ Вселенная вариантов

Существуют специальные, ориентированные на код инструменты, но большинство из них являются закрытыми: поиск на GitHub работает прекрасно, но над ним явно работает отдельная команда с постоянным финансированием.

• Сделанный Sourcegraph форк Zoekt довольно неплох, но при этом является пугающе нишевым и наложит на инфраструктуру лишние издержки по обслуживанию.
• Окончательным и неизбежным решением нашей задачи может стать Elasticsearch. В нём нет специальной обработки кода, но зато есть широкие возможности кастомизации. Нас не вдохновляет тот факт, что придётся изучать настройку памяти в Java и вносить в приложение первое постоянное дисковое хранилище, а также дополнительный источник истины для наших данных. Возможно, мы сможем использовать Elasticsearch Cloud, чтобы избежать лишних хлопот с обслуживанием.
• Meilisearch, будучи построенным на ✨Rust✨ со всеми его достоинствами, выглядит многообещающей альтернативой ES. Но акцент в нём сделан на увеличении скорости обработки, а не масштабируемости, и мы сомневаемся, что для инфраструктуры его использование создаст меньше издержек.
• ParadeDB обещает все возможности Elasticsearch, но «только Postgres», что очень заманчиво. Жаль, но пока Render их расширение не поддерживает.

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

Telegram-канал со скидками, розыгрышами призов и новостями IT ?