SELECT Explanation, Example FROM Pro.Knowledge
FacebookRSS

Wyszukiwanie ciągłych zakresów, dziur, problemy wysp w SQL

Weryfikacja ciągłości zakresu, identyfikacja dziur oraz scalanie przedziałów, przydaje się do rozwiązywania różnych zadań. W systemach transakcyjnych, szczególnie mocno obciążonych przez wielu użytkowników, mogą wystąpić sytuacje gdy funkcja IDENTITY nie zapewnia bezwzględnej ciągłości identyfikatorów. Dotyczy to również obiektów wprowadzonych w SQL Server 2012, znanych już od dawna w Oracle – sekwencji.

Artykuł ten, nie będzie jednak o bezpiecznym nadawaniu kolejnych, ciągłych identyfikatorów (polecam triggery INSTEAD OF INSERT). Zaprezentuję tu kilka wskazówek i praktycznych przykładów jak wykrywać nieciągłości, identyfikować dziury oraz scalać zakresy.

Niezwykle pomocne okazują się tutaj funkcje szeregujące bazujące na funkcji okna OVER() oraz wspólne wyrażenia tablicowe.


Wykrywanie nieciągłości w zbiorze

Na początek coś bardzo prostego. Trochę podstaw, bez których trudno jest rozwiązywać bardziej skomplikowane przykłady.

Załóżmy, że mamy zbiór elementów ponumerowanych w zakresie od 1-1000, inkrementowanych co 1. Każdy ciągły, jednostajnie rosnący zbiór wartości, powinien zwrócić ten sam wynik dla takiego wyrażenia:

Wartość_elementu  – ( Inkrementacja * Nr_elementu_w_szeregu ) = Const.


Wykorzystując funkcję ROW_NUMBER() i powyższą zasadę, sprawdźmy ciągłość dla poniższego zbioru:

Use tempdb
GO
 
set nocount on 
go
 
IF ( OBJECT_ID('dbo.zakres') is not null)  
drop table dbo.zakres;
 
create table dbo.zakres
( 
	Vlan int
);
 
DECLARE @zmienna int = 1
 
WHILE (@zmienna<=1000)
BEGIN
	insert into  dbo.zakres values (@zmienna)
	set @zmienna = @zmienna + 1
END;
 
-- kwerenda sprawdzająca
with CheckCont as (
	-- dla inkrementowanego o 1
	select distinct T1.VLAN  - (1*(ROW_NUMBER() OVER (ORDER BY  VLAN))) as Diff
	from dbo.zakres t1
)
Select CASE WHEN Count(Diff)> 1 then 'Discontinuous' else 'Continuous' end as Result
from CheckCont

Zakresy_ciagle_01

Jak widać bez niespodzianek – jest ok. Skasujemy teraz kilka losowych rekordów i ponowie zweryfikujemy ciągłość elementów, tą samą kwerendą sprawdzającą.

DELETE FROM dbo.zakres
WHERE VLAN IN (
SELECT TOP 3 VLAN from dbo.zakres ORDER BY NEWID() 
)

Zakresy_ciagle_02


Scalanie zakresów

Scenariusz, z którym ostatnio się spotkałem to scalanie zakresów VLAN w konfiguracji interfejsów urządzeń sieciowych (routerów). Informacje o VLANach są przechowywane w tabeli, w której każdy rekord, odpowiada pojedynczemu VLANowi, przypisanemu do danego portu, określonego urządzenia. To co trzeba wykonać, to agregacja (sklejenie zakresów) do skrótowej postaci przyjaznej dla użytkownika.

Wygenerujmy sobie prostą tabelę, z nieciągłą numeracją w kolumnie VLAN :

IF ( OBJECT_ID('dbo.zakres') is not null)  drop table dbo.zakres;
create table dbo.zakres
( 
	Vlan int
);
 
DECLARE @zmienna int = 1, @los int =0, @cnt int =1
 
WHILE (@cnt<=10)
BEGIN
 
	SET @los = case when   CONVERT(INT, (11) * RAND()) > 8  then 1 else 0 end
 
	insert into dbo.zakres values (@zmienna + @los)
	SELECT @zmienna = @zmienna +1+ @los, @cnt +=1
END;
 
select * from dbo.zakres

Zakresy_ciagle_03

Zadaniem jest wykrycie i scalenie zakresów rekordów o ciągłej numeracji. Stosując się do reguły ciągłości, którą pokazałem w poprzednim przykładzie, sprawdźmy rezultat tej formułki dla kolejnych wierszy. Widać, że wynik może posłużyć jako bezwzględny identyfikator określonego, ciągłego zakresu. W naszym przypadku mamy 4 zakresy, w tym dwa wieloelementowe.

Zakresy_ciagle_04

