Federico Razzoli

Dernière mise à jour le 8 décembre 2019

Retourner des lignes aléatoires dans un ordre aléatoire à partir d’une base de données relationnelle est un problème très difficile. Dans cet article, nous verrons un anti-modèle, nous discuterons pourquoi ce problème est si difficile, et nous examinerons quelques solutions imparfaites.

MISE À JOUR : Certains SGBD supportent TABLESAMPLE. Je ne l’ai pas mentionné parce que jusqu’à aujourd’hui, je ne connaissais que l’implémentation de SQL Server, et je ne la considère pas comme bonne pour extraire des lignes aléatoires (je vais expliquer pourquoi). Mais après une question posée sur Facebook par Daniël van Eeden, j’ai fait quelques recherches et j’ai découvert que l’implémentation de PostgreSQL pourrait être beaucoup plus adaptée. Je vais encore lire sur ce sujet et l’essayer, puis j’écrirai probablement un deuxième article à ce sujet. De toute façon, MySQL et MariaDB ne supportent pas TABLESAMPLE.

La mauvaise façon : ORDER BY RAND()

De nombreux développeurs pensent qu’ils peuvent le faire de cette façon :

SELECT some_columns FROM some_table ORDER BY RAND() LIMIT 10;

C’est la seule requête qui fait exactement ce qui est attendu. Si la fonction RAND() est aléatoire de manière fiable, elle renvoie un ensemble aléatoire de lignes, où chaque ligne a les mêmes chances d’être renvoyée.

Le problème est de savoir comment cela fonctionne sous le capot. Pour ordonner des valeurs aléatoires, il faut d’abord les créer. Pour créer une valeur aléatoire pour chaque ligne d’une table, un SGBD doit lire chaque ligne. Donc le SGBD va faire une opération en deux étapes:

1. Copier les lignes plus une valeur aléatoire dans une table temporaire, espérons-le en mémoire;
2. Ordonner les lignes dans la table temporaire.

Notez ce détail : espérons-le en mémoire. Selon le SGBD, il peut y avoir des raisons pour lesquelles la table doit être créée sur le disque. Typiquement, cela se produit si la table est trop grande. Les anciennes versions de MySQL créent également des tables temporaires sur le disque si elles contiennent TEXT ou BLOB colonnes.

Il va sans dire que si la table est grande, c’est une opération lente qui consomme beaucoup de ressources.

Pourquoi les SGBD relationnels ne fournissent-ils pas un moyen intégré de renvoyer des lignes aléatoires ?

Les bases de données relationnelles sont construites autour d’une branche des mathématiques appelée algèbre relationnelle. Elle est basée sur la logique, car elle traite des prédicats vrai/faux ; et similaire à la théorie des ensembles, même si une relation est quelque chose de plus complexe qu’un ensemble, et même la voir comme une table n’est pas mathématiquement correcte. Cet article est un bel exemple de ce que je veux dire, mais il existe des arguments plus complexes.

Malgré que SQL ne soit pas une implémentation précise du modèle relationnel, son algèbre est utilisée comme référence. Comme toutes les branches des mathématiques, il possède un ensemble bien défini d’opérations. Obtenir des tuples aléatoires à partir d’une relation n’en fait définitivement pas partie.

Cette réponse semble un peu trop théorique, non ? ORDER BYet les tables sans clé primaire violent également les règles de l’algèbre relationnelle, mais SQL les supporte.

Cependant, pour les bases de données, la vitesse est vitale. Les SGBD relationnels sont conçus pour effectuer des opérations relationnelles très rapidement. Évidemment, une structure de données conçue pour optimiser certaines opérations n’est pas optimisée pour d’autres opérations. Ainsi, les SGBD relationnels ne sont pas optimisés pour les recherches aléatoires.

Il devrait être évident que le fait de boucler sur les lignes pour en choisir certaines au hasard serait lent. Théoriquement, la lecture d’une ligne aléatoire à l’aide d’un index serait aussi rapide que la recherche d’une ligne par la valeur de la clé primaire. Mais alors, différentes lignes auraient différentes chances d’être choisies.

