employees ejemplos datos consultas complejas mysql sql postgresql random random-sample

mysql - ejemplos - Muestras aleatorias simples de una base de datos Sql



mysql sample database (9)

¿Cómo tomo 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, es demasiado lento: llama a RAND () para cada fila (que ya lo coloca en O (n)), y las ordena, por lo que es 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 señala Andrew Mao en los comentarios, si usa 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 MÁS TARDE

Volví a encontrar este problema con una tabla más grande, y terminé usando una versión de la solución de @injustiante, con dos ajustes:

  • Muestre las filas a 2-5x el tamaño de muestra deseado, a bajo precio ORDEN POR 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 en cuanto a las 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 muestro 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 estoy por debajo del muestreo, y para envolver manualmente a rand_high, pero la idea básica es "reducir aleatoriamente tu 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 () nuevamente.

Más rápido que ORDEN POR RAND ()

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

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

Versión no MSSQL - No probé esto

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

Versión 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. 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 aleatoriamente los registros sobrantes del conjunto resultante, utilizando el método más costoso ORDER BY RAND() .

Aun más rápido

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

Por ejemplo, si tiene una columna indexada con números 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 reduje el tiempo necesario para obtener 20 (20 mil) registros de muestra de 3 minutos usando ORDER BY RAND () ¡hasta 0.0 segundos !

Aquí hay una discusión muy interesante sobre este tipo de problema:

Creo que con absolutamente ninguna suposición sobre la tabla que 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 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 suposiciones que podríamos probar:

  1. hay una clave principal única e 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 va de 1 a n sin espacios vacíos

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 necesariamente un O rápido (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 ni nada delante de mí en este momento, así que en un pseudocódigo leve se vería algo así 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) &lt 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 estuvieras realmente preocupado por la eficiencia, podrías considerar la generación aleatoria de claves en algún tipo de lenguaje de procedimientos e insertar los resultados en la base de datos, ya que casi cualquier cosa que no sea SQL probablemente sea mejor en el tipo de bucle y generación de números aleatorios requeridos .

Comenzando con la observación de que podemos recuperar los identificadores de una tabla (por ejemplo, recuento 5) en función de 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 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 ids tienen vacíos, entonces los indices iniciales de arraylist son el resultado de una consulta sql en ids.

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

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

Esta es la razón por la que creo que esto debería hacer el trabajo.

  • 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 .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 esa solución y fueron derribados sin pruebas ... esto es lo que yo le diría a eso:

  • Esto es O (n) pero no se requiere 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. Prueba esto -

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

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

Quiero señalar que todas estas soluciones parecen muestrear 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 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 SQL db.

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 .

Aquí hay una solución O(max(n, m lg n)) -time, O(n) -space asumiendo simplemente las claves BTREE:

  1. Obtenga todos los valores de la columna de clave de la tabla de datos en cualquier orden en una matriz en su lenguaje de scripting favorito en O(n)
  2. Realice una mezcla de Fisher-Yates , deteniéndose después de m swaps, y extraiga el subcampo [0:m-1] en ϴ(m)
  3. "Unir" el subcampo con el conjunto de datos original (por ejemplo, SELECT ... WHERE id IN (<subarray>) ) en O(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 afirmaciones O(m) son fantásticas para la mayoría de los motores) y la mezcla está limitada debajo de n y m lg n y no 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])

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.

Tal vez podrías hacer

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