Хабрахабр / Комментарии к посту «Выборка произвольных записей в MySQL» в блоге «MySQL»

31.08.2010 10:26:24 clockworkbird

clockworkbird — Tue, 31 Aug 2010 10:26:24 GMT

«Глупый и ленивый аутсорсер» решает поставленную задачу. Максимально простым для него способом. Поскольку его время — его деньги, а за «проявление смекалки» его никто никогда не поблагодарит. Может быть «умный и работящий постановщик» поленился расписать требования и поставил задачу неправильно?

18.04.2010 17:35:54 xaxaTyH

xaxaTyH — Sun, 18 Apr 2010 17:35:54 GMT

Это Вы неадекват.
Человек говорит правильно. Ибо показав свою «умность» Вы лишь принизили себя в глазах спецов, ибо полнейшая глупость, работающая немногим быстрее стандартного RAND().

Ничего другого не признаете.
Уверен процентов на 99%, что разработчику в ТЗ не ставилось задачи сделать High-Load решения.

07.01.2010 05:30:04 INIT

INIT — Thu, 07 Jan 2010 05:30:04 GMT

действительно не так важно на больших таблицах, а вот LIMIT offset на таких будет очень сильно тормозить

07.01.2010 05:24:41 INIT

INIT — Thu, 07 Jan 2010 05:24:41 GMT

а когда вам неравные веса баннеров захочется, база тоже должна это уметь :)?

22.06.2009 12:56:07 maovrn

maovrn — Mon, 22 Jun 2009 12:56:07 GMT

Две задачи в одном триггере несколько портят красоту кода, но жить вполне можно. Впрочем, я могу себе это только представлять, ибо на практике не сталкивался.

22.06.2009 09:04:09 TEHEK

TEHEK — Mon, 22 Jun 2009 09:04:09 GMT

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

Но вцелом, тоже мысль.

22.06.2009 08:49:24 TEHEK

TEHEK — Mon, 22 Jun 2009 08:49:24 GMT

И вдобавок MySQL не поддерживает несколько триггеров на одном событии одной таблицы. Так что если там уже висит один триггер, его придется менять, дописывая функционал.

20.03.2009 21:55:54 Bal

Bal — Fri, 20 Mar 2009 21:55:54 GMT

>Да и про LIMIT в mysql советую прочитать. Работает он очень быстро, поскольку строки MySQL попросту пропускает не записывая в результат.

Ваши бы слова, да в эту физическую реальность… :)

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

Вылечилось только введением отдельного поля «номер страницы».

MySQL очень болезненно относится к выборке последних значений в большой отсортированной таблице.

16.03.2009 14:12:53 McDEN

McDEN — Mon, 16 Mar 2009 14:12:53 GMT

так они (СУБД) и так понимают, вопрос в том как они это выполняют.

16.03.2009 13:12:01 symbix

symbix — Mon, 16 Mar 2009 13:12:01 GMT

order by rand() это temporary table + filesort соответственно есть резкий переход от использования памяти к диску, который зависит от размера буферов. четко предсказать когда этот переход произойдет невозможно, разве что провести эксперимент для конкретного запроса с конкретными настройками и конкретными данными

16.03.2009 12:57:57 LoneCat

LoneCat — Mon, 16 Mar 2009 12:57:57 GMT

Да, вы правы, просто как я уже писал, я изначально использую синтетический ключ именно для того чтобы поддерживать нумерацию, но если использовать его исключительно для случайной выборки — то это вполне подходит, и тогда этот вариант подойдет даже в случае когда происходит частое добавление/удаление записей, по одному лишнему запросу на действие имхо погоды в плане производительности сильно не сделают, а выборка уже будет не в пример быстрее.

16.03.2009 12:32:04 markshevchenko

markshevchenko — Mon, 16 Mar 2009 12:32:04 GMT

Что-то как-то строго Вы к аутсорсерам. Вопрос не в том, «что будет если в исходной таблице 10 000 записей. А что если 1 000 000?», а в том, сколько их там будет, и какие вообще требования к задаче. Предложенный аутсорсером вариант вполне себе рабочий для небольших таблиц, если в ТЗ размер таблиц не оговорен, то это, скорее, Ваш косяк.

Если записей действительно миллион, и выбирать надо быстро, я бы сделал так: завёл бы поле, куда помещал бы случайные значения при вставке. При нормальном распределении случайных чисел и большом количестве записей можно получать выборку с запасом, и затем ограничивать её с помощью LIMIT.

16.03.2009 11:39:06 Ueasley

