seleção rápida de linha aleatória no Postgres

95

Eu tenho uma tabela no postgres que contém alguns milhões de linhas. Eu verifiquei na internet e encontrei o seguinte

SELECT myid FROM mytable ORDER BY RANDOM() LIMIT 1;

Funciona, mas é muito lento ... existe outra forma de fazer essa consulta, ou uma forma direta de selecionar uma linha aleatória sem ler toda a tabela? A propósito, 'myid' é um número inteiro, mas pode ser um campo vazio.

Juan
fonte
1
Se você deseja selecionar várias linhas aleatórias, consulte esta pergunta: stackoverflow.com/q/8674718/247696
Flimm

Respostas:

97

Você pode querer experimentar OFFSET, como em

SELECT myid FROM mytable OFFSET floor(random()*N) LIMIT 1;

O Né o número de linhas em mytable. Você pode precisar primeiro fazer um SELECT COUNT(*)para descobrir o valor deN .

Atualizar (por Antony Hatchkins)

Você deve usar flooraqui:

SELECT myid FROM mytable OFFSET floor(random()*N) LIMIT 1;

Considere uma tabela de 2 linhas; random()*Ngera 0 <= x < 2e, por exemplo, SELECT myid FROM mytable OFFSET 1.7 LIMIT 1;retorna 0 linhas devido ao arredondamento implícito para o int mais próximo.

NPE
fonte
faz sentido usar um N menor que SELECT COUNT(*)?, quer dizer, não usar todos os valores da tabela, mas apenas uma parte deles?
Juan
@Juan Isso depende de seus requisitos.
NPE
usando o EXPLAIN SELECT ...com valores diferentes de N dá o mesmo custo para a consulta, então eu acho que é melhor ir para o valor máximo de N.
Juan
3
veja uma correção de
bug
2
Isso tem um erro off por um. Ele nunca retornará a primeira linha e gerará um erro 1 / COUNT (*) porque tentará retornar a linha após a última linha.
Ian
60

PostgreSQL 9.5 introduziu uma nova abordagem para seleção de amostra muito mais rápida: TABLESAMPLE

A sintaxe é

SELECT * FROM my_table TABLESAMPLE BERNOULLI(percentage);
SELECT * FROM my_table TABLESAMPLE SYSTEM(percentage);

Esta não é a solução ideal se você deseja apenas uma linha selecionada, porque você precisa saber a CONTAGEM da tabela para calcular a porcentagem exata.

Para evitar um COUNT lento e usar TABLESAMPLE rápido para tabelas de 1 linha a bilhões de linhas, você pode fazer:

 SELECT * FROM my_table TABLESAMPLE SYSTEM(0.000001) LIMIT 1;
 -- if you got no result:
 SELECT * FROM my_table TABLESAMPLE SYSTEM(0.00001) LIMIT 1;
 -- if you got no result:
 SELECT * FROM my_table TABLESAMPLE SYSTEM(0.0001) LIMIT 1;
 -- if you got no result:
 SELECT * FROM my_table TABLESAMPLE SYSTEM(0.001) LIMIT 1;
 ...

Isso pode não parecer tão elegante, mas provavelmente é mais rápido do que qualquer uma das outras respostas.

Para decidir se deseja usar o BERNULLI oder SYSTEM, leia sobre a diferença em http://blog.2ndquadrant.com/tablesample-in-postgresql-9-5-2/

alfonx
fonte
2
Isso é muito mais rápido e fácil do que qualquer outra resposta - esta deve estar no topo.
Hayden Schiff
1
Por que você não pode simplesmente usar uma subconsulta para obter a contagem? SELECT * FROM my_table TABLESAMPLE SYSTEM(SELECT 1/COUNT(*) FROM my_table) LIMIT 1;?
machineghost
2
@machineghost "Para evitar uma contagem lenta ..." ... Se seus dados são tão pequenos que você pode contar em um tempo razoável, vá em frente! :-)
alfonx
2
@machineghost Use SELECT reltuples FROM pg_class WHERE relname = 'my_table'para estimativa de contagem.
Hynek -Pichi- Vychodil
@ Hynek-Pichi-Vychodil entrada muito boa! Para garantir que a estimativa não esteja desatualizada, ela deve ser ANALISADA A VÁCUO recentemente .. mas um bom banco de dados deve ser analisado adequadamente de qualquer maneira .. E tudo depende do caso de uso específico. Normalmente mesas grandes não crescem tão rápido ... Obrigado!
alfonx
34

