Comment puis-je prendre un échantillon aléatoire simple et efficace en SQL? La base de données en question exécute MySQL; ma table comporte 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 appelle RAND()chaque ligne (ce qui la met déjà à O (n)), et les trie, ce qui en fait au mieux O (n lg n). Existe-t-il un moyen de le faire plus rapidement que O (n)?

Remarque : comme Andrew Mao le souligne dans les commentaires, si vous utilisez cette approche sur SQL Server, vous devez utiliser la fonction T-SQL NEWID(), car RAND () peut renvoyer la même valeur pour toutes les lignes .

EDIT: 5 ANS PLUS TARD

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

• Échantillonnez les lignes jusqu'à 2 à 5 fois la taille de l'échantillon souhaitée, à un prix avantageux ORDER BY RAND()
• Enregistrez le résultat de RAND()dans une colonne indexée à chaque insertion / mise à jour. (Si votre ensemble de données ne nécessite pas beaucoup de mises à jour, vous devrez peut-être trouver un autre moyen de garder cette colonne à jour.)

Pour prendre un échantillon de 1000 éléments d'une table, je compte les lignes et échantillonne le résultat jusqu'à, en moyenne, 10000 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

(Ma mise en œuvre réelle implique plus de travail pour m'assurer de ne pas sous-échantillonner et pour envelopper manuellement rand_high, mais l'idée de base est de "réduire au hasard votre N à quelques milliers")

Bien que cela fasse des sacrifices, cela me permet d'échantillonner la base de données en utilisant une analyse d'index, jusqu'à ce qu'elle soit suffisamment petite pour à ORDER BY RAND()nouveau.

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

Je pense sans aucune hypothèse sur le tableau que 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 listez peut être un peu meilleure, O (m * n) où m est le nombre de lignes aléatoires souhaité, car il ne serait pas nécessaire de trier tout le grand tableau , il pourrait simplement rechercher les m plus petits fois. Mais pour le genre de nombres que vous avez publié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 souhaitez sélectionner (m) est beaucoup plus petit que le nombre de lignes du tableau (n)

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

Avec seulement les hypothèses 1 et 2, je pense que cela peut être fait en O (n), bien que vous deviez écrire un index complet dans la table pour correspondre à l'hypothèse 3, donc ce n'est pas nécessairement un O (n) rapide. Si nous pouvons en plus assumer quelque chose de bien à 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 garantissait l'absence de doublons lors de la génération de m nombres d'affilée, 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 le tableau. Je n'ai pas mysql ou quoi que ce soit devant moi pour le moment, donc en légèrement pseudo-code, 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 préoccupé par l'efficacité, vous pourriez envisager de faire la génération de clé aléatoire dans une sorte de langage procédural et d'insérer les résultats dans la base de données, car presque tout autre que SQL serait probablement meilleur pour le type de boucle et de génération de nombres aléatoires requis. .

Je pense que la solution la plus rapide est

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

Voici pourquoi je pense que cela devrait faire le travail.

• Cela créera un nombre 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 0,3 (30%).

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

J'ai vu que quelqu'un avait recommandé cette solution et ils ont été abattus sans preuve ... voici ce que je dirais à cela -

• C'est O (n) mais aucun tri n'est requis donc c'est plus rapide que l'O (n lg n)

• mysql est très capable de générer des nombres aléatoires pour chaque ligne. Essaye ça -

  sélectionnez rand () dans la limite INFORMATION_SCHEMA.TABLES 10;

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

Apparemment, dans certaines versions de SQL, il existe une TABLESAMPLEcommande, mais ce n'est pas dans toutes les implémentations SQL (notamment, Redshift).

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

Juste utiliser

WHERE RAND() < 0.1 

pour obtenir 10% des enregistrements ou

WHERE RAND() < 0.01 

pour obtenir 1% des enregistrements, etc.

Plus rapide que ORDER BY RAND ()

J'ai testé cette méthode pour être beaucoup plus rapide que ORDER BY RAND(), par conséquent, elle s'exécute en temps O (n) , et le fait de manière incroyablement rapide.

À partir de http://technet.microsoft.com/en-us/library/ms189108%28v=sql.105%29.aspx :

Version non-MSSQL - Je n'ai pas testé cela

SELECT * FROM Sales.SalesOrderDetail
WHERE 0.01 >= RAND()

Version MSSQL:

SELECT * FROM Sales.SalesOrderDetail
WHERE 0.01 >= CAST(CHECKSUM(NEWID(), SalesOrderID) & 0x7fffffff AS float) / CAST (0x7fffffff AS int)

Cela sélectionnera ~ 1% des enregistrements. Donc, si vous avez besoin d'un nombre exact de pourcentages ou d'enregistrements à sélectionner, estimez votre pourcentage avec une certaine marge de sécurité, puis extrayez au hasard les enregistrements excédentaires de l'ensemble résultant, en utilisant la ORDER BY RAND()méthode la plus coûteuse .

