В связи с часто поступающими вопросами о том, как можно быстро и хорошо показать несколько случайных неповторяющихся записей из БД, рассмотрим классическую задачу: показ нескольких неповторяющихся банеров из множества имеющихся.
Варианты решения:
- Сгенерировать несколько случайных чисел в диапазоне от 1 до количества записей в таблице. НЕ ГОДИТСЯ. Высок риск попасть на "дырку" в последовательности значений первичных ключей, получившуюся из-за того, что какие-то банеры были удалены. Да, можно эти "дырки" устранять, но менять значение суррогатного первичного ключа — извращение. Однако, мы попробуем один хитрый способ (см. пункт E).
- Выбрать несколько записей, отсортировав всю выборку в случайном порядке. Этот способ ОЧЕНЬ НЕ РЕКОМЕНДЕТСЯ специалистами по БД, но часто применяется на практике. РАССМОТРИМ. (См. пункт A).
- Перенести логику определения случайного банера на уровень бизнес-логики приложения. Сначала получаем полный список имеющихся значений поля b_uid, а потом что-то с ним делаем. РАССМОТРИМ. (См. пункты B, C, D).
- Модификация способа 1, основанная на выборке банеров по случайно сгенерированному множеству значений в диапазоне от минимального до максимального значения поля b_uid. Это множество должно превосходить (иногда, значительно) количество показываемых банеров, т.к. может содержать значения поля b_uid, отсутствующие в БД в силу того, что такие банеры были удалены. РАССМОТРИМ. (См. пункт E).
- Модификация способа 4, основанная на выборе банеров не по значениям buid, а по диапазонам значений. РАССМОТРИМ. (См. пункт F).
Допустим, банеры хранятся в такой таблице в MySQL:
`b_uid` int(11) NOT NULL AUTO_INCREMENT COMMENT ‘Идентификатор’,
`b_url` text NOT NULL COMMENT ‘URL рекламируемого сайта’,
`b_text` text NOT NULL COMMENT ‘Текстовая часть банера’,
`b_pic` varchar(200) NOT NULL DEFAULT » COMMENT ‘Имя файла для графической части банера’,
`b_show` bit(1) NOT NULL DEFAULT ‘1’ COMMENT ‘1 — отображать, 0 — нет’,
`b_to_show` int(11) NOT NULL COMMENT ‘Сколько показов оплачено’,
`b_to_click` int(11) NOT NULL COMMENT ‘Сколько кликов оплачено’,
`b_real_show` int(11) NOT NULL COMMENT ‘Сколько раз банер показан’,
`b_real_click` int(11) NOT NULL COMMENT ‘Сколько раз по банеру кликнули’,
PRIMARY KEY (`b_uid`),
KEY `b_show` (`b_show`,`b_to_show`,`b_to_click`,`b_real_show`,`b_real_click`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
Итак, алгоритмы и оценка их производительности. Будем выбирать 20 банеров.
A) Алгоритм 1.
- Начало.
- Выбрать из БД нужное количество случайных записей, отсортированных в случайном порядке.
- Показать записи.
- Конец.
B) Алгоритм 2, модификация 1.
- Начало.
- Выбрать из БД ВСЕ значения поля b_uid.
- Переместить все значения b_uid в массив "ИСХОДНЫЙ".
- Сгенерировать случайное число в диапазоне [0, количество элементов в массиве "ИСХОДНЫЙ" — 1].
- Если в массиве "ИСХОДНЫЙ" есть элемент с таким номером, поместить его в массив "КОНЕЧНЫЙ", иначе — вернуться на шаг 4.
- Повторять шаги 4-5 до накопления в массиве "КОНЕЧНЫЙ" необходимого количества значений b_uid.
- Выбрать из БД записи со значениями b_uid, содержащимися в массиве "КОНЕЧНЫЙ".
- Показать записи.
- Конец.
C) Алгоритм 2, модификация 2.
- Начало.
- Выбрать из БД ВСЕ значения поля b_uid.
- Переместить все значения b_uid в массив "ИСХОДНЫЙ".
- Сгенерировать случайное число в диапазоне [0, количество элементов в массиве "ИСХОДНЫЙ" — 1].
- Получить значение b_uid из элемента массива "ИСХОДНЫЙ" с номером, полученным на шаге 4.
- Поместить значение b_uid, полученное на шаге 4, в массив "КОНЕЧНЫЙ".
- Удалить элемент с номером, полученным на шаге 4 из массива "ИСХОДНЫЙ".
- Переиндексировать массив "ИСХОДНЫЙ".
- Повторять шаги 4-8 до накопления в массиве "КОНЕЧНЫЙ" необходимого количества значений b_uid.
- Выбрать из БД записи со значениями b_uid, содержащимися в массиве "КОНЕЧНЫЙ".
- Показать записи.
- Конец.
D) Алгоритм 2, модификация 3.
- Начало.
- Выбрать из БД ВСЕ значения поля b_uid.
- Переместить все значения b_uid в массив "ИСХОДНЫЙ".
- Сгенерировать случайное число в диапазоне [0, количество элементов в массиве "ИСХОДНЫЙ" — 1].
- Получить значение b_uid из элемента массива "ИСХОДНЫЙ" с номером, полученным на шаге 4.
- Если в массиве "КОНЕЧНЫЙ" ещё нет такого значения, поместить его туда. Иначе — вернуться на шаг 4.
- Повторять шаги 4-6 до накопления в массиве "КОНЕЧНЫЙ" необходимого количества значений b_uid.
- Выбрать из БД записи со значениями b_uid, содержащимися в массиве "КОНЕЧНЫЙ".
- Показать записи.
- Конец.
E) Алгоритм 3.
- Начало.
- Получить минимальное значение поля b_uid.
- Получить максимальное значение поля b_uid.
- Сгенерировать в пять раз больше, чем требуется показать банеров, случайных чисел в диапазоне [минимальное значение b_uid, максимальное значение b_uid] и поместить их в массив "КОНЕЧНЫЙ".
- Выбрать из БД записи со значениями b_uid, содержащимися в массиве "КОНЕЧНЫЙ".
- Если количество возвращённых БД записей меньше требуемого количества банеров И не исчерпано количество попыток, перейти к шагу 4.
- Показать записи.
- Конец.
Теперь исследуем, как наши алгоритмы ведут себя на разных объёмах данных. Тест проводился на MySQL 5.1.41, PHP 5.3.2, Apache 2.2.14. Скрипты выполнялись в случайном порядке так, чтобы каждый из них выполнился 100 раз. Ниже приведены средние данные (в секундах) по всем 100 выполнениям для каждого скрипта.
| Записи \ Метод | A | B | C | D | E |
| 10000 | 0.059 | 0.014 | 0.021 | 0.014 | 0.005 |
| 20000 | 0.103 | 0.027 | 0.043 | 0.028 | 0.005 |
| 30000 | 0.158 | 0.040 | 0.064 | 0.041 | 0.005 |
| 40000 | 16.710 | 0.245 | 0.219 | 0.250 | 0.009 |
| 50000 | 107.522 | 0.228 | 0.236 | 0.297 | 0.010 |
| 60000 | 232.938 | 0.256 | 0.232 | 0.353 | 0.011 |
| 70000 | 362.722 | 0.247 | 0.226 | 0.384 | 0.012 |
| 80000 | — | 0.239 | 0.223 | 0.379 | 0.014 |
| 90000 | — | 0.259 | 0.237 | 0.373 | 0.015 |
| 100000 | — | 0.270 | 0.279 | 0.389 | 0.017 |
| 500000 | — | 7.925 | 8.740 | 7.983 | 0.104 |
| 1000000 | — | 16.294 | 16.947 | 16.143 | 0.557 |
| Память при 1000000 записей | — | 12538 Kb | 12538 Kb | 12541 Kb | 347 Kb |
Алгоритм 3 (пункт E) является абсолютным лидером как по производительности, так и по объёму используемой памяти, поэтому именно его мы доработаем и проверим в "условиях, наиболее близких к реальности". Имеющийся миллион банеров мы "проредим", удалив случайные банеры так, чтобы их осталось только сто тысяч. Затем проверим, как работает классический вариант алгоритма 3 (пункт E) и его модификация (алгоритм 4, пункт F), основанная на выборке данных по диапазонам и случайной сортировке средствами СУБД в случае неудачи выборки по конкретным значениям.
F) Алгоритм 4.
- Начало.
- Получить минимальное и максимальное значение поля b_uid.
- Сгенерировать в пять раз больше, чем требуется показать банеров, случайных чисел в диапазоне [минимальное значение b_uid, максимальное значение b_uid] и поместить их в массив "КОНЕЧНЫЙ".
- Выбрать из БД записи со значениями b_uid, содержащимися в массиве "КОНЕЧНЫЙ".
- Если количество возвращённых БД записей меньше требуемого количества банеров, сгенерировать запрос, WHERE часть которого вместо секции IN будет содержать перечень диапазонов в виде (`b_uid`>=1868 AND `b_uid`<=1888) OR (`b_uid`>=5257 AND `b_uid`<=5277) и т.д. и сортировку по rand(), иначе - перейти к шагу 10.
- Выполнить запрос.
- Увеличить диапазон вдвое.
- Если количество возвращённых БД записей меньше требуемого количества банеров И не исчерпано количество попыток, перейти к шагу 3.
- Показать записи.
- Конец.
Итак, исследование скорости работы на ста тысячах записей, первичные ключи которых не образуют непрерывную последовательность целых чисел, показало.
Результаты испытаний:
| Записи \ Метод | A | B | C | D | E | F |
| 100000 | 743.944 | 0.191 | 0.332 | 0.536 | 0.134 | 0.024 |
ВЫВОД
Алгоритм 1 (пункт A) вполне пригоден для работы с небольшим количеством данных. На большом же количестве его использование совершенно исключено.
Алгоритм 2 (в модификациях B, C, D) "продержался" гораздо дольше, но на действительно больших объёмах данных (от ста тысяч записей и больше) он тоже показывает недопустимое время выполнения.
Алгоритм 3 (пункт E) хорош на "непрерывной последовательности первичных ключей". В случае, если таковой нет, этот алгоритм может с достаточно высокой вероятностью не возвратить требуемого количества записей. При проводимом эксперименте на "прореженных ключах" этот алгоритм НИ РАЗУ не вернул 20 банеров. Да, теоретически, можно суммировать банеры, выбранные этим алгоритмом за несколько попыток, но вот будет ли это достаточно эффективно и быстро на больших объёмах данных — вопрос открытый.
Алгоритм 4 (пункт F) наиболее универсален: быстр, занимает мало памяти, прекрасно справляется с поставленной задачей. При проводимом эксперименте на "прореженных ключах" этот алгоритм НИ РАЗУ не был вынужден переходить к повторному увеличению диапазона, т.е. в 100 случаях из 100 он справился с задачей с первой попытки. Пользуйтесь, предлагайте свои усовершенствования.
Все исходные файлы эксперимента.
Готовый дамп БД (сто тысяч записей с "прореженными ключами").
,strike>уважаемый, не изобретайте велосипед!
SELECT DISTINCT(id) FROM table ORDER BY RAND() limit 20;
Даже не смешно. Рекомендую внимательнее перечитать условие задачи и анализ в т.ч. такого решения.
А почему бы не использовать такой (самы простой вариант):
$count=SELECT COUNT(`b_uid`) FROM `banner`
$limit=mt_rand(0,$count-20);
SELECT * FROM `banner` LIMIT $limit, 20
??
Потому, что «выбрать 20 случайных записей» и «выбрать 20 подряд идущих записей из случайного места» — не одно и то же. Изначальная идея состоит как раз в том, чтобы выбирать записи из случайных (в прямом математическом смысле слова) мест.