PostgreSQLで類似した文字列をすばやく見つける

あなたがそれを持っている方法で、テーブルのすべての要素と他のすべての要素の間の類似性を計算する必要があります（ほとんどクロス結合）。テーブルに1000行ある場合、それはすでに1,000,000（！）の類似度計算です。前それらは条件に対してチェックされ、ソートすることができます。ひどくスケーリングします。

SET pg_trgm.similarity_thresholdを使用します および% 代わりに演算子。どちらもpg_trgmによって提供されますモジュール。このように、トリグラムGiSTインデックスを使用すると大きな効果が得られます。

構成パラメーターpg_trgm.similarity_threshold 関数set_limit()を置き換えましたおよびshow_limit() Postgres9.6で。非推奨の関数は引き続き機能します（Postgres 13以降）。また、Postgres 9.1以降、GINおよびGiSTインデックスのパフォーマンスは多くの点で向上しました。

代わりに試してください：

SET pg_trgm.similarity_threshold = 0.8;  -- Postgres 9.6 or later
  
SELECT similarity(n1.name, n2.name) AS sim, n1.name, n2.name
FROM   names n1
JOIN   names n2 ON n1.name <> n2.name
               AND n1.name % n2.name
ORDER  BY sim DESC;

桁違いに高速ですが、それでも低速です。

pg_trgm.similarity_threshold は「カスタマイズされた」オプションであり、他のオプションと同じように処理できます。参照：

「max_connections」のようなパラメータ（postgresql.conf設定）をクエリします

前に前提条件（最初の文字の一致など）を追加して、可能なペアの数を制限することをお勧めします。相互結合（および一致する機能インデックスでそれをサポートします）。 クロスジョインのパフォーマンス O（N²）で劣化します。

これは機能しません WHEREの出力列を参照できないためまたはHAVING 条項：

WHERE ... sim > 0.8

これはSQL標準（他の特定のRDBMSによってかなり緩く処理されます）に準拠しています。一方：

ORDER BY sim DESC

動作出力列ができる GROUP BYで使用されますおよびORDER BY 。参照：

PostgreSQLが計算結果を選択クエリで再利用する

テストケース

古いテストサーバーでクイックテストを実行して、クレームを確認しました。
PostgreSQL9.1.4。 EXPLAIN ANALYZEにかかった時間（ベスト5）。

CREATE TEMP table t AS 
SELECT some_col AS name FROM some_table LIMIT 1000;  -- real life test strings

GINインデックスを使用した最初のテスト：

CREATE INDEX t_gin ON t USING gin(name gin_trgm_ops);  -- round1: with GIN index

GISTインデックスを使用した第2ラウンドのテスト：

DROP INDEX t_gin;
CREATE INDEX t_gist ON t USING gist(name gist_trgm_ops);

新しいクエリ：

SELECT set_limit(0.8);

SELECT similarity(n1.name, n2.name) AS sim, n1.name, n2.name
FROM   t n1
JOIN   t n2 ON n1.name <> n2.name
           AND n1.name % n2.name
ORDER  BY sim DESC;

使用されたGINインデックス、64ヒット：合計実行時間：484.022ミリ秒
使用されたGISTインデックス、64ヒット：合計実行時間：248.772ミリ秒

古いクエリ：

SELECT (similarity(n1.name, n2.name)) as sim, n1.name, n2.name
FROM   t n1, t n2
WHERE  n1.name != n2.name
AND    similarity(n1.name, n2.name) > 0.8
ORDER  BY sim DESC;

GINインデックスない使用済み、64ヒット：合計実行時間：6345.833ミリ秒
GISTインデックスなし使用済み、64ヒット：合計実行時間：6335.975ミリ秒

それ以外は同じ結果になります。アドバイスは良いです。そしてこれはたった1000行のためのものです！

GINまたはGiST？

多くの場合、GINは優れた読み取りパフォーマンスを提供します：

GiSTとGINインデックスの違い

しかし、この特定のケースではありません！

これは、GiSTインデックスでは非常に効率的に実装できますが、GINインデックスでは実装できません。

異種データ型の3つのフィールドの複数列インデックス