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

Question

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

«Очевидный» ответ:

SELECT * FROM table ORDER BY RAND() LIMIT 10000

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

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

РЕДАКТИРОВАТЬ: 5 лет спустя

Я снова столкнулся с этой проблемой с таблицей большего размера и в итоге использовал версию решения @ ignorant с двумя изменениями:

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

Чтобы взять образец таблицы из 1000 элементов, я считаю строки и выбираю результат в среднем до 10 000 строк с помощью столбца 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

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

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

Answer 1

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

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

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

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

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

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

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

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

  выберите rand () из ограничения INFORMATION_SCHEMA.TABLES 10;

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

Answer 2

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

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

Три предположения, которые мы могли бы опробовать:

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

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

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

С учетом только предположений 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) &lt 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 3

Быстрее, чем заказ по RAND ()

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

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

Версия не 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 4

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

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

Answer 5

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

WHERE RAND() < 0.1 

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

WHERE RAND() < 0.01 

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

Answer 6

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

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

Answer 7

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

Вот решение O(max(n, m lg n)) -time, O(n) -pace, предполагающее просто простые ключи BTREE:

1. Выбрать все значения ключевого столбца таблицы данных в любом порядке в массив на вашем любимом языке сценариев в O(n)
2. Выполните перемешивание Фишера-Йейтса , остановив его после m перестановок, и извлеките подмассив [0:m-1] в ϴ(m)
3. "Соединить" подмассив с исходным набором данных (например, SELECT ... WHERE id IN (<subarray>)) в O(m lg n)

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

В псевдокоде Pythonic:

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])

Answer 8

Начиная с наблюдения, что мы можем получить идентификаторы таблицы (например, количество 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(']', ')');

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

Answer 9

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

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