Créer un moteur de recherche avancé avec PostgreSQL

 (xata.io)
6 points par GN⁺ 2023-07-13 | 1 commentaires | Partager sur WhatsApp
  • La recherche plein texte de PostgreSQL est une approche qui permet de construire une fonctionnalité de recherche sans moteur dédié, en combinant tsvector, tsquery, @@, ts_rank et les index GIN
  • Les termes recherchés et les documents sont normalisés au niveau des lexèmes, et les requêtes peuvent être exprimées avec des opérateurs comme AND, OR, NOT et FOLLOWED BY, ce qui permet d’implémenter une grande partie de la syntaxe de recherche courante
  • Dans l’environnement d’exemple, l’index GIN a réduit le temps de recherche de plus de 200 ms à environ 4 ms, mais lorsque le nombre de résultats augmente, le coût de classement et de tri de ts_rank peut devenir un goulot d’étranglement
  • L’ajustement de la pertinence se fait en ajoutant à l’expression de tri des signaux comme le poids du titre, le nombre de votes, la note, le genre ou la fraîcheur, ou en attribuant des poids aux colonnes avec setweight
  • La tolérance aux fautes de frappe, la recherche à facettes, l’autocomplétion, la recherche d’expressions exactes et la recherche hybride sont aussi possibles, mais avec PostgreSQL il faut assembler soi-même les composants, et vérifier les limites de performance sur de grands jeux de données

L’approche de la recherche plein texte dans PostgreSQL

  • PostgreSQL fournit des composants de bas niveau pour la recherche plein texte, que l’on peut combiner pour créer des fonctionnalités de moteur de recherche
  • Cette approche est flexible, mais demande davantage de travail d’implémentation que des solutions dont la recherche plein texte est l’usage principal, comme Elasticsearch, Typesense ou Meilisearch
  • Les requêtes d’exemple utilisent le jeu de données Wikipedia Movie Plots de Kaggle
    • Il contient 34 000 titres de films
    • Sa taille au format CSV est d’environ 81 Mo

Composants clés

  • La recherche plein texte de PostgreSQL s’articule autour des éléments suivants
    • tsvector : stocke le texte à rechercher sous forme de liste de lexèmes normalisés
    • tsquery : représente une requête de recherche normalisée
    • @@ : opérateur de correspondance qui vérifie si une tsquery correspond à un tsvector
    • ts_rank, ts_rank_cd : calculent le score de pertinence des résultats de recherche
    • Index GIN : index inversé permettant d’interroger efficacement un tsvector

tsvector et configuration de recherche

  • tsvector stocke une liste triée de lexèmes
    • Un lexème ressemble à un token, mais c’est une chaîne normalisée afin que plusieurs formes d’un même mot soient ramenées à une forme commune
    • Avec la configuration anglaise, les majuscules sont converties en minuscules et les suffixes sont supprimés lors de la normalisation
  • Lorsque to_tsvector analyse une phrase anglaise, les mots vides comme “I”, “to” ou “an” sont supprimés
    • “refuse” et “Refusing” sont tous deux transformés en refus
    • La ponctuation est ignorée
    • La position des mots dans le texte original et leur poids sont également enregistrés
  • En utilisant la configuration simple au lieu de la configuration de recherche english, les mots sont inclus tels qu’ils apparaissent dans le texte
    • “refuse” et “refusing” restent des lexèmes distincts
    • La configuration simple est particulièrement utile pour les colonnes contenant des libellés ou des tags
  • PostgreSQL fournit des configurations de recherche intégrées pour plusieurs langues, mais pas pour les langues CJK (chinois, japonais, coréen)
    • Pour les langues non prises en charge, la configuration simple peut fonctionner de manière pratique
    • Il n’est toutefois pas certain qu’elle soit suffisante pour le CJK

