Como faço para obter uma amostra aleatória simples eficiente no SQL? O banco de dados em questão está executando MySQL; minha tabela tem pelo menos 200.000 linhas e quero uma amostra aleatória simples de cerca de 10.000.

A resposta "óbvia" é:

SELECT * FROM table ORDER BY RAND() LIMIT 10000

Para tabelas grandes, isso é muito lento: ele chama RAND()cada linha (o que já o coloca em O (n)) e os classifica, tornando-o O (n lg n) na melhor das hipóteses. Existe uma maneira de fazer isso mais rápido do que O (n)?

Nota : Como Andrew Mao aponta nos comentários, se você estiver usando essa abordagem no SQL Server, deve usar a função T-SQL NEWID(), porque RAND () pode retornar o mesmo valor para todas as linhas .

EDITAR: 5 ANOS DEPOIS

Eu me deparei com esse problema novamente com uma mesa maior e acabei usando uma versão da solução do @inognant, com dois ajustes:

• Amostrar as linhas de 2 a 5x o tamanho de amostra desejado, a baixo custo ORDER BY RAND()
• Salve o resultado de RAND()em uma coluna indexada em cada inserção / atualização. (Se o seu conjunto de dados não for muito atualizado, pode ser necessário encontrar outra maneira de manter esta coluna atualizada.)

Para obter uma amostra de 1000 itens de uma tabela, conto as linhas e faço uma amostra do resultado até, em média, 10.000 linhas com a coluna 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

(Minha implementação real envolve mais trabalho para garantir que eu não subamostra, e para envolver manualmente rand_high, mas a ideia básica é "cortar aleatoriamente seu N para alguns milhares.")

Embora isso faça alguns sacrifícios, me permite analisar o banco de dados usando uma varredura de índice, até que esteja pequeno o suficiente para ORDER BY RAND()novamente.

Há uma discussão muito interessante sobre esse tipo de problema aqui: http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/

Acho que sem suposições sobre a tabela de que sua solução O (n lg n) é a melhor. Embora, na verdade, com um bom otimizador ou uma técnica um pouco diferente, a consulta que você lista possa ser um pouco melhor, O (m * n) onde m é o número de linhas aleatórias desejadas, já que não seria necessário ordenar todo o grande array , ele poderia apenas pesquisar os menores tempos. Mas para o tipo de números que você postou, m é maior do que lg n de qualquer maneira.

Três suposições que podemos experimentar:

1. há uma chave primária única indexada na tabela

2. o número de linhas aleatórias que você deseja selecionar (m) é muito menor do que o número de linhas na tabela (n)

3. a chave primária única é um número inteiro que varia de 1 a n sem lacunas

Com apenas as suposições 1 e 2, acho que isso pode ser feito em O (n), embora você precise escrever um índice inteiro na tabela para corresponder à suposição 3, portanto, não é necessariamente um O (n) rápido. Se pudermos ADICIONALMENTE assumir algo mais interessante sobre a mesa, podemos fazer a tarefa em O (m log m). A suposição 3 seria uma propriedade adicional agradável e fácil de trabalhar. Com um bom gerador de números aleatórios que não garantisse duplicatas ao gerar m números em uma linha, uma solução O (m) seria possível.

Dadas as três suposições, a ideia básica é gerar m números aleatórios únicos entre 1 e n e, em seguida, selecionar as linhas com essas chaves da tabela. Não tenho mysql ou qualquer coisa na minha frente agora, então em um pseudocódigo levemente parecido com:

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

Se você estiver realmente preocupado com a eficiência, pode considerar fazer a geração de chave aleatória em algum tipo de linguagem procedural e inserir os resultados no banco de dados, já que quase qualquer coisa diferente de SQL provavelmente seria melhor no tipo de loop e geração de número aleatório necessária .

Acho que a solução mais rápida é

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

Aqui está porque eu acho que isso deve funcionar.

• Isso criará um número aleatório para cada linha. O número está entre 0 e 1
• Ele avalia se deve exibir essa linha se o número gerado estiver entre 0 e 0,3 (30%).

Isso assume que rand () está gerando números em uma distribuição uniforme. É a maneira mais rápida de fazer isso.

Eu vi que alguém havia recomendado essa solução e eles foram abatidos sem provas .. aqui está o que eu diria sobre isso -

• Este é O (n), mas nenhuma classificação é necessária, por isso é mais rápido que o O (n lg n)

• mysql é muito capaz de gerar números aleatórios para cada linha. Experimente isto -

  selecione rand () no limite 10 de INFORMATION_SCHEMA.TABLES;

Como o banco de dados em questão é mySQL, esta é a solução certa.

Aparentemente, em algumas versões do SQL existe um TABLESAMPLEcomando, mas não em todas as implementações de SQL (notavelmente, Redshift).

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

Apenas use

WHERE RAND() < 0.1 

para obter 10% dos registros ou

WHERE RAND() < 0.01 

para obter 1% dos registros, etc.

Mais rápido que ORDER BY RAND ()

Testei esse método para ser muito mais rápido do que ORDER BY RAND(), portanto, ele é executado no tempo O (n) e é impressionantemente rápido.

De http://technet.microsoft.com/en-us/library/ms189108%28v=sql.105%29.aspx :

