еще раз о случайной выборке или ORDER BY RAND()

[Klaus]

еще раз о случайной выборке или ORDER BY RAND()

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

Прежде всего хочется отметить, что такой запрос:
-------------------------------
SELECT *
FROM TABLE
ORDER BY RAND ()
LIMIT 1
-------------------------------
использовать НЕЛЬЗЯ!
Точнее можно, но только если записей мало или если Вы приветствуете тормоза Вашей системы.
И это при том, что это решение советуется во многих топиках, а также есть в мануале

Наиболее подходящее решение изложено в этом топике, но и оно далеко от идеала, т.к. правильно заметил Фанат , нет рандома если есть дырки.

Т.к. мне все же нужен рандом, то на данный момент я использую:
SELECT ID
FROM TABLE
ORDER BY RAND( )
LIMIT N
где ID - это PRIMARY с auto_increment, а потом уже идет выборка по этим ключам.
Но меня не устраивает общая скорость выборки в 1 сек, при моих 500к+ записей.

Вопрос: как, все же, получить номер записи, а не какой-нить auto_increment?
Т.е. допустим мы имеем 10 записей, но из-за многочисленного удаления и инсерта, мы имеем auto_increment номера - 13, 28, 548, 964 и т.д. Но если записей-то всего 10, то как получить седьмую запись или третью???
тогда бы уже со спокойной душой можно рандомить и брать по истиным номерам записей, а не по auto_increment.

 

[alexhemp]

Klaus

Какие-такие "истинные номера" в SQL-е?
Нет никаких номеров, порядок определяется исключительно заданным ORDER BY.

Решением может быть генерация своего случайного ID записи (как вы и хотите) а потом SELECT ... FROM table WHERE ID <= [случайный_id] LIMIT 1

но проверить результат тоже будет нелишне... Т.е. идея в том, что т.к. могут быть "дырки" в последовательности автоинкрементных id то возьмем ближайшее "слева" ;-)

 

[Wicked]

Для поиска одной записи:

1) выбираем $LEFT = MAX(id), $RIGHT = MIN(id), $CNT = COUNT() из таблицы.

2) генерим рандомный порядковый номер $N (из диапазона 0 .. $CNT) записи, которую нам нужно найти.

3) производим бинарный поиск N-й записи

точный алгоритм не помню (могут быть ошибки!), но идея такая:

while (bla-bla-bla) {
  //разбиваем отрезок пополам, смотрим, сколько записей попало в левую часть
  $N_CENTER = select count(*) from ... where id <= ($LEFT +   $RIGHT)/2;
  //если наша $N-тая запись попала в левую половину, то
  if ($N_CENTER > $N) {
    // сдвигаем правую границу на середину
    $RIGHT = ($LEFT + $RIGHT) / 2;
  //иначе
  } else {
    //сдвигаем левую
    $LEFT = ($LEFT + $RIGHT) / 2;
  }
}

требует около log2(MAX(id) - MIN(id)) довольно быстрых операций.

под bla-bla-bla подразумевается условие на $left и $right, которое позволит нам остановиться, когда мы будем близки к нужной записи

 

[Klaus]

alexhemp
пожалуйста, перечитайте мой пост, я же ясно выразился: при наличии дыр - рандомом в Вашем примере не пахнет.
Если Вам не понятно я опишу еще раз, допустим есть ID =1 остальные ID начинаются с 5999 и заканчиваются 6999
так вот при mt_rand(1,6999) и select полученного как часто будет выпадать ближайшее "слева" ID=1 ?????

Wicked
сорри, у Вас тож самое

 

[Wicked]

Originally posted by Klaus
Wicked
сорри, у Вас тож самое [/B]

То же самое = плохая работа при наличии дыр что ли?

 

[Klaus]

отсутствие рандома при наличии дыр

 

[Wicked]

ты попутал

 

[Klaus]

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

 

[Wicked]

1) Ну сначала мы рандомом выбираем порядковый номер записи, которую мы хотим искать. На этом этапе для любой записи вероятность быть выбранной = 1/COUNT(*).

2) Остается только найти id записи, соответствующей этому порядковому номеру. Это однозначная задача, которая на вероятностях уже никак не сказывается.
пусть будет такой набор номеров и id записей:
N id
1 10
2 700
3 701
4 702
5 1034

Пусть мы ищем запись #2.

На первой итерации мы смотрим, сколько записей с id < (10 + 1034) / 2. получаем ответ 1 < 2. Значит нижнюю границу двигаем с 10 до 522.

На второй итерации смотрим, сколько записей с id < (522 + 1034) / 2. получаем ответ 5. 5 > 2. Значит верхнюю границу двигаем с 1034 до 778.

На третей итерации смотрим, сколько записей с id < (522 + 778) / 2. получаем ответ 5. 1 < 2. Значит нижнюю границу двигаем с 522 до 650.

....

почти в самом конце получаем границы близкие к нашему второму элементу - 698 и 702 => 700 и 702 => 700 и 701 => 700 и 700.5

на этом поиск останавливается, т.к. (кол-во элементов <= 700) = 2 = (кол-во элементов <= 700.5)

значит наш пациент - это id = 700
итого проделано около 11 итераций.

 

[TuBu]

Klaus

Ну как вариант, выбирать все во временную таблицу, в которой сделать дополнительное авто_инрементное поле.

А потом выбирать из этой таблицы. Уж в ней-то дыр не будет.

 

[Klaus]

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

потестирую и этот вариант.

 

[alexhemp]

Klaus

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

Меня вполне устраивает такая конструкция:

SELECT ... MD5(RAND()) AS RANDOM .... ORDER BY RANDOM LIMIT 1;

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

Как вариант, если число записей огромно - таблицу можно сделать не временную, и генерировать ночью по CRON-у заново.

 

[Yurik]

Как можно оптимально получить не через ORDER BY RAND (для таблиц больше 30к он практически не подходит)
а) более 1 результата
б) 1 результат но с условиями WHERE
в) более 1 результата с условиями WHERE

Вопрос не как реализовать (способов много) а как оптимально, чтобы при больше 30к время было в пределах 0,1 сек