Ueasley — Mon, 16 Mar 2009 11:39:06 GMT

Я храню в мемкеше массив с айдишниками, оттуда беру и мешаю, дальше IN().

Вроде шустро бегает.

16.03.2009 11:24:03 alexzzam

alexzzam — Mon, 16 Mar 2009 11:24:03 GMT

Ну, перестраивать весь хвост при удалении не обязательно. Synth_key же не обязан поддерживать порядок нумерации.
То есть, UPDATE table SET synth_key=$synh_key_of_deleted_item WHERE synth_key=$max_synth_key

15.03.2009 22:55:24 symbix

symbix — Sun, 15 Mar 2009 22:55:24 GMT

Правильное с точки зрения производительности, если нужно «показать что-то от балды». Именно для этого начинающие используют order by rand().

Если нужно выдерживать распределения, то для этого надо строить вспомогательные таблицы строить.

Если же пофиг на производительность — то и order by rand() покатит.

15.03.2009 20:37:30 Sulako

Sulako — Sun, 15 Mar 2009 20:37:30 GMT

ах да, еще LIMIT:

SELECT * FROM table WHERE id IN (SELECT id FROM table ORDER BY RAND() LIMIT 0,10)

15.03.2009 20:32:32 Sulako

Sulako — Sun, 15 Mar 2009 20:32:32 GMT

(почемуто само отправилось раньше времени)
тогда
SELECT * FROM table WHERE id IN (SELECT id FROM table ORDER BY RAND() )
где id — первичный ключ.
а то выбирать для сортировки все имеющиеся поля явно не айс…

15.03.2009 20:30:15 Sulako

Sulako — Sun, 15 Mar 2009 20:30:15 GMT

Ну если уж уменьшать размер таблицы в памяти…

15.03.2009 18:19:14 tvv

tvv — Sun, 15 Mar 2009 18:19:14 GMT

Дополнение к лабораторной работе N1.

Как и подсказали выше (TimTowdy), если сужать исходный набор данных, используя например WHERE RAND() < 0.01, то ORDER BY RAND работает значительно быстрее. Например, на используемом мной в примере выше c 500.000 записями запрос

SELECT id FROM table1 WHERE RAND() < 0.1 ORDER BY RAND() LIMIT 10;

отрабатывает за 0.34 sec, почти в 2.5 раза быстрее.

или например

SELECT id FROM table1 WHERE id % 100 = 0 ORDER BY RAND() LIMIT 10;

отработает за 0.30 sec (в том случае 0 — это вычисленное ранее случайное значение из диапазона 0..99).

Но все равно это не хороший путь, я не спорю. Хотя и его нельзя отвергать в ряде случаев.

15.03.2009 18:03:59 tvv

tvv — Sun, 15 Mar 2009 18:03:59 GMT

Нет, не придется. Я же написал выше, что можно использовать WHERE id IN (..., ..., ...). То есть запросов будет намного меньше (возможно, даже только один, это по ситуации, нужно замерять).

15.03.2009 18:01:09 tvv

tvv — Sun, 15 Mar 2009 18:01:09 GMT

Кстати, отличное решение, хоть и частичное. Спасибо.

На моем примере, выборка 10 из 500.000, позволяет ускорить примерно в 3 раза. Забавно, что если вместо коэффициента 0.001 выбрать например 0.1 или 0.000001, но время выборки не изменяется вообще, по крайней мере на моих тестах.

15.03.2009 17:59:15 LDEV

LDEV — Sun, 15 Mar 2009 17:59:15 GMT

Вооот, вот и получается что для выборки в 3к записей придется делать 3к запросов к базе. Не лучше…

15.03.2009 17:50:48 tvv

tvv — Sun, 15 Mar 2009 17:50:48 GMT

Нет, случайная последовательность не нужна, в порядке добавления — вполне достаточно. Нужно только знать количество элементов этого массива, и сгенерировать нужное количество случайных индексов (от 0 до N-1). Затем по этим индексам извлечь id из массива, и уже затем по этим id извлечь записи из базы данных.

Ну смотрите, допустим есть массив из N = 15000000 элементов.
1. получаете случайный индекс: i = rand(0, 15000000 — 1)
2. извлекаете id: id = cache[i], или id = getIdFromCache(i) в зависимости от реализации

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

15.03.2009 17:45:08 maovrn

maovrn — Sun, 15 Mar 2009 17:45:08 GMT

Йеллопуки-Йеллопуки, перешей мне с жопы руки! Спасибо вам за дельное замечание. Теперь я запомню что такое join в php.

15.03.2009 17:35:42 LDEV

