Простые случайные образцы из базы данных Sql

Question

Как я могу использовать эффективный простой случайный образец в SQL? В этой базе данных работает MySQL; моя таблица составляет не менее 200 000 строк, и я хочу, чтобы простая случайная выборка составляла около 10 000.

«очевидный» ответ заключается в следующем:

SELECT * FROM table ORDER BY RAND() LIMIT 10000 

Для больших таблиц, это слишком медленно: он вызывает RAND() для каждой строки (что уже ставит его в точке О (п)) и сортирует их , что делает его O (n lg n) в лучшем случае. Есть ли способ сделать это быстрее, чем O (n)?

Примечание: Как Эндрю Мао указывает в комментариях, если вы используете этот подход на SQL Server, вы должны использовать функцию NEWID T-SQL(), так как RAND() may return the same value for all rows.

EDIT: 5 ЛЕТ СПУСТЯ

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

• Sample Ряды до 2-5x мой желаемый размер выборки, дешево ORDER BY RAND()
• Сохраните результат RAND() в индексированном столбце при каждой вставке/обновлении. (Если ваш набор данных не очень тяжелый для обновления, вам может потребоваться найти другой способ сохранить этот столбец свежим.)

Чтобы взять образец из 1000 элементов таблицы, я подсчитываю строки и примеры результат вниз, в среднем, 10000 строк с колонки frozen_rand:

SELECT COUNT(*) FROM table; -- Use this to determine rand_low and rand_high 

    SELECT * 
    FROM table 
    WHERE frozen_rand BETWEEN %(rand_low)s AND %(rand_high)s 
ORDER BY RAND() LIMIT 1000 

(Моя фактическая реализация включает в себя больше работы, чтобы убедиться, что я не undersample и вручную завернуть rand_high вокруг, но основная идея «случайным образом сокращает ваш N до нескольких тысяч».)

Хотя это приносит некоторые жертвы, это позволяет мне делать оставьте базу данных вниз с помощью сканирования индекса, пока она не станет достаточно маленькой для ORDER BY RAND().

Answer 1

Там очень интересное обсуждение этого типа вопроса здесь: http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/

Я думаю, с абсолютно никаких предположений о таблице, что ваш O (п Л.Г. п) решение является лучшим. Хотя на самом деле с хорошим оптимизатором или немного другим методом список запросов может быть немного лучше, O (m * n), где m - количество требуемых случайных строк, так как не обязательно сортировать весь большой массив , он мог бы просто искать наименьшие m раз. Но для тех номеров, которые вы разместили, m больше, чем lg n.

Три asumptions мы могли бы попробовать:

1. есть уникальный, индексируется, первичный ключ в таблице

2. число случайных строк, которые вы хотите выбрать (м) значительно меньше, чем число строк в таблице (п)

3. уникальный первичный ключ является целым числом, которое находится в диапазоне от 1 до п без каких-либо зазоров

Только с предположениями 1 и 2 я думаю, что это можно сделать в O (n), хотя вам нужно будет написать целый индекс в таблицу для соответствия предположению 3, поэтому не обязательно быстрый O (n) , Если мы можем ДОПОЛНИТАТЬ что-то еще приятное в таблице, мы можем выполнить задачу в O (m log m). Успение 3 было бы легким приятным дополнительным свойством для работы. С хорошим генератором случайных чисел, который не гарантировал дублирования при генерации m чисел в строке, возможно решение O (m).

Учитывая три предположения, основная идея состоит в том, чтобы сгенерировать m уникальных случайных чисел между 1 и n, а затем выбрать строки с этими ключами из таблицы. У меня нет MySQL или что-нибудь передо мной прямо сейчас, так и в слегка псевдокоде это будет выглядеть примерно так:

create table RandomKeys (RandomKey int) 
create table RandomKeysAttempt (RandomKey int) 

-- generate m random keys between 1 and n 
for i = 1 to m 
    insert RandomKeysAttempt select rand()*n + 1 

-- eliminate duplicates 
insert RandomKeys select distinct RandomKey from RandomKeysAttempt 

-- as long as we don't have enough, keep generating new keys, 
-- with luck (and m much less than n), this won't be necessary 
while count(RandomKeys) < m 
    NextAttempt = rand()*n + 1 
    if not exists (select * from RandomKeys where RandomKey = NextAttempt) 
    insert RandomKeys select NextAttempt 

-- get our random rows 
select * 
from RandomKeys r 
join table t ON r.RandomKey = t.UniqueKey 

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

Answer 2

Может быть, вы могли бы сделать

SELECT * FROM table LIMIT 10000 OFFSET FLOOR(RAND() * 190000) 

Answer 3

Просто используйте

WHERE RAND() < 0.1 

, чтобы получить 10% записей или

WHERE RAND() < 0.01 

, чтобы получить 1% записей и т.д.

Answer 4

Я думаю, что самым быстрым решением является

select * from table where rand() <= .3 

Вот почему я думаю, что t он должен выполнять эту работу.

• Это создаст случайное число для каждой строки. Число от 0 до 1
• Он оценивает, отображать ли эту строку, если число сгенерировано между 0 и .3 (30%).

