Problèmes de sortie et de performances des résultats de recherche

L'un des scénarios typiques de toutes les applications que nous connaissons consiste à rechercher des données selon certains critères et à les afficher sous une forme facile à lire. Il peut également y avoir des options supplémentaires pour le tri, le regroupement et la pagination. La tâche est, en théorie, triviale, mais lorsqu'elle est résolue, de nombreux développeurs commettent un certain nombre d'erreurs, qui entraînent ensuite une baisse de productivité. Essayons d'envisager diverses options pour résoudre ce problème et formulons des recommandations pour choisir la mise en œuvre la plus efficace.

Option de pagination n° 1

L’option la plus simple qui nous vient à l’esprit est l’affichage page par page des résultats de recherche dans sa forme la plus classique.

Disons que votre application utilise une base de données relationnelle. Dans ce cas, pour afficher les informations sous ce formulaire, vous devrez exécuter deux requêtes SQL :

• Obtenez les lignes de la page actuelle.
• Calculez le nombre total de lignes correspondant aux critères de recherche - cela est nécessaire pour afficher les pages.

Regardons la première requête en utilisant une base de données de test MS SQL comme exemple Aventure pour le serveur 2016. Pour cela nous utiliserons la table Sales.SalesOrderHeader :

SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

La requête ci-dessus renverra les 50 premières commandes de la liste, triées par date d'ajout décroissante, autrement dit les 50 commandes les plus récentes.

Il s'exécute rapidement sur la base de test, mais regardons le plan d'exécution et les statistiques d'E/S :

Table 'SalesOrderHeader'. Scan count 1, logical reads 698, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Vous pouvez obtenir des statistiques d'E/S pour chaque requête en exécutant la commande SET STATISTICS IO ON dans le runtime de requête.

Comme vous pouvez le voir sur le plan d'exécution, l'option la plus gourmande en ressources consiste à trier toutes les lignes de la table source par date d'ajout. Et le problème est que plus il y a de lignes dans le tableau, plus le tri sera « difficile ». En pratique, de telles situations doivent être évitées, ajoutons donc un index à la date d'ajout et voyons si la consommation des ressources a changé :

Table 'SalesOrderHeader'. Scan count 1, logical reads 165, physical reads 0, read-ahead reads 5, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Évidemment, ça s'est beaucoup amélioré. Mais tous les problèmes sont-ils résolus ? Modifions la requête pour rechercher les commandes dont le coût total des marchandises dépasse 100 $ :

SELECT * FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

Table 'SalesOrderHeader'. Scan count 1, logical reads 1081, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Nous nous trouvons face à une situation amusante : le plan de requête n'est pas bien pire que le précédent, mais le nombre réel de lectures logiques est presque deux fois plus important qu'avec une analyse complète de la table. Il existe un moyen de s'en sortir - si nous créons un indice composite à partir d'un indice déjà existant et ajoutons le prix total des marchandises comme deuxième champ, nous obtiendrons à nouveau 165 lectures logiques :

CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);

Cette série d’exemples peut se poursuivre longtemps, mais les deux principales réflexions que je souhaite exprimer ici sont :

• L'ajout de tout nouveau critère ou ordre de tri à une requête de recherche peut avoir un impact significatif sur la vitesse de la requête de recherche.
• Mais si nous devons soustraire seulement une partie des données, et non tous les résultats correspondant aux termes de recherche, il existe de nombreuses façons d'optimiser une telle requête.

Passons maintenant à la deuxième requête mentionnée au tout début : celle qui compte le nombre d'enregistrements satisfaisant au critère de recherche. Prenons le même exemple : recherche de commandes supérieures à 100 $ :

SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100

Compte tenu de l'indice composite indiqué ci-dessus, on obtient :

Table 'SalesOrderHeader'. Scan count 1, logical reads 698, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Le fait que la requête parcourt l'intégralité de l'index n'est pas surprenant, puisque le champ SubTotal n'est pas en première position, donc la requête ne peut pas l'utiliser. Le problème est résolu en ajoutant un autre index sur le champ SubTotal et, par conséquent, il ne donne que 48 lectures logiques.

