Отсебятина Статьи Проекты
Облако тегов
Web CMS CSS htaccess HTML Javascript MySQL Php Безопасность Мониторы Новостная лента Оптимизация Ошибки Разработка сайта Часы Юзабилити оптимизация ошибки

Выборка произвольных (рандомных) записей из базы

Отсебятина от 21 марта 2009 года.    Теги: MySQL Оптимизация


При разработке порталов очень часто возникает задача из ряда "вывести десяток произвольных записей на главную страницу". А как вывести — уже проблема.


Проблема стандартного решения


Стандартным является следующее решение:
SELECT * FROM `tbl` ORDER BY RAND() LIMIT 10

Когда записей в таблице меньше тысячи, особых проблем не наблюдается. Но когда их больше — появляются значительные издержки. Давайте посмотрим EXPLAIN этого запроса:
mysql> EXPLAIN SELECT * FROM `tst` ORDER BY RAND() LIMIT 10; +----+-------------+-------+------+---------------+------+---------+------+-------+---------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------+---------+------+-------+---------------------------------+ | 1 | SIMPLE | tst | ALL | NULL | NULL | NULL | NULL | 90347 | Using temporary; Using filesort | +----+-------------+-------+------+---------------+------+---------+------+-------+---------------------------------+ 1 row in set (0.00 sec)

  • Mysql проходит по всем строкам
  • filesort сортирует записи по функции RAND()
  • Результат помещается во временную таблицу
  • Выбирается 10 первых записей

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

Альтернативные варианты. Введение

Поводом для написания статьи является статья от Андрея WhiteD Кравчука помещенная сначала vkontakte.ru, а затем на habrahabr.ru — Выбор произвольных записей в MySQL. Мне не очень понравился предложенный им вариант из-за использования LIMIT x, y. Ведь для этой выборки Mysql перебирает x+y записей.


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

Посмотреть код
>CREATE TABLE `tst` ( `id` INT UNSIGNED NOT NULL AUTO_INCREMENT, `cat` TINYINT(3) UNSIGNED NOT NULL, `string` VARCHAR(100) NOT NULL, PRIMARY KEY (`id`), KEY `cat` (`cat`) ) ENGINE=InnoDB;


Посмотрим, что говорит MySQL:
mysql> SELECT COUNT(*) FROM `tst`; +----------+ | COUNT(*) | +----------+ | 90001 | +----------+ 1 row in set (0.05 sec) mysql> SELECT * FROM `tst` LIMIT 1; +----+-----+-----------+ | id | cat | string | +----+-----+-----------+ | 2 | 8 | запись №2 | +----+-----+-----------+ 1 row in set (0.00 sec)

Улучшение стандартного решения

Посмотрим, сколько выполняется стандартное решение на нашей таблице:
mysql> SELECT * FROM `tst` ORDER BY RAND() LIMIT 10; +-------+-----+---------------+ | id | cat | string | +-------+-----+---------------+ | 48409 | 7 | запись №48408 | | 95335 | 5 | запись №95334 | | 33179 | 4 | запись №33178 | | 60510 | 2 | запись №60509 | | 84378 | 7 | запись №84377 | | 81915 | 6 | запись №81914 | | 66983 | 3 | запись №66982 | | 37146 | 2 | запись №37145 | | 90136 | 6 | запись №90135 | | 46903 | 7 | запись №46902 | +-------+-----+---------------+ 10 rows in set (0.39 sec)
Если посмотреть на EXPLAIN, приведенный выше, можно заметить тип выборки — ALL, и при этом не используются ключи! Попробуем сделать выборку по id:
mysql> SELECT * FROM `tst` ORDER BY RAND() LIMIT 10; mysql> SELECT `id` FROM `tst` ORDER BY RAND() LIMIT 10; +-------+ | id | +-------+ | 3028 | | 19395 | | 73747 | | 15553 | | 42191 | | 65079 | | 2174 | | 58496 | | 53484 | | 65654 | +-------+ 10 rows in set (0.27 sec) mysql> EXPLAIN SELECT `id` FROM `tst` ORDER BY RAND() LIMIT 10; +----+-------------+-------+-------+---------------+------+---------+------+-------+----------------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+------+---------+------+-------+----------------------------------------------+ | 1 | SIMPLE | tst | index | NULL | cat | 1 | NULL | 89701 | Using index; Using temporary; Using filesort | +----+-------------+-------+-------+---------------+------+---------+------+-------+----------------------------------------------+ 1 row in set (0.00 sec)
Выборка ускорилась почти в полтора раза. Но помимо ключа, нам нужны и остальные данные. MySQL не позволяет использовать во вложенных запросах LIMIT. Поэтому необходимо вытаскивать все `id` и на их основе делать выборку. Но смысла в этом нет, потому что скорость выборки будет еще хуже.

Альтернативные варианты

Так как рассматриваемые выборки будут подготавливаться с помощью PHP, то замерять их скорость мы тоже будем в PHP.


Вариант с LIMIT от WhiteD:


Посмотреть код
Посмотреть EXPLAIN

Результат:

