БлогNot. ORDER BY RAND()

ORDER BY RAND()

Тривиальная, в общем-то, задача по выбору K случайных записей из N имеющихся в таблице, оказывается на MySQL весьма непростой - если пытаться сделать всё правильно. Чаще всего приходится встречать код вида

SELECT * FROM Таблица WHERE Условие ORDER BY RAND() LIMIT 0,Число_записей

- то есть, "выполнять сортировку по случайному числу".

Между тем, в документации пишут, что функцию RAND() не стоит применять вместе с ORDER BY, так как она выполняется многократно и влёчёт нагрузку на систему.

Фактически в показанном выше коде делается следующее: MySQL генерирует дополнительное виртуальное поле в таблице и генерирует случайные числа для каждой записи этой таблицы. Затем вся таблица сортируется по этому полю. И только потом выбирается указанное в LIMIT количество записей. Как и обычно происходит с БД, неоптимизированный код будет приемелемо работать до некоторого размера базы и только потом "неожиданно" всё начнёт подвисать с экспоненциальным ростом времени подвисания от размера таблицы.

Если в Вашей системе всегда будет мало пользователей (100, к примеру, это ещё мало), а в таблице всегда будет мало записей (ну, до 10-20 тысяч это точно мало), всё равно ничего лучше ORDER BY RAND() не придумаете.

Для больших таблиц и нагруженных систем лучше поискать другое решение.

Нетрудно было бы решить задчу для обычного "плоского" файла (ссылка), но многократные запросы в цикле, в отличие от последовательного чтения строк из файла, разумеется, не решение.

У меня на форуме всего 1,5млн. постингов. Уже после ~700 тыс. на топиках с десятками страниц записи вида SELECT * FROM posts WHERE topic_id =… ORDER BY… LIMIT 10000, 15; стали капитально вешать сервер. Не смотря на все оптимизации индексов и настроек :)

Распространенный подход - получить максимальный id записи по полю счётчика, затем использовать его как верхнюю границу для встроенного в PHP генератора случайных чисел, например, так:

$res=mysql_query('select min(id), max(id) from '.Таблица)
    or die(mysql_error());
  $min_id=mysql_result($res, 0, 0);
  $max_id=mysql_result($res, 0, 1);
  $rand_id=rand($min_id, $max_id);
  $res=mysql_query('select * from '.TBL_PHOTOS." where id>=$rand_id limit 1")
    or die(mysql_error());
  if ($row=mysql_fetch_assoc($res))
  {
    extract($row);
    ........
    ........
  }

Увы, нет никакой гарантии в том, что поле первичного ключа будет представлять собой правильную последовательность 1,2,3, ..., N, ... "без дыр".

При больших "дырах" выбираться будет вообще очень неравномерно.

Здесь, кстати, выбирается одна запись, а выбор с помощью limit нескольких вообще весьма трудоёмок (mysql делает scan до нужной записи). Вообще, указание вида LIMIT 999, 1 выберет не 1 строку. Сначала будет извлечена 1000 строк, затем из этой тысячи выбрана одна. А если в таблице будет не 1000 строк, а намного больше — опять начнутся тормоза. Кстати, MySQL очень болезненно относится к выборке последних значений в любой большой таблице. Отсортированной тоже.

Можно получить количество записей в таблице (для подсчёта количества элементов таблица перебирается только при отсутствии подходящего индекса), затем сгенерировать число в диапазоне [1,КоличествоЗаписей], выбрать случайную запись по этому числу. Увы, если это делать с помощью Limit, вступают в действие все соображения, высказанные выше.

Ещё разновидность подхода:

SELECT * FROM table1 WHERE tid> (floor(rand())*(SELECT count(*) FROM table1) ) LIMIT 1
Все варианты с выборкой по первичному ключу не дают равномерного распределения вероятности выборки, если ключ разреженный. На таблицах с большим количеством удалений по отношению к общему числу записей такое лучше не делать.

Можно получить все нужные id записей в массив и затем выбирать элемент из этого массива:

$r = mysql_query("SELECT `id` FROM `table` WHERE Условие ");
while($id = mysql_result($r,0)) $available_ids[] = $id;
$rand = rand( 0 , (count($available_ids)-1) );
$id = $available_ids[$rand];

Что ж, на больших таблицах здесь будет тормозить не MySQL, а сам PHP - создавая в памяти огромные массивы... думаю, на 10-15 тысячах строк уже будет заметно.

