Нарастающий итог в Денали
Начнем с практического примера. Вернее, продолжим. В предыдущем посте мы доставали из таблицы случайную запись. Чуть усложним задачу. Пусть записи выбираются не равномерно, а в соответствии с проставленными им весами. Например, если в таблице из двух записей первая запись имеет вес 2, а вторая - 3, это означает, что первая запись должна выбираться с вероятностью 2/5, а вторая - 3/5. То есть на каждые 5 попыток первая запись должна выпадать в среднем 2 раза, а вторая - 3. Добавим в таблицу Customers (см. Скрипт 1 предыдущего поста) колонку Weight:
use tempdb
if OBJECT_ID('dbo.Customer', 'U') is not null drop table dbo.Customer
create table dbo.Customer (CustomerID nchar(5) primary key, CompanyName nvarchar(40), Weight float)
insert dbo.Customer values ('ALFKI', 'Alfreds Futterkiste', 2), ('ANATR', 'Ana Trujillo Emparedados y helados', 1), ('ANTON', 'Antonio Moreno Taqueria', 3), ('AROUT', 'Around the Horn', 2), ('BERGS', 'Berglunds snabbkop', 2)
Скрипт 1
Совершенно очевидно, как выбирать из таблицы записи в соответствии с их вероятностями. Отнормируем проставленные веса на диапазон 0, 1:
update Customer set Weight = Weight / (select SUM(Weight) from Customer)
Скрипт 2
Разобьем диапазон от 0 до 1последовательно на интервалы длиной 0.2, 0.1, 0.3, 0.2, 0.2, т.е. на отрезки [0, 0.2), [0.2, 0.3), [0.3, 0.6), [0.6, 0.8), [0.8, 1.0). (*)
Бросаем в диапазон [0, 1) равномерно распределенный датчик случайных чисел. Если точка попала в первый отрезок, выбирается первая запись (ALFKI), во второй - вторая (ANATR) и т.д. Чтобы реализовать этот алгоритм, добавим в таблицу Сustomer поле Weight_RunningTotal
alter table Customer add Weight_RunningTotal float
Если в этом поле для каждой записи будет лежать левая граница соответствующего отрезка (*)
Скрипт 3
остается кинуть случайную точку и найти максимальную запись с левой границей, меньше этой точки
select top 1 * from Customer where Weight_RunningTotal <= RAND() order by Weight_RunningTotal desc
Скрипт 4
Все, что для этого нужно - заполнить колонку Weight_RunningTotal нарастающей суммой колонки Weight, т.е. в n-ю запись вставляется сумма весов n-1 предыдущих (в порядке ключевого поля CustomerID). Навскидку можно предложить 3 сравнительно честных способа решения.
Способ 1. С использованием курсора. Здесь все просто - ползем от записи к записи, по мере продвижения накапливая сумму в переменной @Weight_RunningTotal.
declare @cur cursor, @Weight float, @Weight_RunningTotal float = 0
set @cur = cursor local keyset for select Weight from Customer order by CustomerID for update of Weight_RunningTotal
open @cur
while 1 = 1 begin
fetch next from @cur into @Weight
if @@FETCH_STATUS <> 0 break
update Customer set Weight_RunningTotal = @Weight_RunningTotal where current of @cur
set @Weight_RunningTotal += @Weight
end
close @cur
deallocate @cur
select * from Customer
Скрипт 5
Способ 2. Я условно назову его sql-ex. На сайте SQL Exercises курсорами пользоваться нельзя. Там обожают упаковывать все в один запрос, с непринужденностью теоретиков жонглируя множествами. Сделаем треугольное произведение таблицы саму на себя:
select t2.CustomerID ID, t1.CustomerID ID_Preceding, t1.Weight from Customer t1 right join Customer t2 on t1.CustomerID < t2.CustomerID
Скрипт 6
В колонке ID содержится текущая запись, а в ID_Preceding - все, ей предшествующие. Сумма нарастающим итогом получается как сумма по группам ID:
select t2.CustomerID ID, sum(isnull(t1.Weight, 0)) s from Customer t1 right join Customer t2 on t1.CustomerID < t2.CustomerID group by t2.CustomerID
Cкрипт 7
Способ 3. В лоб. Что слышится - "в n-ю запись вставляется сумма весов n-1 предыдущих" - то и пишется:
select CustomerID, CompanyName, Weight, (select SUM(Weight) from Customer t2 where t2.CustomerID < t1.CustomerID) from Customer t1
Скрипт 8
Ни один из приведенных способов не свободен от недостатков. Курсор, по определению, медленный, перемножение - затраты растут как квадрат числа записей, тоже очевидные тормоза на больших объемах, вложенный подзапрос - аналогично. Идеальным был бы линейный способ, при котором таблица пробегается один раз а ля курсор, но без курсора. Что-нибудь вроде
declare @Weight_RunningTotal float = 0
update Customer set Weight_RunningTotal = @Weight_RunningTotal, @Weight_RunningTotal += Weight
select * from Customer
Скрипт 9
Как мы видим, невзирая на указанный в запросе порядок локальная переменная инкрементится раньше поля, поэтому нарастающий итог получается по, а не до текущей записи. Но это еще полбеды. Проблема в том, что мы вообще не можем гарантировать порядок, в котором записи будут перебираться в ходе выполнения запроса, и SQL Server тут не при чем, т.к. язык SQL оперирует с множествами, а классические множества неупорядочены. В данном случае нам повезло, и записи перебирались в нужном нам порядке, т.е. в соответствии с ключом CustomerID, но никто не гарантирует, что так будет всегда. Если в один прекрасный раз оптимизатору покажется лучше по каким-нибудь соображениям изменить порядок сканирования, Скр��пт 9 возвратит чушь. Ушлый народ пытался обеспечить порядок хинтами оптимизатору WITH(INDEX(1),TABLOCKX), OPTION (MAXDOP 1) и другими уловками, однако еще пару лет назад Ицик Бен-Ган в своей статье "Ordered UPDATE and Set-Based Solutions to Running Aggregates" в журнале SQL Server Magazine подверг их разбору и в результате пришел к неутешительному выводу - in SQL Server 2008 and earlier versions, I haven’t yet found a pure set-based technique for running totals that SQL Server’s optimizer handles very efficiently with large partition sizes. Наиболее надежным, он отметил, способом могла бы стать реализация порядка в оконных предикатах, прописанная, кстати, в стандарте SQL-2003. Imagine how great it would be if one day we’d be able to express a running total like this: … SUM(Weight) over (order by CustomerID).
Мне очень приятно сообщить, что этот день настал:
select CustomerID, CompanyName, Weight, SUM(Weight) over (order by CustomerID) from Customer
Скрипт 10
Сумма нарастающим итогом, не включая текущую запись:
select CustomerID, CompanyName, Weight, SUM(Weight) over (order by CustomerID rows between unbounded preceding and 1 preceding) from Customer
Скрипт 11
Подробности про новый синтаксис оконных функций можно прочитать в BOL.
Примечание. Фишка появилась в СТР3. СТР2 и ранние версии не воспринимают order by внутри sum(), count(), avg() и др., ругаясь на Incorrect syntax near 'order'.
В качестве продолжения – сравнение производительности способов между собой.
Алексей Шуленин