Eu tentei isso com uma subconsulta e funcionou bem. O deslocamento, pelo menos no Postgresql v8.4.4, funciona bem.

select * from mytable offset random() * (select count(*) from mytable) limit 1 ;
John Coryat
fonte
Na verdade, a v8.4 é essencial para que isso funcione, não funciona para <= 8,3.
Antony Hatchkins,
1
veja uma correção de
bug
30

Você precisa usar floor:

SELECT myid FROM mytable OFFSET floor(random()*N) LIMIT 1;
Antony Hatchkins
fonte
Considere uma tabela de 2 linhas; random()*Ngera 0 <= x <2 e, por exemplo, SELECT myid FROM mytable OFFSET 1.7 LIMIT 1;retorna 0 linhas devido ao arredondamento implícito para o int mais próximo.
Antony Hatchkins,
Infelizmente isso não funciona se você quiser usar um LIMIT maior ... Eu preciso obter 3 itens, então preciso usar a sintaxe ORDER BY RANDOM ().
Alexis Wilke
1
Três consultas consecutivas ainda serão mais rápidas do que uma order by random(), aproximadamente como 3*O(N) < O(NlogN)- os números da vida real serão ligeiramente diferentes devido aos índices.
Antony Hatchkins
Meu problema é que os 3 itens precisam ser distintos e um WHERE myid NOT IN (1st-myid)e WHERE myid NOT IN (1st-myid, 2nd-myid)não funcionariam já que a decisão é feita pelo OFFSET. Hmmm ... acho que poderia reduzir N em 1 e 2 no segundo e no terceiro SELECT.
Alexis Wilke
Você ou alguém poderia expandir esta resposta com uma resposta de por que eu preciso usar floor()? Que vantagem isso oferece?
ADTC
14

Verifique este link para algumas opções diferentes. http://www.depesz.com/index.php/2007/09/16/my-thoughts-on-getting-random-row/

Atualizar: (A. Hatchkins)

O resumo do (muito) longo artigo é o seguinte.

O autor lista quatro abordagens:

1) ORDER BY random() LIMIT 1; - lento

2) ORDER BY id where id>=random()*N LIMIT 1- não uniforme se houver lacunas

3) coluna aleatória - precisa ser atualizada de vez em quando

4) agregado aleatório personalizado - método astuto, pode ser lento: random () precisa ser gerado N vezes

e sugere melhorar o método 2 usando

5) ORDER BY id where id=random()*N LIMIT 1 com repetições subsequentes se o resultado estiver vazio.

Kuberchaun
fonte
Eu me pergunto por que eles não cobriram OFFSET? Usar um ORDER está fora de questão apenas para obter uma linha aleatória. Felizmente, OFFSET está bem coberto nas respostas.
androidguy
4

A maneira mais fácil e rápida de buscar linha aleatória é usar a tsm_system_rowsextensão:

CREATE EXTENSION IF NOT EXISTS tsm_system_rows;

Em seguida, você pode selecionar o número exato de linhas que deseja:

SELECT myid  FROM mytable TABLESAMPLE SYSTEM_ROWS(1);

Isso está disponível com PostgreSQL 9.5 e posterior.

Veja: https://www.postgresql.org/docs/current/static/tsm-system-rows.html

