У документов есть целочисленные последовательные id? У нас, в Mysql на PHP это решается просто: получаем max_id и min_id, генерируем 20 рандомных чисел в этом диапазоне и выбираем SELECT * FROM table WHERE id IN (20 random numbers) LIMIT 1. Работает замечательно, через индексы, без всяких извращений.