Vous pouvez donner quelques exemples supplémentaires de demandes de comptage de quantités, mais l'essence reste la même : recevoir une donnée et compter le montant total sont deux requêtes fondamentalement différentes, et chacun nécessite ses propres mesures d’optimisation. En général, vous ne pourrez pas trouver une combinaison d’index qui fonctionne aussi bien pour les deux requêtes.

En conséquence, l'une des exigences importantes à clarifier lors du développement d'une telle solution de recherche est de savoir s'il est vraiment important pour une entreprise de voir le nombre total d'objets trouvés. Il arrive souvent que non. Et la navigation par numéros de page spécifiques, à mon avis, est une solution avec une portée très étroite, puisque la plupart des scénarios de pagination ressemblent à « passer à la page suivante ».

Option de pagination n° 2

Supposons que les utilisateurs ne se soucient pas de connaître le nombre total d'objets trouvés. Essayons de simplifier la page de recherche :

En fait, la seule chose qui a changé est qu'il n'y a aucun moyen de naviguer vers des numéros de page spécifiques, et désormais ce tableau n'a pas besoin de savoir combien il peut y en avoir pour l'afficher. Mais la question se pose : comment le tableau sait-il s'il y a des données pour la page suivante (afin d'afficher correctement le lien « Suivant ») ?

La réponse est très simple : vous pouvez lire dans la base de données un enregistrement de plus que ce qui est nécessaire à l'affichage, et la présence de cet enregistrement « supplémentaire » indiquera s'il y a une partie suivante. De cette façon, vous n'avez besoin d'exécuter qu'une seule requête pour obtenir une page de données, ce qui améliore considérablement les performances et facilite la prise en charge de ces fonctionnalités. Dans ma pratique, il y a eu un cas où le refus de compter le nombre total d'enregistrements a accéléré la livraison des résultats de 4 à 5 fois.

Il existe plusieurs options d'interface utilisateur pour cette approche : des commandes "précédent" et "suivant", comme dans l'exemple ci-dessus, un bouton "charger plus", qui ajoute simplement une nouvelle partie aux résultats affichés, "défilement infini", qui fonctionne sur le principe de "charger plus" ", mais le signal pour obtenir la partie suivante est pour l'utilisateur de faire défiler tous les résultats affichés jusqu'à la fin. Quelle que soit la solution visuelle, le principe d’échantillonnage des données reste le même.

Nuances de mise en œuvre de la pagination

Tous les exemples de requête donnés ci-dessus utilisent l'approche « offset + count », lorsque la requête elle-même spécifie dans quel ordre les lignes de résultat et combien de lignes doivent être renvoyées. Voyons d’abord comment organiser au mieux le passage des paramètres dans ce cas. En pratique, j'ai rencontré plusieurs méthodes :

• Le numéro de série de la page demandée (pageIndex), la taille de la page (pageSize).
• Le numéro de série du premier enregistrement à renvoyer (startIndex), le nombre maximum d'enregistrements dans le résultat (count).
• Le numéro de séquence du premier enregistrement à renvoyer (startIndex), le numéro de séquence du dernier enregistrement à renvoyer (endIndex).

À première vue, cela peut sembler si élémentaire qu’il n’y a aucune différence. Mais ce n'est pas le cas - l'option la plus pratique et la plus universelle est la seconde (startIndex, count). Il y a plusieurs raisons à cela:

• Pour l'approche de relecture d'entrée +1 donnée ci-dessus, la première option avec pageIndex et pageSize est extrêmement gênante. Par exemple, nous souhaitons afficher 50 articles par page. Selon l'algorithme ci-dessus, vous devez lire un enregistrement de plus que nécessaire. Si ce "+1" n'est pas implémenté sur le serveur, il s'avère que pour la première page il faut demander des enregistrements de 1 à 51, pour la seconde - de 51 à 101, etc. Si vous spécifiez une taille de page de 51 et augmentez pageIndex, la deuxième page reviendra de 52 à 102, etc. Ainsi, dans la première option, la seule façon de bien implémenter un bouton pour passer à la page suivante est de faire relire par le serveur la ligne « extra », ce qui sera une nuance très implicite.
• La troisième option n'a aucun sens, car pour exécuter des requêtes dans la plupart des bases de données, vous devrez toujours transmettre le nombre plutôt que l'index du dernier enregistrement. Soustraire startIndex de endIndex peut être une simple opération arithmétique, mais elle est superflue ici.

