Tirage aléatoire dans une table MySQL (solutions et questions)

[Toma]

Bonsoir,

Je fais ce post parce que ça intéressera peut-être certains (j'ai pas vraiment vu de solution clé en main sur le forum) mais aussi pour avoir d'éventuelles améliorations à ma méthode, et peut-être des réponses à mes interrogations. J'ai donc essayé trois méthodes pour faire un tirage aléatoire dans une table.


Méthode 1

J'avais l'habitude de faire une requête dans ce genre pour avoir une ligne aléatoire dans ma table :

$sql = "SELECT tous_les_champs_dont_j_ai_besoin
	FROM ma_table
	WHERE conditions
	ORDER BY rand()
	LIMIT 1";

$requet = mysql_query($sql);
$data = mysql_fetch_assoc($requet);

C'est une jolie solution en MySQL pur mais le temps d'exécution augmente grandement avec le nombre de lignes. Le ORDER BY rand() oblige MySQL à tirer un nombre aléatoire pour chaque ligne puis à les trier et enfin renvoyer la première. C'est très lourd et aucun index ne peut accélérer les choses. Il n'y a pas de cache MySQL possible.
J'ai fait un test avec 10 requêtes consécutives :
Temps première : 62ms
Temps suivantes : 62ms
Pour faire un vrai tirage aléatoire avec des lignes ayant des id non nécessairement consécutifs, on est obligé de passer par php.


Méthode 2

Ma première idée était de faire ça :

$sql = "SELECT tous_les_champs_dont_j_ai_besoin
	FROM ma_table
	WHERE conditions"; // On prend toutes les données de toutes les lignes

$requet = mysql_query($sql1);
	
$r = rand(0,mysql_num_rows($requet) - 1); // On tire une ligne au hasard
mysql_data_seek($requet, $r);
$data = mysql_fetch_assoc($requet);

Mais ici le temps gagné sur la requête (utilisation d'index et de cache par MySQL), on le perd sur le traitement du gros résultat avec toutes les lignes. La table ma_table est une table avec des champs text donc la récupération de toutes les lignes est très coûteuse. Ça peut être une bonne solution avec des lignes légères (sans texte et pas beaucoup de colonnes).
Temps première : 45ms
Temps suivantes : 45ms (Je comprends pas trop pourquoi il n'y a pas un cache qui accélère les requêtes suivantes...)


Méthode 3

Finalement, voilà comment je procède :

$sql0  = "SELECT id
	FROM ma_table
	WHERE conditions"; // On ne prend que les ids

$requet0 = mysql_query($sql0);

$r = rand(0,mysql_num_rows($requet0) - 1); // On tire une ligne au hasard
mysql_data_seek($requet0, $r);
$data0 = mysql_fetch_assoc($requet0);
$id = $data0['id'];

$sql = "SELECT tous_les_champs_dont_j_ai_besoin
	FROM ma_table
	WHERE id = '$id'"; // On va chercher toutes les données de la ligne dans la table
	
$requet = mysql_query($sql);
$data = mysql_fetch_assoc($requet);

Ici, la requête est rapide (avec index et cache) le volume de données est réduit au max (une colonne de int). Php tire un seul nombre aléatoire et la dernière requête est aussi extrêmement rapide (index et cache).
Temps première : 19ms
Temps suivantes : 0.7ms


La dernière solution est donc bien la plus rapide on gagne un facteur de 3 à 90 par rapport à la première solution.

J'ai juste une question concernant cette dernière méthode, pourquoi lorsque je recharge ma page de test, la première requête n'est pas plus rapide ? N'est-elle pas en cache ? Le cache mysql est-il propre à chaque connexion ?

N'hésitez pas à me dire s'il y a un truc qui va pas dans mes explications, ou si vous avez une méthode plus efficace.

 

[forty]

J'ai fait un test un jour et le plus rapide c'est de récupérer le nombre de ligne de la table et de faire un select limit avec un nombre aléatoire entre 0 et count( * ) détermine en php.

 

[duchnoun38]

Moi je dirais :


SELECT champ1,champ2,champ3
FROM (
SELECT @cnt := COUNT(*) + 1,
@lim := 1
FROM TA_TABLE
) vars
STRAIGHT_JOIN
(
SELECT r.*,
@lim := @lim - 1
FROM TA_TABLE r
WHERE (@cnt := @cnt - 1)
AND RAND() < @lim / @cnt
) tmp

c'est comme ca que je fais

 

[spout]

+1 Forty: http://www.electrictoolbox.com/msyql-alternative-order-by-rand/

 

[Toma]

Si j'ai bien compris Forty :

$sql0  = "SELECT COUNT(*)
	FROM ma_table
	WHERE conditions"; // On compte les lignes

$requet = mysql_query($sql4);
$row = mysql_fetch_array($requet);
$offset = rand(0,$row[0] - 1); On tire un offset aléatoire

$sql = "SELECT tous_les_champs_dont_j_ai_besoin
	FROM ma_table
	WHERE conditions
	LIMIT $offset, 1"; // On va chercher toutes les données de la ligne dans la table
	
$requet = mysql_query($sql);
$data = mysql_fetch_assoc($requet);

J'ai testé, ça donne :
Temps première : 20ms et plus
Temps suivantes : 13ms en moyenne

Les temps sont très dépendants de l'offset, plus il est élevé, plus c'est long. Ma table de test fait 10 000 lignes, avec 100 000 lignes ça doit être vraiment élevé en moyenne. Ça vient de la façon dont l'offset est géré par MySQL (http://www.electrictoolbox.com/mysql-limit-slow-large-offset/). Du coup, j'ai l'impression que ma méthode reste un peu plus rapide.

@duchnoun38 : honnêtement, j'ai pas compris. Mais je suis pas un expert MySQL. :?

 

[duchnoun38]

deux requete qui crée une table, jusque là ca bouffe pas de temp,
la premiere recup la taille de la table et definit aussi le nombre
de valeur que tu veux,
la deuxieme, se sert utilise la colonne crée pour faire le rand via le where...
donc pas de rand crée pour "chaque ligne".

On peut utiliser "explain extended" pour comprendre

Toma, tu peux tester ma requete sur ta table de test ?
(en remplacant TA_TABLE et champ1,champ2,champ3)

 

[Leonick]

je ne comprends pas pourquoi tu parles de n requêtes successives ? si tu veux n lignes au hasard, ton select avec rand() et un limit n devrait suffire
éventuellement, si ta table est trop grosse, tu peux extraire une table temporaire avec juste les champs qui t'intéressent et faire ton rand() dessus

 

[Toma]

En fait Leonick, les requêtes successives c'est juste pour le test, pour pouvoir moyenner les temps. J'ai juste vu que dans certains cas la première est plus longue que les suivantes alors j'annonçais les temps séparément. Et je n'ai d'ailleurs pas vraiment compris pourquoi (ça peut pas vraiment être un cache mysql, peut-être un cache entre mysql et php ? Je sais même pas si ça existe...)
Le but est bien de tirer une seule ligne.

duchnoun38, ok je vais voir si j'arrive à comprendre.

 

[Toma]

Ok, j'ai pas vraiment compris mais j'ai réussi à faire marcher ton truc duchnoun38

$sql  = "SELECT tous_les_champs_dont_j_ai_besoin
FROM (
	SELECT @cnt := COUNT(*) + 1, @lim := 1
	FROM ma_table
	WHERE conditions
) vars
STRAIGHT_JOIN
(
	SELECT tous_les_champs_dont_j_ai_besoin, @lim := @lim - 1
	FROM ma_table
	WHERE conditions AND (@cnt := @cnt - 1) AND RAND() < @lim / @cnt
) tmp";

$requet = mysql_query($sql);
$data = mysql_fetch_assoc($requet);

Du coup comme temps j'ai 53ms en moyenne. Donc ça semble pas plus efficace. Après j'ai peut-être mal adapté à mon cas particulier. Je précise aussi que ma_table est issue d'une jointure. J'ai aussi rajouté mes conditions car je ne sélectionne pas toutes les lignes de la table.

Finalement, je n'arrive pas à expliquer pourquoi j'ai des temps si différents entre la première requête et les suivantes seulement avec ma méthode 3 (des requêtes faites à la suite dans une boucle for). Si on ne prend en compte que la première pour cette méthode, ça donne 19ms et la méthode de Forty 15ms en moyenne (j'ai refait des mesures). Donc avec ce raisonnement celle de Forty serait plus rapide. (même si j'ai le sentiment que avec un plus grand nombre de lignes elle traînerait un peu la patte)

 

[duchnoun38]

Moi pour ma part avec ce genre de requete, sur une table à 80 000 enregistrement,

Je passe de 2.3 seconde à 0.40ms 8)

 

[Zecat]

J'aurais une approche à te proposer (un peu hérétique mais surement efficace) :

1 - tu maintiens au cours de la gestion de ta table un document nommé disons "map.txt" pré-sizé disons à 1 million d'octets avec 1 octets par fiche qui contient 0 si la fiche n'existe pas (supprimées ou pas encore crée).

2 - pour ton tirage aleatoire tu fait ensuire un simple rand et tu va lire juste l'octet concerné. si 1 tu peux aller lire le record concerné dans la base de données. Si 0 tu refais un autre rand ...

Intérêt en 1 : En pré-sizant le doc, la gestion se limite a positionner un 1 sur un octet d'offset connu (temps d'execution marginal). La lecture "si fiche existe" est elle aussi marginal en terme de temps puisque juste la lecture d'un octet.

Interet en 2 : tu n'as plus aucune requete a optimiser dans mysql mais juste un acces direct à un record suite à un rand (temps la aussi marginal).

Note : si tu veux reduire la taille du doc, tu peux travailler au niveau du bit (donc reduction par 8) mais bon ca complqiue beaucoup le code (qui sinon reste ultra simple) et tu payes le gain de place par un temps d'accès au bit plus long que l'accès direct à l'octet (donc à mon avis complication inutile).

J'ai pas fait de tests mais à la lumière d'exprience passée utlisant ce type de technique, je suis sur que tes temps doivent descendre à du 0,000n s :wink:

 

[oliquide]

Je n'ai pas tout compris à la requête de duchnoun38,
Mais ça marche super bien !
5 s, là où l'interface phpMyAdmin déconnectait sur un timeout !

Merci