Kluczowym znów będzie numerowanie rekordów i późniejsze ich grupowanie względem wyliczonego w ten sposób identyfikatora zakresu. Dwa podejścia – stare, sprzed SQL Server 2005 z zapytaniem skorelowanym :

with PoNumerowane as
(
	select VLAN ,  
           (select count(*) from dbo.zakres t2 where t2.VLAN  <= t1.VLAN )  as IdRek
	from dbo.zakres t1
)
select VLAN - IdRek as ZakresID, MIN(VLAN) as VLAN_START, MAX(VLAN) as VLAN_END
from PoNumerowane
group by VLAN - IdRek

Oraz lepsze, zdecydowanie bardziej wydajne, rozwiązanie z użyciem funkcji ROW_NUMBER() :

with Ponumerowane as (
	select VLAN , ROW_NUMBER() OVER(order by VLAN)  as IdRek,
	 VLAN - ROW_NUMBER() OVER(order by VLAN) as IdZakres
	from dbo.zakres t1 
)
select IdZakres, MIN(VLAN) as VLAN_START, MAX(VLAN) as VLAN_END
from Ponumerowane
group by IdZakres

Zakresy_ciagle_05
Takie rozwiązanie można ubrać w funkcję użytkownika i prezentować scalone zakresy liczb w przyjaznej formie, np. dodatkowo agregując je do postaci skalarnej (FOR XML PATH).


Wyszukiwanie brakujących elementów w zbiorze

Na koniec sytuacja, gdy interesuje nas to, czego nie ma w tabeli. Mogą to być braki numerów zamówień, albo dziury w ciągłym zakresie adresacji urządzeń IP, nadające się do ponownego przydzielenia. Identyfikację brakujących elementów, na przykładzie zbioru inkrementowanego o 1, możemy wykonać na przykład tak :

with cte as (
 
	SELECT (select MIN(VLAN) from dbo.zakres) as VLAN, 
(select MAX(VLAN) from dbo.zakres) as MaxVal
	UNION ALL
 
	-- zakładamy inkrementację + 1 
	SELECT VLAN + 1 , MaxVal
	FROM CTE  c 
	where VLAN < MaxVal
)
select c.VLAN as MissingVlan from cte c left join dbo.zakres t on c.VLAN = t.VLAN
where t.VLAN is null
OPTION (MAXRECURSION 0)

Zakresy_ciagle_06

Grafy, drzewa i hierarchie w SQL

Z grafami można spotkać się nad wyraz często. Takie najprostsze to struktura katalogów na dysku czy hierarchia przełożony-podwładny w firmie.

Bardziej skomplikowane znajdziesz w serwisach społecznościowych – np. drzewa znajomości. W sieciach teleinformatycznych będą to struktury połączeń pomiędzy węzłami. W nawigacji GPS – najkrótsze ścieżki od punktu A-Z itd.

Z punktu widzenia baz danych i tworzenia zapytań do tego typu struktur – zadania z grafami nie są trywialne. Szczególnie, gdy chcemy je rozwiązać za pomocą pojedynczej kwerendy.
W artykule tym, zaprezentuję kilka praktycznych scenariuszy wraz z rozwiązaniami bazującymi na SQL Server 2012. Mam nadzieję, że jeśli szukasz gotowych rozwiązań – uda Ci się zaadoptować prezentowane tutaj przykłady do swoich zastosowań.

W każdym z nich, wyzwaniem było napisanie rozwiązania w postaci pojedynczej kwerendy. Podejście proceduralne jest prostsze w zrozumieniu i może prowadzić do bardziej efektywnych rozwiązań (materializowanie pośrednie, indeksy na tabelach tymczasowych).

Trochę teorii

Patrząc na matematyczną teorię grafów, możemy mieć do czynienia z różnymi typami tych struktur. Na początek zajmiemy się grafami prostymi, wprowadzając przy okazji kilka podstawowych pojęć. Zbudujemy sobie tło do bardziej zaawansowanych scenariuszy.


Graf prosty (acykliczny, nieskierowany)

Graf prosty – to drzewo bez cykli, krawędzie nie są skierowane (nie ma ograniczeń kierunkowych) a pomiędzy każdą parą dowolnych wierzchołków, jest tylko jedna ścieżka. Dodanie jakiejkolwiek nowej krawędzi, spowoduje powstanie cyklu a usunięcie istniejącej doprowadzi do niespójności (podział grafu).

Grafy_Drzewa_SQL_01

W przypadku, gdy jeden z wierzchołków, jest wyszczególniony (korzeń), mówimy o drzewie ukorzenionym. Grafy proste, ukorzenione są łatwe w implementacji w relacyjnych bazach. Tworzenie zapytań do takich struktur nie stwarza większych problemów. Tego typu graf, to na przykład organizacja systemu plikowego lub hierarchia pracownicza – przełożony/podwładny.