Nous devons maintenant décrire les inconvénients de la mise en œuvre de la pagination via « offset + quantité » :

• La récupération de chaque page suivante sera plus coûteuse et plus lente que la précédente, car la base de données devra toujours parcourir tous les enregistrements « depuis le début » selon les critères de recherche et de tri, puis s'arrêter au fragment souhaité.
• Tous les SGBD ne peuvent pas prendre en charge cette approche.

Il existe des alternatives, mais elles sont également imparfaites. La première de ces approches est appelée « pagination du jeu de clés » ou « méthode de recherche » et est la suivante : après avoir reçu une partie, vous pouvez mémoriser les valeurs des champs​​dans le dernier enregistrement de la page, puis les utiliser pour obtenir la partie suivante. Par exemple, nous avons exécuté la requête suivante :

SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

Et dans le dernier enregistrement, nous avons obtenu la valeur de la date de commande « 2014-06-29 ». Ensuite, pour obtenir la page suivante, vous pouvez essayer de faire ceci :

SELECT * FROM Sales.SalesOrderHeader
WHERE OrderDate < '2014-06-29'
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

Le problème est que OrderDate est un champ non unique et que la condition spécifiée ci-dessus risque de manquer de nombreuses lignes obligatoires. Pour clarifier cette requête, vous devez ajouter un champ unique à la condition (supposons que 75074 soit la dernière valeur de la clé primaire de la première partie) :

SELECT * FROM Sales.SalesOrderHeader
WHERE (OrderDate = '2014-06-29' AND SalesOrderID < 75074)
   OR (OrderDate < '2014-06-29')
ORDER BY OrderDate DESC, SalesOrderID DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

Cette option fonctionnera correctement, mais en général elle sera difficile à optimiser puisque la condition contient un opérateur OR. Si la valeur de la clé primaire augmente à mesure que OrderDate augmente, la condition peut être simplifiée en laissant uniquement un filtre par SalesOrderID. Mais s'il n'y a pas de corrélation stricte entre les valeurs de la clé primaire et le champ selon lequel le résultat est trié, ce OU ne peut être évité dans la plupart des SGBD. Une exception que je connais est PostgreSQL, qui prend entièrement en charge les comparaisons de tuples, et la condition ci-dessus peut être écrite sous la forme "WHERE (OrderDate, SalesOrderID) <('2014-06-29', 75074)". Étant donné une clé composite avec ces deux champs, une requête comme celle-ci devrait être assez simple.

Une deuxième approche alternative peut être trouvée, par exemple, dans API de défilement ElasticSearch ou Base de données Cosmos — lorsqu'une requête, en plus des données, renvoie un identifiant spécial avec lequel vous pouvez obtenir la partie suivante des données. Si cet identifiant a une durée de vie illimitée (comme dans Comsos DB), alors c'est un excellent moyen d'implémenter une pagination avec une transition séquentielle entre les pages (option n°2 mentionnée ci-dessus). Ses inconvénients possibles : il n'est pas supporté dans tous les SGBD ; l'identifiant du morceau suivant qui en résulte peut avoir une durée de vie limitée, ce qui n'est généralement pas adapté à la mise en œuvre d'une interaction utilisateur (telle que l'API de défilement ElasticSearch).

Filtrage complexe

Compliquons encore la tâche. Supposons qu'il soit nécessaire de mettre en œuvre la recherche dite à facettes, qui est très familière à tous les magasins en ligne. Les exemples ci-dessus basés sur la table des commandes ne sont pas très illustratifs dans ce cas, passons donc à la table Product de la base de données AdventureWorks :

Quelle est l’idée derrière la recherche à facettes ? Le fait est que pour chaque élément filtrant, le nombre d'enregistrements répondant à ce critère est affiché en tenant compte des filtres sélectionnés dans toutes les autres catégories.

Par exemple, si nous sélectionnons la catégorie Vélos et la couleur Noir dans cet exemple, le tableau affichera uniquement les vélos noirs, mais :

