Ищем имена с опечатками в PostgreSQL

Все началось с того, что мне нужно было разработать поиск пациентов для одной внутренней медицинской системы. Логика работы была в том, что если мы не нашли человека в системе, то его нужно создать (а дубли пациентов плодить нельзя). В связи с этим одной из подзадач стала реализация поиска людей с учетом опечаток в их именах. Ну а поскольку я люблю PostgreSQL (а когда в руках у тебя молоток, то все похоже на гвозди), не сложно угадать, на чем я решил реализовать поиск с опечатками…

Обычно подобная задача решается двумя путями: с помощью нечеткого поиска или фонетическими алгоритмами. Будучи человеком ленивым и свято верящим, что все уже давно украдено придумано до нас, я обратился к документации PostgreSQL. На текущий момент в PostgreSQL есть два модуля, которые могут помочь в поиске с опечатками: pg_trgm и fuzzystrmatch.

1. pg_trgm работает с триграммами, умеет поиск по подстроке и нечеткий поиск. В качестве индексов работает с gist и gin.
   
2. fuzzystrmatch умеет считать расстояние Левенштейна между словами и три фонетических алгоритма: Soundex, Metaphone и Double Metaphone. Подводными камнями является, во-первых, то, что функция Левенштейна в данном модуле не позволяет создать индекс для произвольного поискового запроса. Во-вторых, все фонетические алгоритмы реализованы для латиницы.
   

В связи с этим, решение задачи я начал искать там, где светлее, а именно с модуля pg_trgm.

Триграммы

Для простоты модели рассмотрим таблицу info с идентификатором пациента, его фамилией, именем и отчеством. Так как мы хотим gist/gin индексы, то для начала нужно знать важный, но неприятный момент: один gist/gin индекс — одна колонка таблицы. Его нельзя создать, например, по конкатенации нескольких колонок. Поэтому ниже под катом будут созданы:

• расширение pg_trgm
  
• таблица пациентов, хранящая ФИО в виде jsonb (с проверками существования и заполнения ключей)
  
• иммутабельная функция для построения индекса триграмм, преобразующая ФИО из jsonb в text
  

Скучный SQL код

create extension pg_trgm;

create table info (
  patid integer, fullname jsonb, 
  constraint info_pk primary key (patid),
  constraint fullname_exists check (
    fullname ? 'lname'::text and 
    fullname ? 'fname'::text and 
    fullname ? 'sname'::text
  ),
  constraint fullname_notnull check (
    (fullname ->> 'lname'::text) is not null and 
    (fullname ->> 'fname'::text) is not null
  )
);

create function fullname(in_fullname jsonb)
returns text
language plpgsql
immutable
as $$
begin
  return regexp_replace(
    lower(
      trim(
        coalesce(in_fullname->>'lname', '') || ' ' ||
        coalesce(in_fullname->>'fname', '') || ' ' ||
        coalesce(in_fullname->>'sname', '')
      )
    ),
    'ё',
    'е',
    'g'
   );
exception
  when others then raise exception '%', sqlerrm;
end;
$$;

Вставляем в таблицу около 300 тыс. записей ФИО и приступаем.

Триграммы и GIST

Итак, первым проверяем gist индекс для нечеткого поиска по триграммам.

Еще более скучный SQL код

create index info_gist_idx on info 
using gist (fullname(fullname) gist_trgm_ops);

CREATE INDEX
Time: 15054,102 ms 

explain (analyze, buffers) 
select patid, fullname(fullname) <-> 'смерно дени анато' as dist
from info order by dist limit 10; 
 
  Limit  (cost=0.28..4.35 rows=10 width=8) (actual time=157.378..157.688 rows=10 loops=1)
  Buffers: shared hit=5743
  ->  Index Scan using info_gist_idx on info  (cost=0.28..126822.96 rows=312084 width=8) (actual time=157.371..157.655 rows=10 loops=1)
        Order By: (fullname(fullname) <-> 'смерно дени анато'::text)
        Buffers: shared hit=5743
