Kerman

Я вот таких людей как Вы, простите, не понимаю. Оно работает? Работает. Задачу выполняет? Выполняет. Так зачем Вы пытаетесь применить перфекционизм к простейшей задаче?

То что запрос страшненький получился - это нормально. БД не предназначена для таких вещей. Это к Вам должен быть вопрос: а почему Вы у базы спрашиваете, который час? У Вас что, крона (планировщика задач) нет? Или вы не знаете про event в MySQL?

Если нужен именно честный выбор действительно случайных и равномерно распределённых 10000 строк из пятимиллионной таблицы, то лучше SQL с этой задачей ничто не справится. Разве что самописная база, заточенная конкретно под этот случай. Нужно просто расставить индексы на нужные поля, чтобы облегчить поиск.
Мой совет: добавьте памяти на сервер, проиндексируйте поля. Всё будет хорошо, используйте стандарный RAND(), оптимизировав его до приемлемого значения.

Для редких случаев ещё помогает выборка массива ID по условию и дальнейший выбор нужного количества случайных ID из массива.