IdCatString
557853запись №55784
713283запись №71327
652606запись №65259
313654запись №31364
686293запись №68628
510062запись №51005
61999запись №6198
160469запись №16045
24435запись №2443
87166запись №8715
Запрос выполнен за: 0.3158 с


Заметно, скорость выполнения выборки чуть чем, чем у ORDER BY RAND, но она по-прежнему слишком высока.

Преимущества варианта:
  • Количество возвращаемых значений всегда будет одинаково и равно запрошенным
  • Полученные значения будут уникальными
  • Не зависим от равномерности удаленных строк
  • Простота реализации
Недостатки варианта:
  • Большое время выполнения
  • Использование UNION


Вариант с неравенством псевдослучайному числу MySQL RAND()


Как мне кажется, использование UNION — не очень хороший тон. Но иногда UNION удобный вариант для получения необходимого результата. Чтобы решить проблему, нам нужно задавать случайное число для каждого результата. Причем нельзя id жестко привязывать к этому числу, ведь такого id может и не быть.

На помощь на приходит
`id` > FLOOR(RAND()*МАКСИМАЛЬНЫЙ_ID)
RAND() возвращает псевдослучайное число от 0 до 1. Умножая на максимальный ID и округляя в меньшую сторону, мы получим число от 0 до (MAX_ID -1). `Id` больше этого числа, поэтому он входит в диапазон всех существующих идентификаторов. Если идентификатор не существует, то выбирается следующий существующий. Таким образом, пробелы в ключах нам не страшны.

Стоит обратить внимание на то, что нам необходим именно максимальный ID, а не количество записей. Если из 10 записей мы удалим две из середины, и будем использовать COUNT(*), который будет равен 8, то запись 9 и 10 никогда не будут выбраны. Поэтому нам необходимо использовать максимальный идентификатор 10.


Составляем запрос
Посмотреть код

Посмотреть EXPLAIN


Результат:
IdCatString
3385запись №338
4788запись №478
4901запись №490
6927запись №692
4176запись №417
2129запись №212
1691запись №169
4652запись №465
4852запись №485
12352запись №1235
Запрос выполнен за: 0.0095 с

По-моему, замечательный результат, но есть одно но...

Когда мы делаем запрос "SELECT FLOOR(RAND()*100000)", то получаем значение от 0 до 99999. Но когда эту процедуру вставляем в условие WHERE, то проявляется нечто и id всегда получается меньше полутора тысяч.

Преимущества варианта:
  • Полученные значения будут уникальными
  • Малое время выполнения
  • Простота реализации
Недостатки варианта:
  • Id записей меньше 1000!
  • Количество возвращаемых значений не всегда будет одинаково
  • Использование UNION
  • Зависим от равномерности удаленных строк (насколько — зависит от общего количества записей)

Жаль, конечно, но придется воспользоваться другим вариантом.


Вариант с неравенством псевдослучайному числу PHP mt_rand()


Посмотреть код

Посмотреть EXPLAIN


Результат:

IdCatString
479387запись №47937
170339запись №17032
57913запись №5790
493225запись №49321
913449запись №91343
395323запись №39531
75437запись №7542
741679запись №74166
582852запись №58284
815018запись №81500
Запрос выполнен за: 0.0121 с


Конечно, не все так идеально, как хотелось бы. WhiteD подметил, что если таблица будет иметь 100 записей, а id будет начинаться со 101, то выборка будет некорректной:
Если все 10 псевдослучайных чисел будут меньше 101, то после выборки мы получим всего один результат с id = 101. В предложенном им варианте такой проблемы не существует.



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

Преимущества варианта:
  • Полученные значения будут уникальными
  • Малое время выполнения
  • Простота реализации
Недостатки варианта:
  • Количество возвращаемых значений не всегда будет одинаково
  • Использование UNION
  • Зависим от равномерности удаленных строк (насколько — зависит от общего количества записей)


Доборный метод


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


Посмотреть код
Посмотреть EXPLAIN

Исходя из приведенного кода, заметно, что разбор результата (fetch) должен происходить внутри цикла, поэтому здесь нельзя измерить время выполнения запросов и, одновременно, вывести результат. Отдельно время выполнения составляет ~0.006 секунд, что является лучшим результатом.


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


Тестирование

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


Дано:
  • Таблица innoDB с 90001 записью
  • Скрипты, представленные выше. Каждый скрипт запускался 1000 раз. В расчет шло время на составление запроса и выборку результата (без отображения и перебора fetch)
  • Командная строка php 5.2.8
  • MySQL 5.0.27
  • Система: CPU — AMD Duron 1600, RAM &mdash 1024mb PC 2700, HDD &mdash 7200RPM ATA100
  • ОС: Windows XP с отключенными ресурсоемкими программами
#1. ORDER BY RAND();
#2. Вариант от WhiteD
#3. Вариант с неравенством псевдослучайному числу PHP mt_rand()
#4. Доборный метод
Результаты:
Результат/Вариант#1#2#3#4
Общее время теста347.491200c387.169800c3.87530c4.07540c
Средний результат000.347491c000.387170c0.00388c0.00408c
Оставить сообщение






Любое копирование должно сопровождаться ссылкой на сайт.
Если вам что-то не понравилось — сообщайте.
Кича Владимир
x
Мне не нравится этот сайт, удалить его