Même plus vite

J'ai pu améliorer encore plus cette méthode car j'avais une plage de valeurs de colonnes indexées bien connue.

Par exemple, si vous avez une colonne indexée avec des entiers uniformément distribués [0..max], vous pouvez l'utiliser pour sélectionner aléatoirement N petits intervalles. Faites-le dynamiquement dans votre programme pour obtenir un ensemble différent pour chaque exécution de requête. Cette sélection de sous-ensemble sera O (N) , qui peut de plusieurs ordres de grandeur plus petite que votre ensemble de données complet.

Dans mon test, j'ai réduit le temps nécessaire pour obtenir 20 enregistrements d'échantillons (sur 20 millions) de 3 minutes en utilisant ORDER BY RAND () à 0,0 seconde !

Je tiens à souligner que toutes ces solutions semblent échantillonner sans remplacement. La sélection des K premières lignes d'un tri aléatoire ou la jonction à une table qui contient des clés uniques dans un ordre aléatoire produira un échantillon aléatoire généré sans remplacement.

Si vous voulez que votre échantillon soit indépendant, vous devrez échantillonner avec remplacement. Voir la question 25451034 pour un exemple de la façon de procéder en utilisant un JOIN d'une manière similaire à la solution de user12861. La solution est écrite pour T-SQL, mais le concept fonctionne dans n'importe quelle base de données SQL.

À partir de l'observation que nous pouvons récupérer les identifiants d'une table (par exemple, compte 5) à partir d'un ensemble:

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

nous pouvons arriver au résultat que si nous pouvions générer la chaîne "(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 identifiants ont des espaces, alors l'arraylist initiale indicesest le résultat d'une requête SQL sur les identifiants.

Si vous avez besoin exactement de mlignes, vous générerez de manière réaliste votre sous-ensemble d'identifiants en dehors de SQL. La plupart des méthodes nécessitent à un moment donné de sélectionner la "nième" entrée, et les tables SQL ne sont vraiment pas du tout des tableaux. L'hypothèse que les clés sont consécutives afin de simplement joindre des entiers aléatoires entre 1 et le nombre est également difficile à satisfaire - MySQL par exemple ne le prend pas en charge nativement, et les conditions de verrouillage sont ... délicates .

Voici un O(max(n, m lg n))-temps, O(n)solution -espace en supposant que les clés de BTREE simples:

1. Récupérez toutes les valeurs de la colonne clé de la table de données dans n'importe quel ordre dans un tableau dans votre langage de script préféré dans O(n)
2. Effectuez un mélange Fisher-Yates , en vous arrêtant après les méchanges et en extrayant le sous-tableau [0:m-1]dansϴ(m)
3. "Join" le sous-tableau avec le jeu de données d'origine (par exemple SELECT ... WHERE id IN (<subarray>)) dansO(m lg n)

Toute méthode qui génère le sous-ensemble aléatoire en dehors de SQL doit avoir au moins cette complexité. La jointure ne peut pas être plus rapide O(m lg n)qu'avec BTREE (les O(m)revendications sont donc fantastiques pour la plupart des moteurs) et la lecture aléatoire est limitée ci n- dessous m lg net n'affecte pas le comportement asymptotique.

En pseudocode pythonique:

ids = sql.query('SELECT id FROM t')
for i in range(m):
  r = int(random() * (len(ids) - i))
  ids[i], ids[i + r] = ids[i + r], ids[i]

results = sql.query('SELECT * FROM t WHERE id IN (%s)' % ', '.join(ids[0:m-1])

Sélectionnez 3000 enregistrements aléatoires dans Netezza:

WITH IDS AS (
     SELECT ID
     FROM MYTABLE;
)

SELECT ID FROM IDS ORDER BY mt_random() LIMIT 3000

Essayer

SELECT TOP 10000 * FROM table ORDER BY NEWID()

Cela donnerait-il les résultats escomptés, sans être trop compliqué?

Dans certains dialectes comme Microsoft SQL Server, PostgreSQL et Oracle (mais pas MySQL ou SQLite), vous pouvez faire quelque chose comme

select distinct top 10000 customer_id from nielsen.dbo.customer TABLESAMPLE (20000 rows) REPEATABLE (123);

La raison pour laquelle il ne suffit pas de se (10000 rows)passer de topest que la TABLESAMPLElogique vous donne un nombre extrêmement inexact de lignes (comme parfois 75%, parfois 1,25% fois cela), vous voulez donc suréchantillonner et sélectionner le nombre exact que vous voulez. Le REPEATABLE (123)sert à fournir une graine aléatoire.

Peut-être que tu pourrais faire

SELECT * FROM table LIMIT 10000 OFFSET FLOOR(RAND() * 190000)