Planning time: 0.225 ms
Execution time: 158.223 ms
(7 rows)

Индекс создавался 15 сек, размер 45 Мб, поиск по неполному имени с опечатками — 158 мс.

Триграммы и GIN

Далее рассмотрим gin индекс для нечеткого поиска по триграммам.

Думаете, передыдущие спойлеры с SQL были скучными?

create index info_trgm_idx on info 
using gin(fullname(fullname) gin_trgm_ops);

CREATE INDEX
Time: 10163,401 ms

explain (analyze, buffers) 
select patid, similarity(fullname(fullname), 'смерно дени анато' ) as sml
from info where true
and fullname(fullname) % 'смерно дени анато'
order by sml desc limit 10;

 Limit  (cost=1180.22..1180.25 rows=10 width=8) (actual time=133.086..133.117 rows=8 loops=1)
  Buffers: shared hit=5741
  ->  Sort  (cost=1180.22..1181.00 rows=312 width=8) (actual time=133.080..133.090 rows=8 loops=1)
        Sort Key: (similarity(fullname(fullname), 'смерно дени анато'::text)) DESC
        Sort Method: quicksort  Memory: 25kB
        Buffers: shared hit=5741
        ->  Bitmap Heap Scan on info  (cost=26.70..1173.48 rows=312 width=8) (actual time=132.828..133.048 rows=8 loops=1)
              Recheck Cond: (fullname(fullname) % 'смерно дени анато'::text)
              Heap Blocks: exact=7
              Buffers: shared hit=5741
              ->  Bitmap Index Scan on info_gist_idx  (cost=0.00..26.62 rows=312 width=0) (actual time=132.699..132.699 rows=8 loops=1)
                    Index Cond: (fullname(fullname) % 'смерно дени анато'::text)
                    Buffers: shared hit=5734
Planning time: 0.573 ms
Execution time: 133.225 ms
(15 rows)

Создание индекса 10 сек, размер 18 Мб, поиск по неполному имени с опечатками — 133 мс.

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

Триграммы и полнотекстовый поиск

Идея крайне простая — собрать из всех написаний фамилий, имен и отчеств отдельную таблицу-словарь. Вначале входную строку поиска мы разрежем на лексемы, каждую из лексем поищем в таблице-словаре через нечеткий поиск, выберем оттуда все возможные варианты написаний каждой лексемы, положим их в tsquery и сделаем полнотекстовый поиск по tsvector индексу таблицы info. Выгода от этого плана в том, что скорость нечеткого поиска по триграммам зависит от ширины строки и их количества в колонке с текстом. Очевидно, что словарь ФИО будет компактнее, чем оригинальная колонка в таблице info, а значит — поиск будет быстрее. Недостаток у метода лишь один — при добавлении каждого нового пациента придется обновлять словарь, если лексемы из ФИО в нем не встречались. Для проверки нам потребуется собрать из исходников rum индекс для построения tsvector индекса по ФИО в таблице info. Rum является модифицированной версией gin индекса, хранящем в листьях дополнительную информацию. В нашем случае воспользуемся классом операторов rum_tsvector_ops, который хранит позиционную информацию о лексеме в индексе. Поэтому, в отличие от gin, мы сможем использовать index-only запрос tsquery вида

(смернов|смирнов|чернов)<->(денис)<->(анатольевич) 

без обращения к таблице за дополнительной информацией о порядке лексемы в кортеже. Более того, рекомендацией для gin является физическое существование колонки tsvector, так как все найденные указатели на кортежи придется перепроверять в таблице. А если физически колонки tsvector нет (вы его построили функцией для индекса), то для каждого кортежа придется производить дополнительное вычисление tsvector. В общем, rum в данной истории будет куда производительнее.

Эверест в мире скучного SQL

