🔧 🚆 🙁 PostgreSQLのタイプミスを探す 🎅🏽 🙅🏿 🤾🏽

すべては、1つの内部医療システムの患者検索を開発する必要があるという事実から始まりました。作業のロジックは、システム内で人が見つからなかった場合、それを作成する必要があるということでした（そして、重複した患者を作成することはできません）。この点で、サブタスクの1つは、名前のタイプミスを考慮した人の検索の実装でした。まあ、私はPostgreSQLが大好きなので（そしてハンマーを手に持っていると、すべてが釘のように見えます）、タイプミス検索を実装することに決めたものを推測するのは難しくありません...

通常、この問題は、ファジー検索または音声アルゴリズムの使用という2つの方法で解決できます。怠け者であり、すべてのものが私たちの前に長い間盗まれたという神聖な信者であった私は、PostgreSQLのドキュメントに目を向けました。 PostgreSQLには現在、タイプミスに役立つ2つのモジュールがあります： pg_trgmとfuzzystrmatchです。

pg_trgmはトライグラムで動作し、部分文字列およびファジー検索で検索できます。インデックスとしてgistとginで動作します。
fuzzystrmatchは、単語と3つの音声アルゴリズム（ Soundex 、 Metaphone 、およびDouble Metaphone）間のレーベンシュタイン距離をカウントできます。落とし穴は、まず、このモジュールのレーベンシュタイン関数では、任意の検索クエリのインデックスを作成できないことです。第二に、すべての音声アルゴリズムはラテンアルファベット用に実装されています。

この点で、私はそれがより軽い問題、つまりpg_trgmモジュールからの解決策を探し始めました。

トライグラム

モデルを単純化するために、患者ID、彼の姓、名、および後援者を含む情報テーブルを検討します。 gist / ginインデックスが必要なので、最初に重要であるが不快な瞬間を知る必要があります。1つのgist / ginインデックス-テーブルの1列です。たとえば、複数の列を連結して作成することはできません。したがって、猫の下に作成されます：

pg_trgm拡張
jsonbの形式で名前を格納する患者テーブル（キーの存在と入力のチェック付き）
名前をjsonbからテキストに変換する、トリグラムインデックスを構築するための不変の関数

退屈な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; $$;

フルネームの約30万件のレコードをテーブルに挿入して続行します。

トライグラムと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 MB、入力ミスのある不完全な名前による検索-158ミリ秒です。

トライグラムと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 MB、タイプミスで不完全な名前を検索-133 ms。

正直に言うと、結果はまあまあです-私のラップトップには、栄光の都市深Shenzhenの中国製のssdディスクがあります。そのため、ファジー検索と全文検索を組み合わせてプロセスの高速化を試みます。

トライグラムと全文検索

アイデアは非常に単純です-姓、名前、愛称のすべてのスペルから、別個のテーブル辞書を収集します。最初に、入力検索文字列をトークンに切り取り、ファジー検索でディクショナリテーブル内の各トークンを探し、そこから各トークンのすべての可能なスペルバリエーションを選択し、tsqueryに入れて、infoテーブルのtsvectorインデックスで全文検索を実行します。このプランの利点は、トライグラムによるファジー検索の速度が行の幅とテキストのある列の番号に依存することです。明らかに、フルネーム辞書はinfoテーブルの元の列よりもコンパクトになるため、検索が高速になります。この方法には1つだけ欠点があります。新しい患者を追加するたびに、名前のトークンが見つからない場合は辞書を更新する必要があります。検証のために、ソースrumからインデックスを収集して、infoテーブルの名前でtsvectorインデックスを作成する必要があります。ラムはジンインデックスの修正バージョンであり、リーフに追加情報を保存します。この場合、rum_tsvector_ops演算子クラスを使用します。これは、インデックス内のトークンに関する位置情報を格納します。したがって、ginとは異なり、次の形式のインデックスのみのtsqueryクエリを使用できます。

 (||)<->()<->()