• Pour chaque critère du groupe Catégories, le nombre de produits de cette catégorie sera affiché en noir.
• Pour chaque critère du groupe « Couleurs », le nombre de vélos de cette couleur sera affiché.

Voici un exemple du résultat obtenu pour de telles conditions :

Si vous cochez également la catégorie « Vêtements », le tableau affichera également les vêtements noirs en stock. Le nombre de produits noirs dans la section « Couleur » sera également recalculé selon les nouvelles conditions, seulement dans la section « Catégories » rien ne changera... J'espère que ces exemples suffiront à comprendre l'algorithme de recherche à facettes habituel.

Imaginons maintenant comment cela peut être mis en œuvre sur une base relationnelle. Chaque groupe de critères, tels que Catégorie et Couleur, nécessitera une requête distincte :

SELECT pc.ProductCategoryID, pc.Name, COUNT(1) FROM Production.Product p
  INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
  INNER JOIN Production.ProductCategory pc ON ps.ProductCategoryID = pc.ProductCategoryID
WHERE p.Color = 'Black'
GROUP BY pc.ProductCategoryID, pc.Name
ORDER BY COUNT(1) DESC

SELECT Color, COUNT(1) FROM Production.Product p
  INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
WHERE ps.ProductCategoryID = 1 --Bikes
GROUP BY Color
ORDER BY COUNT(1) DESC

Quel est le problème avec cette solution ? C'est très simple : cela ne s'adapte pas bien. Chaque section de filtre nécessite une requête distincte pour calculer les quantités, et ces requêtes ne sont pas les plus simples. Dans les boutiques en ligne, certaines catégories peuvent comporter plusieurs dizaines de sections de filtrage, ce qui peut constituer un sérieux problème de performances.

Habituellement, après ces déclarations, on me propose quelques solutions, à savoir :

• Combinez tous les nombres en une seule requête. Techniquement, cela est possible en utilisant le mot-clé UNION, mais cela n'améliorera pas beaucoup les performances : la base de données devra toujours exécuter chacun des fragments à partir de zéro.
• Quantités de cache. Cela me est suggéré presque à chaque fois que je décris un problème. La mise en garde est que cela est généralement impossible. Disons que nous avons 10 « facettes », chacune ayant 5 valeurs. Il s’agit d’une situation très « modeste » par rapport à ce que l’on peut constater dans les mêmes boutiques en ligne. Le choix d'un élément de facette affecte les quantités de 9 autres, autrement dit, pour chaque combinaison de critères les quantités peuvent être différentes. Dans notre exemple, il y a un total de 50 critères que l'utilisateur peut sélectionner ; il y aura donc 250 combinaisons possibles. Il n'y a pas assez de mémoire ou de temps pour remplir un tel tableau de données. Ici, vous pouvez objecter et dire que toutes les combinaisons ne sont pas réelles et que l'utilisateur sélectionne rarement plus de 5 à 10 critères. Oui, il est possible d'effectuer un chargement paresseux et de mettre en cache une quantité uniquement de ce qui a déjà été sélectionné, mais plus il y a de sélections, moins un tel cache sera efficace et plus les problèmes de temps de réponse seront visibles (surtout si le l'ensemble de données change régulièrement) .

Heureusement, il existe depuis longtemps des solutions assez efficaces pour résoudre ce problème, qui fonctionnent de manière prévisible sur de gros volumes de données. Pour chacune de ces options, il est logique de diviser le recalcul des facettes et la réception de la page de résultats en deux appels parallèles au serveur et d'organiser l'interface utilisateur de manière à ce que le chargement des données par facettes « n'interfère pas » avec l'affichage de Résultats de recherche.