LDEV — Sun, 15 Mar 2009 17:35:42 GMT

да, в принципе кэш Primary Key таблицы тоже вариант. И выше вариант с частью этих ключей — вполне нормальная выборка для небольшой группы.

Но даже выборка ID из кэша — тот еще велосипед получается — нужна же не последовательность с которой они добавлены, а случайная. Разве нет?

15.03.2009 17:31:41 tvv

tvv — Sun, 15 Mar 2009 17:31:41 GMT

А почему бы и не кешировать результаты? Если конечно это не жесткое требование «должны быть случайны в каждой выборке». Скажем, имеете 15 млн записей, даже если в памяти у Вас в кеше хотя бы несколько тысяч — этого уже достаточно чтобы пользователю устроить случайный хоровод из этих значений. А кеш можно время от времени обновлять.

15.03.2009 17:28:43 tvv

tvv — Sun, 15 Mar 2009 17:28:43 GMT

Дальше — храните id всех этих миллионов записей в кеше в памяти, 15 млн id — это 60 Мб массив. Когда нужно выдать набор случайных — извлекайте id из кеша, и делайте например запрос вида SELECT… WHERE id IN (..., ..., ...). Будет работать практически мгновенно.

Добавляемые записи накапливайте в отдельный массив, и раз в N времени перестраивайте основной, добавляя или удаляя из него записи в зависимости от изменений.

Про ORDER BY RAND() рекомендую в данном случае забыть.

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

15.03.2009 16:51:39 LDEV

LDEV — Sun, 15 Mar 2009 16:51:39 GMT

ну 50 юзверей я просто не пущу в панель :)) и всё-таки при таком большом объеме одновременных выборок лучше разделить таблицу на несколько. Будет некий рандом внутри одной группы, не заходящий в другую.

15.03.2009 16:51:04 tvv

tvv — Sun, 15 Mar 2009 16:51:04 GMT

Лабораторная работа N1, случайные выборки из таблицы.

Создаем таблицу table1 с первичным ключом id, генерим 500.000 записей.
Делаем ряд запросов (тесты проводим с MyISAM и InnoDB без блокировок и транзакций), запускаем по 10 раз, вычисляем среднее и минимальное время.

1. Делаем запрос с ORDER BY RAND()

SELECT id FROM table1 ORDER BY RAND() LIMIT 10;

MyISAM 0.78 sec
InnoDB 1.20 sec

2. Делаем запрос, предложенный автором, с использованием UNION

(SELECT id FROM table1 LIMIT 10000, 1)
UNION
(SELECT id FROM table1 LIMIT 60000, 1)
UNION
(SELECT id FROM table1 LIMIT 110000, 1)
UNION
(SELECT id FROM table1 LIMIT 160000, 1)
UNION
(SELECT id FROM table1 LIMIT 210000, 1)
UNION
(SELECT id FROM table1 LIMIT 260000, 1)
UNION
(SELECT id FROM table1 LIMIT 310000, 1)
UNION
(SELECT id FROM table1 LIMIT 360000, 1)
UNION
(SELECT id FROM table1 LIMIT 410000, 1)
UNION
(SELECT id FROM table1 LIMIT 460000, 1);

MyISAM 1.31 sec
InnoDB 2.90 sec

3. Ускоряем предыдущий запрос, заменяем UNION на UNION ALL

MyISAM 1.31 sec
InnoDB 2.89 sec

4. Используем один запрос с WHERE id IN (...) вместо набора запросов, объединенных по UNION.

SELECT id FROM table1 WHERE id IN (10000, 60000, 110000, 160000, 210000, 260000, 310000, 360000, 410000, 460000);

MyISAM 0.00 sec (менее 10 миллисекунд)
InnoDB 0.01 sec

Выводы.

Способ N1 с ORDER BY RAND(), несмотря на то что он очень неэффективный, работает очень надежно, гарантированно выдавая результат независимо от состояния набора данных, в том числе и при условии конкурентного доступа.

Для способов N 2-4 придется или использовать а) предварительный запрос SELECT COUNT(...) и б) блокировки (для MyISAM) или транзакции с уровнем изоляции repeatable read или sirializable (для InnoDB) чтобы гарантировать корректный результат в условиях конкурентного доступа к данным. Если это делать, то время выполнения этих запросов можно увеличить еще примерно на 50%.

Использование набора запросов, объединенных через UNION, работает медленнее на больших наборах данных чем даже тормозной ORDER BY RAND().
UNION ALL позволяет выиграть несколько микросекунд, но проблему не решает.

