Amostras aleatórias simples de um database Sql

Como faço para obter uma amostra aleatória simples e eficiente em SQL? O database em questão está executando o MySQL; minha tabela é de pelo menos 200.000 linhas, e eu 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 () para cada linha (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, deverá usar a function T-SQL NEWID (), porque RAND () pode retornar o mesmo valor para todas as linhas .

EDIT: 5 ANOS DEPOIS

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

  • Amostre as linhas para 2-5x meu tamanho de amostra desejado, para barato ORDER BY RAND ()
  • Salve o resultado de RAND () em uma coluna indexada em cada inserção / atualização. (Se seu dataset não for muito pesado para atualizações, talvez seja necessário encontrar outra maneira de manter essa coluna atualizada.)

Para obter uma amostra de 1.000 itens de uma tabela, eu conto as linhas e amostro o 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 ter certeza de que não subamostrar e envolver manualmente o rand_high, mas a ideia básica é “cortar aleatoriamente o seu N em alguns milhares”).

Embora isso faça alguns sacrifícios, ele permite que eu experimente o database usando uma varredura de índice, até que seja 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- linhas de tabela /

Eu penso com absolutamente nenhuma suposição sobre a tabela 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 listada pode ser um pouco melhor, O (m * n) onde m é o número de linhas aleatórias desejadas, já que não precisaria classificar toda a grande matriz , só poderia procurar pelo menor m vezes. Mas para o tipo de números que você postou, m é maior que lg n de qualquer maneira.

Três sugestões que podemos experimentar:

  1. existe uma chave primária exclusiva, indexada na tabela

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

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

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 rápido O (n). Se nós pudermos ADICIONALMENTE assumir algo mais legal sobre a tabela, podemos fazer a tarefa em O (m log m). A suposição 3 seria uma propriedade adicional agradável e fácil de se trabalhar. Com um bom gerador de números randoms que garantia nenhuma duplicação ao gerar números m em uma linha, seria possível uma solução O (m).

Dadas as três suposições, a idéia básica é gerar m números randoms únicos entre 1 e n e, em seguida, selecionar as linhas com essas chaves da tabela. Eu não tenho mysql ou qualquer coisa na minha frente agora, então em um pouco de pseudocódigo isso seria algo como:

 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ê estivesse realmente preocupado com a eficiência, você poderia considerar fazer a geração aleatória de chaves em algum tipo de linguagem procedural e inserir os resultados no database, já que quase qualquer coisa além de SQL seria melhor no tipo de looping e geração de números randoms .

Eu acho que a solução mais rápida é

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

Aqui está porque eu acho que isso deveria fazer o trabalho.

  • Ele irá criar um número random para cada linha. O número está entre 0 e 1
  • Avalia se deve exibir essa linha se o número gerado estiver entre 0 e .3 (30%).

Isso pressupõe 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 prova .. aqui está o que eu diria a isso -

  • Isso é O (n), mas nenhuma sorting é necessária, então é mais rápido que o O (n lg n)
  • O mysql é muito capaz de gerar números randoms para cada linha. Tente isto -

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

Como o database em questão é mySQL, esta é a solução correta.

Mais rápido que ORDER BY RAND ()

Eu testei este método para ser muito mais rápido do que ORDER BY RAND() , portanto, ele é executado no tempo O (n) , e faz isso de forma impressionantemente rápida.

Em http://technet.microsoft.com/pt-br/library/ms189108%28v=sql.105%29.aspx :

Versão não MSSQL – eu não testei isso

 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) 

Isto irá selecionar ~ 1% dos registros. Portanto, se você precisa de um número exato de porcentagens ou registros a serem selecionados, estime sua porcentagem com alguma margem de segurança e, em seguida, escolha aleatoriamente os registros excedentes do conjunto resultante, usando o método ORDER BY RAND() mais caro.

Ainda mais rápido

Consegui melhorar ainda mais esse método porque tinha um intervalo de valores de coluna indexado bem conhecido.

Por exemplo, se você tiver uma coluna indexada com números inteiros uniformemente distribuídos [0..max], poderá usá-la para selecionar aleatoriamente N pequenos intervalos. Faça isso dinamicamente em seu programa para obter um conjunto diferente para cada execução de consulta. Essa seleção de subconjunto será O (N) , que pode ter várias ordens de magnitude menores que o dataset completo.

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

Aparentemente, em algumas versões do SQL há um comando TABLESAMPLE , mas não está em todas as implementações 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.

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

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

podemos chegar ao resultado de 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 indices = new ArrayList(rowsCount); for (int i = 0; i < rowsCount; i++) { indices.add(i); } Collections.shuffle(indices); String inClause = indices.toString().replace('[', '(').replace(']', ')'); 

Se os ids tiverem intervalos, os indices arraylist iniciais são o resultado de uma consulta sql nos ids.

Quero salientar que todas essas soluções parecem ser amostras sem substituição. Selecionar as linhas K superiores de uma sorting aleatória ou unir-se a uma tabela que contenha chaves exclusivas em ordem aleatória produzirá uma amostra aleatória gerada sem substituição.

Se você quiser que sua amostra seja independente, será necessário fazer uma amostra com a substituição. Veja a Pergunta 25451034 para um exemplo de como fazer isso usando um JOIN de maneira similar à solução do user12861. A solução é escrita para o T-SQL, mas o conceito funciona em qualquer database SQL.

Se você precisar exatamente de m linhas, de forma realista, você gerará seu subconjunto de IDs fora do SQL. A maioria dos methods requer, em algum momento, selecionar a input “n” e as tabelas SQL não são realmente matrizes. A suposição de que as chaves são consecutivas para unir inputs aleatórias 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 O(max(n, m lg n)) -time, O(n) -space assumindo apenas teclas 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 shuffle de Fisher-Yates , parando após m swaps, e extraia o subarray [0:m-1] em ϴ(m)
  3. “Join” o subarray com o dataset original (por exemplo, SELECT ... WHERE id IN () ) em O(m lg n)

Qualquer método que gere o subconjunto random fora do SQL deve ter pelo menos essa complexidade. A junit não pode ser mais rápida que O(m lg n) com BTREE (assim, as alegações O(m) são fantasiosas para a maioria dos mecanismos) e o embaralhamento é limitado abaixo de n e m lg n e não afeta o comportamento assintótico.

No pseudocódigo pitonico:

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

Talvez você possa fazer

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