PostgreSQLにおけるファジィ探索の実装ハンドブック

ソフトウェア工学がpolyglotになったように、PostgreSQLのようなデータベースシステムはますますマルチモデルになりました.

.

Key-Value store type in PostgreSQL .

.

そしてもっとたくさん.本稿では、PostgreSQLのファジーサーチを実装する方法に焦点をあてます.

PostgreSQL Varlenaデータ型の紹介

我々が選択するかどうかにかかわらずchar , varchar or text , PostgreSQLの使用構造は以下の通りです varlena . スキーマをデザインしようとすると、データベースがどのように解釈しているかを理解することが重要です.以下はからの抜粋ですdocs ,
注意:これらの3つのタイプの間にパフォーマンスの違いはありません.空白のパッド型を使用した場合のストレージ領域の増加と、長さの制約を受けた列に格納するときの長さをチェックするためのいくつかの余分なCPUサイクルです.中character( n ) それは他のいくつかのデータベースシステムで性能上の利点があります.PostgreSQLにはそのような利点はありません.事実、character( n ) それは通常、その追加のストレージコストのため、3つの中で最も遅いです.たいていの場合text or character varying 代わりに使用する必要があります.
The text DataTypeはこの記事の主な焦点です.

学習のためのデータセットの選択

この記事のために、我々は2009年から嵐イベントデータセットを選ぶつもりですNOAA website . 簡単にするために、我々はオリジナルのデータセットが付属しているすべての列を含みません.以下は、データセットのデータベーススキーマの修正です.

対応するテーブルは、次のCREATE TABLEステートメントを使用して作成できます.

CREATE TABLE storm_events (
  event_id integer,
  event_type text,
  damage_property text,
  damage_crops text,
  event_source text,
  flood_cause text,
  episode_narrative text,
  event_narrative text
)

以下のコマンドを使ってCSVをインポートできます.

COPY storm_events FROM '/path/to/csv' DELIMITER ',' CSV HEADER;

Btreeインデックスを用いた簡単な探索

テキスト列で実行できるクエリの中で最も簡単なのは、等値演算子です.イベントタイプがAであるクエリを実行しましょうWinter Storm .

SELECT
  event_narrative
FROM
  storm_events
WHERE
  event_type = 'Winter Storm'

計画は、インデックスがない場合、すべての行を検索することです.クエリプランの詳細については、そのトピックの詳細記事です.

インデックスの作成

クエリを高速化する40ms 行の数が少ないために、しかし、テキストが大きく、行の数の増加とともに大幅に変更されます.40ms クエリの数が数千になり、サーバーを大幅に遅くすることができるので、リレーショナルDBSでは非常に遅いと見なされます)簡単なB - treeインデックスを作成できます.

CREATE INDEX ON storm_events USING BTREE(event_type)

また、多数の行があれば、同時にインデックスを作成します.

簡単なクエリの実行

インデックスを作成した後、我々は速度の向上が重要です観察することができます.

The B-Tree index PostgreSQLの世界で最も単純な、まだ使用されているインデックスの一つです.しかし、テキストに関しては、それは検索を扱うことができません.以下の質問を考えてみましょう.私たちは、嵐、すなわち、冬の嵐や氷の嵐などのイベントを検索します.

EXPLAIN ANALYZE SELECT
  event_type
FROM
  storm_events
WHERE
  event_type LIKE '%Storm'

btreeインデックスはそのようなクエリを処理できません.また、プランナーはシーケンシャルスキャンに対応します.

パターン検索

インデックスを作成する場合、B - treeはまだ検索のバリエーションを処理することができます pattern_ops 戦略

CREATE INDEX anchored_search ON storm_events (event_type text_pattern_ops)

左アンカー探索を使用する前に使用したクエリLIKE '%Storm' インデックスを使用できます.

regex検索

The pattern_ops 正規表現でも使えます.下記のクエリを考えます.

SELECT
  DISTINCT(event_type)
FROM
  storm_events
WHERE
  event_type ~ '^(S|H)'

これはS or H .
注意:この結果は、結果のアイデアを与えるためだけに使用されます.

上に作成したアンカーされた検索インデックスなしで、上記のクエリはシーケンシャルスキャンを使用します.今ではインデックスを使用します.

パターンの制限

