Быстрый выбор случайного идентификатора из таблицы mysql с миллионами непоследовательных записей

Я осмотрелся и не нашел простого способа сделать это. Похоже, что проще просто взять подмножество записей и выполнить всю рандомизацию в коде (perl). Методы, которые я видел в сети, похоже, больше подходят для сотен тысяч, но уж точно не для миллионов.

Таблица, с которой я работаю, имеет 6 миллионов записей (и продолжает расти), идентификаторы автоматически увеличиваются, но не всегда сохраняются в таблице (без пропусков).

Я попытался выполнить рекомендованный LIMIT 1 запрос, но выполнение запроса занимает вечность - есть ли быстрый способ сделать это, учитывая, что в записи есть пробелы? Я не могу просто взять максимум и рандомизировать по диапазону.

Обновление:

Одна из моих идей, возможно, заключалась в том, чтобы получить максимальное значение, рандомизировать ограничение на основе максимального значения, а затем получить диапазон из 10 записей от random_limit_1 до random_limit_2, а затем взять первую запись, найденную в этом диапазоне.

Или, если я знаю максимальное значение, могу ли я просто выбрать, скажем, 5-ю запись таблицы, не зная, какой это идентификатор. Затем просто захватите идентификатор этой записи.

Обновление:

Этот запрос несколько быстрее.Все еще недостаточно быстро = /

SELECT t.id FROM table t JOIN (SELECT(FLOOR(max(id) * rand())) as maxid FROM table) as tt on t.id >= tt.maxid LIMIT 1