Version du 27 février 2016 à 00:28

La requête jdonrefv4 du plugin éponyme permet de chercher efficacement des adresses correspondant aux types de JDONREFv4.

Requête et résultat

 {
   "query": {
     "jdonrefv4" : {
        "value" : "24 BOULEVARD DE L HOPITAL 75 PARIS"
     }
   }
 }

Il s'agit d'une requête multi-termes. Ils sont décrit dans la page traitant des index.

Avec une requête POST du type :

 curl -XPOST 'http://localhost:9200/jdonref/_search' -d '{
   "query": {
     "jdonrefv4" : {
       "value" : "24 BOULEVARD DE L HOPITAL 75005 PARIS"
     }
   }
 }'

le résultat est de la forme :

 {
   "_shards":{
       "total" : 5,
       "successful" : 5,
       "failed" : 0
   },
   "hits":{
       "total" : 1,
       "hits" : [
           {
               "_index" : "jdonref",
               "_type" : "adresse",
               "_id" : "1",
               "_score" : 200.0,
               "_source" : {
                   "adr_id" : "123456789X",
                   "code_insee" : "75105",
                   "code_departement": "75",
                   "numero" : "24",
                   "type_de_voie" : "BOULEVARD",
                   "article" : "DE L",
                   "libelle" : "HOPITAL",
                   "commune" : "PARIS",
                   "code_postal" : "75005",
                   "ligne4": "24 BOULEVARD DE L HOPITAL",
                   "ligne6": "75005 PARIS",
                   "ligne7": "FRANCE",
                   "geometrie": { "type" :"point", "coordinates": [123, 456] }
               }
           }
       ]
   }
 }

Les types "voie", "commune", "departement", "pays" peuvent aussi être retournés. Les coordonnées sont en WGS84 par défaut dans la version 0.2, une version ultérieure permettra de le transformer à la volée en Lambert 93.

Filtres

Il est possible de la combiner avec des filtres, par exemple pour limiter les résultats à un département précis :

 {
   "filtered" : {
     "query": {
       "jdonrefv4" : {
         "value" : "24 BOULEVARD DE L HOPITAL 75 PARIS"
       }
     },
     "filter": {
       "term" : { "code_departement" : "75" }
     }
   }
 }

Ou de restreindre la recherche à une zone géographique :

 {
   "filtered" : {
     "query": {
       "jdonrefv4" : {
         "value" : "24 BOULEVARD DE L HOPITAL 75 PARIS"
       }
     },
     "filter" : {
       "geo_shape": {
          "geometrie" : {
            "shape" : {
               "type" : "enveloppe",
               "coordinates": [[13,53],[14,52]]
            }
          }
       }
     }
   }
 }

Fonctionnement

JDONREFv4Query s'appuie sur un mélange de multiples sous-requêtes et de mécanismes de scoring.

Les sous-requêtes sont constituées :

1. de chacun des tokens saisis pour chacun des termes cherchés
2.  sont spécifique à chaque index (adresse, voie, ...)
3. évoluent au fil de la requête. Une requête très permissive est d'abord effectuée, puis moins permissive, puis encore moins ...

Le score est influencé par plusieurs éléments :

1. la présence de plusieurs termes identiques
2. l'absence de termes dans le document (notamment la repetition)
3. divisé par le score maximum possible pour un document

J'explique ces choix dans le détail.

Elasticsearch (tout comme lucene) fourni un outil manipulant des index inversés. Ce qui est très efficace lorsque le scoring s'appuie sur la somme des notes associées au termes cherchés. Pour être très simplificateur, l'algorithme consiste alors à faire la somme des valeurs d'un tableau. Néanmoins, un tableau de 5 000 éléments reste différent d'un tableau de 5 000 000 d'éléments, et le parcourir est généralement 1000 fois plus long. Suivant la fréquence des termes, il est facile de voire passer une requête de 1ms à 1s.

