Нарастающий итог в Денали

 

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

 

В качестве продолжения – сравнение производительности способов между собой.

 

 

 

Алексей Шуленин