W typowej organizacji plików i katalogów zakładamy, że dany obiekt (plik lub katalog) nie może być w dwóch różnych miejscach jednocześnie (pomijając skróty, które mogą tworzyć cykle – o tym później). Do każdego węzła, jest tylko jedna ścieżka, prowadząca ,od korzenia grafu. Patrząc na tą strukturę, całość stanowi jedno spójne drzewo – graf prosty, ukorzeniony.

Grafy_Drzewa_SQL_02

Podobnie w strukturze zatrudnienia. Dany pracownik zazwyczaj nie może mieć na tym samym poziomie dwóch bezpośrednich szefów. Droga eskalacji od podwładnego do przełożonego najwyższego szczebla, jest jedna.

Implementacja takiej struktury w bazie danych może być bardzo prosta. Realizuje się ją zazwyczaj, jako SELF JOIN, czyli złączenie tabeli samej ze sobą.

USE tempdb
GO
 
CREATE TABLE dbo.Folders (
    ID INT NOT NULL PRIMARY KEY IDENTITY(1, 1),
    Folder VARCHAR(100) NOT NULL,
    Parent INT NULL REFERENCES dbo.Folders( ID ) 
);
 
INSERT INTO dbo.Folders ( Folder ) VALUES ('C:');
 
INSERT INTO dbo.Folders ( Folder, Parent )
VALUES  ('Inetpub',1),('Program Files',1),('Windows',1),('wwwroot',2),
('Adobe',3),('MS SQL',3),('Data',7),('system32',4),('Data',9);
 
select * from dbo.Folders

Grafy_Drzewa_SQL_03

Zapytania SQL do takiego grafu, również nie są szczególnie skomplikowane. Wystarczy wykorzystać rekurencję wspólnych wyrażeń tablicowych (CTE Common Table Expressions) i przeszukiwać drzewo w głąb od korzenia do liści.