タプル内のトークンの順序に関する詳細については、表に移動しません。さらに、ginの推奨事項は、tsvector列の物理的な存在です。これは、タプルへのすべての見つかったポインターをテーブルでダブルチェックする必要があるためです。また、tsvector列が物理的にない場合（インデックス用の関数を使用して作成した場合）、各タプルに対して追加のtsvector計算を実行する必要があります。一般に、この物語のラム酒ははるかに生産的です。

退屈な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 MB）作成され、トークン辞書インデックスが0.6秒（サイズ5.8 MB）で作成され、検索は68ミリ秒でした。欠点のうち、選択性は以前のオプションよりも劣っています。

音声アルゴリズム

pg_trmgモジュールのファジー検索オプションを試した後、fuzzystrmatchをもう一度見ることにしました。レーベンシュタイン関数にインデックスを付ける方法は思いつきませんでしたが、音声アルゴリズムは非常に興味深いものでした。前述のように、PostgreSQLでは、表音関数はラテンアルファベットに対してのみ実装され、英語の名前に対して投獄されます。ロシアの実装をインターネットで検索した結果、Habrの素晴らしい記事に移動しました。この記事では、ロシア語の名前（ロシア語の文字で構成される）のMetaphoneアルゴリズムについて説明しています。悲しかったのは1つだけです-単純ですが、plpgsqlでこのロジックを実装するか、Pythonで何かを実装するのはなんとなく悲しいことでした...そして、plpython3uは安全ではないことを思い出しましたpostgresプロセスの権限を持つファイルシステム）、PostgreSQLで完全に機能する言語。そして、それを使わないのは罪です。したがって、2つの不変の関数を作成しました。

plpython3uの音素。Habréの記事のアルゴリズムに従って、トークンを音素に変換します（「smirnov」を「smirnaf」に変換）。
plpgsqlのmetaphone。1つのトークンを音素に変換するだけでなく、テキスト全体を音素セットに変換します。実際、これは音素関数の単なるバインディングです。

Metaphoneとbtree

次に、metaphone関数で通常のbtreeインデックスを作成し、速度を評価してみてください。

通り過ぎる、面白いものは何もない

 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 MB（パフォーマンスの観点からPythonで最も最適な関数を記述していないようです）、リクエストは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 Mb（こんにちは、私の曲がった手とplpython3u）、検索-14 ms。

まとめ

さまざまなタイプミス検索オプションをまとめましょう

更新1： movEAXからMetaphone 実装を追加しました。

更新2： Ivan MilovanovからplpgsqlにMetaphone実装が追加されました（telegram-milovanov）

plpgsqlのMetaphone

 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; $$;

検索の種類	インデックス作成時間	インデックスサイズ	タイプミス検索速度	備考
トライグラムの要点	15秒	45 Mb	158ミリ秒
ジントライグラム	10秒	18 Mb	133ミリ秒
トライグラムと全文検索	7.6秒	18.8 Mb	68ミリ秒	さらに悪い選択性、トークンの辞書を維持する必要があります
Metaphone btree	114秒	22 Mb	131ミリ秒	安全でない言語plpython3u
Metaphone Trigram	124秒	15 Mb	14ミリ秒	安全でない言語plpython3u
movEAXからMetaphone Trigramを実装する	77.8秒	16 Mb	14ミリ秒	安全でない言語plpython3u
plpgsqlでのIvan Milovanovの実装	72.0秒	16 Mb	14ミリ秒

更新3：インデックスに「smirnaf dinis anatalievich」が含まれる場合、 ミドルネームの 「in」の文字は聞こえません（その後に母音があるため）。部分文字列メタフォン（ 'anatolia'）を見ると、文字「c」は母音の上にありませんが、最後にはat然とします。この問題を回避するために、 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; $$;

私の場合、システムは書き込みではなく読み取りに焦点を当てるため（最大で1分間に患者のペアを追加する）、私のオプションはTrigram付きのMetaphoneです。 Pythonの関数を速度の観点から最適化する方法について誰かがアイデアを持っているなら、コメントの購読を中止し、テストにデータを追加します。

PostgreSQLのタイプミスを探す