Deux principes ont alors été appliqués à notre requête :

1. utiliser des filtres efficaces pour limiter la taille des tableaux
2.  faire évoluer la requête en cours de calcul

Des filtres efficaces

Le premier point est facile à comprendre. Je prends un exemple. Une recherche sur une adresse n'a pas de sens si le numéro n'est pas saisi. Dans le cas contraire, la recherche d'une voie serait encombrée de l'ensemble des adresses de cette voie ! Peut-être que quelques numéros sont pertinents, mais certainement pas tous. Un exemple de filtre efficace est alors, uniquement pour les adresses, d'imposer le numéro.

Comment imposer un numéro pour une adresse ? Le meilleur endroit est au niveau du parser de la requête. A ce niveau, nous pouvons détecter l'index sur lequel la requête est en cours d'exécution et adapter la requête en conséquence. Il aurait aussi été possible de modifier la requête dans la requête elle-même, au niveau de sa réécriture (rewrite). Mais quitte à être modifiée, autant la modifier le plus tôt possible. Dans le code, c'est

 if (matchesIndices(parseContext.index().name(), "*adresse*")
               && terms.stream().filter((i)->isInteger(i)).count()>0    // au moins un numéro dans la requête
               && terms.size()>1)                                       // et deux éléments saisis

Les types suivant ne sont ainsi retournés en résultat que lorsque les filtres spécifiés sont vérifiés :

Changer de requête en cours de calcul

L'influence sur le score

Les filtres qui sont décrit ici n'apporte rien en terme de performances, et peuvent être potentiellement challengés si des solutions plus efficaces existent. Il s'agit uniquement de mettre les documents dans le bon ordre, ou de filtrer les résultats.

Elasticsearch comme lucene ne permettent pas de savoir si une répétition est présente ou pas dans le document sous forme de requête. En effet, la requête générée consiste à chercher les documents qui ne matchent aucun des termes présent dans l'index ! Ce n'est efficace que pour un nombre réduit de valeurs. Mais les répétitions sont une trentaine (les lettres plus les versions longues). Le challenge, c'est de savoir identifier si la requête n'a pas matché une répétition mais que le document en a une. Le type de chaque sous-requête étant connu, il est simple de faire la liste des types qui ont matché. Le code suivant est alors utilisé dans le Scorer de la requête :

 if (((getTypeMask()&2)==0) && isRepetitionInDoc(doc))
               this.score = 0;

Il est facile de savoir si un terme saisi n'a pas été trouvé dans le document. Et d'influencer le score en conséquence. C'est fait ainsi :

               this.score *= ((ICountable)innerScorer).count();
               this.score /= this.maxCoord;

Mais il est plus difficile de savoir combien de termes dans le document aurait pu être trouvés pour influencer le score. Par exemple, par défaut, elasticsearch (comme lucene) retourne le même score pour la recherche

 9 BD PALAIS

sur les documents

 9 BD PALAIS
 9 BD PALAIS ROYAL

car seul les termes saisis ont une influence sur le code. J'ai testé deux méthodes :

1. associer des payloads aux termes pour fournir l'information manquante (par exemple le nombre de termes)
2. utiliser la valeur d'un autre terme

La première méthode prend beaucoup de place mémoire, et ralenti le processus. Les deux méthodes nécessitant un précalcul, je me suis tourné vers la deuxième, plus légère. Le terme choisi est un champ "score". Il contient le score maximal à laquelle une recherche peut aboutir pour un document. Il s'agit d'un choix. Le numéro vaut 30. La répétition vaut 30. Un toke de libelle 50. etc ... Pour que l'absence d'un terme dans la requête influence le score, on prend le total, on le divise par le score du document, ... et c'est tout. Ainsi, si le score des documents est :

 9 BD PALAIS => 100
 9 BD PALAIS ROYAL => 150

et que la recherche aurait conduit au score :

 9 BD PALAIS => 100