create extension rum;

create index info_rum_idx on info 
using rum (
  to_tsvector('simple'::regconfig, fullname(fullname)) rum_tsvector_ops
);

CREATE INDEX
Time: 7.545s (7 seconds)

create table patname (
  lex text,
  constraint patname_uniq_idx unique (lex)
);

create index patname_fuzzy_idx on patname using gin (lex gin_trgm_ops);
CREATE INDEX
Time: 0.596s

insert into patname (lex)
select word from ts_stat($$
  select to_tsvector('simple', fullname(fullname)) from info
$$);

explain (analyze, buffers)
with fio as (
  select lexeme as lex, positions[1] as pos 
  from unnest(to_tsvector('simple','смернов дин онатол'))
),
query as(
  select to_tsquery('simple', string_agg(q.tq,'&')) as q from (
    select f.pos,  '('||string_agg(p.lex,'|')||')' as tq from fio as f
    join patname as p on p.lex % f.lex
    group by f.pos
  ) as q
)
select to_tsvector('simple'::regconfig, fullname(fullname)) 
  <=> (select q from query) as rank, * from info
where to_tsvector('simple'::regconfig, fullname(fullname)) 
  @@ (select q from query)
order by to_tsvector('simple'::regconfig, fullname(fullname)) 
  <=> (select q from query);

 Sort  (cost=6453.71..6457.61 rows=1560 width=100) (actual time=68.201..68.202 rows=1 loops=1)
  Sort Key: ((to_tsvector('simple'::regconfig, fullname(info.fullname)) <=> $3))
  Sort Method: quicksort  Memory: 25kB
  Buffers: shared hit=536
  CTE fio
    ->  Function Scan on unnest  (cost=0.00..0.10 rows=10 width=34) (actual time=0.023..0.034 rows=3 loops=1)
  CTE query
    ->  Aggregate  (cost=1484.60..1484.86 rows=1 width=32) (actual time=11.829..11.830 rows=1 loops=1)
          Buffers: shared hit=325
          ->  HashAggregate  (cost=1484.30..1484.48 rows=10 width=34) (actual time=11.640..11.644 rows=2 loops=1)
                Group Key: f.pos
                Buffers: shared hit=325
                ->  Nested Loop  (cost=16.58..1480.53 rows=755 width=19) (actual time=2.940..11.442 rows=62 loops=1)
                      Buffers: shared hit=325
                      ->  CTE Scan on fio f  (cost=0.00..0.20 rows=10 width=34) (actual time=0.028..0.053 rows=3 loops=1)
                      ->  Bitmap Heap Scan on patname p  (cost=16.58..147.28 rows=75 width=17) (actual time=1.905..3.717 rows=21 loops=3)
                            Recheck Cond: (lex % f.lex)
                            Rows Removed by Index Recheck: 321
                            Heap Blocks: exact=275
                            Buffers: shared hit=325
                            ->  Bitmap Index Scan on patname_fuzzy_idx  (cost=0.00..16.57 rows=75 width=0) (actual time=1.277..1.277 rows=342 loops=3)
                                  Index Cond: (lex % f.lex)
                                  Buffers: shared hit=50
  InitPlan 3 (returns $3)
    ->  CTE Scan on query  (cost=0.00..0.02 rows=1 width=32) (actual time=0.004..0.006 rows=1 loops=1)
  InitPlan 4 (returns $4)
    ->  CTE Scan on query query_1  (cost=0.00..0.02 rows=1 width=32) (actual time=11.834..11.839 rows=1 loops=1)
          Buffers: shared hit=325
  ->  Bitmap Heap Scan on info  (cost=31.99..4885.97 rows=1560 width=100) (actual time=68.184..68.187 rows=1 loops=1)
        Recheck Cond: (to_tsvector('simple'::regconfig, fullname(fullname)) @@ $4)
        Heap Blocks: exact=1
        Buffers: shared hit=536
        ->  Bitmap Index Scan on info_rum_idx  (cost=0.00..31.60 rows=1560 width=0) (actual time=67.847..67.847 rows=1 loops=1)
              Index Cond: (to_tsvector('simple'::regconfig, fullname(fullname)) @@ $4)
              Buffers: shared hit=517
