Se você não se importa em sacrificar a complexidade nas operações de inserção/atualização/exclusão para velocidade na seleção, você sempre pode adicionar um número de sequência e garantir que ele seja mantido em inserir/atualizar/excluir, então sempre que você fizer uma seleção, basta selecionar em um ou mais números aleatórios dentro deste intervalo. Se a coluna "sequência" estiver indexada, acho que é o mais rápido que você obterá.

Uma alternativa é "embaralhar". Adicione uma coluna de sequência, insira valores aleatórios nessa coluna e, sempre que selecionar registros, ordene pela coluna de sequência e atualize as sequências de registro selecionadas para novos valores aleatórios. A atualização deve afetar apenas os registros que você recuperou, portanto, não deve ser muito caro... mas pode valer a pena executar alguns testes em seu conjunto de dados.

Isso pode ser uma coisa bastante ruim de se dizer, mas vou dizer de qualquer maneira ... há necessidade de exibir dados 'aleatórios'? se você estiver tentando exibir registros aleatórios, pode estar fazendo algo errado.

Pense na Amazon... eles exibem produtos aleatórios ou exibem produtos populares e 'coisas que outras pessoas compraram quando viram isso'. O SO fornece uma lista de perguntas aleatórias à direita aqui ou uma lista de perguntas relacionadas? Apenas alguns alimentos para o pensamento.