trigramを用いた関係によるファジィ探索結果の順序付け

私は名前やメールでユーザーを検索したいと言う.「ANA」と入力すれば、名前や電子メールに文字の組み合わせ「ANA」が入っているすべてのユーザーを取得します.「ANA」との正確な一致ではなく、それを含むことができる電子メールまたは名前があるかもしれないので、私は含まれています[email protected] ' - 私は自分の結果から除外したくない.他の名前やメール' ANA 'と同様の価値がある誰でも検索している.
このタイプの検索は、ファジーストリングマッチングと呼ばれていて、ワイルドカードを使用することでSQLで実行されることができます.PostgreSQLを使用しますが、他のデータベースに同様のsqlsを書き込むことができます.

SELECT id, name, email
FROM users
AND users.name ILIKE '%ana%'
OR users.email ILIKE '%ana%'
LIMIT 20

この質問は、名前または電子メールが『ANA』を含むすべてのユーザーを返します、しかし、私はどんな特定の順序ででも彼らを得ません.私はアルファベット順に'名前'と'メール'で注文することができますが、それは関連性を保証しません.私は最初の20に結果を制限するので、アルファベット順に、関連する結果を除外することもできます.
幸いにも、Postgresはこの非常に興味深い拡張機能を持っていますpg_trgm . から引用するpostgresql ドキュメント

[pg_trgm] provides functions and operators for determining the similarity of alphanumeric text based on trigram matching, as well as index operator classes that support fast searching for similar strings.

言語学では、trigramは、手紙、音節、または単語のような3つの連続した書かれた単位のグループです.Postgresが行う語はtrigramに単語を分割することです.例えば、' Ruby ' trigramは“r”、“ru”、“by”、Ruby、uby }です.いくつかのtrigramに空のスペースがあることに注意してください.これは、各単語が接頭辞の2つのスペースを持っていると見なされるため、文字列に含まれているtrigramのセットを決定するときに1つのスペースが優先されます.私たちが本当にこれから取る必要があるものはPostgresが3つの英数字の小さい塊に語を分割して、それから他の語の同じサイズ塊と類似点をチェックするということです.
したがって、Trigramsを使用して2つの文字列を比較すると、Postgresは0から1(ここで1は完璧な一致です)の間の類似性をスコアすることができます.と遊びましょうpg_trgm それがどのように働くかについて理解する拡張.
まず、拡張モジュールを追加します.

CREATE EXTENSION pg_trgm;

今、私は2つの単語を比較することができます:

SELECT SIMILARITY('Ana', 'Addriana'); 
-- returns 0.3

SELECT SIMILARITY('Ana', 'Alana'); 
-- returns 0.42857143

これはアルファベット順にの結果を示しています.' Ana 'を検索した場合、' addriana 'は' alana '以前の結果に表示されます.あなたの製品の要件に応じて、アルファベット順にあなたのためにOKかもしれない.類似性を使用すると、複雑なビットをコードに追加しますが、この場合、私が取り組んでいる検索機能に値を追加します.
それで、我々がどのようにtrigramsと類似関数が働くかについてわかっているので、我々の初期の質問にそれを加えましょう.類似性で注文するには、まずSELECT そのスコアはエイリアスを与え、その変数をORDER BY 条項

SELECT
id,
name,              
email,
SIMILARITY(name, 'ana') AS name_score,
SIMILARITY(email, 'ana') AS email_score
FROM users
WHERE users.name ILIKE '%ana%'
OR users.email ILIKE '%ana%'
ORDER BY name_score DESC NULLS LAST, email_score DESC NULLS LAST, name
LIMIT 20;

見ているORDER BY つのコラムを捜しているので、私は最も関連性があると思いましたname_score . それから、私は見ますemail_score そして必要ならアルファベット順に注文します.

