Sélectionner un élément au hasard dans une table MySQL

Details: Written by Neamar; Category: Articles du blog; Created: 14 May 2010; Last Updated: 06 August 2013

Sur la plupart des sites dits « 2.0 », vous trouverez quelque part un petit module « Un article au hasard », et un « Dernier article ».

Souvent, le programmeur derrière ne se pose malheureusement pas de questions pour récupérer cet enregistrement… et pourtant, il devrait ! Car selon les méthodes utilisées et la taille de la table, il peut améliorer sa requête de plusieurs ordres de grandeur.

On est parti pour voir ça…

Protocole de test

Tables

J'effectue les tests sur une table moyennement chargée (10 000 enregistrements) nommée BENCH_Table dans la suite, simulant une bonne base d'articles.
Les calculs se font sur la colonne ID, qui est notée comme PRIMARY auto_increment.

Requêtes SQL

`BENCHMARK`

Pour tester les requêtes SQL présentées ici, je me suis servi de l'instruction BENCHMARK qui permet de calculer plusieurs fois une expression.

Pour cet article, j'ai effectué les requêtes 10 000 000 de fois, sauf contre-ordre (dans certains cas vraiment peu optimisés, il aurait fallu des heures de calcul, montrant l'inadéquation de la solution). Cette valeur assez large permet d'obtenir un résultat fiable.

Petit exemple de requête avec BENCHMARK :

--Répéter 10 000 000 de fois la récupération du titre de l'élément 5
SELECT BENCHMARK(10000000,(

SELECT Titre
FROM BENCH_Table
WHERE ID = 5
))

Attention ! BENCHMARK renvoie toujours 0. Pour récupérer le temps de la requête, il faut utiliser autre chose : le client MySQL en ligne de commande par exemple, qui affiche le temps passé.

`EXPLAIN`

Pour justifier le temps obtenu et l'expliquer, j'utiliserai EXPLAIN, une instruction indispensable pour les gestionnaires de base de données qui affiche le schéma prévu par le compilateur. Une requête EXPLAIN n'exécute pas la demande, mais la compile et affiche les plans de l'exécuteur (je simplifie). EXPLAIN est un vaste sujet, je n'entrerai pas dans le détail et décrirai uniquement les résultats obtenus au cours des tests. Pour un cours complet sur EXPLAIN, RTFM !

Petit exemple de requête avec EXPLAIN :

EXPLAIN SELECT Titre
FROM BENCH_Table
WHERE ID = 5

Et le résultat :

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	BENCH_Table	const	PRIMARY	PRIMARY	4	const	1

Sélectionner un élément aléatoire

C'est sûrement la partie la plus intéressante… mais aussi la plus délaissée par les webmasters !

Présentation de RAND()

Dès que l'on parle d'aléatoire, on aura besoin d'une fonction génératrice de nombres pseudo-aléatoires. En MySQL, il s'agit de l'instruction RAND(), classée avec les fonctions mathématiques. RAND() renvoie un nombre aléatoire flottant entre 0 et 1 (1 non compris).

Sélectionner un élément aléatoire

Si vous vous promenez un peu sur les forums, c'est toujours la même solution qui est donnée :

--Tri par rand
SELECT ID FROM BENCH_Table
ORDER BY RAND()
LIMIT 1

C'est logique : on trie aléatoirement et on ne récupère que le premier élément. Sauf que… c'est long, très long : sur la table de tests décrite ci-dessus, il faut 7,6 secondes pour effectuer 1 000 calculs. Si j'avais pris les 100 000 000 prévus, on serait donc à 21 heures de calcul… presque une journée !
Pourquoi est-ce si long ? Il va falloir jouer du EXPLAIN :

EXPLAIN SELECT ID FROM BENCH_Table
ORDER BY RAND()
LIMIT 1

Que voit-on dans la colonne Extra ? « Using index ; Using temporary ; Using filesort ». Ouch, expliquons un peu.

