Federico Razzoli

Última atualização em 8 de dezembro de 2019

Retornar linhas aleatórias em uma ordem aleatória de uma base de dados relacional é um problema muito difícil. Neste artigo veremos um anti-padrão, discutiremos porque este problema é tão difícil, e examinaremos algumas soluções imperfeitas.

UPDATE: Alguns SGBD suportam TABLESAMPLE. Eu não mencionei isso porque até hoje eu só conhecia a implementação do SQL Server, e não o considero bom para extrair linhas aleatórias (vou explicar o porquê). Mas depois de uma pergunta no Facebook feita por Daniël van Eeden eu fiz algumas pesquisas, e descobri que a implementação do PostgreSQL poderia ser muito mais adequada. Vou ler mais sobre isso e tentar, e depois provavelmente vou escrever um segundo artigo sobre isso. De qualquer forma, o MySQL e a MariaDB não suportam TABLESAMPLE.

O caminho errado: ORDER BY RAND()

Muitos desenvolvedores pensam que podem fazer desta forma:

SELECT some_columns FROM some_table ORDER BY RAND() LIMIT 10;

Esta é a única consulta que faz exatamente o que se esperava. Se a função RAND() for aleatória de forma confiável, ela retorna um conjunto aleatório de linhas, onde cada linha tem as mesmas chances de ser retornada.

O problema é como ela funciona sob o capô. Para ordenar valores aleatórios, é necessário criá-los primeiro. Para criar um valor aleatório para cada linha de uma tabela, um SGBD tem de ler cada linha. Assim o SGBD fará uma operação em dois passos:

1. Copiar as linhas mais um valor aleatório para uma tabela temporária, esperançosamente em memória;
2. Encomendar as linhas na tabela temporária.

Note que este detalhe: esperançosamente em memória. Dependendo do SGBD, pode haver razões pelas quais a tabela precisa ser criada em disco. Tipicamente, isto acontece se a tabela for muito grande. Versões antigas do MySQL também criam tabelas temporárias no disco se elas contiverem TEXT ou BLOB colunas.

Needless para dizer, se a tabela for grande esta é uma operação lenta que consome muitos recursos.

Por que os SGBD relacionais não fornecem uma forma integrada de retornar linhas aleatórias?

Bases de dados relacionais são construídas em torno de um ramo da matemática chamado álgebra relacional. Ela é baseada na lógica, porque lida com previsões verdadeiro/falso; e é semelhante à teoria de conjuntos, mesmo que uma relação seja algo mais complexo do que um conjunto, e mesmo vê-la como uma tabela não é matematicamente correta. Este artigo é um bom exemplo do que quero dizer, mas existem argumentos mais complexos.

Embora o SQL não seja uma implementação precisa do modelo relacional, sua álgebra é usada como referência. Como todos os ramos da matemática, ele tem um conjunto bem definido de operações. Obter tuplos aleatórios de uma relação não é definitivamente uma delas.

Esta resposta soa um pouco teórica demais, certo? ORDER BY e tabelas sem chave primária também violam as regras da álgebra relacional, mas SQL suporta-as.

No entanto, para bases de dados, a velocidade é vital. Os SGBDs relacionais são projetados para realizar operações relacionais muito rapidamente. Obviamente, uma estrutura de dados concebida para optimizar determinadas operações não é optimizada para outras operações. Portanto, os SGBD relacionais não são otimizados para pesquisas aleatórias.

Deve ser óbvio que o loop sobre as linhas para escolher algumas delas de forma aleatória seria lento. Teoricamente, ler uma linha aleatória usando um índice seria tão rápido quanto encontrar uma linha pelo valor da chave primária. Mas então, linhas diferentes teriam diferentes chances de serem escolhidas.

A imagem acima é de um repositório GitHub de Jeremy Cole, innodb_diagrams. Mais cedo ou mais tarde eu deveria escrever sobre seus projetos para analisar estruturas de dados InnoDB.

O importante aqui é que um índice é uma árvore cujos nós são páginas de memória. Os nós da folha contêm dados reais; os níveis superiores contêm apenas a informação necessária para escolher o caminho mais curto para o nó da folha desejado. Detalhes não são importantes neste contexto.

O SGBD poderia teoricamente escolher uma página aleatória executando uma série de decisões aleatórias: eu irei para a esquerda ou para a direita? Mas então, as páginas da folha contêm um número variável de linhas. Elas podem até estar vazias. Assim, linhas diferentes teriam diferentes chances de serem selecionadas.

O resultado está claramente fora dos casos de uso pretendido do SGBD; e pode ser lento ou errado, dependendo se um índice é usado ou não. Os SGBD escolheram corretamente não implementar este recurso.

algumas soluções

Não há soluções perfeitas. Há soluções que podem ser aceitáveis, mas que têm desvantagens. Devemos escolher uma de caso para caso.

Selecionar aleatoriamente de um intervalo

Esta solução é aplicável a tabelas que têm uma chave primária auto-incremental. É a mais fácil de implementar, mas uma chave primária “fragmentada” causa problemas.

Consiste em verificar o id mínimo, o id máximo, e gerar um número aleatório nesse intervalo:

Não que consultas com MIN() e MAX() em qualquer índice, sem outras cláusulas, sejam muito rápidas.

O resultado é uma linha verdadeiramente aleatória. Para escolher mais de uma linha, podemos repetir esta consulta várias vezes. Isto leva-nos a duas desvantagens:

