Что если так попробовать. Генерируем некоторое количество значений и равномерно (или не очень) распределяем по диапазону от 1 до max(id). Делаем выборку и смотрим какие значения "попали". И уже от них генерируем следующие значения в каком-то диапазоне и т.д. Минус в том, что может получится так, что будут выбраны близко лежащие записи, ну а плюс в том, что возможно повезёт и пропустим дыры
я делал поле sort и прогонял его раз в сутки. или при вставке записи сразу делать. UPDATE table SET sort = rand() а потом по нему ключик делал и выборки. RAND() просто добавляет при запросе поле в выборку. при онлайн это накладно.
Ну хорошо. У меня частное решение для среднестатистической таблицы с равномерно выпадающими индексами -) Просто если у тебя вдруг таблица с id 1-100 и пару id = около 1000, то нужно уже писать в коде какой-то анализатор распределения.
440Hz я там выше предложил. добавлять чисто max(randid), удалять массово посложнее. а так у тебя еще порядок вывода не изменяется чаще раза в сутки