tsquery et expression des requêtes

  • tsquery est un type de données qui représente une requête de recherche normalisée
    • Les termes recherchés doivent déjà être des lexèmes normalisés
    • Plusieurs termes peuvent être combinés avec les opérateurs AND, OR, NOT et FOLLOWED BY
  • to_tsquery, plainto_tsquery et websearch_to_tsquery aident à convertir le texte saisi par l’utilisateur en tsquery appropriée
    • Leur rôle principal est de normaliser les mots contenus dans le texte saisi
  • websearch_to_tsquery permet de créer des requêtes proches de celles d’un champ de recherche classique
    • darth vader est traité comme un AND logique exigeant que les deux mots soient présents dans le document
    • Les recherches OR et l’exclusion de mots sont également possibles
    • La recherche d’expression représente une forme où les mots se suivent dans l’ordre
  • Avec la configuration anglaise, les mots vides comme “the” sont supprimés, si bien que dans certaines recherches d’expression, presque toute l’expression peut disparaître
    • Dans ce cas, la configuration simple peut donner le résultat attendu
  • L’opérateur @@ est utilisé pour vérifier si une tsquery correspond à un tsvector

Index GIN et performances de recherche

  • GIN signifie Generalized Inverted Index ; c’est un type d’index conçu pour les requêtes cherchant des valeurs d’éléments contenues dans des valeurs composées
  • GIN peut être utilisé non seulement pour la recherche textuelle, mais aussi pour les requêtes JSON
  • On peut créer une colonne tsvector qui combine plusieurs colonnes recherchables, puis créer un index GIN sur cette colonne
  • Dans l’environnement d’exemple, l’index GIN a réduit le temps de recherche de plus de 200 ms à environ 4 ms

Classement et calcul de pertinence

  • Pour offrir une bonne expérience de recherche, les résultats doivent être triés par pertinence
  • PostgreSQL fournit deux fonctions de classement prédéfinies, ts_rank et ts_rank_cd
    • Les deux prennent en compte la fréquence d’apparition des termes recherchés
    • ts_rank_cd tient aussi compte de la proximité entre les lexèmes correspondants
  • La pertinence dépend fortement de la nature de l’application
    • Les fonctions de classement par défaut sont plutôt un point de départ ; selon les besoins, on peut créer sa propre fonction de classement ou les combiner avec d’autres facteurs
  • ts_rank doit accéder à la colonne search de chaque résultat
    • Si la condition WHERE correspond à de nombreuses lignes, PostgreSQL doit toutes les parcourir pour calculer le classement et effectuer le tri
    • Dans l’environnement d’exemple, une requête était renvoyée en 5 à 7 ms, mais une requête comme darth OR vader, qui doit classer plus de 1 000 résultats, prenait environ 80 ms

Tuning de la pertinence

  • La pertinence basée sur la fréquence des mots est un bon réglage par défaut, mais certaines données peuvent contenir des signaux plus importants que la fréquence
  • Dans le jeu de données de films, les signaux suivants peuvent être intégrés à la pertinence
    • Considérer les résultats correspondant dans le titre comme plus importants que ceux correspondant dans la description ou le synopsis
    • Faire remonter les films plus populaires selon la note ou le nombre de votes
    • Placer les comédies plus haut si l’utilisateur préfère ce genre
    • Considérer les titres récents comme plus pertinents que les titres anciens
  • Les moteurs de recherche dédiés offrent des fonctionnalités permettant de faire influencer le classement par différentes colonnes ou champs

Boosting basé sur les nombres, les dates et les valeurs exactes

  • PostgreSQL ne fournit pas directement de boosting basé sur d’autres colonnes, mais le classement est au final une expression de tri, on peut donc y ajouter ses propres signaux
  • Pour tenir compte du nombre de votes, on peut l’implémenter en ajoutant au score de classement un boost basé sur ce nombre
    • Dans l’exemple, un logarithme est utilisé pour en adoucir l’impact
    • Le coefficient 0.01 aligne le booster sur une échelle proche de celle du score de classement
  • On peut aussi créer une fonction plus complexe qui ne booste la note que lorsque le nombre de votes atteint un certain seuil
  • Pour faire remonter un genre précis, on peut utiliser une fonction comme valueBooster, qui ne renvoie un coefficient que lorsque la valeur correspond à une valeur précise de la colonne

