Exemples aléatoires simples à partir d’une firebase database SQL

Comment puis-je prendre un échantillon aléatoire simple et efficace en SQL? La firebase database en question exécute MySQL; ma table compte au moins 200 000 lignes et je souhaite un échantillon aléatoire simple d’environ 10 000.

La réponse “évidente” consiste à:

SELECT * FROM table ORDER BY RAND() LIMIT 10000 

Pour les tables volumineuses, c’est trop lent: il appelle RAND () pour chaque ligne (ce qui le met déjà à O (n)), et les sortinge, le rendant au mieux O (ng n). Est-il possible 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 à 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 modifications:

  • Échantillonner les lignes à 2-5x la taille de mon échantillon souhaité, à moindre coût ORDER BY RAND ()
  • Enregistrez le résultat de RAND () dans une colonne indexée sur chaque insertion / mise à jour. (Si votre dataset n’est pas très lourd pour la mise à 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 en moyenne jusqu’à 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 m’assurer de ne pas sous-échantillonner, et pour envelopper manuellement rand_high, mais l’idée de base est de “couper aléatoirement votre N jusqu’à quelques milliers”.)

Bien que cela fasse des sacrifices, cela me permet de tester la firebase database en utilisant une parsing d’index, jusqu’à ce qu’elle soit suffisamment petite pour pouvoir être à nouveau ORDER BY RAND ().

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- lignes-de-table /

Je pense sans aucune hypothèse sur la table que votre solution O (n lg n) est la meilleure. Bien qu’en réalité, avec un bon optimiseur ou une technique légèrement différente, la requête que vous listez soit un peu meilleure, O (m * n) où m est le nombre de lignes aléatoires souhaité, car il ne serait pas nécessaire de sortinger tout le grand tableau , il pourrait simplement rechercher les plus petits temps m. Mais pour le genre de chiffres que vous avez affichés, m est en tout cas 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 à sélectionner (m) est beaucoup plus petit que le nombre de lignes de la table (n)

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

Avec seulement les hypothèses 1 et 2, je pense que cela peut être fait dans O (n), bien que vous deviez écrire un index entier dans la table pour correspondre à l’hypothèse 3, donc ce n’est pas nécessairement un O (n) rapide. Si nous pouvons supposer de manière ADDITIONNELLE quelque chose d’autre de bien dans la table, nous pouvons faire la tâche dans O (m log m). Assomption 3 serait une propriété facile à utiliser. Avec un générateur de nombres aléatoires sympa qui ne garantissait aucun doublon lors de la génération de m nombres dans une ligne, 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 quelque chose en face de moi en ce moment, donc en pseudocode légèrement 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 générer des clés aléatoires dans une sorte de langage procédural et d'insérer les résultats dans la firebase database, car presque autre chose que SQL serait probablement meilleure. .

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.

  • Il 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 .3 (30%).

Cela suppose que rand () génère des nombres dans une dissortingbution 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 -

  • Ceci est O (n) mais aucun sorting n'est requirejs, donc il est plus rapide que le O (ng n)
  • mysql est très capable de générer des nombres aléatoires pour chaque ligne. Essaye ça -

    sélectionnez rand () from INFORMATION_SCHEMA.TABLES limit 10;

Puisque la firebase database en question est mySQL, c'est la bonne solution.

Plus rapide que ORDER BY RAND ()

J’ai testé cette méthode pour qu’elle soit beaucoup plus rapide que ORDER BY RAND() , donc elle s’exécute dans O (n) time, et le fait très rapidement.

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 du nombre exact de pourcentages ou d’enregistrements à sélectionner, estimez votre pourcentage avec une marge de sécurité, puis extrayez aléatoirement les enregistrements en excès de l’ensemble résultant en utilisant la méthode plus coûteuse ORDER BY RAND() .

Même plus vite

J’ai été en mesure d’améliorer encore cette méthode parce que j’avais une gamme de valeurs de colonne indexée bien connue.

Par exemple, si vous avez une colonne indexée avec des entiers uniformément dissortingbués [0..max], vous pouvez l’utiliser pour sélectionner aléatoirement N petits intervalles. Faites cela dynamicment dans votre programme pour obtenir un ensemble différent pour chaque requête. Cette sélection de sous-ensemble sera O (N) , qui peut être beaucoup plus petite que votre jeu de données complet.

Dans mon test, j’ai réduit le temps nécessaire pour obtenir 20 (20 millièmes) échantillons d’échantillons de 3 minutes en utilisant ORDER BY RAND () à 0.0 seconde !

Apparemment, dans certaines versions de SQL, il existe une commande TABLESAMPLE , mais 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 records ou

 WHERE RAND() < 0.01 

pour obtenir 1% des records, etc.

En commençant par l’observation que nous pouvons récupérer les identifiants d’une table (par exemple, compter 5) en fonction 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 indices = new ArrayList(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 lacunes, alors les indices arraylist initiaux sont le résultat d'une requête SQL sur les identifiants.

Je tiens à souligner que toutes ces solutions semblent échantillonner sans être remplacées. En sélectionnant les K premières lignes d’un sorting aléatoire ou en vous joignant à une table contenant des clés uniques dans un ordre aléatoire, vous obtiendrez 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 une JOIN d’une manière similaire à celle de user12861. La solution est écrite pour T-SQL, mais le concept fonctionne dans n’importe quelle firebase database SQL.

Si vous avez besoin exactement de m lignes, vous générerez de manière réaliste votre sous-ensemble d’ID en dehors de SQL. La plupart des méthodes nécessitent à un moment ou à un autre de sélectionner l’entrée “n” et les tables SQL ne sont pas du tout des tableaux. L’hypothèse selon laquelle les clés sont consécutives pour simplement joindre des nombres aléatoires entre 1 et le compte est également difficile à satisfaire – MySQL par exemple ne le prend pas en charge de manière native et les conditions de locking sont … délicates .

Voici une solution O(max(n, m lg n)) -heure, O(n) -espace en supposant que les clés BTREE ne sont que des clés:

  1. Récupère toutes les valeurs de la colonne clé de la table de données dans n’importe quel ordre dans un tableau de votre langage de script préféré dans O(n)
  2. Effectuer un mélange Fisher-Yates , s’arrêter après m swaps et extraire le sous-tableau [0:m-1] dans ϴ(m)
  3. “Rejoindre” le sous-tableau avec le jeu de données d’origine (par exemple, SELECT ... WHERE id IN () ) dans O(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 que O(m lg n) avec BTREE (donc les revendications O(m) sont fantastiques pour la plupart des moteurs) et le shuffle est limité en dessous de n et m lg n et 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]) 

Peut-être que tu pourrais faire

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