Czepialski programista

refleksje przy programowaniu w .net i t-sql

Agregaty kroczące

Rozważmy następującą sytuację: mamy w bazie danych rekordy zużycia jakiegoś zasobu oraz pulę do wykorzystania.

Na przykład rozliczamy jeden okres rozliczeniowy abonenta telefonu, ma on w ofercie jakąś ilość darmowych minut w każdym cyklu, więc gdzieś w bazie, w danych bilingowych w kolejnych rekordach ilości minut poszczególnych rozmów wchodzących w skład cyklu rozliczeniowego.

Interesująca nas część rekordu może się składać z dwóch kolumn: (id, minuty), gdzie większa wartość pola id oznacza późniejszy rekord. Chcemy napisać procedurę składowaną czy też funkcję, która w wyniku da nam zestawienie darmowych minut wykorzystanych w kolejnych rekordach, co z kolei w realnym systemie przełoży się na prawdziwy koszt kolejnych rozmów. Poniżej przykładowy wynik. Jego postać jest uzależniona od ilości minut w puli, tutaj pokazano ją  dla puli zawierającej 200 darmowych minut:

Id Minuty Darmowe Płatne
1 17 17 0
2 19 19 0
3 16 16 0
4 12 12 0
5 28 28 0
6 30 30 0
7 9 9 0
8 4 4 0
9 19 19 0
10 25 25 0
11 17 17 0
12 6 4 2
13 18 0 18
14 13 0 13
15 8 0 8
16 14 0 14
17 21 0 21
18 16 0 16
19 7 0 7
20 22 0 22
21 24 0 24
22 18 0 18
23 21 0 21
24 29 0 29

Zdefiniujmy w T-SQL prostą tabelę,  i wstawmy do niej dane tych przykładowych 24 rekordów:

CREATE TABLE Rozmowy
(
  Id int identity(1,1),
  Minuty int
 )

 INSERT INTO Rozmowy
 VALUES (17),(19),(16),(12),(28),(30),(9),(4),(19),(25),(17),(6),(18),(13),(8),(14),(21),(16),(7),(22),(24),(18),(21),(29)

Pierwsze podejście do problemu jest naturalne dla programisty języka wyższego poziomu. Załatwiamy sprawę w pętli – przy pomocy kursorów. W funkcji, której parametrem będzie pula minut, rekord po rekordzie generujemy wynikowy zbiór danych.

Czyli:

CREATE FUNCTION ZestawienieMinut
(@pula int)
RETURNS @tabela TABLE (Id int, Minuty int, Darmowe int, Płatne int)
AS
BEGIN
 DECLARE @id int
 DECLARE @minuty int
 DECLARE @suma int = 0  -- suma częściowa
 DECLARE @darmowe int = 0 -- wynikowa ilość darmowych minut

 -- Kursor przechodzący całą tabelę z rozmowami wg id
 DECLARE kursor CURSOR LOCAL FORWARD_ONLY FOR
	SELECT id, minuty FROM Rozmowy ORDER BY id

 OPEN kursor
 FETCH NEXT FROM kursor INTO @id, @minuty

 -- dopóki mamy co czytać
 WHILE @@FETCH_STATUS = 0
	 BEGIN

		IF @suma > @pula
			SET @darmowe = 0 -- już przekroczyliśmy pulę
		ELSE
			IF @minuty <= @pula - @suma  -- w bieżącym rekordzie jej nie przekraczamy
                SET @darmowe = @minuty
			ELSE						 -- bądź przekraczamy
				SET @darmowe = @pula - @suma

		-- tworzymy rekord wynikowy
		INSERT INTO @tabela values(@id, @minuty, @darmowe, @minuty - @darmowe)

		-- uaktualniamy sumę
		SET @suma = @suma + @minuty

		-- czytamy następny rekord
		FETCH NEXT FROM kursor INTO @id, @minuty
	END
  -- sprzątamy
  CLOSE kursor
  DEALLOCATE kursor
  RETURN
END

Działa? Działa. Ale mądry znajomy powiedział nam, że kursory to ZUO i że zawsze (no, może poza nielicznymi wyjątkowymi sytuacjami) da się zamiast kursora zastosować łączenie tabel i osiągnąć ten sam wynik na ogół z dużo większą wydajnością. Więc – jak tutaj sobie poradzić? Jeśli mamy charyzmę na takim poziomie, żeby przekonać wszystkich, że to na pewno jedna z tych wyjątkowych sytuacji, nie musimy robić nic. Jednak w przeciwnym wypadku, trzeba przedstawić inne rozwiązanie. Będą nim running totals, co podobno (tak mówi nasz lokalny firmowy ekspert baz danych) tłumaczy się na agregaty kroczące, moim zdaniem ładnie brzmi, nawet trochę mniej pośpiesznie niż oryginał (czyżby w Polsce stosowano zasadę A gentleman will walk, but never run?); jeśli chodzi o to, co mówią słowniki – moje poszukiwania zakończyły się znalezieniem banalnych sum częściowych.

