Выборка случайного поля в MySQL

Question

[Евгений Шелег]

Здравствуйте.

До недавнего времени использовал костыль ORDER BY rand() но при увеличении таблицы его скорость падает.

Требуется вывести случайное поле. Записи фрагментированы (id не по порядку и содержит дырки).

Если это как то упростит задачу, использую ZF.

Comments

[Евгений Шелег]

id от большего к меньшему. Прим: 20 26 45 55 56 57 90 и тд

[Евгений Шелег]

*меньшего к большему. Хотя это наверно не как не влияет.

Answer 1

[winnie]

Пусть A — результат SELECT MAX(id) FROM `my_table`(его вполне можно хранить отдельно в key-value-хранилище и иногда обновлять)
Генерируем число от 1 до A включительно, пусть это B на стороне клиента (в данном случае — php приложения).
И выбираем первую запись, id которой >= B (SELECT `pole` FROM `my_table` WHERE `id` >= B LIMIT 1)
Попробуйте. Должно помочь.

Comments

[burdakovd]

из-за фрагментированности записей выбор будет не равновероятен

[winnie]

А это и не нужно скорее всего. Тут какая-нибудь «случайная статья» же, или товар, например. Ну можно часа в четыре утра устранить погрешность за прошлый день по крону — никто не пострадает скорее всего. Считаю архитектурные изменения излишними. Редко на ZF пишут вроде энтерпрайз, где тервер строгий необходим.

[Евгений Шелег]

winnie, кажется то что надо. Надо попробовать.

П.С. Для общего развития, что подразумевается под равновероятен?

[winnie]

Пусть мы имеем множество ключей с id:
1,2,3,4,5,6,7,8
и таким методом выбираем случайную запись.
Количество «выпадений» каждого кортежа с id будет практически равно при большом количестве выборок — идеальный случай. При очень большом количестве выборок. Тут мы говорим, что всякая выборка будет равновероятна (P=1/8 для каждого id) (Закон Больших Чисел из теории вероятности). Это как бросать монетку бесконечное количество раз — примерно будет пополам орла и решки.

А теперь представим, что мы удалили записи с id 1,2,3
И теперь имеем 4,5,6,7,8
А число, что генерируется всё ещё лежит в пределе [1, 8] и по закону больших чисел будет равновероятно выдавать значения от 1 до 8, но поскольку мы обращаемся к БД с «дырками», то вероятность выпадения 4 повышается, повышается в четыре раза (всякое значение функции получения случайного кортежа, в которой сгенерировалось случайное от 1 до 4 в результате даст нам запись с id = 4). Тут мы говорим, что равновероятность не соблюдается и вероятность появления записи с id=4 равна P=4/8=1/2, а у записей c id=5,6,7,8 вероятность P=1/4

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

Устранять дыры можно уже потом, когда перестанет радовать неравномерность, по крону. Да только придется ли вообще это делать? Вот где вопрос. Если удаляются записи не огромными пачками последовательными, то всё будет радовать пользователя.

[winnie]

Ошибся, у записей с id=5,6,7,8 будет вероятность P=1/8

[Евгений Шелег]

Спасибо за развернутый ответ. Примерно это и предполагал. Равновероятность думаю мне не к чему. Вывод нужен условный для показа что еще есть для пользователя.

[Евгений Шелег]

Данный метод получился в 2-3 раза медленнее моего за счет того что идет 2 запроса к базе. Возможно будет обратный эффект при большей таблице.

[winnie]

Безусловно. Вот результаты тестов:

nettsundere@tsundere:~/Desktop/test$ ruby compare.rb
Введите пароль, пожалуйста:
Благодарю вас!
Для 10 элементов результаты показаны следующие:
Было: 0.00035 сек. в среднем
Стало: 0.000275 сек. в среднем
Стало (если бы max сохранили в redis или memcached): 0.0001375 сек. в среднем
Для 100 элементов результаты показаны следующие:
Было: 0.0004375 сек. в среднем
Стало: 0.0002875 сек. в среднем
Стало (если бы max сохранили в redis или memcached): 0.00015 сек. в среднем
Для 1000 элементов результаты показаны следующие:
Было: 0.0011375 сек. в среднем
Стало: 0.0003125 сек. в среднем
Стало (если бы max сохранили в redis или memcached): 0.0001625 сек. в среднем
Для 10000 элементов результаты показаны следующие:
Было: 0.0097125 сек. в среднем
Стало: 0.00035 сек. в среднем
Стало (если бы max сохранили в redis или memcached): 0.000175 сек. в среднем

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

Код теста: gist.github.com/1371692

Первый запрос можно и нужно кэшировать (что видно из результатов (стало и стало с сохранением max), где я кэширование лишь изобразил, дабы не писать сложный тест, но видно, что запрос на max(id) достаточно тяжелый, чтобы его всякий раз выполнять). Записать max(id) можно даже в специальную таблицу для кэша, если не имеется возможности использовать redis или memcached. Обновлять придётся лишь при добавлении новых записей и при удалении.
Ну или просто оставить как есть, если устраивает.

Answer 2

[vart]

Уже был такой вопрос:
habrahabr.ru/qa/5525/

И топики на эту тему:
habrahabr.ru/blogs/mysql/54176/
habrahabr.ru/blogs/mysql/55864/
habrahabr.ru/blogs/mysql/104366/

Answer 3

[edogs]

1) Забацать таблицу id<->realid. Заполнять ее можно очень быстро посредством insert into select from. Соответственно в ней уже id не будут фрагментированы и будет очень легко выбрать.

2) Можно поступить аналогично п.1, сделав таблицу просто из realid, так же ее заполнив, и перемешать случайным образом. А случайное число выбирать позиционируя с помощью лимита, предварительно сгенерив случайное число на основе кол-ва записей.

Answer 4

[betal]

Если правильно понял задачу, нужно получить 1 случайную строку, из таблицы, где ид могут быть с дырками.
Навскидку LIMIT RAND($max),1

Comments

[betal]

В LIMIT вроде бы нельзя использовать RAND(),

//запрос макс количества записей в переменную
SELECT FLOOR(RAND() * COUNT(*)) AS `offset` FROM `table`
//далее запрос с этой переменной
SELECT * FROM `table` LIMIT $somevar, 1

Answer 5

[EugeneOZ]

Это будет работать быстро и не боится неконсистентных последовательностей ID
max = «SELECT COUNT(*) FROM `TABLE` (можно кэшировать)
$random_start = mt_rand(0, max-1);
result = SELECT * FROM `TABLE` LIMIT ».$random_start.",1

Comments

[Виталий Желтяков]

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

У автора и то более оптимальный вариант. Нашлись советчики.

[Евгений Шелег]

LIMIT перелопачивает все до него и выводит. Если таблица большая то это довольна большая нагрузка.
Если надо вывести не одно значение то нагрузка существенна.

[betal]

Спасибо, не знал, думал быстрее на порядок.

[EugeneOZ]

да? эх… было записано у меня в «блокноте». сорри, что написал фигню, удалить тут нельзя.
сам тоже не буду юзать, спасибо :)

Answer 6

[porohnya]

Хранить промежутки