L’image ci-dessus provient d’un dépôt GitHub de Jeremy Cole, innodb_diagrams. Tôt ou tard, je devrais écrire sur ses projets d’analyse des structures de données InnoDB.

Ce qui est important ici, c’est qu’un index est un arbre dont les nœuds sont des pages de mémoire. Les nœuds feuilles contiennent les données réelles ; les niveaux supérieurs ne contiennent que les informations nécessaires pour choisir le chemin le plus court vers le nœud feuille désiré. Les détails ne sont pas importants dans ce contexte.

Le SGBD pourrait théoriquement choisir une page aléatoire en effectuant une série de décisions aléatoires : vais-je aller à gauche ou à droite ? Mais alors, les pages feuilles contiennent un nombre variable de lignes. Elles pourraient même être vides. Ainsi, différentes lignes auraient différentes chances d’être sélectionnées.

Le résultat est clairement en dehors des cas d’utilisation prévus des SGBD ; et il peut être lent ou erroné, selon qu’un index est utilisé ou non. Les SGBDs ont choisi à juste titre de ne pas implémenter cette fonctionnalité.

Certaines solutions

Il n’y a pas de solutions parfaites. Il y a des solutions qui peuvent être acceptables mais qui présentent des inconvénients. Il faut en choisir une au cas par cas.

Choisir au hasard dans une plage

Cette solution est applicable aux tables qui ont une clé primaire autoincrémentale. C’est la plus simple à mettre en œuvre, mais une clé primaire « fragmentée » pose des problèmes.

Elle consiste à vérifier l’id minimum, l’id maximum, et à générer un nombre aléatoire dans cette plage:

Non pas que les requêtes avec MIN() et MAX() sur n’importe quel index, sans autres clauses, soient très rapides.

Le résultat est une ligne vraiment aléatoire. Pour choisir plus d’une ligne, nous pouvons répéter cette requête plusieurs fois. Cela nous amène à deux inconvénients :

• Si cette opération est effectuée souvent, nous pourrions exécuter cette requête un grand nombre de fois.
• Il n’y a aucune garantie que la même ligne ne soit pas sélectionnée plusieurs fois. Si cela se produit, l’application peut réessayer la requête. Si la table est grande, cet événement est rare et nous pouvons l’ignorer – à moins que la RAND()fonction ne soit pas fiable. Mais pour les petites tables, cela peut être un problème.

De plus, une clé primaire peut avoir des trous – en d’autres termes, certains chiffres peuvent manquer. Cela est dû aux suppressions et aux transactions qui ont échoué. Les nombres inférieurs au maximum ne sont pas réutilisés. Pour contourner ce problème, nous pouvons utiliser deux techniques.

Utiliser >=

Si nous utilisons l’opérateur >= dans la clause WHERE, la requête retournera toujours une ligne. Si le numéro généré n’est pas présent, le suivant sera utilisé. Mais cela signifie que les valeurs situées immédiatement après un trou auront plus de chances d’être sélectionnées. Plus le trou est grand, plus les chances sont élevées.

Vous pouvez penser que vous ne devriez pas vous soucier de cela, et vous avez probablement raison. Mais avant que votre décision ne soit définitive, considérez la possibilité d’un grand trou.

Travailler dur

Si la requête ne renvoie aucune ligne, nous pouvons simplement réessayer. Pour les grandes tables avec seulement quelques petits trous, c’est parfaitement bien. Mais pour les grandes tables avec de nombreux trous, ou de gros trous, cette technique pourrait consommer trop de ressources.

Veuillez ne pas être trop paranoïaque à ce sujet. Faites simplement quelques calculs. Quel est le ratio de valeurs manquantes dans votre table ? Cela vous indique combien de fois la requête sera retentée, en moyenne.

Sélectionner plusieurs lignes

Pour sélectionner plusieurs lignes avec cette technique, nous pouvons :

