Semplici campioni casuali da un database SQL

Come faccio a prendere un campione casuale semplice ed efficiente in SQL? Il database in questione sta eseguendo MySQL; la mia tabella ha almeno 200.000 righe e voglio un semplice campione casuale di circa 10.000.

La risposta “ovvia” è:

SELECT * FROM table ORDER BY RAND() LIMIT 10000 

Per le tabelle di grandi dimensioni, è troppo lento: chiama RAND () per ogni riga (che già la colloca su O (n)) e li ordina, rendendola O (n lg n) nella migliore delle ipotesi. C’è un modo per farlo più veloce di O (n)?

Nota : come indicato da Andrew Mao nei commenti, se si utilizza questo approccio su SQL Server, è necessario utilizzare la funzione T-SQL NEWID (), poiché RAND () potrebbe restituire lo stesso valore per tutte le righe .

EDIT: 5 ANNI DOPO

    Mi sono imbattuto nuovamente in questo problema con una tabella più grande e ho finito per utilizzare una versione della soluzione di @ ignorante, con due modifiche:

    • Esempio di righe per 2-5 volte la dimensione del campione desiderata, a buon mercato ORDINA DA RAND ()
    • Salva il risultato di RAND () in una colonna indicizzata su ogni inserimento / aggiornamento. (Se il tuo set di dati non è molto pesante da aggiornare, potrebbe essere necessario trovare un altro modo per mantenere questa colonna fresca.)

    Per prendere un campione di 1000 elementi di una tabella, conto le righe e campionare il risultato in media su 10.000 righe con la colonna 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 

    (La mia implementazione effettiva richiede più lavoro per essere sicuro di non sottostimare, e di avvolgere manualmente rand_high around, ma l’idea di base è “tagliare a caso la tua N fino a qualche migliaio”.)

    Mentre questo fa alcuni sacrifici, mi permette di campionare il database usando una scansione indice, fino a quando è abbastanza piccolo da ORDER BY RAND () di nuovo.

    C’è una discussione molto interessante su questo tipo di problema qui: http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random- righe-da-table /

    Penso che senza assolutamente nessuna ipotesi sul tavolo la soluzione O (n lg n) sia la migliore. Sebbene in realtà con un buon ottimizzatore o una tecnica leggermente diversa la query che elencherai potrebbe essere un po ‘migliore, O (m * n) dove m è il numero di righe casuali desiderato, poiché non dovrebbe necessariamente ordinare l’intero grande array , potrebbe solo cercare il più piccolo m volte. Ma per il tipo di numeri che hai postato, m è più grande di lg n comunque.

    Tre ipotesi che potremmo provare:

    1. c’è una chiave primaria univoca, indicizzata nella tabella

    2. il numero di righe casuali che vuoi selezionare (m) è molto più piccolo del numero di righe nella tabella (n)

    3. la chiave primaria univoca è un numero intero che va da 1 a n senza spazi vuoti

    Con solo le ipotesi 1 e 2, penso che questo possa essere fatto in O (n), sebbene tu abbia bisogno di scrivere un intero indice sulla tabella per corrispondere all’ipotesi 3, quindi non è necessariamente un O (n) veloce. Se possiamo ADDIZIONARE INOLTRE qualcos’altro sulla tabella, possiamo eseguire l’operazione in O (m log m). Assumption 3 sarebbe una proprietà addizionale semplice e piacevole con cui lavorare. Con un buon generatore di numeri casuali che non garantiva duplicati durante la generazione di m numeri in fila, sarebbe stata ansible una soluzione O (m).

    Date le tre ipotesi, l’idea di base è di generare m numeri casuali univoci tra 1 e n, e quindi selezionare le file con quelle chiavi dalla tabella. Non ho mysql o niente di fronte a me in questo momento, quindi con un po ‘di pseudocodice questo sembrerebbe qualcosa di simile:

     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 

    Se si fosse veramente preoccupati dell'efficienza, si potrebbe prendere in considerazione la generazione casuale della chiave in una sorta di linguaggio procedurale e l'inserimento dei risultati nel database, poiché quasi qualsiasi cosa diversa da SQL sarebbe probabilmente migliore con il tipo di generazione di cicli e numeri casuali richiesta .

    Penso che la soluzione più veloce sia

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

    Ecco perché penso che questo dovrebbe fare il lavoro.

    • Creerà un numero casuale per ogni riga. Il numero è compreso tra 0 e 1
    • Valuta se visualizzare quella riga se il numero generato è compreso tra 0 e .3 (30%).

    Ciò presuppone che rand () stia generando numeri in una distribuzione uniforms. È il modo più rapido per farlo.

    Ho visto che qualcuno aveva consigliato quella soluzione e sono stati abbattuti senza prove ... ecco cosa direi a questo -

    • Questo è O (n) ma non è richiesto alcun ordinamento, quindi è più veloce di O (n lg n)
    • mysql è in grado di generare numeri casuali per ogni riga. Prova questo -

      selezionare rand () dal limite 10 di INFORMATION_SCHEMA.TABLES;

    Poiché il database in questione è mySQL, questa è la soluzione giusta.

    Più veloce di ORDER BY RAND ()

    Ho provato questo metodo per essere molto più veloce di ORDER BY RAND() , quindi funziona in tempo O (n) , e lo fa in modo incredibilmente veloce.

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

    Versione non MSSQL : non l’ho verificato

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

    Versione MSSQL:

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

    Questo selezionerà ~ 1% dei record. Pertanto, se è necessario il numero esatto di percentuali o record da selezionare, stimare la percentuale con un margine di sicurezza, quindi estrarre casualmente i record in eccesso dal set risultante, utilizzando il metodo ORDER BY RAND() più costoso.

    Ancora più veloce

    Sono stato in grado di migliorare ulteriormente questo metodo perché avevo un intervallo di valori di colonne indicizzato noto.

    Ad esempio, se si dispone di una colonna indicizzata con numeri interi distribuiti uniformsmente [0..max], è ansible utilizzarla per selezionare casualmente N intervalli di piccole dimensioni. Fai questo in modo dinamico nel tuo programma per ottenere un set diverso per ogni esecuzione di query. Questa selezione di sottoinsiemi sarà O (N) , che può molti ordini di grandezza inferiore al set di dati completo.

    Nel mio test ho ridotto il tempo necessario per ottenere 20 (out 20 mil) record di campioni da 3 minuti usando ORDER BY RAND () fino a 0,0 secondi !

    Apparentemente in alcune versioni di SQL esiste un comando TABLESAMPLE , ma non è in tutte le implementazioni SQL (in particolare, Redshift).

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

    Basta usare

     WHERE RAND() < 0.1 

    per ottenere il 10% dei record o

     WHERE RAND() < 0.01 

    per ottenere l'1% dei record, ecc.

    Partendo dall’osservazione che possiamo recuperare gli id ​​di una tabella (ad esempio contare 5) in base a un set:

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

    possiamo arrivare al risultato che se potessimo generare la stringa "(4, 1, 2, 5, 3)" , avremmo un modo più efficiente di RAND() .

    Ad esempio, in 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(']', ')'); 

    Se gli ID hanno spazi vuoti, gli indices dell'arrayylist iniziali sono il risultato di una query sql su id.

    Voglio sottolineare che tutte queste soluzioni sembrano campionare senza sostituzione. Selezionare le prime righe K da un ordinamento casuale o unirsi a una tabella che contiene chiavi univoche in ordine casuale produrrà un campione casuale generato senza sostituzione.

    Se vuoi che il tuo campione sia indipendente, dovrai campionarlo con la sostituzione. Vedere Domanda 25451034 per un esempio di come farlo usando un JOIN in un modo simile alla soluzione dell’utente12861. La soluzione è scritta per T-SQL, ma il concetto funziona in qualsiasi db SQL.

    Se hai bisogno esattamente di m righe, realisticamente genererai il tuo sottoinsieme di ID al di fuori di SQL. La maggior parte dei metodi richiede a un certo punto di selezionare la voce “nth” e le tabelle SQL non sono affatto matrici. L’ipotesi che le chiavi siano consecutive per unire solo interi casuali tra 1 e il conteggio è anche difficile da soddisfare – MySQL ad esempio non la supporta in modo nativo, e le condizioni di blocco sono … ingannevoli .

    Ecco una soluzione di O(max(n, m lg n)) -time, O(n) assumendo semplicemente le chiavi BTREE:

    1. Recupera tutti i valori della colonna chiave della tabella dati in qualsiasi ordine in un array nel tuo linguaggio di scripting preferito in O(n)
    2. Esegui un rimescolamento di Fisher-Yates , fermandoti dopo m scambi, ed estrai il sottoarray [0:m-1] in ϴ(m)
    3. “Unisci” il sottoarray con il set di dati originale (es. SELECT ... WHERE id IN () ) in O(m lg n)

    Qualsiasi metodo che generi il sottoinsieme casuale al di fuori di SQL deve avere almeno questa complessità. Il join non può essere più veloce di O(m lg n) con BTREE (quindi le affermazioni di O(m) sono fantasiose per la maggior parte dei motori) e lo shuffle è limitato sotto n e m lg n e non influenza il comportamento asintotico.

    In pseudocodice pitonico:

     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]) 

    Forse potresti farlo

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