Planning time: 5.012 ms
Execution time: 68.583 ms
(37 rows)

Итого, индекс полнотекстового поиска создавался 7 секунд (размер 13 Мб), индекс словаря лексем создался за 0,6 секунд (размер 5,8 Мб), поиск — 68 мс. Из недостатков — селективность хуже, чем у предыдущих вариантов.

Фонетические алгоритмы

Перепробовав варианты нечеткого поиска из модуля pg_trmg я решил посмотреть еще раз на fuzzystrmatch. Как проиндексировать функцию Левенштейна я не придумал, а вот фонетические алгоритмы меня крайне заинтересовали. Как говорилось выше, из коробки в PostgreSQL фонетические функции реализованы только для латиницы и заточены под английские имена. Поиск в интернете их русских реализаций привел меня на замечательную статью на Хабре, где описывался рабочий алгоритм Metaphone для русских имен (состоящих из русских букв). Печалило лишь одно — хоть он и был простым, но реализовывать эту логику на plpgsql было как-то совсем грустно, то ли дело на каком-нибудь Python… И тут я вспомнил, что plpython3u — является небезопасным (функции на нем могут получить доступ к файловой системе с правами процесса postgres), но отлично работающим языком в PostgreSQL. И грех бы им не воспользоваться. Поэтому, я написал две иммутабельные функции:

• phoneme на plpython3u, которая превращает лексему в фонему («смирнов» в «смирнаф») по алгоритму из статьи на Хабре
  
• metaphone на plpgsql, которая превращает уже не одну лексему в фонему, а целый текст в набор фонем. По факту, это просто обвязка над функцией phoneme.
  

Metaphone и btree

Далее попробуем создать обычный btree индекс по фукнции metaphone и оценим скорость.

Проходите мимо, здесь нет ничего интересного

create or replace function phoneme (in_lexeme text)
returns text
language plpython3u
immutable
as $$
import re


class Lexeme:
    def __init__(self, body):
        """

        :type body: str
        """
        self.body = body.lower().strip()
        # Правила замены гласных
        self._vowels = {"(?:йо|ио|йе|ие)": "и", "[оыя]": "а", "[еёэ]": "и", "[ю]": "у"}
        # Правила оглушения согласных
        self._consonants = {"б": "п", "з": "с", "д": "т", "в": "ф"}
        # Согласная должна быть оглушена, если за ней следует один из символов списка _deafening_chars
        self._deafening_chars = ["б", "в", "г", "д", "ж", "з", "й"]
        # Удаляемые символы
        self._removable_chars = {"[ъь]": ""}

    def _remove_double_chars(self):
        return Lexeme("".join((char for num, char in enumerate(self.body) if char != self.body[num - 1])))

    def _deafen_consonants(self):
        modified_body = ""
        for num, char in enumerate(self.body):
            if char in self._consonants and (
                num < len(self.body) - 1 and self.body[num + 1] in self._deafening_chars
                or num == len(self.body) - 1
            ):
                modified_body += self._consonants[char]
            else:
                modified_body += char
        return Lexeme(modified_body)

    @staticmethod
    def _regexp_replace(text, char_dict):
        modified_body = text
        for item in char_dict:
            modified_body = re.sub(item, char_dict[item], modified_body)
        return Lexeme(modified_body)

    def _replace_vowels(self):
        return self._regexp_replace(self.body, self._vowels)

    def _remove_chars(self):
        return self._regexp_replace(self.body, self._removable_chars)

    def metaphone(self):
        return self._remove_chars()._replace_vowels()._deafen_consonants()._remove_double_chars().body