Poids des colonnes

  • Les lexèmes d’un tsvector peuvent recevoir un poids
  • PostgreSQL prend en charge quatre poids : A, B, C et D
    • A est le poids le plus élevé
    • D est le plus faible et la valeur par défaut
  • La fonction setweight permet de contrôler le poids lors de la création d’une colonne tsvector
  • En donnant un poids plus élevé à la colonne titre, les films dont le titre contient le terme recherché remontent en haut des résultats et leur score de classement augmente
  • Le fait qu’il n’existe que quatre classes de poids est une limite, et les poids doivent être appliqués au moment du calcul du tsvector

Tolérance aux fautes et recherche floue

  • PostgreSQL ne prend pas directement en charge la recherche floue ni la tolérance aux fautes de frappe avec tsvector et tsquery
  • En partant du principe que la requête contient une faute de frappe, on peut l’implémenter ainsi
    • Indexer tous les lexèmes du contenu dans une table séparée
    • Pour chaque mot de la requête, rechercher des mots candidats par similarité ou distance de Levenshtein
    • Modifier la requête pour inclure les mots trouvés
    • Exécuter la recherche avec la requête modifiée
  • L’exemple utilise la distance de Levenshtein, car c’est une méthode utilisée par les moteurs de recherche pour la recherche floue
  • Une fois la liste de mots candidats obtenue, il faut ajuster la requête pour inclure tous ces mots

Recherche à facettes

  • La recherche à facettes est largement utilisée, notamment sur les sites d’e-commerce, pour permettre aux utilisateurs de restreindre progressivement leur recherche
  • Dans PostgreSQL, on peut l’implémenter en définissant manuellement des catégories puis en les ajoutant aux conditions WHERE de la recherche
  • Il est aussi possible de créer des catégories de manière algorithmique à partir des données existantes
    • Dans l’exemple, une facette “Decade” est créée à partir de l’année des films
    • On peut également calculer le nombre de correspondances par décennie et l’afficher entre parenthèses
  • Pour récupérer plusieurs facettes en une seule requête, on peut combiner des CTE
  • Cette approche peut bien fonctionner sur de petits à moyens jeux de données, mais devenir lente sur de très grands jeux de données

Portée et limites d’un moteur de recherche PostgreSQL

  • En combinant les composants de recherche plein texte de PostgreSQL, on peut créer un moteur de recherche assez avancé
  • Une recherche basée sur PostgreSQL prend aussi en charge les jointures et les transactions ACID
    • Ce sont des fonctionnalités que les autres moteurs de recherche n’ont généralement pas
  • Parmi les sujets avancés de recherche qui mériteraient aussi d’être traités
    • Suggestions et autocomplétion
    • Correspondance exacte d’expressions
    • Recherche hybride combinée avec pg-vector
  • Ces fonctionnalités sont possibles avec PostgreSQL, mais il faut assembler soi-même les composants
  • Dans certains cas, les performances peuvent se dégrader sur de très grands jeux de données
  • L’article suivant, part 2, compare l’implémentation de la recherche dans PostgreSQL à l’ajout d’Elasticsearch dans l’infrastructure avec synchronisation des données

À lire aussi