Trigramインデックスによる高速探索
今私たちのクエリを持っている、私はそのパフォーマンスを分析して、それはかなり速い(〜100〜130 ms)ようです.それでも、私は私のユーザーが入力しているとして検索結果を返したいので、私はこの検索をちょうど速くすることを望みません.私はすぐにフィードバックが必要です.私は応答時間を改善できるかどうかを確認するために2組のインデックスをテストするつもりです.
GIN(一般化された倒立インデックス)とGIST(一般化された検索木)インデックスは、複数の値(例えば、trigramのリスト)を単一の行にマップすることができるので、テキスト検索機能で非常に有用です.一方、PostgresのデフォルトB - treeインデックスは、行が1つのキー値を持つときに最適化されます.
ジン対GISTの間を選ぶとき、私はジンインデックスと一緒に行くことに決めました.書くのは少し遅いかもしれませんが、GISTインデックスより読みやすいです.すべてのパフォーマンスの問題が発生しないことを確認するために、私は生産データに類似したデータ量でローカルインデックスを作成することをテストしました.インデックスを作成すると、書き込み用のテーブルをロックし、問題の場合には、ダウンタイムを引き起こす可能性があります.これを避けるために、Postgresにこれらのインデックスを同時に作成します.これらはビルドするためにより長くかかることができますが、ブロックが書き込むロックを必要としません.
だから助けてpg_trgm , Trigramに基づいてインデックスをサポートしています.私が探している列のそれぞれにジンインデックスを追加します.name and email - 演算子クラスgin_trgm_ops Postgresにこれらのインデックスをtrigramでビルドするよう指示します.

CREATE INDEX CONCURRENTLY index_users_on_name_trigram
ON users 
USING gin (name gin_trgm_ops);

CREATE INDEX CONCURRENTLY index_users_on_email_trigram
ON users 
USING gin (email gin_trgm_ops);

これらの2つのインデックスを使用して、クエリランタイムを🚀.

その他ILIKE 対LIKEPostgreSQLを使うと決めた理由は二つありますILIKE 関数の代わりにLIKE . つは、パフォーマンスとパフォーマンスの他の1つと他の機能を行う必要があります.
機能性に関しては、2つの主な違いはILIKE 大文字小文字を区別しない.だから、もし「ANA」と「ANA」が同じかどうか知りたいのなら、ILIKE は、そのステートメントがtrueであることを教えてくれますLIKE それ以外の場合は

SELECT 'Ana' ILIKE 'ana'; 
-- returns true

SELECT 'Ana' LIKE 'ana'; 
-- returns false

することができますLIKE 大文字小文字を区別しないLOWER 機能

SELECT 'Ana' ILIKE 'ana'; 
--returns true

SELECT LOWER('Ana') LIKE LOWER('ana'); 
-- returns true

しかし、これはより詳細であり、この機能にどんな値も加えないエラーバージョンの傾向があります.加えて、パフォーマンスのわずかな改善に注目しましたILIKE .
あなたがこれらの2つのアプローチの間のパフォーマンスの違いを理解することに興味があるならば、私は推薦しますthis stackoverflow thread . ここでは2つのセントを読んだ後、いくつかのベンチマークを行います.LIKE with LOWER ) は最初よりかなり速くなりますILIKE ) インデックスを使用していない場合.良いインデックスを使用すると、それらの違いは減少または反転されます.私の場合、異なるGINインデックスを作成するname , email そのことを示すILIKE オプションは最もパフォーマンスが高い(インデックスがあるが、この違いは関連しない).

結論
PostgreSQLの使用pg_trgm 拡張は、検索結果の関連性を向上させるだけでなく、また、大きなパフォーマンスの改善(以前は低迷したユーザーエクスペリエンス)と、この機能をもたらした.最終的なクエリとインデックスソリューションを思い付くために、私は使用しました pgAdmin 異なる仮説をテストするにはPostgresEXPLAIN ANALYZE 私はまた、この開発を通じて大規模に使用している素晴らしいコマンドです.それぞれの問題が異なっていることを覚えておいてください.そうすれば、Postgresが異なる潜在的解決策を分析し、測定するためのツールを使用するように誰にもアドバイスすることができます.