Produit

Comprendre « Query Then Fetch » par rapport à « DFS Query Then Fetch »

By
Zachary Tong

Dans notre dernier article sur la correspondance de phrases commençant par, nous avons rencontré une situation où les scores renvoyés étaient suspects. Pour rappel, voici la requête en question :

$ curl -XGET localhost:9200/startswith/test/_search?pretty -d '{
        "query": {
        "match_phrase_prefix": {
           "title": {
             "query": "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"}

Voyez-vous comment le document « drunk » reçoit un score de 1,0, tandis que les autres ont un score de 0,3 ? Ces documents ne devraient-ils pas tous avoir le même score, puisqu'ils correspondent tous de la même manière à la requête « d » ? La réponse est oui, mais il existe une très bonne raison à cet écart de score.

Score de pertinence

Une partie de l'algorithme de score utilisé par Elasticsearch (et Lucene en dessous) inclut des statistiques de « Term Frequency – Inverse Document Frequency » (fréquence des termes – fréquence inverse des documents) pour aider à calculer la pertinence des documents dans l'index.

Beaucoup a été écrit sur le sujet du TF-IDF, mais cela signifie essentiellement : « plus un terme apparaît dans un document, plus ce document est pertinent. Mais la pertinence est atténuée par la fréquence à laquelle le terme apparaît dans l'index entier ».

Les termes rares ne sont présents que dans quelques documents, ce qui signifie que toute requête correspondant à un terme rare devient très pertinente. À l'inverse, les termes courants se trouvent partout, donc leur pertinence par rapport à la requête est faible.

Elasticsearch est confronté à un dilemme intéressant lorsque vous exécutez une recherche. Votre requête doit trouver tous les documents pertinents… mais ces documents sont dispersés sur un nombre quelconque de partitions dans votre cluster.

Chaque partition est essentiellement un index Lucene, qui assure la maintenance de ses propres statistiques TF et DF. Une partition sait seulement combien de fois « pineapple » apparaît au sein du shard, et non dans l'ensemble du cluster.

Mais l'algorithme de pertinence utilise TF-IDF… n'a-t-il pas besoin de connaître la TF et la DF pour l'index entier, et non pour chaque partition ?

Type de recherche par défaut : Query Then Fetch

La réponse est oui et non. Par défaut, Elasticsearch utilisera un type de recherche appelé « Query Then Fetch ». Voici comment cela fonctionne :

  1. Envoyer la requête à chaque partition
  2. Recherchez tous les documents correspondants et calculez les scores à l’aide des fréquences terme/document locales
  3. Construire une file d'attente prioritaire de résultats (tri, pagination avec from/to, etc.)
  4. Renvoie les métadonnées relatives aux résultats au Node demandeur. Notez que le document réel n’est pas encore envoyé, seuls les scores le sont.
  5. Les scores de toutes les partitions sont fusionnés et triés sur le Node demandeur, les documents sont sélectionnés selon les critères de la requête
  6. Enfin, les documents réels sont récupérés à partir des partitions individuelles où ils résident.
  7. Les résultats sont renvoyés au client

Ce système fonctionne généralement bien. Dans la plupart des cas, votre index contient « assez » de documents pour lisser les statistiques de fréquence Terme/Document. Ainsi, bien que chaque partition puisse ne pas avoir une connaissance complète des fréquences dans l’ensemble du cluster, les résultats sont « suffisamment bons » car les fréquences sont assez similaires partout.

Mais dans le cas de notre requête mentionnée au début de cet article, le type de recherche par défaut échoue parfois.

DFS Query Then Fetch

Dans le dernier article, nous avons créé un index sans spécifier le nombre de partitions – Elasticsearch a utilisé la valeur par défaut de 5 partitions. Nous avons ensuite inséré cinq pauvres documents dans l’index et avons demandé à ES de renvoyer des résultats pertinents et des scores précis. Ce n’est pas très juste, n’est-ce pas ?

Les écarts de notation ont été causés par le type de recherche Query Then Fetch. Chaque partition ne contenait qu’un ou deux documents (l’algorithme de hachage utilisé par ES garantit une distribution relativement aléatoire). Lorsque nous avons demandé à Elastic de calculer les scores, chaque partition n’avait qu’une vue très limitée de l’index de cinq documents… les scores étaient donc inexacts.

Heureusement, Elasticsearch ne vous laisse pas tomber. Si vous vous trouvez dans une situation où cet écart de notation est problématique, ES propose un type de recherche appelé « DFS Query Then Fetch ». La procédure est presque identique à Query Then Fetch, à l’exception près qu’elle effectue une pré-requête pour calculer les fréquences globales des documents.

  1. Interroger au préalable chaque partition pour obtenir les fréquences des termes et des documents
  2. Envoyer la requête à chaque partition
  3. Rechercher tous les documents correspondants et calculer les scores à l'aide des fréquences globales des termes/documents calculées à partir de la pré-requête.
  4. Construire une file d'attente prioritaire de résultats (tri, pagination avec from/to, etc.)
  5. Renvoie les métadonnées relatives aux résultats au Node demandeur. Notez que le document réel n’est pas encore envoyé, seuls les scores le sont.
  6. Les scores de toutes les partitions sont fusionnés et triés sur le Node demandeur, les documents sont sélectionnés selon les critères de la requête
  7. Enfin, les documents réels sont récupérés à partir des partitions individuelles où ils résident.
  8. Les résultats sont renvoyés au client

Si nous appliquons ce nouveau type de recherche à notre requête précédente, nous obtenons des résultats de score cohérents (par exemple, ils sont tous identiques) :

$ curl -XGET 'localhost:9200/startswith/test/_search?pretty=true&search_type=dfs_query_then_fetch' -d '{
        "query": {
        "match_phrase_prefix": {
           "title": {
             "query": "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"}

Conclusion

Bien entendu, une meilleure précision a un coût. La pré-requête entraîne un aller-retour supplémentaire entre les partitions, ce qui peut nuire aux performances en fonction de la taille de l'index, du nombre de partitions, du taux de requêtes, etc. Dans la plupart des cas, c'est totalement inutile… disposer d'« assez » de données résout le problème pour vous.

Mais il arrive parfois que vous soyez confronté à des situations de scoring étranges ; dans ces cas-là, il est utile de savoir comment ajuster le plan d'exécution de recherche avec DFS Query then Fetch.