Muestras aleatorias simples de una base de datos SQL

Question

¿Cómo se toma una muestra aleatoria simple eficiente en SQL? La base de datos en cuestión ejecuta MySQL; mi tabla tiene al menos 200,000 filas, y quiero una muestra aleatoria simple de aproximadamente 10,000.

La respuesta "obvia" es:

SELECT * FROM table ORDER BY RAND() LIMIT 10000 

Para tablas grandes, eso es demasiado lento: se llama RAND() para cada fila (que ya pone en O (n)), y los ordena , convirtiéndolo en O (n lg n) en el mejor de los casos. ¿Hay alguna manera de hacer esto más rápido que O (n)?

Nota: Como Andrew Mao señala en los comentarios, si usted está usando este enfoque en SQL Server, debe utilizar la función NEWID T-SQL(), porque RAND() may return the same value for all rows.

EDIT: 5 años más tarde

me encontré con este problema de nuevo con una mesa más grande, y terminó con una versión de @ solución de ignorantes, con dos ajustes:

• Muestra las filas a 2-5x el tamaño de muestra deseado, a bajo costo ORDER BY RAND()
• Guarde el resultado de RAND() en una columna indexada en cada inserción/actualización. (Si su conjunto de datos no es muy pesado, es posible que deba encontrar otra forma de mantener fresca esta columna.)

Para tomar una muestra de 1000 elementos de una tabla, cuento las filas y la muestra el resultado hasta, en promedio, 10.000 filas con la columna de la 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 

(Mi aplicación efectiva implica más trabajo para asegurarse de que no lo hago undersample, y para envolver manualmente rand_high alrededor, pero la idea básica es "cortar aleatoriamente tu N a unos pocos miles")

Si bien esto hace algunos sacrificios, me permite baje la base de datos usando un escaneo de índice, hasta que sea lo suficientemente pequeño como para ORDER BY RAND() nuevamente.

Answer 1

Hay una discusión muy interesante de este tipo de problema aquí: http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/

creo sin ningún tipo de suposiciones sobre la mesa que el O (n lg n) la solución es lo mejor Aunque en realidad con un buen optimizador o una técnica ligeramente diferente, la consulta que enumera puede ser un poco mejor, O (m * n) donde m es el número de filas aleatorias deseadas, ya que no necesariamente tendrían que ordenar toda la gran matriz , podría simplemente buscar el mínimo de m veces. Pero para el tipo de números que publicaste, m es más grande que lg n de todos modos.

Tres asumptions podríamos tratar a cabo:

1. hay una clave única, indexado, principal en la tabla

2. el número de filas aleatorias que desea seleccionar (m) es mucho menor que el número de filas de la tabla (n)

3. la clave principal único es un número entero que varía de 1 a n sin lagunas

Con solo las suposiciones 1 y 2, creo que esto se puede hacer en O (n), aunque tendrá que escribir un índice completo en la tabla para que coincida con la suposición 3, por lo que no es necesario O (n) . Si podemos ADEMÁS asumir otra cosa agradable sobre la tabla, podemos hacer la tarea en O (m log m). La suposición 3 sería una propiedad adicional agradable y fácil de trabajar. Con un buen generador de números aleatorios que garantiza que no habrá duplicados al generar m números en una fila, sería posible una solución de O (m).

Dadas las tres suposiciones, la idea básica es generar m números aleatorios únicos entre 1 y n, y luego seleccionar las filas con esas claves de la tabla. No tengo MySQL o nada delante de mí en este momento, por lo que en poco pseudocódigo esto sería algo como:

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 fueras realmente preocupados por la eficiencia, es posible pensar en hacer la generación de claves aleatorias de alguna tipo de lenguaje de procedimiento e insertar los resultados en la base de datos, ya que casi cualquier cosa que no sea SQL probablemente sería mejor en el tipo de bucle y la generación de números aleatorios necesarios.

Answer 2

Tal vez usted podría hacer

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

Answer 3

sólo tiene que utilizar

WHERE RAND() < 0.1 

para obtener el 10% de los registros o

WHERE RAND() < 0.01 

para obtener el 1% de los registros, etc.

Answer 4

Creo que la solución más rápida es

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

He aquí por qué creo que t él debería hacer el trabajo.

• Creará un número aleatorio para cada fila. El número está entre 0 y 1
• Evalúa si se muestra esa fila si el número generado está entre 0 y .3 (30%).

Esto supone que rand() está generando números en una distribución uniforme. Es la forma más rápida de hacer esto.