• Répéter la requête plusieurs fois;
• Ou, pour de meilleures performances, utiliser l’opérateur >= et utiliser un LIMIT supérieur à un. Cela rend cependant les résultats beaucoup moins aléatoires.

Déplacer le choix aléatoire vers l’application

Dans sa forme la plus simple, cette technique consiste à choisir aléatoirement un bloc d’id contigus. L’application choisira aléatoirement ceux qu’elle utilisera, puis sélectionnera les lignes correspondantes.

Supposons que vous vouliez choisir parmi des blocs de 1000 valeurs:

Plus le bloc est grand, plus vous consommez de ressources, plus le résultat est aléatoire. L’application a la responsabilité de choisir des id uniques existants aléatoires à partir des blocs, il ne devrait donc jamais y avoir besoin de réessayer une requête.

La variante MOD

Un problème avec cette technique est que les lignes sont retournées à partir du même bloc d’id contigus. Cela pourrait être parfaitement acceptable, surtout si le bloc est grand. Mais s’il ne l’est pas, nous pourrions ajouter une certaine complexité pour sélectionner un bloc de lignes non contiguës.

L’idée de cette variante est de :

• Définir des macro-blocs de lignes majoritairement non contiguës;
• Choisir aléatoirement un macro-bloc;
• Retourner un bloc de celui-ci.

Pour ce faire, nous pouvons calculer le module de l’id, et l’utiliser pour sélectionner des résultats aléatoires. Par exemple, nous pouvons définir une colonne virtuelle indexée avec une expression comme (id MOD 4). Chaque ligne aura une valeur comprise entre 0 et 3. Même s’il y a des trous, les lignes de ces macro-blocs seront pour la plupart non-contiguës et elles devraient avoir approximativement le même nombre.

L’application doit générer un nombre aléatoire entre 0 et 3. Ensuite, pour sélectionner des blocs à partir de ces macro-blocs :

SET @block_size := 1000;SELECT id FROM some_table WHERE id_mod = FLOOR(RAND() * 3) ORDER BY id LIMIT @block_size;

Une façon similaire de mettre en œuvre cette idée est d’utiliser des partitions, où la fonction de partitionnement est le module de l’id. Je ne le suggérerais que si la table bénéficie du partitionnement pour d’autres raisons.

Choisir une technique

Les techniques de bloc exécutent plus de requêtes par rapport à la première avec l’opérateur >=, et le résultat pourrait être meilleur ou non. Par rapport à la variante de répétition, cela pourrait exécuter plus ou moins de requêtes, et le résultat est pire.

Généralement, les techniques de bloc sont meilleures si nous avons des trous dans la clé primaire.

Mise en cache de séries aléatoires

Les méthodes précédentes sont un compromis : performance contre meilleur aléatoire, où la solution plus rapide est aussi plus complexe à mettre en œuvre. Tant que nous n’utilisons pas l’anti-modèle ORDER BY RAND(), la sélection de lignes aléatoires ne devrait pas poser de problèmes de performance. Mais que se passe-t-il si c’est le cas ?

Nous pourrions mettre en cache des identifiants triés au hasard obtenus avec l’une des solutions précédentes. Nous pourrions utiliser une requête comme celle-ci (syntaxe MySQL):

Nous pourrions utiliser les séries en ordre croissant ou décroissant, de manière aléatoire. Ou l’application pourrait les mélanger.

Problèmes:

• Lorsqu’un élément est ajouté, nous devrions choisir au hasard s’il doit être inséré dans une série, en remplaçant un élément aléatoire.
• Lorsqu’un élément est supprimé, nous devrions le supprimer de toutes les séries. Il devrait être remplacé par un autre élément aléatoire.
• Nous pourrions vouloir périodiquement supprimer les séries les plus anciennes et les remplacer par de nouvelles, afin d’améliorer le caractère aléatoire de l’expérience utilisateur.

Conclusions

Comme d’habitude, veuillez commenter et me faire savoir si vous repérez une erreur dans cet article, si vous n’êtes pas d’accord sur quelque chose, si vous me faites part de votre expérience personnelle, ou si vous avez d’autres idées à ajouter.