Optimisation des requêtes pour l'élément suivant et précédent

Question

Je cherche le meilleur moyen de récupérer les enregistrements suivants et précédents d'un enregistrement sans exécuter une requête complète. J'ai mis en place une solution complète et j'aimerais savoir s'il existe de meilleures approches pour ce faire.

Imaginons que nous construisions un site web pour un marchand de légumes fictif. En plus de ses pages HTML, il souhaite publier chaque semaine une liste d'offres spéciales sur son site. Il souhaite que ces offres résident dans une véritable table de base de données et que les utilisateurs puissent trier les offres de trois manières différentes.

Chaque article doit également disposer d'une page détaillée contenant des informations textuelles supplémentaires sur l'offre et des boutons "précédent" et "suivant". Les boutons "précédent" et "suivant" doivent pointer vers les entrées voisines. en fonction du tri que l'utilisateur avait choisi pour la liste .

_{(source : <a href="http://www.pekkagaiser.com/stuff/Sort.gif?" rel="nofollow noreferrer">pekkagaiser.com </a>)}

De toute évidence, le bouton "suivant" pour "Tomates, classe I" doit être "Pommes, classe 1" dans le premier exemple, "Poires, classe I" dans le deuxième, et aucun dans le troisième.

La tâche dans la vue détaillée est pour déterminer les éléments suivants et précédents sans lancer une requête à chaque fois. avec l'ordre de tri de la liste comme seule information disponible (disons que nous l'obtenons par un paramètre GET). ?sort=offeroftheweek_price et ignore les implications en matière de sécurité).

De toute évidence, la première solution qui vient à l'esprit consiste à transmettre les ID des éléments suivants et précédents en tant que paramètre. Après tout, nous connaissons déjà les ID à ce stade. Mais ce n'est pas une option ici - cela fonctionnerait dans cet exemple simplifié, mais pas dans la plupart de mes cas d'utilisation réels.

L'approche que j'utilise actuellement dans mon CMS consiste à utiliser quelque chose que j'ai appelé "cache de tri". Lorsqu'une liste est chargée, je stocke les positions des éléments dans les enregistrements d'une table nommée sortingcache .

name (VARCHAR)             items (TEXT)

offeroftheweek_unsorted    Lettuce; Tomatoes; Apples I; Apples II; Pears
offeroftheweek_price       Tomatoes;Pears;Apples I; Apples II; Lettuce
offeroftheweek_class_asc   Apples II;Lettuce;Apples;Pears;Tomatoes

évidemment, le items est réellement remplie d'identifiants numériques.

Dans la page de détail, j'accède maintenant à l'élément approprié de la liste de contrôle. sortingcache récupérer l'enregistrement items l'éclater, rechercher l'ID de l'élément actuel et renvoyer le voisin précédent et le voisin suivant.

array("current"   => "Tomatoes",
      "next"      => "Pears",
      "previous"  => null
      );

Cette méthode est évidemment coûteuse, ne fonctionne que pour un nombre limité d'enregistrements et crée des données redondantes, mais supposons que dans le monde réel, la requête permettant de créer les listes est très coûteuse (elle l'est), qu'il est hors de question de l'exécuter dans chaque vue détaillée et qu'il n'est pas possible de l'utiliser. algunos la mise en cache est nécessaire.

Mes questions :

• Pensez-vous que c'est une bonne pratique pour trouver les enregistrements voisins pour des ordres de requête variables ?

• Connaissez-vous de meilleures pratiques en termes de performance et de simplicité ? Connaissez-vous quelque chose qui rende ce système complètement obsolète ?

• En théorie de la programmation, existe-t-il un nom pour ce problème ?

• Le nom "Cache de triage" est-il approprié et compréhensible pour cette technique ?

• Existe-t-il des modèles reconnus et courants pour résoudre ce problème ? Comment s'appellent-ils ?

Nota: Ma question ne porte pas sur la construction de la liste, ni sur la manière d'afficher la vue détaillée. Ce ne sont que des exemples. Ma question porte sur le fonctionnalité de base de déterminer les voisins d'un enregistrement lorsqu'une nouvelle recherche est impossible, et le moyen le plus rapide et le plus économique d'y parvenir.

Si quelque chose n'est pas clair, veuillez laisser un commentaire et je le clarifierai.

Lancer une prime - il y a peut-être plus d'informations à ce sujet.

Answer 1

Voici une idée. Vous pourriez décharger les opérations coûteuses vers une mise à jour lorsque l'épicier insère/met à jour de nouvelles offres plutôt que lorsque l'utilisateur final sélectionne les données à afficher. Cela peut sembler être une façon non dynamique de gérer les données de tri, mais cela peut augmenter la vitesse. Et, comme nous le savons, il y a toujours un compromis entre les performances et d'autres facteurs de codage.

