プロダクト

「Query Then Fetch」と「DFS Query Then Fetch」の違いを理解する

By
Zachary Tong

前回の「starts-with」フレーズマッチングに関する記事では、返されたスコアが疑わしい状況に遭遇しました。復習として、問題のクエリを以下に示します。

$ curl -XGET localhost:9200/startswith/test/_search?pretty -d '{
        "query": {
        "match_phrase_prefix": {
           "title": {
             "クエリ": "d",
             "max_expansions": 5
           }
         }
       }
     }' | grep title

      "_score" : 1.0, "_source" : {"title":"drunk"}
      "_score" : 0.30685282, "_source" : {"title":"dzone"}
      "_score" : 0.30685282, "_source" : {"title":"data"}
      "_score" : 0.30685282, "_source" : {"title":"drive"}

ドキュメント「drunk」のスコアが1.0であるのに対し、残りのスコアが0.3であることに注目してください。これらはすべて「d」のクエリに等しく一致しているため、同じスコアになるべきではないでしょうか？答えはイエスですが、このスコアの不一致には非常に正当な理由があります。

関連性スコアリング

Elasticsearch（およびその基盤となるLucene）で使用されるスコアリングアルゴリズムの一部には、インデックス内のドキュメントの関連性を計算するのに役立つ「Term Frequency – Inverse Document Frequency（TF-IDF：単語頻度 - 逆文書頻度）」統計が含まれています。

TF-IDFについては多くの文献がありますが、基本的には「あるドキュメントに単語が多く出現するほど、そのドキュメントの関連性は高くなる。しかし、その単語がインデックス全体にどれだけ頻繁に出現するかによって、関連性は抑制される」というものです。

希少な単語は少数のドキュメントにしか存在しないため、希少な単語に一致するクエリは関連性が非常に高くなります。逆に、一般的な単語はどこにでも見つかるため、クエリに対する関連性は低くなります。

Elasticsearchは、検索を実行する際に興味深いジレンマに直面します。クエリはすべての関連ドキュメントを見つける必要がありますが、これらのドキュメントはクラスター内の多数のシャードに分散しています。

各シャードは基本的にLuceneインデックスであり、独自のTFおよびDF統計を保守しています。シャードは、クラスター全体ではなく、そのシャード内で「pineapple」が何回出現するかしか知りません。

しかし、関連性アルゴリズムはTF-IDFを使用しています。各シャードではなく、インデックス全体のTFとDFを知る必要があるのではないでしょうか？

デフォルトの検索タイプ：Query Then Fetch

答えはイエスでもありノーでもあります。デフォルトでは、Elasticsearchは「Query Then Fetch」と呼ばれる検索タイプを使用します。その仕組みは以下の通りです：

  1. 各シャードにクエリを送信する
  2. 一致するすべてのドキュメントを検索し、ローカルの用語/ドキュメント頻度を使用してスコアを計算します
  3. 結果の優先度キューを構築する（並べ替え、from/toを使用したページネーションなど）
  4. リクエスト元のNodeに結果に関するメタデータを返します。注：実際のドキュメントはまだ送信されず、スコアのみが送信されます
  5. すべてのシャードからのスコアがリクエスト元のNodeでマージおよびソートされ、クエリの条件に従ってドキュメントが選択されます
  6. 最後に、実際のドキュメントが格納されている個々のシャードから取得されます。
  7. 結果がクライアントに返されます

このシステムは通常、問題なく動作します。ほとんどの場合、インデックスには用語やドキュメントの頻度統計を平滑化するのに「十分な」ドキュメントが含まれています。そのため、各シャードがクラスター全体の頻度を完全に把握していなくても、頻度はどこでもかなり似通っているため、結果は「十分な精度」となります。

しかし、この記事の冒頭で述べたクエリの場合、デフォルトの検索するタイプでは失敗することがあります。

DFS Query Then Fetch

前回の記事では、シャード数を指定せずにインデックスを作成しました。Elasticsearchはデフォルトの5シャードを使用しました。その後、わずか5つのドキュメントをインデックスに挿入し、関連性の高い結果と正確なスコアを返すようESに要求しました。これでは少し不公平ですよね？

スコアリングの不一致は、「Query Then Fetch」検索するタイプが原因でした。各シャードには1つか2つのドキュメントしか含まれていませんでした（ESで使用されるハッシュアルゴリズムにより、比較的ランダムな分散が保証されます）。Elasticにスコアの計算を要求した際、各シャードは5つのドキュメントからなるインデックスのほんの一部しか認識していなかったため、スコアが不正確になってしまったのです。

幸いなことに、Elasticsearchはユーザーを見捨てません。このようなスコアリングの不一致が問題となる状況では、ESは「DFS Query Then Fetch」と呼ばれる検索するタイプを提供しています。その手順は「Query Then Fetch」とほぼ同じですが、グローバルなドキュメント頻度を計算するための事前クエリを実行する点が異なります。

  1. 各シャードに対して用語頻度と文書頻度を事前にクエリする
  2. 各シャードにクエリを送信する
  3. 事前クエリから計算されたグローバルな単語/ドキュメント頻度を使用して、一致するすべてのドキュメントを検索し、スコアを計算します。
  4. 結果の優先度キューを構築する（並べ替え、from/toを使用したページネーションなど）
  5. リクエスト元のNodeに結果に関するメタデータを返します。注：実際のドキュメントはまだ送信されず、スコアのみが送信されます
  6. すべてのシャードからのスコアがリクエスト元のNodeでマージおよびソートされ、クエリの条件に従ってドキュメントが選択されます
  7. 最後に、実際のドキュメントが格納されている個々のシャードから取得されます。
  8. 結果がクライアントに返されます

この新しい検索するタイプを前述のクエリに適用すると、妥当なスコアリング結果が得られます（例：すべて同一の結果になる）。

$ curl -XGET 'localhost:9200/startswith/test/_検索する?pretty=true&検索する_type=dfs_query_then_fetch' -d '{
        "query": {
        "match_phrase_prefix": {
           "title": {
             "クエリ": "d",
             "max_expansions": 5
           }
         }
       }
     }' | grep title

      "_score" : 1.9162908, "_source" : {"title":"dzone"}
      "_score" : 1.9162908, "_source" : {"title":"data"}
      "_score" : 1.9162908, "_source" : {"title":"drunk"}
      "_score" : 1.9162908, "_source" : {"title":"drive"}

結論

もちろん、精度の向上には代償が伴います。プリクエリはシャード間で追加のラウンドトリップを発生させるため、インデックスのサイズ、シャード数、クエリレートなどに応じてパフォーマンスに影響を与える可能性があります。ほとんどの場合、これはまったく不要であり、「十分な」データがあれば問題は解決します。

しかし、奇妙なスコアリング状況を実行することもあり、そのような場合には、DFS Query then Fetchを使用して検索する実行計画を調整する方法を知っておくと便利です。