« Using index » : ça c'est bien ; on n'utilise que le fichier d'index. Bon, sur une vraie requête, il y a de fortes chances que vous récupériez autre chose que l'ID (par exemple, le titre de l'article sélectionné aléatoirement) auquel cas cet avantage disparaîtra ; sauf si votre index contient ID et Titre.
« Using temporary » : ah, moins bien. Pour calculer les résultats, MySQL est obligé de créer une table temporaire – ici, qui contient les valeurs attribuées par RAND() à chaque colonne.
« Using filesort » : il va y avoir une phase de tri supplémentaire à la fin pour classer les lignes.

On comprend mieux : lors de l'exécution, MySQL va ajouter à chaque ligne une colonne contenant la valeur de RAND() (soit 10 000 nouvelles valeurs), puis trier sur cette colonne et ne récupérer que le plus petit résultat.
Faut-il dire en quoi c'est stupide ? Trier est une opération coûteuse (au mieux en O(n × log(n))), alors qu'on ne veut récupérer qu'un élément et qu'on se fiche d'avoir une table triée. C'est un peu comme si en PHP vous faisiez ceci pour récupérer la plus petite valeur d'un tableau :

Mais, comment faire alors ? Hé bien, on réfléchit. Allez allez, on se creuse un peu la tête…
Déjà, on ne veut plus de ORDER BY. C'est une perte de temps et de mémoire pour ce qui nous intéresse…
La première idée, c'est de ruser avec une sub-query, un SELECT à l'intérieur de SELECT.

Par exemple :

--Sélection d'un élément
SELECT ID
FROM BENCH_Table
WHERE ID =
	(
	SELECT CEIL( COUNT(*) * RAND( ) )
	FROM BENCH_Table
	)

À priori, c'est bien ! On calcule la sous-requête, on obtient alors un nombre aléatoire entier, et on récupère cet ID. Comme on récupère à partir d'un index, l'opération « = » sera extrêmement rapide et tout devrait aller pour le mieux.
Sauf que… exécuter une seule fois cette requête demande 14s ! Tu parles d'une amélioration… qu'est ce qui a bien pu se passer ? Encore une fois, EXPLAIN est notre ami :

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	BENCH_TABLE	index	NULL	PRIMARY	4	NULL	10000	Using where; Using index
2	UNCACHEABLE SUBQUERY	BENCH_TABLE	index	NULL	PRIMARY	4	NULL	10000	Using index

La deuxième ligne nous informe de notre erreur : UNCACHEABLE SUBQUERY. Autrement dit, il va falloir recalculer la sous-requête sur chaque ligne ! (Une bref lecture du manuel sur la page « How the query cache operates » aurait pu nous renseigner : la présence d'un RAND() empêche la mise en cache. )

Forcément, calculer un CEIL( COUNT( * ) * RAND( ) ) sur 10 000 lignes, c'est coûteux…

J'ai un peu cherché comment forcer la mise en cache d'une requête, sans résultat. Alors j'ai arrêté de pleurnicher, et j'ai fait fonctionner à nouveau la matière grise.
L'idée ? Utiliser un JOIN. On sélectionne une valeur aléatoire dans ce JOIN, et on joint notre table dessus. Pour ceux qui ne seraient pas familiers avec les différentes jointures, précisons que JOIN fonctionne « des deux côtés » : c'est une sorte de fonction « intersection », contrairement à un LEFT JOIN / RIGHT JOIN qu'on pourrait qualifier d'« union » – oui, je simplifie, mais encore une fois ce n'est pas le but de l'article.

Donc, un JOIN :

--Jointure de l'élément
SELECT ID
FROM BENCH_Table
JOIN
	(
	SELECT FLOOR( COUNT( * ) * RAND( ) ) AS ValeurAleatoire
	FROM BENCH_Table
	) AS V ON BENCH_Table.ID = V.ValeurAleatoire

Cette fois, les performances sont au rendez-vous : sur 10 000 000 de tests, on ne monte qu'à 1,278s (à comparer avec la presque-journée de la première solution).

Un petit EXPLAIN pour la route :

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	<derived2>	system	NULL	NULL	NULL	NULL	1
1	PRIMARY	BENCH_Table	const	PRIMARY	PRIMARY	4	const	1	Using index
2	DERIVED	BENCH_Table	index	NULL	PRIMARY	4	NULL	8352	Using index

Ce qui est intéressant ici, c'est la colonne type :

« system » : c'est le mieux qu'on puisse rêver, la table n'a qu'une seule ligne.
« const » : ici aussi, il n'y a qu'une seule ligne qui sera calculée au tout début de la requête. Notez que si on n'avait pas de contraintes PRIMARY (ou UNIQUE) l'optimiseur ne pourrait rien dire et serait obligé de lire.
« index » : c'est moins superbe, il faut lire chaque ligne – mais on utilise un index, ce qui accélère les choses.

Par acquit de conscience, j'ai testé avec COUNT(*) et MAX(ID) (je suis en InnoDB, ça a peut-être son importance) : le résultat est mieux avec COUNT(*). À la réflexion, ça paraît logique vu que MAX(ID) est obligé de lire toutes les lignes et de comparer à chaque fois avec le maximum courant. Je pensais cependant qu'il suffisait de lire la dernière ligne du fichier d'index… à priori non donc.

Note sur les tables « creuses »

Les techniques exposées ici fonctionnent parfaitement si vous ne supprimez pas de lignes de votre table.
Sinon, vous risquez d'avoir un problème et de ne récupérer aucune ligne (cas V.ValeurAleatoire = un_index_supprimé). Il faut modifier légèrement la requête pour prendre en compte ce genre de cas :

--Jointure de l'élément avec gestion des index supprimés
--La différence ? LA jointure se fait sur >=, et pas sur =
SELECT ID
FROM BENCH_Table
JOIN
	(
	SELECT FLOOR( COUNT( * ) * RAND( ) ) AS ValeurAleatoire
	FROM BENCH_Table
	) AS V ON BENCH_Table.ID >= V.ValeurAleatoire
LIMIT 1

Forcément, ça ira un peu moins vite (20 secondes, une bonne perte quand même)…

Et dans le futur

Forcément, on se prend à rêver de pouvoir exécuter le code suivant :

--Code imaginaire, NE FONCTIONNE PAS
SELECT ID
FROM BENCH_Table
LIMIT FLOOR( COUNT( * ) * RAND( ) ),1

Mais ce n'est pas pour tout de suite… dommage !

Encore une idée

On peut aussi coupler deux langages (on choisit un enregistrement en PHP/Whatever, puis on le récupère) ou avec des variables SQL :

--Utilisation d'une variable aléatoire
SELECT @ValeurAleatoire := (RAND() * COUNT(*)) FROM BENCH_Table;
SELECT ID FROM BENCH_Table WHERE ID = @ValeurAleatoire;

Mais là, je ne peux pas benchmarker ! En théorie, ça marche…

Récupérer le dernier élément

Deuxième section donc, pour récupérer le dernier élément.

C'est encore plus simple que pour le RAND(), et les trois approches décrites ci-dessus sont possibles :

--Sous requête
SELECT ID
FROM BENCH_Table
WHERE ID =
	(
	SELECT MAX( ID )
	FROM BENCH_Table
	)

--Tri ID DESC
SELECT ID
FROM BENCH_Table
ORDER BY ID DESC
LIMIT 1

--Jointure
SELECT ID
FROM BENCH_Table
JOIN (SELECT MAX(ID) AS Max FROM BENCH_Table) AS M ON M.Max = BENCH_Table.ID

Les résultats sont dans un mouchoir de poche : 356ms pour la sous-requête, 366ms pour le tri décroissant, et 441ms.

Si la sous-requête fonctionne bien ici, c'est parce qu'elle peut être mise en cache et n'a pas à être recalculée à chaque ligne. Un EXPLAIN nous indique « Select tables optimized away ».

Le tri décroissant lui se fait sur un index (« using index »), ce qui explique sa vélocité.

La jointure est un peu défavorisée (trois jointures) et devraient donc être oubliée pour ce cas particulier.

Conclusion

En conclusion : pour un élément aléatoire, ne pas utiliser ORDER BY RAND() ! En revanche, pour récupérer le dernier élément tout se vaut à peu près niveau temps de calcul. Pour la mémoire, c'est une autre paire de manches !

Et surtout, réfléchir à ce qu'on veut et ce qui est fait : la distinction est importante !