PostgreSQLで高度な検索エンジンを作る
(xata.io)- PostgreSQLの全文検索は、専用の検索エンジンなしで
tsvector、tsquery、@@、ts_rank、GINインデックス を組み合わせて検索機能を構築するアプローチ - 検索語と文書を lexeme 単位で正規化し、AND・OR・NOT・FOLLOWED BY のような演算子でクエリを表現することで、一般的な検索文法のかなりの部分を実装できる
- GINインデックスは、例の環境では検索時間を 200ms超から約4ms に短縮したが、結果が増えると
ts_rankによるランキング・ソートのコストがボトルネックになりうる - 関連度の調整は、タイトルの重み、投票数、評価、ジャンル、新しさといったシグナルを ソート式 に加える、あるいは
setweightでカラム重みを付与することで実装する - タイポ許容、ファセット検索、オートコンプリート、正確なフレーズ検索、ハイブリッド検索も可能だが、PostgreSQLでは構成要素を自分で組み合わせる必要があり、大規模データセットでは性能の限界を確認する必要がある
PostgreSQL全文検索のアプローチ
- PostgreSQLは全文検索のための低レベルな 構成要素 を提供しており、それらを組み合わせて検索エンジン機能を作れる
- この方式は柔軟だが、全文検索を主用途とする Elasticsearch、Typesense、Meilisearch よりも実装作業が多く必要になる
- 例のクエリでは Kaggle の Wikipedia Movie Plots データセットを使用
- 映画タイトル34,000件を含む
- CSV形式のサイズは約 81MB
中核構成要素
- PostgreSQL全文検索は次の要素を中心に動作する
tsvector: 検索対象テキストを正規化された lexeme の一覧として保存tsquery: 正規化された検索クエリを表現@@:tsqueryがtsvectorと一致するかを確認するマッチ演算子ts_rank、ts_rank_cd: 検索結果の関連度スコアを計算- GINインデックス:
tsvectorを効率的に問い合わせるための転置インデックス
tsvector と検索設定
tsvectorはソート済みの lexeme 一覧を保存する- lexeme はトークンに似ているが、同じ単語の複数の形が1つにそろうよう正規化された文字列
- 英語設定では、大文字を小文字に畳み込み、接尾辞を除去する形で正規化する
to_tsvectorで英語文をパースすると、“I”、“to”、“an” のような ストップワード が除去される- “refuse” と “Refusing” はどちらも
refusに変換される - 句読点は無視される
- 元文での単語位置と重みも記録される
- “refuse” と “Refusing” はどちらも
english検索設定の代わりにsimple設定を使うと、単語はテキスト内で見つかった形のまま含まれる- “refuse” と “refusing” は別々の lexeme のまま残る
simple設定は、ラベルやタグを含むカラムで特に有用
- PostgreSQLは複数言語の組み込み検索設定を提供するが、CJK（中国語・日本語・韓国語）の設定はない
- サポートされない言語には
simple設定が実用的にうまく動作することがある - ただし、CJKに十分かどうかは確かではない
- サポートされない言語には
tsquery とクエリ表現
tsqueryは正規化された検索クエリを表現するデータ型- 検索語はすでに正規化された lexeme である必要がある
- 複数の検索語は AND、OR、NOT、FOLLOWED BY 演算子で結合できる
to_tsquery、plainto_tsquery、websearch_to_tsqueryは、ユーザー入力のテキストを適切なtsqueryに変換する助けになる- 中核となる役割は、入力テキストに含まれる単語を正規化すること
websearch_to_tsqueryを使うと、一般的な検索ボックスに近いクエリを作れるdarth vaderは、両方の単語が文書内に存在しなければならない論理ANDとして扱われる- OR検索や単語の除外も可能
- フレーズ検索は、単語が順番どおりにつながる形を表現する
- 英語設定では “the” のようなストップワードが除去されるため、一部のフレーズ検索ではほぼ全文句が消えてしまうことがある
- この場合は
simple設定を使うと期待どおりの結果が得られる
- この場合は
@@演算子は、tsqueryがtsvectorと一致するかを確認するときに使う
GINインデックスと検索性能
- GIN は Generalized Inverted Index の略で、複合値の中に含まれる要素値を見つけるクエリ向けに設計されたインデックスタイプ
- GINはテキスト検索だけでなく JSON クエリにも使える
- 検索対象となる複数カラムを結合した
tsvectorカラムを作り、そのカラムに GIN インデックスを生成できる - 例の環境では GIN インデックスにより、検索時間は 200ms超から約4ms に短縮された
ランキングと関連度計算
- 良い検索体験のためには、結果を 関連度 で並べ替える必要がある
- PostgreSQLは
ts_rankとts_rank_cdの2つの事前定義ランキング関数を提供する- どちらの関数も検索語の出現頻度を考慮する
ts_rank_cdは一致した lexeme 間の近接性も反映する
- 関連度はアプリケーションの性質に大きく左右される
- 基本のランキング関数は出発点に近く、必要に応じて独自のランキング関数を作ったり他の要素と組み合わせたりできる
ts_rankは各結果のsearchカラムにアクセスする必要があるWHERE条件に多くの行がマッチすると、PostgreSQLはランキング計算とソートのためにそれらすべての行を訪問しなければならない- 例の環境では、あるクエリは5〜7msで返ったが、
darth OR vaderのように1,000件超の結果をランキングするクエリでは約 80ms かかった
関連度チューニング
- 単語頻度ベースの関連度は良いデフォルトだが、データには頻度より重要なシグナルがある場合がある
- 映画データセットでは、次のシグナルを関連度に反映できる
- タイトルでマッチした結果を、説明やあらすじでマッチした結果より重要に扱う
- 評価や投票数を基準に、より人気の高い映画を押し上げる
- ユーザーがコメディを好むなら、コメディ映画をより上位に配置する
- 古いタイトルより新しいタイトルのほうをより関連度が高いとみなす
- 専用検索エンジンは、異なるカラムやフィールドがランキングに影響するよう設定する機能を提供している
- 関連ドキュメントの例として Elastic、Typesense、Meilisearch を参照
数値、日付、正確な値に基づくブースト
- PostgreSQLは他カラムに基づくブーストを直接は提供しないが、ランキングは結局 ソート式 なので独自シグナルを加えられる
- 投票数を反映するには、ランキングスコアに投票数ベースのブーストを加える形で実装できる
- 例ではログを使って影響を緩やかにしている
0.01の係数でブースターをランキングスコアと近いスケールに合わせている
- 投票数が一定以上の場合にのみ評価をブーストする、より複雑な関数も作れる
- 特定のジャンルを押し上げたいなら、値が特定カラム値と一致したときだけ係数を返す
valueBoosterのような関数を使える
カラム重み
tsvectorの lexeme には 重み を付けられる- PostgreSQLは A、B、C、D の4種類の重みをサポートする
- A が最も高い重み
- D が最も低く、デフォルト値
setweight関数を使ってtsvectorカラムを作る際に重みを制御できる- タイトルカラムにより高い重みを与えると、検索語がタイトルに含まれる映画が結果上位に上がり、ランキングスコアも増加する
- 重みクラスが4つしかない点は制約であり、重みは
tsvectorを計算するときに適用する必要がある
タイポ許容とあいまい検索
- PostgreSQLは
tsvectorとtsqueryを使う場合、あいまい検索 やタイポ許容を直接サポートしない - クエリ側にタイプミスがある前提で、次の方法で実装できる
- コンテンツ中のすべての lexeme を別テーブルにインデックスする
- クエリの各単語ごとに、類似度や Levenshtein distance で候補語を検索する
- 見つかった単語を含むようにクエリを修正する
- 修正後のクエリで検索を実行する
- 例では、検索エンジンがあいまい検索に使う方式であることを理由に Levenshtein distance を使用している
- 候補語の一覧を得たあとは、それらの単語をすべて含むようにクエリを調整する必要がある
ファセット検索
- ファセット検索 は、とくにECサイトでユーザーが検索範囲を段階的に絞り込むために広く使われている
- PostgreSQLではカテゴリを手動で定義し、それを検索の
WHERE条件に追加して実装できる - 既存データをもとにカテゴリをアルゴリズム的に作る方法も可能
- 例では映画の年をもとに “Decade” ファセットを作る
- 各 decade ごとの一致件数も計算し、括弧内に表示できる
- 複数ファセットを1回のクエリで取得するには CTE を組み合わせられる
- この方法は小規模〜中規模のデータセットではうまく動く可能性があるが、非常に大きなデータセットでは遅くなることがある
PostgreSQL検索エンジンの範囲と限界
- PostgreSQLの全文検索コンポーネントを組み合わせれば、かなり高度な検索エンジンを作れる
- PostgreSQLベースの検索は、JOIN と ACIDトランザクション も併せてサポートする
- これは他の検索エンジンが一般には持たない機能
- さらに扱う価値のある高度な検索トピックとして次がある
- サジェストとオートコンプリート
- 正確なフレーズマッチ
pg-vectorと組み合わせたハイブリッド検索
- これらの機能はPostgreSQLでも可能だが、構成要素を自分で組み合わせる必要がある
- 一部のケースでは、非常に大きなデータセットで性能が低下する可能性がある
- 続編の part 2 では、PostgreSQLに検索を実装する場合と、Elasticsearchをインフラに追加してデータを同期する場合を比較している
1件のコメント
Hacker Newsのコメント
Elasticsearchの機能を真似する形でこれをやろうとしてはいけない
2000年代にMySQL 3.xで画像のEXIFデータを解析し、3段階の分類体系とカウントを索引化する検索エンジンを作ったことがあるが、複数の高価なベンダー製品でもまともにできていなかった仕事で、Autonomyは最上位分類すらできなかった
6週間、SELECTのカラム順を変えるだけで性能が変わるような脆いSQLを書いてようやく成功したが、二度とやりたくない。データベースは本質的には大きく変わっていなくても、検索エンジンははるかに進化している
知的好奇心で試すことはできるが、検索は単にトークン化して終わりではない。すぐにカテゴリナビゲーション、多言語、自動同義語、"Did you mean"のスペル提案、大規模性能といった要求が入ってきて、自分で袋小路にはまり込むことになる。精神衛生のためにも検索エンジンを使うほうがよく、PGとESの同期にはZomboDBやPGSyncのようなツールもある
一方で、データアナリストや開発者が大きなデータベースのテキストカラムを
LIKE/ILIKEより柔軟に検索したいだけなら、同じデータベース内に全文検索インデックス/テーブルを作って90%まで持っていくほうが、より簡単で速いこともある第2部のPostgres vs Elasticsearch比較に期待している。うちの会社のあるアプリケーションでは、オブジェクトCRUDはPG、検索はElasticを使っているが、2つのデータストアを同期する手間を完全に過小評価しており、実際にElasticsearchの撤去を検討している
5分ごとにcronが
last_modified_at > last_indexing_started_timestampな索引対象オブジェクトをDBから探し、Elasticsearchに索引した後、last_indexing_started_timestampを同期開始時刻で更新する。そうすると、実行開始から終了までの間に更新されたオブジェクトは次回の実行で拾われるElasticsearchを再構築する必要があれば、最後の索引時刻を空にして最初から再同期すればよく、自己修復が可能になって同期ずれも起きない
非同期ジョブではいつもそうだが、監視とリトライは必要だった。ただESは安定していて速かったので、問題はまれだった。もっとも、一貫性要件が緩く、PGの最新状態が妥当な時間内にESへ届けば十分だったので、要件が違えば話は変わるかもしれない
Postgresの全文検索でインデックスとクエリに重み付けを行う方向へ移した後は、更新トリガーと非常に高速な検索クエリだけで、必要なことをすべてPostgres内で処理できるようになった
全体としては成功で、運用負荷が大幅に減ったため投入したエンジニアリング時間は十分回収できたが、気軽に始めるようなものではない
必要に応じてマテリアライズドビュー、通常のビュー、トリガーのほうが良い場合もある。組み込みのテキスト検索がユースケースに合わないこともあり、代替を作ることが必ずしも難しいとは限らない
現実的な負荷でのp50/p99レイテンシがなければ、実証されたとは言いがたい。結果を1分で返す検索エンジンは「高度」ではなく、Postgresのようなリレーショナルデータベースでも机上ではもちろん可能だ
おおむね同意で、大規模、たとえば数百万レコード以上ではこの方法を使わない可能性が高い。主な関心は、どこまで機能を再現できるかだった
小規模な検索ユースケースでは、維持すべきインフラが少なく、強い整合性やJOINのような利点がある。Xataでは小規模ではPostgresを使い、最小限の破壊的変更でElasticsearchへ移行できる滑らかな移行も検討している
その観点では、速い検索結果自体はそれほど驚くことではない。バックグラウンドジョブでキャッシュ結果を継続的に更新しておき、リクエストが来たらそのまま返せるからだ。こうしたキャッシュと応答時間は、実際の検索結果の計算速度とは別問題に見える
低速な接続を使う人もいるし、地震のような特定の検索語が特定地域でだけ急増することもある
検索語がランダムすぎるとキャッシュに結果がなく実際より悪く出るし、十分にランダムでなければ実際より良く出る
したがって、ESなどの利点は複数ノードにまたがる水平スケーリングや、主インデックスの上に載せる追加機能にある
ts_rankだけ使えば十分なこともあるが、普通は他の関連度指標で順位を補正したくなる。その指標を主順位基準にはできないという点を解決できれば、結果はインデックス付きの通常のDBテーブルクエリと同じくらい高速だ10代のとき、検索エンジンもデータベースもよく分からない状態で、両方をゼロから作ってみた。どこまで行けるのか、どの程度の速さでどの程度関連性のある検索結果を返せるのか見てみたかった
基本的なデータベースや検索エンジンを素早く作るのは、アマチュアプログラマにとってもかなり簡単だ。基礎的なコンピュータサイエンスのアルゴリズムと、OS・ハードウェアの使い方を理解していれば、1〜2か月で作れる
高水準言語でも速度は悪くなく、2003年のノートPCで約 25万 QPS ほどだった。シャーディングすればスケーラビリティも大きな問題ではない。保存と検索よりも、インデックス作成、ロック、一貫性のほうが複雑だ
本当に大きな問題は検索の 主観性 だ。何を本当に探したいのか、自分でも何を探しているのか分からないときにどう見つけるのか、システムを悪用しようとする人をどう防ぐのか、複雑なクエリやデータセットをどう扱うのか、といった話になると難易度は桁違いに上がる
本当に 汎用データベース を使っていて、その数字が正しいのか気になる。こうしたエンジンを上回るためにどんな手法を使ったのか知りたい
それより大きくなると創造的な解決策が必要になり、そこからさまざまなトレードオフが現れる
Postgres 内で検索するときの問題の1つは、検索が CPU を大量に使う処理 だという点で、最近は GPU を使う方向にも進んでいる。理想的には、データベースの CPU はコアデータモデルのトランザクション更新のために残しておきたい
ES や Solr のクラスターが再インデックス中に 10 ノード以上で 100% 稼働したり、平常時でも 10 ノード以上で 30〜50% を使っているケースをよく見てきた。対応するデータベースは、たとえば AWS の L/XL インスタンスで 50〜100GB のデータ、CPU 使用率 30% 程度だったりする
検索用の CPU をすべてメイン DB に移すと、今度は DB をシャーディングしなければならない。それでもサイドプロジェクトでは、検索、再帰結合、ベクトルなどのための PG 拡張 は面白くてシンプルなので良い
以前これを実際にやってみて、かなり高速に作れた
https://austingwalters.com/fast-full-text-search-in-postgres...
現在のウェブサイトは https://askhn.ai
[1]: https://en.wikipedia.org/wiki/Kerning
こうした手法を pgvector と組み合わせれば、埋め込みで関連コンテンツを見つけることもできる。かなり魔法のように感じた
ちなみに "Dark" Vader ではなく Darth Vader だ。自分も子どものころは "Dark" だと思っていた
とても良くて明快な記事だ。SQLite も標準プラグインで 高度なインデックス機能とステミング を提供している
英語であれば SQLite でも十分うまく動く
https://github.com/daitangio/knowledge
一度使ってみるといい。かなり強力だ
良い記事だが、PostgreSQL が あいまい検索 をサポートしていないという部分は一部誤っている。
pg_trgm拡張と GIN トライグラムインデックスは、この記事の例のようなあいまい検索のユースケースをサポートしているhttps://www.postgresonline.com/article_pfriendly/169.html
クエリは大幅に高速化できるが、その代償としてメモリ使用量と更新時の処理時間が増える