Задача на самом деле нетривиальная, но очень распространенная. Одним из самых "качественных" вариантов решения для стандартной слаборазряжённой базы является выборка максимального и минимального значения первичного автоинкрементного ключа, а затем формирование набора из N случайных чисел между ними средствами языка (пхп, ноды, го, не суть), где N тем больше, чем больше разряженность базы. Далее делается выборка с in, и уже по результатам выборки берется случайная запись из группы полученных. Насколько я помню это самый эффективный и быстрый способ.