daamien
fonte
1
Aviso justo, isso não é completamente aleatório. Em tabelas menores, sempre retornei as primeiras linhas em ordem.
Ben Aubin de
1
sim, isso é claramente explicado na documentação (link acima): «Como o método de amostragem SYSTEM embutido, SYSTEM_ROWS realiza amostragem em nível de bloco, de forma que a amostra não seja completamente aleatória, mas pode estar sujeita a efeitos de agrupamento, especialmente se apenas um pequeno número de linhas são solicitadas. ». Se você tiver um pequeno conjunto de dados, o ORDER BY random() LIMIT 1;deve ser rápido o suficiente.
daamien
Eu vi isso. Só queria deixar claro para qualquer pessoa que não clica no link ou se o link será desativado no futuro.
Ben Aubin
1
Também vale a pena notar que isso só funcionará para selecionar linhas aleatórias de uma tabela e filtrar ENTÃO, ao contrário / comparado a executar uma consulta e, em seguida, selecionar um ou alguns registros aleatoriamente.
nomen
3

Eu vim com uma solução muito rápida sem TABLESAMPLE. Muito mais rápido do que OFFSET random()*N LIMIT 1. Nem mesmo requer contagem de mesa.

A ideia é criar um índice de expressão com dados aleatórios, mas previsíveis, por exemplo md5(primary key).

Aqui está um teste com dados de amostra de 1 milhão de linhas:

create table randtest (id serial primary key, data int not null);

insert into randtest (data) select (random()*1000000)::int from generate_series(1,1000000);

create index randtest_md5_id_idx on randtest (md5(id::text));

explain analyze
select * from randtest where md5(id::text)>md5(random()::text)
order by md5(id::text) limit 1;

Resultado:

 Limit  (cost=0.42..0.68 rows=1 width=8) (actual time=6.219..6.220 rows=1 loops=1)
   ->  Index Scan using randtest_md5_id_idx on randtest  (cost=0.42..84040.42 rows=333333 width=8) (actual time=6.217..6.217 rows=1 loops=1)
         Filter: (md5((id)::text) > md5((random())::text))
         Rows Removed by Filter: 1831
 Total runtime: 6.245 ms

Esta consulta pode às vezes (com probabilidade de cerca de 1 / Número_de_rows) retornar 0 linhas, então ela precisa ser verificada e executada novamente. Além disso, as probabilidades não são exatamente as mesmas - algumas linhas são mais prováveis ​​do que outras.

Para comparação:

explain analyze SELECT id FROM randtest OFFSET random()*1000000 LIMIT 1;

Os resultados variam muito, mas podem ser muito ruins:

 Limit  (cost=1442.50..1442.51 rows=1 width=4) (actual time=179.183..179.184 rows=1 loops=1)
   ->  Seq Scan on randtest  (cost=0.00..14425.00 rows=1000000 width=4) (actual time=0.016..134.835 rows=915702 loops=1)
 Total runtime: 179.211 ms
(3 rows)
Tometzky
fonte
2
Sim, rápido. Verdadeiramente aleatório, não. Um valor md5 que passa a ser o próximo maior valor após outro valor existente tem uma chance muito pequena de ser escolhido, enquanto os valores após um grande intervalo no espaço numérico têm uma chance muito maior (maior pelo número de valores possíveis entre) . A distribuição resultante não é aleatória.
Erwin Brandstetter
muito interessante, poderia funcionar em um caso de uso de uma consulta do tipo loteria: a consulta deve examinar todos os bilhetes disponíveis e retornar aleatoriamente apenas UM bilhete único. também posso usar um bloqueio pessimista (selecione ... para atualização) com sua técnica?
Mathieu
Para qualquer coisa relacionada à loteria, você deve usar uma amostragem aleatória justa e criptograficamente segura - por exemplo, escolha um número aleatório entre 1 e máximo (id) até encontrar a id existente. O método desta resposta não é justo nem seguro - é rápido. Pode ser usado para coisas como 'obter 1% de linhas aleatórias para testar algo' ou 'mostrar 5 entradas aleatórias'.
Tometzky