Быстрый выбор случайных значений из больших таблиц MySQL по условию

Задача выбора случайных строчек из таблицы довольно часто возникает перед разработчиками.
В случае, если используется СУБД MySQL, обычно она решается примерно следующим способом:

SELECT *
FROM users
WHERE role_id=5
ORDER BY rand()
LIMIT 10

Такой код работает крайне медленно для больших таблиц и когда задается условие WHERE, без WHERE или таблица небольшая, есть эффективные решения, например habrahabr.ru/post/54176/ ^[1] или habrahabr.ru/post/55864/ ^[2].
Но решений для случая большой таблицы и необходимости фильтровать по условию, получая при каждом запросе новые значения в сети я не нашел, поэтому описание моего способа под катом.

Как оказалось, MySQL не умеет эффективно выбирать случайные строки с помощью ORDER BY rand() LIMIT N WHERE условие (хотя тот же MSSQL отлично справляется с выбором случайных строк из таблицы с большим количеством записей).

Итак, решая задачу «в лоб», запрос (в таблице 5млн. записей):

SELECT *
FROM users
WHERE role_id=5
ORDER BY rand()
LIMIT 10


Запрос занял 41.3544 сек., что недопустимо долго. Найти максимальный и минимальный id, а затем выбрать случайные id из промежутка в данном случае нельзя: из-за условия WHERE id идут уже не по порядку и разряженно.

Мое решение следующее: добавляется таблица random_seed, содержащая поля id и random_seed, заполняемая случайными числами, на данную колонку добавляется индекс, также индекс добавляется на колонку, по которой будет происходить выборка.
Теперь, чтобы выбрать случайные строки по условию, запрос нужно поменять следующим образом (в таблице 5млн. записей):

SELECT
u1.*
FROM
users u1,
random_seed rs
WHERE
u1.role_id=6 AND u1.id=(rs.id+random_from_php)
ORDER BY
rs.random_seed
LIMIT 10

Запрос занял 0.0460 сек., что является уже более чем приемлемым результатом. Переменная random_from_php генерируется вызывающим запрос кодом, что обеспечивает случайный набор значений при каждом запросе, это число обеспечит выборку по новым случайным числам.

Преимущества описанного выше метода:
+ Самый быстрый из возможных способов выбора случайных строк из таблицы по условию
+ Не нужно повторно генерировать случайные числа для каждой из строк в таблице
+ Запрос всех нужных значений происходит не итерационно, в один запрос

Минусы:
— Необходимость ввода дополнительной таблицы
— Необходимость изменения привычных запросов
— В виду специфики алгоритма, последние значения в таблице, из которой делается SELECT будут попадаться реже (или их необходимо заполнить копиями значений), поэтому алгоритм подходит тогда, когда равномерность вероятности выпадения последних элементов не важна (либо придется принять дополнительные меры)

Автор: uterr

Источник ^[3]