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

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

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


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


Как оказалось, MySQL не умеет эффективно выбирать случайные строки с помощью ORDER BY rand() LIMIT N, где необходимо отфильтровать строки по условию (хотя тот же 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=5 AND u1.id=(rs.id+random_from_php)
ORDER BY
rs.random_seed
LIMIT 10


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

Реальный пример из моей работы — выбор случайных категорий товаров из разных комбинаций (всего 4000000 записей):

«Обычный»: запрос «Ускоренный» запрос:
SELECT
oc1.*
FROM
object_category oc1
WHERE oc1.region_id=6
ORDER BY RAND()
LIMIT 10
SELECT
oc1.*
FROM
object_category oc1, random_seed rs
WHERE
oc1.id=(rs.id+564756) AND oc1.region_id=6
ORDER BY
rs.random_seed
LIMIT 10
Время выполнения:
1.726с 0.007с
1.851с 0.010с
1.803с 0.006с
1.784с 0.008с


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

Минусы:
— Необходимость ввода дополнительной таблицы
— Необходимость изменения привычных запросов
Поделиться публикацией

Похожие публикации

Комментарии 18
    0
    Насколько знаю медленный результат был из-за того что использовалась MyISAM, если перейти на InnoDB то все будет ок без танцев с бубном.

    explainextended.com/2009/03/01/selecting-random-rows/
      0
      Таблица уже имеет тип InnoDB.
      0
      А можно реальный пример, когда действительно требуется выборка случайных строк?
      Мне, кроме сбора статистики по большой таблице в ограниченное время, ничего в голову не приходит.
        +1
        во всех примерах которые попадались — что-то типа «показать пользователю в сайдбаре три рандомных товара»…
          0
          не проще ли срандомить айди товара из заданных пределов и выбрать 3 товара?
            0
            Не известно заранее, в каких пределах будут id товара, у которых category_id=5.
            В общем случае они будут идти не по порядку (например 1, 2, 3, 555, 123444), а итеративно выбирать значения до тех пор, пока не получим нужные нам значения — медленно
              0
              Ну вообще-то идея имеет право на жизнь… «where id>=random_from_php limit 1», повторить три раза с разными значениями random_from_php
                0
                такой подход не будет работать, если id распределены следующим образом:
                1, 2, 3, 4, 555, 556, 557, три случайных random_from_php попадут между двумя неразрывными последовательностями и получим в итоге 555, 555, 555, конечно, можно вводить дополнительные условия (не выбирать уже выбранные), как-то анализировать распределение id, но это уже намного сложнее и медленнее
                  0
                  Я и не говорил что это будет работать в данном конкретном случае. Кстати, для случаев типа вашего можно подумать над кешированием, например, тысячи (число от фонаря) готовых отрендереных блоков и вставки рандомного из них. Да, это не чистый рандом, но работать будет еще быстрее (не надо каждый раз рендерить сам блок).
              0
              Дык у автора спросите. Я просто человеку на вопрос «зачем» ответил.
              Вообще я таким не занимаюсь — у нас проблеммные таблички от 100млн, и там не до order by rand() ;)
            +1
            Реальный пример из моей работы — выбор случайных категорий товаров из разных комбинаций (всего 4000000 записей):
            «Обычный»: запрос
            SELECT
            osc1.*
            FROM
            object_category osc1
            WHERE region_id=6
            ORDER BY RAND()
            LIMIT 10
            Время выполнения: 1.726с; 1.851с; 1.803с; 1.784с

            «Ускоренный» запрос:
            SELECT
            osc1.*
            FROM
            object_category osc1, random_seed rs
            WHERE
            osc1.id=(rs.id+564756) AND region_id=6
            ORDER BY
            rs.random_seed
            LIMIT 10
            Время выполнения: 0.007с; 0.010с; 0.006с; 0.008с

            К сожалению, html-оформление не отображается…
            –1
            Всему свое место и время. Я бы рекомендовал, при всей своей любви к RDBMS, глянуть на redis.io/commands/srandmember
              0
              Поясните пожалуйста
              >выбрать случайные id из промежутка в данном случае нельзя: из-за условия WHERE, id идут уже не по порядку и разряженно.

              и
              > WHERE oc1.id=(rs.id+564756)

              как бы говорит о том, что вы можете попасть в id которого не существует и выборка выдаст null
              или я чего-то не понял?

                0
                Спасибо за замечание.

                Действительно, в таблице random_seed должно быть столько же значений, сколько в таблице, из которой нужно брать случайные строки + N записей, где N это максимально возможное значение random_from_php
                  0
                  Еще, скорость зависит не столько от общего кол-ва записей в таблице, а от количества записей после применения условий where (возможно, только если индекс по where-полям есть). У меня на myisam в 11kk записей так.
                0
                Решение не ново. Кстати, подобным образом в NoSQL еще записи случайные выбирают.
                  0
                  К сожалению, когда писал статью не видел подобных решений в интернете. Можете скинуть ссылку?
                  Даже на stackoverflow предлагают селектить rand()*MAX(id)
                    0
                    Вот тут один товарищ расписывал различные варианты jan.kneschke.de/projects/mysql/order-by-rand/

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое