¿Cómo tomo una muestra aleatoria simple eficiente en SQL? La base de datos en cuestión está ejecutando 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: llama RAND()a cada fila (que ya la coloca en O (n)) y las ordena, convirtiéndola en O (n lg n) en el mejor de los casos. ¿Hay alguna forma de hacer esto más rápido que O (n)?

Nota : Como Andrew Mao señala en los comentarios, si está usando este enfoque en SQL Server, debe usar la función T-SQL NEWID(), porque RAND () puede devolver el mismo valor para todas las filas .

EDITAR: 5 AÑOS DESPUÉS

Me encontré con este problema nuevamente con una tabla más grande y terminé usando una versión de la solución de @ ignorant, con dos ajustes:

• Muestree las filas a 2-5 veces 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 tiene muchas actualizaciones, es posible que deba encontrar otra forma de mantener actualizada esta columna).

Para tomar una muestra de 1000 elementos de una tabla, cuento las filas y muestre el resultado hasta, en promedio, 10,000 filas con la columna 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 implementación real implica más trabajo para asegurarme de que no muestre menos y para ajustar manualmente rand_high, pero la idea básica es "reducir aleatoriamente su N a unos pocos miles").

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

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

Creo que, sin ninguna suposición sobre la tabla, su solución O (n lg n) es la mejor. Aunque en realidad con un buen optimizador o una técnica ligeramente diferente, la consulta que enumere puede ser un poco mejor, O (m * n) donde m es el número de filas aleatorias deseadas, ya que no necesariamente tendría que ordenar toda la matriz grande , podría buscar las m veces más pequeñas. Pero para el tipo de números que publicaste, m es más grande que lg n de todos modos.

Tres suposiciones que podríamos probar:

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

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

3. la clave primaria única es un número entero que varía de 1 an sin espacios

Con solo las suposiciones 1 y 2, creo que esto se puede hacer en O (n), aunque deberá escribir un índice completo en la tabla para que coincida con la suposición 3, por lo que no es necesariamente una O (n) rápida. Si ADICIONALMENTE podemos suponer algo más bueno sobre la tabla, podemos hacer la tarea en O (m log m). El supuesto 3 sería una propiedad adicional agradable con la que trabajar. Con un buen generador de números aleatorios que garantiza que no haya duplicados al generar m números seguidos, sería posible una solución O (m).

Dados los tres supuestos, 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 ni nada frente a mí en este momento, por lo que en un pseudocódigo ligeramente esto se vería así:

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 estuviera realmente preocupado por la eficiencia, podría considerar hacer la generación de claves aleatorias en algún tipo de lenguaje de procedimiento e insertar los resultados en la base de datos, ya que casi cualquier otra cosa que no sea SQL probablemente sería mejor en el tipo de generación de números aleatorios y bucles requeridos. .

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

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

He aquí por qué creo que esto debería funcionar.

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

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

Vi que alguien había recomendado esa solución y fue derribado sin pruebas ... esto es lo que diría a eso:

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

• mysql es muy capaz de generar números aleatorios para cada fila. Prueba 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 adecuada.

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

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

Solo usa

WHERE RAND() < 0.1 

para obtener el 10% de los registros o

WHERE RAND() < 0.01 

para obtener el 1% de los registros, etc.

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

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

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

Versión que no es MSSQL : no probé esto

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

Versión de MSSQL:

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

Esto seleccionará ~ 1% de los registros. Entonces, si necesita seleccionar un número exacto de porcentajes o registros, estime su porcentaje con algún margen de seguridad, luego extraiga aleatoriamente los registros excedentes del conjunto resultante, utilizando el ORDER BY RAND()método más costoso .

Aun más rápido

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

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

En mi prueba, reduje el tiempo necesario para obtener 20 (de 20 mil) registros de muestra de 3 minutos usando ORDER BY RAND () a 0.0 segundos .

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

Si desea que su muestra sea independiente, deberá tomar una muestra con reemplazo. Vea la Pregunta 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 base de datos SQL.

Comenzando con la observación de que podemos recuperar los identificadores de una tabla (por ejemplo, cuenta 5) basados ​​en un conjunto:

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

podemos llegar al resultado de que si pudiéramos generar la cadena "(4, 1, 2, 5, 3)", entonces tendríamos una forma 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 ids tienen espacios, entonces la lista de matrices inicial indiceses el resultado de una consulta sql sobre ids.

Si necesita exactamente mfilas, de manera realista generará su subconjunto de ID fuera de SQL. La mayoría de los métodos requieren en algún momento seleccionar la entrada "n-ésima", y las tablas SQL en realidad no son matrices en absoluto. La suposición de que las claves son consecutivas para unir 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 ... complicadas .

Aquí hay una solución de O(max(n, m lg n))tiempo y O(n)espacio asumiendo solo claves BTREE simples:

1. Obtenga todos los valores de la columna clave de la tabla de datos en cualquier orden en una matriz en su lenguaje de programación favorito en O(n)
2. Realice una reproducción aleatoria de Fisher-Yates , deteniéndose después de los mintercambios, y extraiga el subarreglo [0:m-1]enϴ(m)
3. "Unir" el subarreglo con el conjunto de datos original (p SELECT ... WHERE id IN (<subarray>). Ej. ) EnO(m lg n)

Cualquier método que genere el 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 las O(m)afirmaciones son una fantasía para la mayoría de los motores) y la mezcla se limita a continuación ny m lg nno afecta el comportamiento asintótico.

En pseudocódigo Pythonic:

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

Seleccione 3000 registros aleatorios en Netezza:

WITH IDS AS (
     SELECT ID
     FROM MYTABLE;
)

SELECT ID FROM IDS ORDER BY mt_random() LIMIT 3000

Tratar

SELECT TOP 10000 * FROM table ORDER BY NEWID()

¿Daría esto los resultados deseados, sin ser demasiado complicado?

En ciertos dialectos como Microsoft SQL Server, PostgreSQL y Oracle (pero no MySQL o SQLite), puede hacer algo como

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

La razón para no solo (10000 rows)prescindir del topes que la TABLESAMPLElógica le da un número extremadamente inexacto de filas (como a veces 75%, a veces 1,25%), por lo que desea sobremuestrear y seleccionar el número exacto que desea. El REPEATABLE (123)es para proporcionar una semilla aleatoria.

Tal vez podrías hacer

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