• Appelez un recalcul complet des « facettes » aussi rarement que possible. Par exemple, ne recalculez pas tout à chaque fois que les critères de recherche changent, mais recherchez plutôt le nombre total de résultats qui correspondent aux conditions actuelles et invitez l'utilisateur à les afficher - « 1425 enregistrements trouvés, afficher ? L'utilisateur peut soit continuer à modifier les termes de recherche, soit cliquer sur le bouton « afficher ». Ce n'est que dans le second cas que toutes les demandes d'obtention de résultats et de recalcul des quantités sur toutes les « facettes » seront exécutées. Dans ce cas, comme vous pouvez facilement le constater, vous devrez traiter une demande pour obtenir le nombre total de résultats et son optimisation. Cette méthode peut être trouvée dans de nombreuses petites boutiques en ligne. Évidemment, ce n’est pas une panacée à ce problème, mais dans des cas simples, cela peut constituer un bon compromis.
• Utilisez les moteurs de recherche pour trouver des résultats et compter les facettes, tels que Solr, ElasticSearch, Sphinx et autres. Tous sont conçus pour créer des « facettes » et le font assez efficacement grâce à l’index inversé. Comment fonctionnent les moteurs de recherche, pourquoi dans de tels cas ils sont plus efficaces que les bases de données à usage général, quelles sont les pratiques et les pièges - ceci fait l'objet d'un article séparé. Ici, je voudrais attirer votre attention sur le fait que le moteur de recherche ne peut pas remplacer le stockage principal des données, il est utilisé en complément : toutes les modifications dans la base de données principale qui sont pertinentes pour la recherche sont synchronisées dans l'index de recherche ; Le moteur de recherche interagit généralement uniquement avec le moteur de recherche et n'accède pas à la base de données principale. L’un des points les plus importants ici est de savoir comment organiser cette synchronisation de manière fiable. Tout dépend des exigences en matière de « temps de réaction ». Si le temps entre un changement dans la base de données principale et sa « manifestation » dans la recherche n'est pas critique, vous pouvez créer un service qui recherche les enregistrements récemment modifiés toutes les quelques minutes et les indexe. Si vous souhaitez le temps de réponse le plus court possible, vous pouvez implémenter quelque chose comme boîte d'envoi transactionnelle pour envoyer des mises à jour au service de recherche.

résultats

1. La mise en œuvre de la pagination côté serveur est une complication importante et n'a de sens que pour les ensembles de données à croissance rapide ou simplement volumineux. Il n’existe pas de recette absolument exacte pour évaluer « grand » ou « à croissance rapide », mais je suivrais cette approche :
   • Si la réception d'une collection complète de données, prenant en compte l'heure du serveur et la transmission réseau, répond normalement aux exigences de performances, il ne sert à rien d'implémenter la pagination côté serveur.
   • Il peut arriver qu'aucun problème de performances ne soit attendu dans un avenir proche, car il y a peu de données, mais la collecte de données augmente constamment. Si un ensemble de données à l'avenir risque de ne plus satisfaire le point précédent, il est préférable de commencer la pagination immédiatement.
2. S'il n'y a pas d'exigence stricte de la part de l'entreprise d'afficher le nombre total de résultats ou d'afficher les numéros de page, et que votre système ne dispose pas de moteur de recherche, il est préférable de ne pas mettre en œuvre ces points et d'envisager l'option n°2.
3. S'il existe une exigence claire en matière de recherche à facettes, vous disposez de deux options sans sacrifier les performances :
   • Ne recalculez pas toutes les quantités à chaque fois que les critères de recherche changent.
   • Utilisez des moteurs de recherche tels que Solr, ElasticSearch, Sphinx et autres. Mais il faut comprendre qu'elle ne peut pas remplacer la base de données principale et doit être utilisée comme complément au stockage principal pour résoudre les problèmes de recherche.
4. De plus, dans le cas d'une recherche à facettes, il est logique de diviser la récupération de la page de résultats de recherche et le comptage en deux requêtes parallèles. Le comptage des quantités peut prendre plus de temps que l'obtention des résultats, alors que les résultats sont plus importants pour l'utilisateur.
5. Si vous utilisez une base de données SQL pour la recherche, toute modification de code liée à cette partie doit être correctement testée pour vérifier ses performances sur la quantité appropriée de données (dépassant le volume de la base de données active). Il est également conseillé d'utiliser le suivi du temps d'exécution des requêtes sur toutes les instances de la base de données, et notamment sur celle « live ». Même si tout allait bien avec les plans de requête au stade du développement, à mesure que le volume de données augmente, la situation peut changer sensiblement.

Source: habr.com