Créez un tableau pour contenir le suivant et le précédent pour chaque offre et chaque option de tri. (Vous pouvez aussi les stocker dans la table des offres si vous avez toujours trois options de tri - la rapidité des requêtes est une bonne raison de dénormaliser votre base de données).

Vous auriez donc ces colonnes :

• Type de tri (Non trié, Prix, Classe et Prix Desc)
• ID de l'offre
• Prev ID
• Prochain ID

Lorsque les informations détaillées de la page de l'offre sont interrogées à partir de la base de données, le NextID et le PrevID font partie des résultats. Vous n'avez donc besoin que d'une seule requête pour chaque page détaillée.

Chaque fois qu'une offre est insérée, mise à jour ou supprimée, vous devez exécuter un processus qui valide l'intégrité/exactitude de la table des types de tri.

Answer 2

J'ai une idée un peu similaire à celle de Jessica. Cependant, au lieu de stocker des liens vers les éléments de tri suivants et précédents, vous stockez l'ordre de tri pour chaque type de tri. Pour trouver l'enregistrement précédent ou suivant, il suffit de récupérer la ligne avec SortX=currentSort++ ou SortX=currentSort--.

Exemple :

Type     Class Price Sort1  Sort2 Sort3
Lettuce  2     0.89  0      4     0
Tomatoes 1     1.50  1      0     4
Apples   1     1.10  2      2     2
Apples   2     0.95  3      3     1
Pears    1     1.25  4      1     3

Cette solution permettrait d'obtenir des temps d'interrogation très courts et occuperait moins d'espace disque que l'idée de Jessica. Cependant, comme vous le réalisez certainement, le coût de la mise à jour d'une ligne de données est nettement plus élevé, puisque vous devez recalculer et stocker tous les ordres de tri. Mais tout de même, en fonction de votre situation, si les mises à jour de données sont rares et surtout si elles se font toujours en masse, alors cette solution pourrait être la meilleure.

c'est-à-dire

once_per_day
  add/delete/update all records
  recalculate sort orders

J'espère que cela vous sera utile.

Answer 3

Il se peut que j'aie mal compris votre question - faites-moi signe.

Dans l'absolu, la meilleure façon de procéder est la suivante :

Conservez votre base de données comme trois systèmes totalement distincts, complètement triés et séparés.

{Lorsque je parle de "systèmes", il peut s'agir d'une "table", donc de trois tables totalement distinctes, ou d'un "groupe de tables" si c'est ce que vous avez actuellement pour une représentation. En d'autres termes, essentiellement trois bases de données distinctes pour ainsi dire.}

Cela a-t-il un sens ? Supposons que vous deviez modifier la base de données et ajouter un nouvel élément. En fait, à ce moment-là, vous devez ajouter le nouvel élément de trois manières différentes aux trois tables. Pour toutes vos opérations (suppression, etc.), vous devez travailler sur les trois tables. Vous devez également avoir un réconciliateur pour vous assurer que tout est en ordre. Pour ce faire, utilisez l'une des technologies évidentes comme les procédures stockées, etc. ou tout ce qui est à la mode aujourd'hui.

Il s'agit d'une procédure standard pour les grandes bases de données et cela ne devrait pas vous poser de problème.

Ensuite, lorsque l'internaute effectue une recherche, le travail est trivial.

Je suis surpris que personne n'ait mentionné cette approche standard totalement évidente. alors peut-être que je vous ai complètement mal compris ?

---

En outre, Pekka, veuillez expliquer si ce que vous dites est dans le sens d'un utilisateur qui clique sur "50 suivants" ou "50 précédents", comme n'importe quelle liste de résultats sur une page web moderne. Tenez-moi au courant !

Si c'est le cas, bien sûr, évidemment, il faut créer une table, un cache, une session ou autre pour chaque utilisateur qui se présente. (les supprimer après 5 minutes d'inutilisation).

C'est la chose normale que font absolument toutes les pages web de résultats "page avant / page arrière" sur le web depuis au moins 10 ans maintenant !!!!!.

Chaque fois que vous utilisez Google ou un résultat de recherche, vous obtenez un énorme système de base de données temporaire qui existe jusqu'à ce que vous vous endormiez.