return Lexeme(in_lexeme).metaphone()
$$;

create or replace function metaphone (in_phonemes text)
returns text
language plpgsql
immutable
as $$
begin
  return (
    select string_agg(q.lex,' ') from (
      select phoneme(lexeme) as lex from unnest(to_tsvector('simple', in_phonemes))
      order by positions
    ) as q
  );
exception when others then
  raise '%', SQLERRM using errcode = SQLSTATE;
end;
$$;

create index info_metaphone_idx on info (
  metaphone(fullname(fullname)) text_pattern_ops
);

CREATE INDEX
Time: 114.757s (a minute)

explain (analyze, buffers)
select patid, fullname from info 
where metaphone(fullname(fullname)) like 
regexp_replace(metaphone('смернов дин онатол'),'\s','%','g')||'%' 
limit 10;

 Limit  (cost=76.03..1388.96 rows=10 width=96) (actual time=22.452..129.944 rows=3 loops=1)
  Buffers: shared hit=239
  ->  Bitmap Heap Scan on info  (cost=76.03..4146.10 rows=31 width=96) 
         (actual time=22.447..129.927 rows=3 loops=1) 
        Filter: (metaphone(fullname(fullname)) ~~ 'смирнаф%дин%анатал%'::text)
        Rows Removed by Filter: 244
        Heap Blocks: exact=234
        Buffers: shared hit=239
        ->  Bitmap Index Scan on info_metaphone_idx  (cost=0.00..76.02 rows=1560 width=0) 
               (actual time=0.061..0.061 rows=247 loops=1) 
              Index Cond: ((metaphone(fullname(fullname)) ~>=~ 'смирнаф'::text) AND 
                (metaphone(fullname(fullname)) ~<~ 'смирнах'::text))
              Buffers: shared hit=5
Planning time: 1.012 ms
Execution time: 129.977 ms
(12 rows)

Time: 131,802 ms

Индекс создавался 114 сек, размер 22 Мб (кажется, я написал не самую оптимальную функцию на питоне по производительности), запрос 131 мс. Индекс срабатывает лишь по малой части подстроки, а дальше работает фильтр из-за "%". Плохо.

Metaphone и триграммы

Попробуем на базе созданной на plpython3u функции metaphone построить индекс триграмм. Но будем использовать его теперь не для нечеткого поиска, а для поиска подстроки.

Как уменьшить время запроса народными средствами с помощью...

create index info_metaphone_trgm_idx on info 
using gin (metaphone(fullname(fullname)) gin_trgm_ops);

CREATE INDEX
Time: 124.713s (2 minutes)

explain (analyze, buffers)
select patid, fullname from info 
where metaphone(fullname(fullname)) like 
'%'||regexp_replace(metaphone('смернов дин онатол'),'\s','%','g')||'%' limit 10;

 Limit  (cost=92.24..134.98 rows=10 width=96) (actual time=9.562..10.638 rows=3 loops=1)
  Buffers: shared hit=103
  ->  Bitmap Heap Scan on info  (cost=92.24..224.74 rows=31 width=96) (actual time=9.554..10.617 rows=3 loops=1)
        Recheck Cond: (metaphone(fullname(fullname)) ~~ '%смирнаф%дин%анатал%'::text)
        Heap Blocks: exact=2
        Buffers: shared hit=103
        ->  Bitmap Index Scan on info_metaphone_trgm_idx  (cost=0.00..92.23 rows=31 width=0) (actual time=8.354..8.354 rows=3 loops=1)
              Index Cond: (metaphone(fullname(fullname)) ~~ '%смирнаф%дин%анатал%'::text)
              Buffers: shared hit=101
Planning time: 2.029 ms
Execution time: 10.726 ms
(11 rows)

Time: 14,480 ms

Время создания индекса — 124 сек, размер 15 Мб (привет мои кривые руки и plpython3u), поиск — 14 мс.

