W ostatnich dniach natrafiłem na ciekawy problem, którym chciałbym się podzielić. Rzecz dotyczy określania przedziałów czasu kiedy jakieś, nazwijmy to uszeregowane zdarzenia, pozostają ze sobą w relacji ciągłości trwania. Brzmi to może skomplikowanie więc śpieszę z wyjaśnieniem. Spróbujmy wyobrazić sobie wypożyczalnię samochodów gdzie klienci mogą rezerwować pojazdy do użytku na całe dni (przyjmijmy takie uproszczenie – rozwiązanie problemu nie będzie się zbytnio różniło jeśli zejdziemy z dokładnością do minut czy nawet sekund). Nas natomiast interesuje określenie sumarycznych przedziałów czasu kiedy pojazd był wypożyczony.

Aby lepiej poczuć problem zacznijmy przygotowywać sobie pole do zabawy. Zacznijmy od przygotowania tabeli (w celu prezentacji użyję tradycyjnie zmiennej tabelarycznej aby podczas zabawy niepotrzebnie nie tworzyć sobie obiektów w bazie) i wypełnienia jej przykładowymi danymi. Od razu dodam, że wartości NULL w polach daty zwrotu oznaczają, że pojazd nie został jeszcze oddany.

declare @rentals as table (
     idCar int,
     idClient int,
     startDate date,
     stopDate date
 );

 insert into @rentals values
 (1, 1, '20210501', '20210503'),
 (2, 1, '20210504', '20210510'),
 (1, 1, '20210511', '20210514'),
 (3, 1, '20210515', '20210520'),
 (2, 1, '20210521', '20210523'),
 (1, 1, '20210524', '20210527'),
 (3, 1, '20210528', null),
 (3, 2, '20210501', '20210502'),
 (2, 2, '20210503', '20210503'),
 (3, 2, '20210505', '20210509'),
 (3, 2, '20210512', '20210514'),
 (1, 2, '20210515', '20210518'),
 (2, 2, '20210519', '20210520'),
 (1, 2, '20210521', '20210521'),
 (2, 2, '20210527', '20210530'),
 (2, 3, '20210501', '20210502'),
 (3, 3, '20210503', '20210503'),
 (1, 3, '20210504', '20210510'),
 (2, 3, '20210513', '20210518'),
 (3, 3, '20210521', '20210526'),
 (1, 3, '20210531', null);

Moglibyśmy oczywiście pobawić się w dowiązania tabel użytkowników i pojazdów ale na potrzeby tego zagadnienia jest to zupełnie zbyteczne. Wystarczy zwrócić uwagę, iż mamy trzy pojazdy o identyfikatorach kolejno 1, 2 i 3 oraz analogicznie trzech klientów również identyfikowanych jako 1, 2 i 3.

To co moglibyśmy spróbować wydobyć z takich danych to informacja o czasie użytkowania poszczególnych pojazdów oraz informacja o okresach wypożyczeń poszczególnych klientów (różnica pomiędzy jednym a drugim zestawieniem będzie bardzo niewielka).

W jaki sposób zabrałem się do tego zagadnienia? Intuicyjnie przeczuwałem, że przydatna będzie rekurencja (o której pisałem m.in. w tym wpisie). Brakowało mi w niej jednak jakiegoś prostego powiązania pozwalającego zbudować zależności. Ponieważ zestawienie dat musi wiązać się z grupowaniem choćby po identyfikatorach pojazdów dlatego wziąłem również pod uwagę funkcje okna. W ten sposób doszedłem do pierwszego etapu, który pozwolił mi uszeregować dane i określić różnice czasu pomiędzy nimi. Efekt widać na poniższym zapytaniu.

select idCar, 
idClient, 
startDate, 
stopDate, 
datediff(    day, 
             lag (stopDate, 1, '19000101') 
                 over (  partition by idCar order by startDate asc), 
             startDate) as diff
from @rentals
order by idCar, startDate

Skąd data 1 stycznia 1900 roku? To taki stosowany przeze mnie trick ułatwiający pracę z datami. Zamiast uwzględniać w warunkach wartości NULL o wiele łatwiej jest przyjąć umowne daty odległe w czasie zarówno w przeszłości jak i przyszłości (w zależności od ich znaczenia). Efekt zapytania widać poniżej.

Jak widać w przypadku zachowania ciągłości użycia pojazdu w kolumnie diff pojawia się wartość 1. Można z tego wyciągnąć słuszny wniosek, iż każda wartość diff inna niż 1 oznacza początek kolejnego okresu użytkowania pojazdu. Możemy wykorzystać ten fakt budując dalej zapytanie rekurencyjne – dane określające początek okresu użytkowania będą inicjować naszą rekurencję. Gotowe zapytanie może wyglądać tak jak poniżej. 

