рандомные сортировки вообще можно совершенно иначе сделать, оптимизировать под индексы и там вообще всё летать будет на таблицах любого размера…
суть в том, что если у тебя есть где-то промежуточные подзапросы которые выцепляют и начинают перелопачивать тысячи строк – во-первых ты это увидишь в EXPLAIN, во-вторых, лучше как-то выкрутиться и соптимизировать их сразу на уровне запроса. потому что даже срезав сейчас затраты, выкинув часть полей из запроса, ты потом всё равно столкнёшься с тем что таблица вырастет и опять всё начнёт тормозить…