Логика проста. ищем минимальное значение. Потом ищем количество элементов между максимумом и минимумом, не зависимо от флага. Далее с помощью этого диапазона получаем случайное число, которое >= минимума и <= максимума.
Потом все это сравниваем в WHERE.
Хм… второе сравнение на id >= mn уже не нужен… хватит только t.id >= rnd AND t.flag = 0.
Все будет искать довольно шустро. По крайней мере по началу так точно.
Даже самый простой запрос:
Отрабатывает за 4 секунды… не говоря уже про остальные. Наверное, все же лучше будет с самого начала генерировать таблицу…