with rentals as (
     select idCar, 
     startDate, 
     stopDate, 
     datediff(   day, 
                 lag (stopDate, 1, '19000101') 
                     over (  partition by idCar 
                             order by startDate asc), 
                 startDate) as diff
     from @rentals
 ), recursion as (
     select idCar, startDate, stopDate
     from rentals
     where diff > 1
     union all
     select c.idCar, c.startDate, r.stopDate
     from rentals as r
     inner join recursion as c on r.idCar = c.idCar 
          and datediff(day, c.stopDate, r.startDate) = 1
     where r.diff = 1
 )
 select idCar, startDate, max(stopDate) as stopDate
 from recursion
 group by idCar, startDate
 order by idCar, startDate

Jak widać wcześniejsze zapytanie, lekko zmodyfikowane (w tym zestawieniu nie potrzebujemy interesować się poszczególnymi klientami) wydzieliłem do oddzielnej sekcji CTE, zapytanie rekurencyjne natomiast do kolejnego. Nie wspominałem o tym wcześniej ponieważ było to dla mnie oczywiste ale dla kogoś może być zaskoczeniem, że zapytanie rekurencyjne może być zbudowane jako element większego zapytania wykorzystującego inne sekcje CTE. rekurencja wymaga elementu CTE ale nie musi to być jedyny taki element w zapytaniu.

Samo zapytanie rekurencyjne, opisane w sekcji o nazwie recursion, składa się z dwóch części. Pierwsza, inicjująca, zawiera dane zawierające początek każdego okresu czasu (czyli dane dla których diff jest większy niż 1). Drugi natomiast dołącza poprzez unię dane gdzie diff jest równy 1. Bardzo ważnym elementem, który szczególnie polecam uwadze to warunek złączenia. Ponieważ operujemy na danych grupowanych po identyfikatorach pojazdów to bardzo ważne jest aby przede wszystkim łączyć dane tych samych pojazdów. Drugi warunek jest natomiast dosyć intuicyjny – dokonujemy złączenia rekordu gdzie różnica diff pomiędzy obydwoma rekordami wynosi 1.

Warto wspomnieć w tym miejscu, że złączenie działa poprawnie dlatego, iż istnieje nie więcej niż jeden rekord, który można złączyć. Wynika to z logiki samego problemu – pojazd nie może być wypożyczony w tym samym okresie dwóm różnym klientom. Jest to dosyć oczywiste ale należy o tym pamiętać i w razie potrzeby odpowiednio rozbudować warunki złączenia w rekurencji.

W jaki sposób budowane są okresy czasu? Otóż w każdej iteracji dla pierwotnego identyfikatora pojazdu oraz czasu rozpoczęcia okresu czasu ustawiamy datę zakończenia na zgodną z aktualnym złączeniem. Skoro okresy są sklejone i zapewniają ciągłość to możemy niejako w każdej iteracji wydłużyć czas trwania okresu do końca okresu określonego przez kolejny rekord złączenia. Na samym końcu wystarczy już tylko pogrupować dane według identyfikatora pojazdu i czasu rozpoczęcia okresu (jest to poniekąd identyfikator tego okresu) wybierając maksymalną wartość daty zakończenia (każda iteracja dodaje kolejny rekord do wyniku – ten z najdłuższym okresem dla grupy stanowi interesującą nas odpowiedź). Wynik działania tego zapytania możemy obejrzeć poniżej.

Można porównać sobie wyniki z wcześniejszymi danymi. Zapytanie zwróciło nam minimalną liczbę ciągłych okresów czasu kiedy każdy z pojazdów był wypożyczany.

Jeśli lekko zmodyfikujemy nasze zapytanie to możemy otrzymać podobne zestawienie ale nie dla pojazdów tylko dla klientów. Wystarczy oczywiście podmienić identyfikator pojazdu na identyfikator klienta.

with rentals as (
     select idClient, 
     startDate, 
     stopDate, 
     datediff(   day, 
                 lag (stopDate, 1, '19000101') 
                     over (  partition by idCar 
                             order by startDate asc), 
                 startDate) as diff
     from @rentals
 ), recursion as (
     select idClient, startDate, stopDate
     from rentals
     where diff > 1
     union all
     select c.idClient, c.startDate, r.stopDate
     from rentals as r
     inner join recursion as c on r.idClient = c.idClient 
          and datediff(day, c.stopDate, r.startDate) = 1
     where r.diff = 1
 )
 select idClient, startDate, max(stopDate) as stopDate
 from recursion
 group by idClient, startDate
 order by idClient, startDate

Efektem tego zapytania będzie poniższy widok.

Na koniec podpowiem jeszcze, że dla większych zbiorów danych zapytanie może się dodatkowo skomplikować. Poza zapewnieniem odpowiedniej struktury indeksów będę proponował jeszcze ograniczanie danych do konkretnego okresu czasu (np. miesiąca). Zapytania wykorzystujące rekurencję jako jeden z etapów potrafią bowiem istotnie wpłynąć na czas wykonania samego zapytania.