Итоги

Подведем сводную таблицу различных вариантов поиска с опечатками
UPDATE 1: добавил реализацию Metaphone от movEAX.
UPDATE 2: добавил реализацию Metaphone на plpgsql от Ивана Милованова (telegram — milovanov)

Метафон на plpgsql

create or replace function phoneme (in_lexeme text)
returns text
language plpgsql
immutable
as $$
declare
  res varchar(100) DEFAULT '';
begin
  res := lower(in_lexeme);
  res := regexp_replace(res,'[ъь]','','g');
  res := regexp_replace(res,'(йо|ио|йе|ие)','и','g');
  res := regexp_replace(res,'[оыя]','а','g');
  res := regexp_replace(res,'[еёэ]','и','g');
  res := regexp_replace(res,'ю','у','g');
  res := regexp_replace(res,'б([псткбвгджзфхцчшщ]|$)','п\1','g');
  res := regexp_replace(res,'з([псткбвгджзфхцчшщ]|$)','с\1','g');
  res := regexp_replace(res,'д([псткбвгджзфхцчшщ]|$)','т\1','g');
  res := regexp_replace(res,'в([псткбвгджзфхцчшщ]|$)','ф\1','g');
  res := regexp_replace(res,'г([псткбвгджзфхцчшщ]|$)','к\1','g');  
  res := regexp_replace(res,'дс','ц','g');
  res := regexp_replace(res,'тс','ц','g');
  res := regexp_replace(res,'(.)\1','\1','g');
  return res;
exception
  when others then raise exception '%', sqlerrm;
end;
$$;

Тип поиска	Время создания индекса	Размер индекса	Скорость поиска с опечатками	Замечания
Триграммы gist	15 сек	45 Мб	158 мс
Триграммы gin	10 сек	18 Мб	133 мс
Триграммы и полнотекстовый поиск	7,6 сек	18,8 Мб	68 мс	Хуже селективность, нужно поддерживать словарь лексем
Metaphone btree	114 сек	22 Мб	131 мс	Небезопасный язык plpython3u
Metaphone триграммы	124 сек	15 Мб	14 мс	Небезопасный язык plpython3u
Реализация Metaphone триграмм от movEAX	77,8 сек	16 Мб	14 мс	Небезопасный язык plpython3u
Реализация Ивана Милованова на plpgsql	72,0 сек	16 Мб	14 мс

UPDATE 3: когда в индексе содержится «смирнаф динис анаталивич», то буква «в» в отчестве не оглушается (так как после нее идет гласная). Если искать по подстроке metaphone('анатольев'), то буква «в» оказывается не за гласной, а на конце и оглушится. Чтобы обойти эту проблему ниже написана функция mquery и поиск осуществляется по выражению

select metaphone('смирнов денис анатольевич') similar to mquery('Смернов дини онатольев');

Функция mqery

create or replace function mquery(in_fullname text)
returns text
language plpgsql
immutable
as $$
declare
  res text;
begin
  res := metaphone(in_fullname);
  res := regexp_replace(res, '(б|п)', '(б|п)', 'g');
  res := regexp_replace(res, '(з|с)', '(з|с)', 'g');
  res := regexp_replace(res, '(д|т)', '(д|т)', 'g');
  res := regexp_replace(res, '(в|ф)', '(в|ф)', 'g');
  res := regexp_replace(res, '(г|к)', '(г|к)', 'g');
  res := regexp_replace(res, '\s', '%', 'g');
  return '%'||res||'%';
exception
  when others then raise exception '%', sqlerrm;
end;
$$;

Так как в моем случае система будет ориентирована на чтение, а не на запись (максимум добавление пары пациентов в минуту), то мой вариант — Metaphone с триграммами. Если у кого-то есть идеи, как можно оптимизировать функцию на Python по скорости, то отпишитесь в комментариях, я добавлю данные в тесты.