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

Question

[Сергей Савостин]

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

SELECT id, name, param1, param2 
FROM table 
WHERE param1 = some_value 
AND param2 > another_one 
ORDER BY RANDOM() 
LIMIT @N

MySQL, да и, наверное, другие популярные базы, от такого запроса умирают, естественно.
Всякие обходные костыли, типа дополнительное поле с рандомом, перемешивать по крону, составлять запросы на лету и процедуры и пр. не совсем подходят - нужно действительно при каждом запросе отдавать рандомные строки, N > 10000, id с дырами, объемы большие. Может быть есть что-то специализированное? Не обязательно SQL. Может даже сервис, хоть и не желательно.

Comments

[zvorygin]

А сколько всего записей в базе, и сколько хочется выбирать за раз?

[Сергей Савостин]

Записей точно больше 5 млн. Выбирать сколько закажет пользователь, ожидается 10000+

[Ilyas Masirov]

В статье Худсона очень хорошо описана оптимизация случайной выборки :)

[Сергей Савостин]

IlyasMasirov, ссылка на эту статью у меня в вопросе. К сожалению для N > 10000 не подходит.

[zvorygin]

А какой размер в байтах одной записи?

[Сергей Савостин]

zvorygin, до 1 кб

[zvorygin]

А данные буду часто модифицироваться? Удаляться/обновляться. Много ли будет параллельных запросов? Какое приемлемое время отклика ожидается?

[Сергей Савостин]

Обновляться почти не будут (справочник).
Запросов достаточно много (веб-сервис), особенно с учетом длительности запроса.
Ну, 2 секунды (если применять ORDER BY RAND в MySQL) уже мучительно много, мне кажется.

[zvorygin]

А в MySQL успевает за 2 секунды без фильтров перелопатить 5Гб базу на 5Млн записей? Разве только если вся база в память влезает....

[zvorygin]

Если можно все хранить в памяти, тогда намного проще, мне кажется...

Answer 1

[Kerman]

Если нужен именно честный выбор действительно случайных и равномерно распределённых 10000 строк из пятимиллионной таблицы, то лучше SQL с этой задачей ничто не справится. Разве что самописная база, заточенная конкретно под этот случай. Нужно просто расставить индексы на нужные поля, чтобы облегчить поиск.
Мой совет: добавьте памяти на сервер, проиндексируйте поля. Всё будет хорошо, используйте стандарный RAND(), оптимизировав его до приемлемого значения.

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

Answer 2

[TomaZ Vazovsky]

А почему нельзя просто сначала сделать выборку (отфильтровать по условию), а потом из нее, выбрать сколько нужно случайных по порядку записей?

Может быть еще вот эта статья будет полезна akinas.com/pages/en/blog/mysql_random_row

Comments

[Сергей Савостин]

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

[Сергей Савостин]

Для одной записи еще более-менее, мне же нужно 10000+

Answer 3

[egor_nullptr]

Смотрите в сторону MongoDB и MapReduce.

Comments

[Сергей Савостин]

Так вроде бы в MongoDB этот feature request тянется еще с 2010 года и "planned but not scheduled": https://jira.mongodb.org/browse/SERVER-533

[Сергей Савостин]

И в MapReduce, если не врет Google, такие же костыли - делать счетчик при обходе...

[TomaZ Vazovsky]

К слову о MapReduce, насколько я знаю, в рамках монги единовременно может выполняться только один MapReduce.
А вообще чем поможет монга? Да она быстрей отдает данные по ключу (потому что держит индекс в озу), но "нативного рандомизирования" нет и там. Может как-нибудь упросить задачу ее курсор, но у SQL тоже есть курсоры, если мне не изменяет память.

Answer 4

[zvorygin]

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

Причем выборка будет максимально честной. А вообще - можно взять на вооружение как интересную задачку для интервью)

Comments

[Сергей Савостин]

Приложение/сервис и пишется. Вопрос где хранить столько данных и как их доставать. Если бы не фильтрация, можно было бы в бинарном файле с фиксированной длиной записи. Но фильтрование подразумевает перебор всех записей. Сомневаюсь, что у меня получится сделать велосипед лучше, чем у Oracle ;(

[zvorygin]

@savostin, так а в памяти можно все хранить?

[Сергей Савостин]

сильно сомневаюсь. так бы никаких проблем не было ;)

Answer 5

[zvorygin]

Тогда, если учесть, что запросы могут быть какими угодно, вам надо будет на каждый запрос читать всю таблицу хотя бы для того чтобы отфильтровать(хоть самописное у вас, хоть oracle, хоть mysql) - т.е. читать 5Гб (это самый медленный момент во всей системе). Если взять скорость последовательного чтения(а случайное чтени + SSD вам не помогут, как мне кажется), то время чтения будет порядка 5Гб/150МБс т.е. около 30 секунд. Если предположить что записи меняются редко, то можно все это дело дополнительно сжать(зависит от реальных данных) - хранить записи не фиксированной длины - возможно еще процентов 15(или больше) экономии выжмется - итого 25 секунд. Можно применить RAID и ускорить еще в пару раз(или в большее - в зависимости от реализации) - итого получаем 15 секунд на запрос. Никакие стандартные кеши при последовательном чтении не помогут, но можно попробовать просто забить всю свободную память кусками данных - и к ним обращаться не с диска - это дает еще 2Гб в памяти и, на вскидку экономию в 30-40 процентов. Итого, мне кажется, 10 секунд - довольно хороший гарантированный и достижимый результат на почти любых фильтрах и запросах. Если есть заранее известные данные о фильтрации, то можно пробовать как-то по-другому оптимизировать.

Comments

[Сергей Савостин]

ну, при наличии индексов, MySQL и др. базы как-то справляются с поиском по таким таблицам. Вот я и говорю, что самому написать такое вряд ли удастся.

[zvorygin]

@savostin индексы, как я понимаю, не помогут с запросами вида where field1 > field2, если только не строить специальный bitset индекс

Answer 6

[Aisu]

Я не знаю как это сделать в MySQL однако решала такую задачу в sql server . Так вот идея такая - добавляется дополнительное поле в запрос в котором вычисляется функция уникального номера, а в ордере указывается это поле, несмотря на ваши условия выборки. Далее выставите top 10000. Вот и все. Правда не знаю насколько он быстро выполниться, хотя думаю 10000 строк это не много для запроса в SQL Server...
Пример
SELECT TOP 10000 [StudentKID]
,[SKPersRecN]
,[SKSurname]
,[SKName]
,[SKSecondName]
,[FacultyID], NewId() as t
FROM [StudentsKredit]
where FacultyID='ИУБ'
order by t

Comments

[Сергей Савостин]

Это и есть order by rand. К сожалению при этом функция вызывается для каждой записи, а затем лимитируется количество строк (т.к. order ыфполняется раньше limit). Поэтому при любом limit функция будет выполнена для всех записей, а их 5+ млн.