Самый эффективный способ — вычислить заранее случайные значения первичных ключей, и делать запрос по ним. При этом нужно не забывать про описанный выше конкурентный доступ (записи могут быть удалены после того как выполнен запрос SELECT COUNT и вычислены значения ключей, но еще не выполнен основной запрос).

Предложенный автором способ действительно работает немного быстрее на
небольшом количестве записей, но в средних и больших таблицах (от 200-500 тыс. записей) уступает даже неэффективному ORDER BY RAND() если нужно получить несколько случайных значений, и чем больше значений нужно получить, тем более неэффективен этот метод.

Вот, почти что статья получилась ))

15.03.2009 16:49:46 tvv

tvv — Sun, 15 Mar 2009 16:49:46 GMT

Вы уверены, что это невозможно реализовать? Я только что попробовал, успешно. MySQL 5.1.30.

Курсоры в MySQL работают прекрасно, хотя и имеют ряд ограничений (например, нет возможности пропускать записи, что сразу убивает идею использовать курсоры в полной мере для данной задачи) и относительно тормозные. Только что написал тест, извлечение 10 случайных записей из 500.000 с использованием курсоров обработка занимает 3.20 sec. Это конечно медленнее чем даже предложенный автором пример, но зато если, например, нужно было бы вернуть, скажем, 100 случайных, то это заняло бы примерно те же 3.20 sec, а другие примеры будут все более и более тормозить (пример
автора, скажем, выполняется более 10 секунд на моем наборе данных).

15.03.2009 11:41:08 webmechanics

webmechanics — Sun, 15 Mar 2009 11:41:08 GMT

как уже писали ниже — вы можете держать в памяти таблицу и из нее делать выборку, хоть всех данных, хоть одних primary keys

потом, если у вас 50 одновременных запросов на случайную выборку — ничего страшного если все 50 юзеров увидят одни и те же случайные результаты? важно что результаты случайные, не важно какие именно, ведь так?

15.03.2009 10:38:01 LDEV

LDEV — Sun, 15 Mar 2009 10:38:01 GMT

а ведь действительно, если не нужна совсем настоящая случайная последовательность, то можно и сделать дополнительное поле:
а) либо его раз в сутки (или чаще) забивать значением RAND()
б) в моем случае взяли crc32 важных данных записи, которое записывается при вставке и потом не меняется.

Во втором случае удобно — что перетрясать таблицу не нужно каждый день, а просто брать order by по этому полю.

15.03.2009 10:31:48 LDEV

LDEV — Sun, 15 Mar 2009 10:31:48 GMT

оно тут бессмысленно. кто кэшировать — результаты? они должны быть случайны в каждой выборке…

15.03.2009 10:03:12 vcache

vcache — Sun, 15 Mar 2009 10:03:12 GMT

У меня была аналогичная задача, только надо было не случайно выбирать линии, а последовательно. При этом выборки должны быть закольцованы, а в последовательности ключей регулярно появляются «дыры». Решил примерно вот так:

	$cntcache = 'current-state/laste';
	if (file_exists($cntcache)){
		$lastID = file_get_contents($cntcache);
	} else $lastID = 0;

	for($i = 0; $i < 2; $i++){
		$lines = mysql_query( "SELECT id FROM table WHERE id > '$lastID' LIMIT 1");
		if (mysql_num_rows($lines) != 0){
			$line = mysql_fetch_row($anketes);
			$lastID = $line[0];
			break;
		} else $lastID = 0;
	}
	file_put_contents($cntcache, $lastID);

Может кто-то подскажет способ лучше и производительнее?

15.03.2009 09:43:51 webmechanics

webmechanics — Sun, 15 Mar 2009 09:43:51 GMT

дальше — кеширование? :)

15.03.2009 03:41:09 WhiteD

WhiteD — Sun, 15 Mar 2009 03:41:09 GMT

Про универсальность никто и не говорил. Как вы правильно подметили — все решения имеют право на жизнь и некоторые из них вполне применимы при определенных условиях. В тексте топика я сделал ошибку и не выписал в отдельный параграф всех поставленных передо мной условий. В комментарии habrahabr.ru/blogs/mysql/54176/#comment_1453063 я резюмировал все что упустил в топике. Но ничего не поделаешь, я уже дал пищу для хабровских троллей и они уже с пеной у рта начали кричать «все дураки, один я умный». Увы и ах…

15.03.2009 03:34:52 WhiteD

WhiteD — Sun, 15 Mar 2009 03:34:52 GMT

