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

93

Как мне взять эффективную простую случайную выборку в 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().

оджрак
источник
3
Это даже не работает на SQL-сервере, потому RAND()что каждый последующий вызов возвращает одно и то же значение.
Эндрю Мао,
1
Хороший момент - я добавлю замечание, что пользователям SQL Server следует вместо этого использовать ORDER BY NEWID ().
ojrac
Он по-прежнему ужасно неэффективен, потому что должен сортировать все данные. Техника случайной выборки для некоторого процента лучше, но я даже после прочтения кучи сообщений здесь не нашел приемлемого решения, которое было бы достаточно случайным.
Эндрю Мао
Если вы читаете вопрос, я спрашиваю конкретно, потому что ORDER BY RAND () - это O (n lg n).
ojrac
Ответ muposat ниже хорош, если вы не слишком одержимы статистической случайностью RAND ().
Джош Грейфер

Ответы:

25

Здесь есть очень интересное обсуждение этого типа проблем: 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. количество случайных строк, которые вы хотите выбрать (m), намного меньше, чем количество строк в таблице (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) < 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, вероятно, будет лучше для требуемого типа циклов и генерации случайных чисел. .

user12861
источник
Я бы рекомендовал добавить уникальный индекс для случайного выбора ключа и, возможно, игнорировать дубликаты на вставке, тогда вы можете избавиться от отдельных вещей, и соединение будет быстрее.
Сэм Саффрон,
Я думаю, что алгоритм случайных чисел может использовать некоторые настройки - либо ограничение UNIQUE, как упомянуто, либо просто сгенерировать числа 2 * m и SELECT DISTINCT, ORDER BY id (first-come-first-serve, поэтому это сводится к ограничению UNIQUE ) LIMIT m. Мне это нравится.
ojrac
Что касается добавления уникального индекса к случайному выбору ключа, а затем игнорирования дубликатов при вставке, я подумал, что это может вернуть вас к поведению O (m ^ 2) вместо O (m lg m) для сортировки. Не уверен, насколько эффективно сервер поддерживает индекс при вставке случайных строк по одной.
user12861
Что касается предложений по генерации чисел 2 * m или чего-то еще, я хотел, чтобы алгоритм гарантированно работал, несмотря ни на что. Всегда есть (небольшая) вероятность, что ваши случайные числа размером 2 * m будут иметь более m дубликатов, поэтому вам будет недостаточно для вашего запроса.
user12861
1
Как узнать количество строк в таблице?
Awesome-o
54

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

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

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

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

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

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

  • Это O (n), но сортировка не требуется, поэтому она быстрее, чем O (n lg n)
  • mysql очень способен генерировать случайные числа для каждой строки. Попробуй это -

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

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

невежественный
источник
1
Во-первых, у вас есть проблема в том, что это на самом деле не отвечает на вопрос, поскольку возвращает полуслучайное количество результатов, близкое к желаемому, но не обязательно точно это число, вместо точного желаемого количества результатов.
user12861 07
1
Далее, что касается эффективности, у вас O (n), где n - количество строк в таблице. Это не так хорошо, как O (m log m), где m - количество желаемых результатов, а m << n. Вы все еще можете быть правы, что на практике это будет быстрее, потому что, как вы говорите, генерация rand () и их сравнение с константой МОЖЕТ быть очень быстрой. Вам придется протестировать это, чтобы узнать. За меньшими столами вы можете выиграть. С огромными таблицами и гораздо меньшим количеством желаемых результатов я в этом сомневаюсь.
user12861 07
1
Хотя @ user12861 прав в том, что не получает точное число, это хороший способ сократить набор данных до нужного приблизительного размера.
ojrac
1
Как база данных обслуживает следующий запрос - SELECT * FROM table ORDER BY RAND() LIMIT 10000 ? Сначала он должен создать случайное число для каждой строки (как в описанном мной решении), а затем заказать его ... сортировка дорогая! Вот почему это решение БУДЕТ медленнее, чем описанное мною, поскольку сортировка не требуется. Вы можете добавить ограничение к описанному мной решению, и оно не даст вам больше, чем это количество строк. Как кто-то правильно заметил, он не даст вам ТОЧНОГО размера выборки, но со случайными выборками ТОЧНОСТЬ чаще всего не является строгим требованием.
невежественный
Есть ли способ указать минимальное количество строк?
CMCDragonkai
5

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

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

Gatoatigrado
источник
Очень круто! Похоже, что это не реализовано ни в PostgreSQL, ни в MySQL / MariaDB, но это отличный ответ, если вы используете реализацию SQL, которая его поддерживает.
ojrac
Я понимаю, что TABLESAMPLEэто не случайность в статистическом смысле.
Шон
4

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

WHERE RAND() < 0.1 

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

WHERE RAND() < 0.01 

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

Дэвид Ф. Майер
источник
1
Это вызовет RAND для каждой строки, что сделает его O (n). Плакат искал чего-то лучшего.
user12861
1
Не только это, но и RAND()возвращает одно и то же значение для последующих вызовов (по крайней мере, на MSSQL), что означает, что с такой вероятностью вы получите либо всю таблицу, либо ни одну из них.
Эндрю Мао
4

Быстрее, чем ORDER BY 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 секунды !

Muposat
источник
1

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

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

gazzman
источник
0

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

Кит-Кат
источник
0

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

Вот решение O(max(n, m lg n))-time, -space, O(n)предполагающее только простые ключи 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])
concat
источник
0

Выберите 3000 случайных записей в Netezza:

WITH IDS AS (
     SELECT ID
     FROM MYTABLE;
)

SELECT ID FROM IDS ORDER BY mt_random() LIMIT 3000
Одиссей Итака
источник
Я не думаю, что это отвечает на вопрос о том, как запросить случайную выборку строк без ORDER BY rand () LIMIT $ 1, кроме добавления некоторых примечаний, связанных с диалектом SQL.
ojrac
0

Пытаться

SELECT TOP 10000 * FROM table ORDER BY NEWID()

Дало бы это желаемые результаты, не будучи слишком сложным?

Northernlad
источник
Обратите внимание, что NEWID()это характерно для T-SQL.
Петр О.
Мои извенения. Это. Спасибо. Однако полезно знать, приходит ли сюда кто-нибудь, выглядящий так же, как я, и использует ли он T-SQL
Northernlad,
ORDER BY NEWID()Функционально такой же, как ORDER BY RAND()- он вызывает RAND()каждую строку в наборе - O (n) - а затем сортирует все - O (n lg n). Другими словами, это наихудший вариант решения, которое этот вопрос пытается улучшить.
ojrac
0

В некоторых диалектах, таких как Microsoft SQL Server, PostgreSQL и Oracle (но не в MySQL или SQLite), вы можете сделать что-то вроде

select distinct top 10000 customer_id from nielsen.dbo.customer TABLESAMPLE (20000 rows) REPEATABLE (123);

Причина, по которой нельзя просто (10000 rows)обойтись без него, topзаключается в том, что TABLESAMPLEлогика дает вам крайне неточное количество строк (например, иногда 75% больше, иногда 1,25% больше), поэтому вы хотите увеличить выборку и выбрать точное количество, которое хотите. Предназначен REPEATABLE (123)для предоставления случайного начального числа.

Жанвен Чен
источник
-4

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

SELECT * FROM table LIMIT 10000 OFFSET FLOOR(RAND() * 190000)
статический
источник
1
Похоже, это выберет случайный фрагмент моих данных; Я ищу что-то посложнее - 10 000 случайно распределенных строк.
ojrac
Тогда ваш единственный вариант, если вы хотите сделать это в базе данных, - ORDER BY rand ().
staticsan