Les résultats pour chaque document deviennent :

 9 BD PALAIS => 100 %
 9 BD PALAIS ROYAL => 66 %

et le premier document a maintenant un meilleur score.

Par défaut, elasticsearch (et lucene) privilégient les documents dans lequel le terme cherché apparaît plusieurs fois. C'est très gênant pour les adresses. De nombreuses adresses disposent d'un terme présent à la fois dans le libellé et dans le nom de commune par exemple. Il faudrait déjà savoir que le terme est trouvé plusieurs fois ! Pour chaque sous-requête est alors stocké le token correspondant. Lorsque 1 même token matche 2 sous-requête pour un même document, une défausse de point est effectué. Cela prend cette forme dans le code :

 this.score -= countBits(multiTokenMatch())*20;

Exemples de calcul en mode bulk

Les exemples qui suivent ne sont pas exhaustifs mais présentent le comportement recherché par la requête en mode bulk. La note donnée ici est indicative, car en réalité elle s'appuie sur la fréquence des termes recherchés et trouvés, suivant la logique du moteur à indexation inverse.

Ces exemples ne présentent pas la prise en compte de la phonétique, qui n'intervient pas dans la notation. Deux requêtes qui disposent de la même phonétique ont les mêmes résultats.

Changer de champ pour la recherche

Si vous avez personnalisé votre mapping, il vous est peut-être nécessaire de modifier le champ utilisé par défaut pour la recherche. Il s'agit d'utiliser le paramètre default_field. Par défaut, il vaut fullName, mais vous pouvez le modifier. Attention à ce que votre champ contienne bien les payloads attendus par les checkers de la requête.

{
  "query": {
    "jdonrefv4" : {
       "value" : "24 BOULEVARD DE L HOPITAL 75 PARIS",
       "default_field" : "fullName"
    }
  }
}

Optimisation

Si vous avez réparti vos types sur de multiples index (ce qui est conseillé pour les communes, pays et départements qui nécessite un sharding de 1 pour éviter les effets de bords voir getting started), le paramètre "maxSizePerType" vous permettra de filtrer les requêtes sur les adresses ou les voies qui seraient en trop grand nombre. Par exemple, une requête comme

 {
   "query": {
     "jdonrefv4" : {
        "value" : "RUE"
     }
   }
 }

retourne un très grand nombre de documents sur l'ensemble des index. Dans la France entière, il y a environ 695 000 documents qui disposent du terme 'RUE'. La requête prend alors environ (sur mon environnement de test) 2 minutes de calcul, même une fois en cache. Ces performances sont liées au très grand nombre de document à parcourir et à traiter avant de retourner le résultat. Toutefois, il existe des pays et des communes correspondant à ce terme, et il pourrait être utile d'obtenir ces réponses !

Si vous avez segmenté vos types par index, la requête :

 {
   "query": {
     "jdonrefv4" : {
        "value" : "RUE",
        "maxSizePerType": 10000
     }
   }
 }

ne retournera pas les résultats de type "adresse", ni même ceux de type "voie" dont la quantité est supérieure à 50000 (avec 5 shards, tout dépend de l'organisation de vos index). Seuls les pays et communes seront alors retournées, en quantité raisonnable.

Dans une requête multi-terme, c'est la fréquence du terme le moins fréquent qui est pris en compte.

J'insiste sur le fait que ce paramètre n'est valable que si les types sont répartis sur plusieurs index. Lorsqu'ils sont dans le même index, la requête n'est pas en mesure de faire la différence entre les types de manière efficace.

Effets de bord

Les exemples présentés ci-dessus induisent nécessairement des effets de bords compréhensibles sur certaines recherches.

Par exemple :

1. Il ne faut pas s'attendre à trouver comme meilleur résultat l'avenue de France en effectuant une recherche sur le seul mot clé "FRANCE". C'est bien entendu le pays qui aura la meilleure note ...