La recherche plein texte avec Postgresql

J'aime Postgresql, le moteur de base de données le plus ennuyeux au monde. Une technologie tellement fiable et éprouvée que tous les cool kids essayent absolument de la remplacer par autre chose. Pourtant, Postgres offre tellement d'avantages que tout projet qui ne s'appuie pas dessus me semble de facto suspect. Aujourd'hui, nous allons passer en revue l'un des aspects offert par Postsresql : ses fonctionnalités de recherche.

Depuis environ une année, je participe au développement du site Aides-territoires dans le cadre d'une prestation pour la Fabrique Numérique. Aides-territoires est un catalogue / moteur de recherche permettant aux collectivités de trouver des aides de différents types et proposées par divers porteurs pour des projets d'aménagement du territoire. Le code source est entièrement public.

Toutes choses étant égales par ailleurs, Aides-territoires est un site assez classique et ne représente pas un défi technique majeur. La stack technique est donc relativement élémentaire. La partie applicative backend est gérée en Python / Django. La base de données est gérée par Postsresql. Le déploiement se fait via Ansible. Le frontend utilise Bootstrap dans sa version Sass. Aucun framework js n'est utilisé pour le moment.

La recherche plein texte

Le cœur du site est constitué d'un moteur de recherche multi-critères. Nous allons nous intéresser à l'un de ces champs en particulier : la recherche plein texte (fulltext en bon anglais). La recherche plein texte permet de trouver des aides en fonction de leur contenu textuel ; par exemple, si je suis le maire de ma commune et que j'ai un projet de création d'une station d'épuration, je vais saisir les termes « épuration traitement » et trouver les aides qui contiennent ces termes dans le titre, la description, les mots-clés, etc.

Une approche naïve pourrait consister à effectuer une requête SQL classique à base d'expression régulière. Avec l'ORM de Django, la syntaxe serait la suivante :

q_title = Q(title__icontains='épuration')
q_description = Q(description__icontains='épuration')
aids = Aid.object.filter(q_title | q_description)

Avec pour résultat la requête sql suivante :

SELECT *
FROM aids_aid
WHERE title ILIKE '%épuration%'
OR description ILIKE '%épuration%'

Telle méthode est douloureusement sous-optimale :

