Eu quero uma seleção aleatória de linhas no PostgreSQL, tentei o seguinte:

select * from table where random() < 0.01;

Mas alguns outros recomendam isso:

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

Eu tenho uma tabela muito grande com 500 milhões de linhas, quero que seja rápida.

Qual abordagem é melhor? Quais são as diferenças? Qual é a melhor maneira de selecionar linhas aleatórias?

Dadas as suas especificações (além de informações adicionais nos comentários),

• Você tem uma coluna de ID numérica (números inteiros) com apenas algumas (ou moderadamente poucas) lacunas.
• Obviamente, nenhuma ou poucas operações de gravação.
• Sua coluna de ID deve ser indexada! Uma chave primária serve muito bem.

A consulta abaixo não precisa de uma varredura seqüencial da tabela grande, apenas uma varredura de índice.

Primeiro, obtenha estimativas para a 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;

A única parte possivelmente cara é a count(*)(para mesas enormes). Dadas as especificações acima, você não precisa disso. Uma estimativa funcionará perfeitamente, disponível quase sem custo ( explicação detalhada aqui ):

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

Desde que ctnão seja muito menor id_span, a consulta superará outras abordagens.

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

• Gere números aleatórios no idespaço. Você tem "poucas lacunas", então adicione 10% (o suficiente para cobrir facilmente os espaços em branco) ao número de linhas a serem recuperadas.

• Cada um idpode ser escolhido várias vezes por acaso (embora seja muito improvável com um grande espaço de identificação), portanto, agrupe os números gerados (ou use DISTINCT).

• Junte os ids à mesa grande. Isso deve ser muito rápido com o índice no lugar.

• Finalmente, apare os excedentes idque não foram consumidos por burros e lacunas. Cada linha tem uma chance completamente igual de ser escolhida.

Versão curta

Você pode simplificar esta consulta. O CTE na consulta acima é apenas para fins educacionais:

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 com rCTE

Especialmente se você não tiver tanta certeza sobre lacunas e estimativas.

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 trabalhar com um excedente menor na consulta base. Se houver muitas lacunas para não encontrar linhas suficientes na primeira iteração, o rCTE continuará a iterar com o termo recursivo. Ainda precisamos de relativamente poucas lacunas no espaço de identificação ou a recursão pode ficar seca antes que o limite seja atingido - ou precisamos começar com um buffer grande o suficiente que desafie o objetivo de otimizar o desempenho.

As duplicatas são eliminadas pelo UNIONno rCTE.

O externo LIMITfaz o CTE parar assim que tivermos linhas suficientes.

Essa consulta é cuidadosamente elaborada para usar o índice disponível, gerar linhas realmente aleatórias e não parar até cumprirmos o limite (a menos que a recursão se esgote). Existem várias armadilhas aqui, se você deseja reescrevê-lo.

Enrole em função

Para uso repetido com vários 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;

Ligar:

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

Você pode até fazer esse genérico funcionar em qualquer tabela: Pegue o nome da coluna PK e a tabela como tipo polimórfico e use EXECUTE... Mas isso está além do escopo desta pergunta. Vejo:

• Refatorar uma função PL / pgSQL para retornar a saída de várias consultas SELECT

Alternativa possível

Se seus requisitos permitirem conjuntos idênticos para chamadas repetidas (e estamos falando de chamadas repetidas), consideraria uma visão materializada . Execute a consulta acima uma vez e escreva o resultado em uma tabela. Os usuários obtêm uma seleção quase aleatória na velocidade da luz. Atualize sua escolha aleatória em intervalos ou eventos de sua escolha.

O Postgres 9.5 apresenta TABLESAMPLE SYSTEM (n)

Onde nestá uma porcentagem. O manual:

O BERNOULLIeSYSTEM métodos amostragem aceitam um único argumento, que é a fração da tabela a ser amostrada, expressa como uma porcentagem entre 0 e 100 . Este argumento pode ser qualquer realexpressão com valor.

