Books and articles about SQL Rambler's Top100 Сменить язык на: Русский 29 March 2024 01:10:13


www.sql-ex.ru
Skip Navigation Links  

 

Print  Версия для печати

На главную страницу

Случайная выборка строк из таблицы в SQL Server 2000

Моисеенко С.И.

В свое время я использовал случайную выборку записей для формирования списка вопросов теста. Делал я это на клиенте, используя функции базового языка, генерирующие псевдослучайное число в заданном диапазоне (например, функция RND в Visual Basic).

Однако оказалось, что достаточно просто это можно организовать и на сервере.

Одно из решений основывается на типе данных uniqueidentifier, который называется глобальным уникальным идентификатором и имеет вид:


xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx,


где каждое x является шестнадцатеричной цифрой в диапазоне 0-9 или a-f. Например, EEA8BF3A-7633-477A-B8C1-8C60DC9AD20C

Для решения нашей задачи важно то, что этот уникальный идентификатор может генерироваться автоматически при использовании функции NEWID. Просто напишите в QA (Query Analyzer)

SELECT NEWID()

(или SELECT TOP 1 NEWID() FROM PC на сайте)

и вы все увидите. Причем, выполняя этот запрос снова и снова, вы будете получать все время разные значения. На то он и "уникальный" этот идентификатор.

Так вот идея заключается в том, чтобы в запрос, возвращающий нужное число записей, добавить вычисляемый столбец NEWID, по которому должна выполняться сортировка. Поскольку генерируемые значения совершенно произвольны, то мы и получим произвольную выборку.

Итак, пусть нам нужно выбрать две произвольные любые модели из таблицы Product:

SELECT model FROM
(
SELECT TOP 2 model, NEWID() [id] FROM Product
ORDER BY [id]
) x

Выполним этот запрос несколько раз:
--1--
1232
1433
--2--
1276
1260
--3--
1750
1298

Кроме этого, в T-SQL имеется функция, генерирующая случайное число.Она называется RAND и генерирует псевдослучайное число с плавающей точкой в диапазоне от 0 до 1.

Термин "псевдослучайное" означает, что такое число вычисляется с помощью некоторого арифметического алгоритма. Т.е. при одинаковых начальных условиях (входных параметрах) получаемое число будет одним и тем же. Эти начальные условия могут быть заданы явно с помощью аргумента функции, которым может быть любое число типа tinyint, int или smallint, или неявно. В последнем случае аргумент опускается, в результате чего начальное значение будет выбрано SQL Server.

Попробуем выполнить следующий запрос:

SELECT TOP 1 RAND(), RAND(350) FROM Product

Выполним этот запрос в QA. У меня получилось: 0.0485421339242268 и 0.72009490018203537. Могу с уверенностью утверждать, что первое число у вас другое, однако второе должно быть тем же самым, т.к. во втором случае мы задали начальное значение (350). Правда, с одной оговоркой, если при этом еще не используются параметры конкретного компьютера, на котором выполняется запрос. Я не могу дать исчерпывающую информацию по использованию данной функции. Например, о том, будет ли распределение таким образом получаемой случайной величины равномерным.
В связи с чем, я прошу поделиться информацией тех, кто ей обладает, чтобы опубликовать ее на страницах данной рассылки.

Попробуем теперь применить функцию RAND для задачи, рассмотренной в предыдущей рассылке, а именно, для выдачи двух случайным образом выбранных моделей:

SELECT TOP 2 model FROM Product
ORDER BY RAND(model)

Получаем первые две модели в порядке возрастания их номеров. Вот где проявилась псевдослучайность. Посмотрим, что за случайные числа мы имеем:

SELECT model, RAND(model) FROM Product
ORDER BY RAND(model)

По причинам сокращения объема приведу их не все:

1001     0.73222496447112351
1002     0.73224359744238177
1003     0.73226223041363991
1004     0.73228086338489817
1005     0.73229949635615632
1006     0.73231812932741458
1007     0.73233676229867273

Я не знаю, какой алгоритм используется для вычисления случайного числа, однако могу утверждать, что функция RAND ведет себя монотонно в данном диапазоне номеров моделей. Потому у нас ничего и не получилось.

В BOL приводится пример генерации последовательности случайных чисел с использованием системного времени, чтобы динамически менять начальное значение. Вот он:

SELECT RAND( (DATEPART(mm, GETDATE()) * 100000 )
     + (DATEPART(ss, GETDATE()) * 1000 )
     + DATEPART(ms, GETDATE()) )

Однако в таком виде запрос может быть использован только в медленно выполняющихся пакетах, чтобы неоднократное выполнение запроса происходило в не чаще, чем минимальная единица времени, используемая в запросе (миллисекунды). Очевидно, что использование этой функции в выборке модели не будет отвечать этому условию. Однако, если умножить аргумент на некоторый уникальный для модели идентификатор, то мы можем добиться успеха, что, собственно, и было предложено VIG (номер модели уникален в таблице Product):

SELECT model, RAND(model*(DATEPART(mm, GETDATE()) * 100000 )
     + (DATEPART(ss, GETDATE()) * 1000 )
     + DATEPART(ms, GETDATE())) FROM Product