フルテキスト検索でもインデックスを使用しようとするが、それは大幅に遅くなります.下記のクエリを考えます.

SELECT
  event_type
FROM
  storm_events
WHERE
  event_type ILIKE '%winter%'

私たちはILIKE 我々はケースを知らないので、それは混合ケースでもすることができます.また、語winter 文字列内の任意の場所に存在できます.これを実行すると、クエリはインデックスを使用しようとします.

以前のアンカーされた検索(すなわち接頭辞または接尾語検索)より約3.4 x遅いです.
つは、これがシーケンシャル探索より良いと主張することができました.

しかし、これは単なる速度よりも制限があります.のようなより大きな列にパターンopsインデックスを作成してみましょうepisode_narrative .

CREATE INDEX anchored_search_full ON storm_events (episode_narrative text_pattern_ops)

これはエラーになります.

B - treeインデックスは固有のサイズ制限(良い理由のために)を持っています.ファジィ検索の現実世界ユースケースに移りましょう.

PostgreSQLにおけるファジィ探索

Btreeインデックスは、より良いパフォーマンスで直接マッチまたは接頭辞/接尾辞マッチでより小さなストリングだけを検索することができます.しかし、現実世界では、ユーザーはしばしば単語を間違えます、そして、それは彼らを捜すのがかなり難しいです.これはPostgreSQLのファジーサーチ機能が入っているところです.同様の単語で文字列を検索でき、btreeインデックスのサイズ制限はありません.

trigramを用いた単語の類似性

trigramインデックスなしでは、可能性を介して手動で検索しない限り、可能性を検索することは実質的に不可能です.では、どのようにtrigram indexを作成できるかを見てみましょう.

CREATE EXTENSION pg_trgm;

この拡張機能が有効になったら、以下のようなファジー検索を行うことができます.

The SIMILARITY 関数は、いわゆるスコアを返します.我々は必要な試合に応じて、このスコアを調整することができます.デフォルトのスコアは0.3 そして、もし我々がスコアを心配していない場合は、以下の速記を使用することができます.

SELECT * FROM storm_events WHERE event_type % 'Drot'

これは上記のクエリと同じです.The documentation これはかなり広範囲です、そして、拡大は他のきちんとした機能をたくさん持っています.このセクションの後のインデックスを使用してこのようなクエリを高速化する方法を参照してください.

レベンシュテインマッチング

The Levenshtein distance つの単語、すなわち、単一の文字の最小数の間の距離は、マッチするストリング/語のために必要とされる編集です.この機能を使用するには、別の拡張子を fuzzystrmatch .

CREATE EXTENSION fuzzystrmatch;

同じ文字列から4未満のlevenshtein距離を持つすべての偶数の型にマッチしましょうdrot .

SELECT * FROM storm_events WHERE levenshtein(event_type, 'Drot') < 4

イベントタイプに関する結果も得ることに注意してくださいHeat .

発音試合

The fuzzystrmatch エクステンションは、同様のスペルを持っていないが、同じ音を検索することができます別のクールな機能を備えています.

SELECT DISTINCT(event_type) FROM storm_events WHERE DIFFERENCE(event_type, 'he') > 2

これは私たちすべてのイベントのような音を与えるhe .

高速化のインデックス

私たちのtrigramクエリをスピードアップするために使用できる特別なインデックスがあります.

CREATE INDEX trgm_idx on storm_events using gin(event_type gin_trgm_ops);

我々は重要なスピードアップを見ることができます.しかし、返される行が多いので(5160)、クエリは少し長くなります.

Postgresファジィ探索トレードオフ

PostgreSQLには、多くの高度な拡張機能とインデックスがあります.しかし、これらは、速度に関して独自の制限があり、英語/マルチバイト符号化以外の言語で動作しないかもしれないことを心に留めておくべきですUTF-8 . しかし、これらの機能が必要な重要なギャップを埋めるが、我々は完全な検索ソリューションなどのために行くことはできませんSolr/Elastic Search .

閉鎖思考

ここまで学んだことを要約しましょう.

直接文字列マッチ.

パターンオプスLIKE and Regex クエリ.

trigramファジィ探索

レベンシテインマッチング

音声マッチ.

私たちは、この記事では全文検索などの記事を見ていない検索に関して、より多くの機能がありますtext , ts_vector and jsonb 今後の記事で調査されるデータ型.