Negrito ênfase minha. É muito rápido , mas o resultado não é exatamente aleatório . O manual novamente:

o SYSTEM método é significativamente mais rápido que o BERNOULLImétodo quando pequenas porcentagens de amostragem são especificadas, mas pode retornar uma amostra menos aleatória da tabela como resultado de efeitos de cluster.

O número de linhas retornadas pode variar bastante. Para o nosso exemplo, para obter aproximadamente 1000 linhas:

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

Relacionado:

• Maneira rápida de descobrir a contagem de linhas de uma tabela no PostgreSQL

Ou instale o módulo adicional tsm_system_rows para obter exatamente o número de linhas solicitadas (se houver o suficiente) e permitir a sintaxe mais conveniente:

SELECT * FROM big TABLESAMPLE SYSTEM_ROWS(1000);

Vejo a resposta de Evan para detalhes.

Mas isso ainda não é exatamente aleatório.

Você pode examinar e comparar o plano de execução de ambos usando

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

Um teste rápido em uma tabela grande ¹ mostra que a ORDER BYprimeira classifica a tabela completa e depois escolhe os primeiros 1000 itens. A classificação de uma tabela grande não apenas lê essa tabela, mas também envolve a leitura e gravação de arquivos temporários. A where random() < 0.1única varre a tabela completa uma vez.

Para tabelas grandes, isso pode não ser o que você deseja, pois mesmo uma verificação completa da tabela pode levar muito tempo.

Uma terceira proposta seria

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

Esse procedimento interrompe a verificação da tabela assim que 1000 linhas forem encontradas e, portanto, retorna mais cedo. É claro que isso atrapalha um pouco a aleatoriedade, mas talvez isso seja bom o suficiente no seu caso.

Editar: Além dessas considerações, você pode conferir as perguntas já feitas para isso. O uso da consulta [postgresql] randomretorna alguns hits.

• seleção rápida de linhas aleatórias no Postgres
• Como recuperar linhas de dados aleatórios de uma tabela postgreSQL?
• postgres: obtém entradas aleatórias da tabela - muito lento

E um artigo vinculado de depez descrevendo várias outras abordagens:

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

¹ "grande" como em "a tabela completa não cabe na memória".

ordem do postgresql por random (), selecione as linhas em ordem aleatória:

select your_columns from your_table ORDER BY random()

ordem do postgresql por random () com uma distinta:

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

ordem do postgresql por limite aleatório uma linha:

select your_columns from your_table ORDER BY random() limit 1

A partir do PostgreSQL 9.5, há uma nova sintaxe dedicada a obter elementos aleatórios de uma tabela:

SELECT * FROM mytable TABLESAMPLE SYSTEM (5);

Este exemplo fornece 5% de elementos de mytable.

Veja mais explicações nesta postagem do blog: http://www.postgresql.org/docs/current/static/sql-select.html

Aquele com o ORDER BY será o mais lento.

select * from table where random() < 0.01;vai registro por registro e decide filtrá-lo aleatoriamente ou não. Isso acontece O(N)porque ele só precisa verificar cada registro uma vez.

select * from table order by random() limit 1000;vai ordenar a mesa inteira e depois escolher as primeiras 1000. Além de qualquer magia vodu nos bastidores, a ordem é O(N * log N).

A desvantagem random() < 0.01é que você obterá um número variável de registros de saída.

Observe que há uma maneira melhor de embaralhar um conjunto de dados do que classificar aleatoriamente: o Fisher-Yates Shuffle , que é executado O(N). A implementação do shuffle no SQL parece um grande desafio.

Aqui está uma decisão que funciona para mim. Eu acho que é muito simples de entender e executar.

SELECT 
  field_1, 
  field_2, 
  field_2, 
  random() as ordering
FROM 
  big_table
WHERE 
  some_conditions
ORDER BY
  ordering 
LIMIT 1000;

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

Se você souber quantas linhas deseja, confira tsm_system_rows.