1 commentaires

 
GN⁺ 2023-07-13
Avis sur Hacker News

  • Il ne faut pas essayer de faire ça en imitant les fonctionnalités d'Elasticsearch
    Dans les années 2000, j'ai déjà construit avec MySQL 3.x un moteur de recherche qui analysait les données EXIF d'images pour indexer une taxonomie à 3 niveaux avec des comptages ; même plusieurs vendeurs très coûteux n'y arrivaient pas correctement, et Autonomy n'arrivait même pas à la classification de plus haut niveau
    J'ai fini par y arriver au bout de 6 semaines à écrire du SQL fragile dont les performances changeaient rien qu'en modifiant l'ordre des colonnes dans un SELECT, mais je n'ai aucune envie de recommencer. Les bases de données restent fondamentalement assez similaires, mais les moteurs de recherche ont beaucoup plus progressé
    On peut le faire par curiosité intellectuelle, mais la recherche ne se résume pas à tokenizer puis s'arrêter là. Très vite arrivent des exigences comme la navigation par catégories, le multilingue, les synonymes automatiques, les suggestions orthographiques « Did you mean », les performances à grande échelle, et on se retrouve coincé dans une impasse. Pour sa santé mentale, mieux vaut utiliser un moteur de recherche, et il existe aussi des outils comme ZomboDB ou PGSync pour synchroniser PG et ES

    • Il y a en fait deux discussions différentes mélangées dans ce fil. Si l'on construit un moteur de recherche orienté client, il est logique d'utiliser un outil puissant comme Elasticsearch plutôt que de réinventer la roue
      À l'inverse, si un analyste data ou un développeur veut rechercher dans les colonnes texte d'une grosse base de données avec plus de souplesse que LIKE/ILIKE, il peut être plus simple et plus rapide d'aller à 90 % du besoin en créant un index/une table de recherche full-text dans la même base de données

  • J'attends avec intérêt la 2e partie comparant Postgres et Elasticsearch. Une application de l'entreprise utilise PG pour le CRUD des objets et Elastic pour la recherche, mais nous avons complètement sous-estimé l'effort nécessaire pour synchroniser les deux stockages, et nous envisageons concrètement de supprimer Elasticsearch

    • Une approche que j'ai déjà utilisée consiste à traiter Elasticsearch comme quelque chose que l'on peut toujours reconstruire
      Toutes les 5 minutes, un cron cherche en base les objets à indexer pour lesquels last_modified_at > last_indexing_started_timestamp, les indexe dans Elasticsearch, puis met à jour last_indexing_started_timestamp avec l'heure de début de la synchronisation. Ainsi, les objets modifiés entre le début et la fin d'une exécution seront repris à l'exécution suivante
      S'il faut reconstruire Elasticsearch, il suffit de vider le dernier horodatage d'indexation et de resynchroniser depuis le début ; le système peut ainsi s'auto-réparer sans que la synchronisation ne dérive
    • Dans un précédent poste, nous avions une architecture similaire, et ce n'était pas particulièrement difficile. Chaque fois qu'une entité PG était mise à jour, un message était envoyé pour la répliquer de manière asynchrone dans ES, et le côté ES allait la remplir en la relisant dans PG via son ID
      Comme toujours avec les traitements asynchrones, il faut de la surveillance et des tentatives de reprise, mais ES était stable et rapide, donc les problèmes étaient rares. En revanche, nos exigences de cohérence étaient souples : il suffisait que l'état le plus récent de PG arrive dans ES dans un délai raisonnable ; avec d'autres exigences, ce pourrait être différent
    • Nous avions aussi une séparation du type Postgres pour le CRUD et Elastic pour la recherche, mais nous avons sous-estimé non seulement la synchronisation des deux stockages, mais aussi l'exploitation fiable d'un cluster Elastic avec une équipe et une expérience limitées
      Après être passés à la recherche full-text de Postgres avec pondération des index et des requêtes, nous avons pu gérer tout ce dont nous avions besoin uniquement dans Postgres, avec des triggers de mise à jour et des requêtes de recherche très rapides
    • Je me demande si vous avez essayé zombodb [https://www.zombodb.com/]
    • Oui, je l'ai déjà fait, et c'était un travail difficile même avec beaucoup d'expérience ; certains résultats étaient même moins bons. La plupart étaient comparables, et seule une toute petite partie était meilleure
      Globalement, ce fut un succès, et la baisse de la charge d'exploitation a largement remboursé le temps d'ingénierie investi, mais ce n'est pas quelque chose à entreprendre à la légère
      Selon les besoins, des vues matérialisées, des vues normales et des triggers peuvent être préférables. La recherche textuelle intégrée peut aussi ne pas convenir au cas d'usage, et construire une alternative n'est pas forcément si difficile

  • Sans temps de consultation p50/p99 sous une charge réaliste, il est difficile de considérer que quoi que ce soit est démontré. Un moteur de recherche qui renvoie des résultats en 1 minute n'a rien d'« avancé », et une base relationnelle comme Postgres peut bien sûr le faire sur le papier

    • En tant qu'auteur, je prévois un billet de suivi comparant Elasticsearch, mais je ne pense pas essayer de faire des benchmarks. Quel que soit le scénario réaliste qu'on construise, il ne correspondra pas exactement au cas d'usage de chacun
      Je suis globalement d'accord : à grande échelle, par exemple au-delà de quelques millions d'enregistrements, il y a de fortes chances que je n'utilise pas cette approche. Mon intérêt principal était de voir jusqu'où on peut répliquer les fonctionnalités
      Pour les petits cas d'usage de recherche, cela présente des avantages comme moins d'infrastructure à maintenir, une cohérence forte et les jointures. Chez Xata, on réfléchit aussi à une transition fluide consistant à utiliser Postgres à petite échelle puis à passer à Elasticsearch avec un minimum de changements cassants
    • Lors d'un entretien avec un ancien de Google, j'ai entendu dire qu'ils mettaient en cache tous les résultats des requêtes déjà vues et mettaient aussi à jour ces résultats en cache quand l'index était mis à jour
      Vu sous cet angle, la rapidité des résultats de recherche n'a rien de si surprenant. On peut maintenir les résultats en cache en tâche de fond et les servir tels quels quand une requête arrive. Cette question de mise en cache et de temps de réponse me semble distincte de la vitesse réelle de calcul des résultats de recherche
    • Il y a un problème à exiger des p50/p99 sous une charge réaliste. Comment générer la vraie charge réaliste d'un moteur de recherche si, en pratique, beaucoup de gens ne cherchent rien du tout ? Le bombarder avec des requêtes aléatoires n'est pas réaliste
      Certains utilisent des connexions lentes, et un terme particulier comme un séisme peut aussi exploser seulement dans une région donnée
      Si les requêtes sont trop aléatoires, le cache n'aura pas de résultats et les mesures seront pires que la réalité ; si elles ne le sont pas assez, elles seront meilleures que la réalité
    • Lucene, c'est-à-dire la base utilisée par Elasticsearch et Solr, repose sur un index inversé, et le GIN de l'article utilise le même principe
      Par conséquent, les avantages d'ES et consorts se situent plutôt dans la montée en charge horizontale sur plusieurs nœuds ou dans les fonctionnalités additionnelles posées au-dessus de l'index principal
    • J'utilise la recherche full-text de Postgres, et ça fonctionne bien. En revanche, il faut savoir comment classer les lignes dans la requête
      ts_rank seul est parfait, mais en pratique on a souvent envie d'ajuster le classement avec d'autres indicateurs de pertinence. Une fois ce problème résolu — le fait de ne pas pouvoir utiliser cet indicateur comme critère de classement principal — les résultats sont aussi rapides que des requêtes ordinaires sur une table de base de données indexée

  • À l’adolescence, j’ai essayé d’en construire un à partir de zéro sans vraiment bien connaître ni les moteurs de recherche ni les bases de données. Je voulais voir jusqu’où on pouvait aller, à quelle vitesse on pouvait renvoyer des résultats de recherche raisonnablement pertinents
    Construire rapidement une base de données et un moteur de recherche basiques est sans doute assez facile, même pour un programmeur amateur. En comprenant les algorithmes fondamentaux d’informatique ainsi que l’usage des systèmes d’exploitation et du matériel, on peut en faire un en un ou deux mois
    Même avec un langage de haut niveau, les performances n’étaient pas mauvaises, autour de 250 k QPS sur un portable de 2003. Avec du sharding, la scalabilité n’est pas un énorme problème non plus. L’indexation, le verrouillage et la cohérence sont plus complexes que le stockage et la lecture
    Le vrai gros problème, c’est la subjectivité de la recherche. Dès qu’on se demande ce que l’utilisateur veut vraiment trouver, comment chercher quand il ne sait même pas lui-même ce qu’il cherche, comment empêcher les abus du système, ou comment gérer des requêtes et des jeux de données complexes, la difficulté augmente de plusieurs ordres de grandeur

    • 250 k RPS, ça paraît énorme, au point que même SQLite n’atteint probablement pas ça aujourd’hui. Un index inversé semblerait encore plus coûteux, et RocksDB est autour de 130 k RPS ; soit le matériel était plus puissant que mon portable, soit mon environnement est mal réglé
      Je me demande si c’était vraiment une base de données généraliste et si ce chiffre est exact. J’aimerais savoir quelles techniques ont été utilisées pour dépasser ces moteurs
    • Le plus gros problème quand on construit un moteur de recherche, ce n’est pas le QPS mais la taille du jeu de données à indexer. Si la structure de recherche tient dans la mémoire d’une seule machine, la latence est quasiment nulle et on peut fournir un QPS pratiquement infini
      Au-delà, il faut des solutions créatives, et c’est là que commencent les différents compromis
    • Je me demande où c’est publié en open source

  • Quand on fait de la recherche dans Postgres, l’un des nombreux problèmes est que c’est une tâche très consommatrice en CPU, et on va de plus en plus vers l’utilisation du GPU aussi. Idéalement, on voudrait réserver le CPU de la base de données aux mises à jour transactionnelles du modèle de données principal
    J’ai souvent vu des clusters ES et Solr tourner à 100 % sur plus de 10 nœuds pendant une réindexation, ou utiliser 30 à 50 % sur plus de 10 nœuds en régime normal. La base de données correspondante peut, par exemple, être une instance AWS L/XL avec 50 à 100 Go de données et une utilisation CPU d’environ 30 %
    Si on déplace toute la charge CPU de recherche vers la base principale, il faut alors shard la DB. Cela dit, pour des side projects, les extensions PG pour la recherche, les jointures récursives, les vecteurs, etc., sont agréables parce qu’elles sont amusantes et simples

    • Est-ce qu’on ne pourrait pas régler ça en faisant la recherche sur un réplica en lecture seule ?

  • Je l’ai déjà fait en pratique il y a quelque temps, et c’était assez rapide
    https://austingwalters.com/fast-full-text-search-in-postgres...
    Le site actuel est https://askhn.ai

  • En combinant ce genre de technique avec pgvector, on peut aussi retrouver du contenu pertinent via des embeddings. Ça m’a semblé presque magique

    • Tu pourrais détailler un peu plus ou indiquer des ressources utiles ?
    • Je trouve intéressant que les gens passent par ce genre de solution bricolée alors qu’ils pourraient utiliser quelque chose comme Vespa. En termes de performances, de pertinence, de scalabilité et d’expérience développeur, Vespa est à mon avis supérieur de plusieurs ordres de grandeur

  • Pour info, ce n’est pas « Dark » Vader mais Darth Vader. Moi aussi, quand j’étais jeune, je pensais que c’était « Dark »

    • Dans certaines traductions, comme en français, c’est effectivement Dark Vador, donc cette « erreur » est fréquente
    • Ce passage dans l’article m’a tellement dérangé que je n’ai pas réussi à me concentrer sur le reste. Comment peut-on connaître des citations de Yoda et continuer à écrire Dark Vader ?

  • Très bon article, clair aussi. SQLite propose également des fonctions d’indexation avancées et de stemming via des plugins standard
    Pour l’anglais, SQLite fonctionne aussi très bien

    • J’ai retrouvé ce que j’avais expérimenté avec SQLite
      https://github.com/daitangio/knowledge
      Ça vaut le coup d’essayer. C’est assez puissant
    • Je me demande si ce serait aussi possible avec un FDW. Si on ne réplique que les données à rechercher, il n’y aura pas beaucoup de writers, donc ça pourrait bien marcher sur des données de taille intermédiaire

  • Bon article, mais le passage disant que PostgreSQL ne prend pas en charge la recherche floue est en partie faux. L’extension pg_trgm et les index trigrammes GIN couvrent des cas d’usage de recherche floue comme ceux donnés en exemple dans l’article
    https://www.postgresonline.com/article_pfriendly/169.html
    Les requêtes peuvent devenir beaucoup plus rapides, mais au prix d’une consommation mémoire plus élevée et d’un surcoût de traitement lors des mises à jour