Случайная выборка mysql

[rushter]

Кто-нибудь знает как можно оптимизировать получение случайных записей в mysql ?

SELECT * FROM `ai` ORDER BY RAND() LIMIT 0,10;

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

[t0os]

http://www.titov.net/2005/09/21/do-n...ws-from-table/

[rushter]

Забыл дополнить, данные постоянно добавляются и удаляются.
Соответственно индексы всегда разные и с разрывами, получать их все займёт столько же времени. Кэшировать их тоже не вариант, часто меняются.
А так бы я и сам додумался id генерировать

[Revolver]

Сообщение от dveredel

Мда, конечно советовать Сфинкс для решения классической задачи "оптимизация рандомной выборки из огромной таблицы по айди", это либо непонимание задачи, либо сфинкса )

Ну конечно, если вопрос стоит задачу решить, то ее можно решить, не используя spihnx. А если нужна производительность, я другой альтернативы не вижу.

[chesser]

Сообщение от rushter

Забыл дополнить, данные постоянно добавляются и удаляются.
Соответственно индексы всегда разные и с разрывами, получать их все займёт столько же времени. Кэшировать их тоже не вариант, часто меняются.
А так бы я и сам додумался id генерировать

так ты попробуй моими способами, даже несколько запросов с целью угадать рандом индекс - все равно будет быстрее, чем order by rand(). Либо нагенери 100 ранд чисел и запрашивай where id in (тут числа через запятую). У таких запросов сложность O(N), у order by rand() примерно O(log N), а у хеш-индексов O(1) я вообще их использую повсеместно....да и половина технологий хайлоада базируется на этом

а кешировать нужно только мин. и макс. индексы - это один предварительный запрос.

А если нужна скорость, то переходи в память, там все летать будет ну и функционал хеш-индексов получишь

[TerVer]

по айди, если с разрывами не очень рандомно будет (не равновероятно).
Остается. Содать поле `rnd` для записей. При инсерте ... `rnd`=RAND()*10000000
при выборке три запроса.
SELECT MIN(`rnd`)
SELECT MAX(`rnd`)
$myrnd=mt_rand($min-1,$max+1); // PHP
SELECT WHERE `rnd`>'$myrnd' LIMIT 1

как вариант

ЗЫ нидекс по `rnd` само собой

[TerVer]

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

SELECT... WHERE `rnd`>(RAND()*10000000) LIMIT 1

[chesser]

TerVer, согласен на счет равновероятности, поэтому я "слежу" за своим индексом.

Твой вариант будет более требовательный к памяти, местами даже очень, т.к. ты выбираешь диапазон (знак >) и если rand() будет 1, то в выборку попадут все 15кк записей - ваще не торт. Но этот способ лучше ORDER BY rand() тем, что не нужно выбранные записи сортировать по виртуальному полю(наверно даже без индекса) - это да, плюс, т.к. сортировка очень много затратная. Но памяти все равно будет выжираться много. Я его пробовал, меня не устроило.

[TerVer]

а как такой вариант
SELECT COUNT()
mt_rand(1,$count)
SELECT * FROM `keys8_` ORDER BY `rnd` LIMIT $rnd,1

COUNT будет время съедать? его можно не все время пересчитывать.

[chesser]

Сообщение от TerVer

а как такой вариант
SELECT COUNT()
mt_rand(1,$count)
SELECT * FROM `keys8_` ORDER BY `rnd` LIMIT $rnd,1

COUNT будет время съедать? его можно не все время пересчитывать.

да похер на count - у него сложность максимум O(N), но скорее всего O(1), т.к. метаданные о таблице логичнее хранить в системных полях, а не считать каждый раз.

Тут две проблемы:

1) ORDER BY - это тяжелая операция у которой сложность в районе O(n*log n), в зависимости от алго и наличия индексов. Вообще, сортировкой не надо пользоваться, если нужна скорость.
2) LIMIT $rnd,1 - это будет жрать память, т.к. нет WHERE

[xatman]

Oracle