DeathCore

SELECT t.id, t.flag FROM test t,
    (SELECT id mn FROM test WHERE flag = 0 LIMIT 1) tmp1,
    (SELECT ROUND(((SELECT id FROM test WHERE flag = 0 ORDER by id DESC LIMIT 1)-(SELECT id FROM test WHERE flag = 0 LIMIT 1))*rand()+(SELECT id FROM test WHERE flag = 0 LIMIT 1)) rnd FROM test LIMIT 1) tmp2
WHERE t.id >= rnd AND t.id >= mn AND t.flag = 0
LIMIT 1

Учитывая вот этот вот комментарий:

Разве при таком подходе каждый купленный билет не повышает вероятность покупки следующего порядкового билета? К примеру, если куплены все билеты от 0 до 500000, то любое случайное число от 0 до 500000 приведёт к покупке 500001 билета. Таким образом, вероятность его покупки будет примерно 50%.

Переделал запрос. Теперь в такой ситуации будет генерироваться случайное число от 500 000 до 1 000 000

SELECT t.id, t.flag FROM test t,
    (SELECT id mn FROM test WHERE flag = 0 LIMIT 1) tmp1,
    (SELECT ROUND((SELECT MAX(id) FROM test)*rand()) rnd FROM test LIMIT 1) tmp2
WHERE t.id >= rnd AND t.id > mn AND t.flag = 0
LIMIT 1

Первичный ключ id и комбинированный индекс на (id, flag)

на таблице в 36 миллионов записей проходит за 0.002 секунды.