• Se esta operação for realizada frequentemente, podemos executar esta consulta muitas vezes.
• Não há garantias de que a mesma linha não seja seleccionada várias vezes. Se isto acontecer, a aplicação pode tentar novamente a consulta. Se a tabela for grande, este evento é raro e podemos ignorá-lo – a menos que a RAND()função não seja confiável. Mas para tabelas pequenas, isto pode ser um problema.

Tal como, uma chave primária pode ter buracos – em outras palavras, alguns números podem estar faltando. Isto é devido a exclusões e transações falhadas. Números menores que o máximo não são reutilizados. Para contornar este problema, podemos usar duas técnicas.

Using >=

Se usarmos o operador >= na cláusula WHERE, a consulta retornará sempre uma linha. Se o número gerado não estiver presente, será utilizado o próximo número. Mas isto significa que os valores imediatamente após um buraco terão mais chances de serem selecionados. Quanto maior o buraco, maiores as chances.

Você pode pensar que não deve se importar com isso, e provavelmente está certo. Mas antes da sua decisão ser final, considere a possibilidade de um grande buraco.

Trying hard

Se a consulta não retornar nenhuma linha, podemos apenas tentar novamente. Para mesas grandes com apenas alguns pequenos furos, isto é perfeitamente bom. Mas para grandes buracos com muitos buracos, ou grandes buracos, esta técnica pode consumir demasiados recursos.

Por favor, não seja muito paranóico com isto. Faça apenas algumas contas. Qual é a proporção de valores em falta na sua tabela? Isto diz-lhe quantas vezes a consulta será repetida, em média.

Selecting multiple rows

Para seleccionar várias linhas com esta técnica, podemos:

• Repetir a consulta várias vezes;
• Or, para um melhor desempenho, use o operador >= e use um operador LIMIT maior que um. Isto no entanto torna os resultados muito menos aleatórios.

Movendo a escolha aleatória para a aplicação

Na sua forma mais simples, esta técnica consiste em escolher aleatoriamente um bloco de id’s contíguos. A aplicação irá escolher aleatoriamente quais irá utilizar, e depois seleccionar as linhas correspondentes.

Se quiser escolher de entre blocos de 1000 valores:

Quanto maior for o bloco, quanto mais recursos consumir, mais aleatório será o resultado. A aplicação tem a responsabilidade de escolher aleatoriamente id’s únicos existentes a partir dos blocos, portanto nunca deve haver a necessidade de tentar novamente uma consulta.

A variante MOD

Um problema com esta técnica é que as linhas são retornadas a partir do mesmo bloco de id’s contíguos. Isto pode ser perfeitamente aceitável, especialmente se o bloco for grande. Mas se não for, poderíamos adicionar alguma complexidade para seleccionar um bloco de linhas não contíguas.

A ideia desta variante é para:

• Definir macroblocos de linhas maioritariamente não contíguas;
• Escolher aleatoriamente um macrobloco;
• Retornar um bloco a partir dele.

Para fazer isso, podemos calcular o módulo de id, e usá-lo para selecionar resultados aleatórios. Por exemplo, podemos definir uma coluna virtual indexada com uma expressão como (id MOD 4). Cada linha terá um valor entre 0 e 3. Mesmo que haja buracos, as linhas destes macroblocos serão na sua maioria não contíguas e devem ter aproximadamente o mesmo número.

A aplicação deve gerar um número aleatório entre 0 e 3. Então, para selecionar blocos destes macroblocos:

SET @block_size := 1000;SELECT id FROM some_table WHERE id_mod = FLOOR(RAND() * 3) ORDER BY id LIMIT @block_size;

Uma maneira similar de implementar esta idéia é usar partições, onde a função de particionamento é o módulo do id. Eu só sugeriria isto se a tabela se beneficiasse do particionamento por outros motivos.

Selecionar uma técnica

As técnicas de blocos rodam mais consultas em comparação com a primeira com o operador >=, e o resultado poderia ser melhor ou não. Comparado com a variante de reentrada, isto poderia executar mais ou menos consultas, e o resultado seria pior.

Geralmente, as técnicas de blocos são melhores se tivermos buracos na chave primária.

Caching random series

Os métodos anteriores são uma tradeoff: performance versus melhor aleatoriedade, onde a solução mais rápida também é mais complexa de implementar. Desde que não utilizemos o ORDER BY RAND() antipattern, a selecção de linhas aleatórias não deve causar problemas de performance. Mas e se isso acontecer?

Podemos armazenar em cache alguns id’s aleatoriamente ordenados obtidos com qualquer uma das soluções anteriores. Poderíamos usar uma consulta como esta (sintaxe MySQL):

Poderíamos usar as séries em ordem ascendente ou descendente, de forma aleatória. Ou a aplicação poderia embaralhá-los.

Problems:

• Quando um item é adicionado, devemos escolher aleatoriamente se ele deve ser inserido em uma série, substituindo um item aleatório.
• Quando um item é excluído, devemos excluí-lo de todas as séries. Ele deve ser substituído por outro item aleatório.
• Pode ser que desejemos periodicamente apagar as séries mais antigas e substituí-las por novas, para melhorar a aleatoriedade na experiência do usuário.

Conclusões

Como de costume, por favor comente e me avise se você detectar um erro neste artigo, se você discordar de alguma coisa, me conte sua experiência pessoal, ou se você tiver mais idéias para adicionar.