ORDER BY model

Сравните результаты:

1001     0.4278393574257387
1002     0.88102794651359417
1003     0.33421654885756019
1004     0.78740513794541567
1005     0.24059374028938171
1006     0.69378232984289845
1007     0.14697093172120321

При этом, как мне представляется, если данный запрос будет выполняться с небольшими интервалами времени, нужно увеличить вклад, вносимый миллисекундами. В противном случае, мы опять можем получать одни и те же модели. Итак:

SELECT TOP 2 model FROM Product
ORDER BY RAND(model*(DATEPART(ss, GETDATE()) * 1000
     + DATEPART(ms, GETDATE())))

Субъективный вывод таков: Для решения рассматриваемой задачи проще и надежней использовать функцию NEWID(), которая гарантирует уникальность значений. Однако эти значения не являются числовыми. Поэтому там, где нужно получить именно число, следует обратить внимание на функцию RAND().

Владимир Гершович (VIG) провел независимое расследование и любезно предоставил мне его результаты.
Суть его исследования состояла в том, чтобы выяснить насколько равномерными являются псевдослучайные последовательности, которые можно получить средствами SQL Server 2000.

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

Итак, нам потребуется таблица с большим числом строк, откуда мы будем псевдослучайно выбирать значения.
Следующий код создает таблицу из 10000 строк, при этом первый столбец - это номер строки, а второй содержит последовательность значений от 0 до 0.9999 с шагом 0.0001 в представлении с плавающей точкой:

DECLARE @t TABLE(id_val INT, val FLOAT)
INSERT @t
SELECT 1000*a.n+100*b.n+10*c.n+d.n ,(1000*a.n+100*b.n+10*c.n+d.n)/10000.0
FROM
(SELECT 0 n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4
UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) a,
(SELECT 0 n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4
UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) b,
(SELECT 0 n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4
UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) c,
(SELECT 0 n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4
UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) d

Понятие равномерного распределения на отрезке [0,1] соответствует представлению о случайном выборе точки на этом отрезке наудачу. Математическое ожидание и дисперсия равномерного распределения равны соответственно (1 + 0)/2 = 0.5 и (1 - 0)2/12 = 0.08333.
Итак, если мы случайным образом выберем последовательность значений из второго столбца и окажется, что их среднее значение равно 0.5, а дисперсия - 0.083333, то с большой долей вероятности можно утверждать, что наш метод дает равномерное распределение.

А вот кандидаты на исследование:

1. Использование функции NEWID()
2. Использование контрольной суммы от функции NEWID() - CHECKSUM(NEWID()). CHECKSUM используется для вычисления хеш-значения. За подробностями отсылаю к BOL и Гершовичу.
3. Использование функции RAND - RAND(ID_VAL * (1000 * DATEPART(mi,GETDATE()) + DATEPART(ms,GETDATE()))) ). Здесь в качестве начального значения для раскрутки псевдослучайной последовательности используются показания системных часов.

В теории вероятностей дисперсия равна квадрату стандартного отклонения (квадратичное отклонение!). В SQL Server имеется агрегатная функция, которая возвращает стандартное отклонение - STDEV, которая и позволит нам посчитать дисперсию. Наконец, проведем расчеты, выбирая 1000 значений из нашей таблицы и подсчитывая среднее значение и дисперсию:

SELECT AVG(val) Mean_NewID, POWER(STDEV(val),2) Disp_NewID
FROM
(SELECT TOP 1000 val
FROM @t t
ORDER BY NEWID()
) x

SELECT AVG(val) Mean_CheckSumNewID, POWER(STDEV(val),2) Disp_CheckSumNewID
FROM
(SELECT TOP 1000 val
FROM @t t
ORDER BY CHECKSUM(NEWID())
) x

SELECT AVG(val) Mean_Rand, POWER(STDEV(val),2) Disp_Rand
FROM
(SELECT TOP 1000 val
FROM @t t
ORDER BY RAND(id_val*(1000 * DATEPART(mi,GETDATE())+ DATEPART(ms,GETDATE())))
) x

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

1-й вариант 0.48206389999999955 8.4044806733524047E-2
2-й вариант 0.50844959999999972 8.0233888628468655E-2
3-й вариант 0.50142449999999994 8.3599687277026907E-2

Как видно, все варианты дают примерно одно и то же. Может показаться, что третий результат ближе к прогнозируемому. Однако если еще раз запустить запрос, то лучшим вполне может оказаться другой вариант. Чтобы выявить лидера, нужно еще накопить статистику. Однако главный вывод, как мне кажется, уже можно сделать: любой метод дает близкую к равномерной последовательность.

Приведенные здесь примеры можно выполнить непосредственно на сайте, установив флажок "Без проверки" на странице с упражнениями на SELECT.

На главную страницу

Print  Версия для печати


Usage of any materials of this site is possible
only under condition of mandatory allocation of the direct link to a site
http://www.sqlbooks.ru
on each page where used materials are placed.

 Main   Articles    Books 
Рейтинг@Mail.ru Rambler's Top100 Alt Упражнения по SQL: обучение, тестирование, сертификация по языку SQL Copyright c 2002-2006. All rights reserved.