[解決済み] PostgreSQLで類似した文字列を素早く検索する

質問

テーブルの中の類似した文字列のランキングを作成する必要があります。

次のような表があります。

create table names (
name character varying(255)
);

現在、私は pg_trgm モジュールが提供する similarity 関数がありますが、効率の面で問題があります。のようなインデックスを作りました。 Postgresのマニュアルによると :

CREATE INDEX trgm_idx ON names USING gist (name gist_trgm_ops);

で、以下のクエリを実行しています。

select (similarity(n1.name, n2.name)) as sim, n1.name, n2.name
from names n1, names n2
where n1.name != n2.name and similarity(n1.name, n2.name) > .8
order by sim desc;

このクエリは動作しますが、何百もの名前がある場合、本当に遅くなります。さらに、私はSQLを少し忘れてしまったのかもしれませんが、どうして and sim > .8 column sim doesn't exist"というエラーを出さずに済みます。

クエリを高速化するためのヒントがあれば教えてほしい。

どのように解決するのですか？

この方法では、テーブルのすべての要素と他の要素との間の類似性を計算する必要があります（ほとんどクロスジョインです）。テーブルが1000行ある場合、すでに1,000,000（！）の類似性計算が必要です。 以前 を条件と照合し、ソートすることができる。恐ろしくスケールが大きい。

使用方法 SET pg_trgm.similarity_threshold と、その % 演算子 の代わりに どちらも pg_trgm モジュールを使用します。こうすることで、トリグラムGiSTインデックスを効果的に使うことができる。

設定パラメータ pg_trgm.similarity_threshold は、関数を置き換えたものです。 set_limit() と show_limit() をPostgres 9.6で使用しました。非推奨の関数はまだ動作します（Postgres 13 時点）。また、GINとGiSTインデックスの性能はPostgres 9.1以降、多くの点で向上しています。

代わりに試してみてください。

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はselectクエリで計算結果を再利用します。

テストケース

私の主張を検証するために、古いテストサーバーで簡単なテストを実行しました。
PostgreSQL 9.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 ms
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.833ms
GISTインデックス ではない 使用、64ヒット：総実行時間：6335.975ミリ秒

それ以外は同じ結果です。アドバイスが良いですね。そして、これは わずか1000行 !

GINかGiSTか？

GINは多くの場合、優れた読み取り性能を発揮します。

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

しかし、この場合ではありません

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

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