tsm_system_rows

O módulo fornece o método de amostragem de tabela SYSTEM_ROWS, que pode ser usado na cláusula TABLESAMPLE de um comando SELECT.

Este método de amostragem de tabela aceita um único argumento inteiro que é o número máximo de linhas a serem lidas. A amostra resultante sempre conterá exatamente o número de linhas, a menos que a tabela não contenha linhas suficientes; nesse caso, a tabela inteira será selecionada. Como o método de amostragem SYSTEM embutido, SYSTEM_ROWS executa amostragem em nível de bloco, para que a amostra não seja completamente aleatória, mas possa estar sujeita a efeitos de cluster, especialmente se apenas um pequeno número de linhas for solicitado.

Primeiro instale a extensão

CREATE EXTENSION tsm_system_rows;

Então sua consulta,

SELECT *
FROM table
TABLESAMPLE SYSTEM_ROWS(1000);

Se você quiser apenas uma linha, poderá usar um calculado offsetderivado de count.

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

É possível uma variação da visão materializada "Possível alternativa" descrita por Erwin Brandstetter .

Diga, por exemplo, que você não deseja duplicatas nos valores aleatórios retornados. Portanto, você precisará definir um valor booleano na tabela principal que contém seu conjunto de valores (não randomizados).

Supondo que esta seja a tabela de entrada:

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

Preencha a ID_VALUEStabela conforme necessário. Em seguida, conforme descrito por Erwin, crie uma visão materializada que randomize a ID_VALUEStabela uma vez:

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

Observe que a visualização materializada não contém a coluna usada, porque isso rapidamente se tornará desatualizado. A visualização também não precisa conter outras colunas que possam estar noid_values tabela.

Para obter (e "consumir") valores aleatórios, use um UPDATE-RETURNING id_values, selecionando a id_valuespartir de id_values_randomizeduma junção e aplicando os critérios desejados para obter apenas possibilidades relevantes. Por exemplo:

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;

Altere LIMITconforme necessário - se você precisar apenas de um valor aleatório por vez, mude LIMITpara 1.

Com os índices adequados ativados id_values, acredito que o UPDATE-RETURNING deve ser executado muito rapidamente com pouca carga. Retorna valores aleatórios com um ida e volta ao banco de dados. Os critérios para linhas "elegíveis" podem ser tão complexos quanto necessário. Novas linhas podem ser adicionadas à id_valuestabela a qualquer momento e elas se tornarão acessíveis ao aplicativo assim que a exibição materializada for atualizada (o que provavelmente pode ser executado em um horário fora do pico). A criação e a atualização da visualização materializada serão lentas, mas só precisam ser executadas quando novos IDs forem adicionados à id_valuestabela.

Uma lição da minha experiência:

offset floor(random() * N) limit 1não é mais rápido que order by random() limit 1.

Eu pensei que a offsetabordagem seria mais rápida, pois economizaria o tempo de classificação no Postgres. Acontece que não era.

Adicionar uma coluna chamada rcom o tipo serial. Índicer .

Suponha que temos 200.000 linhas, vamos gerar um número aleatório n, onde 0 <n <<= 200.000.

Selecione as linhas com r > n, classifique-asASC e selecione a menor.

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);

O código é auto-explicativo. A subconsulta no meio é usada para estimar rapidamente a contagem de linhas da tabela em https://stackoverflow.com/a/7945274/1271094 .

No nível do aplicativo, você precisa executar a instrução novamente se n> o número de linhas ou precisar selecionar várias linhas.

Eu sei que estou um pouco atrasado para a festa, mas eu encontrei esta ferramenta incrível chamada pg_sample :

pg_sample - extrai um pequeno conjunto de dados de amostra de um banco de dados PostgreSQL maior, mantendo a integridade referencial.

Eu tentei isso com um banco de dados de 350 milhões de linhas e foi muito rápido, não sei sobre a aleatoriedade .

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