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

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