90 votos

Muestras aleatorias simples de una base de datos Sql

¿Cómo puedo tomar una muestra aleatoria simple eficaz 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 unas 10.000.

La respuesta "obvia" es:

SELECT * FROM table ORDER BY RAND() LIMIT 10000

Para las tablas grandes, eso es demasiado lento: llama a RAND() para cada fila (lo que ya lo pone en O(n)), y las ordena, haciéndolo O(n lg n) en el mejor de los casos. ¿Hay alguna forma de hacerlo más rápido que O(n)?

Nota : Como señala Andrew Mao en los comentarios, si está utilizando este enfoque en Sql Server, debe utilizar 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 de nuevo con una tabla más grande, y terminé usando una versión de la solución de @ignorant, con dos ajustes:

  • Muestrear las filas a 2-5 veces mi tamaño de muestra deseado, para ordenar por RAND() de forma barata
  • Guarda 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 tenga que encontrar otra forma de mantener esta columna actualizada).

Para tomar una muestra de 1000 elementos de una tabla, cuento las filas y muestro el resultado hasta, por término medio, 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 submuestreo, y para envolver manualmente rand_high, pero la idea básica es "reducir aleatoriamente su N a unos pocos miles").

Aunque esto hace algunos sacrificios, me permite muestrear la base de datos hacia abajo usando un escaneo de índice, hasta que sea lo suficientemente pequeño para ordenar por RAND() de nuevo.

49voto

ignorant Puntos 58

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

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

Por eso 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 .3 (30%).

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

He visto que alguien ha recomendado esa solución y le han tumbado sin pruebas esto es lo que yo diría a eso -

  • Esto es O(n) pero no es necesario ordenar, 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

    select rand() from INFORMATION_SCHEMA.TABLES limit 10;

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

24voto

user12861 Puntos 1094

Hay un debate muy interesante sobre este tipo de cuestiones aquí: 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, tu 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 enumeras 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 todo el Array grande, sólo podría buscar el más pequeño m veces. Pero para el tipo de números que has publicado, m es mayor que lg n de todos modos.

Tres supuestos que podríamos probar:

  1. hay una clave primaria única e indexada en la tabla

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

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

Con sólo los supuestos 1 y 2 creo que esto se puede hacer en O(n), aunque tendrás que escribir un índice completo en la tabla para que coincida con el supuesto 3, por lo que no es necesariamente un O(n) rápido. Si podemos asumir ADICIONALMENTE algo más agradable sobre la tabla, podemos hacer la tarea en O(m log m). La suposición 3 sería una propiedad adicional fácil de trabajar. Con un buen generador de números aleatorios que garantice que no hay duplicados al generar m números en una fila, una solución O(m) sería posible.

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 delante de mí en este momento, así que en un poco de pseudocódigo esto se vería algo 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 realmente te preocupa la eficiencia, podrías 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 cosa que no sea SQL probablemente sería mejor en el tipo de bucle y generación de números aleatorios requeridos.

4voto

gatoatigrado Puntos 6230

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

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

4voto

David F Mayer Puntos 31

Sólo tiene que utilizar

WHERE RAND() < 0.1 

para obtener el 10% de los registros o

WHERE RAND() < 0.01 

para conseguir el 1% de los registros, etc.

0voto

KitKat Puntos 311

Partiendo de la observación de que podemos recuperar los identificadores de una tabla (por ejemplo, el recuento 5) a partir 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 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 huecos, entonces la lista inicial de arrays indices es el resultado de una consulta sql sobre ids.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X