47

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

私は次の表を持っています

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;

クエリは機能しますが、名前が数百ある場合は非常に遅くなります。and sim > .8さらに、SQLを少し忘れたかもしれませんが、「列simが存在しません」というエラーが発生せずに条件を使用できない理由がわかりません。

クエリを高速化するためのヒントが欲しいのですが。

4

1 に答える 1

98

あなたがそれを持っている方法で、テーブルのすべての要素と他のすべての要素の間の類似性を計算する必要があります（ほとんどクロス結合）。テーブルに1000行ある場合、条件と照合して並べ替える前に、すでに1,000,000（！）の類似性計算が行われます。ひどくスケーリングします。

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

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

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

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は「カスタマイズされた」オプションであり、他のオプションと同じように処理できます。見る：

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

または句の出力列を参照できないため、これは機能しません。WHEREHAVING

WHERE ... sim > 0.8

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

ORDER BY sim DESC

とで出力列を使用できるGROUP BYため、機能しますORDER BY。見る：

テストケース

古いテストサーバーでクイックテストを実行して、クレームを確認しました。
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インデックスでは実装できません。

于 2012-06-28T17:36:18.613 に答える