La mejor manera de seleccionar filas aleatorias PostgreSQL

performance random

Question

Quiero una selección aleatoria de filas en PostgreSQL, intenté 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ápida.

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

Answer 1

orden postgresql por aleatorio (), seleccione filas en orden aleatorio:

select your_columns from your_table ORDER BY random()

orden postgresql por random () con un distintivo:

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

orden postgresql por límite aleatorio una fila:

select your_columns from your_table ORDER BY random() limit 1

Answer 2

A partir de PostgreSQL 9.5, hay una nueva sintaxis dedicada a obtener elementos aleatorios de una tabla:

SELECT * FROM mytable TABLESAMPLE SYSTEM (5);

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

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

Answer 3

Agregue una columna llamada r con tipo serial . Índice r .

Supongamos que tenemos 200,000 filas, vamos a generar un número aleatorio n , donde 0 < n <= 200, 000.

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 es autoexplicativo. La subconsulta en el medio se utiliza para estimar rápidamente los recuentos de filas de la tabla desde https://.com/a/7945274/1271094 .

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

Answer 4

Aquí hay una decisión que me funciona. 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;

Answer 5

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

• Tiene una columna de ID numérica (números enteros) con solo algunos huecos (o moderadamente pocos).
• Obviamente ninguna o pocas operaciones de escritura.
• Tu columna de ID tiene que ser indexada! Una clave principal sirve muy bien.

La siguiente consulta no necesita una exploración secuencial de la tabla grande, solo una exploración 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;

La única parte posiblemente costosa es la count(*) (para tablas grandes). Teniendo en cuenta las especificaciones anteriores, no es necesario. 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;

Siempre que 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

• Generar números aleatorios en el espacio de id . Tiene "pocos huecos", así que agregue 10% (lo suficiente para cubrir fácilmente los espacios en blanco) al número de filas para recuperar.

• Cada id se puede seleccionar varias veces por casualidad (aunque es muy poco probable que tenga un gran espacio de identificación), así que agrupe los números generados (o use DISTINCT ).

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

• Finalmente, recorte las id excedentes que no hayan sido devoradas por los duplicados y las brechas. Cada fila tiene la misma posibilidad de ser elegida.

Version corta

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 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 excedente más pequeño 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 huecos en el espacio de ID o la recursión puede 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 la UNION en el rCTE.

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

Esta consulta se ha redactado cuidadosamente para usar el índice disponible, generar filas realmente aleatorias y no detenerse hasta que completemos el límite (a menos que la recursión se agote). Hay una serie de escollos aquí si va a reescribirlo.

Envolver en la función

Para uso repetido con diferentes parámetros:

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á fuera del alcance de esta pregunta. Ver:

• Refactorice una función PL / pgSQL para devolver la salida de varias consultas SELECT

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 la velocidad del aligeramiento. Actualice su selección al azar en intervalos o eventos de su elección.

Postgres 9.5 presenta TABLESAMPLE SYSTEM (n)

Es muy rápido , pero el resultado no es 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, intente:

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 cada uno un único 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 de valor real .

Énfasis en negrita el mio

Relacionado:

• Forma rápida de descubrir el recuento de filas de una tabla en PostgreSQL

O instale el módulo adicional tsm_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);

Vea la respuesta de Evan para más detalles.

Pero eso todavía no es exactamente aleatorio.

Answer 6

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 será O(N) porque solo necesita revisar cada registro una vez.

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

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

Tenga en cuenta que hay una mejor manera de barajar un conjunto de datos que ordenarlos al azar: El Shuffle de Fisher-Yates , que se ejecuta en O(N) . Sin embargo, implementar el shuffle en SQL parece ser todo un desafío.

Answer 7

Puedes 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 tabla grande ¹ muestra que ORDER BY primero ordena la tabla completa y luego selecciona los primeros 1000 elementos. Ordenar una tabla grande no solo lee esa tabla sino que también implica leer y escribir archivos temporales. 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 puede llevar demasiado tiempo.

Una tercera propuesta sería

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

Este detiene el escaneo de la tabla tan pronto como se hayan encontrado 1000 filas y, por lo tanto, vuelve antes. Por supuesto, esto atasca un poco la aleatoriedad, pero quizás esto sea lo suficientemente bueno en tu caso.

Edición: Además de estas consideraciones, puede consultar las preguntas ya formuladas para esto. El uso de la consulta [postgresql] random devuelve bastantes resultados.

• Selección aleatoria rápida de filas en Postgres
• ¿Cómo recuperar filas de datos aleatorios de una tabla postgreSQL?
• postgres: obtener entradas aleatorias de la tabla - demasiado lento

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

• http://www.depesz.com/index.php/2007/09/16/my-thoughts-on-getting-random-row/

¹ "grande" como en "la tabla completa no cabrá en la memoria".

Answer 8

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.

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

./pg_sample --limit="small_table = *" --limit="large_table = 100000" -U postgres source_db | psql -U postgres target_db

Answer 9

Si desea solo una fila, puede usar un offset calculado derivado del count .

select * from table_name limit 1
offset floor(random() * (select count(*) from table_name));

Answer 10

Una variación de la vista materializada "Alternativa posible" 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 contenga 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
...

ID_VALUES tabla ID_VALUES según sea necesario. Luego, según lo descrito por Erwin, cree una vista materializada que aleatorice 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, ya que esta quedará obsoleta rápidamente. Tampoco la vista debe contener otras columnas que pueden estar en la tabla id_values .

Para obtener (y "consumir") valores aleatorios, use UPDATE-RETURNING en id_values , seleccionando id_values from id_values_randomized con una unión, y aplicando los criterios deseados para obtener solo las posibilidades relevantes. Por 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; si solo necesita un valor aleatorio a la vez, cambie LIMIT a 1 .

Con los índices adecuados en id_values , creo que UPDATE-RETURNING debería ejecutarse muy rápidamente con poca carga. Devuelve valores aleatorios con una base de datos de ida y vuelta. Los criterios para las filas "elegibles" pueden ser tan complejos como se requiera. Las nuevas filas se pueden agregar a la tabla id_values en cualquier momento, y serán accesibles para la aplicación tan pronto como la vista materializada se actualice (lo que probablemente se puede ejecutar en un horario no pico). La creación y actualización de la vista materializada será lenta, pero solo debe ejecutarse cuando se agreguen nuevos ID a la tabla id_values .

Answer 11

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

Si sabe cuántas filas desea, eche un vistazo a tsm_system_rows .

tsm_system_rows

el módulo proporciona el método de muestreo de tabla SYSTEM_ROWS, que se puede utilizar en la cláusula TABLESAMPLE de un comando SELECT.

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

Primero instala la extensión

CREATE EXTENSION tsm_system_rows;

Entonces su consulta,

SELECT *
FROM table
TABLESAMPLE SYSTEM_ROWS(1000);