Zatem, będziemy korzystać z agregatów, grupowania, sumowania. W rozwiązaniu z kursorami korzystaliśmy ze zmiennej @suma przechowującej sumę dotychczasowych przetworzonych wartości w rekordach i od niej uzależnialiśmy to, czy jeszcze darmowe minuty są, czy już minęły, czy może została ich tylko część ze wszystkich minut bieżącego rekordu. To właśnie ona będzie naszym agregatem kroczącym. Będziemy chcieli dla każdego rekordu zapytania w podzapytaniu taką sumę policzyć. Spróbujmy: dołączmy do naszej danej tabeli tę samą tabelę, tak żeby do każdego rekordu była dołączona suma wartości poprzednich rekordów oraz wartości z bieżącego rekordu. (Czemu dodajemy bieżący? Wolę dodać do sumy poprzednich wartość bieżącą niż się zastanawiać, co będzie, jeśli ja jestem pierwszym rekordem i w związku z tym moich suma poprzednich jest równa NULL). Czyli warunek łączenia będzie miał postać:

LEFT JOIN Rozmowy Rozmowy2 ON Rozmowy2.id<=Rozmowy.id

Grupować będziemy po całej wartości rekordu, do którego dołączamy, w końcu chcemy, żeby występował on raz. Czy oprócz sumy będziemy czegoś potrzebować? Tak. Jakiejś możliwości uzależnienia naszej wartości wynikowej od tej sumy i całkowitej puli minut. Dokładniej chodzi o zapisanie takiego warunku:

wynik = {jeśli suma poprzednich rekordów i mnie jest mniejsza od puli  ->    minuty;

jeśli suma poprzednich rekordów (beze mnie) jest większa lub równa puli -> 0;

a w przypadku pośrednim – pula – suma poprzednich rekordów (beze mnie)}

W podejściu iteracyjnym nie mieliśmy problemu, zmienne tymczasowe i jedna zagnieżdżona instrukcja if załatwiły sprawę. Tutaj kolejne instrukcje muszą być zastąpione wywołaniem jednej funkcji, jednak, jak się okazuje samej funkcji nie musimy pisać. T-SQL dysponuje konstrukcją case, która robi dokładnie to, o co nam chodzi – uzależnia wartość pola od wartości wyrażeń boolowskich.
W naszym przypadku dla pierwszego z wyliczanych pól konstrukcja będzie wyglądać tak:

CASE
	WHEN SUM(Rozmowy2.minuty) <= @pula
		THEN Rozmowy.minuty
	WHEN SUM(rozmowy2.minuty) - Rozmowy.Minuty >= @pula
		THEN 0
	ELSE
		@pula - (SUM(rozmowy2.Minuty) - Rozmowy.Minuty)
END as Darmowe

Drugie pole będzie wyglądało podobnie, jeśli chodzi o warunki, natomiast wartości mają dopełniać się z pierwszym polem do minut w rekordzie. Dzięki temu cała nasza funkcja będzie wyglądała następująco:

CREATE FUNCTION ZestawienieMinutBezKursorów
(
	@pula int
)
RETURNS TABLE
AS
RETURN
(
	SELECT Rozmowy.id, Rozmowy.minuty
	,CASE
		WHEN SUM(Rozmowy2.minuty) <= @pula
			THEN Rozmowy.minuty
		WHEN SUM(Rozmowy2.minuty) - Rozmowy.Minuty >= @pula
			THEN 0
		ELSE
			@pula - (SUM(Rozmowy2.Minuty) - Rozmowy.Minuty)
	 END AS Darmowe
	,CASE
		WHEN SUM(Rozmowy2.minuty) <= @pula
			THEN 0
		WHEN SUM(Rozmowy2.minuty) - Rozmowy.Minuty >= @pula
			THEN Rozmowy.Minuty
		ELSE
			 SUM(Rozmowy2.Minuty) - @pula
	END AS Płatne
	FROM Rozmowy
	 LEFT JOIN Rozmowy Rozmowy2
		ON Rozmowy2.id<=Rozmowy.id
	GROUP BY Rozmowy.id, Rozmowy.minuty
 )

Jej działanie możemy sprawdzić, pisząc:

SELECT Id, Minuty, Darmowe, Płatne FROM dbo.ZestawienieMinutBezKursorów(200) ORDER BY ID

(ORDER BY jest konieczne przy wywołaniu tego typu funkcji, ze względu na to, że serwer nie gwarantuje w żaden sposób kolejności rekordów zwracanych przez funkcję).

Jak widać, przy niewielkim wysiłku intelektualnym udało nam się zastąpić skomplikowaną i mało wydajną formułę iteracyjną na jedno zwięzłe zapytanie.

Przykład został zainspirowany walką z bardzo podobnym zapytaniem w Systemie Planowania Urlopów i Nieobecności (SPUiN).

10.03 '12 - Posted by | Uncategorized | ,

1 komentarz »

  1. Agregaty kroczące « Czepialski programista…

    Thank you for submitting this cool story – Trackback from dotnetomaniak.pl…

    Trackback - autor: dotnetomaniak.pl | 12.03 '12 | Odpowiedz


Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google

Komentujesz korzystając z konta Google. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

Połączenie z %s

%d blogerów lubi to: