Поиск по триграммам

Этим материалом я открываю серию статей по методам полнотекстовых поисков. Будем разбирать:

  1. Elasticsearch — один из самых востребованных, судя по вакансиям, инструмент. Многое умеет, быстро ищет, поставляется со своим личным стеком утилит. Будем разбираться в следующей статье.
  2. Sphinx. Да-да, он вроде как уже мёртв, а вроде много где используется, хорошо работает, имеет адаптеры под разные языки и фреймворки. Так что — имеет право быть.
  3. Поиск по триграммам — интересный поиск, наименее затратный в плане реализации, и весьма эффективный. Работает благодаря расширению, подключаемому в Postgres. Именно он и будет темой сегодняшней статьи.

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

Триграмма — последовательность из трёх символов (при этом postgres добавляет по 2 пробела в начало и в конец строки).

Например, в слове «symfony» триграммами будут: [ s, sy, sym, ymf, mfo, …, ny, y]. Как описывает документация Postgres’а — логика работы этого поиска весьма простая. Мы можем измерить схожесть двух слов по количеству совпавших в них триграмм. Так же указывается параметр, задающий строгость совпадения (напр. 50%, 90%). Этот вид поиска интересен прежде всего тем, что позволяет находить слова по запросу с опечатками.

Теперь установим расширения и поиграемся с этим поиском в psql.

Ставим дополнительные пакеты для postgres, из которых можно подцепить расширение для работы с триграммами:

sudo apt install postgresql-contrib
service postgresql restart

Устанавливаем расширение:

psql -U postgres
CREATE EXTENSION pg_tgrm;

Теперь посмотрим, какие методы предоставляет это расширение (подробное описание методов можно найти, например, тут)

Проверим, работает ли расширение:

SELECT show_trgm('symfony');

Теперь сравним два слова:

SELECT word_similarity('junsenior', 'junseniors pg_tgrm');

Эта функция выводит коэффициент соответствия первого слова и одного из слов второй строки. В данном случае — 0.9 — помешала буква ‘s’ на конце.

Расширение, помимо прочего, предоставляет индексы для очень быстрого поиска по триграммам. Пример из доки:

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

Создали таблицу test_tgrm с одним столбцом t, типа text. Ниже создали индекс с названием tgrm_idx для этой таблицы. USING GIST — это указание использовать класс GIST, предоставляющий индексы для триграммного поиска. (t gist_trgm_ops) — t — столбец. Такая конструкция указывает, что для этого столбца создаётся индекс.

Теперь запишем пару строк в таблицу:

INSERT INTO test_trgm VALUES ('test');
INSERT INTO test_trgm VALUES ('aaa');
INSERT INTO test_trgm VALUES ('symfony');

И выполним поиск с учётом индекса:

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

similarity — выводит соответствие между двумя строками 1 в 1 % в WHERE — специальный оператор, предоставляемый расширением pg_trgm, который вернёт true в случае, если коэффициент соответствия будет выше заданного порога (хранится в pg_trgm.similarity_threshold)

На моём опыте на 40к-50к строк (что конечно не много, но уже что-то) такой поиск с индексами работал за доли секунд.

Интеграция с Symfony

Ставим свежую версию Symfony и набор компонентов, которые нам будут нужны:

symfony new tgrm_test
composer require symfony/orm-pack orm
composer require symfony/maker-bundle --dev

Теперь создаём файл src/Doctrine/Function/TrigramSimilarity.php:

<?php

namespace App\\Doctrine\\Functions;

use Doctrine\\ORM\\Query\\{
    AST\\Functions\\FunctionNode,
    Lexer,
    Parser,
    QueryException,
    SqlWalker
};

class TrigramSimilarity extends FunctionNode
{
    /** @var FunctionNode */
    private $compareFrom;

    /** @var FunctionNode */
    private $compareTo;

    /**
     * @inheritDoc
     */
    public function getSql(SqlWalker $sqlWalker)
    {
        return 'similarity(' .
            $this->compareFrom->dispatch($sqlWalker) . ', ' .
            $this->compareTo->dispatch($sqlWalker) .
            ')';
    }

    /**
     * @inheritDoc
     *
     * @throws QueryException
     */
    public function parse(Parser $parser)
    {
        $parser->match(Lexer::T_IDENTIFIER);
        $parser->match(Lexer::T_OPEN_PARENTHESIS);
        $this->compareFrom = $parser->ArithmeticPrimary();
        $parser->match(Lexer::T_COMMA);
        $this->compareTo = $parser->ArithmeticPrimary();
        $parser->match(Lexer::T_CLOSE_PARENTHESIS);
    }
}

Доктрина имеет прекрасную возможность — позволяет пользователю определять кастомные функции, которые потом можно использовать в билдере запросов. Для этого нужно унаследоваться от класса FunctionNode и реализовать 2 метода — parse и getSql :

  1. getSql() определяет, как будет выглядеть генерируемый SQL-запрос.
  2. Метод parse() — указывает лексическому анализатору из каких лексем будет состоять строка с запросом.

Определение кастомных DQL-функций — очень интересная и объёмная тема, затрагивающая как внутренние механизмы ORM, так и лексический анализ. Сейчас подробно на этом не будем останавливаться, но как-нибудь обязательно разберём.

Теперь зарегистрируем функцию. В config/packages создаём файл doctrine_postgres_function.yaml:

doctrine:
  orm:
    dql:
      numeric_functions:
        trgmSimilarity: App\\Doctrine\\Functions\\TrigramSimilarity

Создадим сущность и репозиторий к ней:

bin/console make:entity 

 Class name of the entity to create or update (e.g. OrangeElephant):
 > Test

 created: src/Entity/Test.php
 created: src/Repository/TestRepository.php
 
 Entity generated! Now let's add some fields!
 You can always add more fields later manually or by re-running this command.

 New property name (press <return> to stop adding fields):
 > name

 Field type (enter ? to see all types) [string]:
 > 

 Field length [255]:
 > 

 Can this field be null in the database (nullable) (yes/no) [no]:
 > 

 updated: src/Entity/Test.php

 Add another property? Enter the property name (or press <return> to stop adding fields):
 > 

           
  Success! 
           

 Next: When you're ready, create a migration with make:migration

Не забываем в .env прописать путь до базы (как создать базу, пользователя и всё это связать — смотри в предыдущих статьях). Важно так же, чтобы расширение pg_trgm было установлено под ту базу данных, которая указана в .env-файле.

Теперь создаём миграцию и накатываем её:

bin/console d:m:diff
bin/console d:m:m

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

<?php

namespace App\\Repository;

use App\\Entity\\Test;
use Doctrine\\Bundle\\DoctrineBundle\\Repository\\ServiceEntityRepository;
use Doctrine\\Common\\Persistence\\ManagerRegistry;
use Doctrine\\ORM\\QueryBuilder;

/**
 * @method Test|null find($id, $lockMode = null, $lockVersion = null)
 * @method Test|null findOneBy(array $criteria, array $orderBy = null)
 * @method Test[]    findAll()
 * @method Test[]    findBy(array $criteria, array $orderBy = null, $limit = null, $offset = null)
 */
class TestRepository extends ServiceEntityRepository
{
    public function __construct(ManagerRegistry $registry)
    {
        parent::__construct($registry, Test::class);
    }

    /**
     * @param string $name
     *
     * @return array
     */
    public function getNames(string $name)
    {
        return $this
            ->createQueryBuilder('entity')
            ->andWhere('trgmSimilarity(entity.name, :name) > 0.3')
            ->setParameter('name', $name)
            ->getQuery()
            ->getArrayResult();
    }
}

Теперь я руками добавил в базу несколько значений:

Создадим контроллер, где проверим работоспособность нашей функции:

<?php

namespace App\\Controller;

use App\\Repository\\TestRepository;
use Symfony\\Bundle\\FrameworkBundle\\Controller\\AbstractController;
use Symfony\\Component\\HttpFoundation\\JsonResponse;
use Symfony\\Component\\HttpFoundation\\Request;
use Symfony\\Component\\Routing\\Annotation\\Route;

class TestController extends AbstractController
{
    /**
     * @Route("/test", name="test", methods="POST")
     *
     * @param Request $request
     *
     * @param TestRepository $repository
     * @return JsonResponse
     */
    public function test(
        Request $request,
        TestRepository $repository
    )
    {
        $post = json_decode($request->getContent(), true);

        $names = [];

        if (isset($post['name'])) {
            $names = $repository->getNames($post['name']);
        }

        return $this->json([
            'names' => $names
        ]);
    }
}

И проверим результат:

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

Ссылочки:

Twitter — https://twitter.com/SeniorJun

Можно поддержать развитие канала — https://www.patreon.com/junsenior

Наш чатик в tlg — https://t.me/junsenior_chat

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *