La mejor manera de seleccionar filas aleatorias PostgreSQL


Quiero una selección aleatoria de filas en PostgreSQL, probé esto:

select * from table where random() < 0.01;

Pero algunos otros recomiendan esto:

select * from table order by random() limit 1000;

Tengo una mesa muy grande con 500 millones de filas, quiero que sea rápido.

¿Qué enfoque es mejor? ¿Cuáles son las diferencias? ¿Cuál es la mejor manera de seleccionar filas aleatorias?

Author: Eric Leschinski, 2011-12-30

11 answers

Dadas sus especificaciones (más información adicional en los comentarios),

  • Tiene una columna de identificación numérica (números enteros) con solo unos pocos (o moderadamente pocos) espacios.
  • Obviamente ninguna o pocas operaciones de escritura.
  • Su columna de ID tiene que ser indexada! Una llave primaria sirve muy bien.

La siguiente consulta no necesita un escaneo secuencial de la tabla grande, solo un escaneo de índice.

Primero, obtenga estimaciones para la consulta principal:

SELECT count(*) AS ct              -- optional
     , min(id)  AS min_id
     , max(id)  AS max_id
     , max(id) - min(id) AS id_span
FROM   big;

El único posiblemente la parte cara es la count(*) (para mesas enormes). Dadas las especificaciones anteriores, no lo necesita. Una estimación estará bien, disponible casi sin costo ( explicación detallada aquí):

SELECT reltuples AS ct FROM pg_class WHERE oid = 'schema_name.big'::regclass;

Mientras ct no sea mucho más pequeño que id_span, la consulta superará a otros enfoques.

WITH params AS (
    SELECT 1       AS min_id           -- minimum id <= current min id
         , 5100000 AS id_span          -- rounded up. (max_id - min_id + buffer)
    )
SELECT *
FROM  (
    SELECT p.min_id + trunc(random() * p.id_span)::integer AS id
    FROM   params p
          ,generate_series(1, 1100) g  -- 1000 + buffer
    GROUP  BY 1                        -- trim duplicates
    ) r
JOIN   big USING (id)
LIMIT  1000;                           -- trim surplus
  • Genere números aleatorios en el espacio id. Tiene "pocos espacios", así que agregue el 10 % (suficiente para cubrir fácilmente los espacios en blanco) al número de filas a recuperar.

  • Cada id se puede elegir varias veces por casualidad (aunque es muy poco probable con un gran espacio de identificación), por lo que agrupa los números generados (o usa DISTINCT).

  • Une las ids a la mesa grande. Esto debería ser muy rápido con el índice en su lugar.

  • Finalmente recorte los excedentes ids que no han sido consumidos por los duplicados y los huecos. Cada fila tiene una probabilidad completamente igual de ser escogida.

Corto versión

Puede simplificar esta consulta. El CTE en la consulta anterior es solo para fines educativos:

SELECT *
FROM  (
    SELECT DISTINCT 1 + trunc(random() * 5100000)::integer AS id
    FROM   generate_series(1, 1100) g
    ) r
JOIN   big USING (id)
LIMIT  1000;

Refinar con rCTE

Especialmente si no está tan seguro de las brechas y las estimaciones.

WITH RECURSIVE random_pick AS (
   SELECT *
   FROM  (
      SELECT 1 + trunc(random() * 5100000)::int AS id
      FROM   generate_series(1, 1030)  -- 1000 + few percent - adapt to your needs
      LIMIT  1030                      -- hint for query planner
      ) r
   JOIN   big b USING (id)             -- eliminate miss

   UNION                               -- eliminate dupe
   SELECT b.*
   FROM  (
      SELECT 1 + trunc(random() * 5100000)::int AS id
      FROM   random_pick r             -- plus 3 percent - adapt to your needs
      LIMIT  999                       -- less than 1000, hint for query planner
      ) r
   JOIN   big b USING (id)             -- eliminate miss
   )
SELECT *
FROM   random_pick
LIMIT  1000;  -- actual limit