WITH Paths AS 
(
    SELECT Id, Folder, CAST(null AS VARCHAR(8000)) AS Parent,
           CAST(Folder + '\' AS VARCHAR(8000)) FullFolderName, 0 as Poziom
    FROM dbo.Folders
    WHERE Parent IS NULL   
 
    UNION ALL
 
    SELECT f.Id, f.Folder, p.FullFolderName, 
           CAST(ISNULL(p.Parent, '')  + p.Folder + '\' 
		+  f.Folder + '\'  AS VARCHAR(8000)) , p.Poziom +1
    FROM dbo.Folders f INNER JOIN Paths p
                                ON f.Parent= p.ID
)
SELECT * FROM Paths
Order by FullFolderName

Grafy_Drzewa_SQL_04

Takie podejście, załatwia również sprawę, w sytuacji, gdy mamy do czynienia ze zbiorem grafów prostych (las drzew). Zakotwiczenie CTE, identyfikuje wszystkie grafy i rekurencyjnie rozpina ja analogicznie jak poprzednio. Drzewa możemy ponumerować, do późniejszej analizy.

-- dorzućmy nowe drzewo - dysk D:
Insert into dbo.Folders(Folder) Values('D:');
 
Insert into dbo.Folders ( [Folder], [Parent] )
VALUES('Music',11),('Docs',11),('Mike Oldfield',12),('Tres Lunas',14);
 
WITH Paths AS 
(
    SELECT Id, Folder, CAST(null AS VARCHAR(8000)) AS Parent,
CAST(Folder + '\' AS VARCHAR(8000)) FullFolderName, 0 as Poziom, 
ROW_NUMBER() OVER(ORDER BY FOLDER) as TreeNo
    FROM dbo.Folders
    WHERE Parent IS NULL   
 
    UNION ALL
 
    SELECT f.Id, f.Folder, p.FullFolderName, 
           CAST(ISNULL(p.Parent, '')  + p.Folder + '\' 
		+  f.Folder + '\'  AS VARCHAR(8000)) , p.Poziom +1, TreeNo
    FROM dbo.Folders f INNER JOIN Paths p
                                ON f.Parent= p.ID
)
SELECT * FROM Paths
Order by FullFolderName

Grafy_Drzewa_SQL_05

W SQL Server od wersji 2008, mamy dostępny specjalny typ danych HierarchyId. Pozwala on na tworzenie bardziej zaawansowanych struktur w porównaniu do SELF JOINów. Za jego pomocą, można bardzo łatwo zamodelować scenariusz w którym istotna jest kolejność węzłów na danym poziomie hierarchii.


Graf nieskierowany z cyklami

Sytuacja staje się bardziej złożona, gdy mamy do czynienia z grafami, które posiadają cykle. Jest to typowy przykład architektury sieci teleinformatycznej, w której istnieją redundantne ścieżki w celu zapewnienia protekcji. Innym przykładem z którego korzystasz na co dzień to po prostu siatka połączeń drogowych pomiędzy miastami.

Grafy_Drzewa_SQL_06

Wyszukiwanie ścieżek pomiędzy dowolnymi węzłami takiego grafu, musi uwzględniać możliwość zapętlenia. Dla każdej pary węzłów, może pojawić się wiele ścieżek. Zależnie od stopnia złożoności grafu (liczby węzłów i krawędzi) analiza możliwych dróg, może stanowić nie lada wyzwanie.

Grafy_Drzewa_SQL_07

Skrypt z danymi do przeprowadzenia dalszych ćwiczeń od pobrania tutaj.

Implementacja takiego grafu w relacyjnej bazie danych, może być oparta o dwie tabele – węzłów i krawędzi między nimi. Na początek znajdźmy wszystkie ścieżki z punktu A-Z.

WITH Edges AS (
	-- graf nieskierowany więc bierzemy pod uwagę krawędzi dwukierunkowo
        -- A-Z i Z-A
	SELECT Node1 as Start, Node2 as Koniec, Metric from EDGE
	UNION
	SELECT Node2, Node1 , Metric from EDGE	
),
Paths as 
(
	-- rekurencyjne CTE
        SELECT start , koniec ,  
        CAST('.' + start + '.' + koniec + '.' as varchar(max)) as paths, 1 as Dist
	FROM Edges
 
	UNION ALL
 
	SELECT f.start, t.koniec , CAST(f.paths + t.koniec + '.' as varchar(max)), 
	F.dist+1
	FROM Paths as F join Edges T on 
	--  wykluczenie cykli, czyli nie przechodzimy 
        -- przez żaden wierzchołek dwukrotnie
		case when F.paths like '%.' + T.koniec  + '.%' then 1 else 0 end = 0
		 and f.koniec = T.start
)
SELECT *  
FROM  Paths
WHERE Start = 'A' and Koniec = 'Z'
ORDER BY Dist

Grafy_Drzewa_SQL_08

Powyższe podejście, pomimo że w jednej kwerendzie, jest słabe wydajnościowo i przy dużej liczbie (tysiące) węzłów / krawędzi działa po prostu bardzo wolno. Wystarczy spojrzeć na plan wykonania – przypomina zapytanie prawdziwie skorelowane. Alternatywnym rozwiązaniem jest podejście proceduralne, w którym tworzymy drzewa rozpinające.


Graf skierowany z cyklami i metrykami krawędzi

Wyszukiwanie najkrótszej drogi z punktu A-Z, zazwyczaj wymaga analizy jakości poszczególnych odcinków. Sytuacja taka ma zastosowanie zarówno w sieciach drogowych (autostrady, drogi lokalne), jak również informatycznych. W tych drugich, brane są pod uwagę zazwyczaj parametry jakościowe, czyli pasmo, opóźnienia, jitter. O ile w sieciach teleinformatycznych kierunkowość zazwyczaj jest tematem pomijalnym, o tyle drogi jednokierunkowe, to norma.

Bazując na danych z poprzedniego przykładu, wyznaczmy raz jeszcze najlepszą ścieżkę z A-Z, biorąc pod uwagę kierunkowość krawędzi oraz metryki. Nasz graf będzie wyglądał teraz tak :

Grafy_Drzewa_SQL_09

W tej sytuacji widać, że pomiędzy węzłami A i Z powinny zostać znalezione tylko dwie ścieżki. Ponadto nie istnieje żadna ścieżka powrotna (Z > A). Zmodyfikujemy odrobinę zapytanie z poprzedniego przykładu :

WITH Edges AS (
	-- graf skierowany więc bierzemy drogi takie jakie są
	SELECT Node1 as Start, Node2 as Koniec, Metric from EDGE
),
Paths as 
(
	SELECT start , koniec ,  
        CAST('.' + start + '.' + koniec + '.' as varchar(max)) as paths, 1 as Dist, Metric
	FROM Edges 
 
	UNION ALL
 
	select f.start, t.koniec , CAST(f.paths + t.koniec + '.' as varchar(max)), 
	F.dist+1, F.Metric + T.Metric
	from Paths as F join Edges T on 
                 case when F.paths like '%.' + T.koniec  + '.%' then 1 else 0 end = 0
		 and f.koniec = T.start
),
PathRanking as (
select   *, 
	DENSE_RANK() OVER(Partition BY Start, Koniec Order by Metric, Dist) as RNK
from Paths)
Select * from PathRanking
where start = 'A' and koniec = 'Z';

Grafy_Drzewa_SQL_10

Obydwie kosztują tyle samo (suma metryk jest identyczna), ale droga bezpośrednia A>Z ma mniej skoków, stąd zostaje wybrana jako najlepsza.


Las drzew (grafów) nieskierowanych, nieukorzenionych

Bazując na powyższej metodzie, możemy pokusić się o rozwiązanie jeszcze jednego problemu. Zadaniem nietrywialnym, jest analiza zbioru grafów nieskierowanych bez korzenia. Tego typu struktury, spotkać możesz na przykład w serwisach społecznościowych.

Grafy_Drzewa_SQL_11

Wyobraźmy sobie prostą tabelę powiązań (znajomości) pomiędzy użytkownikami. Pytanie w jaki sposób, określić czy dana osoba należy do jakiegoś kręgu (grupy znajomości mogą się tworzyć samoczynnie, bez dodatkowych relacji). Daną grupę, wyznaczają wszystkie osoby, które są w jakikolwiek sposób ze sobą powiązane (nawet pośrednio). Czyli tak naprawdę, musimy zidentyfikować przypisanie każdej krawędzi do określonego drzewa.

Rozwiązaniem w postaci jednej kwerendy, może być modyfikacja znanego już algorytmu wyznaczania ścieżek.

WITH Znajomi as 
(
	select * from (
	VALUES  ('a','b'),('a','i'),('b','i'),('c','j'),('d','j'),
		('e','k'),('f','k'),('g','l'),('h','l'),('e','l')--,('a','e')
 
	) as Tab(a,b)
 
), 
Edge as (
 
	select l.a as Start , cast( l.b  as varchar) as Koniec, 1 as dist 
	from Znajomi l
	union all 
		select cast( l.b  as varchar) , l.a, 1
	from Znajomi l
),
Paths as 
(
	select start , koniec ,  CAST('.' + cast(start as varchar(10))+ '.' 
		+ cast(koniec  as varchar(10)) + '.' as varchar(max)) as path, dist
	from Edge
 
	UNION ALL
 
	select f.start, t.koniec , 
		CAST(f.path + cast(t.koniec as varchar(10)) + '.' as varchar(max)), F.dist+1
	from Paths as F join Edge T on 
	case when F.path like '%.' + cast(T.koniec as varchar(10)) + '.%' then 1 else 0 end = 0
		and f.koniec = T.start
)
, 
Grupy as (
 
   select c.a, c.b , SUBSTRING(max(path),2,CHARINDEX('.',max(path),2)-2) as GRID
   from  Znajomi c left join Paths    r  on r.Path like '%' + c.a + '.' +  
   cast( c.b  as varchar) + '%' or r.Path like '%' + cast( c.b  as varchar) + '.' + c.a  + '%' 
   group by c.a, c.b 
)
select a, b, DENSE_RANK() OVER(order by GRID) as Grupa from Grupy

Grafy_Drzewa_SQL_12

Zauważ, że wykorzystałem tu pewne fundamentalne i oczywiste założenie. W danym drzewie, mamy możliwość dojścia do każdego węzła. W przeciwnym razie, dany graf byłby niespójny i stanowiłby tak naprawdę dwa lub więcej drzew.

W związku z tym, w ostatnim CTE (Grupy), grupuję po maksymalnej (równie dobrze mogłaby to by być minimalna) ścieżce, która zawiera identyfikatory węzłów. Na podstawie tego największego identyfikatora węzła, określam przynależność do grupy.


Podsumowanie

Zaprezentowane w tym artykule rozwiązania to tylko jedne z możliwych podejść. Proceduralnie można by je było rozwiązać znacznie prościej i szybciej. Jeśli masz propozycję rozwiązania tych zadań w bardziej efektywny sposób za pomocą jeden kwerendy – zapraszam do dyskusji !

Tematyka grafów jest znacznie szerzej (świetnie) opisana w książce Itzika Ben Gana „Inside Microsoft SQL Server 2008: T-SQL Querying” – polecam wszystkim.

Generowanie zbioru – wektor dyskretnych i ciągłych wartości

W praktyce pisania zapytań SQL, nieraz spotkałem się z potrzebą wygenerowania automatycznej tabeli. Na przykład osi czasu z uwzględnieniem każdego dnia albo wektora kolejnych liczb z zadanego przedziału.

W artykule tym, zademonstruję jak wygenerować za pomocą CTE, zbiór zawierający inkrementowane elementy z określonego przedziału.

Generowanie wektora danych za pomocą CTE

Zastosowań takiego ciągłego, dyskretnego zbioru jest wiele. Rozważmy taki scenariusz.

Chcę utworzyć raport, zagregowanej sumy wszystkich złożonych zamówień w zadanym przedziale dat. Istotnym dla mnie jest zachowanie skali czasu – tak aby pokazane były na niej wszystkie dni z zadanego okresu. Również te, w których nie spłynęło ani nie zostało zrealizowane żadne zamówienie. Chcę także na tym samym wykresie pokazać informacje o realizacji zamówień.


To co potrzebuję na początek, to tabeli w postaci wektora ze wszystkimi kolejnymi dniami np. od ‚2014-02-01’ do ‚2014-02-14’. Do takiego zbioru (osi czasu) będę odnosił się analizując już szczegółowo daty zamówień.

Można stworzyć taką tabelę za pomocą wielu operacji UNION (niewygodne). Można też ładować w pętli wartości do tabeli tymczasowej. Nie są to jednak „ładne” i uniwersalne sposoby.

Do utworzenia takiego ciągłego zbioru, idealnie nadaje się rekurencyjne CTE. W SQL Server 2012, można za ich pomocą tworzyć nieograniczone (rekursywnie) zbiory. Opisuję w detalach strukturę rekurencyjnych CTE w ramach kursu SQL.

Kwerenda, która wygeneruje interesujący mnie zbiór, będzie wyglądała tak :

WITH Daty AS
(
	-- Rekurencyjne Common Table Expression 
          -- domyślnie max 100 przebiegów rekurencyjnych, czyli będzie działało 
          -- do 2014-05-12 :) potem trzeba użyć MAXRECURSION
 
	SELECT cast('2014-02-01' as SmallDatetime) as Data , 1 as Liczba
 
	UNION ALL
 
	SELECT Data+1, Liczba+1
	FROM Daty a
	WHERE a.Data < getdate()-1
 
)
SELECT * FROM Daty

CTE_wektor_wartosci

Szczególnie fajną rzeczą w CTE, jest możliwość korzystania z nich w różnych strukturach – np. widokach. Tworzenia tabel tymczasowych i technik programistycznych nie wpleciemy w zwykły widok.

Rekurencyjne CTE są domyślnie ograniczone do 100 przebiegów. Możemy jednak sterować ich maksymalną liczbą, stosując opcję MAXRECURSION.

Parametr ten przyjmuje wartości od 0 (nieograniczona ilość przebiegów) do 32767. Tworzenie np. zbioru (wektoru) z 1000 kolejnych liczb, wymaga zastosowania opcji MAXRECURSION. W przeciwnym razie, po wykonaniu setnego (domyślnie) przebiegu rekurencyjnego, otrzymamy błąd :

Msg 530, Level 16, State 1, Line 3
The statement terminated. The maximum recursion 100 has been exhausted before statement completion.

Zatem jeśli potrzebujemy większy wektor, na przykład wspomniany 1000-elementowy, to utworzymy go w ten sposób :

with Liczby as 
(
	select  1 as Liczba
	UNION ALL
	select Liczba+1
	from Liczby a where a.Liczba < 1000
 
)
Select * from Liczby
OPTION (MAXRECURSION 0)
Liczba
-----------
1
2
3
. . .
998
999
1000

(1000 row(s) affected)

Wróćmy jednak do naszego scenariusza. Skrypt generujące przykładowe dane, z których korzystam w dalszej części znajdziesz tutaj.

Kwerenda odnosiła się będzie bezpośrednio do utworzonego wektora czasu (pierwsze CTE – Daty). Jest on główną osią na której pokazywać będę zagregowane i narastające sumy zleceń.

with Daty as 
(
	SELECT cast('2014-02-01' as date) as Data 
 
	UNION ALL
 
	SELECT DateAdd(dd,1,a.Data)
	from Daty a
	where a.Data < getdate()-1
 
),
Orders_raport as (
 
	SELECT a.Data,  count(distinct o.Order_id) as Orders_QTY, 
	     SUM(count(distinct o.Order_id)) OVER(order by a.Data)  as Agg_Orders_Qty,
	     count(distinct o2.Order_id) as Comp_Orders_QTY, 
	     SUM(count(distinct o2.Order_id)) OVER(order by a.Data)  as Agg_Comp_Order_qty
	FROM Daty a 
	     left join dbo.Orders o on a.Data =  cast(o.create_date as date) 
                         and cast(o.create_date as date) > '2014-01-31'
	      left join dbo.Orders o2 on a.Data = cast(o2.completion_date as date) 
                         and cast(o2.create_date as date) > '2014-01-31'
	GROUP BY a.Data
 
) 
SELECT *
FROM Orders_raport
ORDER BY  DATA

CTE_wektor_wartosci2

Teraz na podstawie tak przetworzonych danych, łatwo np. w Excelu wygenerować wykres – co należy podkreślić – w ciągłej dziedzinie czasu.

CTE_wektor_wartosci3

CTE – Common Table Expressions

CTE, czyli wspólne wyrażenia tablicowe, zostały wprowadzone po raz pierwszy w SQL Server 2005, jako rozszerzenie składni T-SQL.

Upraszczają i poprawiają przejrzystość kodu SQL. W tym zakresie, ich stosowanie nie ma wpływu na wydajność zapytań, tylko na jego czytelność. Oprócz funkcji czysto estetycznej, posiadają jeszcze jedną, specjalną właściwość – ich struktura pozwala na realizację rekurencji.


Wspólne wyrażenia tablicowe CTE – czytelność kodu

CTE, możemy stosować praktycznie wszędzie – w widokach, funkcjach, procedurach składowanych, skryptach etc. Składnia jest prosta i omówię ją na przykładzie :

-- definicja wyrażenia tablicowego o nazwie Sales_CTE
WITH Sales_CTE  (SalesPersonID, NumberOfOrders, MaxDate)
AS
(
    SELECT top 5 SalesPersonID, COUNT(*) , MAX(OrderDate) 
    FROM Sales.SalesOrderHeader
    GROUP BY SalesPersonID
    ORDER BY 2 ASC
)
-- bezpośrednio po definicji, kwerenda odwołująca się m.in do tego CTE
SELECT P.FirstName, P.LastName, c.NumberOfOrders, c.MaxDate
FROM Sales_CTE c left join Person.Person AS P
    ON c.SalesPersonID = P.BusinessEntityID

CTE_01
Definicję CTE otwiera słowo kluczowe WITH z nazwą zbioru, który zostanie za jej pomocą utworzony. Do niej będziemy odwoływać się w kwerendzie, tak jak do zwykłej tabeli.

Obowiązują te same reguły jak w przypadku każdego obiektu tabelarycznego, do którego chcemy się w jakikolwiek sposób odnosić w zapytaniu.

Nazwy kolumn (atrybutów) muszą być unikalne w ramach zbioru. Jeśli określimy je w „ciele” wyrażenia tablicowego, nie jest wymagane ich ponowne nazywanie w klauzuli WITH – co jest często stosowanym skrótem. W kodzie produkcyjnym, zalecane jest jednak jawne wyszczególnianie nazw.

WITH Sales_CTE
AS
(   -- określenie unikalnych nazw kolumn
    SELECT SalesPersonID, COUNT(*) as NumberOfOrders ,
 MAX(OrderDate) as MaxDate
    FROM Sales.SalesOrderHeader
    GROUP BY SalesPersonID
)
SELECT * from Sales

Do raz zdefiniowanego CTE, możemy się odnosić wiele razy w kwerendzie z którą jest związany. Zakres widoczności jest bardzo wąski i obejmuje tylko i wyłącznie zapytanie następujące po nim, ale w pełnym zakresie. Dokładnie tak jakbyśmy odpytywali zbiór, tabelę lub widok, określoną w tym przypadku przez CTE.

Możemy definiować kilka wyrażeń tablicowych i co istotne, widoczne są one nie tylko w kwerendzie powiązanej z WITH, ale również w kolejno określanych CTE (jeśli jest ich więcej niż 1)

WITH CTE_1 -- definicja pierwszego CTE
AS
(
    SELECT SalesPersonID, COUNT(*) as NumberOfOrders ,
	MAX(OrderDate) as MaxDate
    FROM Sales.SalesOrderHeader
    GROUP BY SalesPersonID
),  
CTE_2 -- definicja drugiego CTE, możemy odwołaś się już do CTE_1
AS
(
    SELECT SalesPersonID, NumberOfOrders, MaxDate
    FROM CTE_1 
    WHERE NumberOfOrders  < 200 
)
 -- tutaj możemy odwołać się do wszystkich CTE określonych w WITH
SELECT top 10 CTE_1.*, CTE_2.* 
FROM CTE_1 LEFT JOIN CTE_2
	ON CTE_1.SalesPersonID= CTE_2.SalesPersonID

CTE_02
CTE są szczególnie użyteczne w przypadku rozbudowanych zapytań, łączących wiele tabel, które chcemy użyć w kolejnym kroku, wykonując na nich dodatkowe operacje.

Inny przykład zastosowań to skomplikowane wyrażenia w klauzuli SELECT (np. z CASE WHEN) zapytania, które również chcemy dalej przetwarzać, np. połączyć wewnętrznie z samą sobą. Nie będziemy musieli powielać tego samego kodu zapytania lub materializować (choć czasem się opłaca) tabeli pośredniej.

CTE jest po prostu wygodnym opakowaniem, tabel pośrednich, dzięki któremu łatwiej odnaleźć się w kodzie.

Trzeba pamiętać, że słowo kluczowe WITH, używane jest również do innych celów np. do przekazywania hintów (podpowiedzi dla silnika relacyjnego) w zapytaniach. Z tego względu, jeśli chcemy definiować CTE w ramach skryptu zawierającego kilka odrębnych komend T-SQL np. w procedurze składowanej, konieczne jest jawne określania końca poleceń poprzedzających – czyli stosowanie znaku średnika, przynajmniej na końcu polecania SQL poprzedzającego CTE.

Jeśli o tym zapomnimy – parser, zasygnalizuje błąd, bo będzie traktował słowo kluczowe WITH jako kontynuację poprzedniej komendy SQL. Stosowanie ‚;’ jest jedną z dobrych praktyk pisania poleceń SQL i nic nie stoi na przeszkodzie, aby umieszczać je zawsze na koniec komendy.

Rekurencyjne wyrażenia tablicowe (recursive CTE)

Interesującą i bardzo użyteczną właściwością wspólnych wyrażeń tablicowych, jest możliwość stosowania rekurencji w ich wnętrzu. Tego typu funkcjonalność, wykorzystujemy w zbiorach z określoną hierarchią elementów (pracownicy / przełożeni, struktura folderów na dysku, wątków na forum itp.). Rekurencja pozwala rozwiązywać skomplikowane zadania, typu wyznaczanie drzew rozpinających, grafów.

Składnię rekurencyjnych wyrażeń CTE, przeanalizujemy na przykładzie hierarchicznej struktury zatrudnienia w firmie Northwind:

USE NORTHWIND
GO
WITH recursive_CTE
AS
(
        -- zapytanie zakotwiczające, określa korzeń, najwyższy poziom hierarchii
        -- w tym przypadku tylko TOP Management (nie mają przełożonych)
	select EmployeeId, ReportsTo, FirstName, LastName, 0 as Organization_Level 
        from dbo.Employees
	where ReportsTo is null
 
        -- operator UNION ALL – obowiązkowy w rekurencji, 
        -- łączący ostetecznie wyniki z kolejnych iteracji (przebiegów) wykonania
 
	UNION ALL
 
        -- Zapytanie rekurencyjne działające zawsze na zbiorze wynikowym z kroku n-1. 
        -- Zwróć uwagę, że jest powiązane po nazwie wyrażenia tablicowego CTE
 
	select e.EmployeeId, e.ReportsTo, e.FirstName, e.LastName, Organization_Level + 1
	from dbo.Employees e inner join recursive_CTE r 
             on e.ReportsTo = r.EmployeeId
)
Select * from recursive_CTE

CTE_03
Definicja wyrażeń rekurencyjnych CTE składa się z 3 elementów.

  • rozpoczyna się przez określenie zapytania zakotwiczającego. Jest to zazwyczaj zbiór elementów stanowiących korzeń (lub korzenie). W naszym przykładzie jest to TOP management czyli pracownicy, którzy do nikogo nie raportują. Od tych elementów będziemy rekurencyjnie „rozpinać” nasze struktury drzew.
  • Zapytanie rekursywne – skorelowane z wynikiem zwracanym przez zapytanie poprzednie. To tu odwołujemy się do struktury hierarchicznej. W naszym przypadku, w pierwszym kroku jest to powiązanie TOP managementu z bezpośrednimi podwładnymi. W następnym kroku, będzie to powiązanie tych bezopśrednich podwładnych z ich własnymi podwładnymi czyli kolejny poziom niżej itd.
    Operator UNION ALL łączy wszystkie przebiegi w finalny zbiór wynikowy. Ważne jest, aby zrozumieć, że w każdym kroku działamy tylko na zbiorze zwracanym przez krok poprzedni (u nas to będzie za każdym razem, zbiór pracowników, kolejnego, niższego szczebla).
  • – Niejaweny warunek zakończenia rekurencji. Jeśli zapytanie rekurencyjne, skorelowane, nie zwróci żadego elementy, działanie CTE zostaje porzerwane.

Istnieje kilka istotnych faktów związanych z tą strukturą. Warunek zakończenia jest niejawny, dlatego jeśli w naszych danych występują cykle, i rekurencja wpadnie w taką pętle, zapytanie CTE zostanie przerwane dopiero po osiągnięciu maksymalnego poziomu – 32767 przebiegów.

Może to trwać bardzo długo. Na szczęście możemy jawnie określić maksymalną ilość wykonywanych przebiegów za pomocą opcji MAXRECURSION :

WITH recursive_CTE
AS
(       
	select EmployeeId, ReportsTo, FirstName, LastName, 0 as Organization_Level 
        from dbo.Employees
	where ReportsTo is null
 
	UNION ALL
 
	select e.EmployeeId, e.ReportsTo, e.FirstName, e.LastName, Organization_Level + 1
	from dbo.Employees e inner join recursive_CTE r on e.ReportsTo = r.EmployeeId
)
Select * from recursive_CTE
option (maxrecursion 1)

CTE_04
W sytuacji gdy CTE samo nie zakończy działania na n-tym przebiegu, czyli jeśli zwróci w n-tym kroku niepusty zbiór, opcja ‚MAXRECURSION n’ wymusi jej zakończenie. Zostanie również zwrócona informacji o błędzie :

Msg 530, Level 16, State 1, Line 2
The statement terminated. The maximum recursion 1 has been exhausted before statement completion.

Jeśli chcemy umieszczać tego typu „hamulce”, trzeba zapewnić obsługę błędów (np. za pomocą try catch). Maksymalna liczba przebiegów które możemy z góry określić za pomocą MAXRECURSION to 32767. Ewentualnie pozostaje opcja „infinitive” czyli MAXRECURSION = 0.