Versão não MSSQL - não testei

SELECT * FROM Sales.SalesOrderDetail
WHERE 0.01 >= RAND()

Versão MSSQL:

SELECT * FROM Sales.SalesOrderDetail
WHERE 0.01 >= CAST(CHECKSUM(NEWID(), SalesOrderID) & 0x7fffffff AS float) / CAST (0x7fffffff AS int)

Isso selecionará cerca de 1% dos registros. Portanto, se você precisar selecionar o número exato de porcentagens ou registros, estime sua porcentagem com alguma margem de segurança e, em seguida, retire os registros em excesso do conjunto resultante, usando o ORDER BY RAND()método mais caro .

Ainda mais rápido

Consegui aprimorar esse método ainda mais porque tinha uma faixa de valores de coluna indexada bem conhecida.

Por exemplo, se você tiver uma coluna indexada com inteiros uniformemente distribuídos [0..max], você pode usar isso para selecionar aleatoriamente N pequenos intervalos. Faça isso dinamicamente em seu programa para obter um conjunto diferente para cada consulta executada. Esta seleção de subconjunto será O (N) , que pode muitas ordens de magnitude menor do que seu conjunto de dados completo.

Em meu teste, reduzi o tempo necessário para obter 20 (de 20 mil) registros de amostra de 3 minutos usando ORDER BY RAND () para 0,0 segundos !

Quero salientar que todas essas soluções parecem ter amostra sem substituição. Selecionar as primeiras K linhas de uma classificação aleatória ou unir-se a uma tabela que contém chaves exclusivas em ordem aleatória resultará em uma amostra aleatória gerada sem substituição.

Se quiser que sua amostra seja independente, você precisará fazer uma amostra com reposição. Consulte a Questão 25451034 para obter um exemplo de como fazer isso usando JOIN de maneira semelhante à solução do usuário12861. A solução foi escrita para T-SQL, mas o conceito funciona em qualquer banco de dados SQL.

Em certos dialetos como Microsoft SQL Server, PostgreSQL e Oracle (mas não MySQL ou SQLite), você pode fazer algo como

select distinct top 10000 customer_id from nielsen.dbo.customer TABLESAMPLE (20000 rows) REPEATABLE (123);

A razão para não apenas fazer (10000 rows)sem o topé que a TABLESAMPLElógica fornece um número extremamente inexato de linhas (como às vezes 75% disso, às vezes 1,25% vezes isso), então você deseja sobreamostrar e selecionar o número exato que deseja. O REPEATABLE (123)serve para fornecer uma semente aleatória.

Começando com a observação de que podemos recuperar os ids de uma tabela (por exemplo, contagem 5) com base em um conjunto:

select *
from table_name
where _id in (4, 1, 2, 5, 3)

podemos chegar ao resultado que, se pudéssemos gerar a string "(4, 1, 2, 5, 3)", teríamos uma maneira mais eficiente do que RAND().

Por exemplo, em 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(']', ')');

Se os ids tiverem lacunas, o arraylist inicial indicesé o resultado de uma consulta sql em ids.

Se você precisar exatamente de mlinhas, realisticamente, você gerará seu subconjunto de IDs fora do SQL. A maioria dos métodos requer, em algum ponto, a seleção da "enésima" entrada, e as tabelas SQL realmente não são arrays. A suposição de que as chaves são consecutivas apenas para unir ints aleatórios entre 1 e a contagem também é difícil de satisfazer - o MySQL, por exemplo, não suporta nativamente, e as condições de bloqueio são ... complicadas .

Aqui está uma solução -time O(max(n, m lg n)), O(n)-space, assumindo apenas chaves BTREE simples:

1. Busque todos os valores da coluna-chave da tabela de dados em qualquer ordem em uma matriz em sua linguagem de script favorita em O(n)
2. Execute um embaralhamento Fisher-Yates , parando após as mtrocas, e extraia o subarray [0:m-1]emϴ(m)
3. "Junte" o subarray com o conjunto de dados original (por exemplo SELECT ... WHERE id IN (<subarray>)) emO(m lg n)

Qualquer método que gere o subconjunto aleatório fora do SQL deve ter pelo menos essa complexidade. A junção não pode ser mais rápida do que O(m lg n)com BTREE (portanto, as O(m)declarações são fantasia para a maioria dos mecanismos) e o embaralhamento é limitado abaixo ne m lg nnão afeta o comportamento assintótico.

No pseudocódigo pitônico:

ids = sql.query('SELECT id FROM t')
for i in range(m):
  r = int(random() * (len(ids) - i))
  ids[i], ids[i + r] = ids[i + r], ids[i]

results = sql.query('SELECT * FROM t WHERE id IN (%s)' % ', '.join(ids[0:m-1])

Selecione 3.000 registros aleatórios no Netezza:

WITH IDS AS (
     SELECT ID
     FROM MYTABLE;
)

SELECT ID FROM IDS ORDER BY mt_random() LIMIT 3000

Experimentar

SELECT TOP 10000 * FROM table ORDER BY NEWID()

Isso daria os resultados desejados, sem ser muito complicado?

Talvez você pudesse fazer

SELECT * FROM table LIMIT 10000 OFFSET FLOOR(RAND() * 190000)