Podemos trabajar con un superávit menor en la consulta base. Si hay demasiados huecos por lo que no encontramos suficientes filas en la primera iteración, el rCTE continúa iterando con el término recursivo. Todavía necesitamos relativamente pocos espacios en el espacio ID o la recursión pueden agotarse antes de que se alcance el límite, o tenemos que comenzar con un búfer lo suficientemente grande que desafíe el propósito de optimizar el rendimiento.

Los duplicados son eliminados por el UNION en el rCTE.

El exterior LIMIT hace que el CTE se detenga tan pronto como tengamos suficientes filas.

Esta consulta está cuidadosamente redactada para usar el índice disponible, generar filas realmente aleatorias y no detenerse hasta que cumplamos con el límite (a menos que el la recursión se seca). Hay una serie de trampas aquí si vas a reescribirlo.

Ajustar a la función

Para uso repetido con parámetros variables:

CREATE OR REPLACE FUNCTION f_random_sample(_limit int = 1000, _gaps real = 1.03)
  RETURNS SETOF big AS
$func$
DECLARE
   _surplus  int := _limit * _gaps;
   _estimate int := (           -- get current estimate from system
      SELECT c.reltuples * _gaps
      FROM   pg_class c
      WHERE  c.oid = 'big'::regclass);
BEGIN

   RETURN QUERY
   WITH RECURSIVE random_pick AS (
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * _estimate)::int
         FROM   generate_series(1, _surplus) g
         LIMIT  _surplus           -- hint for query planner
         ) r (id)
      JOIN   big USING (id)        -- eliminate misses

      UNION                        -- eliminate dupes
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * _estimate)::int
         FROM   random_pick        -- just to make it recursive
         LIMIT  _limit             -- hint for query planner
         ) r (id)
      JOIN   big USING (id)        -- eliminate misses
   )
   SELECT *
   FROM   random_pick
   LIMIT  _limit;
END
$func$  LANGUAGE plpgsql VOLATILE ROWS 1000;

Llamada:

SELECT * FROM f_random_sample();
SELECT * FROM f_random_sample(500, 1.05);

Incluso podría hacer que este genérico funcione para cualquier tabla: Tome el nombre de la columna PK y la tabla como tipo polimórfico y use EXECUTE... Pero eso está más allá del alcance de esta pregunta. Véase:

Posible alternativa

SI sus requisitos permiten conjuntos idénticos para llamadas repetidas (y estamos hablando de llamadas repetidas) consideraría una vista materializada . Ejecute la consulta anterior una vez y escriba el resultado en una tabla. Los usuarios obtienen una selección casi aleatoria a una velocidad de aligeramiento. Actualice su selección aleatoria a intervalos o eventos de su elección.

Postgres 9.5 introduce TABLESAMPLE SYSTEM (n)

Es muy rápido, pero el resultado es no exactamente aleatorio. El manual:

El método SYSTEM es significativamente más rápido que el método BERNOULLI cuando se especifican pequeños porcentajes de muestreo, pero puede devolver una muestra menos aleatoria de la tabla como resultado de los efectos de agrupación.

Y el número de filas devueltas puede variar enormemente. Para nuestro ejemplo, para obtener aproximadamente 1000 filas, try:

SELECT * FROM big TABLESAMPLE SYSTEM ((1000 * 100) / 5100000.0);

Donde n es un porcentaje. El manual:

Los métodos de muestreo BERNOULLI y SYSTEM aceptan un único método de muestreo argumento que es la fracción de la tabla a muestrear, expresada como un porcentaje entre 0 y 100. Este argumento puede ser cualquier expresión con valor real.

Negrita énfasis mío.

Relacionado:

O instale el módulo adicionaltsm_system_rows para obtener exactamente el número de filas solicitadas (si hay suficientes) y permitir la sintaxis más conveniente:

SELECT * FROM big TABLESAMPLE SYSTEM_ROWS(1000);

Ver La respuesta de Evan para más detalles.

Pero eso todavía no es exactamente aleatorio.

 166
Author: Erwin Brandstetter,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:26:34

Puede examinar y comparar el plan de ejecución de ambos usando

EXPLAIN select * from table where random() < 0.01;
EXPLAIN select * from table order by random() limit 1000;

Una prueba rápida en una mesa grande1 muestra, que el ORDER BY primero ordena la tabla completa y luego elige los primeros 1000 elementos. Ordenar una tabla grande no solo lee esa tabla, sino que también implica leer y escribir archivos temporales. El where random() < 0.1 solo escanea la tabla completa una vez.

Para tablas grandes esto podría no ser lo que desea, ya que incluso un análisis completo de la tabla podría tardar mucho.

Un tercero la propuesta sería

select * from table where random() < 0.01 limit 1000;

Este detiene el análisis de la tabla tan pronto como se han encontrado 1000 filas y, por lo tanto, regresa antes. Por supuesto, esto empaña la aleatoriedad un poco, pero tal vez esto es lo suficientemente bueno en su caso.

Edit: Además de estas consideraciones, puede consultar las preguntas ya hechas para esto. Usando la consulta [postgresql] random devuelve bastantes hits.

Y un artículo vinculado de depez que describe varios enfoques más:


1 "grande", como en "la tabla no caben en la memoria".

 76
Author: A.H.,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:26:34

Postgresql orden por random(), seleccionar filas en orden aleatorio:

select your_columns from your_table ORDER BY random()

Postgresql orden por random () con un distinto:

select * from 
  (select distinct your_columns from your_table) table_alias
ORDER BY random()

Orden de Postgresql por límite aleatorio de una fila:

select your_columns from your_table ORDER BY random() limit 1
 59
Author: Eric Leschinski,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-05-05 15:15:10

Comenzando con PostgreSQL 9.5, hay una nueva sintaxis dedicada a obtener elementos aleatorios de una tabla:

SELECT * FROM mytable TABLESAMPLE SYSTEM (5);

Este ejemplo le dará el 5% de los elementos de mytable.

Ver más explicación en esta entrada del blog: http://www.postgresql.org/docs/current/static/sql-select.html

 28
Author: Mickaël Le Baillif,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-01-25 10:24:28

El que tiene el ORDEN POR va a ser el más lento.

select * from table where random() < 0.01; va registro por registro, y decide filtrarlo aleatoriamente o no. Esto va a ser O(N) porque solo necesita verificar cada registro una vez.

select * from table order by random() limit 1000; va a ordenar toda la mesa, luego elegir los primeros 1000. Aparte de cualquier magia vudú detrás de las escenas, el orden por es O(N * log N).

La desventaja de la random() < 0.01 es que obtendrá un número variable de registros de salida.


Nota, hay un mejor manera de barajar un conjunto de datos que ordenar por azar: El Fisher-Yates Barajar, que se ejecuta en O(N). Sin embargo, implementar el shuffle en SQL suena como un gran desafío.

 23
Author: Donald Miner,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-12-29 23:46:46

Aquí hay una decisión que funciona para mí. Supongo que es muy simple de entender y ejecutar.

SELECT 
  field_1, 
  field_2, 
  field_2, 
  random() as ordering
FROM 
  big_table
WHERE 
  some_conditions
ORDER BY
  ordering 
LIMIT 1000;
 9
Author: Bogdan Surai,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-06-01 11:34:40
select * from table order by random() limit 1000;

Si sabes cuántas filas quieres, echa un vistazo tsm_system_rows.

Tsm_system_rows

El módulo proporciona el método de muestreo de tablas SYSTEM_ROWS, que se puede utilizar en la cláusula TABLES-SAMPLE de un comando SELECT.

Este método de muestreo de tabla acepta un solo argumento entero que es el número máximo de filas a leer. La muestra resultante siempre contendrá exactamente esas filas, a menos que la tabla no contenga suficientes filas, en las que caso se selecciona toda la tabla. Al igual que el método de muestreo del SISTEMA integrado, SYSTEM_ROWS realiza muestreo a nivel de bloque, de modo que la muestra no es completamente aleatoria, sino que puede estar sujeta a efectos de agrupación, especialmente si solo se solicita un pequeño número de filas.

Primero instale la extensión

CREATE EXTENSION tsm_system_rows;

Entonces su consulta,