В варианте типа

select distinct x from table order by rand() limit КоличествоЗаписей

запрос будет создавать временную таблицу. Со всеми последствиями в случае, если таблица большая.

$sql='SELECT COUNT(*) FROM Table';
$result=mysql_query($sql);
$row_count=mysql_num_rows($result);
for ($i=0; $i<$numbers; $i++) {
 $rand_row = round(rand() * $row_count);
 $sql='SELECT field FROM Table LIMIT '.$rand_row.',1';
}

Запрос в цикле - плохо всегда.

Другой момент - если рандомайзер выбрал запись N, а параллельный процесс в это время удалил её. Выборка не находит ничего. Между тем, речь о больших таблицах.

Варианты из форумов:

1) взять кол-во записей удовлетворяющих запросу ($total)
2) с помощью PHP сгенерировать случайное "окно" в промежутке 0<$randnum<($total-1000)
3) выполнить запрос с LIMIT $randnum, 1000
4) shuffle($res)
5) array_slice ($res, 0, сколько_надо_в_результате);

Метод будет достаточно быстрым на больших таблицах, но, увы, "нечестным" - все результаты находятся в пределах "окна" в 1000 записей.

Предполагается, что выборка вида LIMIT X, 1 оптимизируется в MySQL хорошо (идет нересурсоемкий спуск по индексу, если в таблице есть хоть один индекс/ключ) - чего отнюдь нельзя сказать о LIMIT X, 1000

Приемлемым и надежным решением может быть использование хранимой процедуры, которая использует курсор (нужен минимум MySQL 5). Например так:

1. получаем количество записей, допустим N
2. получаем M (в нашем случае M = 10) случайных значений от 0 до N — 1 и помещаем их в массив в порядке возрастания
3. открываем курсор вида DECLARE cur CURSOR FOR SELECT id,другие_поля FROM test
4. так как полученные нами случаные значения расположены по порядку, то вычитываем курсором по очереди все записи, и когда встречаются номера записей, соответствующие нашим выбранным случайным значениям, сохраняем эти записи.
5. когда выбрали запись, номер которой соответствует последнему случайному значению, закрываем курсор.
6. все, мы за один проход выбрали все M случайных записей, при этом не использовали никаких сортировок

Таким образом, если мы имеем миллионы записей, и номера случайных записей будут небольшими, то такая выборка будет очень быстрой. В большинстве случаев это решение считается оптимальным.

Но вообще, если в высокозагруженной системе нужно делать частые выборки случайных записей из некоторой таблицы, даже если это миллионы записей, то намного правильнее хранить ID этих записей (а если позволяют ресурсы, то и таблицу целиком, но это уже опционально) в памяти в кеше, и делать поиск случайных записей именно в памяти, затем при необходимости извлекая записи из таблицы сразу по ID. Даже если там 10 млн записей, это всего лишь 40 Mb в кеше, не так уж и много для выделенного для такой базы сервера.

 "Классический" пост по теме (англ.)

Предлагается и сравнивается 2 варианта,

RAND() * MAX(ID)
RAND() * MAX(ID) + ORDER BY ID

реализация - через довольно трудоемкие хранимые процедуры.

Ну а мне всё-таки хочется сделать без курсоров и хранимых процедур. Однако, на больших базах лёгких решений не бывает.

 Обсуждение на Хабре

 Более раннее обсуждение, довольно большое

Попытка резюме

SELECT * FROM table ORDER BY RAND() LIMIT 1;

Если в таблице больше, чем 4-5 тысяч строк, то

ORDER BY RAND()
будет работать очень медленно. Гораздо более эффективно будет выполнить два запроса:

Если в таблице auto_increment'ный первичный ключ и нет пропусков:

$rnd = rand(1, query('SELECT MAX(id) FROM table'));
$row = query('SELECT * FROM table WHERE id = '.$rnd);

либо:

$cnt = query('SELECT COUNT(*) FROM table');
$row = query('SELECT * FROM table LIMIT '.$cnt.', 1');

что, однако, также может выполняться долго при очень большом количестве строк в таблице.


Для таблиц с "дырками" в ключе придумать нормальное решение и вовсе проблематично.

11.01.2010, 17:33 [15244 просмотра]


теги: числа random алгоритм php mysql

К этой статье пока нет комментариев, Ваш будет первым