Si votre question est ... vous avez inventé l'idée d'une liste de sessions de façon indépendante (sans réaliser que c'est la façon dont le web fonctionne de nos jours) et si c'est OK de le faire de cette façon - alors oui ! !!, chaque fois que vous utilisez google ou n'importe quelle page suivante-précédente sur le web entier, c'est exactement ce qui se passe ! !! Vous avez pensé de manière indépendante à la façon dont toutes les recherches modernes de type "page précédente - page suivante" fonctionnent. Allez-y sans hésiter avec votre "cache" pour chaque utilisateur.

Answer 4

J'ai fait des cauchemars avec celui-là aussi. Votre approche actuelle semble être la meilleure solution, même pour des listes de 10 000 éléments. Mettre en cache les IDs de la vue de la liste dans la session http et ensuite l'utiliser pour afficher le précédent/suivant (personnalisé pour l'utilisateur actuel). Cela fonctionne bien, surtout lorsqu'il y a trop de façons de filtrer et de trier la liste initiale d'éléments au lieu de seulement 3.
De plus, en stockant toute la liste d'identifiants, vous pouvez afficher une "you are at X out of Y" texte améliorant la convivialité.

Au fait, c'est ce que JIRA le fait également.

Pour répondre directement à vos questions :

• Oui, c'est une bonne pratique parce qu'elle évolue sans aucune complexité de code supplémentaire lorsque vos filtres/tri et types d'articles deviennent plus complexes. Je l'utilise dans un système de production avec 250 000 articles avec des variations de filtre/tri "infinies". Il est également possible de réduire à 1000 le nombre d'identifiants pouvant être mis en cache, car l'utilisateur ne cliquera probablement jamais plus de 500 fois sur "prev" ou "next" (il reviendra probablement en arrière pour affiner la recherche ou paginer).
• Je ne connais pas de meilleur moyen. Mais si les sortes étaient limitées et qu'il s'agissait d'un site public (sans session http), je dénormaliserais très probablement.
• Je ne sais pas.
• Oui, le triage du cache semble bon. Dans mon projet, je l'appelle "précédent/suivant sur les résultats de recherche" ou "navigation sur les résultats de recherche".
• Je ne sais pas.

Answer 5

En général, je dénormalise les données des index. Elles peuvent être stockées dans les mêmes lignes, mais je récupère presque toujours mes ID de résultat, puis je fais un voyage séparé pour les données. Cela rend la mise en cache des données très simple. Ce n'est pas si important en PHP où la latence est faible et la bande passante élevée, mais une telle stratégie est très utile lorsque vous avez une application à latence élevée et à bande passante faible, comme un site Web AJAX où une grande partie du site est rendue en JavaScript.

Je mets toujours en cache les listes de résultats et les résultats eux-mêmes séparément. Si quelque chose affecte les résultats d'une requête de liste, le cache des résultats de la liste est rafraîchi. Si quelque chose affecte les résultats eux-mêmes, ces résultats particuliers sont rafraîchis. Cela me permet de mettre à jour l'un ou l'autre sans avoir à tout régénérer, d'où une mise en cache efficace.

Comme mes listes de résultats changent rarement, je génère toutes les listes en même temps. Cela peut rendre la réponse initiale légèrement plus lente, mais cela simplifie le rafraîchissement du cache (toutes les listes sont stockées dans une seule entrée du cache).

Comme j'ai la liste entière en cache, il est trivial de trouver les éléments voisins sans avoir à revisiter la base de données. Avec un peu de chance, les données de ces éléments seront également mises en cache. C'est particulièrement pratique pour trier les données en JavaScript. Si j'ai déjà une copie en cache sur le client, je peux y recourir instantanément.

Pour répondre précisément à vos questions :

• Oui, c'est une excellente idée de connaître les voisins à l'avance, ou toute autre information que le client est susceptible de consulter ensuite, surtout si le coût est faible maintenant et que le coût de recalcul est élevé. Il s'agit alors d'un simple compromis entre le calcul préalable et le stockage supplémentaires et la vitesse.
• En termes de performances et de simplicité, évitez de lier des éléments qui sont logiquement différents. Les index et les données sont différents, sont susceptibles d'être modifiés à des moments différents (par exemple, l'ajout d'une nouvelle donnée affectera les index, mais pas les données existantes), et doivent donc être accédés séparément. Cela peut être légèrement moins efficace d'un point de vue monofilaire, mais chaque fois que vous liez quelque chose ensemble, vous perdez en efficacité de la mise en cache et en asychronie (la clé de la mise à l'échelle est l'asychronie).
• Le terme pour obtenir des données à l'avance est "pre-fetching". L'extraction préalable peut avoir lieu au moment de l'accès ou en arrière-plan, mais avant que les données extraites ne soient réellement nécessaires. Il en va de même pour le pré-calcul. Il s'agit d'un compromis entre le coût actuel, le coût de stockage et le coût à obtenir en cas de besoin.
• "Cache de triage" est un nom approprié.
• Je ne sais pas.

De même, lorsque vous mettez des choses en cache, mettez-les en cache au niveau le plus générique possible. Certaines choses peuvent être spécifiques à l'utilisateur (comme les résultats d'une requête de recherche), tandis que d'autres peuvent être agnostiques, comme la navigation dans un catalogue. Les deux peuvent bénéficier de la mise en cache. La requête de catalogue peut être fréquente et économiser un peu à chaque fois, et la requête de recherche peut être coûteuse et économiser beaucoup à quelques reprises.