Mon premier article porte sur la recherche géospatiale et sa mise en pratique avec Elasticsearch.
Mais d’abord, commençons par voir ce qu’est un moteur d’indexation.
Qu’est ce que Elasticsearch?
Elasticsearch est un moteur d’indexation.
Tout le monde sait ce qu’est un moteur de recherche, par exemple celui de Google.
Et bien un moteur de recherche est composé d’un moteur d’indexation où l’on indexe des pointeurs (url) vers du contenu externe (pages web).
Le moteur d’indexation peut aussi servir à indexer du contenu et à le servir directement.
Mais en général, il sert à indexer ce qu’on appelle des « ressources » qu’il ne stocke ni ne gère.
Par exemple pour des images ou des documents, on peut indexer les métadonnées (titre, auteur, date, etc…) sous forme de json ou de xml.
Les avantages sont de décharger la base de données qui se concentrera sur la persistance de données nécessitant du transactionnel et/ou du relationnel.
Ensuite cela permet de faire de la recherche full text, approximative ou approchante avec des scores sur la pertinence, du facetting, etc…
Un lien avec une autre explication :
Le moteur d’indexation-recherche (par Smile)
Un autre lien intéressant qui explique la problématique et les solutions retenues sur des sites web grand publique à forte charge :
ApéroTech #6 : Les moteurs d’indexation – Compte rendu
On y retrouve entre autre Elasticsearch et on voit au passage que l’on retrouve également Redis et RabbitMQ qui feront sûrement l’objet d’un autre article prochainement.
Qu’est ce qu’une recherche géospatiale?
Une recherche géospatiale cumule les mêmes critères de recherche classique avec en plus des critères géospatiales.
C’est à dire :
- soit une position (coordonnées GPS, position de l’utilisateur par exemple), un ordre de tri (du plus proche au plus éloigné ou l’inverse) et en option une limite (par exemple 10km autour). Le résultat peut être paginé avec 100, 1000, 5000 ou plus de résultats par page.
- soit une zone délimitée définie par exemple par les coordonnées du point en haut à gauche et du point en bas à droite. On appelle cela une « bounding box ». Ca sert par exemple à afficher sur une carte les positions des « documents » indexés en fonction du niveau de zoom et de ce que regarde réellement l’utilisateur sur la carte.
Quand l’utilisateur déplace la carte ou change le niveau de zoom, on fait en asynchrone des requêtes paginées vers le serveur pour afficher petit à petit l’ensemble des points.
Attention à la limite du nombre de positions affichables sur une carte dézoomée complétement (monde entier). Ceci fera également l’objet d’un autre article, concentrons nous sur la partie backend pour le moment.
Mise en pratique
Indexation de documents localisés
Pour indexer un document dans Elasticsearch, ça se fait en un appel REST.
Un document dans Elasticsearch doit être au format JSON, mais ça peut aussi être un méta-document ne contenant que les méta-données ou bien le document lui même est dans l’un des méta-champs. Dans le cas de binaire, comme une image par exemple, soit on stocke un lien vers le fichier stocké ailleurs, soit on l’inclut mais dans ce cas il faut l’encoder (en base 64 par exemple).
Pour géolocaliser un document, il faut lui rajouter un champs « location » de type geo_point qui contiendra la position GPS du document.
En fait le champ peut s’appeler comme on veut, l’important est de faire un mapping explicite car le mapping dynamique ne se fait pas automatiquement sur le type geo-point.
PUT /attractions
{
"mappings": {
"restaurant": {
"properties": {
"name": {
"type": "string"
},
"location": {
"type": "geo_point"
}
}
}
}
}
Voici le mapping pour indexer un restaurant avec son nom et sa localisation.
Maintenant, voici 3 exemples d’indexation de document pour ce mapping en utilisant les différents formats acceptés pour le type geo_point :
PUT /attractions/restaurant/1
{
"name": "Chipotle Mexican Grill",
"location": "40.715, -74.011"
}
PUT /attractions/restaurant/2
{
"name": "Pala Pizza",
"location": { "lat": 40.722, "lon": -73.989 }
}
PUT /attractions/restaurant/3
{
"name": "Mini Munchies Pizza",
"location": [ -73.983, 40.719 ]
}
Attention, dans le cas du format tableau (le 3ème exemple) c’est longitude puis latitude, donc l’ordre inverse des deux autres formats.
C’est ainsi pour respecter le standard geojson.
A partir de là, on va pouvoir faire des recherches sur nos documents, des restaurants dans notre exemple.
On va donc pouvoir faire une recherche full text, par exemple les restaurants dont le nom contient le mot « pizza ».
On va aussi pouvoir chercher les restaurants selon une recherche géospatiale.
On va aussi pouvoir combiner les deux et en plus demander un résultat facetté / agrégé, tout en ne demandant que les 10 premiers afin de faire de la pagination.
Recherche géospatiale
Une recherche dans Elasticsearch est composée de filtres.
Nous avons plusieurs types de filtres géospatiales à notre dispositions :
- geo_bounding_box : recherche les positions à l’intérieur d’un rectangle dont on passe les coordonnées en haut à gauche et en bas à droite
Voir la doc pour l’optimisation de l’index pour ce cas de recherche :
https://www.elastic.co/guide/en/elasticsearch/guide/current/geo-bounding-box.html - geo_distance : recherche les positions qui sont à moins d’une certaine distance d’une coordonnée GPS centrale passée dans la requête
Ca revient à chercher les positions comprises dans un cercle.
La doc nous conseille de privilégier si possible le rectangle plutôt que le cercle car c’est beaucoup plus efficace.
Néanmoins, en passant par ce filtre, Elasticsearch réalise tout seul un préfiltre en calculant le rectangle dans lequel s’inscrit le cercle pour éliminer un maximum de document et limiter le calcul de distance sur un minimum de document car c’est ce qui est coûteux.
L’autre optimisation possible est sur le choix de l’algo pour calculer la distance. Si on n’a pas besoin d’être hyper précis, d’autant si la position elle même n’est pas très précise, on peut prendre l’algo le plus rapide qui considère que la terre est plate.
Le plus précis considère la terre sphérique et un autre algo est intermédiaire et précis dans 99.9% des cas. C’est ce dernier algo qui est sélectionné par défaut.
https://www.elastic.co/guide/en/elasticsearch/guide/current/geo-distance.html - geo_distance_range : c’est la même chose que le filtre geo_distance mais avec une distance minimum et une distance maximum.
- geo_polygon : le plus coûteux des filtres, recherche les positions incluses dans un polygon. La doc conseille de passer par les geo_shapes qui eux utilisent l’ensemble des geohash inclus dans le polygon.
https://www.elastic.co/guide/en/elasticsearch/guide/current/geo-shapes.html
Les filtres géospatiales étant coûteux en terme de performance, la doc conseille de les mettre en dernier critère et de faire passer devant les autres critères comme les filtres « term » ou « range ».
Encore une optimisation est possible en préparant un cache sur une région désignée par un geo_bouding_box.
https://www.elastic.co/guide/en/elasticsearch/guide/current/geo-caching.html
Si par exemple dans notre Elasticsearch nous avons indexé des positions sur la planète entière et que pour certains utilisateurs nous savons qu’ils sont en France voir même dans la région Ile de France, nous pouvons appliquer un préfiltre de mise en cache sur un bounding box couvrant cette région.
Du coup, toutes les recherches « à moins d’1 km de la position de l’utilisateur » se feront sur le résultat du préfiltre mis en cache.
Et une dernière optimisation est possible en réduisant la place mémoire que prend une position au détriment de sa précision.
Chaque position prend 16 octets en mémoire pour la latitude et la longitude.
On peut réduire cette taille de 62% en prenant une précision de 3m et de 75% en prenant une précision de 1km.
https://www.elastic.co/guide/en/elasticsearch/guide/current/geo-memory.html
Tri du résultat de la recherche
Elasticsearch permet de trier le résultat par distance du plus proche au plus éloigné et le contraire.
Dans ce cas, la distance calculée est donnée avec l’unité de mesure choisie. Par exemple le mètre ou le km.
https://www.elastic.co/guide/en/elasticsearch/guide/current/sorting-by-distance.html
L’autre façon de trier est par le scoring (note évaluant la pertinence du résultat). Et la distance peut être l’un des critères pour calculer le score.
https://www.elastic.co/guide/en/elasticsearch/guide/current/function-score-query.html
Exemple : recherche des positions présentes dans un rectangle (bounding box) par ordre d’éloignement d’une position donnée dans la requête
GET /attractions/restaurant/_search
{
"query":
{
"filtered":
{
"filter":
{
"geo_bounding_box":
{
"type": "indexed",
"location":
{
"top_left": { "lat": 40.8, "lon": -74.0 },
"bottom_right": { "lat": 40.4, "lon": -73.0 }
}
}
}
}
},
"sort":
[
{
"geo_distance":
{
"location": { "lat": 40.715, "lon": -73.998 },
"order": "asc",
"unit": "km",
"distance_type": "plane"
}
}
]
}
distance_type à la valeur « plane » indique d’utiliser l’algo le moins précis mais le plus performant. La distance calculée sera donc approximative.
Géo-aggrégations
Elasticsearch permet d’agréger les résultats. Sur une requête géospatiale, il y a trois types d’agrégation :
- geo_distance : groupe les résultats dans des cercles concentriques autour d’un point central
https://www.elastic.co/guide/en/elasticsearch/guide/current/geo-distance-agg.html - geohash_grid : groupe les résultats dans des cellules géohash afin d’être affichés sur une carte
https://www.elastic.co/guide/en/elasticsearch/guide/current/geohash-grid-agg.html - geo_bounds : retourne les coordonnées du plus petit rectangle (bound) qui permet d’afficher tous les résultats. Cela permet de choisir le bon niveau de zoom sur la carte en évitant d’afficher des zones vides
https://www.elastic.co/guide/en/elasticsearch/guide/current/geo-bounds-agg.html
Conclusion
Voilà, nous avons fait le tour des principales fonctionnalités géospatiales d’Elasticsearch.