vi que alguien había recomendado que la solución y se obtuvo derribado sin pruebas .. Esto es lo que diría a esa -

• Esta es O (n), pero no se requiere ninguna clasificación por lo que es más rápido que el O (n lg n)

• mysql es muy capaz de generar números aleatorios para cada fila.Pruebe esto -

  seleccione rand() de INFORMATION_SCHEMA.TABLES límite 10;

Dado que la base de datos en cuestión es mySQL, esta es la solución correcta.

Answer 5

A partir de la observación de que podemos recuperar los ID de una tabla basada en un conjunto (por ejemplo, contar con 5.):

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

podemos llegar al resultado que si pudiéramos generar la cadena "(4, 1, 2, 5, 3)", entonces tendríamos una manera más eficiente que RAND().

Por ejemplo, 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 los identificadores tienen lagunas, entonces el ArrayList inicial indices es el resultado de una consulta SQL en las identificaciones.

Answer 6

Aparentemente en algunas versiones de SQL hay un comando TABLESAMPLE, pero no está en todas las implementaciones de SQL (notablemente, Redshift).

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

Answer 7

Quiero señalar que todas estas soluciones parecen a la muestra sin reemplazo. Seleccionar las filas K superiores de una clasificación aleatoria o unirlas a una tabla que contiene claves únicas en orden aleatorio generará una muestra aleatoria generada sin reemplazo.

Si desea que su muestra sea independiente, tendrá que muestrear con el reemplazo. Vea Question 25451034 para ver un ejemplo de cómo hacer esto usando un JOIN de una manera similar a la solución de user12861. La solución está escrita para T-SQL, pero el concepto funciona en cualquier SQL db.

Answer 8

más rápido que ORDER BY RAND()

Probé que este método sea mucho más rápido que ORDER BY RAND(), por lo tanto, se ejecuta en O (n) tiempo, y lo hace impresionantemente rápido.

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

Versión no MSSQL - no he probado esta versión

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

MSSQL:

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

Esto seleccionará ~ 1% de archivos. Por lo tanto, si necesita un número exacto de porcentajes o registros que se deben seleccionar, calcule su porcentaje con un margen de seguridad y luego extraiga al azar los registros sobrantes del conjunto resultante, utilizando el método más costoso ORDER BY RAND().

aún más rápido

que fue capaz de mejorar este método aún más porque tenía un conocido rango de valores columna indexada.

Por ejemplo, si tiene una columna indexada con enteros uniformemente distribuidos [0..max], puede usar eso para seleccionar aleatoriamente N intervalos pequeños.Haga esto dinámicamente en su programa para obtener un conjunto diferente para cada ejecución de consulta. Esta selección de subconjuntos será O (N), que puede tener muchos órdenes de magnitud más pequeños que su conjunto de datos completo.

En mi prueba que reduce el tiempo necesario para obtener 20 (de un total de 20 mil) de registros de muestras de 3 minutos utilizando ORDER BY RAND() hacia abajo a 0,0 segundos!

Answer 9

Si necesita exactamente m filas, de forma realista generará su subconjunto de ID fuera de SQL. La mayoría de los métodos requieren en algún momento seleccionar la entrada "enésima", y las tablas SQL realmente no son matrices. La suposición de que las claves son consecutivas para simplemente unir las entradas aleatorias entre 1 y el recuento también es difícil de satisfacer — MySQL, por ejemplo, no lo admite de forma nativa, y las condiciones de bloqueo son ... tricky.

He aquí un, O(n) solución -espacio O(max(n, m lg n)) -tiempo asumiendo teclas BTree apenas aclara:

1. obtener todos los valores de la columna de clave de la tabla de datos en cualquier orden en una matriz en su lenguaje de script favorito en O(n)
2. Realice una Fisher-Yates shuffle, deteniéndose después de m permutas y extracto de la submatriz [0:m-1] en ϴ(m)
3. "unirse" a la submatriz con el conjunto de datos original (por ejemplo SELECT ... WHERE id IN (<subarray>)) en O(m lg n)

Cualquier método que genere un subconjunto aleatorio fuera de SQL debe tener al menos esta complejidad. La unión no puede ser más rápida que O(m lg n) con BTREE (por lo que O(m) afirmaciones son fantásticas para la mayoría de los motores) y la reproducción aleatoria está limitada por debajo de n y m lg n y no afecta el comportamiento asintótico.

En Pythonic pseudocódigo:

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