Это предполагает, что rand() генерирует числа в равномерном распределении. Это самый быстрый способ сделать это.

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

• Это O (N), но нет сортировки не требуется, так что быстрее, чем O (n lg n)

• mysql очень способен генерировать случайные числа для каждой строки.Попробуйте это -

  выберите rand() из INFORMATION_SCHEMA.TABLES limit 10;

Поскольку эта база данных является mySQL, это правильное решение.

Answer 5

Начиная с наблюдением, что мы можем получить идентификаторы таблицы на основе набора (например, кол-5.):

select * 
from table_name 
where _id in (4, 1, 2, 5, 3) 

мы можем прийти к тому, что если бы мы могли генерировать строку "(4, 1, 2, 5, 3)", то у нас был бы более эффективный способ, чем RAND().

Например, в Java:

ArrayList<Integer> indices = new ArrayList<Integer>(rowsCount); 
for (int i = 0; i < rowsCount; i++) { 
    indices.add(i); 
} 
Collections.shuffle(indices); 
String inClause = indices.toString().replace('[', '(').replace(']', ')'); 

Если иды есть пробелы, то начальный ArrayList indices является результатом SQL запроса на ид.

Answer 6

По-видимому, в некоторых версиях SQL есть команда TABLESAMPLE, но это не во всех реализациях SQL (в частности, в Redshift).

http://technet.microsoft.com/en-us/library/ms189108(v=sql.105).aspx

Answer 7

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

Если вы хотите, чтобы ваш образец был независимым, вам нужно будет сменить образец. См. Question 25451034 для примера того, как это сделать с помощью JOIN способом, подобным решению пользователя12861. Решение написано для T-SQL, но концепция работает в любом SQL db.

Answer 8

быстрее, чем ORDER BY RAND()

Я проверил этот метод намного быстрее, чем ORDER BY RAND(), следовательно, он работает в O (п) времени, и делает это впечатляюще быстро.

От http://technet.microsoft.com/en-us/library/ms189108%28v=sql.105%29.aspx:

Non-MSSQL версия - Я не проверял эту версию

SELECT * FROM Sales.SalesOrderDetail 
WHERE 0.01 >= RAND() 

MSSQL:

SELECT * FROM Sales.SalesOrderDetail 
WHERE 0.01 >= CAST(CHECKSUM(NEWID(), SalesOrderID) & 0x7fffffff AS float)/CAST (0x7fffffff AS int) 

Это отберет ~ 1% записей. Поэтому, если вам нужно точное количество процентов или записей, которые нужно выбрать, оцените свой процент с некоторым запасом прочности, а затем произвольно вырвите лишние записи из результирующего набора, используя более дорогой метод ORDER BY RAND().

даже быстрее

я был в состоянии улучшить этот метод еще больше, потому что был хорошо известным индексированным диапазон значений столбца.

Например, если у вас есть индексированный столбец с равномерно распределенными целыми числами [0..max], вы можете использовать его для случайного выбора N небольших интервалов.Сделайте это динамически в своей программе, чтобы получить другой набор для каждого запуска запроса. Этот выбор подмножества будет O (N), который может на много порядков меньше вашего полного набора данных.

В моем тесте я уменьшил время, необходимое, чтобы получить 20 (из 20 млн) выборки записей из 3 минут с помощью ORDER BY RAND() до 0,0 секунды!

Answer 9

Если вам нужны ровно m строк, реалистично вы создадите подмножество идентификаторов вне SQL. В большинстве случаев в какой-то момент требуется выбрать запись «nth», а таблицы SQL на самом деле не являются массивами. Предположение о том, что ключи являются последовательными, чтобы просто присоединиться к случайным ints между 1 и счетом, также трудно удовлетворить. — MySQL, например, не поддерживает его изначально, а условия блокировки ... tricky.

Вот O(max(n, m lg n)) -время, O(n) решения -пространства предполагая только простой ВТКЕЙ ключи:

1. Fetch всех значения ключевого столбца таблицы данных в любом порядке в массив в вашем любимом языке сценариев в O(n)
2. Выполните Fisher-Yates shuffle, останавливая после m свопов, и извлечь подмассив [0:m-1] в ϴ(m)
3. «Регистрация» подмассив с исходным набором данными (например, SELECT ... WHERE id IN (<subarray>)) in O(m lg n)

Любой метод, который генерирует случайное подмножество вне SQL, должен иметь по крайней мере такую ​​сложность. Соединение не может быть быстрее, чем O(m lg n) с BTREE (так что O(m) утверждает, что это фантазия для большинства двигателей), и тасовка ограничена ниже n и m lg n и не влияет на асимптотическое поведение.

В вещий псевдокоде:

ids = sql.query('SELECT id FROM t') 
for i in range(m): 
    r = int(random() * (len(ids) - i)) 
    ids[i], ids[i + r] = ids[i + r], ids[i] 

results = sql.query('SELECT * FROM t WHERE id IN (%s)' % ', '.join(ids[0:m-1])