SELECT *
FROM table
TABLESAMPLE SYSTEM_ROWS(1000);
 5
Author: Evan Carroll,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-12-27 01:03:24

Si desea una sola fila, puede usar un offset calculado derivado de count.

select * from table_name limit 1
offset floor(random() * (select count(*) from table_name));
 4
Author: Nelo Mitranim,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-09-12 09:16:56

Una variación de la vista materializada "Posible alternativa" esbozada por Erwin Brandstetter es posible.

Digamos, por ejemplo, que no desea duplicados en los valores aleatorios que se devuelven. Por lo tanto, deberá establecer un valor booleano en la tabla principal que contiene su conjunto de valores (no aleatorios).

Suponiendo que esta es la tabla de entrada:

id_values  id  |   used
           ----+--------
           1   |   FALSE
           2   |   FALSE
           3   |   FALSE
           4   |   FALSE
           5   |   FALSE
           ...

Rellene la tabla ID_VALUES según sea necesario. Luego, como lo describe Erwin, cree una vista materializada que aleatoriza la tabla ID_VALUES una vez:

CREATE MATERIALIZED VIEW id_values_randomized AS
  SELECT id
  FROM id_values
  ORDER BY random();

Tenga en cuenta que la vista materializada no contiene la columna utilizada, porque esto se desactualizará rápidamente. Tampoco es necesario que la vista contenga otras columnas que puedan estar en la tabla id_values.

Para obtener (y "consumir") valores aleatorios, utilice un UPDATE-RETURNING en id_values, seleccionando id_values de id_values_randomized con una combinación, y aplicando los criterios deseados para obtener solo posibilidades relevantes. Para ejemplo:

UPDATE id_values
SET used = TRUE
WHERE id_values.id IN 
  (SELECT i.id
    FROM id_values_randomized r INNER JOIN id_values i ON i.id = r.id
    WHERE (NOT i.used)
    LIMIT 5)
RETURNING id;

Cambie LIMIT según sea necesario if si solo necesita un valor aleatorio a la vez, cambie LIMIT a 1.

Con los índices adecuados en id_values, creo que el RETORNO de ACTUALIZACIÓN debería ejecutarse muy rápidamente con poca carga. Devuelve valores aleatorios con una base de datos ida y vuelta. Los criterios para las filas" elegibles " pueden ser tan complejos como sea necesario. Se pueden agregar nuevas filas a la tabla id_values en cualquier momento, y serán accesibles para la aplicación tan pronto como el la vista materializada se actualiza (lo que probablemente se puede ejecutar en un momento fuera de las horas punta). La creación y actualización de la vista materializada será lenta, pero solo necesita ejecutarse cuando se agreguen nuevos ID a la tabla id_values.

 2
Author: Raman,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:10:47

Agregue una columna llamada r con el tipo serial. Index r.

Supongamos que tenemos 200.000 filas, vamos a generar un número aleatorio n, donde 0 n

Seleccione filas con r > n, ordénelas ASC y seleccione la más pequeña.

Código:

select * from YOUR_TABLE 
where r > (
    select (
        select reltuples::bigint AS estimate
        from   pg_class
        where  oid = 'public.YOUR_TABLE'::regclass) * random()
    )
order by r asc limit(1);

El código se explica por sí mismo. La subconsulta en el medio se utiliza para estimar rápidamente los recuentos de filas de la tabla desde https://stackoverflow.com/a/7945274/1271094 .

En aplicación nivel necesita ejecutar la instrucción de nuevo si n > el número de filas o necesita seleccionar varias filas.

 0
Author: MK Yung,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:10:47

Sé que llego un poco tarde a la fiesta, pero acabo de encontrar esta increíble herramienta llamada pg_sample :

pg_sample - extraiga un pequeño conjunto de datos de muestra de una base de datos PostgreSQL más grande mientras mantiene la integridad referencial.

Probé esto con una base de datos de filas de 350M y fue muy rápido, no sé sobre la aleatoriedad .

./pg_sample --limit="small_table = *" --limit="large_table = 100000" -U postgres source_db | psql -U postgres target_db
 0
Author: Daniel Gerber,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-05-30 08:25:05