> и я тоже могу ошибаться.
И ошибаетесь. Опять же без обид.
Приведенный вами выше алгоритм невозможно реализовать, используя возможности написания хранимых процедур в MySQL.
Моя ошибка в том, что я не обозначил рамки использования моего варианта решения в тексте топика, но оговорил их в одном из комментариев. Про проектирование и анализ/постановку задачи и говорить нечего — железное решение «правящих менеджеров», с которым не поспоришь.

Повторю на всякий случай условия и рамки: выборка абсолютно произвольна (вариант с выборкой по первичному ключу отпадает, с условием его разряженности), кол-во записей большое, но не гигантское (порядка 100 000 — 500 000 записей, и не зависит от масштабов и роста проекта), частота вставок и удалений записей относительно велика (порядка 20 записей в минуту, поддержка второго суррогатного не разряженного индекса неприемлема в виду частых обновлений). При обозначенных выше условиях мой вариант при тестировании показал наилучшие результаты. И если уж говорить о грамотности стороннего разработчика — то он изначально знал условия и особенности работы его кода, но все равно применил столь не производительный вариант (как потом выяснилось из личного общения — по незнанию).

ЗЫ: вы правы насчет кеширования результатов. В итоге пришлось применить (в обход требований менеджмента) кеширование произвольно выбранных записей, но на порядок большего кол-ва чем требуется. При каждом же выводе результатов происходит произвольная выборка нужного кол-ва записей из результатов первого (большого) набора.

15.03.2009 00:31:07 tvv

tvv — Sun, 15 Mar 2009 00:31:07 GMT

Данный аутсорсер вовсе не ленивый и не глупый. Он применил наиболее надежное решение из всех возможных, при этом соблюдая приемлемую производительность и потратив на данное решение минимум времени с средств заказчика.

Остальные вышеуказанные решения или ненадежны, как было указано выше, или еще более неэффективны с точки зрения производительности, например требуют блокировок или транзакций с уровнем изоляции минимум repeatable read.

А решение автора статьи вообще категорически неприемлемо IMHO. Например, хорошо если нужно извлечь 10 случайных записей. А если нужно извлечь 100 или 1000 случаных, что тогда? Кошмар получится. Не говоря о том, что при этом для надежности нужно или блокировать таблицу или использовать ту же транзакцию с уровнем изоляции repeatable read или serializable. И не говоря о том, что нужно учитывать возможные повторы.

Приемлемым и надежным решением может быть использование хранимой процедуры, которая использует курсор (нужен минимум 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 в кеше, не так уж и много для выделенного для данной задачи сервера.

Обычно, по опыту, в бизнес-проектах не требуется получать случайные некешируемые выборки из миллионов записей при каждом запросе. Даже если это огромная баннерная система, но и там совсем другие принципы, и «случайные» выборки вовсе не случайны… То есть мне воистину сложно представить себе бизнес-задачу, где нужна была бы выборка именно случайных значений из базы данных при каждом запросе пользователя, скорее всего тут имеет место проблема аналитической стадии и проектирования.

P.S. Называть кого-то глупым из-за написанного им кода считаю неправильным в принципе. По карйней мере автор, который привел свой неприемлемый вариант решения, уж точно не имеет права так делать IMHO. Пожалуйста, без обид, все мы учимся на ошибках, и я тоже могу ошибаться.

14.03.2009 21:13:38 Alexsib

Alexsib — Sat, 14 Mar 2009 21:13:38 GMT

Сталкивался с подобной проблемой. Применил следующее:
1. Ввёл в таблицу дополнительный столбей int(11)
2. Раз в сутки этот столбец обновляется и в него пишутся значения rand
3. Выборка идёт примерно следующая: SELECT * FROM table WHERE rand_field > RAND() LIMIT 10

Таким образом функция RAND() вызывается один раз, нет копирования записей в темповую таблицу, обновление «случайного» столбца происходит ночью, когда большенство пользователей спит

14.03.2009 20:44:06 Swappp

Swappp — Sat, 14 Mar 2009 20:44:06 GMT

В комментариях неоднократно указали как правильно.

И что тут правильного?
Как будет выглядеть результат например на таблице с такими id: 1, 2, 3, 1000? Что мы будем видеть? В 997 из 1000 просмотров будет запись с id 1000. Это правильно? На мой взгляд тут вообще нету единого правильного решения. Все зависит от конкретной ситуация, от того, сколь в таблице строк, как часто удаляются эти строки, насколько важно, что бы строки выдавались с действительно равной вероятностью и т.п. Предложенное автором решение вполне рабочее и имеет право на жизнь, как выдаваемое вами за «правильное», но они не универсальны.