Échantillons aléatoires simples à partir d'une base de données Sql

Question

Comment prendre un échantillon aléatoire simple efficace en SQL ? La base de données en question fonctionne sous MySQL ; ma table compte au moins 200 000 lignes, et je veux un échantillon aléatoire simple d'environ 10 000.

La réponse "évidente" est de :

SELECT * FROM table ORDER BY RAND() LIMIT 10000

Pour les grandes tables, c'est trop lent : il faut appeler RAND() pour chaque ligne (ce qui le place déjà à O(n)), et les trie, ce qui le rend O(n lg n) au mieux. Existe-t-il un moyen de faire cela plus rapidement que O(n) ?

Note : Comme Andrew Mao le souligne dans les commentaires, si vous utilisez cette approche sur SQL Server, vous devez utiliser la fonction T-SQL NEWID() parce que RAND() peut retourner la même valeur pour tous les rangs .

EDIT : 5 ANS PLUS TARD

J'ai rencontré ce problème à nouveau avec une table plus grande, et j'ai fini par utiliser une version de la solution de @ignorant, avec deux modifications :

• Échantillonner les rangs de 2 à 5 fois la taille de l'échantillon souhaité, afin de réduire les coûts. ORDER BY RAND()
• Sauvegarder le résultat de RAND() à une colonne indexée à chaque insertion/mise à jour. (Si votre ensemble de données n'est pas très chargé en mises à jour, vous devrez peut-être trouver un autre moyen de garder cette colonne fraîche).

Pour prendre un échantillon de 1000 articles d'une table, je compte les lignes et échantillonne le résultat jusqu'à, en moyenne, 10 000 lignes avec la colonne frozen_rand :

SELECT COUNT(*) FROM table; -- Use this to determine rand_low and rand_high

  SELECT *
    FROM table
   WHERE frozen_rand BETWEEN %(rand_low)s AND %(rand_high)s
ORDER BY RAND() LIMIT 1000

(Mon implémentation réelle implique plus de travail pour s'assurer que je ne sous-échantillonne pas, et pour envelopper manuellement rand_high, mais l'idée de base est "réduire aléatoirement votre N à quelques milliers").

Bien que cela implique quelques sacrifices, cela me permet d'échantillonner la base de données à l'aide d'un balayage d'index, jusqu'à ce qu'elle soit suffisamment petite pour que je puisse l'utiliser. ORDER BY RAND() encore.

Answer 1

Je pense que la solution la plus rapide est

select * from table where rand() <= .3

Voici pourquoi je pense que cela devrait faire l'affaire.

• Il créera un numéro aléatoire pour chaque ligne. Le nombre est compris entre 0 et 1
• Il évalue s'il faut afficher cette ligne si le nombre généré est compris entre 0 et .3 (30%).

Cela suppose que rand() génère des nombres selon une distribution uniforme. C'est le moyen le plus rapide de le faire.

J'ai vu que quelqu'un avait recommandé cette solution et qu'elle avait été rejetée sans preuve.

• C'est O(n) mais aucun tri n'est nécessaire, donc c'est plus rapide que la méthode O(n lg n).

• mysql est très capable de générer des numéros aléatoires pour chaque ligne. Essayez ceci -

  select rand() from INFORMATION_SCHEMA.TABLES limit 10 ;

Comme la base de données en question est mySQL, c'est la bonne solution.

Answer 2

Il y a une discussion très intéressante sur ce type de question ici : http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/

Je pense qu'avec absolument aucune hypothèse sur la table, votre solution O(n lg n) est la meilleure. Bien qu'en fait, avec un bon optimiseur ou une technique légèrement différente, la requête que vous indiquez pourrait être un peu meilleure, O(m*n) où m est le nombre de lignes aléatoires souhaitées, car elle n'aurait pas nécessairement à trier l'ensemble du grand tableau, elle pourrait juste rechercher les m plus petites fois. Mais pour le genre de nombres que vous avez affichés, m est de toute façon plus grand que lg n.

Trois hypothèses que nous pourrions essayer :

1. il y a une clé primaire unique, indexée, dans la table

2. le nombre de lignes aléatoires que vous voulez sélectionner (m) est beaucoup plus petit que le nombre de lignes dans le tableau (n)

3. la clé primaire unique est un nombre entier compris entre 1 et n sans discontinuité.

Avec seulement les hypothèses 1 et 2, je pense que cela peut être fait en O(n), bien que vous ayez besoin d'écrire un index complet de la table pour répondre à l'hypothèse 3, donc ce n'est pas nécessairement un O(n) rapide. Si nous pouvons SUPPLEMENTAIREMENT supposer quelque chose d'agréable à propos de la table, nous pouvons faire la tâche en O(m log m). L'hypothèse 3 serait une propriété supplémentaire facile à travailler. Avec un bon générateur de nombres aléatoires qui garantit l'absence de doublons lors de la génération de m nombres à la suite, une solution O(m) serait possible.

Compte tenu des trois hypothèses, l'idée de base est de générer m nombres aléatoires uniques entre 1 et n, puis de sélectionner les lignes avec ces clés dans la table. Je n'ai pas mysql ou quoi que ce soit d'autre sous les yeux pour l'instant, donc en pseudo-code léger cela ressemblerait à quelque chose comme :

create table RandomKeys (RandomKey int)
create table RandomKeysAttempt (RandomKey int)

-- generate m random keys between 1 and n
for i = 1 to m
  insert RandomKeysAttempt select rand()*n + 1

-- eliminate duplicates
insert RandomKeys select distinct RandomKey from RandomKeysAttempt

-- as long as we don't have enough, keep generating new keys,
-- with luck (and m much less than n), this won't be necessary
while count(RandomKeys) < m
  NextAttempt = rand()*n + 1
  if not exists (select * from RandomKeys where RandomKey = NextAttempt)
    insert RandomKeys select NextAttempt

-- get our random rows
select *
from RandomKeys r
join table t ON r.RandomKey = t.UniqueKey

Si vous étiez vraiment soucieux de l'efficacité, vous pourriez envisager de faire la génération de clés aléatoires dans une sorte de langage procédural et d'insérer les résultats dans la base de données, car presque tout autre langage que SQL serait probablement plus efficace pour le type de boucles et de génération de nombres aléatoires requis.

Answer 3

Apparemment, dans certaines versions de SQL, il existe une fonction TABLESAMPLE mais elle n'est pas présente dans toutes les implémentations de SQL (notamment Redshift).

http://technet.microsoft.com/en-us/library/ms189108(v=sql.105).aspx

Answer 4

Il suffit d'utiliser

WHERE RAND() < 0.1 

pour obtenir 10% des enregistrements ou

WHERE RAND() < 0.01 

pour obtenir 1% des enregistrements, etc.

Answer 5

Partant de l'observation que l'on peut récupérer les identifiants d'une table (par exemple, le nombre 5) à partir d'un ensemble :

select *
from table_name
where _id in (4, 1, 2, 5, 3)

nous pouvons arriver à la conclusion que si nous pouvions générer la chaîne de caractères "(4, 1, 2, 5, 3)" alors nous aurions un moyen plus efficace que RAND() .

Par exemple, en Java :

ArrayList<Integer> indices = new ArrayList<Integer>(rowsCount);
for (int i = 0; i < rowsCount; i++) {
    indices.add(i);
}
Collections.shuffle(indices);
String inClause = indices.toString().replace('[', '(').replace(']', ')');

Si les ids ont des lacunes, alors la liste de tableaux initiale indices est le résultat d'une requête sql sur les identifiants.