elle est catastrophique d'un point de vue des performances ;
elle ne permet pas de trier les résultats par pertinence (parce qu'une aide qui contiendra le terme de recherche dans le titre sera probablement plus pertinente qu'une autre qui contient le terme au fin fond de la description) ;
elle ne permet pas de gérer les erreurs de saisies (si je tape « épuraton » ou « epuration », je n'obtiendrai aucun résultat) ;
elle ne permet pas de proposer des mécanismes avancés comme les synonymes (si je tape « épuration », je voudrais aussi les aides qui contiennent les termes « épurer », « épurations », « station de traitement », etc.)
etc.

Il existe de nombreux outils dédiés qui offrent des fonctionnalités de recherche avancée : Solr, Elasticsearch, etc. Toutefois, (trop) peu de gens savent que Postsqresql propose également de outils de recherche, avec l'énorme avantage de ne pas avoir besoin d'alourdir sa stack technique.

Par ailleurs, ces fonctionnalités sont remarquablement encapsulées par l'ORM de Django.

Le modèle de données

Voici le modèle de données simplifié à partir duquel nous allons travailler.

class Aid(models.Model):
    name = models.CharField(
        _('Name'),
        max_length=256,
        blank=False)
    description = models.TextField(
        _('Short description'),
        blank=False)
    tags = ArrayField(
        models.CharField(max_length=50, blank=True),
        verbose_name=_('Tags'),
        default=list,
        size=16,
        blank=True)

Documents et requêtes

La documentation de Postsqresql est en général très complète et bien conçue, et les fonctionnalités de recherche plein-texte sont très bien expliquées.

Dans le cadre des requêtes qui font intervenir de la requête plein texte, Postsqresql utilise deux types d'objets : des tsvector et tsquery.

Un tsvector est un objet qui permet de représenter du texte de manière à faciliter la recherche.

SELECT to_tsvector('french', 'Aide à la construction de stations d''épuration | Aides aux collectivités');
-----------------------------------------------------------
 'aid':1,9 'collect':11 'construct':4 'station':6 'épur':8

Avec cette commande sql, je créé un objet tsvector permettant d'indexer un texte saisi manuellement : « Aide à la construction de stations d''épuration | Aides aux collectivités », qui pourrait très bien être le titre d'une aide existante.

La fonction to_tsvector effectue les actions suivantes :

le texte est découpé en tokens, c'est à dire en terme individuels ;
en fonction de leur type, les tokens sont normalisés en lexemes — par exemple, les termes « Aide » et « aides » sont normalisés sous une forme unique « aid » ; le terme « collectivité » est normalisé en « collect », etc.
les termes trop communs pour être pertinents comme « à », « le », « de », etc. sont supprimés (stop words) ;
les différents lexemes sont triés et reçoivent un index qui permet de connaître leurs positions dans le document.

Dans la mesure ou ces opérations sont spécifiques à la langue du document (on n'utilise pas les même suffixes ni les mêmes stop words en français ou en anglais), on passe la langue en paramètre à la fonction to_tsvector.

Un tsquery représente une requête de recherche : des termes liés entre eux via des opérateurs booléens (ou, et, etc.). Pour optenir un tsquery à partir d'un texte non formatté, on utilise la méthode plainto_tsquery.

SELECT plainto_tsquery('french', 'station d''épuration');
--------------------
 'station' & 'épur'

On constate que le traitement est un peu similaire : la requête est découpée en tokens, épurée de ses stop words, les tokens sont normalisés en lexemes.

Pour vérifier qu'une tsquery correspond à un tsvector, on utilise l'opérateur @@.

SELECT to_tsvector('french', 'Aide à la construction de stations d''épuration | Aides aux collectivités') @@ plainto_tsquery('french', 'station d''épuration');
----------
 true

SELECT to_tsvector('french', 'Aide à la construction de stations d''épuration | Aides aux collectivités') @@ plainto_tsquery('french', 'gratin à la fourme d''ambert');
----------
 false

Recherche dans des documents

On veut en général effectuer une recherche dans du contenu existant. On va donc générer des objets tsvector à la volée.

aides=# SELECT id, name from aids_aid where to_tsvector('french', name || description) @@ plainto_tsquery('french', 'épuration');
  id  |                                                                    name                                                                    
------+--------------------------------------------------------------------------------------------------------------------------------------------
  448 | Dépollution des rejets urbains par temps de pluie – Collectivités
  430 | Études spécifiques – Épuration
  450 | Assainissement non collectif - Etudes
  432 | Création et modernisation d’ouvrages collectifs de traitement
  433 | Réhabilitation d’anciens sites d’épuration par épandage d'eaux usées brutes
  503 | H2Indus - Appel à Projets - Investissements d’Avenir - Production et fourniture d'hydrogène décarboné pour des consommateurs industriels -
  675 | Aide - Innover dans les stations de traitement des eaux usées
  673 | Aide - Accompagner les actions d'adaptation au changement climatique, y compris l'innovation
 2302 | Appel à Projets - Investissements d’Avenir - Production et fourniture d'hydrogène décarboné pour des consommateurs industriels
(9 rows)

On demande à Postsresql de nous afficher l'id et le titre de toutes les aides dont le nom et la description correspondent à la requête « épuration ».

L'ORM de Django nous offre un accès direct à ce type de recherche.

from django.contrib.postgres.search import SearchVector, SearchQuery

aids = Aid.objects \
    .annotate(search_vectory=SearchVector('name', 'description', config='french')) \
    .filter(search_vector=SearchQuery('épuration', config='french'))

Indexation des `tsvector`

Il n'est pas très intelligent de re-générer les objets tsvector à chaque requête. Au lieu de ça, nous allons stocker ce champ dans un attribut dédié.

Dans Django, nous allons ajouter ce champ au modèle :

from django.contrib.postgres.search import SearchVectorField

class Aid(models.Model):
    …
    search_vector = SearchVectorField(
        _('Search vector'),
        null=True)

L'objet search_vector doit être rempli à chaque modification / sauvegarde de l'objet.

from django.contrib.postgres.search import SearchVector
from django.db.models import Value

class Aid(models.Model):
    …
    def save(self, *args, **kwargs):
        self.search_vector = \
            SearchVector(Value(self.name), weight='A', config='french') + \
            SearchVector(Value(self.description), weight='B', config='french') + \
            SearchVector(Value(' '.join(self.tags)), weight='C', config='french')
        super().save(*args, **kwargs)

Il est intéressant de noter que assignons des poids spéficiques (A, B, C…) aux différents champs. Ainsi, le titre de l'aide aura plus d'importance que la description ou les mots clés pour évaluer sa pertinence par rapport à une recherche donnée.

Enfin, pour des raisons de performances, il est important de penser à créer un index.

from django.contrib.postgres.indexes import GinIndex

class Aid(models.Model):
    …
    class Meta:
        indexes = [
            GinIndex(fields=['search_vector']),
        ]

La recherche s'effectuera désormais via la syntaxe suivante :

from django.contrib.postgres.search import SearchQuery

aids = Aid.objects.filter(search_vector=SearchQuery('épuration', config='french'))

Tri par pertinence

Nous avons fait des progrès par rapport à une recherche classique : la requête « station d'épuration » permet désormais de trouver des résultats qui contiennent les mots « épurer », « stations », etc. Pour aller plus loin, nous allons maintenant trier les résultats par pertinence.

from django.contrib.postgres.search import SearchQuery, SearchRank
from django.db.models import F

query = 'épuration'
aids = Aid.objects \
    .filter(search_vector=SearchQuery(query, config='french')) \
    .annotate(rank=SearchRank(F('search_vector'), query)) \
    .order_by('-rank')

Recherche par trigrammes

Une autre fonctionnalité d'Aides-territoires utilise la recherche : l'auto-complétion géographique.

Dans la mesure ou les aides proposées ont souvent une composante locale très forte, il peut être utile de trouver les résultats qui ne seront disponibles qu'en Bretagne, à Montpellier ou dans le Périgord (par exemple).

Ainsi, un champ de recherche permet de sélectionner un « périmètre », une valeur possible parmi toutes les communes, communautés de communes, département, région de France. Ce champ fait appel à une api pour proposer une autocomplétion. Si je tape « nant » dans le champ, on me propose « Nant », « Nantes », « Nanterres », « Nanton », etc.

À la base, nous utilisions une approche (très) naïve pour récupérer les résultats.

import operator
from functools import reduce
from django.db.models import Q

from geofr.models import Perimeter

MIN_SEARCH_LENGTH = 2

class PerimeterViewSet(viewsets.ReadOnlyModelViewSet):

    def get_queryset(self):
        qs = Perimeter.objects.all()
        q = self.request.query_params.get('q', '')
        terms = q.split()
        q_filters = []
        for term in terms:
            if len(term) >= MIN_SEARCH_LENGTH:
                q_filters.append(Q(name__icontains=term))

        if q_filters:
            qs = qs.filter(reduce(operator.and_, q_filters))

        return qs

Cette méthode donnait de très mauvais résultats (duh).

En terme de performance, ce n'était pas terrible. Dans la mesure ou il s'agit d'une autocomplétion, une bonne réactivité est essentielle, et même avec une faible volumétrie d'environ 40000 entrées dans la base, la latence était pénible.

Ensuite, la pertinence des résultats était mauvaise, notamment avec les noms de villes composés. En tapant la requête « vic », le maire de Vic-la-Gardiole aurait trouvé les résultats « Vichy », « Ancretiéville-Saint-Victor », « Cauvicourt », « Crévic », etc.

Finalement, il était impossible de trouver certaines communes aux noms particulièrement courts, comme « Y ».

Nous avons effectué des tests avec la recherche plein-texte telle que décrite plus haut, mais les résultats étaient à peine meilleurs. En effet, la recherche textuelle donne de bons résultats quand il y a beaucoup de texte à indexer, ce qui n'est pas le cas pour des noms de lieux. Par ailleurs, comme il ne s'agit que de noms propres, les algorithmes de tokenisations donnaient des résultats parfois arbitraires.

Finalement, nous avons mis en place un outil proposé par Postgres : la recherche par similarité de trigrammes.

L'extraction de trigrammes consiste à déterminer toutes les séries de trois caractères ou moins contenues dans un texte donné.

Ainsi le terme « Montpellier » contient les trigrammes [M, Mo, Mon, ont, ntp, tpe… ier, er, r].

En utilisant les trigrammes, on peux mesurer la similarité de deux morceaux de texte en calculant tous les trigrammes de chaque texte et en comptant le nombre de trigrammes communs. Les résultats sont étonamment pertinents pour les recherches de noms propres.

En utilisant la recherche par trigrammes, la recherche « Y » permet de trouver la commune « Y », « ile de france » permet de trouver « Île-de-France », « vic la ga » trouve « Vic-la-Gardiole », etc.

Un étonnant avantage de la recherche par trigramme est que compléter sa recherche permet toujours d'avoir des résultats plus pertinents. Ainsi la recherche « vic » renvoie « vico », « vicq », « vichel », « volvic » ; la recherche « vic la » renvoie « la vicogne », « vic-la-gardiole » en seconde position ; la recherche « vic la ga » renvoie bien « vic-la-gardiole » en première position.

Voici le code de l'api actuelle :

from rest_framework import viewsets
from django.contrib.postgres.search import TrigramSimilarity

from geofr.models import Perimeter

MIN_SEARCH_LENGTH = 1

class PerimeterViewSet(viewsets.ReadOnlyModelViewSet):
    def get_queryset(self):
        qs = Perimeter.objects.all()
        q = self.request.query_params.get('q', '')
        if len(q) >= MIN_SEARCH_LENGTH:
            qs = qs \
                .annotate(similarity=TrigramSimilarity('name', q)) \
                .filter(name__trigram_similar=q) \
                .order_by('-similarity')

        return qs

Pour que cela fonctionne, vous devrez au préalable activer une extension postgres. Plusieurs solutions : le faire à la main (CREATE EXTENSION pg_trgm;) ou utiliser l'extension Django dédiée.

Indexation avec trigrammes

Une recherche par trigramme efficace nécessite de mettre en place un index dédié : nous allons utiliser un index GIN avec une classe d'opérateur utilisant les trigrammes. Un tel index permet d'accélerer la recherche de similarité entre le contenu d'un champ et une requête textuelle en se basant sur les trigrammes.

from django.contrib.postgres.indexes import GinIndex

class Perimeter(models.Model):
    …
    class Meta:
        indexes = [
            GinIndex(fields=['name'], opclasses=['gin_trgm_ops']),
        ]

Pour nous convaincre de l'utilité de cet index, voici la requête sql générée par la fonction django décrite ci-dessus, avec la requête « Montpellier » :

SELECT …, SIMILARITY("name", 'montpellier') AS "similarity" FROM "geofr_perimeter" WHERE "name" % 'montpellier' ORDER BY "similarity" DESC;

En local, cette requête nécessite 116ms.

Limit  (cost=1231.52..1231.61 rows=37 width=139) (actual time=91.728..91.735 rows=46 loops=1)
  ->  Sort  (cost=1231.52..1231.61 rows=37 width=139) (actual time=91.727..91.732 rows=46 loops=1)
        Sort Key: (similarity((name)::text, 'montpellier'::text)) DESC, scale DESC, name
        Sort Method: quicksort  Memory: 37kB
        ->  Seq Scan on geofr_perimeter  (cost=0.00..1230.56 rows=37 width=139) (actual time=3.163..91.549 rows=46 loops=1)
              Filter: ((name)::text % 'montpellier'::text)
              Rows Removed by Filter: 36711
Planning time: 0.401 ms
Execution time: 91.777 ms

L'analyse de la requête montre que Postgres réalise une recherche séquentielle sur toutes les lignes de la table (Seq Scan).

Après application de l'index, la requête ne prends plus que 7ms.

Limit  (cost=225.49..225.58 rows=37 width=139) (actual time=8.804..8.815 rows=46 loops=1)
  ->  Sort  (cost=225.49..225.58 rows=37 width=139) (actual time=8.803..8.807 rows=46 loops=1)
        Sort Key: (similarity((name)::text, 'montpellier'::text)) DESC, scale DESC, name
        Sort Method: quicksort  Memory: 37kB
        ->  Bitmap Heap Scan on geofr_perimeter  (cost=100.28..224.52 rows=37 width=139) (actual time=2.886..8.666 rows=46 loops=1)
              Recheck Cond: ((name)::text % 'montpellier'::text)
              Rows Removed by Index Recheck: 1207
              Heap Blocks: exact=412
              ->  Bitmap Index Scan on name_trgm  (cost=0.00..100.28 rows=37 width=0) (actual time=2.350..2.350 rows=1253 loops=1)
                    Index Cond: ((name)::text % 'montpellier'::text)
Planning time: 1.220 ms
Execution time: 8.937 ms

On constate l'utilisation de l'index (Bitmap Index Scan).

Dans toute mise en place de ce type de recherche, il faut donc 1/ mettre en place les indexes appropriés et 2/ vérifier que ces indexes sont bel et bien utilisés.

Conclusion

Postgresql est un outil extraordinaire. Pensez à bien exploiter ses fonctionnalités à fond avant de décider d'embarquer des outils lourds comme Elasticsearch.