Все началось с того, что мне нужно было разработать поиск пациентов для одной внутренней медицинской системы. Логика работы была в том, что если мы не нашли человека в системе, то его нужно создать (а дубли пациентов плодить нельзя). В связи с этим одной из подзадач стала реализация поиска людей с учетом опечаток в их именах. Ну а поскольку я люблю PostgreSQL (а когда в руках у тебя молоток, то все похоже на гвозди), не сложно угадать, на чем я решил реализовать поиск с опечатками…
Обычно подобная задача решается двумя путями: с помощью нечеткого поиска или фонетическими алгоритмами. Будучи человеком ленивым и свято верящим, что все уже давно украдено придумано до нас, я обратился к документации PostgreSQL. На текущий момент в PostgreSQL есть два модуля, которые могут помочь в поиске с опечатками: pg_trgm и fuzzystrmatch.
- pg_trgm работает с триграммами, умеет поиск по подстроке и нечеткий поиск. В качестве индексов работает с gist и gin.
- fuzzystrmatch умеет считать расстояние Левенштейна между словами и три фонетических алгоритма: Soundex, Metaphone и Double Metaphone. Подводными камнями является, во-первых, то, что функция Левенштейна в данном модуле не позволяет создать индекс для произвольного поискового запроса. Во-вторых, все фонетические алгоритмы реализованы для латиницы.
В связи с этим, решение задачи я начал искать там, где светлее, а именно с модуля pg_trgm.
Триграммы
Для простоты модели рассмотрим таблицу info с идентификатором пациента, его фамилией, именем и отчеством. Так как мы хотим gist/gin индексы, то для начала нужно знать важный, но неприятный момент: один gist/gin индекс — одна колонка таблицы. Его нельзя создать, например, по конкатенации нескольких колонок. Поэтому ниже под катом будут созданы:
- расширение pg_trgm
- таблица пациентов, хранящая ФИО в виде jsonb (с проверками существования и заполнения ключей)
- иммутабельная функция для построения индекса триграмм, преобразующая ФИО из jsonb в text
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 индекс для нечеткого поиска по триграммам.
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 индекс для нечеткого поиска по триграммам.
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 в данной истории будет куда производительнее.
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 мс.
Итоги
Подведем сводную таблицу различных вариантов поиска с опечатками
| Тип поиска | Время создания индекса | Размер индекса | Скорость поиска с опечатками | Замечания |
| Триграммы 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 с триграммами. Если у кого-то есть идеи, как можно оптимизировать функцию на Python по скорости, то отпишитесь в комментариях, я добавлю данные в тесты.
Автор: Денис Смирнов
